Skip to main content
1 of 2
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

Unique words in dihedral groups

Suppose $x$ is a word over the alphabet $\{0,1\}$. Let $a$, $b$ be elements of the group Dih$_k$ for some $k$.

Let $\varphi=\varphi_{a,b,k}$ be the map from words over $\{0,1\}$ to elements of the dihedral group Dih$_k$ (having $2k$ elements) such that $\varphi(0)=a$, $\varphi(1)=b$, and $\varphi$ takes concatenation to multiplication: $\varphi(xy)=\varphi(x)\varphi(y)$.

Let's say that $x$ is dihedrally simple if there is some $\varphi_{a,b,k}$ such that $\varphi(x)\ne\varphi(y)$ for all $y\ne x$ of the same length as $x$.

Computer experimentation suggests the

Conjecture: The dihedrally simple words form a regular language, namely $S\cup T$ where $$ S=\bigcup_{n=0}^\infty \{0^n,\quad 0^{n-1}1,\quad (01)^{n/2},\quad 01^{n-1},\quad 01^{n-2}0\} $$ where $(01)^{t+\frac12}=(01)^t0$, and $T$ is obtained from $S$ by interchanging 0 and 1.

My question is: Is the Conjecture similar to anything in the literature? Or do you see how to prove it?

Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114