# Automata and a kind of pumping lemma on state transition function

We encountered this question as an exercise in a Büchi automata book a couple of decades ago, and back then gave a few tries thinking that it should be easy. But haven't seen a solution. My friend Deepak helped me with the problem statement, here it is:

Given a DFA $A = (Q,Letters,\delta,Final)$ with $n$ states, each letter $a$ induces a function $f_a: Q \to Q$, given by $f_a(q) = \delta(q,a)$. A word $w$, by extension, also induces a function $f_w : Q \to Q$.

The problem was to show that for any $w$, we can find a $w'$ of length $\leq n!$, such that $f_{w'} = f_w$.

Wondering if there is any bound on the word length, even if not a $n!$ (like $n^n$).

• The $n^n$ version is easy to get by repeatedly using the pigeonhole principle on the prefixes of $w$. Oct 15 '14 at 17:07

The following argument works as long as $f_w$ is injective. The same ideas should also work for general $f_w$. Indeed, below I show how they give a bound $|w| \leq O(n!)$. However, even further down I show a much better bound, $|w| \leq e^{2(1+o(1))\sqrt{n\log n}}$, which is tight up to the constant $2$.

Consider some word $w$ which is the minimal length word resulting in $f_w$, and suppose that the range of $f_w$ is $Q$. We want to show that $|w| \leq n!$. Let $w_{\leq i}$ denote the prefix of $w$ of length $i$. If $f_{w_{\leq i}} = f_{w_{\leq j}}$ for some $i < j$ then $f_{w_{\leq i} w_{>j}} = f_w$, contradicting the assumption that $w$ has minimal length. We conclude that $f_{w_{\leq i}}$ is different for all $i$. Since the range of $f_w$ is full, all $f_{w_{\leq i}}$ must be permutations of $Q$. Since there are $n!$ permutations of $Q$, we conclude that $|w| \leq n!-1$.

Suppose now that $f_w$ is not injective, and write $w = x_1\ldots x_k$, where each step passing from $x_i$ to $x_{i+1}$ decreases the image. The same argument as before shows that $|x_1| \leq n!$, $|x_2| \leq n!/1!$, $|x_3| \leq n!/2!$, and so on. In total, we get that $|w| \leq n!(1+1+1/2+1/6+\cdots) \leq e n!$.

We can do slightly better. For example, if $f_{x_1}(q_1) = f_{x_2}(q_2)$ then when bounding $x_1$, it is enough to consider permutations up to a permutation of the images of $q_1$ and $q_2$, and so when $k \geq 2$ we can conclude that $|x_1| \leq n!/2$. This argument probably gives $|w| \leq (3/2)n!$. One can probably push the argument further, but that would require looking across the boundaries of the segmentation $w=x_1\ldots x_k$.

The following construction shows that $n!-1$ cannot be replaced by anything smaller than roughly $e^{\sqrt{n\log n}}$. Landau's function $g(n)$ is the maximal order of an element in $S_n$. It is known that $g(n) = e^{(1\pm o(1))\sqrt{n\log n}}$. Given an element $\pi \in S_n$ of maximal order, we can construct an automaton over the one language alphabet $\{a\}$ in which $Q = \{1,\ldots,n\}$ and $f_a = \pi$. The word $a^{g(n)-1}$, which generates the permutation $\pi^{-1}$, cannot be shortened.

Consider again the case of injective $f_w$. We can think of the letters of $w$ as generating a subgroup of $S_n$. Babai and Seress show that the diameter of the corresponding Cayley graph is at most $e^{(1+o(1)) \sqrt{n\log n}}$. This means that every permutation in the subgroup, including $f_w$, can be written as a word over the letters of $w$ and their inverses of length at most $e^{(1+o(1)) \sqrt{n\log n}}$. Since the order of each permutation is at most $e^{(1+o(1))\sqrt{n\log n}}$, we can replace the inverse of each letter by at most $e^{(1+o(1))\sqrt{n\log n}}$ copies of itself, obtaining a word of length $e^{2(1+o(1))\sqrt{n\log n}}$. This bound can perhaps be improved by looking at the construction of Babai and Seress.

