Réduction modulo un sous-groupe d'un groupe abélien libre

(i) Montrons, par récurrence sur $m \in \mathbb N$ (Récurrence), qu'une partie $A$ à $m + 1$ éléments a un plus grand élément. Pour $m = 0$, $A$ a un seul élément, qui convient.

Si $A$ a $m + 2$ éléments, par une bijection $f$ de $m + 2$ sur $A$, la partie $A' = A \setminus \{f(m + 1)\}$ est l'image de $m + 1$ par $f$, et elle a $m + 1$ éléments. Par hypothèse de récurrence, elle a un plus grand élément $a'$, et le plus grand des deux éléments $a'$ et $f(m + 1)$, qui sont comparables puisque l'ordre est total, est le plus grand élément de $A$.

Un bon ordre est total (Bon ordre, (i)), et le support d'un $x \neq 0$ est fini et non vide : il a un plus grand élément $\operatorname{ht}(x)$, et $x(j) = 0$ pour $j > \operatorname{ht}(x)$.

(ii) Supposons $d = x - y$ non nul, et soit $j = \operatorname{ht}(d)$. Comme $d \in F_{<i}$ et $d(j) \neq 0$, on a $j < i$. Par (i), $d \in H_{\leqslant j}$, donc $d(j) = \pi_j(d)$ appartient à $n_j\mathbb Z$.

Puisque $d(j) \neq 0$, cela impose $n_j > 0$ et $|d(j)| \geqslant n_j$ : $j$ est un pivot inférieur à $i$. Mais $x$ et $y$ sont réduits sous $i$, donc $0 \leqslant x(j) < n_j$ et $0 \leqslant y(j) < n_j$, d'où $|d(j)| < n_j$ : contradiction.

(iii) Unicité. Si $z$ et $z'$ conviennent, les éléments $x - z$ et $x - z'$ sont réduits sous $i$, et leur différence $z' - z$ appartient à $H_{<i}$ : ils sont égaux par (ii), donc $z = z'$.

Existence. Soit $Q$ l'ensemble des $i \in I$ tels que, pour tout $x \in F$, il existe $z \in H_{<i}$ avec $x - z$ réduit sous $i$. Par le principe d'induction dans un ensemble bien ordonné (Bon ordre, (ii)), il suffit de montrer que $i \in Q$ dès que tout $j < i$ appartient à $Q$. Supposons-le, et soit $x \in F$.

Soit $A$ l'ensemble des éléments du support de $x$ strictement inférieurs à $i$. Si $A$ est vide, $z = 0$ convient : $x(j) = 0$ pour tout $j < i$, et $0 \leqslant 0 < n_j$ pour tout pivot $j$. Sinon, soit $j$ le plus grand élément de $A$, donné par (i).

Si $j$ est un pivot, il existe, par définition de $n_j$, un élément $g \in H_{\leqslant j}$ tel que $g(j) = n_j$. La division euclidienne (Division euclidienne) donne $x(j) = q n_j + r$ avec $0 \leqslant r < n_j$, et l'on pose $x' = x - qg$, de sorte que $x'(j) = r$. Si $j$ n'est pas un pivot, on pose $x' = x$. Dans les deux cas, $x - x' \in H_{\leqslant j}$, et $x'(k) = x(k)$ pour tout $k > j$.

Comme $j < i$, on a $j \in Q$ : il existe $z' \in H_{<j}$ tel que $x' - z'$ soit réduit sous $j$. Posons $z = (x - x') + z'$. C'est un élément de $H_{\leqslant j}$, donc de $H_{<i}$, et $$x - z = x' - z'.$$ Vérifions que cet élément est réduit sous $i$. Aux pivots $k < j$, c'est le choix de $z'$. Si $j$ est un pivot, sa coordonnée en $j$ est $x'(j) - z'(j) = r$, puisque $z' \in F_{<j}$. Enfin, pour $j < k < i$, on a $x(k) = 0$, puisque $k$ n'est pas dans le support de $x$ au-delà de $\max A$, de sorte que $x'(k) = 0$, et $z'(k) = 0$ : la coordonnée est nulle, ce qui satisfait la condition $0 \leqslant 0 < n_k$. Ainsi $i \in Q$, et $Q = I$.