# Group action with unique word

This must be known or easy for some of you, but here goes:

Suppose $$f_0,f_1:[n]\to [n]$$ are invertible functions, where $$[n]=\{0,\dots,n-1\}$$ is a set of $$n$$ elements. For a word $$w=w_1\dots w_m\in\{0,1\}^m$$ we define $$f_w=f_{w_m}\circ f_{w_{m-1}}\circ\dots\circ f_{w_1}$$ (or make it the opposite order, if you prefer). Suppose $$c, d$$ and $$m$$ are such that there is exactly one word $$w\in\{0,1\}^m$$ with $$f_w(c)=d$$. Does it follow that $$n\ge m+1$$?

I've checked that it does follow for all $$m\le 11$$ (eleven).

## 1 Answer

Fix $$c\in [n]$$. Let $$\mathcal R_m(c)$$ be $$\{f_w(c)\colon |w|=m\}$$ and $$r_m(c)=|\mathcal R_m(c)|$$. We define $$\mathcal R_0(c)$$ to be $$\{c\}$$.

Claim: Let $$m\ge 0$$. If $$r_m(c)=r_{m+1}(c)$$, then for all $$M>m$$ and for all $$d\in\mathcal R_M(c)$$, there are two $$w$$'s in $$\{0,1\}^M$$ with $$f_w(c)=d$$.

Proof: Let $$S=\mathcal R_m(c)$$. Then $$\mathcal R_{m+1}(c)=f_0(S)\cup f_1(S)$$. By invertibility if the $$f_i$$, $$f_0(S)$$ and $$f_1(S)$$ each have cardinality $$r_m(c)=r_{m+1}(c)$$, and their union also has cardinality $$r_{m+1}(c)$$. It follows that $$f_0(S)=f_1(S)$$. Now let $$w\in \{0,1\}^M$$ and let $$f_w(c)=d$$. Let $$w$$ be the concatenation of $$u$$ (of length $$m+1$$) and $$v$$ of length $$M-(m+1)\ge 0$$. By the above, there exists a $$u'$$ also of length $$m+1$$ with the opposite $$(m+1)$$st symbol such that $$f_{u'}(c)=f_{u}(c)$$. Now $$f_v\circ f_{u'}(c)=f_v\circ f_u(c)$$. $$\square$$

It follows that if $$c$$ and $$d$$ are such that there is a unique $$w$$ of length $$m$$ with $$f_w(c)=d$$, then $$r_{j+1}(c)>r_j(c)$$ for each $$j, so that $$n\ge r_m(c)\ge m+r_0(c)=m+1$$.

I should comment that this proof somewhat resembles that of the Morse-Hedlund theorem in symbolic dynamics.

• Yes: I used $|f_i(S)|=|S|$. Also there are easy counter-examples if you don’t have invertibility. – Anthony Quas Sep 27 at 15:10
• I edited the answer to make the role of invertibility explicit. – Anthony Quas Sep 27 at 15:17
• Hey Bjørn, it would feed my ego to be a co-author on a logic paper, but I don’t think this is much of a contribution. – Anthony Quas Sep 27 at 15:54
• The standard practice in this situation would be to acknowledge Anthony Quas's help in your paper, and possibly cite this question using a weblink. – Derek Holt Sep 27 at 16:18
• I agree with @DerekHolt. That would be just fine. – Anthony Quas Sep 27 at 16:26