Thread: Minimal Generating Sets (Basis) for a Group

1. Minimal Generating Sets (Basis) for a Group

Hi guys,

Let me quickly define my terms here:

A generating set for a group is a set of group elements that together can express every other element of the group (and no more) through products and inverses.

A basis or minimal generating set is a generating set such that if you remove any elements from the set, it is no longer a generating set.

I may have used nonstandard terminology, but this is how I think about it.

Anyways my question is:
Let G be a group

For any n less than |G|, does there exist a basis of this size n?
Why?

If anyone knows the answer to the analogous question with the group infinite, thats cool beans as well.

2. Originally Posted by Xian
Hi guys,

Let me quickly define my terms here:

A generating set for a group is a set of group elements that together can express every other element of the group (and no more) through products and inverses.

A basis or minimal generating set is a generating set that if you remove any elements from the set, it is no longer a generating set.

I may have used nonstandard terminology, but this is how I think about it.

Anyways my question is:
For any n less than G, does there exist a basis of this size?
Why?

If anyone knows the answer to the analogous question with the group infinite, thats cool beans as well.

1) Don't use "basis" in this context. It can be pretty misleading

2) Your question is completely incomprehensible: what is n, what is G...what did you mean??

Tonio

3. I have edited the phrasing a bit now so that its crystal clear.
I suppose I should have defined G as a group and not accidentally omit the cardinality operation.
I thought n would obviously be a number, considering the language being used.
I think basis is a reasonable term here, since this set is quite analogous to the linear algebra basis in the sense that it minimally generates the space (in this case a group).

Anyways, all those trivial details aside, any thoughts?

4. Originally Posted by Xian
I have edited the phrasing a bit now so that its crystal clear.
I suppose I should have defined G as a group and not accidentally omit the cardinality operation.
I thought n would obviously be a number, considering the language being used.
I think basis is a reasonable term here, since this set is quite analogous to the linear algebra basis in the sense that it minimally generates the space (in this case a group).

Anyways, all those trivial details aside, any thoughts?
Once again, the name "base" is reserved for other things within group theory. And once again, again, your question makes no sense: what do you mean by "for any n less than G"??
Perhaps you mean that G is a (finite?) group of order |G|, then does there exist a minimal generating set (for this same group G?) with n, n < |G|, elements? If this is what you meant to ask, and I'm not sure at all it is, the answer is obviously no.

Tonio

5. Originally Posted by tonio
Once again, the name "base" is reserved for other things within group theory. And once again, again, your question makes no sense: what do you mean by "for any n less than G"??
Perhaps you mean that G is a (finite?) group of order |G|, then does there exist a minimal generating set (for this same group G?) with n, n < |G|, elements? If this is what you meant to ask, and I'm not sure at all it is, the answer is obviously no.
Tonio
Well, if you read the mentioned edit you would have noticed that your guess as to what my "incomprehensible" query meant was indeed correct.

Its actually not important whether G is finite or not actually because there is an ordering for all cardinals, but as it happens to turn out it was the finite case which I was curious about.

Now, its nice that the answer is obviously no, however that does not answer the whole question. That is, it fails to answer the why.

6. Originally Posted by Xian
Well, if you read the mentioned edit you would have noticed that your guess as to what my "incomprehensible" query meant was indeed correct.

Its actually not important whether G is finite or not actually because there is an ordering for all cardinals, but as it happens to turn out it was the finite case which I was curious about.

Now, its nice that the answer is obviously no, however that does not answer the whole question. That is, it fails to answer the why.
That's even easier: take any cyclic group of order bigger than 2, then it only needs one single element to be generated...

Tonio

7. Originally Posted by tonio
That's even easier: take any cyclic group of order bigger than 2, then it only needs one single element to be generated...

Tonio
It is obviously true that a single element is sufficient to generate it, but I said a minimal generating set is a set that generates the group, and also has the property that it is no longer a generating set if an element is removed. This leaves room for other min. gen. sets.

If you consider a cyclic group of order k, $C_k$, and let $x_1, x_2, x_3,... x_m$ be the prime factors of k we can construct another min. gen. set. If we collect a set of elements from $C_k$ such that for each prime factor there is exactly one element of that order, then we have a generating set. Further more it is minimal because any removal will make it lose it generating property. So there are other min. gen. sets besides those of order 1. I have an instictive feeling that there will be forbidden sizes, but I am very curious as to the properties of these forbidden sizes. They must inevitably be connected to the group structure.

Another example of a family of groups with at least two mingen sets is $S_n$. Two mingen sets are {(12...n), $\tau$} where $\tau$ is a tansposition or {all transposition} (according to my professor). I don't know if there are any other mingen sets but would definitely like to know if the research has been done.

Any insight?

8. Originally Posted by Xian
It is obviously true that a single element is sufficient to generate it, but I said a minimal generating set is a set that generates the group, and also has the property that it is no longer a generating set if an element is removed. This leaves room for other min. gen. sets.

If you consider a cyclic group of order k, $C_k$, and let $x_1, x_2, x_3,... x_m$ be the prime factors of k we can construct another min. gen. set. If we collect a set of elements from $C_k$ such that for each prime factor there is exactly one element of that order, then we have a generating set. Further more it is minimal because any removal will make it lose it generating property. So there are other min. gen. sets besides those of order 1.

