# Showing a subgroup of $\mathbb{R}^n$ is a free abelian group on $\leq n$ generators

I'm a bit stuck on Exercise III.5 of Lang's Algebra. (Page 166.)

Let $A$ be an additive subgroup of Euclidean space $\mathbb R^n$, and assume that in every bounded region of space, there is only a finite number of elements of $A$. Show that $A$ is a free abelian group on $\leq n$ generators.

[Hint: Induction on the maximal number of linearly independent elements of $A$ over $\mathbb R$. Let $v_1, \ldots, v_m$ be a maximal set of such elements, and let $A_0$ be the subgroup of $A$ contained in the $\mathbb R$-space generated by $v_1, \ldots, v_{m-1}$. By induction, one may assume that any element of $A_0$ is a linear integral combination of $v_1, \ldots, v_{m-1}$. Let $S$ be the subset of elements $v \in A$ of the form $v= a_1 v_1 + \cdots + a_m v_m$ with real coefficients $a_i$ satisfying $$\begin{eqnarray*} 0 \leq a_i < 1, &\ \ \text{if } i=1,2,\ldots, m-1 \\ 0 \leq a_m \leq 1 .& \end{eqnarray*}$$ If $v'_m$ is an element of $S$ with the smallest $a_m \neq 0$, show that $\{ v_1, \ldots, v_{m-1}, v'_m \}$ is a basis of $A$ over $\mathbb Z$.]

Following the hint, I suppose $c_1v_1+\cdots+c_{m-1}v_{m-1}+c_mv'_m=0$ for $c_i\in\mathbb{Z}$. Then $$c_1v_1+\cdots+c_{m-1}v_{m-1}+c_m(a_1v_1+\cdots+a_mv_m)=0$$ implies $$(c_1+a_mc_1)v_1+\cdots+(c_{m-1}+c_ma_{m-1})v_{m-1}+c_ma_mv_m=0.$$ But $v_1,\dots,v_m$ are linearly independent, so $c_ma_m=0$, thus $c_m=0$ since $a_m\neq 0$. Then since $c_i+c_ma_i=0$ for all other $i$, $c_i=0$ for $i=1,\dots,m-1$, and the vectors are linearly independent over $\mathbb{Z}$.

I'm trying to show $\{v_1,\dots,v_{m-1},v'_m\}$ also span $A$ over $\mathbb{Z}$. Since $v_1,\dots,v_m$ is a maximal linearly independent set, I think I can write any $x\in A$ as $$x=c_1v_1+\cdots+c_mv_m,\quad c_i\in\mathbb{R}.$$ I realized $$x=(\lfloor c_1\rfloor v_1+\cdots+\lfloor c_m\rfloor v_m)+(c'_1v_1+\cdots+c'_mv_m)$$ where $\lfloor \cdot\rfloor$ is the floor function, and $0\leq c'_i<1$. So the second summand in parentheses is in $S$, and the first summand is a linear integral combination of $v_1,\dots,v_m$. I'm not sure if this observation leads anywhere, and I'm not sure where the fact that $A$ has only finitely many elements in every bounded region of space comes in. What's the right way to proceed? Thanks.

