Bound on minimal word length by generators of monoid

Question

Say I have a monoid of size $n$ (a group except there aren't always inverse elements), I have some subset and I'm looking at the submonoid (is that a word?) formed by the subset, is there a bound on the minimal length of things in the submonoid? What I mean is say my subset is $\{x,y\}$, then my submonoid will contain all elements of the form multiplications of $x,y$. For example $xy,xxy,yyyy$ will all be there, now for any element, I can take the representation with the minimal length (number of letters). I'm looking for a bound.

Answer 1

There is an upper bound of $n-1$. If not, then a minimal length word representing some element is $a_1a_2 \cdots a_m$ with $m \ge n$. But this word has $m+1$ prefixes, so two of them must represent the same monoid element. Then, if say $a_1 \cdots a_i = a_1 \cdots a_j$ with $i < j$, you can omit the subword $a_{i+1}\cdots a_j$ and thereby shorten the word.

From the cyclic group of order $n$, we see that we cannot do better than $n-1$ as an upper bound.