This post reports on some progress Gady Kozma and I have done recently on the problem of the irreducibility of random polynomials.
The main object of study is a random polynomial; i.e.,
,
where
are random variables. In general we assume that the
are iid. Perhaps the most interesting example is when
with probabilities
. Here is how the roots look like:

The roots of polynomials with plus-minus 1 coefficients as illustrated by Sam Derbyshire
There are four types of classical questions on these polynomials:
- How many real roots
has? Here there is a huge body of literature starting with the classical works of Bloch-Pòlya, Offord-Littlewood, Kac, and many many more. (On average there are about
real roots, for
with mean zero. See the introduction in here for a nice historical review.)
- How the complex roots distribute? We refer to the work of Odlyzko-Poonen and to here for the above and many more beautiful illustrations.
- The universality question: How the answers to the above questions depend on the actual distribution of the
.
If the
, then a question of irreducibility over
arises.
4. Is
irreducible whp?
Here we should stress that the assumption
is obviously necessary. One of the most exciting problems in this field is:
Conjecture (Odlyzko-Poonen): Let
be iid random variables taking the values
with equal probabilities expect
. Then
.
This conjecture is open. In fact, I got familiarized with these type of questions by some guy on the street who asked about irreducibly whp in the
model.
The best lower bound is due to Konyagin:
Theorem 1 (Konyagin): In the setting of the conjecture,
.
Here we use the notation
if there exists an absolute constant
such that
.
Even if one takes the easier problem when the coefficients are allowed to take values in a bigger fixed set, no result was known. Recently, Gady Kozma and I uploaded to the arXiv a paper, in which we prove a Odlyzko-Poonen type conjecture, for
taking the values
.
Theorem 2 (LBS-Kozma): Let
be an integer divisible by at least
primes; the smallest being
. Assume that the
-s are iid random variables taking values uniformly in
. Then

(as
).
In fact, we just need the coefficients to distribute uniformly modulo
and, of course, that
.
In fact, we show that
is very irreducible. For this we recall that for a polynomial with integer coefficients one attaches a Galois group: If
are the complex roots of
(with multiplicity), and if
is the minimal subfield of
containing the
-s, then the Galois group is defined as the group of field automorphisms of
:
.
An element
is determined by its action on the
since every element in
is a polynomial expression in the
. So we have an embedding

which is well defined up to reordering of the roots; i.e., up to conjugation in
. So from now on we consider
as a subgroup of
.
Galois theory connects arithmetic properties of
with group theoretical properties of
, and the most basic one is that
is transitive if and only if
is irreducible.
The property of
being doubly transitive (i.e., acting transitively on the set of pairs
with
) translates to the property that
is irreducible over
and
is irreducible over
. One may continue like this for
-transitive, and so on. However, by the classification of finite simple groups, this ends in
steps, since a
-transitive group is either
or
in which case the group is either
or
-transitive, respectively. (We remarks that with four exceptions
we in fact can be done in
steps). We prove
Theorem 3 (LBS-Kozma): Let
be an integer divisible by at least
primes; the smallest being
. Assume that the
-s are iid random variables taking values uniformly in
. Then

(as
).
Large box model
We start by an easier model which we call the large box model. In this model, we fix the degree of
, and we choose the
to vary uniformly in
, where now
. The study of this model goes back to Van der Waerden, who proved in the 1930s that
.
The heuristic idea (which we give for irreducibility, for simplicity) is that
,
and the right-hand-side events are roughly independent when
is much bigger than
, and so we have

where in the last equality we have used the prime polynomial theorem. So, if this estimation is ok for a set primes which grows with
, we get that most polynomials are irreducible.
Van der Waerden’s bound was improved to
in the 1960s by Gallagher who applied the large sieve inequality and to
by Dietmann in 2012. In 2015, Rivin gave an elementary argument which gives the nearly optimal bound of
. (The lower bound
is very easy.)
Let me present the argument in the irreducibility setting : A very naive approach is to say that for 
.
Since there are
monic
-s modulo
and
monic
-s modulo
we get the bound
.
We recover the trivial bound, which is not very helpful 😦 However, if we just condition on the first coefficients
of
and noting that
, so
, we would already get the power saving we aim for. Indeed, putting 

Here we used the classical result in number theory that the average value of
in the interval
is
.
Noting that
is reducible if and only if
,
for some
, we conclude that

