1
$\begingroup$

Say I'm given the group $\Bbb{Z}_6\times \Bbb {Z}_4 \times \Bbb {Z}_2$. How would the minimal generator of it be defined and what should be the algorithm to find it?

First of all, I'm not very clear about how minimal generating set is defined. Is it defined as the smallest set whose pairwise addition of elements (and addition of the elements with themselves) produces the rest of the group elements? (Replace "addition" with whatever "binary operation" is defined for the group)

$\endgroup$
1
  • 1
    $\begingroup$ it's important to remember to talk about "a" minimal generating set rather than "the" minimal generating set, because the same group can have many different minimal generating sets (and they can have different sizes) $\endgroup$ May 23, 2018 at 10:16

2 Answers 2

5
$\begingroup$

First of all, I'm not very clear about how minimal generating set is defined.

A generating subset $X$ of $G$ is a subset such that $G$ is the only subgroup of $G$ containing $X$.

The term "minimal" always refers to some ordering. In this situation it is referring to the ordering given by inclusion. Meaning $X$ is a minimal subset satisfying property $P$ (here $P$ = being a generating subset) if no proper subset of $X$ satisfies $P$.

In other words a minimal generating subset is a generating subset such that none of its subsets is a generating subset.

For example let $G=\mathbb{Z}$ be the group of integers. Then $\{1, 3\}$ is a generating subset but it is not minimal. Inside it there's $\{1\}$ which is a minimal generating subset. Also $\{2, 3\}$ is a minimal generating subset. Note that these subsets do not have the same number of elements even though both are minimal.

Is it defined as the smallest set whose pairwise addition of elements (and addition of the elements with themselves) produces the rest of the group elements?

Sort of. A generating subset can also be defined as a subset $X\subseteq G$ such that every element of $g\in G$ is expressible as $g=x_1\cdots x_n$ for some $x_i\in X$.

Note that "smallest" and "minimal" are (typically) two different things. Smallest means that it is smaller then everything else. Minimal means that there is no smaller. These two are the same for example for (so called) total orderings. And inclusion relationship (over all subsets) is not total.

Say I'm given the group $\Bbb{Z}_6\times \Bbb {Z}_4 \times \Bbb {Z}_2$. How would the minimal generator of it be defined and what should be the algorithm to find it?

The brute force algorithm is always a possibility: you start with a generating subset $X\subseteq G$ (possibly $X=G$) and then you remove elements from $X$ in such a way that the resulting subset is still a generating subset. If you reach a point where removing any element does not produce a generating subset then you are done. This algorithm will work for any finite group.

Now in case of direct products we have an easy situation: if $X, Y$ are (minimal) generating subsets of $G,H$ respectively then $X\times \{e_H\}\cup\{e_G\}\times Y$ is a (minimal) generating subset of $G\times H$ (I encourage you to try proving this fact).

So lets apply it to your case. Since each of the components of $G=\Bbb{Z}_6\times \Bbb {Z}_4 \times \Bbb {Z}_2$ is cyclic then it has exactly one generator. It follows that the following set

$$\{(1,0,0), (0,1,0), (0,0,1)\}$$

is a minimal generating subset of $G$.

$\endgroup$
0
$\begingroup$

This is not an answer but a simple example (and too long for a comment).

Consider $G := (\mathbb Z/6 \mathbb Z, +)$ as example with $a := 2$ and $b := 3$. Then, $ \left\langle a,b\right\rangle = \mathbb Z/6 \mathbb Z$ because $b - a = 1$ and $\left\langle 1\right\rangle = \mathbb Z/6 \mathbb Z$.

But $\left\langle a\right\rangle = \{0,2,4\} \subsetneq \mathbb Z/6 \mathbb Z$ and $ \left\langle b\right\rangle = \{0,3\} \subsetneq \mathbb Z/6 \mathbb Z$, that is, $\{a,b\}$ is a minimal generating set of $\mathbb Z/6 \mathbb Z$.

On the other hand $\left\langle a+b\right\rangle = \{0,5,4,3,2,1\} = \mathbb Z/6 \mathbb Z$, that is, $\{a+b\}$ is a generating set of smallest cardinality where $|\{a+b\}| = 1 < 2 = |\{a,b\}|$.

$\endgroup$

You must log in to answer this question.