11
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Can you, please, clarify: are $a,b$ completely arbitrary elements of some dihedral group? In particular, you do not consider just Coxeter generators, right? $\endgroup$ Aug 14, 2017 at 3:43
  • $\begingroup$ @VictorProtsak yep, completely arbitrary $\endgroup$ Aug 14, 2017 at 3:58
  • 1
    $\begingroup$ @BjørnKjos-Hanssen I enjoyed playing with your definition. I am wondering now in which context such a definition can arise. $\endgroup$
    – Luc Guyot
    Aug 16, 2017 at 23:13

1 Answer 1

9
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Looks great. And yes there is no case (4): $a$ and $b$ are non-commuting and both of order $>2$, because the elements are of the form $r^ks$ and $r^k$ where $s^2=1$, and $(r^ks)^2=r^kr^{-k}ss=1$. $\endgroup$ Aug 17, 2017 at 2:45
  • $\begingroup$ I'm interested in when we can have $\varphi(x)^2=1$... might ask about that later $\endgroup$ Aug 18, 2017 at 1:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.