Skip to content

Helpers

Quantum Algebra

QuantumCombinatorics

Source code in helpers\quantum_algebra.py 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class QuantumCombinatorics:
    def __init__(self):
        # Cache to store previously computed q-binomials: keys are (n, k)
        self.binomial_cache = {}
        self.multinomial_cache = {}

    def _add_polynomials(self, p1, p2):
        """Element-wise addition of two polynomials."""
        length = max(len(p1), len(p2))
        result = [0] * length
        for i in range(len(p1)):
            result[i] += p1[i]
        for i in range(len(p2)):
            result[i] += p2[i]
        return result

    def _multiply_polynomials(self, p1, p2):
        """Multiplies two polynomials using discrete convolution."""
        if not p1 or not p2:
            return []
        result = [0] * (len(p1) + len(p2) - 1)
        for i, c1 in enumerate(p1):
            for j, c2 in enumerate(p2):
                result[i + j] += c1 * c2
        return result

    def q_binomial(self, n, k):
        """
        Computes the q-binomial coefficient (n choose k)_q.
        Returns a list of coefficients.
        """
        # Base cases
        if k < 0 or k > n:
            return [0]
        if k == 0 or k == n:
            return [1]  # Equals 1 (q^0)

        # Check cache
        if (n, k) in self.binomial_cache:
            return self.binomial_cache[(n, k)]

        # Recurrence: binom(n, k) = binom(n-1, k-1) + q^k * binom(n-1, k)
        left_term = self.q_binomial(n - 1, k - 1)
        right_term = self.q_binomial(n - 1, k)

        # Multiplying by q^k means shifting the polynomial array by k zeros
        shifted_right = [0] * k + right_term

        # Add them together and cache the result
        result = self._add_polynomials(left_term, shifted_right)
        self.binomial_cache[(n, k)] = result

        return result

    def q_multinomial(self, n, k_list):
        """
        Computes the q-multinomial coefficient.
        k_list is a list of the bottom parameters [k_1, k_2, ..., k_m].
        """
        if sum(k_list) != n:
            raise ValueError("The sum of elements in k_list must equal n.")

        result = [1]
        current_sum = k_list[0]

        # Factor into a product of q-binomials:
        # binom(k1+k2, k2) * binom(k1+k2+k3, k3) * ... * binom(n, k_m)
        for k_i in k_list[1:]:
            current_sum += k_i
            binom = self.q_binomial(current_sum, k_i)
            result = self._multiply_polynomials(result, binom)

        return result

    def get_multinomial(self, d):
        d_tuple = tuple(sorted(d))
        if d_tuple not in self.multinomial_cache:
            self.multinomial_cache[d_tuple] = self.q_multinomial(sum(d), list(d))
        return self.multinomial_cache[d_tuple]

    def format_polynomial(self, poly):
        """Helper to print the array as a readable mathematical string."""
        terms = []
        for power, coeff in enumerate(poly):
            if coeff == 0:
                continue
            if power == 0:
                terms.append(str(coeff))
            elif power == 1:
                terms.append(f"{coeff if coeff > 1 else ''}q")
            else:
                terms.append(f"{coeff if coeff > 1 else ''}q^{power}")
        return " + ".join(terms) if terms else "0"

format_polynomial(poly)

Helper to print the array as a readable mathematical string.

Source code in helpers\quantum_algebra.py 
81
82
83
84
85
86
87
88
89
90
91
92
93
def format_polynomial(self, poly):
    """Helper to print the array as a readable mathematical string."""
    terms = []
    for power, coeff in enumerate(poly):
        if coeff == 0:
            continue
        if power == 0:
            terms.append(str(coeff))
        elif power == 1:
            terms.append(f"{coeff if coeff > 1 else ''}q")
        else:
            terms.append(f"{coeff if coeff > 1 else ''}q^{power}")
    return " + ".join(terms) if terms else "0"

q_binomial(n, k)

Computes the q-binomial coefficient (n choose k)_q. Returns a list of coefficients.

Source code in helpers\quantum_algebra.py 
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def q_binomial(self, n, k):
    """
    Computes the q-binomial coefficient (n choose k)_q.
    Returns a list of coefficients.
    """
    # Base cases
    if k < 0 or k > n:
        return [0]
    if k == 0 or k == n:
        return [1]  # Equals 1 (q^0)

    # Check cache
    if (n, k) in self.binomial_cache:
        return self.binomial_cache[(n, k)]

    # Recurrence: binom(n, k) = binom(n-1, k-1) + q^k * binom(n-1, k)
    left_term = self.q_binomial(n - 1, k - 1)
    right_term = self.q_binomial(n - 1, k)

    # Multiplying by q^k means shifting the polynomial array by k zeros
    shifted_right = [0] * k + right_term

    # Add them together and cache the result
    result = self._add_polynomials(left_term, shifted_right)
    self.binomial_cache[(n, k)] = result

    return result

q_multinomial(n, k_list)

Computes the q-multinomial coefficient. k_list is a list of the bottom parameters [k_1, k_2, ..., k_m].

