ROSS Problem 3

3 (a)

Considering the letters $A,B,C$ as generating elements, the subword rule defines the relation:

• $AA\sim \epsilon$ (the empty string), i.e. $A^2=1$
• $BB\sim \epsilon$, i.e. $B^2=1$
• $CC\sim \epsilon$, i.e. $C^2=1$
• $ABAB\sim \epsilon$, i.e. $(AB{)}^2=1$
• $BCBC\sim \epsilon$, i.e. $(BC{)}^2=1$
• $CACA\sim \epsilon$, i.e. $(CA{)}^2=1$
  This defines a group that generates the elements $A,B,C$ satisfying:

$$A^2=B^2=C^2=1,(AB{)}^2=(BC{)}^2=(CA{)}^2=1$$

$(AB{)}^2=1$ implies that $AB=B{A}^{-1}=BA$ (since $A^2=1$), so $A$ and $B$ are exchangeable. Similarly, $BC=CB$ and $CA=AC$. Thus, $A,B,C$ are exchangeable, and the corresponding group is $(\mathbb{Z}/2\mathbb{Z}{)}^3$, i.e. the direct product of the three $\mathbb{Z}/2\mathbb{Z}$.
The elements of the group $(\mathbb{Z}/2\mathbb{Z}{)}^3$ can be written as $A^a{B}^b{C}^c$, where $a,b,c\in 0,1$ (since $A^2=1$, $A^1=A$, $A^2=\epsilon$, and other similar reasoning applies to $B,C$). The possible elements are $\epsilon ,A,B,C,AB,AC,BC,ABC$, totaling $2^3=8$.

$$\boxed{\text{The number of different words that can be formed is 8}}$$

3 (b)

Non-adjacent letters cannot be exchanged. For example, A and C are not “directly interchangeable”, nor are B and D. Thus four letters are only “directly interchangeable” in the sense of “directly interchangeable”.
So the four letters are only interchangeable with each other in “adjacent” rings (A↔B, B↔C, C↔D, D↔A).
Therefore, if “AC” is present, it cannot be exchanged for the string “CA”!
Consider the string: $(AC{)}^n$, i.e. $ACACACAC...$ (n for AC). When $n\ne m$, it is not possible to simplify $(AC{)}^n$ to $(AC{)}^m$ by existing rules.

$$\boxed{\text{An infinite number of words can be obtained using this type of element splicing}}$$

3 (c)

As with (b), non-adjacent letters cannot be exchanged. Consider also the string: $(AC{)}^n$, i.e. $ACACACAC...$ (n for AC). When $n\ne m$, it is not possible to simplify $(AC{)}^n$ to $(AC{)}^m$ by existing rules.

$$\boxed{\text{An infinite number of words can be obtained using this type of element splicing}}$$

Both the five-letter form and the four-letter form create an infinite number of strings that cannot be compared. However, five letters have more string arrangements than four letters for the same length. More in a sense.

3 (d)

The previous rule rule is shaped like this:

• Each letter satisfies $X^2=e$ (free to delete/add AA to indicate that the square of $X$ is equal to the identity element)
• For some pairs of letters X, Y, if deletion/addition of the substring XYXY is allowed, this corresponds to $e(XY{)}^2=e$.
  Since $X^2=Y^2=e$, $(XY{)}^2=e⟺XY=YX$, i.e. they are interchangeable with each other.
  Thus, when we add only the relations $X^2=e$ and $(XY{)}^2=e⟹X,Yexchange$, the resulting group is called the “right-corner Coxeter group”. Each letter is treated as a vertex, and an edge is connected between the two vertices if they are “exchangeable”. If the graph is clique, it means that all letters are exchangeable with each other. Thus, all generators are sequentially exchangeable, each of order 2, and the whole group is isomorphic to

$$\underset{\text{number of letters }n}{\underbrace{Z_2\times Z_2\times \cdots \times Z_2}}$$

The size of this group is $2^n$ and is a finite group.
If the graph has missing edges (indicating that a pair of letters is not exchanged), an infinite number of distinguishable elements are created, and it can generally be introduced that the group is infinite.
In (b), the fact that 4 letters form a quadrilateral (cycle) instead of being completely contiguous already leads to an infinite group; the 5 letters in (c) are also 5-cycles, and are similarly infinite.