Cactus Groups#

AUTHORS:

  • Travis Scrimshaw (1-2023): initial version

class sage.groups.cactus_group.CactusGroup(n)[source]#

Bases: UniqueRepresentation, Group

The cactus group.

The \(n\)-fruit cactus group \(J_n\) is the group generated by \(s_{pq}\) for \(1 \leq p < q \leq n\) with relations:

  • \(s_{pq}^2 = 1\)

  • \(s_{pq} s_{kl} = s_{kl} s_{pq}\) if the intervals \([p, q]\) and \([k, l]\) are disjoint, and

  • \(s_{pq} s_{kl} = s_{p+q-l,p+q-k} s_{pq}\) if \([k, l] \subseteq [p, q]\).

INPUT:

  • n – integer

EXAMPLES:

We construct the cactus group \(J_3\) and do some basic computations:

sage: J3 = groups.misc.Cactus(3)
sage: s12,s13,s23 = J3.group_generators()
sage: s12 * s13
s[1,2]*s[1,3]
sage: x = s12 * s23; x
s[1,2]*s[2,3]
sage: x^4
s[1,2]*s[2,3]*s[1,2]*s[2,3]*s[1,2]*s[2,3]*s[1,2]*s[2,3]
sage: s12 * s13 == s13 * s23
True

>>> from sage.all import *
>>> J3 = groups.misc.Cactus(Integer(3))
>>> s12,s13,s23 = J3.group_generators()
>>> s12 * s13
s[1,2]*s[1,3]
>>> x = s12 * s23; x
s[1,2]*s[2,3]
>>> x**Integer(4)
s[1,2]*s[2,3]*s[1,2]*s[2,3]*s[1,2]*s[2,3]*s[1,2]*s[2,3]
>>> s12 * s13 == s13 * s23
True

We verify the key equality in Lemma 2.3 in [White2015], which shows that \(J_5\) is generated by \(s_{1q}\):

sage: J5 = groups.misc.Cactus(5)
sage: gens = J5.group_generators()
sage: all(gens[(p,q)] == gens[(1,q)] * gens[(1,q-p+1)] * gens[(1,q)]
....:     for p in range(1, 6) for q in range(p+1, 6))
True

>>> from sage.all import *
>>> J5 = groups.misc.Cactus(Integer(5))
>>> gens = J5.group_generators()
>>> all(gens[(p,q)] == gens[(Integer(1),q)] * gens[(Integer(1),q-p+Integer(1))] * gens[(Integer(1),q)]
...     for p in range(Integer(1), Integer(6)) for q in range(p+Integer(1), Integer(6)))
True
class Element(parent, data)[source]#

Bases: MultiplicativeGroupElement

An element of a cactus group.

to_matrix()[source]#

Return self as a matrix.

The resulting matrix is the geometric representation of self.

EXAMPLES:

sage: J3 = groups.misc.Cactus(3)
sage: s12,s13,s23 = J3.gens()
sage: s12.to_matrix()
[ -1   0 2*t]
[  0   1   0]
[  0   0   1]
sage: (s12*s13).to_matrix()
[2*t   0  -1]
[  0  -1   0]
[  1   0   0]
sage: (s13*s23).to_matrix()
[2*t   0  -1]
[  0  -1   0]
[  1   0   0]
sage: (s13*s12).to_matrix()
[  0   0   1]
[  0  -1   0]
[ -1   0 2*t]
sage: all(x.to_matrix() * y.to_matrix() == (x*y).to_matrix()
....:     for x in J3.gens() for y in J3.gens())
True

>>> from sage.all import *
>>> J3 = groups.misc.Cactus(Integer(3))
>>> s12,s13,s23 = J3.gens()
>>> s12.to_matrix()
[ -1   0 2*t]
[  0   1   0]
[  0   0   1]
>>> (s12*s13).to_matrix()
[2*t   0  -1]
[  0  -1   0]
[  1   0   0]
>>> (s13*s23).to_matrix()
[2*t   0  -1]
[  0  -1   0]
[  1   0   0]
>>> (s13*s12).to_matrix()
[  0   0   1]
[  0  -1   0]
[ -1   0 2*t]
>>> all(x.to_matrix() * y.to_matrix() == (x*y).to_matrix()
...     for x in J3.gens() for y in J3.gens())
True
to_permutation()[source]#

