<p>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$.</p>

<p>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 &lt; j$ then $f_{w_{\leq i} w_{&gt;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$.</p>

<p>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!$.</p>

<p>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$.</p>

<hr>

<p>The following construction shows that $n!-1$ cannot be replaced by anything smaller than roughly $e^{\sqrt{n\log n}}$. <a href="http://en.wikipedia.org/wiki/Landau%27s_function" rel="nofollow">Landau's function</a> $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.</p>

<hr>

<p>Consider again the case of injective $f_w$. We can think of the letters of $w$ as generating a subgroup of $S_n$. <a href="http://ac.els-cdn.com/S0195669805800290/1-s2.0-S0195669805800290-main.pdf?_tid=4a0d8894-54a6-11e4-a977-00000aab0f02&amp;acdnat=1413403571_7d77b5f795f4d04cd096a0fd3b76acaa" rel="nofollow">Babai and Seress</a> 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.</p>

<p>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}}$.</p>

<hr>

<p>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.</p>

CC BY-SA 3.0
2014-10-16T00:17:53.433Z
Thank you for the wonderful argument... am I right in saying that the bound established is then (3/2)n! ?
zrini
CC BY-SA 3.0
2014-10-16T01:58:06.577Z
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})}$.
Yuval Filmus
CC BY-SA 3.0
2014-11-30T00:11:02.450Z
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'$.
Pavel Panteleev
CC BY-SA 3.0
2014-11-30T00:12:58.033Z
@Pavel Thanks, that always happens when details aren't written down in full...
Yuval Filmus
CC BY-SA 3.0
2014-10-15T18:04:56.930Z
2014-10-15T20:15:51.140Z
2014-10-15T20:15:51.140Z
Yuval Filmus
<p>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})$.</p>

<p>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.</p>

<p>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] <a href="http://grammars.grlmc.com/lata2015/AcceptedPapers.php" rel="noreferrer">accepted</a> for publication in the forthcoming LATA 2015 proceedings.</p>

<p>[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)</p>

<p>[2] Salomaa, A.: Composition sequences for functions over a finite domain. Theoret.
Comput. Sci. 292, 263-281 (2003)</p>

<p>[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)</p>

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

CC BY-SA 3.0
2014-11-29T23:34:30.280Z
2014-11-29T23:34:30.280Z
Pavel Panteleev
<p>We encountered this question as an exercise in a B&uuml;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:</p>

<p>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$.</p>

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

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

CC BY-SA 3.0
2014-10-15T17:07:28.917Z
The $n^n$ version is easy to get by repeatedly using the pigeonhole principle on the prefixes of $w$.
Klaus Draeger
<automata-theory><omega-language>
Automata and a kind of pumping lemma on state transition function
zrini
# Automata and a kind of pumping lemma on state transition function

(Asked by: username_0 on 2014-10-15)

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

**Tags:** automata-theory, omega-language
> **Comments:**
> **username_1**: The $n^n$ version is easy to get by repeatedly using the pigeonhole principle on the prefixes of $w$.  

---

## 2 answers

### Answer by username_2 on 2014-10-15. Score: 4 | Accepted answer

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](http://en.wikipedia.org/wiki/Landau%27s_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](http://ac.els-cdn.com/S0195669805800290/1-s2.0-S0195669805800290-main.pdf?_tid=4a0d8894-54a6-11e4-a977-00000aab0f02&acdnat=1413403571_7d77b5f795f4d04cd096a0fd3b76acaa) 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.

> **Comments:**
> **username_0**: Thank you for the wonderful argument... am I right in saying that the bound established is then (3/2)n! ?  
> **username_2**: 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})}$.  
> **username_3**: 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'$.  
> **username_2**: @Pavel Thanks, that always happens when details aren't written down in full...  

---

### Answer by username_3 on 2014-11-29. Score: 5

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](http://grammars.grlmc.com/lata2015/AcceptedPapers.php) 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 finite 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)


---

