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 always contain a prime? (Legendre’s Conjecture)
- Are there infinitely many primes of the form ?
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 “ is prime” with the statement “ has a prime factor which is relatively large.”
The result we prove is the following:
Theorem: Let denote the largest prime factor of
Then as .
It follows that the sequence contains infinitely many terms whose largest prime factor is . This is a far cry from our goal (that the largest prime factor be ), but one has to start somewhere.
A weak version of this theorem in the form was first proven by Markov in 1895. Nagell proved that for some 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 as an application of the Selberg sieve. Hooley’s exponent was improved to by Iwaniec–Deshouillers in 1982.
— BROAD OUTLINE OF THE PROOF —
As in the theorem statement, let denote the largest prime factor of . For each , let
The prime divides with multiplicity equal to . (This result should be compared to Legendre’s theorem about the -adic valuation of .) It follows that
By Stirling’s approximation, we conclude that
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
- the contribution of “large” primes in the range
We obtain a contradiction unless the interval is sufficiently long, and this gives us the lower bound on stated in our theorem.
Before jumping into the three cases above, we present a general lemma about the size of which we require multiple times.
Lemma: Let denote the number of solutions to the congruence equation . We have
Proof: We may rewrite in the form
For further bounds on , see the Exercises.
— THE CONTRIBUTION OF PRIME POWERS —
Using our Lemma, we bound the contribution from prime powers by
The contribution from the main term is
To bound the error term, we first remark that Hensel’s lemma implies that , uniformly in and . The contribution of the error term is therefore no larger than
where the functions and are Chebyshev functions and the final bound follows from the PNT. (One of Chebyshev’s earlier bounds for would suffice as well. See here (§2) for one treatment.) The contribution of prime powers is then , which does not contribute to the overall expected size .
— THE CONTRIBUTION OF SMALL PRIMES —
Our next topic is the contribution towards our sum from primes . These contribute the term
The contribution of the errors totals . For the main term, we remark that can be written in terms of the Legendre symbol:
The contribution from “+1” is
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
(The additional appears because we ignore prime powers.) It follows that
by Abel summation. The contribution of the small primes is overall .
— THE CONTRIBUTION OF LARGE PRIMES —
Before continuing further, we remind the reader that our work in the last two sections has produced the estimate
In this final section, we show that this inequality forces . As before, we bound the left-hand side by
The contribution of the O-terms is . The contribution of the main term is
again by Mertens’ first theorem. If , this last expression is , while the term above is . This contradicts the inequality at the start of this section and completes the proof of our theorem.
— EXERCISES —
Exercise 1. Let denote the number of distinct prime factors of . Show that . Hint: Hensel’s Lemma and the Chinese Remainder Theorem.
Exercise 2. Compute the constant
to ten decimal places. Can you find a closed form?
Exercise 3. Make the O-dependence explicit where needed in order to find an explicit such that as .