Putnam 2016, Problem A-5

Suppose that \( G \) is a finite group generated by the two elements \( g \) and \( h \), where the order of \( g \) is odd. Show that every element of \( G \) can be written in the form
\[
g^{m_1} h^{n_1} g^{m_2} h^{n_2} \cdots g^{m_r} h^{n_r}
\]
with \( 1 \leq r \leq |G| \) and \( m_1, n_1, m_2, n_2, \ldots, m_r, n_r \in \{-1, 1\} \). (Here \( |G| \) is the number of elements of \( G \).)

Solution:
**First solution:** For $s \in G$ and $r$ a positive integer, define a representation of $s$ of length $r$ to be a sequence of values $m_1,n_1,\ldots,m_r,n_r \in \{-1,1\}$ for which

$$s = g^{m_1}h^{n_1}\cdots g^{m_r}h^{n_r}.$$

We first check that every $s \in G$ admits at least one representation of some length; this is equivalent to saying that the set $S$ of $s \in G$ which admit representations of some length is equal to $G$ itself. Since $S$ is closed under the group operation and $G$ is finite, $S$ is also closed under formation of inverses and contains the identity element; that is, $S$ is a subgroup of $G$. In particular, $S$ contains not only $gh$ but also its inverse $h^{-1}g^{-1}$; since $S$ also contains $g^{-1}h$, we deduce that $S$ contains $g^{-2}$. Since $g$ is of odd order in $G$, $g^{-2}$ is also a generator of the cyclic subgroup containing $g$; it follows that $g \in S$ and hence $h \in S$. Since we assumed that $g,h$ generate $G$, we now conclude that $S = G$, as claimed.

To complete the proof, we must now check that for each $s \in G$, the smallest possible length of a representation of $s$ cannot exceed $|G|$. Suppose the contrary, and let

$$s = g^{m_1}h^{n_1}\cdots g^{m_r}h^{n_r}$$

be a representation of the smallest possible length. Set

$$s_i = g^{m_1}h^{n_1}\cdots g^{m_i}h^{n_i} \quad (i = 0,\ldots,r-1),$$

interpreting $s_0$ as $e$; since $r > |G|$ by hypothesis, by the pigeonhole principle there must exist indices $0 \leq i < j \leq r-1$ such that $s_i = s_j$. Then

$$s = g^{m_1}h^{n_1}\cdots g^{m_i}h^{n_i}g^{m_{i+1}}h^{n_{i+1}}\cdots g^{m_r}h^{n_r}$$

is another representation of $s$ of length strictly less than $r$, a contradiction.

**Remark:** If one considers $s_1,\ldots,s_r$ instead of $s_0,\ldots,s_{r-1}$, then the case $s = e$ must be handled separately: otherwise, one might end up with a representation of length 0 which is disallowed by the problem statement.

**Reinterpretation:** Note that the elements $gh,gh^{-1},g^{-1}h,g^{-1}h^{-1}$ generate $gh(g^{-1}h)^{-1} = g^2$ and hence all of $G$ (again using the hypothesis that $g$ has odd order, as above). Form the Cayley digraph on the set $G$, i.e., the directed graph with an edge from $s_1$ to $s_2$ whenever $s_2 = s_1 *$ for $* \in \{gh,gh^{-1},g^{-1}h,g^{-1}h^{-1}\}$. Since $G$ is finite, this digraph is strongly connected: there exists at least one path from any vertex to any other vertex (traveling all edges in the correct direction). The shortest such path cannot repeat any vertices (except the starting and ending vertices in case they coincide), and so has length at most $|G|$.

**Second solution:** For $r$ a positive integer, let $S_r$ be the set of $s \in G$ which admit a representation of length at most $r$ (terminology as in the first solution); obviously $S_r \subseteq S_{r+1}$. We will show that $S_r \neq S_{r+1}$ unless $S_r = G$; this will imply by induction on $r$ that $\#S_r \geq \min\{r,|G|\}$ and hence that $S_r = G$ for some $r \leq |G|$.

Suppose that $S_r = S_{r+1}$. Then the map $s \mapsto sgh$ defines an injective map $S_r \to S_{r+1} = S_r$, so $S_r$ is closed under right multiplication by $gh$. By the same token, $S_r$ is closed under right multiplication by each of $gh^{-1},g^{-1}h,g^{-1}h^{-1}$. Since $gh,gh^{-1},g^{-1}h,g^{-1}h^{-1}$ generate $G$ as in the first solution, it follows that $S_r = G$ as claimed.since $r+1 \leq |G|$, we are done in this case also.

**Remark:** The condition on the order of $g$ is needed to rule out the case where $G$ admits a (necessarily normal) subgroup $H$ of index 2 not containing either $g$ or $h$; in this case, all products of the indicated form belong to $H$. On the other hand, if one assumes that both $g$ and $h$ have odd order, then one can say a bit more: there exists some positive integer $r$ with $1 \leq r \leq |G|$ such that every element of $G$ has a representation of length exactly $r$. (Namely, the set of such elements for a given $r$ strictly increases in size until it is stable under right multiplication by both $gh(g^{-1}h)^{-1} = g^2$ and $gh(gh^{-1})^{-1} = gh^2g^{-1}$, but under the present hypotheses these generate $G$.)