# Tag Archives: hilbert irreducibility

## On van der Waerden’s Conjecture

Recently1, Manjul Bhargava uploaded his paper Galois groups of random integer polynomials and van der Waerden’s Conjecture to the arXiv. The primary result of this paper is to prove van der Waerden’s conjecture that the number of polynomials with “small” Galois group is “small”.

Improving the bounds towards this conjecture was one of the purposes of my recent paper with Anderson, Gafni, Lemke Oliver, Shakan, and Zhang (accepted to IMRN; arXiv preprint; previous discussion on this site). I’ll refer to this paper as AGLDLOSZ2.

For $H \geq 2$, let $E _n(H)$ count the number of monic integer polynomials $f(x) = x^n + a _1 x^{n-1} + \cdots + a _n$ of degree $n$ with $\lvert a _i \rvert \leq H$, and whose Galois group is not the full Galois group $S _n$. Classical reasoning due to Hilbert shows that $E _n(H) = o(H^n)$, sometimes phrased as indicating that one hundred percent of monic polynomials are irreducible and have Galois group $S _n$.

Van der Waerden’s conjecture concerns improving this count. Improvements using varied techniques and ideas have appeared over the years. Prior to the paper of Bhargava, the best record was held by my collaborators and me in AGLDLOSZ, when we showed that $$E _n(H) = O(H^{n – \frac{2}{3} + \frac{2}{3n + 3} + \epsilon}).$$ But now Bhargava proves the conjecture outright, proving that $$E _n(H) = O(H^{n – 1}).$$

This is a remarkable improvement and a very good result!

As in AGLDLOSZ, Bhargava studies the problem with a mixture algebraic techniques and Fourier analysis. Let $V(\mathbb{F} _p)$ denote the space of monic degree $n$ (which I keep implicit in the notation) polynomials over $\mathbb{F} _p$. For any complex function $\psi _p$ on $V(\mathbb{F} _p)$, define its Fourier transform $\widehat{\psi} _p$ by $$\widehat{\psi} _p(x) = \frac{1}{p^n} \sum _{g \in V^*(\mathbb{F} _p)} \psi _p(g) \exp\left( \frac{2\pi i \langle f, g \rangle}{p} \right).$$

We should think of $\psi _p$ as standing for a characteristic function of some appropriate set $S \subset V(\mathbb{F} _p)$. If $\phi$ is a Schwarz function approximating the characteristic function of $[-1, 1]^n$, then Poisson summation gives $$\sum _{f \in V(\mathbb{Z})} \phi(f/H) \psi _p(f) = H^n \sum _{g \in V^*(\mathbb{Z})} \widehat{\phi}(gH/p) \widehat{psi} _p(g). \tag{1}$$ For reasonable $\phi$, the left hand side of $(1)$ gives a good upper bound for the number of elements projecting to $S$ from the polynomial box $[-H, H]^n$. As $\phi$ is Schwarz, we should expect the rapid decay of $\widehat{\phi}$ to rapidly bound the error term on the right hand side by $\max \lvert \widehat{\psi} _p(g) \rvert$ times the size of the box $H^n$, with a possible main term coming from the $g = 0$ term.

In AGLDLOSZ, we used precisely this Fourier setup in a modified form of Selberg’s sieve. We focused on counting polynomials $f$ whose Galois group was a subgroup of $A _n$, and we chose $\psi _p$ to be roughly an indicator function that $f (\bmod p)$ had splitting type mod $p$ that was compatible with Galois group $A _n$. (Actually, we were sieving the incompatible elements out, but this is unimportant). The limit of our result was in understanding the size of the error term in $(1)$, which amounts to providing good bounds for the Fourier transform $\widehat{\psi} _p(g)$. For us, we related this error term to general bounds for the Mobius $\mu$ function and applied these general bounds.

In this paper, Bhargava uses more refined indicator functions. Suppose that the polynomial $f$ factors over $\mathbb{F} _p$ as $\prod P _i^{e _i}$, where each $P _i$ is irreducible (and distinct) and the degree of $P _i$ is $f _i$. Then the degree of $f$ is $\sum f _i e _i$ and we can define the index of $f$ mod $p$ as $\sum (e _i – 1) f _i$.

Bhargava roughly considers indicator functions for polynomials having specified index, and shows that for almost any index the corresponding Fourier transform has significant decay. This is roughly the content of Proposition 24 and Corollary 25 (for non-monic polynomials) or Proposition 28 and Corollary 29 (for monic polynomials).

The ideas and methods used in the proofs of Propositions 24 and 28 in particular are very powerful. I think they’re worth meditating over, and I’ll spend more time thinking about them.

To complete the argument, Bhargava then splits up the regions to estimate. Note that counting polynomials and counting the number fields generated by those polynomials are very similar; here, we count the number fields. Using a result of Lemke Oliver and Thorne, it is possible to bound the number of polynomials leading to number fields with “small” absolute discriminant and “small” product of ramified primes. If the product of ramified primes is “small” but the discriminant is “large”, then the index of these polynomials must be large and is thus bounded by his index counts above.

The third case, where the product of the ramified primes is large, takes more work. Bhargava supplies an additional argument using discriminants. In short, one can show that for each ramified prime $p _r$, the source polynomial $f$ must have a triple root or a pair of double roots mod $p _r$. It turns out that this controls the mod $p$ structure of an iterated discriminant, and counting the number of polynomials giving this structure gives a bound $O(H^{n-1 + \epsilon})$. (This is my summary of the bottom paragraphs of pg 22 on the arXiv version).

Further work is needed to remove the $\epsilon$, but this takes small details when compared to the earlier, bigger ideas.