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
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
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
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.
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.