Continuing the series of previous posts on what I called the Chebotarev invariant, here are some (easy) results on cyclic groups, which are certainly the simplest groups to consider!
Starting from the formula for c(G)
we obtain by a straightforward translation between maximal subgroups of Z/nZ and prime divisors of n (the subgroup corresponding to some p|n being given by pZ/nZ), the formula
which is not without some interest — it is both familiar-looking (a sum over divisors with a Möbius function involved –, yet subtly different — the factor 1/(1-1/d) which is not multiplicative in d.
To go further, the natural step is to expand this last term in geometric series, since each of the terms dk which then appear is multiplicative (this is the analogue of obtaining directly the formula explained in T. Tao’s comment on one of the earlier posts on combinatorial cancellation); exchanging the resulting sums and transforming the inner sums using multiplicativity, we get
which is rewritten most conveniently by isolating the first two terms:
and the point is that a trivial estimate follows
where the last series is convergent.
In fact, this last series, plus 1 (which can be considered to be the natural term k=1 since the Riemann zeta function has a pole at s=1), is a “known” constant, called the Niven constant N: its defining property is that it is the average value of the maximal power of a prime dividing n:
It is more or less obvious that the upper estimate above is best possible: if we consider n given by the product of the first k primes, and let k tend to infinity, we get a sequence of integers where c(Z/nZ) converges to 1+N.
The appearance of N here is, a posteriori at least, easy to explain: it is because
is both the probability that a “random” vector in Zk not be primitive (i.e., its coordinates are not coprime in their totality; this is what lies behind our computation), and the probability that a “random” integer is not k-power free (i.e, it is divisible by a k-th power; this is why N appears in the average of α(n)).
The numerical value of N is very easy to compute (using Pari for instance):
(and to show how mathematical knowledge has degenerated, I did not recognize the value N from a well-rounded knowledge of analytic number theory, but by searching for 0.70521, 1.70521 and 2.70521 with Google…)
So, the conclusion is that, for a cyclic group with many subgroups, we may have to get close to 3 elements before we can conclude that we have generators of the whole group. Whether that is surprising or not will of course depend on the reader.
Now, it is natural to go somewhat further if we consider the definition of the Chebotarev invariant as the expectation of a random variable. As is emphasized in any probability theory course, the expectation is very far from sufficient to get a good idea, in general, of a random variable: the basic question is whether its values are rather concentrated around the average, or if instead they tend to spread out a lot. A much better feeling of the variable (though still allowing a lot of variation among all possible distributions) arises if the variance V (or the second moment M2) is known; recall that
One can compute, in principle, the second moment of the waiting time whose expectation is the Chebotarev invariant by a formula similar to the one described above. In the special case of a cyclic group, and assuming I did not make a mistake in the computation (which I have yet to check by consulting probabilists), we get
(where I write c2(G) for the second moment, and where [d,e] is the lcm of d and e).
This sum is not much more difficult to approach than the previous one, and after some computations it reduces to a single divisor sum
from which the estimates
follow; as before, they are best possible, but this time the new constant
does not seem to have appeared before — at least, according to Google.
All this gives a variance, in the case of n with many small prime factors, which is close to
(hence a standard deviation around 1.18, and is therefore not negligible at all compared with the expectation).
Now what about the field with 6 elements? Well, the point is that both for the Chebotarev invariant and for the secondary one, the expression as a divisor sum is an inclusion-exclusion (or sieve) formula over the non-trivial subgroups of Z/nZ, where the terms corresponding to each d are the same as if we computed the corresponding invariant for a hypothetical group with d elements having no subgroup except the trivial one and the whole group, such as the additive groups of finite prime fields do. So for n=6, things behave in this respect as if a field with 6 elements existed. (Yes, this is far-fetched…)