Examples

This module provides a number of explicit examples for use in doctests. Additionally, functions to generate random automorphisms are provided.

Explict named examples

A list of named examples is loaded from the .aut files in the examples folder. This includes all the examples given in the paper, as well as others used to test the package. Use the following functions to load one of these examples.

thompson.examples.available_examples()

Returns an iterator yielding the names of the examples that are provided with the package. (Note that the full list is provided in this documentation.)

>>> list(available_examples())[:4]
['alphabet_size_two', 'arity_four', 'arity_three_order_inf', 'bleak_alpha']

thompson.examples.load_example(name)

Loads the example with the given name from disk. A corresponding Automorphism instance is created and returned. The results are cached, so call this method as often as you like.

thompson.examples.load_example_pair(name)

Loads a pair of examples, *name*_psi and *name*_phi.

Return type:a 2-tuple of automorphisms.

thompson.examples.load_all_examples()

Loads (and processes) all examples provided by the package. Returns a dictionary whose keys are the example names and whose values are the loaded automorphisms.

Note

To discourage use of this function, it is not available when importing * from thompson.examples. Instead it must be explicitly imported with from thompson.examples import load_all_examples.

Warning

Some of the examples are slow to process, so calling this could take a long time.

thompson.examples.standard_generator(n=0)

Produces the standard generator \(X_n\) of \(F\) as described in [CFP96]. For instance, \(X_0\) is the following:

>>> print(standard_generator())
InfiniteAut: V(2, 1) -> V(2, 1) specified by 3 generators (after expansion and reduction).
x1 a1    -> x1 a1 a1
x1 a2 a1 -> x1 a1 a2
x1 a2 a2 -> x1 a2   

For \(n > 0\) the element \(X_n\) is a Mixed automorphism, consisting of a large fixed part and a smaller part which looks like \(X_0\).

>>> from random import randint
>>> n = randint(1, 20)
>>> x_n = standard_generator(n)
>>> type(x_n)
<class 'thompson.mixed.MixedAut'>

The \(X_n\) generate \(F\); in fact just \(X_0\) and \(X_1\) are sufficient, due to the relation \(X_k^{-1} X_n X_k = X_{n+1}\) for \(k < n\). See [CFP96] for more details.

>>> x_k = standard_generator(randint(0, n-1))
>>> x_k * x_n * ~x_k == standard_generator(n+1) #operation is the other way round in Python
True

Todo

Add the named generators A, B, C of Thompson’s T and V. Analogues for general G_n,r?

List of named examples

Note that some automorphisms have more than one name—they will appear once in this list for every alias.

alphabet_size_two

See the forest diagram and function plot.

A toy example to test that the program works in \(V_{3,2}\).

arity_four

See the forest diagram and function plot.

Another example for sanity checking. This is an automorphism of \(V_{4,1}\).

arity_three_order_inf

See the forest diagram and function plot.

A purely infinite automorphism of \(V_{3,1}\).

bleak_alpha

See the forest diagram and function plot.

The element \(\alpha\) of \(V\) used by Bleak et al [BBG11] to illustrate their train tracks and flow graphs.

bleak_klein_alpha

See the forest diagram and function plot.

The example in [BBG11] of an element whose centraliser contains the Klein four group \(\mathbb{Z_2 \oplus Z_2}\) as a subgroup. We have represented it as an element of \(G_{2, 8}\) rather than \(G_{2, 1}\).

bleak_klein_beta

See the forest diagram and function plot.

The example \(\beta\) in [BBG11] of an element generating a Klein four group as part of the centraliser of bleak_klein_alpha.

bleak_klein_gamma

See the forest diagram and function plot.

The example \(\gamma\) in [BBG11] of an element generating a Klein four group as part of the centraliser of bleak_klein_alpha.

commutator

See the forest diagram and function plot.

An element of the commutator subgroup of F. It has one bump and two fixed intervals.

cyclic_order_six

See the forest diagram and function plot.

An introductory example drawn on the board by NB. It is purely periodic of order six.

example_4_1

See the forest diagram and function plot.

