Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$?

share|cite|improve this question
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
up vote 5 down vote accepted

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$.

share|cite|improve this answer
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.