Free Factors and conjugacy

To test for conjugacy we need to extract periodic and infinite components of an automorphism and test those components for conjugacy. These next few classes keep track of

• how the components embed into the original automorphism, and
• any extra information that we need to test the components for conjugacy.

Periodic Factors

class thompson.periodic.PeriodicAut(domain, range, reduce=True)

A purely periodic automorphism, which may have been extracted from a mixed automorphism.

>>> example_5_9 = load_example('example_5_9')
>>> print(example_5_9)
PeriodicAut: V(2, 1) -> V(2, 1) specified by 7 generators (after expansion and reduction).
x1 a1 a1 a1 -> x1 a1 a1 a2
x1 a1 a1 a2 -> x1 a1 a2   
x1 a1 a2    -> x1 a1 a1 a1
x1 a2 a1 a1 -> x1 a2 a1 a2
x1 a2 a1 a2 -> x1 a2 a1 a1
x1 a2 a2 a1 -> x1 a2 a2 a2
x1 a2 a2 a2 -> x1 a2 a2 a1
>>> sorted(example_5_9.cycle_type)
[2, 3]
>>> #Two orbits of size 2, one orbit of size 3
>>> from pprint import pprint
>>> pprint(example_5_9.multiplicity)
{2: 2, 3: 1}
>>> example_5_9.order
6

>>> load_example('cyclic_order_six').order
6
>>> phi = random_periodic_automorphism()
>>> 1 <= phi.order < float('inf')
True
>>> len(phi.cycle_type) != 0
True
>>> len(phi.characteristics)
0

test_conjugate_to(other)

We can determine if two purely periodic automorphisms are conjugate by examining their orbits.

>>> psi_p, phi_p = load_example('example_5_12_psi'), load_example('example_5_12_phi')
>>> rho_p = psi_p.test_conjugate_to(phi_p)
>>> print(rho_p)
PeriodicAut: V(2, 1) -> V(2, 1) specified by 6 generators (after expansion and reduction).
x1 a1 a1 a1 a1 -> x1 a1 a2   
x1 a1 a1 a1 a2 -> x1 a2 a2   
x1 a1 a1 a2    -> x1 a1 a1 a1
x1 a1 a2       -> x1 a2 a1 a1
x1 a2 a1       -> x1 a1 a1 a2
x1 a2 a2       -> x1 a2 a1 a2
>>> rho_p * phi_p == psi_p * rho_p
True
>>> psi_p, phi_p = random_conjugate_periodic_pair()
>>> rho_p = psi_p.test_conjugate_to(phi_p)
>>> rho_p * phi_p == psi_p * rho_p
True

See also

This implements algorithm 5.13 of the paper—see section 5.3.

find_power_conjugators(other, identity_permitted=False, cheat=False)

test_power_conjugate_to(other, cheat=False)

Tests two periodic factors to see if they are power conjugate. Yields minimal solutions \((a, b, \rho)\). such that \(\rho^{-1}\psi^a\rho = \phi^b\).

See also

Section 6.1 of the paper.

power_conjugacy_bounds(other, identity_permitted)

We simply try all powers of both automorphisms. There are only finitely many, because everything is periodic.

Returns:self.power, other.power if the identity is permitted as a solution; otherwise self.power - 1, other.power - 1.

Todo

Maybe this should be 0 to order if the identity is permitted and 1 to order otherwise?

See also

Section 6.1 of the paper.

Infinite Factors

class thompson.infinite.InfiniteAut(domain, range, reduce=True)

A purely infinite automorphism which may have been extracted from a mixed automorphism.

>>> print(load_example('example_5_3').free_factors()[1])
InfiniteAut: V(2, 1) -> V(2, 1) specified by 6 generators (after expansion and reduction).
This automorphism was derived from a parent automorphism.
'x' and 'y' represent root words of the parent and current derived algebra, respectively.
x1 a1 a1 a1 a1 ~>    y1 a1 a1 a1 => y1 a1 a1       ~> x1 a1 a1 a1   
x1 a1 a1 a1 a2 ~>    y1 a1 a1 a2 => y1 a1 a2 a1    ~> x1 a1 a1 a2 a1
x1 a1 a1 a2    ~>    y1 a1 a2    => y1 a1 a2 a2    ~> x1 a1 a1 a2 a2
x1 a2 a1       ~>    y1 a2 a1    => y1 a2 a1 a1    ~> x1 a2 a1 a1   
x1 a2 a2 a1    ~>    y1 a2 a2 a1 => y1 a2 a1 a2    ~> x1 a2 a1 a2   
x1 a2 a2 a2    ~>    y1 a2 a2 a2 => y1 a2 a2       ~> x1 a2 a2      
>>> phi = random_infinite_automorphism()
>>> phi.order
inf
>>> len(phi.cycle_type)
0
>>> len(phi.characteristics) != 0
True

test_conjugate_to(other)

We can determine if two purely infinite automorphisms are conjugate by breaking down the quasi-normal basis into equivalence classes.

>>> for psi_i, phi_i in (
...   load_example_pair('example_5_26'),
...   load_example_pair('inf_conj'),
...   random_conjugate_infinite_pair()):
...     rho_i = psi_i.test_conjugate_to(phi_i)
...     print('Conjugate:', rho_i is not None, ' Conjugator works:', rho_i * phi_i == psi_i * rho_i)
Conjugate: True  Conjugator works: True
Conjugate: True  Conjugator works: True
Conjugate: True  Conjugator works: True

