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?




---


**Edit**: to answer @LucGuyot's question below: this definition arises in my model of **quantum security** from a recent [UCNC'17 paper](https://link.springer.com/chapter/10.1007/978-3-319-58187-3_12) (see also [arXiv version](https://arxiv.org/abs/1703.04878)) except that there is an additional constraint there, that we map the locked state $|0\rangle$ to the unlocked state $|1\rangle$.


The relevance of dihedral groups is that Dih$\_k$ is representable as a subgroup of the projective unitary group $\mathrm{PU}(2, \mathbb C)$. The interpretation then is that $x$ is a secret code which should be punched into a quantum device with buttons labeled 0 and 1 and which trigger unitary operations $U\_A$, $U\_B$. Any code of the same length as $x$ but different from $x$ will not have the same effect (say, unlocking the device). Any attempt to inspect the state of the device during entering of the code, as one might do with a simple padlock, will constitute a measurement of the device and therefore reset the quantum superposition.



Unique words in dihedral groups
The conjecture holds **true** and I don't know of anything similar.


Given a word $w$ over $\{0, 1\}$, we denote by $\overline{w}$ the word obtained from $w$ by interchanging $0$ and $1$.
Let us show first that the elements of $S \cup T$, where $T = \overline{S}$, are dihedrally simple.



> 
> 
> > 
> > **Claim 1.** A word $w$ over $\{0, 1\}$ is dihedrally simple if and only if $\overline{w}$ is.
> > 
> > 
> > **Proof.** Consider $\overline{\varphi}\_{a,b,k} \Doteq \varphi\_{b, a, k}$. 
> > 
> > 
> > 
> 
> 
> 


Because of Claim 1, it suffices to show



> 
> 
> > 
> > **Claim 2.** The elements of $S$ are dihedrally simple.
> > 
> > 
> > 
> 
> 
> 


The following will come soon in handy.



> 
> 
> > 
> > **Lemma 1.** Let $a \in \text{Dih}\_k$ be either central or of order $k > 2$ and let $b \in \text{Dih}\_k$ be a non-central element of order $2$. Let $w$ be a word over $\{0, 1\}$ of length $n$. 
> >  If $w$ contains at least two $1$'s (resp. more than two $1$'s), then $\varphi\_{a, b, k}(w)$ is either of the form $a^i$ or $a^ib$ with $\vert i \vert \le n - 2$ (resp. $\vert i \vert < n - 2$). If $w$ is of the form $0^i 1 0^j$, then $\varphi\_{a, b, k}(w) = a^{i - j}b$.
> > 
> > 
> > **Proof.** Write $w = 0^{i\_1}1^{j\_1} \cdots 0^{i\_s}1^{j\_s}$ with $i\_t, j\_t \ge 0$. 
> >  It follows from the identities $b^2 = 1$ and $bab = a^{-1}$ that $\varphi\_{a, b, k}(w) = a^{\sum\_{t = 1}^s \pm i\_t}b^{\varepsilon}$ with $\varepsilon \in \{0, 1\}$ and $\varepsilon \equiv \sum\_{t = 1}^s j\_t\mod 2$. If $w$ contains at least two $1$'s (resp. more than two $1$'s), then $\sum\_{t = 1}^s i\_t \le n - 2$ (resp. $\sum\_{t = 1}^s i\_t < n - 2$), which implies the first statement.
> >  Consider now the second statement with $w = 0^i 1 0^j$. Then $\varphi\_{a, b, k}(w) = a^iba^j = a^{i - j}b$.
> > 
> > 
> > 
> 
> 
> 


We are now in position to prove Claim 2.



