Unique words in dihedral groups

Question

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 (see also arXiv version) 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.

Answer 1

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).