Putnam 2018, Problem A-4

Let $m$ and $n$ be positive integers with $\gcd(m,n) = 1$, and let
\[
a_k = \left\lfloor \frac{mk}{n} \right\rfloor - \left\lfloor \frac{m(k-1)}{n} \right\rfloor
\]
for $k = 1, 2, \ldots, n$. Suppose that $g$ and $h$ are elements in a group $G$ and that
\[
gh^{a_1} gh^{a_2} \cdots gh^{a_n} = e,
\]
where $e$ is the identity element. Show that $gh = hg$. (As usual, $\lfloor x \rfloor$ denotes the greatest integer less than or equal to $x$.)

Solution:
**First solution.** We prove the claim by induction on $m+n$. For the base case, suppose that $n=1$; we then have $m=1$ and the given equation becomes $gh=e$. The claim then reduces to the fact that a one-sided inverse in $G$ is also a two-sided inverse. (Because $G$ is a group, $g$ has an inverse $g^{-1}$; since $gh=e$, we have $h=g^{-1}(gh)=g^{-1}e=g^{-1}$, so $hg=e=gh$.)

Suppose now that $n>1$. In case $m>n$, set $\tilde{g}=gh$, $\tilde{h}=h$, and
$$
b_k = \left\lfloor \frac{(m-n)k}{n} \right\rfloor - \left\lfloor \frac{(m-n)(k-1)}{n} \right\rfloor \quad (k=1,\ldots,n).
$$
then
$$
\tilde{g}\tilde{h}^{b_1} \cdots \tilde{g}\tilde{h}^{b_n} = gh^{a_1} \cdots gh^{a_n} = e,
$$
so the induction hypothesis implies that $\tilde{g}$ and $\tilde{h}$ commute; this implies that $g$ and $h$ commute.

In case $m<n$, note that $a_k \in \{0,1\}$ for all $k$. Set $\tilde{g}=h^{-1}, \tilde{h}=g^{-1}$, and
$$
b_l = \left\lfloor \frac{n\ell}{m} \right\rfloor - \left\lfloor \frac{n(\ell-1)}{m} \right\rfloor \quad (\ell=1,\ldots,m);
$$
we claim that
$$
\tilde{g}\tilde{h}^{b_1} \cdots \tilde{g}\tilde{h}^{b_m} = (gh^{a_1} \cdots gh^{a_n})^{-1} = e,
$$
so the induction hypothesis implies that $\tilde{h}$ and $\tilde{g}$ commute; this implies that $g$ and $h$ commute.

**Second solution.** (by Greg Martin) Since $\gcd(m,n)=1$, there exist integers $x,y$ such that $mx+ny=1$; we may further assume that $x \in \{1,\ldots,n\}$. We first establish the identity
$$
a_{k-x} =
\begin{cases}
a_k - 1 & \text{if } k \equiv 0 \pmod{n} \\
a_k + 1 & \text{if } k \equiv 1 \pmod{n} \\
a_k & \text{otherwise}.
\end{cases}
$$
Namely, by writing $-mx=ny-1$, we see that
$$
\begin{aligned}
a_{k-x} &= \left\lfloor \frac{m(k-x)}{n} \right\rfloor - \left\lfloor \frac{m(k-x-1)}{n} \right\rfloor \\
&= \left\lfloor \frac{mk+ny-1}{n} \right\rfloor - \left\lfloor \frac{m(k-1)+ny-1}{n} \right\rfloor \\
&= \left\lfloor \frac{mk-1}{n} \right\rfloor - \left\lfloor \frac{m(k-1)-1}{n} \right\rfloor
\end{aligned}
$$
and so
$$
\begin{aligned}
a_{k-x} - a_k &= \left( \left\lfloor \frac{mk-1}{n} \right\rfloor - \left\lfloor \frac{mk}{n} \right\rfloor \right) \\
&\quad - \left( \left\lfloor \frac{m(k-1)-1}{n} \right\rfloor - \left\lfloor \frac{m(k-1)}{n} \right\rfloor \right).
\end{aligned}
$$
The first parenthesized expression equals 1 if $n$ divides $mk$, or equivalently $n$ divides $k$, and 0 otherwise. Similarly, the second parenthesized expression equals 1 if $n$ divides $k-1$ and 0 otherwise. This proves the stated identity.