with absolute implied constant.
One may see that this bound does not help in the restricted coefficient model discussed above, as it tends to
with
.
However, it gives a
coefficient result in the easier case when the number of variables is
:
Theorem (LBS-Kozma): Let
be a random bivariate polynomial with iid coefficients taking the values
uniformly. Then

as
.
The crux of the proof is specializing
, which essentially reduces to the large box model. This was generalized by Chern to more general fixed sets of coefficients, see here.
Restricted coefficient model
Ideas in the proof of Theorem 1
Going back to the restricted coefficients model, we now explain the main tools/steps in the proof of Theorem 2. We always assume that
is a random polynomial with iid coefficients taking the values
, uniformly (unless explicitly stated otherwise).
It will be convenient to introduce a piece of terminology: An event on a random polynomial
holds a.s. (almost surely) if the probability for it to hold is
, as
.
Our first ingredient is that
A.s., the degrees of
are
, for some
.
In fact, Konyagin, while proving Theorem 1, proved the above with
(he considered the model of
, but his argument carries over to this model too). We will not need such a strong bound on
. To get a flavor of the tools in the proof we show that a random
-coefficient polynomial has no linear factors, a.s.:
A linear factor corresponds to a rational root, which by the rational root theorem must be
. The probability that
is a root is the same as the probability that a length
random walk on the line will come back to the starting point, which is
. So a.s.
has no linear factor.
Using the first ingredient we may reduce the proof of Theorem 1 to proving
.
Indeed, by the first case and neglecting events that a.s. do not occur,

The next thing we need relates to the anatomy of the polynomials. Consider the space
.
of partitions of
. We have two probabilities measures on
coming from
the set of degree-
monic polynomials with coefficients in the finite field
and from
, and are given respectively by

Since we have an exact formula for the number of primes of each degree (the prime polynomial theorem) both these probabilities have formulas, see Arratia, Barbour and Tavaré for an extensive study on the relations of the two probability functions. In particular, it is not very difficult to show that
with absolute constant that is independent on
(and funny enough this gives a new proof of the derangement problem).
However in our case
. For such small
there are events, coming from the small
-s, for which the respective probabilities are not close (e.g. compare the probabilities of the event
). The next ingredient is to show that if an event
is invariant to changing
for
, then
(*)
Dimitris Koukoulopoulos suggested a way to directly work with polynomials instead of going through permutations. This will be discussed elsewhere.
Since our
has coefficients that are uniform modulo
, when we reduce modulo each of the primes
we get
-independent uniform polynomial (this is a consequence of the Chinese remainder theorem). This consideration combined with the fact that the reductions of
modulo
are independent from each other and each of them is uniform, reduce the proof to showing
for every
, the probability that there is
for which four iid uniform random permutations has invariant set of size
is
.
This was shown (essentially) by Pemantle-Peres-Rivin with the bound
. This does not hold for three random permutations as was shown by Eberhard, Ford and Green. This completes the steps in the proof.
Galois group
Ideas in Proof of Theorem 3
Now we know that a.s. a random polynomial is irreducible, and in particular it has a transitive Galois group. To get that the Galois group contains the alternating group, we follow Łuczak and Pyber who proved that a.s. a random permutation is contained in no transitive subgroup other than
or
. The difference of what is needed for our theorem, is that we have a random permutation only up to a small perturbation:
Let
be a random uniform permutation and let
be sufficiently small (in fact
suffices). Then a.s. there exists no transitive group
that contains a permutation that can be get from changing
by cycles of length
.
The need for perturbation comes from two sources. The first is that we can from (*). The second one comes from lifting the Frobenius.
To be more precise, write
for
modulo
. If
has
prime factors of degree
and it is squarefree, then the Frobenius acts on the roots of
has a permutation with
cycles of length
, and this action may be lifted to an element of
.
However, if
is not squarefree, this doesn’t work as simple. There exists a unique factorization
with
squarefull,
squarefree, and
. Then, the roots of
and the roots of
each are invariant set under the action of the Frobenius. Now we can lift the Frobenius to an element
, so that
acts the same on the set of liftings of the roots of
. This means that, up to the perturbation of the size of
, the element
is uniform. Now, we know that a.s.
, and so we get a random element up to perturbation as needed.