Representation of elements by words on finite groups.

Consider a finite group $G$ of order $n$, that is generated by two elements $a,b$.

I would like to find some good upper bound $m$, such that for any element $g \in G$ there is an expression of $g$ by a word of some length shorter than $m$. By word, I mean a sequence of symbols on the alphabet $\{a,b,a^{-1},b^{-1}\}$.

Clearly, this isnt true for non-finite groups - for any $j$, the free group on $\{a,b\}$ has elements that cannot expressed by a word of length less than $j$.

For commutative groups finite groups, the answer is also clear - any element can be written as $a^ib^j$, and both $i,j$ are bound by the order of $n$.

Is there some "good" bound for finite groups that are generated by two elements?

• Note that the commutative case is actually quite bad compared to the theoretical minimum; there are $4^{\ell}$ words of length $\ell$ so the easiest lower bound is that we need words of length at least $\log_4 n$, which is logarithmic in $n$, whereas in the commutative case the bound ends up being linear in $n$. Actually I think the commutative case should be the worst case but I'm not sure how to prove it. – Qiaochu Yuan Nov 24 '17 at 19:39
• At first it wasn't obvious to me that there even exists such an $m$ depending only on $n$. Of course that's obvious. In case I'm not the only one that stupid: There are only finitely many groups of order $n$. Take the maximum of the $m$ that works for each group and each pair of generators. – David C. Ullrich Nov 24 '17 at 19:45

Fix a group $G$ and two generators $a$ and $b$. For any element $g \in G$ we define its length $\mathrm{len}(g)$ to be the minimal length of a word in $a$, $b$, $a^{-1}$ and $b^{-1}$ expressing $g$. We define the length of $G$ itself to be the maximal length of its elements. Notice that these quantities do not only depend on $g$ and $G$ but also on our choice of generators.

An easy observation is that for every $k \leq \mathrm{len}(G)$ there is an element $g \in G$ with length exactly $k$. Indeed, if $h \in G$ is an element of maximal length, we can take a word expressing $h$ of length $\mathrm{len}(G)$. By minimality every subword of length $k$ of this word gives an element of length $k$.

Another easy observation is that $\mathrm{len}(g) = \mathrm{len}(g^{-1})$: from a minimal expression for $g$ we can make an expression for $g^{-1}$ by inverting the letters and switching the other, showing $\mathrm{len}(g^{-1}) \leq \mathrm{len}(g)$, and equality follows from symmetry.

Putting these together and using that $g \neq g^{-1}$ if and only if $g$ has order at least 3 and that the identity of $G$ has length $0$, we get the upper bound \begin{align*} \mathrm{len}(G) &\leq \#\{g \in G \textrm{ of order } 2\} + \frac{1}{2}\#\{g \in G \textrm{ of order }\geq 3\} \\ & = \frac{1}{2}(\#G -1) + \frac{1}{2}\#\{g \in G \textrm{ of order }2\} \end{align*} In terms of $m$ and $n$ in your question, this gives $m \leq n-1$. If $n$ is odd we can do even better, because then the second term above vanishes and we obtain $m \leq (n-1)/2$ for $n$ odd.

To show that these upper bounds are quite reasonable, consider the cyclic group $C_n$ of order $n$, and let $a$ be a generator of this group and $b$ the identity. Then one easily shows that $\mathrm{len}(C_n) = n/2$ for $n$ even and $\mathrm{len}(C_n) = (n-1)/2$ for $n$ odd (for this choice of generators). So for $n$ odd, this already proves that $m = (n-1)/2$ exactly, while for $n$ even we have $n/2 \leq m \leq n-1$.

• By the way, I don't know if what I call 'length' above is usually called that way. If somebody happens to know a more standard terminology I'd be happy to edit. – Marc Paul Nov 24 '17 at 21:24
• I like this approach, thanks for the answer. – John P Nov 25 '17 at 7:48
• Also, I think in the last inequality, it could be $n/2 = m$ instead. Lastly, I'm not sure about the equality (which I think should be an inequality) - $= \frac{1}{2}(\#G -1) + \frac{1}{2}\#\{g \in G \textrm{ of order }2\}$. – John P Nov 25 '17 at 7:53