We now use the given relation $gh^{a_1} \cdots gh^{a_n} = e$ to write
$$
\begin{aligned}
ghg^{-1}h^{-1} &= gh(h^{a_1}gh^{a_2} \cdots gh^{a_{n-1}}gh^{a_n})h^{-1} \\
&= gh^{a_1+1}gh^{a_2} \cdots gh^{a_{n-1}}gh^{a_n-1} \\
&= (gh^{a_{n+1-x}} \cdots gh^{a_n})(gh^{a_1} \cdots gh^{a_{n-x}}).
\end{aligned}
$$
The two parenthesized expressions multiply in the opposite order to $gh^{a_1} \cdots gh^{a_n} = e$, so they must be (two-sided) inverses of each other. We deduce that $ghg^{-1}h^{-1} = e$, meaning that $g$ and $h$ commute.

**Third solution.** (by Sucharit Sarkar) Let $T$ denote the torus $\mathbb{R}^2/\mathbb{Z}^2$. The line segments from $(0,0)$ to $(1,0)$ and from $(0,0)$ to $(0,1)$ are closed loops in $T$, and we denote them by $g$ and $h$ respectively. Now let $p$ be the (image of the) point $(\varepsilon, -\varepsilon)$ in $T$ for some $0 < \varepsilon \ll 1$. The punctured torus $T \setminus \{p\}$ deformation retracts onto the union of the loops $g$ and $h$, and so $\pi_1(T \setminus \{p\})$, the fundamental group of $T \setminus \{p\}$ based at $(0,0)$, is the free group on two generators, $\langle g,h \rangle$.

Let $\gamma$ and $\tilde{\gamma}$ denote the following loops based at $(0,0)$ in $T$: $\gamma$ is the image of the line segment from $(0,0)$ to $(n,m)$ under the projection $\mathbb{R}^2 \to T$, and $\tilde{\gamma}$ is the image of the lattice walk from $(0,0)$ to $(n,m)$, staying just below the line $y=mx/n$, that was described in the first solution. There is a straight-line homotopy with fixed endpoints between the two paths in $\mathbb{R}^2$ from $(0,0)$ to $(n,m)$, the line segment and the lattice walk, and this homotopy does not pass through any point of the form $(a+\varepsilon, b-\varepsilon)$ for $a,b \in \mathbb{Z}$ by the construction of the lattice walk. It follows that $\gamma$ and $\tilde{\gamma}$ are homotopic loops in $T \setminus \{p\}$. Since the class of $\tilde{\gamma}$ in $\pi_1(T \setminus \{p\})$ is evidently $gh^{a_1}gh^{a_2} \cdots gh^{a_n}$, it follows that the class of $\gamma$ in $\pi_1(T \setminus \{p\})$ is the same.

Now since $\gcd(m,n)=1$, there is an element $\phi \in GL_2(\mathbb{Z})$ sending $(n,m)$ to $(1,0)$, which then sends the line segment from $(0,0)$ to $(n,m)$ to the segment from $(0,0)$ to $(1,0)$. Then $\phi$ induces a homeomorphism of $T$ sending $\gamma$ to $g$, which in turn induces an isomorphism $\phi_*: \pi_1(T \setminus \{p\}) \to \pi_1(T \setminus \{\phi^{-1}(p)\})$. Both fundamental groups are equal to $\langle g,h \rangle$, and we conclude that $\phi_*$ sends $gh^{a_1}gh^{a_2} \cdots gh^{a_n}$ to $g$. It follows that $\phi_*$ induces an isomorphism
$$
\langle g,h \,|\, gh^{a_1}gh^{a_2} \cdots gh^{a_n} \rangle \to \langle g,h \,|\, g \rangle \cong \langle h \rangle \cong \mathbb{Z}.
$$
Since $\mathbb{Z}$ is abelian, $g$ and $h$ must commute in $\langle g,h \,|\, gh^{a_1}gh^{a_2} \cdots gh^{a_n} \rangle$, whence they must also commute in $G$.