Previously I mentioned very briefly Granville’s *The Anatomy of Integers and Permutations*, which explores an analogy between prime factorizations of integers and cycle decompositions of permutations. Today’s post is a record of the observation that this analogy factors through an analogy to prime factorizations of polynomials over finite fields in the following sense.

**Theorem:** Let be a prime power, let be a positive integer, and consider the distribution of irreducible factors of degree in a random monic polynomial of degree over . Then, as , this distribution is asymptotically the distribution of cycles of length in a random permutation of elements.

One can even name what this random permutation ought to be: namely, it is the Frobenius map acting on the roots of a random polynomial , whose cycles of length are precisely the factors of degree of .

Combined with our previous result, we conclude that as (with tending to infinity sufficiently quickly relative to ), the distribution of irreducible factors of degree is asymptotically independent Poisson with parameters .

**Proof modulo some analytic details**

By the cyclotomic identity, we have

where the sum runs over all monic polynomials over , the product runs over over all monic irreducible polynomials over , and

is the number of monic irreducible polynomials of degree over . This is Euler product for the zeta function for . To get the results we want we need an analogue for polynomials over finite fields of the exponential formula which keeps track of how many factors of a given degree a polynomial has. Letting denote the number of irreducible factors of degree of , this is given by

.

To get a generating function describing the joint moment generating function of the variables we will also need to divide the terms corresponding to polynomials of degree by the number of such polynomials, which is . This is equivalent to replacing with , which gives

.

We are now in a position to take the limit . We will do so somewhat cavalierly: since as and is fixed, we expect that

as , hence the above generating in some sense approaches

as , at least in the sense that their lower-order terms should match up reasonably well (where “lower-order” depends on ). But this is precisely

by the exponential formula.

**Some comments on Granville’s analogy**

The tripartite analogy between cycle decomposition of permutations, prime factorization of polynomials over a finite field, and prime factorization of integers can be made more specific as follows. There is a lot to say on this subject, but we will content ourselves with two sets of analogies.

First, the following three statements are analogous.

- A random permutation of elements is a -cycle with probability .
- A random monic polynomial of degree over is irreducible with probability asymptotically (as ).
- An integer of size approximately is prime with probability approximately (the prime number theorem).

This suggests that the correct analogue of the degree of a positive integer is , an idea which is also suggested by the fact that the norm of a polynomial of degree over is , since this is the size of , whereas the norm of a positive integer is .

Second, the following three statements are analogous.

- The distribution of cycles of length of a random permutation of elements is asymptotically (as ) independent Poisson with parameters .
- The distribution of irreducible factors of degree of a random monic polynomial over of degree is asymptotically (as with growing sufficiently fast relative to ) independent Poisson with parameters .
- The distribution of prime factors in the intervals of a random integer in the interval is asymptotically (as ) independent Poisson with parameters asymptotic to the sequence .

The third statement in this analogy is false as stated; for example, the distribution of prime factors in the interval is asymptotically geometric, not Poisson. It may be true if one takes in addition to in a suitable way while throwing out small primes in a way dependent on and while changing “independent Poisson” to “independent asymptotically Poisson,” where this second use of “asymptotically” depends on .

I offer as weak evidence the following heuristic calculation. First, the probability that a large positive integer is divisible by some is . If is a random variable which takes on non-negative integer values, then a straightforward telescoping argument shows that

.

If is the exponent of a prime in the prime factorization of , then heuristically , so

.

There is a well-known asymptotic for the sum of the reciprocals of the primes which implies that

and consequently the expected number of prime factors (counted with multiplicity) in the interval of a large positive integer is heuristically asymptotically .

(**Edit, 11/11/12:**) The heuristic calculation can be taken further as follows. Letting denote the random variable describing the exponent of in a random prime factorization, we have heuristically and therefore heuristically the moment generating function

.

For prime factorizations of large positive integers we expect the variables to heuristically be asymptotically independent, so heuristically their sum has moment generating function

.

By the PNT, there are approximately primes in this interval. Let us blithely pretend that they all have absolute value approximately , because this is somewhere between and and gives the expected value we computed above. Then we are reduced to a calculation very similar to the calculation over finite fields. Namely, we get a moment generating function

and as this is asymptotic to

which is the moment generating function of a Poisson random variable with parameter as expected.

on November 11, 2012 at 8:55 am |JSEOne relevant reference for this stuff:

http://www.ams.org/notices/199708/tavare.pdf

In fact it gets even more fun when you hold q fixed and just let n go to infinity — see e.g.

http://www.cmb.usc.edu/people/stavare/STpapers-pdf/ABT93.pdf

I blogged a while ago about how you can think of the problem of computing the probability that a random polynomial over F_q is squarefree as a question about the cohomology of the braid group (not, of course, the easiest way to solve that problem!) In the same way, these questions about short cycles of random polynomials over F_q have to do with the cohomology of the _pure_ braid group, and the fact that the short cycles approach a limiting joint distribution (even with fixed q) has to do with the fact that that cohomology is “finitely generated as an FI-module” in the sense of the stuff that Tom Church, Benson Farb and I are working on. Happy to talk about this more! (but probably not in the somewhat constrained venue of blog comment box…)

on November 11, 2012 at 1:39 pm |Qiaochu YuanThanks for the references! I’ve read those blog posts and had some vague suspicion that they might be relevant. Can you elaborate on the relationship to the pure braid group? The variety this comment suggests is relevant seems to be, say, the complement of the locus where the discriminant vanishes in , but I’m not sure what this has to do with random polynomials that aren’t necessarily squarefree.

on November 11, 2012 at 5:08 pm |JSEBriefly: a question like “how many quadratic factors does the average squarefree degree-n polynomial have?” can be expressed in terms of the cohomology of a certain local system on the configuration space of n points in the affine line. These local systems are all representations of the fundamental group of configuration space (i.e. the braid group on n strands) which factor through the map from the braid group to S_n, whose kernel is the pure braid group (which here is manifested as the fundamental group of the space of ORDERED configurations, which covers the usual configuration space with Galois groups S_n.) This means that the statistics you want can be computed from the cohomology of the ordered configuration space (= cohomology of pure braid group) but you need to know what that cohomology is not just as a vector space but as a representation of S_n. (You need to know how Frobenius acts too but in this case it’s not hard to show that everything in sight is Tate type.) Anyway, this last thing is exactly the kind of situation contemplated in the FI-module papers.

But let me emphasize that this is an unnecessarily difficult way to obtain statements like the ones you prove in the post! I’m more saying “this is where these statements fit in to a stable cohomology story” than “this is how you should prove those statements.”

on November 11, 2012 at 5:16 pm |Qiaochu YuanInteresting. Can you tell a similar story for polynomials that aren’t squarefree?