>>> f, g = (load_example('not_conjugate_' + c) for c in 'fg')
>>> f.is_conjugate_to(g)
False

See also

This implements Algorithm 5.27 of the paper—see Section 5.4.

equivalence_data(type_b, type_c)

Let \(X\) be the quasi-normal basis for the current automorphism \(\psi\). We can define an equivalence relation \(\equiv\) on \(X\) by taking the non-transitive relation

\[x \equiv y \iff \exists k, \Gamma, \Delta : x\Gamma\psi^k = y\Delta\]

and allowing it to generate an equivalence relation. This method returns a pair (roots, graph) where

• graph is a DiGraph()

  • vertices are type B words in \(X\)
  • directed edges \(x \to y\) correspond to the direct relation \(x \equiv y\)
  • the graph is a directed forest

• roots is a list of type B words in \(X\)

  • Each root is the root of a different tree in the forest graph.

This information allows us to (attempt to) compute the images of \(X\) under a conjugator given only the images of roots.

See also

Definition 5.17 through to Lemma 5.20.

potential_image_endpoints(self_type_b)

Let x be a type B word with respect to the current automorphism. This returns a mapping which takes x and produces the set of words w which are endpoints of other-orbits which have the same characteristic as x.

See also

The sets \(\mathcal R_i\) of defintion 5.23.

find_power_conjugators(other, cheat=False)

Tests two infinite factors to see if they are power conjugate. Yields minimal solutions \((a, b, ho)\).

>>> example_6_8_psi, example_6_8_phi = load_example_pair('example_6_8')
>>> solns = example_6_8_psi.find_power_conjugators(example_6_8_phi)
>>> for a, b, rho in solns:
...     print(a, b)
...     assert example_6_8_psi ** a * rho == rho * example_6_8_phi ** b
3 1
-3 -1

Warning

If the power_conjugacy_bounds() are reasonable large (say > 30), this method could potentially take a long time!

See also

Algorithm 6.11 of the paper.

test_power_conjugate_to(other, cheat=False)

Tests two infinite factors to see if they are power conjugate. If a solution exists, returns \((a, b, \rho)\) such that \(\rho^{-1}\psi^a\rho = \phi^b\). Otherwise returns None.

>>> result = example_6_8_psi.test_power_conjugate_to(example_6_8_phi)
>>> result is not None
True
>>> a, b, rho = result
>>> (example_6_8_psi ** a) * rho == rho * (example_6_8_phi ** b)
True

Warning

If the power_conjugacy_bounds() are reasonable large (say > 30), this method could potentially take a long time!

See also

Algorithm 6.11 of the paper.

power_conjugacy_bounds(other)

Compute the bounds \(\hat a, \hat b\) on powers which could solve the power conjugacy problem.

>>> example_6_8_psi.power_conjugacy_bounds(example_6_8_phi)
(9, 1)

See also

Proposition 6.6 and Corollary 6.7.

minimal_partition()

Let \(\psi\) be the current automorphism. This method partitions the characteristics \(M_\psi\) into cells \(P_1 \sqcup \dots \sqcup P_L\), where - The multipliers \(\Gamma\) all have the same root(), for all \((m, \Gamma)\) in each \(P_i\). - \(L\) is minimal with this property.

>>> def print_partition(p):
...     for root in sorted(p.keys(), reverse=True):
...             print(format(root), end = ':')
...             for power, mult, _ in p[root]:
...                     print(' ({}, {})'.format(power, format(mult)), end='')
...             print()
>>> print_partition(example_6_8_psi.minimal_partition())
a1: (-1, a1)
a2: (1, a2)
>>> print_partition(example_6_8_phi.minimal_partition())
a1: (-1, a1 a1 a1)
a2: (1, a2 a2 a2)
>>> example_6_9_psi, example_6_9_phi = load_example_pair('example_6_9')
>>> print_partition(example_6_9_phi.minimal_partition())
a1: (-2, a1)
a2: (1, a2)

Returns:a dictionary of sets. The keys of this dictionary are the roots \(\sqrt\Gamma\); the values are the cells \(P_i\). An element of a cell looks like \(m, \Gamma, r\) where \(m, \Gamma\) is a characteristic and \(r\) is the root power corresponding to \(\sqrt\Gamma\).

See also

the discussion following Corollary 6.7.

static compute_bounds(s_parts, o_parts)

Computes the bounds \(\hat a, \hat b\) (in terms of the partitions \(P, Q\) given by s_parts and o_parts) as in eqns (14) and (15) of the paper.

>>> def bounds(s, o):
...     P = s.minimal_partition()
...     Q = o.minimal_partition()
...     a_hat = InfiniteAut.compute_bounds(P, Q)
...     b_hat = InfiniteAut.compute_bounds(Q, P)
...     return a_hat, b_hat
>>> bounds(example_6_8_psi, example_6_8_phi)
(9, 1)
>>> bounds(example_6_9_psi, example_6_9_phi)
(1, 2)

Next steps

With these classes, the conjugacy and power conjugacy tests are implemented. The other important part of this package is the examples module.