Large Prime Factors of a Quadratic Polynomial

Primes of the form $n^2+1$ highlighted inside of Ulam’s Spiral.

At the International Congress of Mathematicians in 1912, Landau posed four problems about prime numbers that he described as “unattackable at the present state of mathematics.” Landau’s problems include some that you may have heard of before:

Can every even integer greater than two be written as a sum of two primes? (Goldbach’s Conjecture)
Are there infinitely many primes which differ by two? (The Twin Prime Conjecture)
Does the interval $[n^2,(n+1)^2]$ always contain a prime? (Legendre’s Conjecture)
Are there infinitely many primes of the form $n^2+1$ ?

Landau’s decriptor unattackable has withstood the test of time — to this day, none of his conjectures have been resolved. Nevertheless, some interesting progress has occurred over the last century. For a good survey on Landau’s problems, I direct the reader to János Pintz’s article Landau’s problems on primes from 2009.

This post discusses Landau’s fourth problem. More specifically, we will discuss a proxy version of Landau’s problem which replaces the condition “ $n^2+1$ is prime” with the statement “ $n^2+1$ has a prime factor which is relatively large.”

The result we prove is the following:

Theorem: Let $P_x$ denote the largest prime factor of

$\displaystyle \prod_{n \leq x} (n^2+1).$

Then $P_x \gg x \log x$ as $x \to \infty$ .

It follows that the sequence $\{n^2+1:n \in \mathbb{Z}\}$ contains infinitely many terms whose largest prime factor is $\gg n \log n$ . This is a far cry from our goal (that the largest prime factor be $\gg n^2$ ), but one has to start somewhere.

A weak version of this theorem in the form $P_x/x \to \infty$ was first proven by Markov in 1895. Nagell proved that $P_x/x > \log^\epsilon x$ for some $\epsilon > 0$ in 1921. The full log-power would not be obtained until 1952, as a consequence of a stronger and more general result due to Erdős. The first power improvement was due to Hooley (1967), who proved that $\displaystyle P_x \gg x^{1.1}$ as an application of the Selberg sieve. Hooley’s exponent was improved to $1.202468$ by Iwaniec–Deshouillers in 1982.

— BROAD OUTLINE OF THE PROOF —

As in the theorem statement, let $P_x$ denote the largest prime factor of $\prod_{n \leq x} (n^2+1)$ . For each $\ell \geq 1$ , let

$\displaystyle N_x(\ell) = \#\{n \leq x : \ell \mid n^2+1\}.$

The prime $p$ divides $\prod_{n \leq x} (n^2+1)$ with multiplicity equal to $\sum_{\alpha \geq 1} N_x(p^\alpha)$ . (This result should be compared to Legendre’s theorem about the $p$ -adic valuation of $x!$ .) It follows that

$\displaystyle \prod_{\substack{p \leq P_x \\ p^\alpha \leq x^2+1}} p^{N_x(p^\alpha)} = \prod_{n \leq x} (n^2+1) > (x!)^2.$

By Stirling’s approximation, we conclude that

$\displaystyle \sum_{\substack{p \leq P_x \\ p^\alpha \leq x^2+1}} N_x(p^\alpha) \log p > 2x \log x + O(x).$

Our proof proceeds by splitting the sum at left into three terms and estimating the contribution of each term. These terms correspond to:

the contribution of prime powers (which are not themselves prime)
the contribution of “small” primes $p\leq x$
the contribution of “large” primes $p$ in the range $[x,P_x]$

We obtain a contradiction unless the interval $[x,P_x]$ is sufficiently long, and this gives us the lower bound on $P_x$ stated in our theorem.

Before jumping into the three cases above, we present a general lemma about the size of $N_x(\ell)$ which we require multiple times.

Lemma: Let $\rho(\ell)$ denote the number of solutions to the congruence equation $z^2 \equiv -1 \!\! \mod \ell$ . We have

$\displaystyle N_x(\ell) = \frac{x\rho(\ell)}{\ell} + O(\rho(\ell)).$

Proof: We may rewrite $N_x(\ell)$ in the form

$\displaystyle N_x(\ell) = \sum_{\substack{n \leq x \\ n^2 \equiv -1(\ell)}} 1 = \sum_{\substack{0<v\leq \ell \\ v^2\equiv -1(\ell)}} \sum_{\substack{n \leq x \\ n \equiv v(\ell)}} 1 = \sum_{\substack{0<v\leq \ell \\ v^2\equiv -1(\ell)}} \Big(\Big\lfloor \frac{x}{\ell} \Big\rfloor +O(1)\Big)$
$\displaystyle =\rho(\ell) \Big\lfloor \frac{x}{\ell}\Big\rfloor +O(\rho(\ell)) = \frac{x\rho(\ell)}{\ell} + O(\rho(\ell)). \qquad \square$

