2
$\begingroup$

It's very intuitive that the minimal size of a generating set for the group $\mathbb{Z}_n^k=\mathbb{Z}_n\times...\times\mathbb{Z}_n$ is exactly $k$. However, I was actually unable to find a simple proof of this trait (or even better - of a generalized theorem for a product of finite cyclic groups).

I know that for $n=2$ this can be easily proven since $\mathbb{Z}_2^k$ is a vector space. I also know one can use theorems related to free-abelian groups together with homomorphisms from such groups to finite abelian groups to prove the desired result, but it seemed to me like an overkill for a trait that appears to be very basic.

Are there such proofs that are more "elementary"?

$\endgroup$
  • 1
    $\begingroup$ Your argument for $n=2$ works for any prime, and for any $n>1$ ${\mathbb Z}_n^k$ has a quotient ${\mathbb Z}_p^n$ for some prime $p$, $\endgroup$ – Derek Holt Sep 18 '18 at 8:00
  • $\begingroup$ Can you please expand on the case of a general non-prime $n$? $\endgroup$ – Dean Gurvitz Sep 18 '18 at 8:12
1
$\begingroup$

Eventually I found a more elementary proof using combinatorics. The number of elements in $\mathbb{Z}_n^k$ is $n^k$, and the maximal order for each element is $n$. Because $\mathbb{Z}_n^k$ is abelian, the group generated by some elements $x_1,...x_m\in\mathbb{Z}_n^k$ can be written as the set: $$\{x_1^{a_1}*...*x_m^{a_m}|a_1,...,a_m\leq n\}$$ The size of this set is at most $n^m$, and therefore, for the set to be generating, it must contain at least $k$ elements. Since the standard Euclidean base is a generating set of size $k$, we can see that the minimal size of a generating set is indeed exactly $k$.

$\endgroup$
0
$\begingroup$

$\mathbb Z$ is not a vector space but rather a module over the commutative ring $\mathbb Z$. It is finitely generated as a product of finitely generated modules. A system of $k$ linear independent elements in $\mathbb Z$ then form a minimal generating set. Note that in general for modules you have to distinguish between a generating set and a basis. However, in your case it should be possible to repeat the proof that $k$ linear independent vectors form a basis for a vector space $V^k$ to prove that $\mathbb Z^k$ is generated by $k$ linearly independent vectors.

$\endgroup$
  • $\begingroup$ Thank you, however, I am relatively unfamiliar with the language of modules and rings. I will further look into the linear algebra proof for a vector space to see if it helps. $\endgroup$ – Dean Gurvitz Sep 18 '18 at 8:07
  • 1
    $\begingroup$ To define a module you just take the definition of a vector space (=Abelian over a field having scalar multiplication) and replace the field by a ring. Therefore, a module is an Abelian group over a ring having scalar multiplication. Easiest example: every module over a field is a vector space. Have a look in your favorite linear algebra textbook -- where did you really need that you are over a field? almost nowhere! usually, a ring suffices. This is why you can carry over a lot of linear algebra to modules, including things like generating sets. $\endgroup$ – James Sep 18 '18 at 8:27
0
$\begingroup$

Let $\{ C_1, \dots, C_k \}$ be a collection of cyclic groups s.t. $C_i = < a_i >$ and $|C_i| = n_i$, $\forall i = 1 \div k$; and define: $$C = C_1 \times \dots \times C_k$$ Then, it can be readily proven that: $$\tilde{a_i} = (e_1, \dots, a_i, \dots, e_k) \in C \> \land \> \tilde{C_i} \leq C, \forall i = 1 \div k$$ Therefore, due to the definition of Cartesian product, $C$ has $k$ generators: $\{ \tilde{a_1}, \dots, \tilde{a_k} \}$.

$\endgroup$
  • $\begingroup$ But how would you prove that this is the minimal number of generators? $\endgroup$ – Dean Gurvitz Sep 18 '18 at 8:08
  • $\begingroup$ Suppose you have an element $x = (x_1, \dots, x_k) \in C$, you can express each $x_i$ as a power of $a_i$; therefore, you can express $x$ as powers of $\tilde{a_1}, \dots, \tilde{a_k}$. Ergo, you don't need more generators. $\endgroup$ – AlbertCG93 Sep 18 '18 at 8:14
  • $\begingroup$ Thank you, but unfortunately this still only proves an upper bound on the number of needed generators, and not a lower bound. $\endgroup$ – Dean Gurvitz Sep 18 '18 at 8:15
  • $\begingroup$ I'm guessing you are considering the possibility of joining two groups together, let's say $\bar{C_1} \cong C_1 \times C_2$, and then having $C = \bar{C_1} \times C_3 \times \dots \times C_k$; is that it? $\endgroup$ – AlbertCG93 Sep 18 '18 at 8:21
  • $\begingroup$ I know it isn't actually possible to do so, but I am looking for a proof for that. As I said, the minimality is a very intuitive trait to which I didn't find a simple proof. $\endgroup$ – Dean Gurvitz Sep 18 '18 at 8:25