This example is used in the paper to illustrate the meaning of a semi-normal form (Example 4.11) and of a tree pair diagram (Example 4.1).

example_4_12

See the forest diagram and function plot.

This example is used in the paper to illustrate the meaning of a semi-normal form. This example needs to be expanded from its minimal representation to find a semi-normal (in fact quasi-normal) form.

example_4_5

See the forest diagram and function plot.

This example is used to illustrate the different types of components/orbits in the paper.

example_5_12_phi

See the forest diagram and function plot.

The example used in the paper to demonstrate the periodic conjugacy test.

example_5_12_psi

See the forest diagram and function plot.

The example used in the paper to demonstrate the periodic conjugacy test.

example_5_15

See the forest diagram and function plot.

This example is used in the paper to illustrate the process of finding the quasi-normal basis.

example_5_26_psi

See the forest diagram and function plot.

The example used in the paper to demonstrate the infinite conjugacy test.

example_5_3

See the forest diagram and function plot.

This example is used to demonstrate how we can break down an automorphism into its free_factors().

example_5_9

See the forest diagram and function plot.

This example is used in the paper to illustrate the definition of cycle types.

example_6_2

See the forest diagram and function plot.

Example 6.2 of the paper, used to illustrate lemma 6.1.

example_6_8_phi

See the forest diagram and function plot.

A purely infinite automorphism which illustrates the bounds \(\hat a, \hat b\) for power conjugacy.

f_thirds_fixed

See the forest diagram and function plot.

An element of \(F\) whose fixed point set is exactly \(\{ 0, 1/3, 2/3, 1\}\).

first_pond_example_phi

See the forest diagram and function plot.

The example of a pond orbit we found by a random search. Its banks are \(x\alpha_1^4\alpha_2\) and \(x\alpha_1\alpha_2^2\).

first_pond_example_psi

See the forest diagram and function plot.

The element which was conjugate to first_pond_example_phi.

four_minimal_revealing_pairs

See the forest diagram and function plot.

I think this automorphism has 4 minimal revealing pairs. It has an orbit of characteristic (-4, a1^4) spread apart over four components of \(A \setminus B\). Brin’s algorithm would have you add three of these components to the tree, and I think the component you DON’T add is the one that determines the revealing pair.

inf_conj_phi

See the forest diagram and function plot.

An example used to debug the infinite conjugacy test.

inf_conj_psi

See the forest diagram and function plot.

An example used to debug the infinite conjugacy test.

mixed_pconj_phi

See the forest diagram and function plot.

An example of mixed power conjugacy found by random search. Should have \(\psi^{-4} \sim \phi^2\).

mixed_pconj_psi

See the forest diagram and function plot.

An example of mixed power conjugacy found by random search. Should have \(\psi^{-4} \sim \phi^2\).

mixed_plines

See the forest diagram and function plot.

An element of \(T\) with rotation number \(1/2\). The square of this element acts like \(x_0^2\) on the first and third quarters, and acts like the identity elsewhere. Thus it has two periodic flow lines and two pointwise periodic lines. The same is true of the square of mixed_plines_2, but even though it does not act as the identity on the second and fourth quarters.

mixed_plines_2

See the forest diagram and function plot.

An element of \(T\) with rotation number \(1/2\) and no fixed intervals. The square of this element acts like \(x_0^2\) on the first and third quarters, and acts like the identity elsewhere. Thus it has two periodic flow lines and two pointwise periodic lines. The same is true of the square of mixed_plines, which acts as the identity on the second and fourth quarters.

multiple_classes

See the forest diagram and function plot.

A purely infinite automorphism for which there are two equivalence classes defined on X.

multiple_classes_smaller

See the forest diagram and function plot.

A purely infinite automorphism for which there are two equivalence classes defined on X. It was more straightforward to see that this automorphism had two equivalence classes.

nathan1_example

See the forest diagram and function plot.

One of Nathan’s examples. This is almost, but not quite conjugate to nathan_pond_example. Nathan had this to say: “I untwisted one of the infinite orbits after a conjugation and so they definitely should not be conjugate.”

nathan_pond_example

See the forest diagram and function plot.

Nathan’s example of an automorphism containing a pond. This has a simpler tree pair than first_pond_example_phi.

no_minimal_revealing

See the forest diagram and function plot.

An example from section 3.6 of [SD10]. This is an automorphism \(f \in G_{2,1}\) for which there is no minimal revealing pair from which every other revaling pair can be obtained via rollings.

non_dyadic_fixed_point

See the forest diagram and function plot.

In their paper introducing strand diagrams, Belk and Matucci provide an example of an element of \(F\) which has a non-dyadic fixed point. This is a slight simplification of that example.

non_revealing

See the forest diagram and function plot.

A purely infinite automorphism for which - The minimal representation does NOT correspond to a revealing pair; and - The quasinormal basis does NOT correspond to a revealing pair.

not_conjugate_f

See the forest diagram and function plot.

An example of an element which isn’t conjugate to not_conjugate_g, even though it comes quite close to being so!

not_conjugate_g

See the forest diagram and function plot.

An element which is not conjugate to not_conjugate_f, even though it comes quite close to being so!

olga_f

See the forest diagram and function plot.

An automorphism described in example 5 of [SD10]. Nathan had this to say: “olga_f is conjugate to olga_g, via a rho that can be found using your program or olga_h. Note that characteristics are not the same for two of the semi-infinite orbits.”

olga_g

See the forest diagram and function plot.

An automorphism described in example 5 of [SD10]. Nathan had this to say: “olga_f is conjugate to olga_g, via a rho that can be found using your program or olga_h. Note that characteristics are not the same for two of the semi-infinite orbits.”

olga_gdash

See the forest diagram and function plot.

An automorphism described in example 5 of [SD10]. The paper claims that olga_f and olga_gdash are not conjugate.

olga_h

See the forest diagram and function plot.

An automorphism described in example 5 of [SD10]. Nathan had this to say: “olga_f is conjugate to olga_g, via a rho that can be found using your program or olga_h. Note that characteristics are not the same for two of the semi-infinite orbits.”

periodic_QNB_206

See the forest diagram and function plot.

This purely periodic automorphism (again found by random search) has a quasinormal basis of size 206.

periodic_QNB_344

See the forest diagram and function plot.

This purely periodic automorphism (again found by random search) has a quasinormal basis of size 344.

pond_width_4

See the forest diagram and function plot.

An example found by random search of a pond orbit of width 4. Prior to this we had only seen ponds of width 1 or 2.

power_smaller_QNB

See the forest diagram and function plot.

The square of this automorphism appears to have a QNB above the QNB of the original automorphism.

rotation_number_one_third

See the forest diagram and function plot.

An non-periodic element of T_{2,3} which should have rotation number 1/3.

scott_free_alpha

See the forest diagram and function plot.

The element alpha in the appendix of [Scott] which generates a free group of rank 2 with beta, also from the appendix.

scott_free_beta

See the forest diagram and function plot.

The element beta in the appendix of [Scott] which generates a free group of rank 2 with alpha, also from the appendix.

semi_inf_c

See the forest diagram and function plot.

An example of an automorphism whose quasi-normal basis \(X\) contains an element \(x\alpha_2\alpha_1\) which belongs to a semi-infinite \(X\)-component which is not characteristic.

t_generator_c

See the forest diagram and function plot.

This is the element C used by Cannon, Floyd and Parry to generate Thompson’s group T.

thirds_fixed

See the forest diagram and function plot.

This element of T has only two fixed points: 1/3 and 2/3; note that these are non dyadic!

two_flow_components_d

See the forest diagram and function plot.

An example which found a bug in the infinite conjugacy test. This automorphism contains two flow components which are identical in all but their location.

two_flow_components_e

See the forest diagram and function plot.

An example which found a bug in the infinite conjugacy test. This automorphism is a conjugated version of two_flow_components_d.

v_generator_pi

See the forest diagram and function plot.

This is the generator \(\pi_0\) used by Cannon, Floyd and Parry to generate V.

v_revealing_test

See the forest diagram and function plot.

