Recent Progress on a Problem of Sárközy

Additive Combinatorics

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 {p} be a prime and {S \subset \mathbb{F}_p^{\times}} be the set of squares. Suppose {A+B = S}. Then either {|A| = 1} or {|B| = 1}. {\spadesuit} {\ }

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 {A+B = S}, then

\displaystyle \frac{\sqrt{p}}{3 \log p} \leq |A| , |B| \leq \sqrt{p} \log p,\ \ \ \ \ (1)

which we recall below. In fact, Shparlinski (in Theorem 7) improved (1) and then later Shkredov showed (in Corollary 2.6)

\displaystyle (1/6 - o(1)) \sqrt{p} \leq |A| , |B| \leq (3 + o(1)) \sqrt{p}.

Brandon Hanson and Giorgis Petridis, utilizing the polynomial method, recently made significant progress towards Conjecture 1.

{\ } Theorem 1 (Hanson-Petridis): Suppose {A+B = S}. Then

\displaystyle |A| |B| = |S|.

In particular every element of {S} has a unique representation of the form

\displaystyle a + b , \ \ \ a \in A \ \ , b \in B. \ \ \ \spadesuit

{\ }

Their techniques handle the case where {S} is replaced by any nontrivial multiplicative subgroup, but we focus on the squares for simplicity. In particular, if {(p-1)/2} 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 {\pi(x)} is the prime counting function.

{\ } Corollary 1: For all but {o(\pi(x))} primes less than {x}, Conjecture 1 holds. {\spadesuit} {\ }

Proof: Let {p} be a prime. Suppose {A+B = S} with {|A| , |B| > 1}. Then by Theorem 1 and (1), {(p-1)/2} has a divisor between {\frac{\sqrt{p}}{3 \log p} } and {\sqrt{p} \log p}. 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 {o(x / \log x)} such primes. Corollary 1 then follows from the prime number theorem. {\spadesuit} {\ }

If {S = A+B}, we always have trivial bound

\displaystyle (p-1)/2 = |A+B| \leq |A||B|, \ \ \ \ \ (2)

which can be compared to the following bilinear estimate.

{\ } Theorem 2: Let {\chi} be the quadratic character modulo {p}. Then

\displaystyle |\sum_{a \in A , b \in B} \chi(a +b ) | \leq \sqrt{p |A| |B|}.

In particular if {S = A+B}, then

\displaystyle |A| |B| \leq p. \ \ \ \spadesuit

{\ }

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 {S= A + B}, then

\displaystyle \sum_{a \in A , b \in B} \chi(a+b) = |A| |B|.

By Fourier inversion, it is enough to show

\displaystyle \sum_{a \in A , b \in B , \xi \in \mathbb{F}_p} e_p(\xi (a +b)) \widehat{\chi}(\xi) \leq \sqrt{p |A| |B|}, \ \ \ e_p(\theta) : = e^{2 \pi i \theta / p} ,\ \ \ \ \ (3)

where

\displaystyle \widehat{f}(\xi) = \frac{1}{p} \sum_{x \in \mathbb{F}_p} f(x) e_p(-\xi x).

Note { \widehat{\chi}(0) = 0}, and the usual estimate for Gauss sums implies

\displaystyle |\widehat{\chi}(\xi)| \leq p^{-1/2} , \ \ \ \xi \neq 0.

Combining with (3), it is enough to show

\displaystyle \sum_{\xi \in \mathbb{F}_p^{\times}} |\widehat{1_A}(\xi)||\widehat{1_B}(\xi)| \leq p^{-1} \sqrt{|A| |B|} .

But this follows from Cauchy-Schwarz and Parseval. {\spadesuit} {\ }

Combining (2) and Theorem 2, we see that if {S = A+B}, then

\displaystyle (p-1)/2 \leq |A||B| \leq p.\ \ \ \ \ (4)

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 {a \in \mathbb{F}_p}. Then {a \neq 0} if and only if {a} is a root of {x^{p-1} - 1}. {\spadesuit} {\ }

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 {a \in \mathbb{F}_p^{\times}}. Then {a} is a square if and only if {a} is a root to

\displaystyle x^{(p-1) / 2} - 1. \ \ \ \spadesuit \ \ \ \ \ (5)

{\ }

Proof: Every square is a root of (5) as if {a = x^2} for some nonzero {x} then by Theorem 3,

\displaystyle a^{(p-1)/2} = x^{p-1} = 1.

Thus the squares are a subset of the roots of (5). On the other hand there are {(p-1)/2} squares and at most {(p-1)/2} 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 {0 \leq n \leq p} and {A \subset \mathbb{F}_p}. Then {|A| \geq n} if and only if for any {d_0 , \ldots , d_{n-1} \in \mathbb{F}_p}, the equations

\displaystyle \sum_{a\in A} c_a a^k = d_k , \ \ \ 0 \leq k \leq n-1,

have a solution in the {c_a}. {\spadesuit} {\ }

Proof: This is a classical fact about Vandermonde matrices. {\spadesuit} {\ }