> 
> 
> > 
> > **Proof of Claim 2.** If $w \in S$ is of length $n = 0$, then $w$ is certainly dihedrally simple. Let us assume that $n > 0$ and let $k > 4n$. Let $a \in \text{Dih}\_k$ be an element of order $k$ and let $b \in \text{Dih}\_k$ be a non-central element of order $2$. Then $\varphi\_{a,b,k}(0^n) = a^n$. Since $\text{Dih}\_k = \langle a \rangle \rtimes \langle b \rangle$, it follows from Lemma 1 that the image by $\varphi\_{a,b,k}$ of any other word of length $n$ is distinct from $a^n$. Thus $0^n$ is dihedrally simple. Since $\varphi\_{a,b,k}(0^{n - 1}1) = a^{n - 1}b$, it also follows from Lemma 1 that $0^{n - 1}1$ dihedrally simple. The case of $01^{n - 1}$ is very similar but relies on $\overline{\varphi}\_{a,b,k}$ instead; we will omit it. 
> >  Let us now consider $\varphi\_{a,b,k}(10^{n -2}1) = a^{-(n - 2)}$. We infer from Lemma 1 that $10^{n -2}1$, and hence $01^{n -2}0$, is dihedrally simple.
> >  Eventually, let us consider $\varphi\_{b, ba, k}((01)^{n/2})$. This is $a^{n/2}$ if $n$ is even and $a^{(n - 1)/2}b$ if $n$ is odd. 
> >  Since $b^2 = (ba)^2 = 1$, we have $\varphi\_{b, ba, k}(00) = \varphi\_{b, ba, k}(11) = 1$. Therefore the image of any word of length $n$ by $\varphi\_{b, ba, k}$ is the image of a word of the form $(01)^{i/2}$ or $(10)^{i/2}$ with $0 \le i \le n$, that is, a group element $g$ of the form $a^{\lfloor i/2 \rfloor}b^{\varepsilon}$ or respectively $a^{-\lfloor i/2 \rfloor}(ba)^{\varepsilon}$ with $\varepsilon \in \{0, 1\}$. It is easily checked that such an element $g$ coincides with $\varphi\_{b, ba, k}((01)^{n/2})$ if and only if $i = n$, which shows that $(01)^{n/2}$ is dihedrally simple.
> > 
> > 
> > 
> 
> 
> 


The following claim will settle the conjecture.



> 
> 
> > 
> > **Claim 3.** Let $w$ be a dihedrally simple word. Then $w \in S \cup T$.
> > 
> > 
> > **Proof.** Let $w$ be dihedrally simple word of length $n$.
> >  Since $S \cup T$ contains all words of length at most three, we can assume that $n \ge 4$. By definition, we can find $k \ge 2$, $a,b \in \text{Dih}\_k$ such that $\varphi\_{a, b, k}(w) \neq \varphi\_{a, b, k}(v)$ for every word $v \neq w$ of length $n$. We can split our reasoning into three cases. 
> > 
> > 
> > 
> 
> 
> 1. The group elements $a$ and $b$ commute. If $w$ contains a subword of the form $01$ or $10$, then we can interchange these two subwords, producing a word $v \neq w$ such that $\varphi\_{a, b, k}(v) = \varphi\_{a, b, k}(w)$, a contradiction. Therefore $w$ is of the form $0^n$ or $1^n$, and hence lies in $S \cup T$.
> 2. The group elements $a$ and $b$ are non-commuting elements of order $2$. We have then $\varphi\_{a, b, k}(00) = \varphi\_{a, b, k}(11) = 1$. Thus $w$ cannot contain any of the subword $00$ or $11$, since interchanging them would yield a contradiction. Therefore $w$ is of the form $(01)^{n/2}$ or $(10)^{n/2}.$ Thus $w$ lies in $S \cup T$.
> 3. The group elements $a$ and $b$ are non-commuting elements of order $2$ and $k > 2$ respectively. We have then $\varphi\_{a, b, k}(00) = 1$. If $w$ contains at least one $1$, i.e., $w = w'1w''$, then it cannot contain a subword of the form $00$, since otherwise moving this subword from $w'$ to $w''$, or vice versa, would yield a word $v \neq w$ with the same image. As we also have $\varphi\_{a, b, k}(101) = \varphi\_{a, b, k}(000)$, the word $w$ cannot contain a subword of the form $101$. As a result, $w$ is of the form $0^n$, or $1^{n - 1}0$, or $01^{n - 2}0$. Therefore $w$ lies in $S \cup T$.
> 
> 
> The very last case consists in interchanging the orders of $a$ and $b$, but this is too similar to case (3).
> 
> 
> 