For further bounds on $\rho(\ell)$ , see the Exercises.

— THE CONTRIBUTION OF PRIME POWERS —

Using our Lemma, we bound the contribution from prime powers by

$\displaystyle \sum_{\substack{\alpha > 1 \\ p^{\alpha} \leq x^2+1}} N_x(p^\alpha) \log p \ll \sum_{\substack{\alpha > 1 \\ p^{\alpha} \leq x^2+1}}\Big( \frac{x}{p^\alpha} \log p + O\left(\rho(p^\alpha) \log p \right)\Big).$

The contribution from the main term is

$\displaystyle x \sum_{\substack{\alpha > 1 \\ p^{\alpha} \leq x^2+1}} \frac{\log p}{p^\alpha} \ll x \sum_{\alpha \geq 2} \sum_{n \geq 2} \frac{\log n}{n^\alpha} = x\sum_{n \geq 2} \frac{\log n}{n(n-1)} \ll x.$

To bound the error term, we first remark that Hensel’s lemma implies that $\rho(p^\alpha) = O(1)$ , uniformly in $p$ and $\alpha$ . The contribution of the error term is therefore no larger than

$\displaystyle \sum_{\substack{\alpha > 1 \\ p^{\alpha} \leq x^2+1}} \log p \ll \psi(x^2+1)-\vartheta(x^2+1)\ll \vartheta(\sqrt{x^2+1}) \ll x,$

where the functions $\vartheta(x)$ and $\psi(x)$ are Chebyshev functions and the final bound follows from the PNT. (One of Chebyshev’s earlier bounds for $\vartheta(x)$ would suffice as well. See here (§2) for one treatment.) The contribution of prime powers is then $O(x)$ , which does not contribute to the overall expected size $2x \log x$ .

— THE CONTRIBUTION OF SMALL PRIMES —

Our next topic is the contribution towards our sum from primes $p \leq x$ . These contribute the term

$\displaystyle \sum_{p \leq x} N_p(x) \log p = \sum_{p \leq x} \frac{x\rho(p)\log p}{p} + O(\log p).$

The contribution of the $O(\log p)$ errors totals $O(\vartheta(x)) = O(x)$ . For the main term, we remark that $\rho(p)$ can be written in terms of the Legendre symbol:

$\displaystyle \rho(p) = \Big(\frac{-1}{p}\Big)+1.$

The contribution from “+1” is

$\displaystyle x \sum_{p \leq x} \frac{\log p}{p} = x \log x +O(x)$

by Mertens’ first theorem on the distribution of primes. To address the contribution from the Legendre symbol, we apply the Bombieri–Vinogradov theorem to prove that

$\displaystyle \sum_{p \leq x} \Big(\frac{-1}{p}\Big) \log p = 2\psi(x;4,1)-2\psi(x;4,3) +O(x^{\frac{1}{2}})= O\left(x^{\frac{1}{2}} \log^5 x\right).$

(The additional $O(\sqrt{x})$ appears because we ignore prime powers.) It follows that

$\displaystyle x \sum_{p \leq x} \Big(\frac{-1}{p}\Big) \frac{\log p }{p} = O\left(x^{\frac{1}{2}} \log^5 x\right)$

by Abel summation. The contribution of the small primes is overall $x \log x + O(x)$ .

— THE CONTRIBUTION OF LARGE PRIMES —

Before continuing further, we remind the reader that our work in the last two sections has produced the estimate

$\displaystyle \sum_{x < p \leq P_x} N_p(x) \log p > x \log x +O(x).$

In this final section, we show that this inequality forces $P_x \gg x \log x$ . As before, we bound the left-hand side by

$\displaystyle \sum_{x < p \leq P_x} \frac{x\rho(p)\log p}{p} + O(\log p).$

The contribution of the O-terms is $O(\vartheta(P_x))=O(P_x)$ . The contribution of the main term is

$\displaystyle \ll \sum_{x < p \leq P_x} \frac{x\log p}{p} = x \left(\log P_x - \log x + O(1)\right),$

again by Mertens’ first theorem. If $P_x =o(x\log x)$ , this last expression is $O(x\log\log x)$ , while the $O(P_x)$ term above is $o(x\log x)$ . This contradicts the inequality at the start of this section and completes the proof of our theorem.

— EXERCISES —

Exercise 1. Let $\omega(\ell)$ denote the number of distinct prime factors of $\ell$ . Show that $\rho(\ell) = O(2^{\omega(\ell)})$ . Hint: Hensel’s Lemma and the Chinese Remainder Theorem.