Source code in helpers\quantum_algebra.py 
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
def q_multinomial(self, n, k_list):
    """
    Computes the q-multinomial coefficient.
    k_list is a list of the bottom parameters [k_1, k_2, ..., k_m].
    """
    if sum(k_list) != n:
        raise ValueError("The sum of elements in k_list must equal n.")

    result = [1]
    current_sum = k_list[0]

    # Factor into a product of q-binomials:
    # binom(k1+k2, k2) * binom(k1+k2+k3, k3) * ... * binom(n, k_m)
    for k_i in k_list[1:]:
        current_sum += k_i
        binom = self.q_binomial(current_sum, k_i)
        result = self._multiply_polynomials(result, binom)

    return result

Find Loops

findpathwithloops(num, denom)

returns (path, loops)

Source code in helpers\findloops.py 
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
def findpathwithloops(num, denom):
    "returns (path, loops)"
    path = findpath(num, denom)
    pathwithloops = []
    iter = 1
    end = len(path) - 1
    index = 0
    while path[index] != path[end]:
        nextindex = index + iter
        cur = path[index]
        nxt = path[nextindex]
        index += iter
        if cur > num and nxt > num:
            if num > denom or cur + nxt == denom + (2 * num) + 1:
                pathwithloops.append("R")
                continue
            pathwithloops.append("C")
            continue
        if (cur > num and nxt <= num) or (cur <= num and nxt > num):
            pathwithloops.append("T")
            continue
        if  denom > num or cur + nxt == num + 1:
            pathwithloops.append("L")
            continue
        pathwithloops.append("C")
    return path, pathwithloops

Tangle State

TangleState

Keeps track of the orientation of a tangle.

Orientation is one of UP, OP, RI. The points are a permutation of Y, X-, X+.

Source code in helpers\tanglestate.py 
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class TangleState():
    """Keeps track of the orientation of a tangle.

    Orientation is one of UP, OP, RI.
    The points are a permutation of Y, X-, X+.
    """
    def __init__(self):
        self.orient = "UP"
        self.points = ("Y", "X-", "X+")

    def set_points(self, points):
        self.points = points
        if self.points[0] == "X+":
            self.orient = "RI"
        if self.points[1] == "X+":
            self.orient = "OP"
        if self.points[2] == "X+":
            self.orient = "UP"

    def t_twist(self):
        """Updates the state after a top twist """
        self.points = (self.points[1], self.points[0], self.points[2])
        if self.points[0] == "X+":
            self.orient = "RI"
        if self.points[1] == "X+":
            self.orient = "OP"
        if self.points[2] == "X+":
            self.orient = "UP"

    def r_twist(self):
        """Updates the state after a right twist"""
        self.points = (self.points[0], self.points[2], self.points[1])
        if self.points[0] == "X+":
            self.orient = "RI"
        if self.points[1] == "X+":
            self.orient = "OP"
        if self.points[2] == "X+":
            self.orient = "UP"

r_twist()

Updates the state after a right twist

Source code in helpers\tanglestate.py 
64
65
66
67
68
69
70
71
72
def r_twist(self):
    """Updates the state after a right twist"""
    self.points = (self.points[0], self.points[2], self.points[1])
    if self.points[0] == "X+":
        self.orient = "RI"
    if self.points[1] == "X+":
        self.orient = "OP"
    if self.points[2] == "X+":
        self.orient = "UP"

t_twist()

Updates the state after a top twist

Source code in helpers\tanglestate.py 
54
55
56
57
58
59
60
61
62
def t_twist(self):
    """Updates the state after a top twist """
    self.points = (self.points[1], self.points[0], self.points[2])
    if self.points[0] == "X+":
        self.orient = "RI"
    if self.points[1] == "X+":
        self.orient = "OP"
    if self.points[2] == "X+":
        self.orient = "UP"

continuedfrac(a, b)

Computes the continued fraction expansion of a/b.

Source code in helpers\tanglestate.py 
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def continuedfrac(a, b): 
    """Computes the continued fraction expansion of a/b."""
    X = []
    num = a
    denom = b
    if num >= b:
        c = num // denom
        X.append(c)
        num -= (c * denom)
    parity = 0
    while (num != 0):
        num, denom = denom, num
        if parity == 0:
            num -= 1
        c = num // denom
        X.append(c)
        if parity == 0:
            num += 1
        num -= (c * denom)
        parity = 1 - parity
    return X

get_state(u, v)

Computes the state of K_u/v.

Returns (orientation, points).

Source code in helpers\tanglestate.py 
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
def get_state(u,v):
    """Computes the state of K_u/v.

    Returns (orientation, points).
    """
    x = continuedfrac(u,v)
    tangle = TangleState()
    x.reverse()

    par = 0
    for k in x:
        if par == 0:
            if k % 2 != 0:
                tangle.t_twist()

        else:
            if k % 2 != 0:
                tangle.r_twist()
        par = 1 - par
    return (tangle.orient, tangle.points)