# The “Pumping Lemma” For Finite Monoids

Let $$M$$ be a finite monoid. I’m trying to prove the following: there is a constant $$N$$ such that if $$n \geq N$$ and $$m_1, \ldots, m_n \in M$$, then some subword of $$m_1 \cdots m_n$$ is an idempotent. (This is analogous to the classic pumping lemma for finite automata.)

The closest I’ve gotten is to prove an analogue of the theorem for groups: if $$G$$ is a finite group, $$n \geq |G|$$, and $$g_1\ldots g_n \in G$$, then some subword of $$g_1 \cdots g_n$$ equals the group identity $$e$$. The proof here is pretty simple: consider the prefixes $$g_1, g_1g_2, g_1g_2g_3, \ldots, g_1g_2g_3\cdots g_n.$$ If these prefixes are pairwise distinct, then (since there are at least $$|G|$$ of them) one must equal $$e$$. If they’re not pairwise distinct, then for some $$m$$ and $$k$$ $$g_1 \dots g_m = g_1 \cdots g_{m + k} \implies e = g_{m + 1} \cdots g_{m + k}.$$ In either case, some subword is the identity.

I haven’t been able to extend this idea to the monoid case. Could somebody help me out?

• Must a subword consist of consecutive indices (e.g., is $m_1m_3$ an acceptable subword of $m_1m_2m_3$)? Commented Jun 12 at 18:22
• Yeah, the indices have to be consecutive. Commented Jun 12 at 18:23

Here is a proof slightly adapted from [1, p. 37].

Let $$M$$ be a finite monoid and let $$n = |M|$$. Then there is an integer $$K$$ such that $$s^K$$ is idempotent for each $$s \in M$$ (see here for a proof). Let $$M^*$$ be the free monoid over $$M$$ (considered as an alphabet). The identity on $$M$$ extends uniquely to a monoid morphism $$f: M^* \to M$$. For each $$s \in M$$, let $$T_s = f^{-1}(s)$$. Now define a map $$t: M^* \to \Bbb{N}^M$$ by setting $$t(u) = \bigl(n_s(u)\bigr)_{s \in M} \quad\text{where } n_s(u) = \max\{r \mid u \in M^*T_s^r\}$$ Observe that if $$u$$ is a word, $$v$$ a nonempty word and $$s = f(v)$$, then by definition $$u \in M^*T_s^{n_s(u)}$$ but $$uv \in M^*T_s^{n_s(u) + 1}$$. Consequently, $$t(u) \not= t(uv)$$.

Let now $$w$$ be a word of $$M^*$$ of length $$K^n$$ and let $$P$$ be the set of prefixes of $$w$$. By the previous remark, the restriction of $$t$$ to $$P$$ is injective. Since $$|P| = 1 + K^n$$, the set $$t(P)$$ cannot be included in the set $$\{0, 1, \ldots, K-1\}^n$$. It follows that there exists a word $$p \in P$$ and an element $$s \in M$$ such that $$n_s(p) \geqslant K$$. Coming back to the definition of $$n_s$$, this means that $$p \in M^*T_s^KM^*$$ and hence $$p$$ admits a factorisation $$p = p_0p_1p_2 \dotsm p_Kp_{K+1}$$ such that $$f(p_1) = f(p_2) = \dotsm = f(p_K)$$. By the definition of $$K$$, it follows that $$f(p_1p_2 \dotsm p_K)$$ is idempotent.

Remarks (1) A similar proof shows that, for every $$r$$, every sufficiently long word $$w \in M^*$$ admits a factorization $$w = w_0w_1 \ldots w_rw_{r+1}$$ where $$f(w_1) = f(w_2)= \ldots = f(w_r) = e$$ is idempotent.

(2) A simple proof can be obtained via Ramsey's theorem. Let me know if you want me to include it in this answer.

(3) One can also require in (1) that $$|w_1| = |w_2| = \ldots = |w_r|$$, but the proof is more difficult and relies on Van der Waerden's theorem.

[1] M. Lothaire, Combinatorics on words. Corrected reprint of the 1983 original, Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997. xviii+238 pp. ISBN: 0-521-59924-5

• Brilliant, thanks! Commented Jun 16 at 8:56
• You're welcome. Commented Jun 16 at 10:14