The Chebotarev Invariant of a Finite Group

Abstract

We consider invariants of a finite group related to the number of random (independent, uniformly distributed) conjugacy classes that are required to generate it. These invariants are intuitively related to problems of Galois theory. We find group-theoretic expressions for them and investigate their values both theoretically and numerically.

2000 AMS Subject Classification:

• 20P05
• 20Dxx
• 20K01
• 20F69
• 60Bxx

Keywords:

• Chebotarev density theorem
• coupon collector problems
• Galois group
• conjugacy classes generating a group
• probabilistic group theory

Notes

¹After the first version of this paper appeared as a preprint, some new results appeared in [Kantor et al. 10]; see the remarks at the end of Section 4.

²This means distributed in proportion to the size of the conjugacy class.

³Alternatively, following [Dixon 92], one says that elements (g ₁, … , g_m ) invariably generate G if their conjugacy classes generate G in the above sense.

⁴Note that this depends on the underlying group G.

⁵The trivial bound in trying to estimate c(G) in terms of |G| is easily seen to be c(G)⩽|G|².

⁶This conjecture is imprecisely formulated in [Dixon 92], where the “expected number of elements needed to generate invariably” seems to mean any r(n) for which .