Landau's Fourth Problem: Primes of the Form n² + 1

Landau's Fourth Problem: Primes of the Form n² + 1

Definitions and mathematical statement

For $x\ge1$, set \[ Q(x)=\#\{n\in{\mathbb{N}}:1\le n\le x,\ n^2+1\text{ is prime}\}. \] The selected conjecture is $Q(x)\to\infty$ as $x\to\infty$, equivalently $\forall B\ \exists n>B$ such that $n^2+1$ is prime. Prime means an integer greater than one having no positive divisors other than one and itself. The problem asks only infinitude, not an asymptotic formula for $Q(x)$, a positive density among integers, or primality for every $n$. In particular, parity restrictions on $n$ do not negate the infinitude formulation.

Formulation and concept references: [S1].

Short English statement

Are there infinitely many primes that exceed a positive integer square by exactly one?

Research attempt

Current frontier.

The infinitude target is weaker than a Bateman--Horn asymptotic, but still concerns primes rather than almost-primes. Iwaniec proved infinitely many values of $n^2+1$ with at most two prime factors counted with multiplicity [E1]. The later treatments explain both the importance of this result and the remaining distinction from primality [E2], [E3]. We do not treat an almost-prime theorem as a solution of [S1]. The attempt below extracts a signed statistic that would convert suitable almost-prime mass into prime mass, and tests why local congruence estimates alone do not control it.

Attack route.

A direct sieve needs information breaking parity. An almost-prime construction might be combined with cancellation of a multiplicative sign, while an analytic approach to the von Mangoldt sum would need genuinely bilinear estimates beyond elementary root counting. We pursue the signed almost-prime route. The required lemma will be stated as a precise estimate on a specified class of weights, rather than as the undefined instruction "improve the sieve."

Attempt.

For squarefree $d$ define \[ \rho(d)=\#\{r\bmod d:r^2+1\equiv0\pmod d\},\qquad A_d(x)=\#\{1\le n\le x:d\mid n^2+1\}. \] Counting each admissible residue separately gives the exact uniform estimate \begin{equation}\label{wsref-0-65-71-31-39-30-3a-6c-6f-63-61-6c} \left|A_d(x)-\frac{\rho(d)}d\lfloor x\rfloor\right|\le\rho(d). \end{equation} The Chinese remainder theorem makes $\rho$ multiplicative on squarefree integers. Moreover $\rho(2)=1$, and for odd primes $p$ it equals $2$ when $p\equiv1\pmod4$ and $0$ when $p\equiv3\pmod4$. The odd-prime assertion follows because the cyclic group ${\mathbb{F}}_p^\times$ contains a square root of $-1$ exactly when $4\mid p-1$, with two roots in that case.

Since $\rho(d)\le\tau(d)$, \[ \sum_{\substack{d\le D\\d\text{ squarefree}}} \left|A_d(x)-\frac{\rho(d)}d\lfloor x\rfloor\right| \le\sum_{d\le D}\tau(d) \le D(1+\log D). \] The last inequality counts pairs $ab\le D$. This proves a useful distribution estimate, but values $n^2+1$ have size roughly $x^2$. A level around $x$ in the parameter $n$ is not distribution to the full size of the represented integers. Nor do these unsigned errors control the parity of the number of prime factors.

Let $\Omega(m)$ count prime factors with multiplicity and $\lambda(m)=(-1)^{\Omega(m)}$. Suppose a construction produces weights \[ 0\le w_x(n)\le1,\qquad w_x(n)=0\text{ unless }1\le n\le x \text{ and }\Omega(n^2+1)\le2. \] Set \[ M_x=\sum_nw_x(n),\qquad L_x=\sum_nw_x(n)\lambda(n^2+1). \] Because $n^2+1>1$, the support consists of primes and two-factor values. Thus we have the identity \begin{equation}\label{wsref-0-65-71-31-39-30-3a-70-61-72-69-74-79} \sum_{\substack{n:\,n^2+1\text{ prime}}}w_x(n)=\frac{M_x-L_x}{2}. \end{equation} There is no sieve error in this formula. In fact $n^2+1$ is never a perfect square for positive $n$, since it lies strictly between $n^2$ and $(n+1)^2$, although the identity would remain valid if prime squares were present.

Conditional extraction lemma. If along an unbounded sequence of $x$ one has $M_x\to\infty$ and, for some fixed $\eta>0$, \begin{equation}\label{wsref-0-65-71-31-39-30-3a-6e-65-65-64-65-64} L_x\le(1-\eta)M_x, \end{equation} then there are infinitely many primes of the form $n^2+1$. Indeed, (eq190:parity) gives a prime weight at least $\eta M_x/2$. If only $B$ such integers existed, the bound $w_x(n)\le1$ would make this weight at most $B$ for every $x$, a contradiction. The upper bound on the weights is essential: unbounded weights could make finitely many primes appear to provide diverging mass.

This suggests combining an Iwaniec-type almost-prime construction with a sign-cancellation estimate. It does not say that the weights in the published proof already satisfy (eq190:needed). They have not been shown to do so here. Choosing the indicator of all two-almost-prime values merely rewrites the problem and leaves the sign estimate untouched. A substantive implementation would specify the sieve weights before observing the primality outcomes and prove a quantitative saving from the all-positive value $L_x=M_x$.

A second attempted simplification is to pre-sieve above $z=(x^2+1)^{1/3}$. Every surviving integer $n^2+1\le x^2+1$ then has at most two prime factors, since three factors exceeding $z$ would be too large. However, proving sufficiently many survivors at that range is itself beyond the elementary estimate (eq190:local); this does not produce a free substitute for Iwaniec's theorem. Even successful survival leaves the signed statistic unresolved.

Stress test.

For any finite set of primes, taking $n$ divisible by their product avoids all of them as divisors of $n^2+1$. This proves there is no obstruction from that finite list, not that any resulting value is prime. Likewise a positive lower bound for $M_x$ can coexist with $L_x=M_x$, when every supported value has exactly two prime factors. The parity identity exposes rather than circumvents that possibility. Averages of $\lambda(m)$ over ordinary integer intervals cannot be transferred without proof to the sparse, weighted quadratic sequence. Exact small-range factorization checks in the script test the identity and local counts only.

Outcome.

Outcome: Conditional reduction. A bounded-weight signed saving (eq190:needed), together with diverging two-almost-prime mass, suffices for the literal infinitude target. Elementary root counting and a complete proof of the extraction step were supplied. The unsolved estimate is the parity-breaking saving on that sparse weighted sequence; no such saving is proved here, and no quantitative asymptotic for prime values is claimed.

Sources

• S1 Weisstein, Eric W. "Landau's Problems." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LandausProblems.html. Catalogue formulation source.
• E1 Henryk Iwaniec, Almost-primes represented by quadratic polynomials, Inventiones Mathematicae 47 $1978$, 171--188, main theorem for $n^2+1$. https://doi.org/10.1007/BF01578070. Research reference; consulted 27 September 2026.
• E2 Robert J. Lemke Oliver, Almost-primes represented by quadratic polynomials, Acta Arithmetica 151$3$ $2012$, 241--261; introduction and quadratic almost-prime results. https://lemkeoliver.github.io/papers/04-Quadratic.pdf. Research reference; consulted 27 September 2026.
• E3 Vishaal Kapoor, Almost-Primes Represented by Quadratic Polynomials, arXiv:1910.02885 $2019$; detailed exposition of Iwaniec's method and its two-prime-factor conclusion. https://arxiv.org/abs/1910.02885. Research reference; consulted 27 September 2026.