Either you are very confused, or else I don't understand what you're saying: if you meant to take the set of all the elements $\{x,x^{k_1},...,x^{k_m}\}$ , with $(k,k_j)=1$ , then one single element of these is enough to generate the whole cyclic group of order k, and then the above set is not minimal generating. That'd be a contradiction to the group being cyclic.

Tonio

I have an instictive feeling that there will be forbidden sizes, but I am very curious as to the properties of these forbidden sizes. They must inevitably be connected to the group structure.

Another example of a family of groups with at least two mingen sets is $S_n$. Two mingen sets are {(12...n), $\tau$} where $\tau$ is a tansposition or {all transposition} (according to my professor). I don't know if there are any other mingen sets but would definitely like to know if the research has been done.

Any insight?
.

9. I haven't ever though about this before, but I do think it is quite intriguing. Take a group, then what are the possible sizes of (independent) generating sets (there is a name for these things - I can't remember it though!)? Is this a question which you have been set, or one you are contemplating yourself? However, note that if we take a group G of prime order then it is cyclic and generated by any non-trivial element. Every independent generating set (or basis or whatever) has size precisely 1. On the other hand, assume G is not cyclic then there is not a minimal generating set of size 1.

There is a series of papers by one (James?) Wiegold which discusses this (sort of) generalised to cross products, and you may find it intriguing/usefull to look up. Let G by a group and use $G^n$ to denote $G \times G \times \ldots G$ n-times. Then how many elements does a minimum (a basis of smallest size) generating set of G need? This is actually an interesting question for semigroups to - if $\mathbb{N}$ is the natural numbers under addition withzero then $\mathbb{N} \times \mathbb{N}$ needs 2 elements to generate it, while if we remove the 0s it needs...infinitely many! You may find the semigroup stuff in papers by one Nik Ruskuc, I believe.

Originally Posted by tonio
.
A theorem of Tarski (The Irredundant Basis Theorem) in universal algebra
asserts that for groups there are no gaps. For your example, Z_m,
m= a product of k distinct primes, the largest irredundant basis has
k elements as you noted, the smallest has 1, and all sizes in between are
possible.

It is a theorem of Whiston that the largest irredundant basis of S_n, the
n-th symmetric group is n-1; the proof requires the classification of the
finite simple groups.

11. Originally Posted by rkd
A theorem of Tarski (The Irredundant Basis Theorem) in universal algebra
asserts that for groups there are no gaps. For your example, Z_m,
m= a product of k distinct primes, the largest irredundant basis has
k elements as you noted, the smallest has 1, and all sizes in between are
possible.

It is a theorem of Whiston that the largest irredundant basis of S_n, the
n-th symmetric group is n-1; the proof requires the classification of the
finite simple groups.
What do you mean by there are no gaps'?

Also - and I don't know why I didn't think of this before - the Burnside Basis Theorem solves this problem for p-groups. If $|G: Frat(G)| = p^r$ then every basis contains precisely $r$ elements. See p140 of Robinson'sA Course in the Theory of Groups'. (Frat(G) is the Frattini subgroup of G, and is defined to be the intersection of all the maximal subgroups of G, or equivalently the set of non-generators for G (x is a non-generator if $x\in S$ with $=G$ then $ = G$). The theorem also tells us that $Frat(G) = G^{\prime}G^p$).

Also, another interesting fact is that some groups do not contain any basis. For example, the prufer quasicyclic p-group does not contain a basis (assume it does, then there exists some generating set, B, such than removing an element no longer generated your group. Let $x\in B$. However, the p-th roots of $x$ must be contained in the group, and cannot be generated by $x$, and so they are contained in $$. However, as the p-th roots of $x$ are in $$ then so is $x$ and so $B\setminus x$ generates $G$, a contradiction).

12. Originally Posted by Swlabr
What do you mean by there are no gaps'?

Also - and I don't know why I didn't think of this before - the Burnside Basis Theorem solves this problem for p-groups. If $|G: Frat(G)| = p^r$ then every basis contains precisely $r$ elements. See p140 of Robinson'sA Course in the Theory of Groups'. (Frat(G) is the Frattini subgroup of G, and is defined to be the intersection of all the maximal subgroups of G, or equivalently the set of non-generators for G (x is a non-generator if $x\in S$ with $=G$ then $ = G$). The theorem also tells us that $Frat(G) = G^{\prime}G^p$).

Also, another interesting fact is that some groups do not contain any basis. For example, the prufer quasicyclic p-group does not contain a basis (assume it does, then there exists some generating set, B, such than removing an element no longer generated your group. Let $x\in B$. However, the p-th roots of $x$ must be contained in the group, and cannot be generated by $x$, and so they are contained in $$. However, as the p-th roots of $x$ are in $$ then so is $x$ and so $B\setminus x$ generates $G$, a contradiction).

No gaps = all possible values between smallest possible size of a generating set
and the largest possible size of an irredundant = independent generating set

,

,

,

,

basis iff minimal generating

Click on a term to search for related topics.