# Find all subgroups of $\mathbb{Z}\times\mathbb{Z}$.

Find all subgroups of $\mathbb{Z}\times\mathbb{Z}$.

I can find all the infinite subgroups of the form $n\mathbb{Z}\times m\mathbb{Z}$, where $n,m$ run over $\mathbb{Z}$. But I don't know how to write out all the finite subgroups in a uniform expression.

-
Technically you have found all subgroups up to isomorphism, but I wonder if you have found all the subgroups themselves. For example, $$(1,1)\Bbb Z=\{(n,n):n\in\Bbb Z\}\le\Bbb Z\times\Bbb Z$$ cannot be written as the internal direct sum $$n(\Bbb Z\times 0)\oplus m(0\times\Bbb Z)=\{(nx,my):x,y\in \Bbb Z\}$$ for any $n,m\in\Bbb Z$, although is is isomomorphic to $n(\Bbb Z\times0)\oplus0(0\times\Bbb Z)$. (Indeed the subgroups you identify are all isomorphic for nonzero $n,m$ but are not the same subgroups.) –  anon Sep 11 '12 at 1:28
@anon What do you mean by "isomorphism" in this context? What are its origin and target? –  Vladimir Sep 11 '12 at 1:40
I mean, for example, $\{(2x,0):x\in\Bbb Z\}$ is isomorphic to $\{(x,x):x\in\Bbb Z\}$, via the map $(2a,0)\mapsto(a,a)$, though these are not the same subgroup of $\Bbb Z\times\Bbb Z$. –  anon Sep 11 '12 at 1:50
@anon But these two subgroups seem both in $n\mathbb{Z}\times m\mathbb{Z}$... Confused... –  Vladimir Sep 11 '12 at 2:01
I'm afraid it gets worse than that, @anon: the subgroup generated by (1,1) and (1,-1), for instance. –  Billy Sep 11 '12 at 3:22

Let $e_1 = (1, 0), e_2 = (0, 1)$ be the canonical basis of $\mathbb{Z}\times\mathbb{Z}$. Let $p_i\colon \mathbb{Z}\times\mathbb{Z} \rightarrow \mathbb{Z}$ be the $i$-th projection for $i = 1, 2$. Let $N \neq 0$ be a subgroup of $\mathbb{Z}\times\mathbb{Z}$. If $p_1(N) = 0$, then $N \subset \mathbb{Z}e_2$. Hence $N = \mathbb{Z}be_2$ for some integer $b > 0$. If $p_1(N) \neq 0$, then $p_1(N) = \mathbb{Z}a$ for some integer $a > 0$. Hence there exists $y_1 \in N$ such that $p_1(y_1) = a$. Let $x = x_1e_1 + x_2e_2 \in N$. Then $x_1$ is divisible by $a$. Hence $x - ny_1 \in \mathbb{Z}e_2$ for some integer $n$. Since $x - ny_1 \in N \cap \mathbb{Z}e_2$, $N = \mathbb{Z}y_1 \oplus (N \cap \mathbb{Z}e_2)$. If $N \cap \mathbb{Z}e_2 = 0$, then $N = \mathbb{Z}y_1$. If $N \cap \mathbb{Z}e_2 \neq 0$, then $N \cap \mathbb{Z}e_2 = \mathbb{Z}ce_2$ for some integer $c > 0$. Hence $N = \mathbb{Z}y_1 \oplus \mathbb{Z}ce_2$

Therefore the non-zero subgroups of $\mathbb{Z}\times\mathbb{Z}$ are classified as follows.

(1) $N = \mathbb{Z}be_2$ for some integer $b > 0$.

(2) $N = \mathbb{Z}y_1$, where $y_1 = ae_1 + be_2, a > 0$

(3) $N = \mathbb{Z}y_1 \oplus \mathbb{Z}ce_2$, where $y_1 = ae_1 + be_2, a > 0, c > 0$

-
This is a clean proof. –  Bombyx mori Sep 11 '12 at 6:02
Can't this be simplified to $N = \mathbb{Z}y_1 + \mathbb{Z}y_2$ with $y_1, y_2 \in \mathbb{Z}\times\mathbb{Z}$? –  lhf Sep 11 '12 at 11:23
@lhf The bases are explicitly given. –  Makoto Kato Sep 11 '12 at 12:20
I wonder what is the "i-th projection". What are $p_1$ and $p_2$? Thanks. –  Vladimir Sep 11 '12 at 13:57
@JackWitt $p_1(x, y) = x, p_2(x, y) = y$ –  Makoto Kato Sep 11 '12 at 14:00

