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?

  • $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Nov 24 '17 at 19:39
  • 2
    $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – Marc Paul Nov 24 '17 at 21:24
  • $\begingroup$ I like this approach, thanks for the answer. $\endgroup$ – John P Nov 25 '17 at 7:48
  • $\begingroup$ 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\}$. $\endgroup$ – John P Nov 25 '17 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.