Cycles of a random permutation, and irreducible factors of a random polynomial

In analytic number theory, there is a well known analogy between the prime factorisation of a large integer, and the cycle decomposition of a large permutation; this analogy is central to the topic of “anatomy of the integers”, as discussed for instance in this survey article of Granville. Consider for instance the following two parallel lists of facts (stated somewhat informally). Firstly, some facts about the prime factorisation of large integers:

• Every positive integer has a prime factorisation

  

  into (not necessarily distinct) primes , which is unique up to rearrangement. Taking logarithms, we obtain a partition

  

  of .

• (Prime number theorem) A randomly selected integer of size will be prime with probability when is large.
• If is a randomly selected large integer of size , and is a randomly selected prime factor of (with each index being chosen with probability ), then is approximately uniformly distributed between and . (See Proposition 9 of this previous blog post.)
• The set of real numbers arising from the prime factorisation of a large random number converges (away from the origin, and in a suitable weak sense) to the Poisson-Dirichlet process in the limit . (See the previously mentioned blog post for a definition of the Poisson-Dirichlet process, and a proof of this claim.)

Now for the facts about the cycle decomposition of large permutations:

• Every permutation has a cycle decomposition

  

  into disjoint cycles , which is unique up to rearrangement, and where we count each fixed point of as a cycle of length . If is the length of the cycle , we obtain a partition

  

  of .

• (Prime number theorem for permutations) A randomly selected permutation of will be an -cycle with probability exactly . (This was noted in this previous blog post.)
• If is a random permutation in , and is a randomly selected cycle of (with each being selected with probability ), then is exactly uniformly distributed on . (See Proposition 8 of this blog post.)
• The set of real numbers arising from the cycle decomposition of a random permutation converges (in a suitable sense) to the Poisson-Dirichlet process in the limit . (Again, see this previous blog post for details.)

See this previous blog post (or the aforementioned article of Granville, or the Notices article of Arratia, Barbour, and Tavaré) for further exploration of the analogy between prime factorisation of integers and cycle decomposition of permutations.

There is however something unsatisfying about the analogy, in that it is not clear why there should be such a kinship between integer prime factorisation and permutation cycle decomposition. It turns out that the situation is clarified if one uses another fundamental analogy in number theory, namely the analogy between integers and polynomials over a finite field , discussed for instance in this previous post; this is the simplest case of the more general function field analogy between number fields and function fields. Just as we restrict attention to positive integers when talking about prime factorisation, it will be reasonable to restrict attention to monic polynomials . We then have another analogous list of facts, proven very similarly to the corresponding list of facts for the integers:

• Every monic polynomial has a factorisation

  

  into irreducible monic polynomials , which is unique up to rearrangement. Taking degrees, we obtain a partition

  

  of .

• (Prime number theorem for polynomials) A randomly selected monic polynomial of degree will be irreducible with probability when is fixed and is large.
• If is a random monic polynomial of degree , and is a random irreducible factor of (with each selected with probability ), then is approximately uniformly distributed in when is fixed and is large.
• The set of real numbers arising from the factorisation of a randomly selected polynomial of degree converges (in a suitable sense) to the Poisson-Dirichlet process when is fixed and is large.

The above list of facts addressed the large limit of the polynomial ring , where the order of the field is held fixed, but the degrees of the polynomials go to infinity. This is the limit that is most closely analogous to the integers . However, there is another interesting asymptotic limit of polynomial rings to consider, namely the large limit where it is now the degree that is held fixed, but the order of the field goes to infinity. Actually to simplify the exposition we will use the slightly more restrictive limit where the characteristic of the field goes to infinity (again keeping the degree fixed), although all of the results proven below for the large limit turn out to be true as well in the large limit.

The large (or large ) limit is technically a different limit than the large limit, but in practice the asymptotic statistics of the two limits often agree quite closely. For instance, here is the prime number theorem in the large limit:

Theorem 1 (Prime number theorem) The probability that a random monic polynomial of degree is irreducible is in the limit where is fixed and the characteristic goes to infinity.

