International Mathematics Competition
for University Students
2024

IMC2024: Day 1, Problem 4

Problem 4. Let \(\displaystyle g\) and \(\displaystyle h\) be two distinct elements of a group \(\displaystyle G\), and let \(\displaystyle n\) be a positive integer. Consider a sequence \(\displaystyle w=(w_1,w_2,\ldots)\) which is not eventually periodic and where each \(\displaystyle w_i\) is either \(\displaystyle g\) or \(\displaystyle h\). Denote by \(\displaystyle H\) the subgroup of \(\displaystyle G\) generated by all elements of the form \(\displaystyle w_{k}w_{k+1}\ldots w_{k+n-1}\) with \(\displaystyle k\geq 1\). Prove that \(\displaystyle H\) does not depend on the choice of the sequence \(\displaystyle w\) (but may depend on \(\displaystyle n\)).

Ivan Mitrofanov, Saarland University

Solution. Let \(\displaystyle X_m\) denote the subset of \(\displaystyle G\) of products of the form \(\displaystyle g_1\ldots g_m\), where each \(\displaystyle g_i\) is either \(\displaystyle g\) or \(\displaystyle h\).

Lemma. For all \(\displaystyle j=1,2,\ldots,n\) and for all \(\displaystyle a,b\in X_j\) the ratio \(\displaystyle a^{-1}b\) is contained in \(\displaystyle H\).

Proof. Induction in \(\displaystyle j\).

We start with the base case \(\displaystyle j=1\). By the pigeonhole principle, there exist \(\displaystyle k<\ell\) for which the sequences \(\displaystyle (w_{k+1},\ldots,w_{k+n-1})\) and \(\displaystyle (w_{\ell+1},\ldots,w_{\ell+n-1})\) coincide. If \(\displaystyle w_{k+m}=w_{\ell+m}\) for all positive integer \(\displaystyle m\), then the sequence \(\displaystyle w\) is eventually periodic with period \(\displaystyle \ell-k\). Thus, there exists \(\displaystyle m>0\) for which \(\displaystyle w_{k+m}\ne w_{\ell+m}\). We have \(\displaystyle m\geqslant n\), so \(\displaystyle w_{k+m-i}=w_{\ell+m-i}\) for \(\displaystyle i=1,2,\ldots,n-1\). Therefore, since the products \(\displaystyle x=w_{k+m-n+1}\ldots w_{k+m}\) and \(\displaystyle y=w_{\ell+m-n+1}\ldots w_{\ell+m}\) both are elements of \(\displaystyle H\), the subgroup \(\displaystyle H\) contains their ratios \(\displaystyle x^{-1}y\) and \(\displaystyle y^{-1}x\). These ratios are equal to \(\displaystyle g^{-1}h\) and \(\displaystyle h^{-1}g\) (in some order), that finishes the proof for \(\displaystyle j=1\).

Induction step from \(\displaystyle j-1\) to \(\displaystyle j\), \(\displaystyle 2\leqslant j\leqslant n\). We say that an element \(\displaystyle a\in X_j\) is a \(\displaystyle g\)-element, correspondingly an \(\displaystyle h\)-element, if it can be represented as \(\displaystyle a=g a_1\), correspondingly \(\displaystyle a=ha_1\), where \(\displaystyle a_1\in X_{j-1}\). The ratio of two \(\displaystyle g\)-elements, or of two \(\displaystyle h\)-elements, is a ratio of two elements of \(\displaystyle X_{j-1}\), thus, it is in \(\displaystyle H\) by the induction hypothesis. Since the property \(\displaystyle a^{-1}b\in H\) is an equivalence relation on pairs \(\displaystyle (a,b)\), it suffices to find a \(\displaystyle g\)-element and \(\displaystyle h\)-element whose ratio is in \(\displaystyle H\).

Define \(\displaystyle k,\ell,m\), as in the base case. The subgroup \(\displaystyle H\) contains the products

$$\begin{align*} v&=w_{k+m-n+j}\dots w_{k+m}w_{k+m+1}\dots w_{k+m+j-1},\\ u&=w_{\ell+m-n+j}\dots w_{\ell+m}w_{\ell+m+1}\dots w_{\ell+m+j-1}. \end{align*}$$

Their ratio \(\displaystyle u^{-1}v\) is a ratio of \(\displaystyle g\)-element and an \(\displaystyle h\)-element in \(\displaystyle X_j\), since \(\displaystyle \{w_{k+m}, w_{\ell+m}\}=\{g,h\}\) and \(\displaystyle w_{k+m-i}=w_{\ell+m-i}\) for all \(\displaystyle i=1,2,\ldots,n-j\).

The Lemma for \(\displaystyle j=n\) yields that \(\displaystyle H\) is the subgroup of \(\displaystyle G\) generated by \(\displaystyle X_n\), and this description does not depend on \(\displaystyle w\).