The Chebotarev invariant of a finite group. (English) Zbl 1277.20080

Let \(f(X)\) be an irreducible polynomial over \(\mathbb Z[X]\) and let \(G\) be the Galois group over \(\mathbb Q\) of the splitting field of \(f(X)\) as a permutation group on the roots of \(f(X)\). Then a theorem of Chebotarev shows that in appropriate sense the proportion of primes \(p\) such that \(f(X)\bmod p\) factors into irreducible factors of degrees \(d_1\leq d_2\leq\cdots\leq d_k\) is equal to the proportion of permutations in \(G\) whose cycles are of these lengths. This is used as a heuristic in computing Galois groups. Of particular interest is the use of this heuristic to prove that \(G\) is the full symmetric group since a theorem of van der Waerden shows that the Galois group of a random polynomial in \(\mathbb Z[X]\) will nearly always be the full symmetric group (see [J. D. Dixon, Discrete Math. 105, No. 1-3, 25-39 (1992; Zbl 0756.60010)] and [T. Łuczak and L. Pyber, Comb. Probab. Comput. 2, No. 4, 505-512 (1993; Zbl 0817.20002)]).
Let \(G\) be a finite group and \(L:=\{C_1,\dots,C_m\}\) be a list of conjugacy classes of \(G\). The authors say that \(L\) generates \(G\) if for any \(g_i\in C_i\) we have \(G=\langle g_1,\dots,g_m\rangle\). It is well known that \(L\) generates \(G\) when \(L\) is the set of all conjugacy classes of \(G\). Suppose that we make successive independent choices of conjugacy classes \(C_1,C_2,\dots\) where at each step the class \(C\) is chosen with probability \(|C|/|G|\) until the list of classes we obtain generates \(G\). The Chebotarev invariant \(c(G)\) of \(G\) is defined to the expected number of choices which are made; more generally \(c_k(G)\) is defined to be \(k\)-th moment of this random variable.
The paper discusses a number of properties of the Chebotarev invariants and computes their values for some special cases (for example, for the affine group \(H_q\) of order \(q(q-1)\) where \(q\) is a prime power we have \(c(H_q)\sim q\)). The main theorem of the paper (Theorem 1.1) states that for \(G=S_n\) (the symmetric group of degree \(n\)) each of the sequences \(\{c_k(S_n)\}_{n\geq 1}\) is bounded. Numerical evidence suggests that \(\{c(S_n)\}_{n\geq 1}\) may converge to a limit \(<5\) and \(\{c_2(S_n)\}_{n\geq 1}\) to a limit \(<25\). The proof of Theorem 1.1 follows easily from the paper of Łuczak and Pyber referenced above.


20P05 Probabilistic methods in group theory
20D60 Arithmetic and combinatorial problems involving abstract finite groups
20B30 Symmetric groups
20E45 Conjugacy classes for groups
20F05 Generators, relations, and presentations of groups
12F10 Separable extensions, Galois theory
60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
Full Text: DOI arXiv Euclid


[1] Arratia [Arratia et al. 03] R., Logarithmic Combinatorial Structures: A Probabilistic Approach, E.M.S. Monographs (2003) · doi:10.4171/000
[2] Arratia [Arratia and Tavaré 92] R., Annals of Prob. 20 pp 1567– (1992) · Zbl 0759.60007 · doi:10.1214/aop/1176989707
[3] DOI: 10.1006/jsco.1996.0125 · Zbl 0898.68039 · doi:10.1006/jsco.1996.0125
[4] Dixon [Dixon 92] J. D., Discrete Math. 105 pp 25– (1992) · Zbl 0756.60010 · doi:10.1016/0012-365X(92)90129-4
[5] Dixon [Dixon 02] J. D., C.R. Math. Rep. Acad. Sci. Canada 24 pp 1– (2002)
[6] DOI: 10.1016/0166-218X(92)90177-C · Zbl 0762.60006 · doi:10.1016/0166-218X(92)90177-C
[7] Fulman [Fulman and Guralnick 03] J., Groups, Combinatorics, and Geometry (Durham, 2001) pp 99– (2003)
[8] Fulton [Fulton and Harris 91] W., Representation Theory. A First Course, Grad. Texts in Math. 129. (1991) · Zbl 0744.22001
[9] Gallagher [Gallagher 73] P. X., Proc. Sympos. Pure Math. pp 91– (1973)
[10] Goncharov [Goncharov 44] V., Bull. Acad. Sci. USSR Ser. Mat. (Izv. Akad. Nauk SSSR) 8 pp 3– (1944)
[11] Jouve [Jouve et al. 08] F., Journal de Théorie des Nombres de Bordeaux 20 pp 761– (2008) · Zbl 1200.12003 · doi:10.5802/jtnb.649
[12] Jouve [Jouve et al. 10] F., arXiv pp 1008.3662– (2010)
[13] DOI: 10.1007/BF00181465 · Zbl 0718.20011 · doi:10.1007/BF00181465
[14] Kantor [Kantor et al. 10] W. M., arXiv pp 1010.5722– (2010)
[15] Kowalski [Kowalski and Zywina 11] E., arXiv pp 1008.4909– (2011)
[16] Lagarias [Lagarias et al. 79] J. C., Inventiones math. 54 pp 271– (1979) · Zbl 0401.12014 · doi:10.1007/BF01390234
[17] Lloyd [Lloyd and Shepp 66] S. P., Trans. Amer. Math. Soc. 121 pp 340– (1966) · doi:10.1090/S0002-9947-1966-0195117-8
[18] Łuczak [Łuczak and Pyber 93] T., Combin. Probab. Comput. 2 pp 505– (1993) · Zbl 0817.20002 · doi:10.1017/S0963548300000869
[19] Pomerance [Pomerance 01] C., Period. Math. Hungar. 43 pp 191– (2001) · Zbl 0980.20079 · doi:10.1023/A:1015250102792
[20] Rose [Rose 94] J. S., A Course on Group Theory (1994)
[21] DOI: 10.1007/BF01405086 · Zbl 0235.14012 · doi:10.1007/BF01405086
[22] Serre [Serre 98] J.-P., Abelian -adic Representations and Elliptic Curves, Res. Notes Math (1998)
[23] Serre [Serre 02] J.-P., Math. Medley 29 pp 3– (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.