You should find it quite easy to write out all the finite subgroups of $\mathbb{Z}$. (If you're still struggling, here's a hint: a finite subgroup will have a largest element...) This should give you a clue as to how many finite subgroups there are of $\mathbb{Z}\times\mathbb{Z}$.

-
There are infinitely many finite subgroups, I know. But can I write them in one expression? –  Vladimir Sep 11 '12 at 0:57
Are there? (Hint: no.) –  Billy Sep 11 '12 at 0:58
Perhaps that was a rather mean hint. So let me be more explicit. Z has no finite subgroups except {0}, because if any subgroup contains the element n (n =/= 0), then it also contains n+n, n+n+n, n+n+n+n, ..., all of which are non-zero in Z. Perhaps you're confusing subgroups with quotient groups? –  Billy Sep 11 '12 at 1:00
Like ${(-n,-n),(0,0),(n,n)}$, where $n$ runs over positive integers. Doesn't it generate infinite many? –  Vladimir Sep 11 '12 at 1:02
That set doesn't form a group - if it contains (n,n), then it should contain (n,n) + (n,n) too, for example. In general, if g and h are elements of a group G, then g*h must be too - otherwise it's not a group. –  Billy Sep 11 '12 at 1:05

I accidentally made an incorrect comment, and the question still hasn't been answered entirely, so it seems fair that I should come back and answer the other half...

The question is: have you found all the infinite subgroups of $\mathbb{Z}\times\mathbb{Z}$? And the answer is no. Where are the rest?

The subgroups $m\mathbb{Z} \times n\mathbb{Z}$ are generated by two elements: (m,0) and (0,n). This generates a nice, rectangular-looking grid (unless either m or n is zero, in which case we get a horizontal/vertical line, or 0 itself). What else is there? Well, clearly there's the line generated by (1,1), or indeed (1,2), (1,3), (5,7), or anything else. There are also all kinds of parallelogram-shaped grids, e.g. the one generated by (3,0) and (1,1). Do we get anything more exotic? These look a little reminiscent of 0-, 1- and 2-dimensional subspaces of a vector space...

In fact, the answer is that we don't get anything more exotic - all of our subgroups look like parallelogram-shaped grids, with two generators, except for the degenerate cases (the lines and 0). Why not? Well, we can't appeal to linear algebra directly (vector spaces and finitely generated abelian groups are similar, but subtly different things), but we can certainly borrow a trick from it.

Let me give you an example, and hopefully you can fill in the details. Suppose your group is generated by 3 (or more) things: $g_1, g_2, g_3$. Then it's obviously also generated by $g_1, g_2, (g_3+g_2)$, or by $g_1, g_2, (g_3-g_1)$, or similar things. In other words, one at a time, we can add/subtract integer multiples of one generator to/from another. So let's look at the group generated by (5,0), (1,1) and (3,-4):

(5,0), (1,1), (3,-4) - these are my current generators. I'm going to add the second to the third, 4 times:

(5,0), (1,1), (7,0) - and these still generate the same group. Now I'll subtract the first from the third:

(5,0), (1,1), (2,0) - and now I'll subtract the third from the first, twice:

(1,0), (1,1), (2,0) - and now I'll subtract the first from the third, twice:

(1,0), (1,1), (0,0) - and now I only really have 2 generators, because (0,0) doesn't generate anything. So it's a 2-dimensional subgroup after all.

Can you fill in the details for the general case?

