You are currently browsing the tag archive for the ‘permutations’ tag.
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.
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:
- (Prime factorisation) Given a natural number
, one can decompose it into prime factors
(counting multiplicity), and then the multiset
is a partition of
.
- (Cycle decomposition) Given a permutation
on
labels
, one can decompose
into cycles
, and then the multiset
is a partition of
.
- (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.
- 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
.
- 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
.)
- 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
.
- 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:
- 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.
- 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.
- 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:
- (Uniform distribution)
is drawn uniformly at random from the natural numbers in
.
- (Shifted uniform distribution)
is drawn uniformly at random from the natural numbers in
.
- (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
.
Read the rest of this entry »
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.
- For any
, one has
. In particular,
.
- More generally, for any
and
with
, one has
.
- More generally still, for any
and
with
, one has
- 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.)
- For fixed
,
converges in distribution as
to the Poisson distribution of intensity
.
- 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é.)
- One has
.
- More generally, one has
for all natural numbers
.
Recent Comments