Tag Archives: polynomials

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 , ,

Motivic puzzle: the moduli space of squarefree polynomials

As I’ve mentioned before, the number of squarefree monic polynomials of degree n in F_q[t] is exactly q^n – q^{n-1}.

I explained in the earlier post how to interpret this fact in terms of the cohomology of the braid group.  But one can also ask whether this identity has a motivic interpretation.  Namely:  let U be the variety over Q parametrizing monic squarefree polynomials of degree d.  So U is a nice open subvariety of affine n-space.  Now the identity of point-counts above suggests the question:

Question: Is there an identity [U] = [A^n] – [A^{n-1}] in the ring of motives K_0(Var/Q)?

I asked Loeser, who seemed to feel the answer was likely yes, and pointed out to me that one could also ask whether the two classes were identical in the localization K_0(Var/Q)[1/L], where L is the class of A^1.  Are these questions different?  That is, is there any nontrivial kernel in the natural map K_0(Var/Q) -> K_0(Var/Q)[1/L]?  This too is apparently unknown.

Here, I’ll start you off by giving a positive answer in the easy case n=2!  Then the monic polynomials are parametrized by A^2, where (b,c) corresponds to the polynomial x^2 + bx + c.  The non-squarefree locus (i.e. the locus of vanishing of the discriminant) consists of solutions to b^2 – 4c = 0; the projection to c is an isomorphism to A^1 over Q.  So in this case the identity is indeed correct.

Update:  I totally forgot that Mike Zieve sent me a one-line argument a few months back for the identity |U(F_q)| = q^n – q^{n-1} which is in fact a proof of the motivic identity as well!  Here it is, in my paraphrase.

Write U_e for the subvariety of U consisting of degree-d polynomials of the form a(x)b(x)^2, with a,b monic, a squarefree, and b of degree e.  Then U is the union of U_e as e ranges from 1 to d/2.  Note that the factorisation as ab^2 is unique; i.e, U_e is naturally identified with {monic squarefree polynomials of degree d-2e} x {monic polynomials of degree e.}

Now let V be the space of all polynomials (not necessarily monic) of degree d-2, so that [V] = [A^{n-1}] – [A^{n-2}].  Let V_e be the space of polynomials which factor as c(x)d(x)^2, with d(x) having degree e-1.  Then V is the union of V_e as e ranges from 1 to d/2.

Now there is a map from U_e to V_e which sends a(x)b(x)^2 to a(x)(b(x) – b(0))^2, and one checks that this induces an isomorphism between V_e x A^1 and U_e, done.

But actually, now that I think of it, Mike’s observation allows you to get the motivic identity even without writing down the map above:  if we write U^d_e for the space of monic squarefrees of degree d in stratum e, then U^d_e = U_{d-2e} \times \mathbf{A}^e, and then one can easily compute the class U^d_0 by induction.

Tagged , , ,
%d bloggers like this: