# Landau's problems

At the 1912 International Congress of Mathematicians, Edmund Landau listed four basic problems about prime numbers. These problems were characterised in his speech as "unattackable at the present state of mathematics" and are now known as Landau's problems. They are as follows:

1. Goldbach's conjecture: Can every even integer greater than 2 be written as the sum of two primes?
2. Twin prime conjecture: Are there infinitely many primes p such that p + 2 is prime?
3. Legendre's conjecture: Does there always exist at least one prime between consecutive perfect squares?
4. Are there infinitely many primes p such that p − 1 is a perfect square? In other words: Are there infinitely many primes of the form n2 + 1?

As of June 2024, all four problems are unresolved.

## Progress toward solutions

### Goldbach's conjecture

Goldbach's weak conjecture, every odd number greater than 5 can be expressed as the sum of three primes, is a consequence of Goldbach's conjecture. Ivan Vinogradov proved it for large enough n (Vinogradov's theorem) in 1937,[1] and Harald Helfgott extended this to a full proof of Goldbach's weak conjecture in 2013.[2][3][4]

Chen's theorem, another weakening of Goldbach's conjecture, proves that for all sufficiently large n, ${\displaystyle 2n=p+q}$ where p is prime and q is either prime or semiprime.[note 1] Bordignon, Johnston, and Starichkova,[5] correcting and improving on Yamada,[6] proved an explicit version of Chen's theorem: every even number greater than ${\displaystyle e^{e^{34.5}}\approx 4.2\cdot 10^{417776432441823}}$ is the sum of a prime and a product of at most two primes. Bordignon and Starichkova[7] reduce this to ${\displaystyle e^{e^{15.85}}\approx 3.6\cdot 10^{3321634}}$ assuming the Generalized Riemann hypothesis (GRH) for Dirichlet L-functions. Johnson and Starichkova give a version working for all n >= 4 at the cost of using a number which is the product of at most 369 primes rather than a prime or semiprime; under GRH they improve 369 to 33.[8]

Montgomery and Vaughan showed that the exceptional set of even numbers not expressible as the sum of two primes has a density zero, although the set is not proven to be finite.[9] The best current bounds on the exceptional set is ${\displaystyle E(x) (for large enough x) due to Pintz,[10][11] and ${\displaystyle E(x)\ll x^{0.5}\log ^{3}x}$ under RH, due to Goldston.[12]

Linnik proved that large enough even numbers could be expressed as the sum of two primes and some (ineffective) constant K of powers of 2.[13] Following many advances (see Pintz[14] for an overview), Pintz and Ruzsa[15] improved this to K = 8. Assuming the GRH, this can be improved to K = 7.[16]

### Twin prime conjecture

Yitang Zhang showed[17] that there are infinitely many prime pairs with gap bounded by 70 million, and this result has been improved to gaps of length 246 by a collaborative effort of the Polymath Project.[18] Under the generalized Elliott–Halberstam conjecture this was improved to 6, extending earlier work by Maynard[19] and Goldston, Pintz and Yıldırım.[20]

Chen showed that there are infinitely many primes p (later called Chen primes) such that p + 2 is either a prime or a semiprime.

### Legendre's conjecture

It suffices to check that each prime gap starting at p is smaller than ${\displaystyle 2{\sqrt {p}}}$. A table of maximal prime gaps shows that the conjecture holds to 264 ≈ 1.8×1019.[21] A counterexample near that size would require a prime gap a hundred million times the size of the average gap.

Järviniemi,[22] improving on Heath-Brown[23] and Matomäki,[24] shows that there are at most ${\displaystyle x^{7/100+\varepsilon }}$ exceptional primes followed by gaps larger than ${\displaystyle {\sqrt {2p}}}$; in particular,

${\displaystyle \sum _{\stackrel {p_{n+1}-p_{n}>{\sqrt {p_{n}}}^{1/2}}{p_{n}\leq x}}p_{n+1}-p_{n}\ll x^{0.57+\varepsilon }.}$

A result due to Ingham shows that there is a prime between ${\displaystyle n^{3}}$ and ${\displaystyle (n+1)^{3}}$ for every large enough n.[25]

### Near-square primes

Landau's fourth problem asked whether there are infinitely many primes which are of the form ${\displaystyle p=n^{2}+1}$ for integer n. (The list of known primes of this form is A002496.) The existence of infinitely many such primes would follow as a consequence of other number-theoretic conjectures such as the Bunyakovsky conjecture and Bateman–Horn conjecture. As of 2023, this problem is open.

One example of near-square primes are Fermat primes. Henryk Iwaniec showed that there are infinitely many numbers of the form ${\displaystyle n^{2}+1}$ with at most two prime factors.[26][27] Ankeny[28] and Kubilius[29] proved that, assuming the extended Riemann hypothesis for L-functions on Hecke characters, there are infinitely many primes of the form ${\displaystyle p=x^{2}+y^{2}}$ with ${\displaystyle y=O(\log p)}$. Landau's conjecture is for the stronger ${\displaystyle y=1}$. The best unconditional result is due to Harman and Lewis[30] and it gives ${\displaystyle y=O(p^{0.119})}$.

Merikoski,[31] improving on previous works,[32][33][34][35][36] showed that there are infinitely many numbers of the form ${\displaystyle n^{2}+1}$ with greatest prime factor at least ${\displaystyle n^{1.279}}$.[note 2] Replacing the exponent with 2 would yield Landau's conjecture.

The Friedlander–Iwaniec theorem shows that infinitely many primes are of the form ${\displaystyle x^{2}+y^{4}}$.[37]

Baier and Zhao[38] prove that there are infinitely many primes of the form ${\displaystyle p=an^{2}+1}$ with ${\displaystyle a; the exponent can be improved to ${\displaystyle 1/2+\varepsilon }$ under the Generalized Riemann Hypothesis for L-functions and to ${\displaystyle \varepsilon }$ under a certain Elliott-Halberstam type hypothesis.

The Brun sieve establishes an upper bound on the density of primes having the form ${\displaystyle p=n^{2}+1}$: there are ${\displaystyle O({\sqrt {x}}/\log x)}$ such primes up to ${\displaystyle x}$. Hence almost all numbers of the form ${\displaystyle n^{2}+1}$ are composite.

## Notes

1. ^ A semiprime is a natural number that is the product of two prime factors.
2. ^ Merikoski gives two conjectures which would improve the exponent to 1.286 or 1.312, respectively.

## References

1. ^ I. M. Vinogradov. Representation of an odd number as a sum of three primes, Doklady Akademii Nauk SSSR, 15 (1937), pp. 291-294.
2. ^ Helfgott, H.A. (2013). "Major arcs for Goldbach's theorem". arXiv:1305.2897 [math.NT].
3. ^ Helfgott, H.A. (2012). "Minor arcs for Goldbach's problem". arXiv:1205.5252 [math.NT].
4. ^ Helfgott, H.A. (2013). "The ternary Goldbach conjecture is true". arXiv:1312.7748 [math.NT].
5. ^ Matteo Bordignon, Daniel R. Johnston, and Valeriia Starichkova, An explicit version of Chen's theorem
6. ^ Yamada, Tomohiro (2015-11-11). "Explicit Chen's theorem". arXiv:1511.03409 [math.NT].
7. ^ Matteo Bordignon, Valeriia Starichkova, An explicit version of Chen's theorem assuming the Generalized Riemann Hypothesis
8. ^ Daniel R. Johnston and Valeriia V. Starichkova, Some explicit results on the sum of a prime and an almost prime (2023)
9. ^ Montgomery, H. L.; Vaughan, R. C. (1975). "The exceptional set in Goldbach's problem" (PDF). Acta Arithmetica. 27: 353–370. doi:10.4064/aa-27-1-353-370.
10. ^
11. ^ http://real.mtak.hu/124681/1/Cikk2020Rivista.pdf
12. ^ D.A. Goldston, On Hardy and Littlewood’s contribution to the Goldbach conjecture. Proceedings of the Amalfi Conference on Analytic Number Theory (Maiori, 1989), pp. 115–155, Univ. Salerno, Salerno, 1992.
13. ^ Yu V Linnik, Prime numbers and powers of two, Trudy Matematicheskogo Instituta imeni VA Steklova 38 (1951), pp. 152-169.
14. ^ János Pintz, Approximations to the Goldbach and twin prime problem and gaps between consecutive primes, Probability and Number Theory (Kanazawa, 2005), Advanced Studies in Pure Mathematics 49, pp. 323–365. Math. Soc. Japan, Tokyo, 2007.
15. ^ Pintz, J.; Ruzsa, I. Z. (July 2020). "On Linnik's approximation to Goldbach's problem. II" (PDF). Acta Mathematica Hungarica. 161 (2): 569–582. doi:10.1007/s10474-020-01077-8. S2CID 225457520.
16. ^ D. R. Heath-Brown and J.-C. Puchta. Integers represented as a sum of primes and powers of two. Asian J. Math., 6(3):535–565, 2002.
17. ^ Yitang Zhang, Bounded gaps between primes, Annals of Mathematics 179 (2014), pp. 1121–1174 from Volume 179 (2014), Issue 3
18. ^ D.H.J. Polymath (2014). "Variants of the Selberg sieve, and bounded intervals containing many primes". Research in the Mathematical Sciences. 1 (12): 12. arXiv:1407.4897. doi:10.1186/s40687-014-0012-7. MR 3373710. S2CID 119699189.
19. ^ J. Maynard (2015), Small gaps between primes. Annals of Mathematics 181(1): 383-413.
20. ^ Alan Goldston, Daniel; Motohashi, Yoichi; Pintz, János; Yalçın Yıldırım, Cem (2006). "Small Gaps between Primes Exist". Proceedings of the Japan Academy, Series A. 82 (4): 61–65. arXiv:math/0505300. doi:10.3792/pjaa.82.61. S2CID 18847478.
21. ^ Dr. Thomas R. Nicely, First occurrence prime gaps
22. ^ Olli Järviniemi, On large differences between consecutive primes, arXiv preprint (2022). arXiv:2212.10965 [math.NT]
23. ^ Heath-Brown, Roger (October 2020). "The Differences Between Consecutive Primes, V". International Mathematics Research Notices. 2021 (22): 17514–17562. arXiv:1906.09555. doi:10.1093/imrn/rnz295.
24. ^ Kaisa Matomäki (2007). "Large differences between consecutive primes". Quarterly Journal of Mathematics. 58 (4): 489–518. doi:10.1093/qmath/ham021..
25. ^ Ingham, A. E. (1937). "On the difference between consecutive primes". Quarterly Journal of Mathematics. 8 (1): 255–266. Bibcode:1937QJMat...8..255I. doi:10.1093/qmath/os-8.1.255.
26. ^ Iwaniec, H. (1978). "Almost-primes represented by quadratic polynomials". Inventiones Mathematicae. 47 (2): 178–188. Bibcode:1978InMat..47..171I. doi:10.1007/BF01578070. S2CID 122656097.
27. ^ Robert J. Lemke Oliver (2012). "Almost-primes represented by quadratic polynomials" (PDF). Acta Arithmetica. 151 (3): 241–261. doi:10.4064/aa151-3-2..
28. ^ N. C. Ankeny, Representations of primes by quadratic forms, Amer. J. Math. 74:4 (1952), pp. 913–919.
29. ^ J. Kubilius, On a problem in the n-dimensional analytic theory of numbers, Vilniaus Valst. Univ. Mokslo Darbai. Mat. Fiz. Chem. Mokslu Ser., 4:5–43, 1955.
30. ^ Harman, G.; Lewis, P. (2001). "Gaussian primes in narrow sectors". Mathematika. 48 (1–2): 119–135. doi:10.1112/S0025579300014388. S2CID 119730332.
31. ^ Merikoski, Jori (2022). "Largest prime factor of ${\displaystyle n^{2}+1}$". Journal of the European Mathematical Society. 25 (4): 1253–1284. arXiv:1908.08816. doi:10.4171/JEMS/1216.
32. ^ de la Bretèche, Régis; Drappeau, Sary (2020), "Niveau de répartition des polynômes quadratiques et crible majorant pour les entiers friables", Journal of the European Mathematical Society, 22 (5): 1577–1624, arXiv:1703.03197, doi:10.4171/JEMS/951, S2CID 146808221
33. ^ Jean-Marc Deshouillers and Henryk Iwaniec, On the greatest prime factor of ${\displaystyle n^{2}+1}$, Annales de l'Institut Fourier 32:4 (1982), pp. 1–11.
34. ^ Hooley, Christopher (July 1967). "On the greatest prime factor of a quadratic polynomial". Acta Mathematica. 117: 281–299. doi:10.1007/BF02395047.
35. ^ J. Todd (1949), "A problem on arc tangent relations", American Mathematical Monthly, 56 (8): 517–528, doi:10.2307/2305526, JSTOR 2305526
36. ^ J. Ivanov, Uber die Primteiler der Zahlen vonder Form A+x^2, Bull. Acad. Sci. St. Petersburg 3 (1895), 361–367.
37. ^ Friedlander, John; Iwaniec, Henryk (1997), "Using a parity-sensitive sieve to count prime values of a polynomial", PNAS, 94 (4): 1054–1058, Bibcode:1997PNAS...94.1054F, doi:10.1073/pnas.94.4.1054, PMC 19742, PMID 11038598.
38. ^ Stephan Baier and Liangyi Zhao, Bombieri-Vinogradov Type Theorem for Sparse Sets of Moduli, Acta Arith., Vol. 125, No. 2, 2006, pp. 187-201. arXiv:math/0602116 [math.NT]