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]

[STRIKE]Does this work? Given a group G, look at its composition series 1 = G₀ ⊲ ... ⊲ G_n = G; then letting Q_i = G_i/G_i-1 for i = 1, ..., n, we have |G| = |Q₁| × ... × |Q_n|. Now one may appeal to the classification of finite simple groups to show that each Q_i may be generated by k_i elements, where |Q_i| ≥ 2^k_i. (I haven't verified this, but there are only 5 noncyclic cases to check with order less than 1000.) And then note that since G_i-1 ⊲ G_i, generators of G_i-1, together with representatives of generators of Q_i = G_i/G_i-1, generate all of G_i. (I imagine this is true but I haven't proven it.) Thus, by induction, G may be generated by k = k₁ + ... + k_n elements, and |G| = |Q₁| × ... × |Q_n| ≥ 2^{k₁ + ... + k_n} = 2^k. 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.[/STRIKE]

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

 

[gerben]

Ah yes I see, thanks a lot.

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

Every finite group G_i+1 generated by G_i and one additional element g_i+1 ∉ G_i has at least twice the number of elements that G_i has, because it contains both G_i and g_i+1G_i. Take G₁ = ⟨g₁⟩, with g₁ ≠ 1, then |G₁| ≥ 2 and |G₁₀| ≥ 1024.

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