Automorphisms¶

As usual, a bijective homomorphism is called an isomorphism, and an isomorphism from an algebra to itself is called an automorphism. A collection of automorphisms of an object $O$ forms a group $\mathrm{Aut}(O)$ under composition. The group of automorphisms $\mathrm{Aut}(V_{n,r})$ is known as $G_{n,r}$.

We consider three different classes of automorphism; this module implements functionality common to each class.

The Automorphisms class¶

class thompson.automorphism.Automorphism(domain, range, reduce=True)[source]¶

Represents an automorphism as a bijection between bases.

Generic attributes:

Variables:	signature – The `Signature` shared by the generating sets domain and range. quasinormal_basis – See `compute_quasinormal_basis()`. pond_banks – A list of tuples $(\ell, k, r)$ such that $(\ell, r)$ are banks of a pond with $\ell\phi^k = r$. (See also 4.15 of the paper.)

>>> olga_f = load_example('olga_f')
>>> olga_g = load_example('olga_g')
>>> olga_f.signature
Signature(arity=2, alphabet_size=1)
>>> print(len(olga_f.pond_banks)) #No ponds
0
>>> print(len(olga_g.pond_banks)) #One pond
1
>>> print(*olga_g.pond_banks[0], sep=',  ') 
x1 a2 a1 a2 a1 a1,  2,  x1 a1 a2 a2

Periodic attributes:

Variables:

cycle_type – the set $\{d \in \mathbb{N} : \text{$\exists$ an orbit of length $d$.}\}$. This is implemented as a frozenset which is a readonly version of Python’s set type.
order – The lcm() of the automorphism’s cycle type. This is the group-theoretic order of the periodic factor of $\phi$. If the cycle type is empty, the order is $\infty$. NB: mixed automorphisms will have a finite order, despite being infinite-order group elements.
periodic_orbits – a mapping $d \mapsto L_d$, where $L_d$ is the list of size $d$ orbits in the quasinormal basis.
multiplicity – a mapping $d \mapsto m_\phi(d, X_\phi)$, which is the number of periodic orbits of size $d$ in the quasinormal basis for $\phi$. See Definition 5.8 in the paper.

>>> olga_f.cycle_type
frozenset()
>>> olga_f.order
inf
>>> f = load_example('cyclic_order_six')
>>> f.cycle_type
frozenset({1, 2, 3})
>>> f.order
6
>>> def display_orbits(orbits_by_size):
...     for key in sorted(orbits_by_size):
...             print('Orbits of length', key)
...             for list in orbits_by_size[key]:
...                     print('...', *list, sep=' -> ', end=' -> ...\n')
>>> display_orbits(load_example('example_5_9').periodic_orbits)
Orbits of length 2
... -> x1 a2 a1 a1 -> x1 a2 a1 a2 -> ...
... -> x1 a2 a2 a1 -> x1 a2 a2 a2 -> ...
Orbits of length 3
... -> x1 a1 a1 a1 -> x1 a1 a1 a2 -> x1 a1 a2 -> ...

Infinite attributes:

Variables:	characteristics – the set of characteristics $(m, \Gamma)$ of this automorphism. Like the `cycle_type` above, this is a `frozenset`.

>>> for char in sorted(olga_f.characteristics):
...             #TODO the order here isn't sorted intuitively
...     print(char)
Characteristic(-1, a2)
Characteristic(-1, a1)
Characteristic(2, a2 a1)
Characteristic(2, a1 a2)

__init__(domain, range, reduce=True)[source]¶

Creates an automorphism mapping the given domain basis to the range basis in the given order. That is, $\text{domain}_{\,i} \mapsto \text{range}_{\,i}$.

The quasi-normal basis $X$ and the various attributes are all calculated at creation time.

Raises:	TypeError – if the bases have different arities or alphabet sizes. TypeError – if either basis `isn't actually a basis`.

See also

The superclass' method.

classmethod from_dfs(domain, range, labels=None, reduce=True)[source]¶

Creates elements of $V=G_{2,1}$ using the notation of [Kogan].

The domain and range trees are described as a string of ones and zeros. A 1 denotes a vertex which has children; a 0 denotes a vertex which has none (i.e. a leaf). The ‘dfs’ stands for depth-first search, the order in which we traverse the vertices of the tree. We initialise the current vertex as the root. Upon reading a 1 we add two child vertices to the current vertex, then redeclare the current vertex to be the current vertex’s left child. Upon reading a 0 we set the current vertex to be the next vertex of the tree in depth-first order. If the current vertex is the root we are done.

Parameters:

domain (str) – A description of a binary tree as a stream of ones and zeroes.
range (str) – The same.
labels (str) – A string of natural numbers $1, \dots, m$ in some order. If omitted, taken to be the string "1 2 "..."len(domain)". If a single string n, taken to be the cyclic permuation mapping $1 \mapsto n$.
reduce (bool) – Passed to the superclass' initialiser method. If True, carets are reduced in the domain and range where possible.

>>> f = Automorphism.from_dfs("100", "100", "2 1")
>>> f.order
2
>>> print(f)
PeriodicAut: V(2, 1) -> V(2, 1) specified by 2 generators (after expansion and reduction).
x1 a1 -> x1 a2
x1 a2 -> x1 a1
>>> Automorphism.from_dfs("100", "100", "2") == f
True

>>> g = Automorphism.from_dfs("1010100", "1011000")
>>> print(g)
MixedAut: V(2, 1) -> V(2, 1) specified by 4 generators (after expansion and reduction).
x1 a1       -> x1 a1      
x1 a2 a1    -> x1 a2 a1 a1
x1 a2 a2 a1 -> x1 a2 a1 a2
x1 a2 a2 a2 -> x1 a2 a2   
>>> g == standard_generator(1)
True

>>> h = load_example("example_6_2")
>>> h2 = Automorphism.from_dfs("1110000", "1100100", "3 1 2 4")
>>> h == h2
True

classmethod rotation(numerator, denominator=None)[source]¶

Constructs an automorphism which represents a rotation when thought of as a homeomorphism of the circle. The displacement of this rotation be a dyadic rational. If both arguments are given, the displacement is numerator/denominator; if only one argument is given, the displacement is the result of passing numerator to the constructor of Fraction.

Note

This only works in $T_{2,1}$, but could be modified in future to work for different arities.

Raises:	ValueError – if the displacement is not dyadic.
Returns:	`PeriodicAut`

>>> print(Automorphism.rotation(1, 2))
PeriodicAut: V(2, 1) -> V(2, 1) specified by 2 generators (after expansion and reduction).
x1 a1 -> x1 a2
x1 a2 -> x1 a1
>>> print(Automorphism.rotation(3, 8))
PeriodicAut: V(2, 1) -> V(2, 1) specified by 8 generators (after expansion and reduction).
x1 a1 a1 a1 -> x1 a1 a2 a2
x1 a1 a1 a2 -> x1 a2 a1 a1
x1 a1 a2 a1 -> x1 a2 a1 a2
x1 a1 a2 a2 -> x1 a2 a2 a1
x1 a2 a1 a1 -> x1 a2 a2 a2
x1 a2 a1 a2 -> x1 a1 a1 a1
x1 a2 a2 a1 -> x1 a1 a1 a2
x1 a2 a2 a2 -> x1 a1 a2 a1
>>> Automorphism.rotation(0) == Automorphism.rotation(100) == Automorphism.identity((2, 1))
True

>>> denominator = 2 ** randint(1, 10)
>>> numerator = randrange(denominator)
>>> rot = Automorphism.rotation(numerator, denominator)
>>> rot.rotation_number() == Fraction(numerator, denominator)
True
>>> rot.cycles_order()
True
>>> rot.preserves_order() == (numerator == 0)
True

image(key, inverse=False)[source]¶

If inverse is True, the inverse of the current automorphism is used to map key instead. Otherwise this method delegates to Homomorphism.image.

As a shorthand, we can use function call syntax in place of this method. For instance:

>>> phi = load_example('example_5_15')
>>> print(phi('x1 a2 a2 a1 a1'))
x1 a2 a2

Examples of finding inverse images:

>>> phi = load_example('example_5_15')
>>> print(phi.image('x1 a2 a2', inverse=True))
x1 a2 a2 a1 a1
>>> print(phi.image('x1 a1 a1 a2 a2 a1', inverse=True))
x1 a2 a1 a2 a1
>>> print(phi.image('x a2', inverse=True))
x1 a2 a2 a2 x1 a2 a2 a1 a1 L
>>> print(phi.image('x a2 a2 x a1 a2 L', inverse=True))
x1 a2 a2 a1

image_of_set(set, inverse=False)[source]¶

If inverse is True, the inverse of the current automorphism is used to map set instead. Otherwise this method delegates to Homomorphism.image_of_set.

Examples of finding inverse images:

>>> basis = Generators.standard_basis((2,1))
>>> basis.expand_to_size(8);
>>> print(load_example('example_5_3').image_of_set(basis, inverse=True))
[x1 a1 a1 a1 a1, x1 a1 a1 a1 a2 x1 a1 a1 a2 L, x1 a1 a2 a2, x1 a1 a2 a1, x1 a2 a1, x1 a2 a2 a1, x1 a2 a2 a2 a1, x1 a2 a2 a2 a2]

repeated_image(key, power)[source]¶

If $\psi$ is the current automorphism, returns $\text{key}\psi^\text{ power}$.

Return type:	a `Word` instance.

>>> phi = load_example('example_5_15')
>>> print(phi.repeated_image('x1 a1', 10))
x1 a1 a1 a1 a1 a1 a1 a1 a1 a1 a1 a1 a1 a1 a1 a1 a1 a1 a1 a1 a1 a1
>>> print(phi.repeated_image('x1 a1 a1 a1 a1 a1 a1 a1', -3))
x1 a1
>>> phi = load_example('arity_four')
>>> print(phi.repeated_image('x1 a4 a4 a2', 4))
x1 a3 a3 a2
>>> print(phi.repeated_image('x1 a3 a3 a2', -4))
x1 a4 a4 a2

Todo

This could be made more efficient for large values of power by using knowledge of the component containing key.

__pow__(power)[source]¶

Python uses the double star operator to denote exponentiation.

>>> psi = random_automorphism()
>>> psi ** 0 == 1 #identity
True
>>> ~psi ** 2 == ~psi * ~psi == psi ** -2
True

__invert__()[source]¶

We overload python’s unary negation operator ~ as shorthand for inversion. (In Python, ~ is normally used for bitwise negation.) We can also call a method explicitily: phi.inverse() is exactly the same as ~phi.

>>> phi = random_automorphism()
>>> phi * ~phi == ~phi * phi
True
>>> (phi * ~phi).is_identity()
True
>>> (~phi).quasinormal_basis == phi.quasinormal_basis
True

__xor__(other)[source]¶

We overload the bitwise exclusive or operator ^ as a shorthand for conjugation. We act on the right, so that $s^c = c^{-1}sc$.

>>> sig = random_signature()
>>> f = random_automorphism(signature=sig)
>>> g = random_automorphism(signature=sig)
>>> h = f^g
>>> f.is_conjugate_to(h)
True
>>> f ^ (f.test_conjugate_to(h)) == h
True

compute_quasinormal_basis()[source]¶

We say that $\phi$ is in semi-normal form with respect to the basis $X$ if no element of $X$ lies in an incomplete $X$-component of a $\phi$ orbit. See the orbits module for more details.

There is a minimal such basis, $X_\phi$ say, and we say that $\phi$ is in quasi-normal form with respect to $X_\phi$. This method determines and returns the basis $X_\phi$ where $\phi$ denotes the current automorphism. The result is cached so that further calls to this method perform no additional computation.

Note

This method is called automatically at creation time and does not need to be called by the user.

>>> for name in ['example_4_5', 'alphabet_size_two', 'example_5_12_phi', 'example_6_2', 'example_6_8_phi']:
...     print(load_example(name).quasinormal_basis)
[x1 a1 a1, x1 a1 a2, x1 a2 a1, x1 a2 a2]
[x1 a1, x1 a2, x1 a3, x2]
[x1 a1, x1 a2]
[x1 a1 a1, x1 a1 a2, x1 a2]
[x1 a1, x1 a2]

Return type:	a `Generators` instance.

See also

Quasi-normal forms are introduced in Section 4.2 of the paper. In particular, this method implements Lemma 4.28. Higman first described the idea of quasi-normal forms in Section 9 of [Hig74].

seminormal_form_start_point()[source]¶

Returns the minimal expansion $X$ of $\boldsymbol{x}$ such that every element of $X$ belongs to either self.domain or self.range. Put differently, this is the minimal expansion of $\boldsymbol{x}$ which does not contain any elements which are above $Y \cup Z$. This basis that this method produces is the smallest possible which might be semi-normal.

