# "Halfway" approach to Landau's 4th problem (special case of Bateman-Horn)

Landau's 4th problem asks if $$n^2 + 1$$ is prime for infinitely many $$n \in \Bbb{Z}$$. It is known that $$n^2 + 1$$ can only be divisible by Pythagorean primes, and that for any $$p$$ congruent to $$1 \pmod 4$$, there will be in general 2 solutions to $$x^2 + 1 \equiv 0 \pmod p$$. It's not too hard to use this to show that $$S(N) := \{ n \leq N: n^2 + 1 \text{ is prime } \}$$ satisfies $$|S(N)| = O(N/\log N)$$, and in fact it seems likely that $$S(N) = \Theta(N/\log N)$$ (as Bateman-Horn would imply).

Asymptotically, it seems like sieving out $$2$$ values for "every other" prime (since primes congruent to $$3 \pmod 4$$ will never divide $$n^2 + 1$$) should give about the same asymptotic density of primes in $$n^2 + 1$$, as there are primes in the regular integers. If there's so many of them, what makes this conjecture so resistant, since we end up sieving "about the same" amount of residue classes in each prime?

And what would be the obstruction to taking a "halfway" approach? Specifically:

• only sieve out one of the two square roots of $$-1$$ mod some Pythagorean prime $$p$$ (the bigger one: if $$x_p$$ is the smallest positive integer for which $$x_p^2 + 1 \equiv 0 \pmod p$$, we are sieving out the congruence class $$p - x_p$$. E.g. sieve out by $$3 \pmod 5$$ but not $$2 \pmod 5$$) but over all of $$\Bbb{Z}$$ instead of just $$\Bbb{N}$$

• get a set $$S(N) := \{ n \in \Bbb{Z}: |n| \leq N, n \not \equiv p - x_p \pmod p \}$$ of density $$\Theta(N/\sqrt{\log N})$$

• then make some argument that $$S(N)$$ has to overlap with its reflection $$-S(N) := \{ k \in \Bbb{Z}: -k \in S(N) \}$$ infinitely often?

• I am not sure you understand how sieves work in practice. It is easy to obtain upper bounds using sieves, but it is EXTREMELY difficult to produce lower bounds. Jul 25 '20 at 12:03

In practice, sieves have a hard time producing useful lower bounds for prime counting problems due to the so-called parity problem, a phenomenon that is very poorly understood. The best general "prime producing sieve" is due to Bombieri (though the formulation below is due to Friedlander and Iwaniec in this paper.

The question is phrased as follows: consider a sequence $$\mathcal{A} = (a_n)$$ of positive integers, supported on $$n \in \mathbb{N}$$. Consider the sum

$$\displaystyle A_d(X) = \sum_{\substack{n \leq X \\ d | n}} a_n.$$

We shall assume that $$\mathcal{A}$$ satisfies the following property: that for all $$d \in \mathbb{N}$$ we have

$$\displaystyle A_d(X) = g(d) A_1(X) + R_d(X),$$

where $$g$$ is a multiplicative function satisfying $$0 \leq g(p) < 1$$ for all primes $$p$$.

If our goal is to produce an asymptotic formula for the expression

$$\displaystyle S(X) = \sum_{p \leq X} a_p \log p,$$

where $$p$$ runs over primes, then Bombieri's sieve reduces the question to establishing two estimates:

(1) - Level of distribution: the remainder terms $$R_d(X)$$ satisfies

$$\displaystyle \sum_{d \leq D} \left \lvert R_d(X) \right \rvert \ll_A X(\log X)^{-A}$$

for fixed $$A > 1$$ uniformly in some range $$D \ll X$$, and

(2) - Bilinear sum estimates

$$\displaystyle \sum_m \left \lvert \sum_{\substack{N < n \leq 2N \\ mn \leq X \\ \gcd(m, nP(z)) = 1 }} \beta(n) a_{mn} \right \rvert \leq A_1(X) (\log X)^{-B}$$

for some (large) absolute constant $$B$$ and

$$\displaystyle \beta(n) = \mu(n) \sum_{\substack{c \leq C \\ c|n}} \mu(c)$$

where $$C$$ satisfies

$$\displaystyle 1 \leq C \leq X/D$$

and $$N$$ depends on two additional parameters $$\delta, \Delta$$ satisfying $$\Delta \geq \delta \geq 2$$ as follows:

$$\displaystyle \Delta^{-1} \sqrt{D} < N < \delta^{-1} \sqrt{X}.$$

As a reminder, $$P(z) = \prod_{p < z} p$$, and $$z$$ is to be chosen to be $$2 \leq z \leq \Delta^{\kappa \log \log X}$$ for some small absolute constant $$\kappa$$.

The theorem is that once (1) and (2) are satisfied, then one can evaluate the asymptotic formula for $$S(X)$$.

Trying to apply this to the case when $$a_n = \# \{x \in \mathbb{Z} : n = x^2 + 1\}$$, condition (1) can only be obtained for $$D \ll X^{1/2} \asymp n^{1/2} \asymp x$$, which is not that great (ideally, we'd want $$D$$ to be almost as large as $$X$$). Condition (2) is essentially impossible to verify.

As a measure of how hard the problem is, consider two closely related results due to Friedlander-Iwaniec and Heath-Brown/Li: they considered $$a_n = \#\{(x,y) \in \mathbb{Z}^2 : n = x^2 + y^4\}$$ and $$a_n = \#\{(x,p) \in \mathbb{Z}^2 : n = x^2 + p^4, p \text{ prime}\}$$ respectively. In other words, they added a second variable and restricted it to the set of squares and the set of prime squares respectively. In the case of Landau the second variable is forced to be one (it's essentially equivalent to simply consider it as bounded). Both of these results are at the frontier of what we are able to do. Indeed, even restricting the second variable further to say the set of cubes represents an immense challenge, and whose solution would answer another old question in number theory: does there exist infinitely many elliptic curves defined over $$\mathbb{Q}$$ with prime discriminant?

• I admit to using the word "sieve" very informally in my question and not necessarily meaning sieve theory per se, just measuring the size of a complement set by, for instance, using the tools of analytic number theory such as a Dirichlet series which also contains "only those numbers that don't fall into this residue class modulo Pythagorean primes". Jul 25 '20 at 16:29