# Cactus Groups#

AUTHORS:

• Travis Scrimshaw (1-2023): initial version

class sage.groups.cactus_group.CactusGroup(n)#

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 – an 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


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

class Element(parent, data)#

An element of a cactus group.

to_matrix()#

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

to_permutation()#

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]


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'

bilinear_form(t=None)#

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]


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]

gen(i, j=None)#

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

gens()#

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])

geometric_representation_generators(t=None)#

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]
]


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
....:         matp = mat * r
....:         matp.set_immutable()
....:         assert matp not in mats, f"not injective {val} \n{matp}"

group_generators()#

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]}

n()#

Return the value $$n$$.

EXAMPLES:

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

one()#

Return the identity element in self.

EXAMPLES:

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

random_element(max_length=10)#

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]

right_angled_coxeter_group()#

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]

class sage.groups.cactus_group.PureCactusGroup(n)#

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)#

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

gens()#

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

n()#

Return the value $$n$$.

EXAMPLES:

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