Irreducibility of random polynomials of bounded degree

Irreducibility of random polynomials of bounded degree, Discrete Analysis 2021:7, 16 pp.

This paper contributes to a substantial literature on the subject of random polynomials and their behaviour, considerably generalizing known results that show that under suitable circumstances such polynomials are likely to be irreducible.

There are several natural notions of random polynomial of which two stand out in particular: the “bounded degree model”, where one fixes the degree $d$ and takes coefficients uniformly and independently at random from the set $[-H,H]$, where $H$ tends to infinity, and the “bounded-height model”, which is the same except that this time $H$ is fixed and $d$ tends to infinity. It was shown by van der Waerden in 1936 that the probability of irreducibility tends to 1 in the bounded degree model, and a sharp bound of $1-(1+o(1))C_d/H$ was obtained by Chela in 1963. For the bounded-height model (or even for a height that can grow at a certain controlled rate with the degree) a comparable result was obtained in 2018 by Breuillard and Varju, but this was conditional on suitable versions of the Riemann hypothesis.

More generally, one can look at other distributions: in the bounded degree case, Rivin observed, via a short argument, that if the constant coefficient of a random polynomial has few divisors, then the polynomial is unlikely to be reducible. Since most integers have few divisors, this immediately implied van der Waerden’s result. It also led to results of the following general kind: if the constant coefficient has few divisors and the remaining coefficients are chosen independently at random from a set $S$ that satisfies certain conditions, then the polynomial is irreducible with probability $1-o(1)$.

The proofs of these results relied heavily on the independence of the coefficients, but there is no particular reason to suppose that independence is genuinely important for obtaining irreducibility. The main contribution of this paper is to prove that almost all polynomials are irreducible for a much larger class of distributions, and in particular in several situations where the distributions of the coefficients are not independent. This they do by taking Rivin’s basic idea and building on it.

One of their results has the following consequence. Let $H_0,H_1,\dots,H_{d-1}$ be sets of integers of size at least $H$, and let $g_0,g_1,\dots,g_{d-1}$ be polynomials of bounded degree, where $g_i$ is a polynomial in $i+2$ variables. Let $a_0$ have a bounded number of prime factors, and for $i=1,\dots,d$ let $a_i=g_{i-1}(a_0,a_1,\dots,a_{i-1};t_{i-1})$, where the $t_{i-1}$ are chosen uniformly and independently from the $H_{i-1}$. Then the probability that the polynomial with coefficients $a_0,a_1,\dots,a_d$ is irreducible tends to 1 as $H$ tends to infinity.

Several of the assumptions above can be relaxed: see the paper for details. The main thing to note is that while independence has not entirely disappeared, since the $t_{i-1}$ are independent, the coefficients themselves have strong dependencies. Note also that one cannot hope for too general a result, since one must somehow rule out, in a non-trivial way, distributions that are concentrated on the reducible polynomials. The particular conditions obtained in this paper may at first look slightly technical, but they are satisfied by a number of natural-looking models, such as when the coefficients form a random walk: that is, $a_i=a_{i-1}+t_i$, where the $t_i$ are chosen independently from a set of size $H$. The paper also sheds some light on Rivin’s method, which had previously appeared to be somewhat mysterious.