Homomorphisms

The algebra of words has its own structure, and just like groups, rings etc. there exist homomorphisms which preserve this structure. In our specific case, a homomorphism \(\phi: V_{n,r} \to V_{n,s}\) is a function satisfying

\[w \alpha_i \phi = w \phi \alpha_i \qquad \text{and} \qquad w_1 \dots w_n \lambda \phi = aw_1 \phi \dots w_n \phi \lambda.\]

In other words, a homomorphism is a function which ‘commutes’ with the algebra operations \(\alpha_i\) and \(\lambda\).

The Homomorphism Class

class thompson.homomorphism.Homomorphism(domain, range, reduce=True)

Let \(f: D \to R\) be some map embedding a basis \(D\) for \(V_{n,r}\) into another algebra \(V_{n,s}\) of the same Signature. This map uniquely extends to a homomorphism of algebras \(\psi : V_{n,r} \to V_{n,s}\).

Variables:

• domain – a basis of preimages
• range – a basis of images.

The next few attributes are used internally when constructing free factors. We need to have a way to map back to the parent automorphisms.

Variables:

• domain_relabeller – the homomorphism which maps relabelled words back into the original algebra that this automorphism came from.
• range_relabeller – the same.

__init__(domain, range, reduce=True)

Creates a homomorphism with the specified domain and range. Sanity checks are performed so that the arguments do genuinely define a basis.

By default, any redudancy in the mapping is reduced. For example, the rules x1 a1 a1 -> x1 a2 a1 and x1 a1 a2 -> x1 a2 a2 reduce to the single rule x1 a1 -> x1 a2. The reduce argument can be used to disable this. This option is intended for internal use only. [1]

Raises:

• TypeError – if the bases are of different sizes.
• TypeError – if the algebras described by domain and range have different arities.
• ValueError – if domain is not a basis.

classmethod from_file(filename)

Reads in a file specifying a homomorphism and returns the homomorphism being described. Here is an example of the format:

5
(2,1)           ->      (2,1)
x1 a1 a1 a1     ->      x1 a1 a1
x1 a1 a1 a2     ->      x1 a1 a2 a1
x1 a1 a2        ->      x1 a1 a2 a2
x1 a2 a1        ->      x1 a2 a2
x1 a2 a2        ->      x1 a2 a1
This is an example intended to illustrate the format for reading and writing automorphisms to disk.

There are three components

• number \(k\) of generators in domain and range
• signatures of domain and range
• list of \(k\) rules domain -> range

Any lines after this are ignored, and can be treated as comments. Comments are read in and added to the __doc__ attribute of the homomorphism that gets created.

Todo

Should use a different attribute (.comment?) rather than __doc__.

classmethod from_string(string)

An alternative from_file() for working with examples that you might want to copy and paste somewhere. string should be a Python string which describes an automorphism in the same format as in from_file().

static next_non_comment_line(file)

save_to_file(filename=None, comment=None)

Takes a homomorphism and saves it to the file with the given filename. The homomorphism is stored in a format which is compatible with from_file(). Optionally, a comment may be appended to the end of the homomorphism file.

>>> before = random_automorphism()
>>> before.save_to_file('test_saving_homomorphism.aut')
>>> after = Automorphism.from_file('test_saving_homomorphism.aut')
>>> before == after, before is after
(True, False)

__eq__(other)

We can test for equality of homomorphisms by using Python’s equality operator ==. The Python integer 1 can be used as a shorthand for the identity of the current homomorphism’s algebra.

>>> phi = random_automorphism()
>>> phi == phi
True
>>> phi * ~phi == 1
True
>>> 1 == Homomorphism.identity(phi.signature)
True

__mul__(other)

If the current automorphism is \(\psi\) and the other is \(\phi\), multiplication forms the composition \(\psi\phi\), which maps \(x \mapsto x\psi \mapsto (x\psi)\phi\).

Raises:TypeError – if the homomorphisms cannot be composed in the given order; i.e. if self.range.signature != other.domain.signature. Return type:an MixedAut if possible; otherwise a Homomorphism.

