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.