Return the image of self under the canonical projection to the permutation group.

EXAMPLES:

sage: J3 = groups.misc.Cactus(3)
sage: s12,s13,s23 = J3.gens()
sage: s12.to_permutation()
[2, 1, 3]
sage: s23.to_permutation()
[1, 3, 2]
sage: s13.to_permutation()
[3, 2, 1]
sage: elt = s12*s23*s13
sage: elt.to_permutation()
[1, 3, 2]

sage: J7 = groups.misc.Cactus(7)
sage: J7.group_generators()[3,6].to_permutation()
[1, 2, 6, 5, 4, 3, 7]

>>> from sage.all import *
>>> J3 = groups.misc.Cactus(Integer(3))
>>> s12,s13,s23 = J3.gens()
>>> s12.to_permutation()
[2, 1, 3]
>>> s23.to_permutation()
[1, 3, 2]
>>> s13.to_permutation()
[3, 2, 1]
>>> elt = s12*s23*s13
>>> elt.to_permutation()
[1, 3, 2]

>>> J7 = groups.misc.Cactus(Integer(7))
>>> J7.group_generators()[Integer(3),Integer(6)].to_permutation()
[1, 2, 6, 5, 4, 3, 7]

We check that this respects the multiplication order of permutations:

sage: P3 = Permutations(3)
sage: elt = s12*s23
sage: elt.to_permutation() == P3(s12) * P3(s23)
True
sage: Permutations.options.mult='r2l'
sage: elt.to_permutation() == P3(s12) * P3(s23)
True
sage: Permutations.options.mult='l2r'

>>> from sage.all import *
>>> P3 = Permutations(Integer(3))
>>> elt = s12*s23
>>> elt.to_permutation() == P3(s12) * P3(s23)
True
>>> Permutations.options.mult='r2l'
>>> elt.to_permutation() == P3(s12) * P3(s23)
True
>>> Permutations.options.mult='l2r'
bilinear_form(t=None)[source]#

Return the t-bilinear form of self.

We define a bilinear form \(B\) on the group algebra by

\[\begin{split}B(s_{ij}, s_{pq}) = \begin{cases} 1 & \text{if } i = p, j = q, \\ -t & \text{if } [i, j] \not\subseteq [p, q] \text{ and } [p, q] \not\subseteq [i, j], \\ 0 & \text{otherwise}. \end{cases}\end{split}\]

In other words, it is \(1\) if \(s_{ij} = s_{pq}\), \(-t\) if \(s_{ij}\) and \(s_{pq}\) generate a free group, and \(0\) otherwise (they commute or almost commute).

INPUT:

  • t – (default: \(t\) in \(\ZZ[t]\)) the variable \(t\)

EXAMPLES:

sage: J = groups.misc.Cactus(4)
sage: B = J.bilinear_form()
sage: B
[ 1  0  0 -t -t  0]
[ 0  1  0  0 -t -t]
[ 0  0  1  0  0  0]
[-t  0  0  1  0 -t]
[-t -t  0  0  1  0]
[ 0 -t  0 -t  0  1]

>>> from sage.all import *
>>> J = groups.misc.Cactus(Integer(4))
>>> B = J.bilinear_form()
>>> B
[ 1  0  0 -t -t  0]
[ 0  1  0  0 -t -t]
[ 0  0  1  0  0  0]
[-t  0  0  1  0 -t]
[-t -t  0  0  1  0]
[ 0 -t  0 -t  0  1]

We reorder the generators so the bilinear form is more “Coxeter-like”. In particular, when we remove the generator \(s_{1,4}\), we recover the bilinear form in Example 6.2.5 of [DJS2003]:

sage: J.gens()
(s[1,2], s[1,3], s[1,4], s[2,3], s[2,4], s[3,4])
sage: S = SymmetricGroup(6)
sage: g = S([1,4,6,2,5,3])
sage: B.permute_rows_and_columns(g, g)
sage: B
[ 1 -t  0  0 -t  0]
[-t  1 -t  0  0  0]
[ 0 -t  1 -t  0  0]
[ 0  0 -t  1 -t  0]
[-t  0  0 -t  1  0]
[ 0  0  0  0  0  1]

>>> from sage.all import *
>>> J.gens()
(s[1,2], s[1,3], s[1,4], s[2,3], s[2,4], s[3,4])
>>> S = SymmetricGroup(Integer(6))
>>> g = S([Integer(1),Integer(4),Integer(6),Integer(2),Integer(5),Integer(3)])
>>> B.permute_rows_and_columns(g, g)
>>> B
[ 1 -t  0  0 -t  0]
[-t  1 -t  0  0  0]
[ 0 -t  1 -t  0  0]
[ 0  0 -t  1 -t  0]
[-t  0  0 -t  1  0]
[ 0  0  0  0  0  1]
gen(i, j=None)[source]#

Return the \(i\)-th generator of self or the generator \(s_{ij}\).

EXAMPLES:

sage: J3 = groups.misc.Cactus(3)
sage: J3.gen(1)
s[1,3]
sage: J3.gen(1,2)
s[1,2]
sage: J3.gen(0,2)
Traceback (most recent call last):
...
ValueError: s[0,2] is not a valid generator
sage: J3.gen(1,4)
Traceback (most recent call last):
...
ValueError: s[1,4] is not a valid generator
sage: J3.gen(2,1)
Traceback (most recent call last):
...
ValueError: s[2,1] is not a valid generator

>>> from sage.all import *
>>> J3 = groups.misc.Cactus(Integer(3))
>>> J3.gen(Integer(1))
s[1,3]
>>> J3.gen(Integer(1),Integer(2))
s[1,2]
>>> J3.gen(Integer(0),Integer(2))
Traceback (most recent call last):
...
ValueError: s[0,2] is not a valid generator
>>> J3.gen(Integer(1),Integer(4))
Traceback (most recent call last):
...
ValueError: s[1,4] is not a valid generator
>>> J3.gen(Integer(2),Integer(1))
Traceback (most recent call last):
...
ValueError: s[2,1] is not a valid generator
gens()[source]#

Return the generators of self as a tuple.

EXAMPLES:

sage: J3 = groups.misc.Cactus(3)
sage: J3.gens()
(s[1,2], s[1,3], s[2,3])

>>> from sage.all import *
>>> J3 = groups.misc.Cactus(Integer(3))
>>> J3.gens()
(s[1,2], s[1,3], s[2,3])
geometric_representation_generators(t=None)[source]#

Return the matrices corresponding to the generators of self.