Proof: There are monic polynomials of degree . If is irreducible, then the zeroes of are distinct and lie in the finite field , but do not lie in any proper subfield of that field. Conversely, every element of that does not lie in a proper subfield is the root of a unique monic polynomial in of degree (the minimal polynomial of ). Since the union of all the proper subfields of has size , the total number of irreducible polynomials of degree is thus , and the claim follows.

Remark 2 The above argument and inclusion-exclusion in fact gives the well known exact formula for the number of irreducible monic polynomials of degree .

Now we can give a precise connection between the cycle distribution of a random permutation, and (the large limit of) the irreducible factorisation of a polynomial, giving a (somewhat indirect, but still connected) link between permutation cycle decomposition and integer factorisation:

Theorem 3 The partition of a random monic polynomial of degree converges in distribution to the partition of a random permutation of length , in the limit where is fixed and the characteristic goes to infinity.

We can quickly prove this theorem as follows. We first need a basic fact:

Lemma 4 (Most polynomials square-free in large limit) A random monic polynomial of degree will be square-free with probability when is fixed and (or ) goes to infinity. In a similar spirit, two randomly selected monic polynomials of degree will be coprime with probability if are fixed and or goes to infinity.

Proof: For any polynomial of degree , the probability that is divisible by is at most . Summing over all polynomials of degree , and using the union bound, we see that the probability that is not squarefree is at most , giving the first claim. For the second, observe from the first claim (and the fact that has only a bounded number of factors) that is squarefree with probability , giving the claim.

Now we can prove the theorem. Elementary combinatorics tells us that the probability of a random permutation consisting of cycles of length for , where are nonnegative integers with , is precisely

since there are ways to write a given tuple of cycles in cycle notation in nondecreasing order of length, and ways to select the labels for the cycle notation. On the other hand, by Theorem 1 (and using Lemma 4 to isolate the small number of cases involving repeated factors) the number of monic polynomials of degree that are the product of irreducible polynomials of degree is

which simplifies to

and the claim follows.

This was a fairly short calculation, but it still doesn’t quite explain why there is such a link between the cycle decomposition of permutations and the factorisation of a polynomial. One immediate thought might be to try to link the multiplication structure of permutations in with the multiplication structure of polynomials; however, these structures are too dissimilar to set up a convincing analogy. For instance, the multiplication law on polynomials is abelian and non-invertible, whilst the multiplication law on is (extremely) non-abelian but invertible. Also, the multiplication of a degree and a degree polynomial is a degree polynomial, whereas the group multiplication law on permutations does not take a permutation in and a permutation in and return a permutation in .

I recently found (after some discussions with Ben Green) what I feel to be a satisfying conceptual (as opposed to computational) explanation of this link, which I will place below the fold.

The Poisson-Dirichlet process, and large prime factors of a random number

Define a partition of to be a finite or infinite multiset of real numbers in the interval (that is, an unordered set of real numbers in , possibly with multiplicity) whose total sum is : . For instance, is a partition of . Such partitions arise naturally when trying to decompose a large object into smaller ones, for instance:

1. (Prime factorisation) Given a natural number , one can decompose it into prime factors (counting multiplicity), and then the multiset

   

   is a partition of .

2. (Cycle decomposition) Given a permutation on labels , one can decompose into cycles , and then the multiset

   

   is a partition of .

3. (Normalisation) Given a multiset of positive real numbers whose sum is finite and non-zero, the multiset

   

   is a partition of .

In the spirit of the universality phenomenon, one can ask what is the natural distribution for what a “typical” partition should look like; thus one seeks a natural probability distribution on the space of all partitions, analogous to (say) the gaussian distributions on the real line, or GUE distributions on point processes on the line, and so forth. It turns out that there is one natural such distribution which is related to all three examples above, known as the Poisson-Dirichlet distribution. To describe this distribution, we first have to deal with the problem that it is not immediately obvious how to cleanly parameterise the space of partitions, given that the cardinality of the partition can be finite or infinite, that multiplicity is allowed, and that we would like to identify two partitions that are permutations of each other

