I would like to thank Brandon Hanson, Giorgis Petridis, and Kevin Ford for helpful contributions to this post.
A well-known problem of Sárközy is the following.
Conjecture 1: Let be a prime and be the set of squares. Suppose . Then either or .
As the squares are a multiplicative subgroup, it is natural to guess they cannot be written additively as a sumet. Conjecture 1 is in a similar spirit of a long list of conjectures concerning the independence of multiplication and addition, such as the twin prime conjecture, the abc-conjecture, and the sum-product conjecture.
Progress towards Conjecture 1, as of last week, was summarized in this mathoverflow post and this other mathoverflow post (and the papers referenced within). Sárközy proved that if , then
which we recall below. In fact, Shparlinski (in Theorem 7) improved (1) and then later Shkredov showed (in Corollary 2.6)
Brandon Hanson and Giorgis Petridis, utilizing the polynomial method, recently made significant progress towards Conjecture 1.
Theorem 1 (Hanson-Petridis): Suppose . Then
In particular every element of has a unique representation of the form
Their techniques handle the case where is replaced by any nontrivial multiplicative subgroup, but we focus on the squares for simplicity. In particular, if is a prime, then Conjecture 1 is established. This implies Conjecture 1 is true for infinitely many primes, provided there are infinitely many Sophie Germain primes (yet another conjecture based on the independence of multiplication and addition). Making use of (1) we are able to prove this unconditionally. Here is the prime counting function.
Corollary 1: For all but primes less than , Conjecture 1 holds.
Proof: Let be a prime. Suppose with . Then by Theorem 1 and (1), has a divisor between and . By Theorem 6 (followed by Theorem 1 (v)) in Kevin Ford’s work on the distribution of integers with divisors in an given interval, there are at most such primes. Corollary 1 then follows from the prime number theorem.
If , we always have trivial bound
which can be compared to the following bilinear estimate.
Theorem 2: Let be the quadratic character modulo . Then
In particular if , then
The proof of Theorem 2, which we give, is standard Fourier manipulations (see chapter 4 of Tao and Vu for more details). As we will see below, Hanson and Petridis make no use of this perspective.
Proof: The second statement follows from the first as if , then
By Fourier inversion, it is enough to show
Note , and the usual estimate for Gauss sums implies
Combining with (3), it is enough to show
But this follows from Cauchy-Schwarz and Parseval.
Combining (2) and Theorem 2, we see that if , then
Thus Theorem 1 asserts that the lower bound in (4) is the only possibility. We now proceed towards a proof of Theorem 1. The starting point is a classical theorem of Fermat.
Theorem 3 (Fermat): Let . Then if and only if is a root of .
There are many proofs of this elementary fact, for instance it is a quick consequence of Lagrange’s theorem. As a consequence, we have the following.
Corollary 2: Let . Then is a square if and only if is a root to
Proof: Every square is a root of (5) as if for some nonzero then by Theorem 3,
Thus the squares are a subset of the roots of (5). On the other hand there are squares and at most roots and so the set of squares is precisely the set of roots of (5).
In is worth noting that there is a significant gap in the degree of the polynomial in (5) as opposed to in Theorem 3, which we make use of later. We now give a polynomial characterization of the cardinality of a set.
Lemma 1: Let and . Then if and only if for any , the equations
have a solution in the .
Proof: This is a classical fact about Vandermonde matrices.
We now proceed to the proof of Theorem 1, which adopts the Stepanov method of auxiliary polynomials.
Proof of Theorem 1: Let and suppose . We choose , which is possible in light of (4). By Lemma 1, we may choose so that , where
Our choice of will ensure that each is a root of with high multiplicity and that . By Corollary 2, since ,
Thus each is a root of (7). Furthermore,
and so, again by Corollary 2,
We may apply this argument for higher derivatives to obtain
Thus each is a root of with multiplicity and it follows that, if ,
It turns out that our previous choice for ensure that (and is thus nonzero). For instance, since , considering the leading term in (6), we have
and so the leading term of , which is the same, is also zero. The same argument works to show that the coefficient of of is zero for . Now the constant term of in (6) is
where is the coefficient of the term in is
Combining this with (8), we find
The second assertion in the Theorem follows immediately (see also Proposition 2.3 in Tao and Vu).
Remark 1: Suppose with . The proof of Theorem 1 reveals that
with and defined (7). Furthermore, we have the identity
A close variant of the extremal case left by Theorem 1 was studied by Lev and Sonn. Following Sárközy, we now prove (1) (with little concern for the precise constants). The key input is the Weil bounds, and so the square root barrier that appears in (1) is natural (as discussed in this previous blog post).
Proof of (1): Let be a prime and suppose . Without loss of generality, we may suppose . By (2), it is enough to show
Let be the Legendre symbol and consider, for ,
Thus and by our assumption for any and so
On the other hand, expanding the product in (10) and applying the Weil bounds of the form
for distinct , we find
This establishes (9) if , since then we may choose . Otherwise, we apply (12) with and multiply both sides by , and using (2), we find
This implies, crudely, that for ,
which is absurd for large (and letting the implied constants handle the case small).