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}.

Curious!

6 thoughts on “Random squarefree polynomials and random permutations and slightly non-random permutations”

1. majordomo says:

Jordan you REALLY have to learn about MathML. These equations on your blog are hard (and not to mention irritating) to read.

2. JSE says:

Making things hard to read = they annoy some people and those people don’t read it
Making things hard for me to write = I just don’t write the post, and then nobody reads it

WordPress offers perfectly good LaTeX support; I just don’t like using it, so I usually don’t. I think of a blog post as something like writing e-mail to a friend or colleague; nobody uses MathML for their e-mail, so why do it on the blog?

3. Richard Séguin says:

I found this neither hard nor irritating to read. If you can understand the subject matter at all, you are most likely also fluent writing and reading LaTeX, and if you’re fluent reading LaTeX then reading stuff like this would be second nature.

4. Tom Church says:

I usually don’t have any trouble with reading LaTeX inline, but for some reason I had trouble with the formulas in this post. (And given the paper we’re writing together, you’d hope that I of all people wouldn’t!)

5. NDE says:

Constructions like “1-1/q” can be confusing at first (it looks like 0/q).
Possibly also (1/n)(…)^{-1}, where we might at first want to invert both factors.
To be sure these can still be confusing when TeXed but (1-\frac{1}{q}) can be even harder to read in plain text (and the fraction may be too small for comfort if not displayed).

6. Regarding math in email, I wish someone created an email client that understood LaTex and displayed math properly, and made it as popular as LaTex, arXiv and such at least within the math community…