Orbits

Let \(y\) be a word, and let \(X\) be an expansion of the standard basis \(\boldsymbol{x}=\{x_1, \dotsc, x_n\}\); finally let \(\phi\) be an MixedAut. We call the set \(\mathrm{orb}_\phi(y) = \{ y \phi^i\}_{i\in \mathbb Z}\) the \(\phi\)-orbit of \(y\). Let us refer to the intersection \(\mathrm{orb}_\phi (y) \cap X\langle A \rangle\) as the \(X\) -component of (the \(\phi\)-orbit of) \(y\). Higman demonstrated how we could classify these components in [Hig74] (section 9).

This module is responsible for two orbit-related data structures. Firstly, ComponentType is set up to describe all possible types of orbits according to Higman’s scheme. Secondly, the SolutionSet describes solutions to the equation \(u \phi^i = v\).

Types of orbits and components

These components come in five different types:

  1. Complete infinite components.

    The component is the entire orbit \(\{ y \phi^i\}_{i\in \mathbb Z}\) and each element of the orbit is different.

  2. Complete finite components.

    The component is the entire orbit, which eventually it repeats itself. Thus the component only contains a finite number of distinct words.

  3. Right semi-infinite components.

    The forward orbit \(\{ y \phi^n\}_{n\in \mathbb N}\) belongs to the component and does not repeat itself. However, the backward orbit \(\{ y \phi^{-n}\}_{n\in \mathbb N}\) eventually leaves \(X\langle A\rangle\); thus the component only contains a finite amount of the backward orbit.

  4. Left semi-infinite components.

    The backward orbit is contained in the component, and does not repeat itself; the forward orbit eventually leaves \(X\langle A\rangle\).

  5. Incomplete finite components.

    A finite part of the orbit

    \[y\phi^{-n}, \dotsc, y\phi^{-1}, y, y\phi, \dotsc, y\phi^m\]

    for which both \(y\phi^{-n-1}\) and \(y\phi^{m+1}\) are not in \(X\langle A\rangle\).

There are six different ways we can form orbits using these components:

  • Complete infinite (or doubly infinite) orbits.
    The entire orbit is a complete infinite component (type 1).
  • Complete finite (or periodic) orbits.
    The entire orbit is a component finite component (type 2).
  • Incomplete finite (or bad) orbits.
    The orbit does not contain any complete or semi-infinite components. Thus the only components which may appear are of type 5. Note that these orbits need not have any components at all!
  • Incomplete infinite orbits.
    The orbit contains at least one semi-infinite component (types 3, 4). The orbit may also contain incomplete finite components (type 5). We give names to the different cases:
    • Right semi-infinite orbits.
      One component of type 3, none of type 4.
    • Left semi-infinite orbits.
      One component of type 4, none of type 3.
    • Pond orbits.
      One component of type 3 and one of type 4. These components must be separated by a finite list of words in \(V_{n,r}\setminus X\langle A\rangle\); we think of this list as being a pond.

If that wasn’t confusing enough, we have a another way to classify those orbits which are not incomplete finite.

  1. Type A components are those with characteristic \((m, \epsilon)\), where \(\epsilon\) is the empty word. These are precisely the periodic orbits.
  2. Type B components are those with characteristic \((m, \Gamma)\), where \(\Gamma \neq \epsilon\) is nontrivial.
  3. Type C components are those which are not of type A or B—that is, they are the components which do not have a characteristic. If \(x\) belongs to a type C orbit, then \(x\phi^\ell = z\Delta\) for some \(z\) of type B. That is, type C orbits are those ‘below’ type B orbits.

Note

Type B components must be semi-infinite, but not all semi-infinite components are of type B. Complete infinite components are always of type C, but some semi-infinite components are of type C too.

class thompson.orbits.ComponentType[source]

This class is essentially a glorified enumeration: its instances store a number from 1 to 5 to represent the type of a component.

Variables:characteristic – Either the characteristic \((m, \Gamma)\) of this component, or None if this component has no characteristic. Periodic components have characteristic \((m, \varepsilon)\), where \(\varepsilon\) is the empty word.

See also

Section 4.1 of the paper.

classmethod periodic(period)[source]

Describes a complete finite (i.e. periodic, type 2) component. The argument is the period of the the component.

classmethod semi_infinite(characteristic, backward=False)[source]

Describes a semi-infinite component (types 3, 4). The first argument is the characteristic of the component; use None if this component doesn’t have a characteristic. The second argument should specify where this component is left or right semi-infinite.

classmethod complete_infinite()[source]

Describes a component which is infinite in both directions (type 1).

classmethod incomplete()[source]

Describes a component which is incomplete finite (type 5).

is_type_A()[source]

Returns true if this component belongs to an orbit of type A (periodic).

is_type_B()[source]

Returns true if this component belongs to an orbit of type B (has a characteristic)

is_type_C()[source]

Returns true if this component belongs to an orbit of type C (does not have a characteristic)

is_incomplete()[source]

Returns True if this component is incomplete, otherwise False.

is_semi_infinite()[source]

Returns True is this component is semi_infinite (with or without characteristic); otherwise returns False.

The SolutionSet structure

Solutions to the equation \(u\psi^m = v\) come in specific instances. If there are no solutions, the solution set is \(\emptyset\). Otherwise \(u\) and \(v\) share an orbit. If this orbit is periodic, then the solution set is of the form \(m + p\mathbb{Z}\), where \(p\) is the period of the orbit. Otherwise the solution set is a single integer \(m\).

