The Chebotarev invariant, or Wait-and-See

So here’s the promised explanation for the sums I described in an earlier post about combinatorial cancellation. Those are particular cases of a formula for the evaluation of an invariant of a finite group G, in the case where G is F_p^k. The definition of this invariant, in turn, is motivated by the approach to computing the Galois group of the splitting field of a polynomial which is based on finding some a-priori upper bound G, and then computing the Frobenius automorphisms modulo successive primes until one obtains this way enough conjugacy classes represented by the Galois group to conclude that it must coincide with G (of course, this can only work if the upper-bound was a correct guess…)

This method is not particularly convenient in general but it may be quite useful for theoretical purposes (it combines well with sieve methods, for instance, as first exploited by Gallagher), and also for particular cases where the computations turn out to work very well. F. Jouve, D. Zywina and myself succeeded in using it to construct our surf-shaped polynomial with Galois group W(E₈), as I described earlier. For this, we only needed to look at two primes, and at that time we were somewhat surprised that it should have worked so well. The question is then: is this a justified surprise, or is it simply that it is intrinsically “easy” to check that a subgroup of W(E₈) is the whole group by this method?

To analyze this, one is led rather naturally to investigate the properties of the following probabilistic model: the finite group G being given and fixed, consider a sequence (X_n) of independent random variables, with values in G, each uniformly distributed. Then define the “waiting time”

$\tau_G=\min\{n\geq 1\ |\ X_1^*,\ldots, X_n^*\ generate\ G\}$

where the superscript * indicates that we look at the conjugacy classes, and where a set C of conjugacy classes generates G if and only if there is no proper subgroup H of G which intersects each class in C.

(Note that this notion requires a little care: it is not even entirely obvious that the set of all conjugacy classes generates G, and indeed this is false for certain infinite groups, like SU(n), where every matrix can be diagonalized, i.e., the subgroup of diagonal matrices intersects every conjugacy class; but it is well-known to be the case for a finite group, by an easy counting argument).

The waiting time is somewhat unwieldy: it is a random variable defined on an unspecified probability space. To get a more concrete invariant, consider its expectation:

$c(G)=\mathbf{E}(\tau_G)$

This is what I call the “Chebotarev invariant”, because of the arithmetic motivation: one may expect that, for a given Galois extension K/Q, the Frobenius conjugacy classes σ_p modulo primes are “close”, in some sense, to the probabilistic model of a sequence of conjugacy classes associated to independent random variables as above. Indeed, the Chebotarev density theorem says that, at least, the frequency of apparition is consistent with the Law of Large Numbers:

$\lim_{X\rightarrow +\infty}\frac{1}{\pi(X)}|\{p\leq X\ |\ \sigma_p=C \}|=\frac{|C|}{|G|}$

for any conjugacy class C in G.

So one may hope that c(G) is close, usually, to the number of primes needed to conclude that the Galois group is G and not a proper subgroup of it. (Note however that for an individual extension, trying to quantify how quickly individual conjugacy classes appear as Frobenius conjugacy classes leads immediately to open questions which are intricately linked with the Generalized Riemann Hypothesis, even for the simplest case G=Z/2Z).

In any case, the link with our famous sums is the expression

$c(G)\ \ \ \ \ =\ \ \ \ \sum_{\emptyset\not=I\subset \max(G)}{\frac{(-1)^{|I|+1}}{1-\nu(\cap_{H\in I}{H^*})}}$

where max(G) is the set of conjugacy classes of (proper) maximal subgroups in G, ν(C), for any set of conjugacy classes is |C|/|G|, and H^* is the set of conjugacy classes which intersect a given (conjugacy class of) maximal subgroup. For the case of F_p^k, where conjugacy is trivial, this leads to the sums of the earlier post. This formula is not hard to prove: it is some example of inclusion-exclusion and the computation of the expectation of a geometric random variable.

(Probabilistically, it is a non-standard variant of a general “coupon collector problem”, where the types of coupons correspond roughly to the various conjugacy classes of maximal subgroups, and what is slightly unusual is that a single coupon, i.e., a single sample X_i, may succeed in giving many different types of coupons, namely all classes of maximal subgroups which do not intersect the conjugacy class of X_i).

Now, here I would have liked to give the value of c(W(E₈)), and checked if it was or not significantly larger than 2, but unfortunately, GAP seems not to be up to the job on my laptop, and I don’t have access to Magma at the moment (which, I suspect, would be able to do it, since it was able to compute the set of maximal subgroups very quickly, as described in the two posts here and there concerning my paper with Jouve and Zywina).

So this series of posts is not finished, and I hope to come back with this value, and more, in another episode…

The Chebotarev invariant, or Wait-and-See

Published by

Kowalski