>>> for name in ['example_4_5', 'example_4_11', 'example_4_12', 'example_5_15', 'cyclic_order_six']:
...     print(load_example(name).seminormal_form_start_point())
[x1 a1 a1, x1 a1 a2, x1 a2 a1, x1 a2 a2]
[x1 a1, x1 a2]
[x1 a1, x1 a2]
[x1 a1, x1 a2 a1, x1 a2 a2]
[x1 a1 a1, x1 a1 a2 a1, x1 a1 a2 a2, x1 a2]

See also

Remark 4.10 of the paper.

orbit_type(y, basis=None)[source]¶

Returns the orbit type of y with respect to the given basis. If basis is omitted, the quasi-normal basis is used by default. Also returns a dictionary of computed images, the list (4.6) from the paper.

Returns:	A triple `(ctype, images, type_b_data)`.

>>> phi = load_example('example_4_5')
>>> print_component_types(phi, phi.domain)
x1 a1 a1 a1: Left semi-infinite component with characteristic (-1, a1)
x1 a1 a1 a2: Bi-infinite component
x1 a1 a2: Right semi-infinite component with characteristic (1, a2)
x1 a2 a1: Periodic component of order 2
x1 a2 a2: Periodic component of order 2
with respect to the basis [x1 a1 a1 a1, x1 a1 a1 a2, x1 a1 a2, x1 a2 a1, x1 a2 a2]
>>> print_component_types(phi, basis=phi.domain, words=['x', 'x a1', 'x a2'])
x1: Incomplete component
x1 a1: Incomplete component
x1 a2: Incomplete component
with respect to the basis [x1 a1 a1 a1, x1 a1 a1 a2, x1 a1 a2, x1 a2 a1, x1 a2 a2]

Components can be calculated with respect to any basis, not just the quasi-normal basis.

>>> print(olga_f.quasinormal_basis)
[x1 a1 a1, x1 a1 a2, x1 a2 a1, x1 a2 a2 a1, x1 a2 a2 a2]
>>> basis = olga_f.quasinormal_basis.copy().expand(-1); print(basis)
[x1 a1 a1, x1 a1 a2, x1 a2 a1, x1 a2 a2 a1, x1 a2 a2 a2 a1, x1 a2 a2 a2 a2]
>>> from pprint import pprint
>>> print(olga_f.orbit_type('x a2 a2 a2')[0])
Bi-infinite component
>>> print(olga_f.orbit_type('x a2 a2 a2', basis)[0])
Incomplete component

See also

Lemmas 4.18, 4.28 of the paper.

Todo

This should be renamed to component_type.

test_semi_infinite(y, basis, backward=False)[source]¶

Computes the orbit type of y under the current automorphism $\psi$ with respect to basis in the given direction. Let $y\psi^m$ be the most recently computed image. The process stops when either:

$y\psi^m$ is not below the basis, for some $m\geq 0$.

infinite: False

start: 0

end: m-1

images: $y, y\psi, \dotsc, y\psi^{m-1}$.

For some $0 \le l < m$, $y\psi^l$ is above (or equal to) $y\psi^m$.

infinite: True

start: l

end: m

images: $y, y\psi, \dotsc, y\psi^{m}$.

Note

The word $y\psi^m$ is not strictly in the core part of the orbit of Lemma 4.24. We return this as part of images so that we can compute the characteristic multiplier in orbit_type().

Returns:	the tuple (infinite, start, end, images).

See also

Lemma 4.28 of the paper.

semi_infinite_end_points(exclude_characteristics=False)[source]¶

Returns the list of terminal Words in left semi-infinite components and the list of initial words in right semi-infinite components. This is all computed with respect the current automorphism’s quasinormal basis. These are the sets $X\langle A\rangle \setminus Y\langle A\rangle$ and $X\langle A\rangle \setminus Z\langle A\rangle$.

Parameters:	exclude_characteristics – if True, only the endpoints of non-characteristic semi-infinite orbits will be returned.

