Tag Archives: random permutations

Random squarefree polynomials and random permutations and slightly non-random permutations

Influenced by Granville’s “Anatomy of integers and permutations” (already a play, soon to be a graphic novel) I had always thought as follows:  a polynomial of degree n over a finite field F_q gives rise to a permutation in S_n, at least up to conjugacy; namely, the one induced by Frobenius acting on the roots.  So the distribution of the degrees of irreducible factors of a random polynomial should mimic the distribution of cycle lengths of a random permutation, on some kind of equidistribution grounds.

But it’s not quite right.  For instance, the probability that a permutation is an n-cycle is 1/n, on the nose.

But the probability that a random squarefree polynomial is irreducible is about (1/n)(1-1/q)^{-1}.

The probability that a random polynomial, with no assumption of squarefreeness, is irreducible, is again about 1/n, the “right answer.”  But a random polynomial which may have repeated factors doesn’t really have an action of Frobenius on the roots — or at least it’s the space of squarefree monics, not the space of all monics, that literally has an etale S_n-cover.

Similarly:  a random polynomial has an average of 1 linear factor, just as a random permutation has an average of 1 fixed point, but a random squarefree polynomial has slightly fewer linear factors on average, namely (1+1/q)^{-1}.



Tagged , ,
%d bloggers like this: