Generating sets and bases

Let \(S\) be a set of words in \(V_{n,r}\). We can obtain new words by applying the operations \(\alpha_i\) and \(\lambda\) to elements of \(S\). Next, we can apply the operations to the new words we’ve received. This process continues indefinitely, producing a set of words \(T\) whose elements are sourced from the original set \(S\). We call \(T\) the subalgebra generated by \(S\) and say that \(S\) generates \(T\).

Of particular interest are bases, which we can think of as generating sets which do not contain any redundant elements. For example, it would be pointless to include each of \(x\), \(x \alpha_1\) and \(x \alpha_2\) in S, as the first can be obtained from the last two and vice versa.

The Generators class

class thompson.generators.Generators(signature, generators=None)[source]

An ordered subset of \(V_{n, r}\), together with methods which treat such sets as generating sets and bases. Internally, this is a subclass of list, so it is possible to reorder and otherwise modify collections of Generators.

Variables:signature – The Signature of the algebra this set belongs to.
__init__(signature, generators=None)[source]

When creating a generating set, you must specify the algebra \(V_{n, r}\) it is a subset of. A list of generators can optionally be provided. Each generator is passed to append().


Adds w to this generating set. If w is a string, a Word object is created and assigned the same arity and alphabet_size as the generating set.

  • TypeError – if w is neither a string nor a Word.
  • IndexError – if w has a different arity to the generating set.
  • IndexError – if w has a larger alphabet_size the generating set.
  • ValueError – if w is already contained in this generating set.
extend(iterable) → None -- extend list by appending elements from the iterable[source]

Two Generators instances are equal iff they have the same signature and the same elements in the same order.

>>> x = random_basis(signature=(3, 2))
>>> y = x.embed_in((4, 3))
>>> x == y #Different signatures, so False
>>> list.__eq__(x, y) #Even though they have the same elements

We override list.copy() so that we don’t have to recreate Generators instances by hand.

>>> olga_f = load_example('olga_f')
>>> X = olga_f.quasinormal_basis.copy()
>>> X is olga_f.quasinormal_basis
>>> type(X).__name__

Creates a copy of the current generating set whose elements x are those for which func(x) is True. The original generating set is unmodified, and the order of elements is inherited by the filtered copy.

>>> X = load_example('olga_f').quasinormal_basis
>>> print(X)
[x1 a1 a1, x1 a1 a2, x1 a2 a1, x1 a2 a2 a1, x1 a2 a2 a2]
>>> def test(x):
...     return len(x) % 2 == 0
>>> print(X.filter(test))
[x1 a2 a2 a1, x1 a2 a2 a2]

Tests to see if the current generating set \(X\) is a free generating set. To do so, the words contained in \(X\) must all be simple.

If the test fails, returns the first pair of indices \((i, j)\) found for which \(X_i\) is above \(X_j\). If the test passes, returns \((-1, -1)\).

>>> g = Generators((2, 3), ["x1 a1", "x1 a2 a1", "x1 a2 a1 a1", "x1 a2 a2"])
>>> g.test_free()
(1, 2)
>>> print(g[1], g[2], sep='\n')
x1 a2 a1
x1 a2 a1 a1
>>> g = Generators((2, 1), ['x1 a2 a2', 'x1 a2 a1 x1 a2 a2 a2 a1 L x1 a1 L'])
>>> g.test_free()
Traceback (most recent call last):
ValueError: Cannot test for freeness unless all words are simple.
Raises:ValueError – if any word in the basis is not simple.

See also

Lemma 3.16 of the paper.


Returns True if this is a free generating set; otherwise False.

>>> g = Generators((2, 3), ['x1', 'x2']);
>>> g.is_free()
>>> g.append('x3'); g.is_free()
>>> g.append('x2 a1'); g.is_free()

Yields words as if traversing the vertices of a tree in pre-order.


An iterator that yields the simple words which can be obtained by contracting this basis \(n \geq 0\) times. (So the ‘above’ condition is not strict.)

>>> g = Generators((3, 1), ["x a1 a1 a3", "x a1 a1 a1", "x a1 a2", "x a1 a1 a2", "x a1 a3"])
>>> for word in g.simple_words_above():
...     print(format(word))
x1 a1 a1 a1
x1 a1 a1 a2
x1 a1 a1 a3
x1 a1 a2
x1 a1 a3
x1 a1 a1
x1 a1