>>> for id in ['4_5', '4_11', '4_12', '5_15', '6_2']:
...     aut = load_example('example_' + id)
...     print(*aut.semi_infinite_end_points())
[x1 a1 a1] [x1 a1 a2]
[x1 a1] [x1 a2]
[] []
[x1 a2 a2, x1 a2 a2 a1] [x1 a1, x1 a1 a1]
[x1 a1 a1] [x1 a2]
>>> phi = load_example('nathan_pond_example')
>>> print(*phi.semi_infinite_end_points())
[x1 a1 a1, x1 a1 a1 a1, x1 a1 a1 a2] [x1 a1 a2, x1 a1 a2 a1, x1 a1 a2 a2]
>>> print(*phi.semi_infinite_end_points(exclude_characteristics=True))
[x1 a1 a1 a2] [x1 a1 a2 a2]

Return type:	A pair of `Generators`.

See also

The discussion before Lemma 4.6.

dump_QNB()[source]¶

A convenience method for printing the quasinormal basis $X$. The $X$-components of the elements $x \in X$ are displayed.

>>> load_example('example_5_3').dump_QNB()
x1 a1 a1 a1 Left semi-infinite component with characteristic (-1, a1)
x1 a1 a1 a2 Right semi-infinite component with characteristic (1, a2)
x1 a1 a2 a1 Periodic component of order 2
x1 a1 a2 a2 Periodic component of order 2
x1 a2 a1 Right semi-infinite component with characteristic (1, a1)
x1 a2 a2 Left semi-infinite component with characteristic (-1, a2)

dump_periodic(cantor=False)[source]¶

A convenience method for printing out periodic orbits in the quasinormal basis.

>>> f = load_example("cyclic_order_six")
>>> f.dump_periodic()
Period 1
x1 a1 a1
Period 2
x1 a1 a2 a2 a1 -> x1 a2 a1
Period 3
x1 a1 a2 a1 -> x1 a1 a2 a2 a2 -> x1 a2 a2
>>> f.dump_periodic(cantor=True)
Period 1
00
Period 2
0110 -> 10
Period 3
010 -> 0111 -> 11

print_characteristics()[source]¶

For convenience, a method that prints out all of the characteristics of type B components wrt the quasinormal_basis.

>>> for id in ['4_1', '5_15', '6_2', '6_8_phi']:
...     name = 'example_' + id
...     print(name)
...     load_example(name).print_characteristics()
example_4_1
(-1, a1)
(1, a2)
example_5_15
(-1, a1 a1)
(1, a1 a1)
example_6_2
(-2, a1)
(1, a2)
example_6_8_phi
(-1, a1 a1 a1)
(1, a2 a2 a2)
>>> (load_example('example_6_2')**2).print_characteristics()
(-1, a1)
(1, a2 a2)
>>> #Lemma 5.16
>>> psi, phi = random_conjugate_pair()
>>> psi.characteristics == phi.characteristics
True

See also

Defintion 5.14.

share_orbit(u, v)[source]¶

Determines if $u$ and $v$ are in the same orbit of the current automorphism $\psi$. Specifically, does there exist an integer $m$ such that $u\psi^m = v$?

>>> phi = load_example('alphabet_size_two')
>>> u  = Word('x1 a2 a3 a1 a2', (3, 2))
>>> v1 = Word('x1 a1 a2 a2 a3 a1', (3, 2))
>>> v2 = Word('x2 a3 a2', (3, 2))
>>> print(phi.share_orbit(u, v1))
{}
>>> print(phi.share_orbit(u, v2))
{-2}
>>> print(phi.share_orbit(u, u))
{0}

Returns:	The (possibly empty) `SolutionSet` of all integers $m$ for which $u\psi^m = v$. Note that if $u = v$ this method returns $\mathbb{Z}$.

See also

The implementation is due to lemma 4.34 of the paper.

is_conjugate_to(other)[source]¶: A shortcut for self.test_conjugate_to(other) is not None.

preserves_order()[source]¶

Returns True if this automorphism is an element of $F_{n,r}$, Higman’s analogue of Thompson’s group $F$. Otherwise returns False.

>>> random_automorphism(group='F').preserves_order()
True
>>> phi = random_automorphism(group='T')
>>> #phi preserves order iff it is in F.
>>> (sorted(phi.range) == phi.range) == phi.preserves_order()
True
>>> load_example('nathan_pond_example').preserves_order()
False

cycles_order()[source]¶

Returns True if this automorphism is an element of $T_{n,r}$, Higman’s analogue of Thompson’s group $T$. Otherwise returns False.

>>> random_automorphism(group='F').cycles_order()
True
>>> random_automorphism(group='T').cycles_order()
True
>>> load_example('nathan_pond_example').cycles_order() # in V \ T
False

