number of generators of finite group

[gerben]

Can someone give some clarification of why this would be the case:

"A group with less then 1000 elements can be generated by less than 10 elements"

Clearly this is the case for some groups, but is it really the case for any group with less than 1000 elements?

[Simon_Tyler]

I don't know much about finite groups - but this does sound like a question that could be answered using the GAP "Small groups" library:
http://www-public.tu-bs.de/~hubesche/small.html

[Office_Shredder]

What are you going to do, check every group to see what its smallest set of generators is?

It sounds plausible. Suppose we have 10 elements generating a group. To make the group as small as possible we give them all order 2. Then to make sure that there are as few multiplicative combinations as possible, we make all the elements commute. But then we have \mathbb{Z}_2^{10} which has 1024 elements

[adriank]

Does this work? Given a group G, look at its composition series 1 = G0 ⊲ ... ⊲ Gn = G; then letting Qi = Gi/Gi-1 for i = 1, ..., n, we have |G| = |Q1| × ... × |Qn|. Now one may appeal to the classification of finite simple groups (http://en.wikipedia.org/wiki/Finite_simple_group#Non-cyclic_simple_groups_of_small_order) to show that each Qi may be generated by ki elements, where |Qi| ≥ 2ki. (I haven't verified this, but there are only 5 noncyclic cases to check with order less than 1000.) And then note that since Gi-1 ⊲ Gi, generators of Gi-1, together with representatives of generators of Qi = Gi/Gi-1, generate all of Gi. (I imagine this is true but I haven't proven it.) Thus, by induction, G may be generated by k = k1 + ... + kn elements, and |G| = |Q1| × ... × |Qn| ≥ 2k1 + ... + kn = 2k. Thus if |G| < 1000, then k < 10.

Hopefully I haven't done something completely wrong; it's been a while since I've done any group theory. Not to mention that the classification of finite simple groups is a large blunt object that is probably not necessary to prove it.

Yeah, the classification of finite simple groups was completely unnecessary; here's an elementary proof. Let G be a finite group, and let {g1, ..., gn} be a minimal set of generators for G. For 0 ≤ i ≤ n, let Hi be the subgroup of G generated by {g1, ..., gi}. Then 1 = H0 ⊂ ... ⊂ Hn = G, and all the inclusions are proper because the generating set is minimal. (If Hi = Hi-1, then gi is in Hi-1, which makes gi redundant, contradicting minimality.) Now note that by Lagrange's theorem, |Hi| ≥ 2|Hi-1| for 0 < i ≤ n, so that |G| = |Hn| ≥ 2n|H0| = 2n.

[gerben]

Ah yes I see, thanks a lot.

Rewording the idea a bit, it can be stated as shortly as:

Every finite group Gi+1 generated by Gi and one additional element gi+1 ∉ Gi has at least twice the number of elements that Gi has, because it contains both Gi and gi+1Gi. Take G1 = ⟨g1⟩, with g1 ≠ 1, then |G1| ≥ 2 and |G10| ≥ 1024.

So a group with less than 1000 elements cannot need more than 9 generators.