Tests to see if this set generates all of \(V_{n,r}\). The generating set is sorted, and then contracted as much as possible. Then we check to see which elements of the standard basis \(\boldsymbol{x} = \{x_1, \dotsc, x_r\}\) are not included in the contraction.

The test fails if there is at least one such element; in this case, the list of all such elements is returned. Otherwise the test passes, and an empty list is returned.

>>> #A basis for V_2,1
>>> Y = Generators((2, 1), ["x a1", "x a2 a1", "x a2 a2 a1 a1", "x a2 a2 a1 a2", "x a2 a2 a2"])
>>> Y.test_generates_algebra()
>>> #The same words do not generate V_2,3
>>> Y = Generators((2, 3), ["x a1", "x a2 a1", "x a2 a2 a1 a1", "x a2 a2 a1 a2", "x a2 a2 a2"])
>>> missing = Y.test_generates_algebra(); missing
[Word('x2', (2, 3)), Word('x3', (2, 3))]
>>> for x in missing: print(x)
Return type:a list of Words.

Returns True if this set generates all of \(V_{n,r}\). Otherwise returns False.

>>> from random import randint
>>> arity = randint(2, 5); alphabet_size = randint(2, 10)
>>> Y = Generators.standard_basis((arity, alphabet_size))
>>> Y.generates_algebra()
>>> random_basis().generates_algebra()
test_above(word, return_index=False)[source]

Searches for a pair (gen, tail) where gen belongs to the current basis and gen + tail = word. If no such pair exists, returns None.

If return_index is False, returns the pair (gen, tail). Otherwise, returns the pair (i, tail) where i is the index of gen in the current basis.

>>> basis = Generators.standard_basis((2, 1)).expand(0).expand(0).expand(0)
>>> basis
Generators((2, 1), ['x1 a1 a1 a1', 'x1 a1 a1 a2', 'x1 a1 a2', 'x1 a2'])
>>> gen, tail = basis.test_above(Word('x1 a2 a2 a1', (2, 1)))
>>> print(gen, '|', format(tail))
x1 a2 | a2 a1
>>> i, tail = basis.test_above(Word('x1 a2 a2 a1', (2, 1)), return_index=True)
>>> print(basis[i])
x1 a2
>>> basis.test_above(Word('x1', (2,1))) is None
>>> gen, tail = basis.test_above(basis[0])
>>> print(gen)
x1 a1 a1 a1
>>> gen is basis[0] and len(tail) == 0

Returns True if any generator is_above() the given word.

>>> g = Generators((2, 2), ['x1 a1', 'x1 a2', 'x2'])
>>> g.is_above(Word('x1 a1 a1 a2', (2, 2)))
>>> g.is_above(Word('x1', (2, 2)))
>>> g.is_above(Word('x2', (2, 2)))
>>> g.is_above(Word('x1 a1 x1 a2 L', (2, 2)))

Returns True if this is a free generating set which generates all of \(V_{n,r}\). Otherwise returns False.

>>> g = Generators((2, 2), ["x1 a1", "x1 a2"])
>>> g.is_free()
>>> g.generates_algebra()
>>> g.is_basis()
>>> g.append('x2')
>>> g.is_basis()
>>> random_basis().is_basis()

Suppose we have a basis floor below the current basis ceiling. There are a finite number of elements below ceiling which are not below floor. This method enumerates them. In symbols, we are enumerating the set \(X\langle A\rangle \setminus F\langle A\rangle\), where \(X\) is the current basis and \(F\) is the floor.

>>> phi = load_example('example_5_15')
>>> X = phi.quasinormal_basis
>>> Y = X.minimal_expansion_for(phi)
>>> Z = phi.image_of_set(Y)
>>> terminal = X.descendants_above(Y)
>>> initial  = X.descendants_above(Z)
>>> print(initial, terminal, sep='\n')
[x1 a1, x1 a1 a1]
[x1 a2 a2, x1 a2 a2 a1]
classmethod standard_basis(signature)[source]