>>> phi = load_example('alphabet_size_two')
>>> print(phi * phi)
MixedAut: V(3, 2) -> V(3, 2) specified by 8 generators (after expansion and reduction).
x1 a1    -> x1 a1      
x1 a2    -> x1 a2 a3 a3
x1 a3 a1 -> x1 a3      
x1 a3 a2 -> x1 a2 a2   
x1 a3 a3 -> x1 a2 a1   
x2 a1    -> x2         
x2 a2    -> x1 a2 a3 a2
x2 a3    -> x1 a2 a3 a1

classmethod identity(signature)

Creates a new homo/automorphism which is the identity map on the algebra with the given signature.

>>> print(Homomorphism.identity((3, 2)))
PeriodicAut: V(3, 2) -> V(3, 2) specified by 2 generators (after expansion and reduction).
x1 -> x1
x2 -> x2
>>> sig = random_signature()
>>> Homomorphism.identity(sig) == 1
True

is_identity()

Returns True if this automorphism is the identity map on the algebra with the given signature. Otherwise returns False.

>>> aut = Homomorphism.identity(random_signature())
>>> aut.is_identity()
True
>>> load_example('example_5_15').is_identity()
False

image(key, sig_in=None, sig_out=None, cache=None)

Computes the image of a key under the given homomorphism. The result is cached for further usage later.

The key must be given as one of:

• a string to be passed to from_string();
• a sequence of integers (see the word module); or
• a Word instance.

Note

All other arguments are intended for internal use only. [2]

The input need not be in standard form. This method

1. Converts key to standard form if necessary.
2. Checks if the image of the standard form of key has been cached, and returns the image if so.
3. Computes the image of key under the homomorphism, then caches and returns the result.

>>> #An element of the domain---just a lookup
>>> phi = load_example('example_5_15')
>>> print(phi.image('x1 a1'))
x1 a1 a1 a1
>>> #A word below a the domain words
>>> print(phi.image('x1 a1 a2 a2'))
x1 a1 a1 a1 a2 a2
>>> #Above domain words---have to expand.
>>> print(phi.image('x1'))
x1 a1 a1 a1 x1 a1 a1 a2 x1 a2 a2 x1 a1 a2 L x1 a2 a1 L L L
>>> #Let's try some words not in standard form
>>> print(phi.image('x1 a1 a1 x1 a1 a2 L'))
x1 a1 a1 a1
>>> print(phi.image('x1 a1 a1 x1 a1 a2 L a2 a1'))
x1 a1 a1 a1 a2 a1
>>> print(phi.image('x1 a1 a1 x1 a2 a2 L'))
x1 a1 a1 a1 a1 x1 a2 a2 x1 a1 a2 L x1 a2 a1 L L

Return type:a Word instance (which are always in standard form).

image_of_set(set, sig_in=None, sig_out=None, cache=None)

Computes the image of a list of Generators under the current homomorphism. The order of words in the list is preserved.

Return type:another list of Generators.

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

image_of_point(x)

Interpret the current homomorphism as a piecewise linear map and evalutate the image of \(x\) under this map. Note that inverse images aren’t supported, as homomorphisms need not be invertible.

Parameters:x (Fraction) – the current point, as an int or a Fraction.

>>> from fractions import Fraction
>>> x = standard_generator(0)
>>> x.image_of_point(0)
Fraction(0, 1)
>>> x(0)    #can also just use __call__ syntax
Fraction(0, 1)
>>> x.image_of_point(Fraction(1, 3))
Fraction(1, 6)

__call__(*args, **kwargs)

Homomorphisms are callable. Treating them as a function just calls the image() method.

>>> from fractions import Fraction
>>> x0 = standard_generator()
>>> x0(Fraction(1, 2))
Fraction(1, 4)

__str__()

Printing an automorphism gives its arity, alphabet_size, and lists the images of its domain elements.

>>> print(load_example('cyclic_order_six'))
PeriodicAut: V(2, 1) -> V(2, 1) specified by 5 generators (after expansion and reduction).
x1 a1 a1    -> x1 a1 a1      
x1 a1 a2 a1 -> x1 a1 a2 a2 a2
x1 a1 a2 a2 -> x1 a2         
x1 a2 a1    -> x1 a1 a2 a2 a1
x1 a2 a2    -> x1 a1 a2 a1   

__repr__()

A tweaked version of __str__(). This produces a string representation which can be passed to from_string() to reobtain the Homomorphism we started with.

