# For synchronizing eulerian finite state machines every proper subset of states has some larger state set leads to this subset

Suppose we have a deterministic complete finite automaton which is synchronized, meaning we have a reset word, i.e. a word which resets the automaton to a definite state, regardless from which state we start. Suppose further that the underlying digraph (i.e. the graph which we get when forgetting the labels on the transitions) is Eulerian, meaning that the outdegree equals the indegree at each vertex. Then do you know any (preferable elementary) proof of the following statement:

For every proper subset of the state set of the automaton, there exists a word whose inverse image (i.e. the set of states that are mapped to the given state set under the word) is larger in cardinality as the given set.

The property that the digraph is Eulerian gives that the automaton is strongly connected, and the common value of the outdegree and the indegree equals the size of the alphabet. So, if we denote the state set by $Q$, the alphabet by $\Sigma$ and the state transition function by $\delta : Q \times \Sigma \to Q$, then as the digraph is Eulerian we have for $T \subseteq Q$ and with $\delta^{-1}(T, x) := \{ q \in Q : \delta(q, x) \in T \}$ for $x \in \Sigma$ that $$\sum_{x \in \Sigma} |\delta^{-1}(T, x)| = |\Sigma||T|.$$ because these are two ways to count the number of incoming edges. Now this gives that for every $T \subseteq Q$ we have exactly one of the two cases $$\forall x \in \Sigma : |\delta^{-1}(T, x)| = |T| \qquad \mbox{or} \qquad \exists x \in \Sigma : |\delta^{-1}(T, x)| > |T|.$$ This observation might be of help. The above statement written more formal:

For every proper subset $T \subseteq Q$, there exits a word $w \in \Sigma^{\ast}$ such that $|\delta^{-1}(T, w)| > |T|$.

• This can be found in Karl's paper. It is also in Chapter 15 of my book on representations of monoids. It is easy linear algebra using that the ask ones vector is an eigenvector for the adjancency matrix. Mar 23, 2018 at 21:39
• The proof of theorem 4 of my paper arxiv.org/pdf/0910.0410.pdf gives a more general result. Mar 23, 2018 at 21:43