-
You know you could edit your original answer with this information? –  JSchlather Sep 11 '12 at 5:39
I know that. I don't know for certain that it notifies Jack that I've edited my answer (i.e. that he'll ever see it)... –  Billy Sep 11 '12 at 6:11
Thanks, @Billy. Is $\mathbb{Z}\times\mathbb{Z}$ finitely generated? I guess I know how things go here by your well-explained example, but I still can't do the general case... –  Vladimir Sep 11 '12 at 14:03
Yes - it's generated by (1,0) and (0,1), for instance. (You can pick an infinite set of generators, but the point is that all but two of them are redundant.) Suppose I give you three elements (a,b), (c,d) and (e,f) which are supposed to generate a subgroup of $\mathbb{Z}\times\mathbb{Z}$. Can you show that one of them is redundant, by using the same adding/subtracting trick? (Hint: suppose a and c are non-zero. Prove that you can kick it into the form (0,b'), (c',d'), (e',f'). What happens if b' = 0? If b' =/= 0 and d' (or f') =/= 0? If b' =/= 0 and d' = f' = 0? Try some examples.) –  Billy Sep 11 '12 at 15:59

If you can use linear algebra, then consider $V$ the subspace of $\mathbb R^2$ generated by a subgroup $H$ of $\mathbb Z \times \mathbb Z$.

• If $\dim V=0$, then $H=0$.

• If $\dim V=1$, take $u\in H$ with smallest positive length. Then $H=\mathbb Z u$.

• If $\dim V=2$, take $u\in H$ with smallest positive length and take $v \in H\setminus\mathbb Z u$ with smallest positive length. Then $H=\mathbb Z u + \mathbb Z v$.

Thus, all subgroups of $\mathbb Z \times \mathbb Z$ are of the form $\mathbb Z u + \mathbb Z v$, where one or both $u$ and $v$ may be zero.

-
In your second step, I wonder what "length" means here. –  Vladimir Sep 11 '12 at 14:00
"length" means Euclidean length of a vector. –  lhf Sep 11 '12 at 16:30
The only finite subgroup is $\{(0,0)\}$. –  Stefan Smith Sep 16 '12 at 1:28

Let ■ $\{(1, 0),(0, 1)\}$ be the canonical basis of $\mathbb{Z}\times\mathbb{Z}$.
■ $p_i\colon \mathbb{Z}\times\mathbb{Z} \rightarrow \mathbb{Z}$ be the $i$-th projection for $i = 1, 2$. Hence $p_1(x, y) = x, p_2(x, y) = y$
■ $N \neq \emptyset$ be a subgroup of $\mathbb{Z}\times\mathbb{Z}$.

If $p_1(N) = 0$, then $N \subset \mathbb{Z}(0, 1)$.
Hence $N = \mathbb{Z}b(0,1)$ for some integer $b > 0$.

If $p_1(N) \neq 0$, then $p_1(N) = \mathbb{Z}(1,0)$ for some integer $a > 0$.
Hence there exists $y_1 \in N$ such that $p_1(y_1) = a$.
Let $x = x_1(1,0) + x_2(0,1) \in N$. Then $x_1$ is divisible by $a$.
Hence $x - ny_1 \in \mathbb{Z}(0,1)$ for some integer $n$.
Since $y_1 \in N$ and $n$ is an integer, hence $ny_1 \in N$. Notice it's possible $n$ $\not\in N$.
Since $x - ny_1 \in \color{purple}{N \cap \mathbb{Z}(0,1)}$, $N = \mathbb{Z}y_1 +(\color{purple}{N \cap \mathbb{Z}(0,1)})$.
Since $\mathbb{Z}y_1 \cap (\color{purple}{N \cap \mathbb{Z}(0,1)}) = 0, N = \mathbb{Z}y_1 \oplus (\color{purple}{N \cap \mathbb{Z}(0,1)} \,).$

If $N \cap \mathbb{Z}(0,1) = \emptyset$, then $N = \mathbb{Z}y_1$.
If $N \cap \mathbb{Z}e_2 \neq \emptyset$, then $N \cap \mathbb{Z}e_2 = \mathbb{Z}ce_2$ for some integer $c > 0$. Hence $N = \mathbb{Z}y_1 \oplus \mathbb{Z}ce_2$

Therefore the non-zero subgroups of $\mathbb{Z}\times\mathbb{Z}$ are classified as follows.

(1) $N = \mathbb{Z}be_2$ for some integer $b > 0$.

(2) $N = \mathbb{Z}y_1$, where $y_1 = ae_1 + be_2, a > 0$

(3) $N = \mathbb{Z}y_1 \oplus \mathbb{Z}ce_2$, where $y_1 = ae_1 + be_2, a > 0, c > 0$

-