Source code for thompson.periodic

.. testsetup::
	from thompson.periodic import *
	from thompson.examples import *

from collections import defaultdict, deque

from .generators    import Generators
from .automorphism  import Automorphism

__all__ = ["PeriodicAut"]

[docs]class PeriodicAut(Automorphism): r"""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 """
[docs] def test_conjugate_to(self, 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 .. seealso:: This implements algorithm :paperref:`alg:periodic` of the paper---see section :paperref:`subsectionP`. """ if not isinstance(other, PeriodicAut): return None # 1. The quasi-normal bases are constructed in initialisation. # 2. Check that the cycle types are the same. if self.cycle_type != other.cycle_type: return None #3. Check that the multiplicities are congruent. modulus = self.signature.arity - 1 for d in self.cycle_type: if self.multiplicity[d] % modulus != other.multiplicity[d] % modulus: return None # 4. Expand bases until the orbits multiplicites are the same s_orbits_of_size = { d: deque(orbits) for d, orbits in self.periodic_orbits.items() } o_orbits_of_size = { d: deque(orbits) for d, orbits in other.periodic_orbits.items() } for d in self.cycle_type: expansions_needed = (self.multiplicity[d] - other.multiplicity[d]) // modulus if expansions_needed > 0: expand_orbits(o_orbits_of_size[d], expansions_needed) elif expansions_needed < 0: expand_orbits(s_orbits_of_size[d], -expansions_needed) assert len(s_orbits_of_size[d]) == len(o_orbits_of_size[d]) domain = Generators(self.signature) range = Generators(self.signature) for d in self.cycle_type: for s_orbit, o_orbit in zip(s_orbits_of_size[d], o_orbits_of_size[d]): for s_word, o_word in zip(s_orbit, o_orbit): domain.append(s_word) range.append(o_word) rho = Automorphism(domain, range) rho.add_relabellers(self.domain_relabeller, other.range_relabeller) return rho
[docs] def find_power_conjugators(self, other, identity_permitted=False, cheat=False): #This is almost exactly the same code as InfiniteAut.test_power_conjugate_to(). Maybe this should be one method on Automorphism if not isinstance(other, PeriodicAut): raise StopIteration if not identity_permitted and (self.is_identity() or other.is_identity()): print("One of the automorphisms is the identity") raise StopIteration if cheat: from .examples.random import random_power_bounds bounds = random_power_bounds else: bounds = self.power_conjugacy_bounds(other, identity_permitted) yield from self._test_power_conjugate_upto(other, *bounds, inverses=False)
[docs] def test_power_conjugate_to(self, other, cheat=False): r"""Tests two periodic factors to see if they are power conjugate. Yields minimal solutions :math:`(a, b, \rho)`. such that :math:`\rho^{-1}\psi^a\rho = \phi^b`. .. seealso:: Section :paperref:`torPower` of the paper. """ try: return next(self.find_power_conjugators(other, cheat=cheat)) except StopIteration: return None
[docs] def power_conjugacy_bounds(self, 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? .. seealso:: Section :paperref:`torPower` of the paper.""" if identity_permitted: return self.order, other.order else: return self.order - 1, other.order - 1
def expand_orbits(deque, num_expansions): r"""Takes a *deque* whose elements are a list of words. The following process is repeated *num_expansions* times. 1. Pop an orbit :math:`\mathcal{O} = [o_1, \dotsc, o_d]` from the left of the deque. 2. For :math:`i = 1, \dotsc, n` (where :math:`n` is the arity): a. Compute the new orbit :math:`\mathcal{O_i} =[o_1\alpha_i, \dotsc, o_d\alpha_i]` b. Append this orbit to the right of *deque*. Once complete, the number of orbits in *deque* has increased by :math:`\text{(arity -1) $\times$ num_expansions}` """ for _ in range(num_expansions): orbit = deque.popleft() arity = orbit[0].signature.arity for i in range(1, arity+1): new_orbit = tuple(w.alpha(i) for w in orbit) deque.append(new_orbit)