IMC 2024 · Day 1 · P4

Let $X_m$ denote the subset of $G$ of products of the form $g_1 \dots g_m$, where each $g_i$ is either $g$ or $h$.

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

Proof. Induction in $j$.

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

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

Define $k, \ell, m$, as in the base case. The subgroup $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 $u^{-1} v$ is a ratio of $g$-element and an $h$-element in $X_j$, since $\{w_{k+m}, w_{\ell+m}\} = \{g, h\}$ and $w_{k+m-i} = w_{\ell+m-i}$ for all $i = 1, 2, \dots, n-j$.

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