Putnam 2016 Part 4

Random number: 20

18th January 2017

A5. 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}...g^{m_r}h^{n_r}$$ with $1 \leq r \leq |G|$ and $m_1,n_1,m_2,n_2,...,m_r,n_r \in \{-1,1\}$. (Here $|G|$ is the number of elements of $G$.)

The legend came by and blessed with his beneficience the solution became apparent. Since $|G|$ is finite, we have that $|gh|$ is finite. Call an element $gh$-colourable if it can be expressed in the form shown in the question, but not worrying about the $r \leq |G|$ restriction (but keeping the $1 \leq r$ restriction) $$ghgh...gh = e$$ $$hghgh...gh = g^{-1}$$ $$h^{-1}g^{-1}h^{-1}g^{-1}h^{-1}...g^{-1}h^{-1} = g$$ $$gh^{-1}g^{-1}h^{-1}g^{-1}h^{-1}...g^{-1}h^{-1} = g^2$$ Now because $|g|$ is odd, then for any $k$ there exists an $m$ such that $g^k = mg^2$, therefore all powers of $g$ are $gh$-colourable. Therefore we know that $g^{-1}$ is $gh$-colourable. Therefore we know that $g^{-1}gh = h$ is $gh$-colourable. We also know that since $|h|$ is finite, we have that $h^k = h^{-1}$ for some integer $k$, which implies that $h^{-1}$ is $gh$-colourable. Now we have that $g,h,g^{-1},h^{-1}$ are all $gh$-colourable. But we also know the group $G$ is generated by $g$ and $h$, therefore every element can be written as products of $g,h,g^{-1},h^{-1}$, which means that every element is $gh$-colourable.

Now to ensure that every number is colourable with $r \leq |G|$. Now denote by $A_k$ the set of all elements expressible as $g^{m_1}h^{n_1}g^{m_2}h^{n_2}...g^{m_k}h^{n_k}$, with $m_i,n_i \in \{-1,1\}$ for all $i$. Since we know that all elements are $gh$-colourable, then there must be a smallest integer $p$ such that $\cup_{q = 1}^p A_q$ contains all the elements of $G$, so we want to show that $p \leq |G|$. For some $a,b : a < b \leq p$, suppose that $A_a = A_b$. But we also know that $A_a = A_b$ implies $A_{a+1} = A_{b+1}$, and $A_{a+2} = A_{b+2}$, so that $A_{p} = A_{(p - b + a)}$. But this would imply that $\cup_{q = 1}^p A_p = \cup_{q = 1}^{p - b + a} A_q$, which suggests that there is a number $(p-b+a)$ less than $p$ that generates all the elements of the group $G$, contradicting the definition of $p$. Hence, we must have that $A_a \neq A_b$ for all satisfactory $a,b$. This implies that we can construct a sequence $\alpha_1,\alpha_2,...\alpha_p$ such that $\alpha_i \in A_i$ and all the $\alpha$ are unique. This is impossible if $p > |G|$. Hence $p \leq |G|$.