Creates the standard basis \(\boldsymbol{x} = \{x_1, \dotsc, x_r\}\) for \(V_{n,r}\), where \(n\) is the arity and \(r\) is the alphabet_size of the signature.

>>> Generators.standard_basis((2, 4))
Generators((2, 4), ['x1', 'x2', 'x3', 'x4'])
classmethod from_dfs(string)[source]

Creates bases correponding to binary trees via a string of 1s and 0s correponding to branches and carets respectively. See from_dfs(). The string can also be specified as a int, in which case it is replaced by its base 10 string representation.

>>> print(Generators.from_dfs("100"))
[x1 a1, x1 a2]
>>> print(Generators.from_dfs(1100100)) #ints are fine too
[x1 a1 a1, x1 a1 a2, x1 a2 a1, x1 a2 a2]
Raises:ValueError – if the string doesn’t correctly describe a rooted binary tree.
>>> print(Generators.from_dfs(""))
Traceback (most recent call last):
ValueError: Should have one more zero than one (got 0 and 0 respectively)
>>> print(Generators.from_dfs("10"))
Traceback (most recent call last):
ValueError: Should have one more zero than one (got 1 and 1 respectively)
>>> print(Generators.from_dfs(10001))
Traceback (most recent call last):
ValueError: Error at character 3: complete description of tree with unprocessed digits remaining. String was 10001

Suppose we are given a finite sequence of automorphisms of \(V_{n,r}\) and that the current generaeting set is a basis \(X\) for \(V_{n,r}\). This methods returns an expansion \(Y\) of \(X\) such that each automorphism maps \(Y\) into \(X\langle A\rangle\).

>>> std_basis = Generators.standard_basis((2, 1))
>>> reduced_domain = Generators((2, 1), ["x a1 a1", "x a1 a2 a1", "x a1 a2 a2", "x a2 a1", "x a2 a2"])
>>> std_basis.minimal_expansion_for(load_example('cyclic_order_six')) == reduced_domain
>>> phi = load_example('example_5_3')
>>> basis = phi.quasinormal_basis
>>> print(basis.minimal_expansion_for(phi))
[x1 a1 a1 a1 a1, x1 a1 a1 a1 a2, x1 a1 a1 a2, x1 a1 a2 a1, x1 a1 a2 a2, x1 a2 a1, x1 a2 a2 a1, x1 a2 a2 a2]
  • ValueError – if no automorphisms are passed to this method.
  • ValueError – if the automorphisms or basis do not all belong to the same group \(G_{n,r}\).
  • ValueError – if the given basis does not generate \(V_{n,r}\).

See also

Lemma 4.3 of the paper proves that this expansion exists, is of minimal size, and is unique with this that property.

embed_in(signature, shift=0)[source]

Creates a copy of the current generating set in the algebra determined by signature.


if the current signature’s algebra is not a subset of the given signature’s algebra.

>>> x = Generators.standard_basis((2, 1)).expand(0); x
Generators((2, 1), ['x1 a1', 'x1 a2'])
>>> y = x.embed_in((3, 2)); y
Generators((3, 2), ['x1 a1', 'x1 a2'])
>>> z = x.embed_in((3, 2), shift=1); z
Generators((3, 2), ['x2 a1', 'x2 a2'])
>>> print(y.signature, y[0].signature)
(3, 2) (3, 2)
>>> x.is_basis()
>>> y.is_basis()

Replaces the word \(w\) at index index in the current generating set with its children, \(w\alpha1, \dotsc, w\alpha_n\), where \(n\) is the arity of the generating set. As with ordinary Python lists, negative values of index are supported.

>>> g = Generators.standard_basis((3, 1)); g
Generators((3, 1), ['x1'])
>>> g.expand(0)
Generators((3, 1), ['x1 a1', 'x1 a2', 'x1 a3'])
>>> g #has been modified
Generators((3, 1), ['x1 a1', 'x1 a2', 'x1 a3'])
>>> g.expand(-2) #expand at the second entry from the right, i.e. at 'x1 a2'
Generators((3, 1), ['x1 a1', 'x1 a2 a1', 'x1 a2 a2', 'x1 a2 a3', 'x1 a3'])
Raises:IndexError – if there is no generator at index index.
Returns:the current generating set, after modification.