A short example used to test the is_revealing method

Randomly generated examples

Words

thompson.examples.random_signature()

Randomly generates a Signature \((n, r)\) for use in the functions below. The values of \(n\) and \(r\) are chosen (uniformly) at random from \(n \in \{2, 3, 4\}\) and \(r \in \{1, 2, 3, 4, 5\}\), respectively.

Note

This function is used to select a random signature when no signature argument is provided to the following random functions.

thompson.examples.random_simple_word(signature=None)

Randomly generates a simple Word belonging to the algebra with the given signature. The word consists of an \(x_i\) followed by 0–15 descendant operators \(\alpha_j\). The length and the index of each \(\alpha_j\) is chosen (uniformly) at random.

>>> random_simple_word().is_simple()
True

thompson.examples.random_basis(signature=None, num_expansions=None, *args, **kwargs)

Randomly generates a basis for the algebra with the given signature \((n,r)\). The basis is generated by expanding the standard_basis() num_expansions times. The expansion point is chosen (uniformly) at random each time. If num_expansions is not provided, a value from \(\{1, 2, 3, 4, 5\}\) is chosen (uniformly) at random.

>>> random_basis().is_basis()
True

The cls argument specifies which class the generated basis should have; this should be a subclass of Generators. At the moment, this is only used internally and experimentally.

Note

This does not generate bases uniformly at random. For instance, take \(V_{n,r} = V_{2,1}\) and let num_expansions = 3. The first expansion always gives the basis \([x\alpha_1, x\alpha_2]\). Expanding this twice produces give six bases, one of which appears twice. (To see this, enumerate the rooted binary trees with four leaves.)

Automorphisms

thompson.examples.random_automorphism(signature=None, num_expansions=None, *args, **kwargs)

Randomly generates an automorphism for the algebra with the given signature. Two bases domain and range are generated by random_basis(). Then the range is manipulated according to the group we’re interesting in. For group == 'V', we randomly shuffle the range; for group == 'T', we cyclicly permute the range; for group == 'F' we do nothing.

>>> random_automorphism(group='T').cycles_order()
True
>>> random_automorphism(group='F').preserves_order()
True

An automorphism is returned which maps the elements of domain to those of range in whichever order results.

Note

The bases may be reduced when the automorphism is created (if they contain redundancy).

thompson.examples.random_periodic_automorphism(signature=None, num_expansions=None, *args, **kwargs)

Randomly generates an automorphism for the algebra with the given signature. A basis domain is generated by random_basis(). A copy range is made of domain, and is then randomly shuffled. An automorphism is returned which maps the elements of domain to those of range in order.

Note

The bases may be reduced when the automorphism is created (if they contain redundancy.

thompson.examples.random_infinite_automorphism(signature=None, num_expansions=None, *args, **kwargs)

Randomly generates an infinite automorphism—either by chance, or by extracting an infinite free_factor().

Todo

The implementation is inefficient: just make auts at random until you find an infinite one. Fix this!

thompson.examples.random_conjugate_pair(signature=None, num_expansions=None, *args, **kwargs)

Calls random_automorphism() to create two automorphisms \(\psi\) and \(\rho\). Returns the pair \((\psi, \rho^{-1}\psi\rho)\), which are conjugate by definition.

thompson.examples.random_conjugate_periodic_pair(signature=None, num_expansions=None, *args, **kwargs)

The same as random_conjugate_pair(), except \(\psi\) is chosen to be a random_periodic_automorphism().

thompson.examples.random_conjugate_infinite_pair(signature=None, num_expansions=None, *args, **kwargs)

The same as random_conjugate_pair(), except \(\psi\) is chosen to be a random_infinite_automorphism().

thompson.examples.random_power_conjugate_pair(signature=None, num_expansions=None, *args, **kwargs)

Generates \(\psi, \rho\) using random_automorphism() and random powers \(a, b\). Returns the tuple \((\Psi, \Phi) = (\psi^b, \rho^{-1}\psi^a\rho)\). Note that \(\Psi^a\) is conjugate to \(\Phi^b\) via \(\rho\).