We now proceed to the proof of Theorem 1, which adopts the Stepanov method of auxiliary polynomials.

{\ } Proof of Theorem 1: Let {A , B \subset \mathbb{F}_p} and suppose {A+B = S}. We choose {|A| < (p-1)/2}, which is possible in light of (4). By Lemma 1, we may choose {c_a\in \mathbb{F}_p} so that {g \equiv 0}, where

\displaystyle g(x) = - 1 + \sum_{a \in A} c_a (x+a)^{|A| -1} .\ \ \ \ \ (6)

Let

\displaystyle F(x) = -1 + \sum_{a\in A} c_a (x+a)^D, \ \ \ D = (p-1) / 2 + |A| -1.\ \ \ \ \ (7)

Our choice of {c_a} will ensure that each {b \in B} is a root of {F} with high multiplicity and that {F \neq 0}. By Corollary 2, since {a+b \in S},

\displaystyle F(b) = -1 + \sum_{a\in A} c_a (b+a)^D =- 1 + \sum_{a\in A} c_a (b+a)^{|A| - 1} = g(b).

Thus each {b \in B} is a root of (7). Furthermore,

\displaystyle F'(x) = \sum_{a \in A} c_a D(x+a)^{D-1},

and so, again by Corollary 2,

\displaystyle F'(b) = Dg'(b) = 0.

We may apply this argument for higher derivatives to obtain

\displaystyle F^{(j)} (b) = 0 , \ \ \ 0 \leq j \leq |A| - 1.

Thus each {b \in B} is a root of {F} with multiplicity {|A|} and it follows that, if {F \neq 0},

\displaystyle |A| |B| \leq {\rm deg}(F).\ \ \ \ \ (8)

It turns out that our previous choice for {c_a} ensure that {{\rm deg}(F) = (p-1)/2} (and is thus nonzero). For instance, since {g \equiv 0}, considering the leading term in (6), we have

\displaystyle \sum_{a \in A} c_a = 0.

and so the leading term of {F}, which is the same, is also zero. The same argument works to show that the coefficient of {x^j} of {F} is zero for {(p-1)/ 2 + 1 \leq j \leq D}. Now the constant term of {g} in (6) is

\displaystyle -1 + \sum_{a \in A} c_a a^{|A| -1} = 0,

where is the coefficient of the {x^{(p-1)/2}} term in {F} is

\displaystyle {D \choose (p-1)/2} \sum_{a \in A} c_a a^{|A| - 1} = {D \choose (p-1) / 2} \neq 0.

Combining this with (8), we find

\displaystyle |A||B| \leq (p-1)/2.

The second assertion in the Theorem follows immediately (see also Proposition 2.3 in Tao and Vu). {\spadesuit} {\ }

Remark 1: Suppose {A+B = S} with {|A||B| = (p-1)/2}. The proof of Theorem 1 reveals that

\displaystyle F(x) = \alpha \prod_{b \in B} (x- b)^{|A|}, \ \ \ \alpha = {D \choose |A| - 1},

with {F} and {D} defined (7). Furthermore, we have the identity

\displaystyle \prod_{a \in A , b \in B} (x - (a+b)) = x^{(p-1)/2} - 1. \ \ \ \spadesuit

{\ }

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 {p} be a prime and suppose {A+B = S}. Without loss of generality, we may suppose {|B| \geq |A|}. By (2), it is enough to show

\displaystyle |B| \lesssim \sqrt{p} \log p.\ \ \ \ \ (9)

Let {\chi} be the Legendre symbol and consider, for {A' \subset A},

\displaystyle h(x) = 2^{-|A'|} \prod_{a \in A'} (\chi(x + a) + 1) .\ \ \ \ \ (10)

Thus {h \geq 0} and by our assumption {h(b) = 1} for any {b \in B} and so

\displaystyle |B| \leq \sum_{x \in \mathbb{F}_p} h(x) \ \ \ \ \ (11)

On the other hand, expanding the product in (10) and applying the Weil bounds of the form

\displaystyle \sum_{x \in \mathbb{F}_p} \chi(x+ a_1) \cdots \chi(x+ a_k) \leq (k-1) \sqrt{p},

for distinct {a_1 , \ldots , a_k}, we find

\displaystyle |B| \leq \sum_{x \in \mathbb{F}_p} h(x) \leq p 2^{-|A'|} + (|A'|- 1) \sqrt{p} , \ \ \ A' \subset A.\ \ \ \ \ (12)

This establishes (9) if {|A| \geq \log p / \log 4}, since then we may choose {\log p / \log 4 \leq |A'| \leq \log p / \log 4 + 1}. Otherwise, we apply (12) with {A' = A} and multiply both sides by {|A|}, and using (2), we find

\displaystyle (p-1) / 2 \leq p 2^{-|A|} + (|A| - 1) \sqrt{p}.

This implies, crudely, that for {|A| \geq 2},

\displaystyle p/4 \lesssim \sqrt{p} \log p,

which is absurd for {p} large (and letting the implied constants handle the case {p} small). {\spadesuit}

Leave a Reply