Q: Are there three $\mathbb{Z}^2$ vectors independent over $\mathbb{Z}$ ?
Context: This problem arise naturally when I'm characterizing possible sub-"latice" in $\mathbb{Z}^2$. Formally let $S$ be a set of points ("lattice points") with integer coordinates, and a set of vectors $V = \{ v_1, v_2, …\} \subseteq \mathbb{Z}^2$ so that for all $p \in S$ and $v \in V$, $$p \pm v \in S.$$ i.e., is also a lattice point.
We can make a hexagon-like lattice by choosing $(v_1, v_2, v_3) = ((2, 1), (2, -1), (0, 2))$. Notice, then, $v_1 – v_2 = v_3$, so $v_3$ is redundant in $V$– so we can remove $v_3$ while keeping the set $S$. So we ask: is the third vector always redundant, in the sense that
$$ cv_3 = av_1+bv_2, a,b,c \in \mathbb{Z} \implies a=b=c=0?$$
A quick search of "L.I. over $\mathbb{Z}$" reveals that in $\mathbb{Z}^n$, linear independence over $\mathbb{Z}$ is equivalent to $\mathbb{R}$. This overkills the question: if there were 3 independent vectors over $\mathbb{Z}$, then they are too in $\mathbb{R}$, a contradiction.
However, the prove involves using the basis of $\mathbb{R}$ over $\mathbb{Q}$ to deal with the real coefficients, which is a implication of Axiom of Choice. Since my question is simple enough, I would like to see if there is a proof without AoC.
Q: Is the negation of "there exists three $\mathbb{Z}^2$ vectors independent over $\mathbb{Z}$" provable without AoC?
Best Answer
Any three elements in $\mathbb{Z}^2$ are also three vectors in $\mathbb{Q}^2$. But $\mathbb{Q}^2$ has dimension $2$ as a $\mathbb{Q}$-vector space (no need for the Axiom of Choice, as $\mathbb{Q}^2$ has an explicit finite generating set over $\mathbb{Q}$).
That means that if $(a_1,b_1)$, $(a_2,b_2)$, and $(a_3,b_3)$ are in $\mathbb{Z}^2$, then there exist rational numbers $\frac{r_1}{s_1}$, $\frac{r_2}{s_2}$, $\frac{r_3}{s_3}$, not all zero, $s_i\neq 0$, such that $$\frac{r_1}{s_1}(a_1,b_1) + \frac{r_2}{s_2}(a_2,b_2) + \frac{r_3}{s_3}(a_3,b_3) = (0,0).$$ Multiplying through by the nonzero element $s_1s_2s_3$, we obtain a $\mathbb{Z}$-linear combination equal to $(0,0)$. Since $s_1s_2s_3\neq 0$ and not all of $r_1$, $r_2$, and $r_3$ are zero, at least one of the coefficients in $$r_1s_2s_3(a_1,b_1) + r_2s_1s_3(a_2,b_2) + r_3s_1s_2(a_3,b_3) = (0,0)$$ is nonzero, proving that the three elements are $\mathbb{Z}$-linearly dependent.