0
$\begingroup$

I am not sure if you will like this argument, but it gives a more general result. Your question is a special case of the proposition below with $(R,I):=(\mathbb{Z},n\mathbb{Z})$. The proposition below, while not elementary, can be used to deal with the case where $(R/I)$ is not a finite ring, where your argument based on counting does not work. (This is not to say that your counting argument was not good. I like it very much.)

Proposition. Let $R$ be a commutative unital ring and $I\subsetneq R$ an ideal of $R$. Then, for a positive integer $k$, the $R$-module $(R/I)^k$ is finitely generated (as an $R$-module) and the minimum possible cardinality of a generating set of the $R$-module $(R/I)^k$ is $k$.

First, we know that $(R/I)^k$ is a finitely generated $R$-module,since the finite set $\left\{e_1,e_2,\ldots,e_k\right\}$ generates $(R/I)^k$, where $$e_j:=\left(0_{R/I},\ldots,0_{R/I},1_{R/I},0_{R/I},\ldots,0_{R/I}\right)\in (R/I)^k$$ in which $1_{R/I}$ appears at the $j$-th coordinate (and every other coordinate is $0_{R/I}$) for $j=1,2,\ldots,k$. Now, suppose that $m$ is the smallest positive integer such that $(R/I)^k$ is generated by some $$u_1,u_2,\ldots,u_m\in(R/I)^k$$ as an $R$-module. We then have $m\leq k$.

Let $J$ be a maximal ideal of $R$ containing $I$. Then, $J/I$ is a maximal ideal of $R/I$. Thus, $$F:=R/J\cong\frac{(R/I)}{(J/I)}$$ is a field. Let $\pi:(R/I)\to F$ be the canonical projection. Define the $R$-module homomorphism $\pi_k:(R/I)^k\to F^k$ to be the map sending $$\left(x_1,x_2,\ldots,x_k\right)\mapsto \big(\pi\left(x_1\right),\pi\left(x_2\right),\ldots,\pi\left(x_k\right)\big)$$ for all $x_1,x_2,\ldots,x_k\in R/I$. For $i=1,2,\ldots,m$, set $$v_i:=\pi_k\left(u_i\right)\in F\,.$$ We claim that $v_1,v_2,\ldots,v_m$ span the $F$-vector space $F^k$. Since $\dim_F\big(F^k\big)=k$, we conclude that $m\geq k$, and so $m=k$ must hold.

Write $\epsilon_j:=\pi_k\left(e_j\right)$ for $j=1,2,\ldots,k$. We only need to show that $$\epsilon_j\in\text{span}_F\left\{v_1,v_2,\ldots,v_m\right\}$$ for all $j=1,2,\ldots,k$. However, this is not difficult. Since the elements $u_1,u_2,\ldots,u_m$ generate the $R$-module $(R/I)^k$, there are coefficients $r_\nu^\mu\in R$, where $\mu\in\{1,2,\ldots,m\}$ and $\nu\in\{1,2,\ldots,k\}$, such that $$e_\nu=\sum_{\mu=1}^m\,r^\mu_\nu\,u_\mu\,.$$ That is, $$\epsilon_\nu=\pi_k\left(e_\nu\right)=\sum_{\mu=1}^m\,\pi\left(r^\mu_\nu\right)\,v_\mu$$ for $\nu=1,2,\ldots,k$. The claim is now proven.

P.S. You can modify my proof specifically for $R:=\mathbb{Z}$ and $I:=n\mathbb{Z}$, where $n>1$ is an integer as follows. Let $p$ be a prime natural number dividing $n$. Set $J:=p\mathbb{Z}$ (so $F=\mathbb{F}_p$ is the finite field of order $p$). Everything follows in the same manner.

$\endgroup$
  • $\begingroup$ As I replied to James, I am unfortunately not fluent enough in the language of rings and modules to properly appreciate this answer. Is this basically a conversion of the proof of basis size for vector spaces to modules over rings? $\endgroup$ – Dean Gurvitz Sep 18 '18 at 10:21
  • $\begingroup$ See the post scriptum (P.S.) if you don't want to deal with rings and modules. (The term "(unitary) $\mathbb{Z}$-modules" is just an alias of "abelian groups.") $\endgroup$ – Batominovski Sep 18 '18 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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