Proving that the following subset of $\mathbb{Z}$ is the subgroup generated by its minimum

Question

Let $F$ be a free abelian group, i.e. $F \simeq \mathbb{Z}^n$ for some $n \in \mathbb{N}$, $n \neq 0$ and let $G < F$ be a subgroup. Consider the following subset of $\mathbb{Z}$: \begin{equation} S := \bigl\{\,s \in \mathbb{Z} \, \bigm| \, sy_1+k_2y_2+\dots+k_ny_n \in G \, , \, \exists \, \{y_1,\dots,y_n\} \hspace{1mm} \text{basis of $F$} \, , \, k_2,\dots,k_n \in \mathbb{Z}\,\bigr\} \end{equation} Let $d_1$ be the minimum of $S$, which is well defined because $S$ is a non-empty set (in fact, $0 \in S$). I need to prove that $S = \langle d_1 \rangle$, where $\langle d_1 \rangle$ denotes the subgroup generated by $d_1$, i.e. the subgroup $\{\,kd_1 \mid k \in \mathbb{Z}\,\} < \mathbb{Z}$. My idea was a proof by double inclusion. Clearly, $\langle d_1 \rangle \subseteq S$: let $kd_1 \in \langle d_1 \rangle$. Then, since $d_1 \in S$, there exist a basis $\{y_1,\dots,y_n\}$ for $F$ and elements $k_2,\dots,k_n \in \mathbb{Z}$ such that $d_1y_1 + k_2y_2 + \dots + k_ny_n \in G$. Since $G < F$ is a subgroup, $kd_1y_1 + kk_2y_2 + \dots + kk_ny_n \in G$ too and this proves that $kd_1 \in S$. I'm stuck with the inclusion $S \subseteq \langle d_1 \rangle$.

Answer 1

You need to choose $d_1$ to be minimal in $S$ with $d_1 \ge 0$. If $d_1=0$ then $S$ is the trivial subgroup so assume not.

So there exists $g=d_1y_1 + k_2y_2 + \cdots k_ny_n \in G$. First note that $d_1$ divides each $k_j$, because if not, then we could write $k_j = rd_1+s$ with $0 < s < d_1$, and then writing $g$ in the free basis $y_1',y_2,\ldots,y_n$ with $y_1' = y_1 + ry_j$ gives $g= d_1y_1' + \cdots + sy_j + \cdots$, contradicting minimalty of $d_1$.

Now let $h = l_1y_1 + \cdots l_ny_n$ be an arbitrary element of $G$. We claim that $d_1$ divides each $l_j$. Note first that $d_1$ divides $l_1$, since otherwise $l_1 = rd_1+s$ with $0 < s < d_1$, and then $h-rg = sy_1 + \cdots$ contradicts the choice of $d_1$.

So $l_1 = d_1r$ for some $r$, and then $$h-(r-1)g = d_1 y_1 + (l_2 -(r-1)k_2)y_2 + \cdots + (l_n - (r-1)k_n)y_n.$$ By the same argument as before, $d_1$ divides each $l_j - (r-1)k_j$ and, since we already know that $d_1$ divides $k_j$, we have $d_1$ divides $l_j$ as claimed.

To write $h$ as a linear combination of a different free basis of $F$, we multiply the vector $(l_1,\ldots,l_n)$ by the change of basis matrix, which is an $n \times n$ matrix with integer entries (and determinant $\pm1$). So the coeffiecients with respect to the new basis are still all divisible by $d_1$.

To avoid talking about a change of basis matrix explicitly,let $z_1,z_2,\ldots,z_n$ be an arbitrary free basis of $F$. Then each $y_i$ can be expressed as a linear combination of the $z_j$, say $y_i = \sum_{j=1}^n \alpha_{ij}z_j$. So then $$h = \sum_{i=1}^n l_i y_i = \sum_{j=1}^n(\sum_{i=1}^n l_i\alpha_{ij})z_j,$$ and since each $l_i$ is divisible by $d_1$, it follows that the coefficients of $h$ when expressed as a linear combination of the $z_i$ are also divisible by $d_1$.

So $S \le \langle d_1 \rangle$ as required.