Experimental method to recursively (and inefficiently) expand a generating set until every word has lambda-length 0.

>>> X = Generators((2,1), ['x1 a1 a1 a1 a2', 'x1 a2 a1 a2 x1 a2 a1 a1 a2 x1 a2 a2 a2 L x1 a2 a2 a1 L L'])
>>> X.expand_away_lambdas()
>>> print(X)
[x1 a1 a1 a1 a2, x1 a2 a1 a2, x1 a2 a1 a1 a2, x1 a2 a2 a2, x1 a2 a2 a1]
classmethod sort_mapping_pair(domain, range)[source]

Makes copies of the given lists of words domain and range. The copy of domain is sorted according to the order defined on words. The same re-ordering is applied to the range, so that the mapping from domain to range is preserved.

Return type:A pair of class:Generator instances.

Expands the current generating set until it has the given size. The expansions begin from the end of the generating set and work leftwards, wrapping around if we reach the start. (This is to try and avoid creating long words where possible.)

>>> basis = Generators.standard_basis((3, 1)); print(basis)
>>> basis.expand_to_size(11); print(basis)
[x1 a1 a1, x1 a1 a2, x1 a1 a3, x1 a2 a1, x1 a2 a2, x1 a2 a3, x1 a3 a1, x1 a3 a2, x1 a3 a3 a1, x1 a3 a3 a2, x1 a3 a3 a3]
>>> basis = Generators.standard_basis((2, 1)); print(basis)
>>> basis.expand_to_size(2); print(basis)
[x1 a1, x1 a2]
>>> basis = Generators.standard_basis((2, 3)).expand(2).expand(0); print(basis)
[x1 a1, x1 a2, x2, x3 a1, x3 a2]
>>> basis.expand_to_size(12); print(basis)
[x1 a1 a1, x1 a1 a2, x1 a2 a1, x1 a2 a2, x2 a1, x2 a2, x3 a1 a1, x3 a1 a2, x3 a2 a1 a1, x3 a2 a1 a2, x3 a2 a2 a1, x3 a2 a2 a2]

Expanding a basis to its current size does nothing.

>>> b1 = random_basis()
>>> b2 = b1.copy()
>>> b2.expand_to_size(len(b1))
>>> b1 == b2

If expansion to the target size is not possible, a ValueError is raised.

>>> basis = Generators.standard_basis((3,2))
>>> len(basis)
>>> basis.expand_to_size(3)
Traceback (most recent call last):
ValueError: Cannot expand from length 2 to length 3 in steps of size 2.
>>> basis.expand_to_size(4)
>>> len(basis)
>>> basis.expand_to_size(1)
Traceback (most recent call last):
ValueError: Cannot expand from length 4 to length 2 in steps of size 2.

Produces a copy of the current generating set, cyclicly shifted by a number of positions to the right.

>>> phi = load_example('example_5_15')
>>> print(phi.domain)
[x1 a1, x1 a2 a1, x1 a2 a2 a1 a1, x1 a2 a2 a1 a2, x1 a2 a2 a2]
>>> print(phi.domain.cycled(2))
[x1 a2 a2 a1 a1, x1 a2 a2 a1 a2, x1 a2 a2 a2, x1 a1, x1 a2 a1]
>>> X = random_basis()
>>> X == X.cycled(0) == X.cycled(len(X))
thompson.generators.rewrite_set(set, basis, new_basis)[source]

Maps set into the algebra generated by new_basis according to the bijection between basis and new_basis. See also rewrite_word().

thompson.generators.rewrite_word(word, basis, new_basis)[source]

Suppose that we have a word which is below a given basis. Suppose we have a bijection between basis and some image new_basis. Then we can rewrite word as as descendant of new_basis in a manner which is compatible with this bijection.

  • ValueError – if basis is not above word.
  • ValueError – if basis and new_basis have different sizes.

Next steps

Suppose we have a map \(f \colon V_{n,r} \to V_{n',r'}\). If this is just a set map then we would have to specify the image of every word in \(V_{n,r}\). However, if \(f\) preserves structure then it is sufficient to specify the image of a generating set—or even better, a basis—for \(V_{n,r}\). Such maps \(f\) are called homomorphisms. The next module describes homomorphisms in terms of the image of a given basis.