One way to proceed is to random partition as a type of point process on the interval , with the constraint that , in which case one can study statistics such as the counting functions

(where the cardinality here counts multiplicity). This can certainly be done, although in the case of the Poisson-Dirichlet process, the formulae for the joint distribution of such counting functions is moderately complicated. Another way to proceed is to order the elements of in decreasing order

with the convention that one pads the sequence by an infinite number of zeroes if is finite; this identifies the space of partitions with an infinite dimensional simplex

However, it turns out that the process of ordering the elements is not “smooth” (basically because functions such as and are not smooth) and the formulae for the joint distribution in the case of the Poisson-Dirichlet process is again complicated.

It turns out that there is a better (or at least “smoother”) way to enumerate the elements of a partition than the ordered method, although it is random rather than deterministic. This procedure (which I learned from this paper of Donnelly and Grimmett) works as follows.

1. Given a partition , let be an element of chosen at random, with each element having a probability of being chosen as (so if occurs with multiplicity , the net probability that is chosen as is actually ). Note that this is well-defined since the elements of sum to .
2. Now suppose is chosen. If is empty, we set all equal to zero and stop. Otherwise, let be an element of chosen at random, with each element having a probability of being chosen as . (For instance, if occurred with some multiplicity in , then can equal with probability .)
3. Now suppose are both chosen. If is empty, we set all equal to zero and stop. Otherwise, let be an element of , with ech element having a probability of being chosen as .
4. We continue this process indefinitely to create elements .

We denote the random sequence formed from a partition in the above manner as the random normalised enumeration of ; this is a random variable in the infinite unit cube , and can be defined recursively by the formula

with drawn randomly from , with each element chosen with probability , except when in which case we instead have

Note that one can recover from any of its random normalised enumerations by the formula

with the convention that one discards any zero elements on the right-hand side. Thus can be viewed as a (stochastic) parameterisation of the space of partitions by the unit cube , which is a simpler domain to work with than the infinite-dimensional simplex mentioned earlier.

Note that this random enumeration procedure can also be adapted to the three models described earlier:

1. Given a natural number , one can randomly enumerate its prime factors by letting each prime factor of be equal to with probability , then once is chosen, let each remaining prime factor of be equal to with probability , and so forth.
2. Given a permutation , one can randomly enumerate its cycles by letting each cycle in be equal to with probability , and once is chosen, let each remaining cycle be equalto with probability , and so forth. Alternatively, one traverse the elements of in random order, then let be the first cycle one encounters when performing this traversal, let be the next cycle (not equal to one encounters when performing this traversal, and so forth.
3. Given a multiset of positive real numbers whose sum is finite, we can randomly enumerate the elements of this sequence by letting each have a probability of being set equal to , and then once is chosen, let each remaining have a probability of being set equal to , and so forth.

We then have the following result:

Proposition 1 (Existence of the Poisson-Dirichlet process) There exists a random partition whose random enumeration has the uniform distribution on , thus are independently and identically distributed copies of the uniform distribution on .

A random partition with this property will be called the Poisson-Dirichlet process. This process, first introduced by Kingman, can be described explicitly using (1) as

where are iid copies of the uniform distribution of , although it is not immediately obvious from this definition that is indeed uniformly distributed on . We prove this proposition below the fold.

An equivalent definition of a Poisson-Dirichlet process is a random partition with the property that

where is a random element of with each having a probability of being equal to , is a uniform variable on that is independent of , and denotes equality of distribution. This can be viewed as a sort of stochastic self-similarity property of : if one randomly removes one element from and rescales, one gets a new copy of .

It turns out that each of the three ways to generate partitions listed above can lead to the Poisson-Dirichlet process, either directly or in a suitable limit. We begin with the third way, namely by normalising a Poisson process to have sum :

Proposition 2 (Poisson-Dirichlet processes via Poisson processes) Let , and let be a Poisson process on with intensity function . Then the sum is almost surely finite, and the normalisation is a Poisson-Dirichlet process.

Again, we prove this proposition below the fold. Now we turn to the second way (a topic, incidentally, that was briefly touched upon in this previous blog post):

Proposition 3 (Large cycles of a typical permutation) For each natural number , let be a permutation drawn uniformly at random from . Then the random partition converges in the limit to a Poisson-Dirichlet process in the following sense: given any fixed sequence of intervals (independent of ), the joint discrete random variable converges in distribution to .

Finally, we turn to the first way:

Proposition 4 (Large prime factors of a typical number) Let , and let be a random natural number chosen according to one of the following three rules:

1. (Uniform distribution) is drawn uniformly at random from the natural numbers in .
2. (Shifted uniform distribution) is drawn uniformly at random from the natural numbers in .
3. (Zeta distribution) Each natural number has a probability of being equal to , where and .

Then converges as to a Poisson-Dirichlet process in the same fashion as in Proposition 3.

The process was first studied by Billingsley (and also later by Knuth-Trabb Pardo and by Vershik, but the formulae were initially rather complicated; the proposition above is due to of Donnelly and Grimmett, although the third case of the proposition is substantially easier and appears in the earlier work of Lloyd. We prove the proposition below the fold.

The previous two propositions suggests an interesting analogy between large random integers and large random permutations; see this ICM article of Vershik and this non-technical article of Granville (which, incidentally, was once adapted into a play) for further discussion.

As a sample application, consider the problem of estimating the number of integers up to which are not divisible by any prime larger than (i.e. they are –smooth), where is a fixed real number. This is essentially (modulo some inessential technicalities concerning the distinction between the intervals and ) the probability that avoids , which by the above theorem converges to the probability that avoids . Below the fold we will show that this function is given by the Dickman function, defined by setting for and for , thus recovering the classical result of Dickman that .

I thank Andrew Granville and Anatoly Vershik for showing me the nice link between prime factors and the Poisson-Dirichlet process. The material here is standard, and (like many of the other notes on this blog) was primarily written for my own benefit, but it may be of interest to some readers. In preparing this article I found this exposition by Kingman to be helpful.

Note: this article will emphasise the computations rather than rigour, and in particular will rely on informal use of infinitesimals to avoid dealing with stochastic calculus or other technicalities. We adopt the convention that we will neglect higher order terms in infinitesimal calculations, e.g. if is infinitesimal then we will abbreviate simply as .

The number of cycles in a random permutation

Let be a natural number, and let be a permutation of , drawn uniformly at random. Using the cycle decomposition, one can view as the disjoint union of cycles of varying lengths (from to ). For each , let denote the number of cycles of of length ; thus the are natural number-valued random variables with the constraint

We let be the number of cycles (of arbitrary length); this is another natural number-valued random variable, of size at most .

I recently had need to understand the distribution of the random variables and . As it turns out this is an extremely classical subject, but as an exercise I worked out what I needed using a quite tedious computation involving generating functions that I will not reproduce here. But the resulting identities I got were so nice, that they strongly suggested the existence of elementary bijective (or “double counting”) proofs, in which the identities are proven with a minimum of computation, by interpreting each side of the identity as the cardinality (or probability) of the same quantity (or event), viewed in two different ways. I then found these bijective proofs, which I found to be rather cute; again, these are all extremely classical (closely related, for instance, to Stirling numbers of the first kind), but I thought some readers might be interested in trying to find these proofs themselves as an exercise (and I also wanted a place to write the identities down so I could retrieve them later), so I have listed the identities I found below.

1. For any , one has . In particular, .
2. More generally, for any and with , one has .
3. More generally still, for any and with , one has

   

4. In particular, we have Cauchy’s formula: if , then the probability that for all is precisely . (This in particular leads to a reasonably tractable formula for the joint generating function of the , which is what I initially used to compute everything that I needed, before finding the slicker bijective proofs.)
5. For fixed , converges in distribution as to the Poisson distribution of intensity .
6. More generally, for fixed , converge in joint distribution to independent Poisson distributions of intensity respectively. (A more precise version of this claim can be found in this paper of Arratia and Tavaré.)
7. One has .
8. More generally, one has for all natural numbers .