# A polynomial with a root mod $p$ for every $p$ has a real root

Rodrigo Angelo  Department of Mathematics, Stanford University, Stanford, CA
94305<EMAIL_ADDRESS>and  Max Wenqiang Xu  Department of Mathematics,
Stanford University, Stanford, CA 94305<EMAIL_ADDRESS>
###### Abstract.

We prove that if a polynomial has a root mod $p$ for every large prime $p$,
then it has a real root. As an application, we show that the primes can’t be
covered by finitely many positive definite binary quadratic forms.

##  1\. Introduction

It is known that if an irreducible polynomial has a root mod $p$ for every
prime $p$, then it has a rational root (and is therefore linear) [6]. The
issue is subtler if the irreducibility condition is dropped, and there exist
polynomials e.g.,

(1.1) $\begin{gathered}(x^{2}+1)(x^{2}+2)(x^{2}-2)\leavevmode\nobreak\
\text{and}\\\ (x^{2}+x+1)(x^{3}-2)\end{gathered}$

[2] that have a root mod $p$ at every prime $p$, yet no rational root. We
prove that it is still possible to guarantee a real root in this more general
context:

######  Theorem 1.

Let $f\in\mathbb{Q}[x]$ be a polynomial that has a root mod $p$ for every
large prime $p$. Then $f$ has a real root.

The proof is a simple application of Chebotarev’s density theorem, though the
result doesn’t seem to have been stated in the literature about polynomials
with a root mod $p$ for every $p$ [1, 2, 7]. This result was motivated by a
problem on representing primes with positive definite quadratic forms.

A binary quadratic form is an expression of the form
$f(x,y)=ax^{2}+bxy+cy^{2}\in\mathbb{Z}[x,y]$, and its discriminant is
$-D=b^{2}-4ac$. We call $f$ positive definite if $D>0$, in which case
$f(x,y)>0$ for all $x,y\neq 0$. There is an extensive literature into which
primes can be represented by a form $f$, that is, written as $p=f(m,n)$ for
some integers $m$ and $n$. A necessary condition is that the equation
$f(x,y)\equiv 0\mod p$ needs to have a non-trivial solution. This requires
$-D$ to be a square mod $p$, ruling out half of the primes. In certain cases
(when the class number of the discriminant $-D$ is $1$) this condition is
sufficient, but in general it is not. A great survey on this area can be found
at [3].

A natural task is to try to find quadratic forms that together represent all
the primes. For instance, by breaking down into cases for $p$ mod $8$,
$\\{x^{2}+y^{2},x^{2}+2y^{2},x^{2}-2y^{2}\\}$ together cover all primes. And
there are many other examples. One can ask that whether negative values are
really necessary in the last form, that is, whether it is possible to cover
the primes with only positive definite quadratic forms. The answer to this
question is the following.

######  Theorem 2.

There is no finite set of positive definite binary quadratic forms such that
for every large prime $p$, at least one of the forms has a non-trivial
solution to $f(x,y)\equiv 0\mod p$.

In particular there is no finite set of positive definite binary quadratic
forms together representing all the primes. Will Jagy independently asked this
question on Mathoverflow, and Lucia [5] gave a proof based on Dirichlet’s
theorem and density considerations. We offer a short proof based on our our
main result on polynomials with a root mod $p$ for every $p$.

##  2\. Proofs of Theorem 1 and Theorem 2

To prove Theorem 1, we use the following Lemma. It is for instance a corollary
of an important theorem of Dedekind (see [4, Corollary 2.7]), relating the
factors of a polynomial $f(x)$ reduced mod $p$ and the cycle type of the
action of the Frobenius automorphism of $p$ on the roots of $f$.

######  Lemma 3.

Let $f$ in $\mathbb{Q}[x]$ be a polynomial with complex roots
$\alpha_{1},\cdots,\alpha_{d}$, and let $K\hookrightarrow\mathbb{C}$ be the
splitting field of $f$, and let $p$ be a prime not dividing the discriminant
of $f$. Then the number of roots of $f(x)$ modulo $p$ is equal to the number
of complex roots $\alpha_{i}$ fixed by the Frobenius automorphism of $p$ in
$Gal(K/\mathbb{Q})$.

The Frobenius of $p$ is defined up to conjugation, and because the roots are
conjugate to each other, we simply conjugate the fixed roots of the Frobenius
when it is conjugated, and thus the statement is well-defined.

###### Proof of Theorem 1.

Let $f$ be the polynomial with a root mod $p$ for every $p$, and
$\alpha_{1},\cdots,\alpha_{d}$ be the complex roots of $f$ and $K/\mathbb{Q}$
is the splitting field. We claim that each element $\sigma$ in
$Gal(K/\mathbb{Q})$ fixes some root of $f$. Indeed, for each $\sigma\in
Gal(K/\mathbb{Q})$, by the Chebotarev density theorem[8], there exists a large
prime $p$ with its Frobenius conjugate to $\sigma$. By the assumption that $f$
has a root mod $p$ and Lemma 3, it follows that $\sigma$ fixes some
$\alpha_{i}$. Hence each automorphism of $K/\mathbb{Q}$ must fix some root.
Complex conjugation is one such automorphism, and it therefore fixes some root
of $f$. This implies the existence of a real root, as desired.

In fact one may deduce the stronger statement, that if $f$ has at least $k$
roots mod $p$ for every prime $p$, then $f$ has at least $k$ real roots (since
every automorphism of $K/\mathbb{Q}$ will be forced to fix $k$ roots). Both
polynomials in (1.1) are sharp examples of this stronger statement: the first
having at least $2$ roots mod every prime $p$ (and $2$ real roots), and the
second at least $1$ root mod $p$ (and $1$ real root).

∎

We remark that as the Chebotarev density theorem gives not only a single
prime, but a positive proportion of primes with Frobenius conjugate to
$\sigma$, so the assumption in Theorem 1 that $f$ has a real root mod $p$ for
every large $p$ can be weakened to the assumption that $f$ has a root mod $p$
for a proportion of at least $1-\frac{1}{|Gal(K/\mathbb{Q})|}$ of primes.

###### Proof of Theorem 2.

The equation $f(x,y)=ax^{2}+bxy+cy^{2}\equiv 0\mod p$ having a non-trivial
solution is the same as $at^{2}+bt+c\equiv 0\mod p$ having a root. If the
forms $a_{i}x^{2}+b_{i}xy+c_{i}y^{2}$ cover all primes, the polynomial

$f(t)=\prod_{i=1}^{n}(a_{i}t^{2}+b_{i}t+c_{i})$

has a root mod $p$ for every prime $p$, which would imply by Theorem 1 that
$a_{i}t^{2}+b_{i}t+c_{i}$ has a real root for some $i$, i.e., it can’t be
positive definite. This completes the proof.

∎

Our previous density remark means as well that this polynomial must not have a
root for a proportion of at least $\frac{1}{|Gal(f/\mathbb{Q})|}$, which is at
least $\frac{1}{2^{n}}$ since the splitting field of $f$ is a composite of
quadratic fields. That is, a set of $n$ positive definite quadratic forms must
fail to cover a proportion of least $\frac{1}{2^{n}}$ of prime numbers.

## References

  * [1] D. Berend and Y. Bilu.  Polynomials with roots modulo every integer.  Proc. Amer. Math. Soc., 124(6):1663–1671, 1996.
  * [2] R. Brandl, D. Bubboloni, and I. Hupp.  Polynomials with roots mod $p$ for all primes $p$.  J. Group Theory, 4(2):233–239, 2001.
  * [3] D.A. Cox.  Primes of the form $x^{2}+ny^{2}$.  Pure and Applied Mathematics (Hoboken). John Wiley & Sons, Inc., Hoboken, NJ, second edition, 2013.  Fermat, class field theory, and complex multiplication.
  * [4] V. Dokchitser.  Lecture Notes: Algebraic Number Theory.  URL: http://aaronkychan.github.io/notes/Algebraic%20Number%20Theory.pdf. Last visited on 2022/05/17.
  * [5] Lucia (https://mathoverflow.net/users/38624/lucia).  reference for: no finite set of positive (integer) binary quadratic forms represents all primes.  MathOverflow.  URL:https://mathoverflow.net/q/373903 (version: 2020-10-12).
  * [6] H. Lenstra.  Lecture Notes: The Chebotarev Density Theorem.  URL: https://websites.math.leidenuniv.nl/algebra/Lenstra-Chebotarev.pdf. Last visited on 2022/05/17.
  * [7] J. Sonn.  Polynomials with roots in $\mathbb{Q}_{p}$ for all $p$.  Proc. Amer. Math. Soc., 136(6):1955–1960, 2008.
  * [8] N. Tschebotareff.  Die Bestimmung der Dichtigkeit einer Menge von Primzahlen, welche zu einer gegebenen Substitutionsklasse gehören.  Math. Ann., 95(1):191–228, 1926.