Internally we represent this as a pair (base, increment) of integers. The first element base is a solution \(m\) if it exists; otherwise None. The second element increment is the increment p between solutions (which occurs for a periodic orbit only).

class thompson.orbits.SolutionSet[source]

Solution sets to the orbit sharing test \(u\phi^k = v\). These are either

  • empty (no such \(k\)) exists;
  • a singleton; or
  • a linear sequence a + b*n.

Create solution sets as follows:

>>> print(SolutionSet(5, 2))
{..., 3, 5, 7, 9, 11, 13, ...}
>>> print(SolutionSet.singleton(4))
{4}
>>> print(SolutionSet.empty_set())
{}
>>> print(SolutionSet.the_integers())
{..., -1, 0, 1, 2, 3, 4, ...}
is_sequence()[source]

Returns True if this set contains more than one distinct element; otherwise returns False.

>>> SolutionSet.empty_set().is_sequence()
False
>>> SolutionSet.singleton(2).is_sequence()
False
>>> SolutionSet(base=4, increment=3).is_sequence()
True
>>> SolutionSet.the_integers().is_sequence()
True
is_singleton()[source]

Returns True if this contains precisely one element, otherwise False.

>>> SolutionSet.empty_set().is_singleton()
False
>>> SolutionSet.singleton(2).is_singleton()
True
>>> SolutionSet(base=4, increment=3).is_singleton()
False
>>> SolutionSet.the_integers().is_singleton()
False
is_empty()[source]

Returns True if this set is empty, otherwise False.

>>> SolutionSet.empty_set().is_empty()
True
>>> SolutionSet.singleton(2).is_empty()
False
>>> SolutionSet(base=4, increment=3).is_empty()
False
>>> SolutionSet.the_integers().is_empty()
False
is_the_integers()[source]

Returns True if this set contains every integer; otherwise returns False.

>>> SolutionSet.empty_set().is_the_integers()
False
>>> SolutionSet.singleton(2).is_the_integers()
False
>>> SolutionSet(base=4, increment=3).is_the_integers()
False
>>> SolutionSet.the_integers().is_the_integers()
True
__contains__(other)[source]

Returns true if this set contains an other number.

>>> 1024 in SolutionSet.empty_set()
False
>>> 1024 in SolutionSet.singleton(128)
False
>>> 1024 in SolutionSet(0, 256)
True
>>> 1024 in SolutionSet.the_integers()
True
__and__(other)[source]

The & operator (usually used for bitwise and) stands for intersection of sets.

>>> phi = SolutionSet.empty_set()
>>> Z = SolutionSet.the_integers()
>>> singleton = SolutionSet.singleton
>>> print(phi & phi)
{}
>>> print(phi & singleton(1))
{}
>>> print(phi & SolutionSet(2, 3))
{}
>>> print(singleton(1) & singleton(1))
{1}
>>> print(singleton(1) & singleton(2))
{}
>>> print(singleton(8) & SolutionSet(4, 2))
{8}
>>> print(SolutionSet(1, 3) & SolutionSet(2, 3))
{}
>>> print(SolutionSet(1, 3) & SolutionSet(1, 2))
{..., -5, 1, 7, 13, 19, 25, ...}
>>> print(SolutionSet(1, 18) & SolutionSet(5, 24))
{}
>>> print(SolutionSet(1, 18) & SolutionSet(13, 24))
{..., -35, 37, 109, 181, 253, 325, ...}
>>> print(SolutionSet(1, 3) & Z)
{..., -2, 1, 4, 7, 10, 13, ...}
>>> print(Z & Z)
{..., -1, 0, 1, 2, 3, 4, ...}

Helper functions

thompson.orbits.print_component_types(aut, basis=None, words=None)[source]

Prints the classification of the components under aut of each word in words with respect to basis. If basis is omitted, it is taken to be the smallest possible expansion which could potentially be a semi-normal basis; see seminormal_form_start_point(). If words is omited, it is taken to be the same as basis.

>>> print_component_types(load_example('arity_three_order_inf'))
x1 a1: Left semi-infinite component with characteristic (-1, a1)
x1 a2: Bi-infinite component
x1 a3 a1: Bi-infinite component
x1 a3 a2: Bi-infinite component
x1 a3 a3: Right semi-infinite component with characteristic (1, a1)
with respect to the basis [x1 a1, x1 a2, x1 a3 a1, x1 a3 a2, x1 a3 a3]

>>> print_component_types(load_example('arity_four'))
x1 a1 a1: Periodic component of order 4
x1 a1 a2: Periodic component of order 4
x1 a1 a3: Periodic component of order 4
x1 a1 a4: Periodic component of order 4
x1 a2: Bi-infinite component
x1 a3: Right semi-infinite component with characteristic (1, a3)
x1 a4: Left semi-infinite component with characteristic (-1, a4)
with respect to the basis [x1 a1 a1, x1 a1 a2, x1 a1 a3, x1 a1 a4, x1 a2, x1 a3, x1 a4]

See also

The orbit_type() method.

class thompson.orbits.Characteristic(power, multiplier)
__getnewargs__()

Return self as a plain tuple. Used by copy and pickle.

static __new__(_cls, power, multiplier)

Create new instance of Characteristic(power, multiplier)

__repr__()

Return a nicely formatted representation string

multiplier

Alias for field number 1

power

Alias for field number 0

Next steps

With tools to describe orbits in hand, we can dive straight into the Automorphism class. In particular, we need to know how orbits work to