Added: With Arturo Magidin's help, $ka_m=c'_m$ for some positive integer $k$. Thus $$x=(\lfloor c_1\rfloor v_1+\cdots+\lfloor c_m\rfloor v_m)+k((c'_1/k)v_1+\cdots+a_mv_m),$$ so taking $v'_m=(c'_1/k)v_1+\cdots+a_mv_m$, $\{v_1,\dots,v_m,v'_m\}$ is a spanning set of $A$ over $\mathbb{Z}$. How can I show from this that $\{v_1,\dots,v_{m-1},v'_m\}$ spans $A$ over $\mathbb{Z}$?

-
To answer your doubt on the hypothesis: the set $S$ is assumed to be finite by your hypothesis but if it is not finite, such a $v_m'$ may not exist. –  tkr Oct 16 '11 at 22:58

You used the fact that $A$ has only finitely many elements in any bounded region of space implicitly when you asserted that the set $S$ would contain an element $v'_m$ with smallest $a_m\neq 0$; you are using the fact that the set $S$ is contained in the ball of radius $\lVert v_1\rVert+\cdots+\lVert v_m\rVert$, hence $S$ is finite, so you can pick that element with "smallest $a_m\neq 0$". Otherwise, since the coefficients are real numbers, there might not be any element with "smallest $v'_m$.

You are doing well. Now, since $c'_1v_1+\cdots +c'_mv_m\in S$, then $c'_m\geq a_m$, where $a_m$ is the coefficient of $v_m$ in the expression for $v'_m$.

Now, there is a smallest positive integer $k$ such that $ka_m \leq c'_m$. You may want to show that $ka_m$ will actually be equal to $c'_m$.

-
@yunone: Note that from $-k(a_1v_1+\cdots + a_mv_m)+ (c'_1v_1+\cdots + c'_mv_m)$ can be used to get an element of $S$ that has $v_m$ component equal to $c'_m-ka_m$. But if this is positive and $(k+1)a_m\gt c'_m$, then $0\lt c'_m-ka_m \lt a_m$, contradicting the minimality of $a_m$. –  Arturo Magidin Oct 17 '11 at 4:28
Ah, so adding those gives $(c'_1-ka_1)v_1+\cdots+(c'_m-ka_m)v_m$, and then if needed I could add to it elements of $A$ of the form $b_iv_i$ for $i=1,\dots,m-1$ and $b_i\in\mathbb{Z}$ to get the appropriate coefficients of $v_1,\dots,v_{m-1}$, to find this contradictory element of $S$. So $ka_m=c'_m$, then $$x=(\lfloor c_1\rfloor v_1+\cdots+\lfloor c_m\rfloor v_m)+k((c'_1/k)v_1+\cdots+a_mv_m),$$ so I can take $v'_m=((c'_1/k)v_1+\cdots+a_mv_m)$. This gives $x$ as a linear integral combination of $\{v_1,\dots,v_m,v'_m\}$. Is there a way to then get rid of the $v_m$? –  yunone Oct 17 '11 at 5:20
@yunone: You are doing things backwards. Start with $x\in A$. Use a variant of the argument I sketched to show that there is a $k$ such that $x-kv'_m$ has $v_m$-component equal to $0$; conclude that $x-kv'_m\in A_0$, and so can be expressed as an integer linear combination of $v_1,\ldots,v_{m-1}$. Deduce that $x$ is an integer linear combination of $v_1,\ldots,v_{m-1},v'_{m}$. –  Arturo Magidin Oct 17 '11 at 20:06
I think I may have something. I know $v_m\in S$, so by same argument you gave to show $ka_m=c'_m$ for some $k$, there is some integer $j$ such that $ja_m=1$. Then $$x=\lfloor c_1\rfloor v_1+\cdots+\lfloor c_{m-1}\rfloor v_{m-1}+(c'_1v_1+\cdots+(k+\lfloor c_m\rfloor j)a_mv_m).$$ Let $p=k+\lfloor c_m\rfloor j$, and $v'_m=((c'_1/p)v_1+\cdots+a_mv_m)$. Then $x-pv'_m\in A_0$, and thus $x$ is a linear combination of $v_1,\dots,v_{m-1},v'_m$. Is this correct? –  yunone Oct 17 '11 at 21:51
@yunone: Looks generally okay, but I didn't check the details. I also think you got too enamoured of your argument with the floors and are trying to shoehorn it in where it is not needed. Let $x\in A$ be arbitrary, written $x=c_1v_1+\cdots +c_mv_m$; by the same argument as used before, there exists an integer $k$ such that the $v_m$ component of $kv'_m$ is the equal to $c_m$. Then $x-kv'_m\in A_0$, so $x-kv'_m$ is an integer linear combination of $v_1,\ldots,v_{m-1}$: $x-kv'_m = a_1v_1+\cdots +a_{m-1}v_{m-1}$. Then $x=a_1v_1+\cdots+a_{m-1}v_{m-1}+kv'_m$ and you are done. –  Arturo Magidin Oct 18 '11 at 3:28
show 1 more comment