| |||||||||||||||

## IMC2024: Day 1, Problem 4
Ivan Mitrofanov, Saarland University
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\). | |||||||||||||||

© IMC |