EquivalentWords 1.12

documentation notebook

Eric Rowland
https://ericrowland.github.io/packages.html

Introduction

EquivalentWords is a package for studying automorphic conjugacy in the free group (Subscript[F, 2]).
This introduction gets you started with a few features of the package; the next section provides a complete list of package symbols along with their usage messages and further examples.

To use EquivalentWords, first you will need to load the package by evaluating the following cell. (If you need help, see loading a package.)

<<EquivalentWords`

Representing words

An element of the free group (Subscript[F, 2]) on two generators is represented as a string.  The generators of (Subscript[F, 2]) are "a" and "b", and their inverses are "A" and "B".  The group operation is string concatenation.

Here are some elements of (Subscript[F, 2]):

{"aabb","abAB","aAbB"}

Each element has a canonical representation where there are no adjacent inverses.  Moreover, it is convenient to take representatives of words modulo the inner automorphism group (since eventually we are interested in representatives modulo the full automorphism group), meaning that inverses can be canceled from the beginning and end of a word.  CancelInverses finds this representative.

CancelInverses["AABaBBAabaa"]

In addition to choosing a representative with respect to inner automorphisms (cycles), it is also relatively simple to choose a representative with respect to permutations of the generators and their inverses.  CanonicalPermutation gives the word equivalent appearing first in lexicographic order among all the words obtained by permuting the generators.

CanonicalPermutation["BaB"]

RCPRepresentative ("reduced under cycled permutations" representative) gives a canonical representative with respect to both inner automorphisms and permutations of generators:

RCPRepresentative["BaB"]

Finally, we would like to take representatives with respect to word length.  A word is minimal if it is of minimum length in its equivalence class under Aut (Subscript[F, 2]).  MinimalWordQ implements a simple test for this.

MinimalWordQ["aab"]

In this package we are concerned with computing equivalence classes of (Subscript[F, 2]) under Aut (Subscript[F, 2]), and we represent an equivalence class by its list of minimal, RCP words.  EquivalenceClass computes the equivalence class of a word.

EquivalenceClass["aab"]

EquivalenceClass["AABaBBAabaa"]

Manipulating words

InverseGenerator gives the inverse of a generator.

InverseGenerator/@{"a","b","A","B"}

SyllableCount gives the number of occurrences of a subword and its inverse in a word.  For example, this counts the number of (b^(±1))'s:

SyllableCount["aaabbaBabbaB","b"]

ApplyAutomorphism applies a Whitehead type II automorphism to a word.

ApplyAutomorphism[{{"a"},"b"},"aaabbaBabbaB"]

In (Subscript[F, 2]), it suffices to consider automorphisms where the set A consists of a single generator.
$AllAutomorphisms contains eight one-letter automorphisms:

$AllAutomorphisms

Computing all equivalence classes

To compute all equivalence classes of words of length n, we start by computing a set of RCP candidate words of that length.

RCPCandidates[4]

RCPWords calls RCPCandidates and then removes the nonminimal words and equivalent duplicates in the resulting list to obtain the set of minimal RCP words of length n.

RCPWords[4]

ClassifyWords partitions this set into equivalence classes.  Thus these are the equivalence classes of length-4 words:

ClassifyWords[{"aaaa","aabb","abaB","abAB"}]

WordEquivalenceClasses does this all behind the scenes.

WordEquivalenceClasses[4]

Root words are a special class of minimal words.  There is a simple test to identify root words, implemented in RootWordQ.
If one minimal RCP word in an equivalence class is a root word, then they all are.

Map[RootWordQ,{{"aaaa"},{"abAB"},{"aabb","abaB"}},{2}]

Package symbols

AlternatingWordQ

?AlternatingWordQ

AlternatingWordQ["abAB"]

AlternatingWordQ["aabAB"]

ApplyAutomorphism

?ApplyAutomorphism

ApplyAutomorphism[#,"aabab"]&/@$Automorphisms

Note that ApplyAutomorphism cancels inverses from the front and back of a word.
Consequently, inner automorphisms always appear to act as the identity:

ApplyAutomorphism[{{"a","A"},"b"},"aabab"]

This is convenient when working modulo Inn (Subscript[F, 2]), but it must be kept in mind where working with words instead of cyclic words.

CancelInverses

?CancelInverses

CancelInverses["ABabaa"]

CancelInverses["AABabaa"]

CanonicalPermutation

?CanonicalPermutation

CanonicalPermutation["bbA"]

Children

?Children

Children["aaaab"]

Children["aaabaBAABaaaaaB"]

ClassifyWords

?ClassifyWords

ClassifyWords[RCPWords[5]]

CountAndClassifyWords

?CountAndClassifyWords

CountAndClassifyWords[5]

CountAndClassifyWords[8]

CountWords

?CountWords

CountWords[5]

EquivalenceClass

?EquivalenceClass

EquivalenceClass["aaaaab"]

EquivalenceClass["aaaabAAAAbaaaabAAAAb"]

EquivalentWords

?EquivalentWords

EquivalentWords["aaaabaaaabaaaabaaaab"]

EquivalentWords["aaaaaaab"]

EquivalentWordsQ

?EquivalentWordsQ

EquivalentWordsQ["aaaaaaaaaaaaaaab","Bbbbbbbbbbbbbbba"]

ExtendWord

?ExtendWord

ExtendWord["aabaabaB",3]

InverseGenerator

?InverseGenerator

InverseGenerator["B"]

MinimalWordQ

?MinimalWordQ

Select[RCPCandidates[5],MinimalWordQ]

OneLetterAutomorphismEquivalentWords

?OneLetterAutomorphismEquivalentWords

OneLetterAutomorphismEquivalentWords["aaaabaaaabaaaabaaaab"]

ProvablyIsolatedWordQ

?ProvablyIsolatedWordQ

Both these words are the only minimal RCP words in their equivalence classes, but only one can be established as such by ProvablyIsolatedWordQ:

ProvablyIsolatedWordQ["aaabbb"]

ProvablyIsolatedWordQ["aaabAB"]

RCPCandidates

?RCPCandidates

RCPCandidates[7]

RCPRepresentative

?RCPRepresentative

This word is not RCP, even though it appears in RCPCandidates[7]:

RCPRepresentative["aabbabb"]

This word is RCP:

RCPRepresentative["aabbaBB"]

RCPWords

?RCPWords

RCPWords[8]

RootWordClasses

?RootWordClasses

RootWordClasses[8]

RootWordQ

?RootWordQ

Select[RCPWords[8],RootWordQ]

RootWords

?RootWords

RootWords[8]

SortWords

?SortWords

RCPWords[6]

SortWords[%]

SyllableCount

?SyllableCount

SyllableCount["aabbAABB","aB"]

SyllableCount["aabbAABB","Ba"]

WordEquivalenceClasses

?WordEquivalenceClasses

WordEquivalenceClasses[8]

$AllAutomorphisms

?$AllAutomorphisms

$AllAutomorphisms

$Automorphisms

?$Automorphisms

$Automorphisms