rotation_number()[source]¶

The rotation number is a map $\operatorname{Homeo}_+(\mathbb{S}^1) \to \mathbb{R/Z}$ which is constant on conjugacy classes.

Return type:	`Fraction` if the current automorphism is a `circle homeomorphism`; otherwise None.

>>> f = random_automorphism()
>>> rot = f.rotation_number()
>>> (rot is None) == (not f.cycles_order())
True
>>> sig = random_signature()
>>> Automorphism.identity(sig).rotation_number() == 0
True
>>> g = random_automorphism(group='T', signature=sig)
>>> k = random_automorphism(group='T', signature=sig)
>>> (g^k).rotation_number() == g.rotation_number()
True

>>> f_examples = "example_4_1 example_4_11 example_6_8_psi example_6_9_psi non_dyadic_fixed_point".split()
>>> all( load_example(name).rotation_number() == 0 for name in f_examples )
True
>>> t_examples = "example_4_1 example_5_12_phi example_6_8_phi non_dyadic_fixed_point rotation_number_one_third scott_free_alpha thirds_fixed".split()
>>> for name in t_examples:
...     print(load_example(name).rotation_number())
0
1/2
0
0
1/3
0
0

commutes(other)[source]¶

A shorthand for the expression self * other == other * self.

>>> x = random_automorphism()
>>> x.commutes(x)
True
>>> x.commutes(~x)
True
>>> x.commutes(1)
True
>>> x.commutes(x*x)
True

test_revealing(domain='wrt QNB')[source]¶

Determines if the given automorphism $\phi$ is revealed by the tree pair $(D, \phi(D))$, where $D$ is the given domain.

The domain may be implicitly specified by the string 'minimal' or 'wrt QNB'. In the first case, domain is taken to be the minimal domain required to specify the automorphism. In the second case, domain is taken to be the minimal expansion of the quasinormal basis.

Returns:	None if the pair is revealing for $\phi$. Otherwise, returns (as a `Word`) the root of a component of either $D \setminus \phi(D)$ or $\phi(D) \setminus D$ which does not contain an attractor/repeller.

>>> load_example('olga_f').test_revealing() is None
True
>>> print(load_example('semi_inf_c').test_revealing())
x1 a2 a1
>>> print(load_example('non_revealing').test_revealing())
x1 a1 a1
>>> f = load_example('cyclic_order_six')
>>> print(f.test_revealing('minimal'))
x1 a2
>>> f.test_revealing('wrt QNB') is None
True

Caution

This is an experimental feature based on [SD10].

Todo

This method is badly named; something like test_revealed_by(basis) would be better.

is_revealing(domain='wrt QNB')[source]¶

Calls test_revealing(), but only returns True or False.

Returns:	True if the pair is revealing, otherwise False.

>>> load_example('olga_f').is_revealing()
True
>>> load_example('semi_inf_c').is_revealing()
False
>>> load_example('non_revealing').is_revealing()
False
>>> f = load_example('cyclic_order_six')
>>> f.is_revealing('minimal')
False
>>> f.is_revealing('wrt QNB')
True
>>> load_example('v_revealing_test').is_revealing()
False

Caution

This is an experimental feature based on [SD10].

Todo

This method is badly named; something like is_revealed_by(basis) would be better.

periodic_points(include_intervals=True)[source]¶

Identifies the intervals and points which are (pointwise) peridically mapped under the current automorphism. Pointwise periodic intervals are represented as :class`~thompson.word.Word`s; isolated periodic points are represented as Fraction s.

Parameters:	include_intervals (bool) – If False, intervals are not included in the output. If the current automorphism is in T, the result is the boundary of the set of fixed points.
Returns:	an `OrderedDict` mapping periodic objects to their period size.

Caution

This is an experimental feature and provides different information to fixed_points().

fixed_points()[source]¶

Returns a list of Fraction and :class`~thompson.word.Word`s which are the fixed points and intervals of this function.

>>> print( *Automorphism.identity((2, 1)).fixed_points() , sep=" ")
x1
>>> standard_generator().fixed_points()
[Fraction(0, 1), Fraction(1, 1)]
>>> f = load_example("non_dyadic_fixed_point")
>>> f.fixed_points()
[Fraction(0, 1), Fraction(1, 3), Word('x1 a2 a2', (2, 1))]
>>> x = Automorphism.from_dfs("1101000", "1100100", "2 3 4 1")
>>> x.fixed_points()
[Fraction(1, 2)]
>>> y = Automorphism.from_dfs("1101000", "1011000", "2 3 4 1")
>>> y.fixed_points()
[Fraction(1, 3), Fraction(2, 3)]

