The “Pumping Lemma” For Finite Monoids

Question

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?

Answer 1

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