Skip to main content
3 of 5
Added two forgotten, and obvious, admissible words in the proof of Claim 3.
Luc Guyot
  • 7.9k
  • 2
  • 30
  • 51

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$, or $01^{n - 1}$ or $10^{n - 1}$, 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).

Luc Guyot
  • 7.9k
  • 2
  • 30
  • 51