In the general case, segment $w=x_1\ldots x_k$ as before, where $k \leq n$. A similar argument shows that $|x_i| \leq e^{2(1+o(1))\sqrt{n\log n}}$, and so $|w| \leq e^{2(1+o(1))\sqrt{n\log n}}$.

This still leaves open the value of the smallest $\ell(n)$ such that the minimal word $w$ with given $f_w$ has length at most $\ell(n)$. Our arguments show that $e^{(1+o(1))\sqrt{n\log n}} \leq \ell(n) \leq e^{2(1+o(1))\sqrt{n\log n}}$, leaving a small gap.

• Thank you for the wonderful argument... am I right in saying that the bound established is then (3/2)n! ? Oct 16 '14 at 0:17
• Yes, though the methods can probably be pushed further. There's also an asymptotically much better bound of $e^{2(1+o(1))\sqrt{n\log n}}$ which I also prove. This bound is almost optimal, since there is a lower bound of $e^{(1+o(1))(\sqrt{n\log n})}$. Oct 16 '14 at 1:58
• While I completely agree with your derivation of the upper bound for $\ell(n)$ in the group case, I can't agree that the similar arguments also work for the general case. Consider, for example, a DFA that has the states $Q=\{0, 1,\ldots, n\}$ and the input alphabet $A=\{a_1,\ldots,a_m\}$, where $m=\binom{n}{k}-1$. Suppose that all the $k$-subsets $Q_1,\ldots,Q_k$ of $\{1,\ldots, n\}$ are lexicographically ordered and $a_i$ sends $Q_i$ to $Q_{i+1}$ while sending all other states to $0$. In this case the function $f_w$, $w=a_1\ldots a_m$, can not be obtained by a shorter word $w'$. Nov 30 '14 at 0:11
• @Pavel Thanks, that always happens when details aren't written down in full... Nov 30 '14 at 0:12

The question is quite old. To the best of my knowledge this problem was first considered in 1976 by Sokolovskii [1], where it was proved that: for the group case ($f_w$ is a permutation) the upper bound is $n!^{\frac12(1+o(1))}$ and the lower bound is $\mathrm{e}^{\sqrt{n\ln n}(1+o(1))}$; for the general case the upper bound is $n^{\frac{n}{2}(1+o(1)))}$ and the lower bound is $\Omega(2^n/\sqrt{n})$.

Much later in 2003 this problem was also independently of Sokolovskii considered among many other problems in [2] by Salomaa but the results were weaker then in the Sokolovskii's paper. In 2006 Babai [3] obtained an optimal upper bound $\mathrm{e}^{\sqrt{n\ln n}(1+o(1))}$ for the group case.

For the general case an optimal estimate $2^n\mathrm{e}^{\sqrt{\frac{n}{2}\ln n}(1+o(1))}$ was obtained in my resent paper [4] accepted for publication in the forthcoming LATA 2015 proceedings.

[1] Sokolovskii, M.N.: The complexity of the generation of transformations, and experiments with automata. In: Discrete analysis methods in the theory of codes and schemes, vol. 29, pp. 68-86. Institute of Mathematics, Siberian. Branch USSR Acad. Sci. (1976), (in Russian)

[2] Salomaa, A.: Composition sequences for functions over a fi nite domain. Theoret. Comput. Sci. 292, 263-281 (2003)

[3] Babai, L.: On the diameter of eulerian orientations of graphs. In: SODA06: proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithms. pp. 822-831. ACM, New York, NY, USA (2006)

[4] Panteleev, P.: Preset Distinguishing Sequences and Diameter of Transformation Semigroups, (accepted for publication in LATA 2015)