>>> f = random_automorphism()
>>> g = Automorphism.from_string( repr(f) )
>>> f == g
True

classmethod pl_segment(d1, d2, r1, r2)

pl_segments()

format_pl_segments(LaTeX=False, sfrac=False)

Returns a description of the current homomorphism as a piecewise-linear map on the interval.

>>> x = standard_generator()
>>> print(x.format_pl_segments())
0   + 1/2 (t - 0   ) from 0   to 1/2
1/4 + 1   (t - 1/2 ) from 1/2 to 3/4
1/2 + 2   (t - 3/4 ) from 3/4 to 1  

Parameters:

• LaTeX (bool) – if True, the description is formatted as a LaTeX cases environment.
• sfrac (bool) – if True, and if LaTeX is True, format fractions using xfrac’s \sfrac command.

>>> print(x.format_pl_segments(LaTeX=True))
%\usepackage{array}
\begin{equation*}
        \setlength\arraycolsep{1.3pt}
        \left\{ \begin{array}{ccrl>{\quad}c<{\quad}ccc}
                 0   &+& 1/2 &(t - 0   ) &\text{if}& 0   &\leq t < & 1/2  \\
                 1/4 &+& 1   &(t - 1/2 ) &\text{if}& 1/2 &\leq t < & 3/4  \\
                 1/2 &+& 2   &(t - 3/4 ) &\text{if}& 3/4 &\leq t < & 1    
        \end{array} \right.
\end{equation*}

classmethod format_pl_segments_directly(segments, LaTeX=False, sfrac=False)

tikz_path()

Return a string which can be passed to a \tikz\draw command to graph the current homomorphism.

add_relabellers(domain_relabeller, range_relabeller)

Raises:

• LookupError – if a relabeller is provided and the relabeller’s signature does not match that of domain or range
• TypeError – if a relabeller is provided and the relabeller’s signature does not match that of domain or range (as appropriate)

relabel()

If this automorphism was derived from a parent automorphism, this converts back to the parent algebra after doing computations in the derived algebra.

In the following example test_conjugate_to() takes a pure periodic automorphism and extracts factors. A conjugator \(\rho\) is produced by the overridden version of this method. Finally \(\rho\) is relabelled back to the parent algebra.

Raises:AttributeError – if the factor has not been assigned any relabellers.

>>> psi, phi = load_example_pair('example_5_12')
>>> rho = psi.test_conjugate_to(phi)
>>> print(rho)
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 * phi == psi * rho
True

gradients()

Interprets the current homomorphism as a piecewise linear map, and returns the list of gradients of each linear piece. The \(i\) th element of this list is the gradient of the affine map sending self.domain[i] to self.range[i].

Return type:list of Fraction s.

>>> standard_generator(0).gradients()
[Fraction(1, 2), Fraction(1, 1), Fraction(2, 1)]
>>> load_example("alphabet_size_two").gradients()
[Fraction(1, 1), Fraction(1, 3), Fraction(3, 1), Fraction(1, 1), Fraction(1, 3), Fraction(1, 3)]

gradient_at(x)

Interprets the current homomorphism as a piecewise linear map, and returns the right-derivative of the current homomorphism at \(x\).

Return type:Fraction

>>> f = standard_generator(0)
>>> f.gradient_at(0)
Fraction(1, 2)
>>> f.gradient_at(-1)
Traceback (most recent call last):
...
AssertionError
>>> f.gradient_at(2/3)
Fraction(1, 1)
>>> f.gradient_at(Word("x a2", (2, 1)))
Traceback (most recent call last):
...
ValueError: Automorphism doesn't map x1 a2 affinely
>>> f.gradient_at(Word("x a2 a2 a2 a2", (2, 1)))
Fraction(2, 1)

static gradient(domain, range)

Computes the gradient of the affine map sending the interval represented by domain to the interval represented by range.

Footnotes

[1]	Sometimes we have to expand free factors so that the orbit sizes match up.

[2]	Exposing more arguments means I can write this function in a more general manner. Doing so makes it easy to compute inverse images under an MixedAut.

Next steps

It is not possible to repeatedly apply a homomorphism \(\psi\) to a word unless \(\psi\) is actually an automorphism. The next class extends Homomorphism to represent an Automorphism.