We construct a representation over \(R = \ZZ[t]\) of \(J_n\) as follows. Let \(E\) be the vector space over \(R\) spanned by \(\{\epsilon_v\}_v\), where \(v\) is a generator of \(J_n\). Fix some generator \(v\), and let \(E_v\) denote the span of \(\epsilon_u - \epsilon_{u'}\), where \(u'\) is the reflected interval of \(u\) in \(v\), over all \(u\) such that \(u \subset v\). Let \(F_v\) denote the orthogonal complement of \(R \epsilon_v \oplus E_v\) with respect to the bilinear form \(B\). We define the action of \(v\) on \(E\) by

\[\rho(v) = -I |_{R\epsilon_v \oplus E_v} \oplus I |_{F_v}.\]

By Theorem 6.2.3 of [DJS2003], this defines a representation of \(J_n\). It is expected that this is a faithful representation (see Remark 6.2.4 of [DJS2003]). As this arises from a blow-up and an analog of the geometric representation of the corresponding Coxeter group (the symmetric group), we call this the geometric representation.

INPUT:

  • t – (default: \(t\) in \(\ZZ[t]\)) the variable \(t\)

EXAMPLES:

sage: J3 = groups.misc.Cactus(3)
sage: list(J3.geometric_representation_generators())
[
[ -1   0 2*t]  [ 0  0  1]  [  1   0   0]
[  0   1   0]  [ 0 -1  0]  [  0   1   0]
[  0   0   1], [ 1  0  0], [2*t   0  -1]
]

>>> from sage.all import *
>>> J3 = groups.misc.Cactus(Integer(3))
>>> list(J3.geometric_representation_generators())
[
[ -1   0 2*t]  [ 0  0  1]  [  1   0   0]
[  0   1   0]  [ 0 -1  0]  [  0   1   0]
[  0   0   1], [ 1  0  0], [2*t   0  -1]
]

We ran the following code with max_tests = 15000 and did not find a counterexample to the faithfulness of this representation:

sage: visited = set([J3.one()])
sage: cur = set([(J3.one(), J3.one().to_matrix())])
sage: mats = set([J3.one().to_matrix()])
sage: RG = list(J3.geometric_representation_generators())
sage: count = 0
sage: max_tests = 1000
sage: while cur:
....:     count += 1
....:     if count >= max_tests:
....:         break
....:     elt, mat = cur.pop()
....:     for g,r in zip(J3, RG):
....:         val = elt * g
....:         if val in visited:
....:             continue
....:         visited.add(val)
....:         matp = mat * r
....:         matp.set_immutable()
....:         assert matp not in mats, f"not injective {val} \n{matp}"
....:         mats.add(matp)
....:         cur.add((val, matp))

>>> from sage.all import *
>>> visited = set([J3.one()])
>>> cur = set([(J3.one(), J3.one().to_matrix())])
>>> mats = set([J3.one().to_matrix()])
>>> RG = list(J3.geometric_representation_generators())
>>> count = Integer(0)
>>> max_tests = Integer(1000)
>>> while cur:
...     count += Integer(1)
...     if count >= max_tests:
...         break
...     elt, mat = cur.pop()
...     for g,r in zip(J3, RG):
...         val = elt * g
...         if val in visited:
...             continue
...         visited.add(val)
...         matp = mat * r
...         matp.set_immutable()
...         assert matp not in mats, f"not injective {val} \n{matp}"
...         mats.add(matp)
...         cur.add((val, matp))
group_generators()[source]#

Return the group generators of self.

EXAMPLES:

sage: J3 = groups.misc.Cactus(3)
sage: J3.group_generators()
Finite family {(1, 2): s[1,2], (1, 3): s[1,3], (2, 3): s[2,3]}

>>> from sage.all import *
>>> J3 = groups.misc.Cactus(Integer(3))
>>> J3.group_generators()
Finite family {(1, 2): s[1,2], (1, 3): s[1,3], (2, 3): s[2,3]}
n()[source]#

Return the value \(n\).

EXAMPLES:

sage: J3 = groups.misc.Cactus(3)
sage: J3.n()
3

>>> from sage.all import *
>>> J3 = groups.misc.Cactus(Integer(3))
>>> J3.n()
3
one()[source]#

Return the identity element in self.

EXAMPLES:

sage: J3 = groups.misc.Cactus(3)
sage: J3.one()
1

>>> from sage.all import *
>>> J3 = groups.misc.Cactus(Integer(3))
>>> J3.one()
1
random_element(max_length=10)[source]#

Return a random element of self of length at most max_length.

EXAMPLES:

sage: J3 = groups.misc.Cactus(3)
sage: J3.random_element()  # random
s[1,2]*s[2,3]*s[1,2]*s[1,3]

>>> from sage.all import *
>>> J3 = groups.misc.Cactus(Integer(3))
>>> J3.random_element()  # random
s[1,2]*s[2,3]*s[1,2]*s[1,3]
right_angled_coxeter_group()[source]#

Return the right-angled Coxeter group that self (set-theoretically) embeds into.

This is defined following [Most2019], where it was called the diagram group. It has generators (of order \(2\)) indexed by subsets of \(\{1, \ldots, n\}\) that commute if and only if one subset is contained in the other or they are disjoint. For the pure cactus group, this is also a group homomorphism, otherwise it is a group 1-cocycle [BCL2022].

EXAMPLES:

sage: J3 = groups.misc.Cactus(3)
sage: J3.right_angled_coxeter_group()
Coxeter group over Rational Field with Coxeter matrix:
[ 1 -1 -1  2]
[-1  1 -1  2]
[-1 -1  1  2]
[ 2  2  2  1]

>>> from sage.all import *
>>> J3 = groups.misc.Cactus(Integer(3))
>>> J3.right_angled_coxeter_group()
Coxeter group over Rational Field with Coxeter matrix:
[ 1 -1 -1  2]
[-1  1 -1  2]
[-1 -1  1  2]
[ 2  2  2  1]
class sage.groups.cactus_group.PureCactusGroup(n)[source]#

Bases: KernelSubgroup

The pure cactus group.

The pure cactus group \(PJ_n\) is the kernel of the natural surjection of the cactus group \(J_n\) onto the symmetric group \(S_n\). In particular, we have the following (non-split) exact sequence:

\[1 \longrightarrow PJ_n \longrightarrow J_n \longrightarrow S_n \longrightarrow 1.\]
gen(i)[source]#

Return the i-th generator of self.

EXAMPLES:

sage: PJ3 = groups.misc.PureCactus(3)
sage: PJ3.gen(0)
s[2,3]*s[1,2]*s[2,3]*s[1,3]
sage: PJ3.gen(1)
s[1,2]*s[2,3]*s[1,2]*s[1,3]
sage: PJ3.gen(5)
Traceback (most recent call last):
...
IndexError: tuple index out of range

>>> from sage.all import *
>>> PJ3 = groups.misc.PureCactus(Integer(3))
>>> PJ3.gen(Integer(0))
s[2,3]*s[1,2]*s[2,3]*s[1,3]
>>> PJ3.gen(Integer(1))
s[1,2]*s[2,3]*s[1,2]*s[1,3]
>>> PJ3.gen(Integer(5))
Traceback (most recent call last):
...
IndexError: tuple index out of range
gens()[source]#

Return the generators of self.

ALGORITHM:

We use Wikipedia article Schreier’s_lemma and compute the traversal using the lex minimum elements (defined by the order of the generators of the ambient cactus group).

EXAMPLES:

We verify Corollary A.2 of [BCL2022]:

sage: PJ3 = groups.misc.PureCactus(3)
sage: PJ3.gens()
(s[2,3]*s[1,2]*s[2,3]*s[1,3], s[1,2]*s[2,3]*s[1,2]*s[1,3])
sage: a, b = PJ3.gens()
sage: a * b  # they are inverses of each other
1

sage: J3 = groups.misc.Cactus(3)
sage: gen = (J3.gen(1,2)*J3.gen(1,3))^3
sage: gen
s[1,2]*s[2,3]*s[1,2]*s[1,3]
sage: gen == b
True

>>> from sage.all import *
>>> PJ3 = groups.misc.PureCactus(Integer(3))
>>> PJ3.gens()
(s[2,3]*s[1,2]*s[2,3]*s[1,3], s[1,2]*s[2,3]*s[1,2]*s[1,3])
>>> a, b = PJ3.gens()
>>> a * b  # they are inverses of each other
1

>>> J3 = groups.misc.Cactus(Integer(3))
>>> gen = (J3.gen(Integer(1),Integer(2))*J3.gen(Integer(1),Integer(3)))**Integer(3)
>>> gen
s[1,2]*s[2,3]*s[1,2]*s[1,3]
>>> gen == b
True
n()[source]#

Return the value \(n\).

EXAMPLES:

sage: PJ3 = groups.misc.PureCactus(3)
sage: PJ3.n()
3

>>> from sage.all import *
>>> PJ3 = groups.misc.PureCactus(Integer(3))
>>> PJ3.n()
3