MixedAuts¶

A general automorphism \(\phi \in G_{n,r}\) may exhibit periodic behaviour, infinite behaviour, or a mix of both. We say that an automorphism is

purely periodic if it has finite order;
purely infinite if it has no periodic orbits; and
mixed otherwise.

We can represent a mixed automorphism \(\psi\) as a free product \(\psi = \psi_P * \psi_I\) of a purely periodic and purely infinite automorphism. The automorphisms \(\psi_P\) and \(\psi_I\) are called free_factors(). We form this decomposition because the conjugacy problem is easier to solve when the automorphisms are both pure infinite or both pure periodic.

This class is responsible for:

Generating the free factors from a mixed automorphism;
Combining a periodic and infinite factor into a mixed automorphism; and
Delegating the conjugacy and power conjugacy tests to these factors.

The MixedAut class¶

class thompson.mixed.MixedAut(domain, range, reduce=True)[source]¶

free_factors()[source]¶

In principle, an automorphism can be decomposed into free factors using any partition of the quasi-normal basis \(X = X_1 \sqcup X_2\). The decomposition \(X = X_P \sqcup X_I\) is particularly interesting since these sets generate \(\psi\)-invariant subalgebras, which means that a conjugator can be reassembled from conjugators of the factors.

See also

This jargon comes from Theorem 5.1.

This is a convenience method which produces the free factors \(\psi_P\) and \(\psi_I\) from \(\psi\).

free_factor(generators)[source]¶

This method restricts the current automorphism to the subalgebra generated by the given set \(W\) of generators. This is then transformed into an automorphism of an isomorphic algebra with minimal alphabet size \(1 \le s \le n-1\).

\[\begin{split}&G_{n, r} &\to &G_{n, |W|} &\to &G_{n, s} \\ &\phi &\mapsto &\phi|_{W\langle A\rangle\langle\lambda\rangle} &\mapsto &\phi\,'\end{split}\]

Returns:	The transformed automorphism \(\phi\, \in G_{n, s}\). Its type is `PeriodicAut` or `InfiniteAut` as appropriate.
Raises:	ValueError – if an empty list of generators is provided.

>>> phi = load_example('alphabet_size_two')
>>> qnb = phi.quasinormal_basis
>>> p, i = phi._partition_basis(qnb)
>>> print(phi.free_factor(p))
PeriodicAut: V(3, 1) -> V(3, 1) specified by 1 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 ~>    y1 => y1    ~> x1 a1
>>> print(phi.free_factor(i))
InfiniteAut: V(3, 1) -> V(3, 1) specified by 5 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 a2 ~>    y1 a1    => y1 a1 a3    ~> x1 a2 a3
x1 a3 ~>    y1 a2    => y1 a3       ~> x2      
x2 a1 ~>    y1 a3 a1 => y1 a2       ~> x1 a3   
x2 a2 ~>    y1 a3 a2 => y1 a1 a2    ~> x1 a2 a2
x2 a3 ~>    y1 a3 a3 => y1 a1 a1    ~> x1 a2 a1

test_conjugate_to(other)[source]¶

Determines if the current automorphism \(\psi\) is conjugate to the other automorphism \(\phi\).

Returns:	if it exists, a conjugating element \(\rho\) such that \(\rho^{-1}\psi\rho = \phi\). If no such \(\rho\) exists, returns `None`.
Raises:	ValueError – if the automorphisms have different arities or alphabet sizes.

>>> psi, phi = random_conjugate_pair()
>>> rho = psi.test_conjugate_to(phi)
>>> rho is not None
True
>>> psi * rho == rho * phi
True
>>> psi, phi = load_example_pair('first_pond_example')
>>> rho = psi.test_conjugate_to(phi)
>>> rho is not None
True
>>> psi * rho == rho * phi
True

See also

This is an implementation of Algorithm 5.6 in the paper. It depends on Algorithms 5.13 and 5.27; these are the periodic and infinite tests for conjugacy.

find_power_conjugators(other, cheat=False)[source]¶

Determines if some power of the current automorphism \(\psi\) is conjugate to some power of the other automorphism \(\phi\). This method exhaustively searches for all minimal solutions \((a, b, \rho)\) such that \(\rho^{-1}\psi^a\rho = \phi^b\). This method returns a generator which yields such minimal solutions.

Warning

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

Parameters:	cheat – (internal) for speeding up testing.
Raises:	ValueError – if the automorphisms have different arities or alphabet sizes.

See also

This is an implementation of Algorithm 6.13 in the paper. It depends on Algorithms 5.6 (the conjugacy test) and 6.11 (the infinite power conjugate test.)

test_power_conjugate_to(other, cheat=False)[source]¶

Determines if some power of the current automorphism \(\psi\) is conjugate to some power of the other automorphism \(\phi\). This method searches for a single minimal solution \((a, b, \rho)\) such that \(\rho^{-1}\psi^a\rho = \phi^b\). If no such solution exists, returns None.

Warning

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

Parameters:	cheat – (internal) for speeding up testing.
Raises:	ValueError – if the automorphisms have different arities or alphabet sizes.

>>> psi, phi = load_example_pair('mixed_pconj')
>>> a, b, rho = psi.test_power_conjugate_to(phi)
>>> a, b
(6, 3)
>>> psi**a * rho == rho * phi ** b
True

See also

This is an implementation of Algorithm 6.13 in the paper. It depends on Algorithms 5.6 (the conjugacy test) and 6.11 (the infinite power conjugate test.)

Next steps¶

To complete the details of the conjugacy test, we have to be able to test if two pure periodic automorphisms are conjugate and if two pure infinite automorphisms are conjugate. Any given automorphism can be broken down into a pure periodic and pure infinite part. These parts are called free factors.