Group action with unique word

Question

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

Answer 1

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<m$, 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.