>>> f = random_automorphism()
>>> fixed_intervals = (x for x in f.fixed_points() if isinstance(x, Word))
>>> all( f(interval) == interval for interval in fixed_intervals )
True

Caution

This is an experimental feature.

fixed_point_boundary(on_circle=False)[source]¶

Replaces any intervals in the output of fixed_points() with their endpoints.

>>> f = load_example("non_dyadic_fixed_point")
>>> f.fixed_point_boundary()
[Fraction(0, 1), Fraction(1, 3), Fraction(3, 4), Fraction(1, 1)]

Parameters:	on_circle (bool) – if True, treat 0 and 1 as the same point.

>>> f.fixed_point_boundary(on_circle=True)
[Fraction(0, 1), Fraction(1, 3), Fraction(3, 4)]

area_to_identity(scaled=False)[source]¶

Let $\phi \in F_{n, 1}$, viewed as a bijection of the interval. What is the (unsigned) area between $\phi$ and the identity?

Parameters:	scaled (bool) – If true, the area is normalised by ignoring subintervals where the function is equal to the identity.

Warning

This is an experimental feature based on a suggestion by Henry Bradford.

>>> for n in range(4):
...     print(standard_generator(n).area_to_identity())
... 
5/32
5/128
5/512
5/2048
>>> x0 = standard_generator(0)
>>> x1 = standard_generator(1)
>>> g = ~x0 * x1 * x0
>>> print(g.area_to_identity())
3/32
>>> f = load_example('non_dyadic_fixed_point')
>>> print(f.area_to_identity())
43/768

>>> for n in range(4):
...             print(standard_generator(n).area_to_identity(scaled=True))
5/32
5/32
5/32
5/32

centralise_period(period, trees, rearranger)[source]¶

Constructs a new element $\psi$ commuting with the given element $\phi$. We construct the centralising element by altering the $\phi$-orbit structure below the orbits of the given period.

There are two parameters: a collection of labelled trees and a rearranger element; in the notation of [BBG11] these are elements of $K_{m_i}$ and $G_{n, r_i}$ respectively.

Todo

doctests

Caution

This is an experimental feature based on [BBG11].

gradients_around(x)[source]¶

Let $x \in \mathbb{Q} \cap [0, 1]$. What’s the gradient to the left of $x$ and right of $x$? If $x$ is a breakpoint it could be different; if not, it’ll be the same number on both sides.

Return type:	2-`tuple` of `fractions.Fraction`.

>>> f = standard_generator(0)
>>> f.gradients_around(5/6)
(Fraction(2, 1), Fraction(2, 1))
>>> f.gradients_around(1/2)
(Fraction(1, 2), Fraction(1, 1))
>>> f.gradients_around(0)
(Fraction(2, 1), Fraction(1, 2))

>>> g = load_example("alphabet_size_two")
>>> g.gradients_around(1/2)
(Fraction(3, 1), Fraction(1, 1))
>>> g.gradients_around(1/3)
(Fraction(1, 3), Fraction(1, 3))
>>> #One third is a breakpoint, but floating point can't accurately represent one third. Need to use a Fraction here
>>> g.gradients_around(Fraction(1, 3))
(Fraction(1, 3), Fraction(3, 1))
>>> g.gradients_around(0)
(Fraction(1, 3), Fraction(1, 1))

Membership placeholders¶

As an alternative to using the preserves_order() and cycles_order() methods, we provide two objects F, T which know how to respond to the in operator.

>>> f = random_automorphism(group='F')
>>> f in F and f in T
True
>>> t = load_example('scott_free_alpha')
>>> t not in F and t in T
True

Next steps¶

Because an Automorphism can be repeatedly applied, we may consider the orbit $\{w\psi^n \mid n \in \mathbb{Z}\}$ of any word $w$. (Note that this is the orbit of $w$ under the cyclic subgroup $\langle \psi \rangle$, rather than all of $G_{n,r}$.)

The next module gives us tools to classify and work with these orbits. (In truth, the Automorphism class uses these tools, so this documentation is really in the wrong order.)