Sum-product formulae

Abstract

This is a survey on sum-product formulae and methods. We state old and new results. Our main objective is to introduce the basic techniques used to bound the size of the product and sumsets of finite subsets of a field.

1 Introduction

1.1 A Few Definitions

For an additive or multiplicative group G and subsets $A,B \subset G$ we define

$$\displaystyle\begin{array}{rcl} A + B& =& \{g \in G:\ \text{There exist}\ a \in A,b \in B\ \text{such that}\ g = a + b\};\ \text{and} {}\\ A \cdot B& =& \{g \in G:\ \text{There exist}\ a \in A,b \in B\ \text{such that}\ g = a \cdot b\}. {}\\ \end{array}$$

We let $r_{A+B}(n):= \#\{a \in A,b \in B:\ n = a + b\},\ r_{AB}(n):= \#\{a \in A,b \in B:$ n = ab}, and note that $0 \leq r_{A+B}(n) \leq \min \{\vert A\vert,\vert B\vert \}$ since $r_{A+B}(n)\,=\,\vert A\,\cap \,(n\,-\,B)\vert$ ≤ | A | and $r_{A+B}(n) = \vert B \cap (n - A)\vert \leq \vert B\vert$. We write $\hat{A}(t) =\sum _{a\in A}e(at)$ where e(u) = e ^{2i π u}.

1.2 Multiplication Tables

We learnt to multiply by memorizing the multiplication tables; that is, we wrote down a table with the rows and columns indexed by the integers between 1 and N and the entries in the table were the row entry times the column entry.¹ Paul Erdős presumably learnt his multiplication tables rather more rapidly than the other students, and was left wondering: How many distinct integers are there in the N-by-N multiplication table? Note that if we take $A =\{ 1,2,\ldots,N\}$, then we are asking how big is A ⋅ A? Or, more specifically, since the numbers in the N-by-N multiplication table are all ≤ N ², what proportion of the integers up to N ² actually appear in the table? That is,

$$\displaystyle{ \mathit{Does}\ \mbox{$\vert A \cdot A\vert /N^{2}$} \ \mathit{tend\ to\ a\ limit\ as }\ \mbox{$N \rightarrow \infty?$}} $$

Erdős showed that the answer is, yes, and that the limit is 0. His proof comes straight from “The Book”.² Erdős’s proof is based on the celebrated result of Hardy and Ramanujan that “almost all” positive integers n ≤ N have $\sim \log \log N$ (not necessarily distinct) prime factors (here “almost all” means for all but o(N) values of n ≤ N): Hardy and Ramanujan’s result implies that “almost all” products ab with a, b ≤ N have $\sim 2\log \log N$ prime factors, whereas “almost all” integers ≤ N ² have $\sim \log \log (N^{2}) \sim \log \log N$ prime factors! The result follows from comparing these two statements.

1.3 The Motivating Conjectures

In fact one can show that | A ⋅ A | is large whenever A is an arithmetic progression or, more generally, when A is a generalized arithmetic progression of not-too-large dimension. ³

This led Erdős and Szemerédi to the conjecture that for any ε > 0, there exists c _ε  > 0 such that for any finite set of integers A, 

$$\displaystyle{ \vert A + A\vert + \vert A \cdot A\vert \geq c_{\epsilon }\vert A\vert ^{2-\epsilon }. }$$

(1)

Even more, one can conjecture that if $\vert A\vert = \vert B\vert = \vert C\vert$ then

$$\displaystyle{ \vert A + B\vert + \vert A \cdot C\vert \geq c_{\epsilon }\vert A\vert ^{2-\epsilon }. }$$

(2)

The above conjectures might hold for complex numbers even. Perhaps the most general version is

$$\displaystyle{ {\text{Either}}\ \ \vert A + B\vert \gg (\vert A\vert \vert B\vert )^{1-\epsilon }\ \ {\text{or}}\ \ \vert A \cdot C\vert \gg (\vert A\vert \vert C\vert )^{1-\epsilon } }$$

with no restrictions on the sizes of A, B, and C. The thinking in these conjectures is that if A + B is small then A must be “structured,” more precisely that it must look like a largish subset of a generalized arithmetic progression, and similarly if AC is small then $\log A$ must look like a largish subset of a generalized arithmetic progression, and that these two structures are incompatible.

2 Sum-Product for Real Numbers

2.1 Results Via Discrete Geometry

The second author proved (2) for $\epsilon = 8/11$ [29] (see Theorem 1 below). We now prove (2) for $\epsilon = 3/4$. We begin by stating the

Szemerédi–Trotter Theorem.

We are given a set $\mathcal{C}$ of m curves in $\mathbb{R}^{2}$ such that

• Each pair of curves meet in ≤κ ₁ points;

• Any pair of points lie on ≤κ ₂ curves.

For any given set $\mathcal{P}$ of n points, there are $\leq m + 4\kappa _{2}n + 4\kappa _{1}\kappa _{2}^{1/3}(mn)^{2/3}$ pairs (π,γ) with point $\pi \in \mathcal{P}$ lying on curve $\gamma \in \mathcal{C}$ .

Székely provided a gorgeous proof of this result, straight from The Book, via geometric and random graph theory [27]. From this Elekes elegantly deduced the following in [7]:

Theorem 1.

If $A,B,C \subset \mathbb{R}$ , then

$$\displaystyle{ \vert A + B\vert + \vert A \cdot C\vert \geq \frac{1} {2}(\vert A\vert - 1)^{3/4}(\vert B\vert \vert C\vert )^{1/4}. }$$

(3)

Proof.

If $\vert A + B\vert \vert A \cdot C\vert \geq ( \frac{1} {2^{4}} \vert B\vert \vert C\vert )^{2}$, then at least one of | A + B | and | A ⋅ C | is $\geq \frac{1} {2^{4}} \vert B\vert \vert C\vert$, and they are both ≥ | A | , so that their product is $\geq \frac{1} {2^{4}} \vert A\vert ^{3}\vert B\vert \vert C\vert$. Hence

$$\displaystyle{\vert A + B\vert + \vert A \cdot C\vert \geq \frac{1} {2}\vert A\vert ^{3/4}(\vert B\vert \vert C\vert )^{1/4},}$$

which implies the result. Hence we may assume that $\vert A + B\vert \vert A \cdot C\vert < \frac{1} {2^{8}} (\vert B\vert \vert C\vert )^{2}$.

Let $\mathcal{P}$ be the set of points (A + B) × (A ⋅ C); and $\mathcal{C}$ the set of lines $y = c(x - b)$ where b ∈ B and c ∈ C. In the Szemerédi–Trotter Theorem we have $\kappa _{1} =\kappa _{2} = 1$ with

$$\displaystyle{ m = \vert B\vert \vert C\vert \ \ \text{and}\ \ n \leq N:= \vert A + B\vert \ \vert A \cdot C\vert, }$$

since the set of points is $\cup _{a\in A}(a + B,aC)$. For fixed b ∈ B and c ∈ C, all of the points {(a + b, ac): a ∈ A} in $\mathcal{P}$ lie on the line $y = c(x - b)$, so that

$$\displaystyle{ \#\{(\pi,\gamma ):\pi \in \mathcal{P}\ \text{on}\ \gamma \in \mathcal{C}\}\geq \vert A\vert m. }$$

Substituting this into the Szemerédi–Trotter Theorem we obtain

$$\displaystyle{ (\vert A\vert - 1)m \leq 4n + 4(mn)^{2/3} \leq 4N + 4(mN)^{2/3}. }$$

We assumed that N < m ²∕2⁸, so that $N < (mN)^{2/3}/2^{8/3} < (2^{2/3} - 1)(mN)^{2/3}$, and hence $(\vert A\vert - 1)m^{1/3} \leq 4(2N)^{2/3}$. This implies that $N > (\vert A\vert - 1)^{3/2}(\vert B\vert \vert C\vert )^{1/2}/16$. □ 

Corollary 2.1.

If $A \subset \mathbb{R}$ , then

$$\displaystyle{ \vert A + A\vert + \vert A \cdot A\vert \geq \frac{1} {2}\vert A\vert ^{5/4}. }$$

Next we give an argument that improves this. It is still not the best result currently known in the direction of (1) but it only uses the Szemerédi–Trotter Theorem which has several advantages. The most important advantage is that incidence bounds between points and lines on a plane over any field K provide sum-product bounds in K. Even better, the point set where the incidence bounds are needed have a special Cartesian product structure. For example, on the complex plane, $\mathbb{C}^{2},$ it is quite easy to give a Szemerédi-Trotter type bound (with the same exponents) for lines and points of a Cartesian product like (A + B) × (A ⋅ C) above. The incidence bound for this special case appeared in [28]. Another example is Vinh’s work [32] who used a Szemerédi-Trotter type bound to obtain a different proof of Garaev’s sum-product estimate in finite fields (see Theorem 4 below).

Theorem 2.

[29] If $A,B,C,D \subset \mathbb{R}$ with 0∉C, then

$$\displaystyle{ \vert A/C\vert \vert A + B\vert \vert C + D\vert \gg (\vert A\vert \vert C\vert )^{3/2}(\vert B\vert \vert D\vert )^{1/2}\min \left \{1, \frac{\vert A/C\vert } {\vert B\vert \vert D\vert }\right \}^{1/4}. }$$

Part of this follows from

Theorem 3.

If $A,B,C,D \subset \mathbb{R}$ with 0∉C and |A∕C|≤|B||D|, then

$$\displaystyle{ \vert A/C\vert ^{3}\ (\vert A + B\vert \vert C + D\vert )^{4} > \frac{1} {2 \cdot 10^{10}}(\vert A\vert \vert C\vert )^{6}(\vert B\vert \vert D\vert ), }$$

(4)

and

$$\displaystyle{ \vert AC\vert ^{3}(\vert A + B\vert \vert C + D\vert )^{4} \geq \frac{1} {10^{9}}\ \frac{(\vert A\vert \vert C\vert )^{6}(\vert B\vert \vert D\vert )} {\log ^{3}(4\min \{\vert A\vert,\vert C\vert \})}. }$$

We note some consequences:

Corollary 2.2.

If $A,C \subset \mathbb{R}$ with 0∉C, then

$$\displaystyle{ \vert A/C\vert ^{3}\ \vert A + C\vert ^{8} > \frac{1} {2 \cdot 10^{10}}(\vert A\vert \vert C\vert )^{7} }$$

(5)

and

$$\displaystyle{ \vert AC\vert ^{3}\ \vert A + C\vert ^{8} \geq \frac{1} {10^{9}}\ \frac{(\vert A\vert \vert C\vert )^{7}} {\log ^{3}(4\min \{\vert A\vert,\vert C\vert \})}. }$$

Hence

$$\displaystyle{ \vert AA\vert ^{3}\ \vert A + A\vert ^{8} \gg \frac{\vert A\vert ^{14}} {\log ^{3}(4\vert A\vert )}; }$$

in particular if |A + A|≤κ|A|, then $\vert AA\vert \gg \kappa ^{-8/3}\vert A\vert ^{2}/\log (4\vert A\vert )$ .

Remark.

If A = { 1, …, N}, then $\vert AA\vert \asymp N^{2}/(\log N)^{\delta }(\log \log N)^{3/2}$ for some $\delta = 1 -\frac{1+\log \log 2} {\log 2} = 0.08607\ldots$. Hence some power of $\log$ in the denominator in this last result is unavoidable.

Proof of Theorem 3.

Let V (k) denote the set of m ∈ C∕A for which $2^{k} \leq r_{C/A}(m) < 2^{k+1}$, for k = 0, 1, 2, … Consider $\mathcal{C} = \mathcal{C}_{k}$ the set of lines $y = mx + e$ with m ∈ V (k) which contain at least one point (x, y) ∈ B × D. Each (x, y) ∈ B × D lies on exactly | V (k) | lines of $\mathcal{C}_{k}$ (as may be seen by taking $e = b - dm$ for each m ∈ V (k)), so that

$$\displaystyle{ \vert V (k)\vert \vert B\vert \vert D\vert \leq \vert \mathcal{C}_{k}\vert + 4\vert B\vert \vert D\vert + 4(\vert \mathcal{C}_{k}\vert \vert B\vert \vert D\vert )^{2/3} }$$

by the Szemerédi–Trotter Theorem. Hence either | V (k) | ≤ 14 or $\frac{11} {15}\vert V (k)\vert \vert B\vert \vert D\vert \leq \vert \mathcal{C}_{k}\vert + 4(\vert \mathcal{C}_{k}\vert \vert B\vert \vert D\vert )^{2/3}$ which implies that

$$\displaystyle{ \vert \mathcal{C}_{k}\vert \geq \min \{ \frac{1} {4}\vert V (k)\vert \vert B\vert \vert D\vert, \frac{1} {27}\vert V (k)\vert ^{3/2}(\vert B\vert \vert D\vert )^{1/2}\}. }$$

Now | V (k) | ≤ | C∕A | ≤ | B | | D | so that $\vert \mathcal{C}_{k}\vert \geq \frac{1} {27}\vert V (k)\vert ^{3/2}(\vert B\vert \vert D\vert )^{1/2}$.

Now consider the set of points $(A + B) \times (C + D)$. If $y = mx + e$ is a line in $\mathcal{C}_{k}$ containing the point (b, d), then it also contains the points $(a + b,c + d)$ whenever $c/a = m$ with a ∈ A, c ∈ C. Hence each such line contains at least 2^k points from $(A + B) \times (C + D)$ and the Szemerédi–Trotter Theorem then yields $2^{k}\vert \mathcal{C}_{k}\vert \leq \vert \mathcal{C}_{k}\vert + 4\vert A + B\vert \vert C + D\vert + 4(\vert \mathcal{C}_{k}\vert \vert A + B\vert \vert C + D\vert )^{2/3}$. Hence

$$\displaystyle{ (2^{k} - 1)\vert \mathcal{C}_{ k}\vert \leq \max \{ 80\vert A + B\vert \vert C + D\vert,4.2\ (\vert \mathcal{C}_{k}\vert \vert A + B\vert \vert C + D\vert )^{2/3}\} }$$

which implies that

$$\displaystyle{ \vert \mathcal{C}_{k}\vert \leq 80\max \left \{\frac{\vert A + B\vert \vert C + D\vert } {(2^{k} - 1)}, \frac{(\vert A + B\vert \vert C + D\vert )^{2}} {(2^{k} - 1)^{3}} \right \} = 80\frac{(\vert A + B\vert \vert C + D\vert )^{2}} {(2^{k} - 1)^{3}}, }$$

where this last inequality follows since $r_{C/A}(m) \leq \min \{\vert A\vert,\vert C\vert \}$ which implies that

$$\displaystyle{ (2^{k} - 1)^{2} < r_{ C/A}(m)^{2} \leq \vert A\vert \vert C\vert \leq \vert A + B\vert \vert C + D\vert. }$$

Combining the deductions at the end of the last two paragraphs gives

$$\displaystyle{ \vert V (k)\vert \leq 6^{2}10^{2/3}\frac{(\vert A + B\vert \vert C + D\vert )^{4/3}} {(2^{k} - 1)^{2}(\vert B\vert \vert D\vert )^{1/3}}. }$$

(6)

Therefore

$$\displaystyle\begin{array}{rcl} \sum _{\begin{array}{c}r_{ C/A}(m)\geq 2^{K}\end{array}}r_{C/A}(m)& \leq & \sum _{k\geq K}\sum _{\begin{array}{c}m\in V (k)\end{array}}2^{k+1} \leq 335\sum _{ k\geq K} \frac{2^{k}} {(2^{k} - 1)^{2}} \cdot \frac{(\vert A + B\vert \vert C + D\vert )^{4/3}} {(\vert B\vert \vert D\vert )^{1/3}} {}\\ & \leq & 670 \frac{2^{K}} {(2^{K} - 1)^{2}} \cdot \frac{(\vert A + B\vert \vert C + D\vert )^{4/3}} {(\vert B\vert \vert D\vert )^{1/3}}, {}\\ \end{array}$$

and this is $\leq \frac{1} {2}\vert A\vert \vert C\vert$ provided $2^{K} \geq 671(\vert A + B\vert \vert C + D\vert )^{4/3}/(\vert A\vert \vert C\vert )(\vert B\vert \vert D\vert )^{1/3}$. So select the smallest K for which this holds, so that

$$\displaystyle{ \frac{1} {2}\vert A\vert \vert C\vert \leq \sum _{\begin{array}{c}r_{ C/A}(m)<2^{K}\end{array}}r_{C/A}(m) < 2^{K}\vert C/A\vert < 1342\vert C/A\vert \ \frac{(\vert A + B\vert \vert C + D\vert )^{4/3}} {(\vert A\vert \vert C\vert )(\vert B\vert \vert D\vert )^{1/3}}, }$$

and the first result follows.

Let us also note that, by the Cauchy–Schwarz inequality

$$\displaystyle{ (\vert A\vert \vert C\vert )^{2} = \left \vert \sum _{n}r_{ AC}(n)\right \vert ^{2} \leq \vert AC\vert \sum _{n}r_{ AC}(n)^{2} = \vert AC\vert \sum _{m}r_{ C/A}(m)^{2} \leq 4\vert AC\vert \sum _{ k}V (k)2^{2k}. }$$

By (6), and the fact that $2^{k} \leq r_{C/A}(m) \leq \min \{\vert A\vert,\vert C\vert \}$ we deduce the second result. □ 

Proof of Theorem 2 when | C∕A |  >  | B | | D | .

We may assume that

$$\displaystyle{ \vert A + B\vert \vert C + D\vert \leq (\vert A\vert \vert C\vert )^{3/2}/(118(\vert B\vert \vert D\vert )^{1/2}), }$$

else we obtain the result by multiplying through by $\vert A/C\vert ^{3/4} > (\vert B\vert \vert D\vert )^{3/4}$.

In the proof of Theorem 3 we note that if V (k) >  | B | | D | then

$$\displaystyle{ V (k) \leq \frac{4\vert \mathcal{C}_{k}\vert } {\vert B\vert \vert D\vert } \leq 320\frac{(\vert A + B\vert \vert C + D\vert )^{2}} {(2^{k} - 1)^{3}\vert B\vert \vert D\vert }, }$$

so we obtain $\sum _{\begin{array}{c}r_{ C/A}(m)\leq 2^{K}\end{array}}r_{C/A}(m) \geq \frac{1} {2}\vert A\vert \vert C\vert$ provided

$$\displaystyle{ 2^{K} \gg \max \left \{\frac{(\vert A + B\vert \vert C + D\vert )^{4/3}} {(\vert A\vert \vert C\vert )(\vert B\vert \vert D\vert )^{1/3}},\ \frac{\vert A + B\vert \vert C + D\vert } {(\vert A\vert \vert B\vert \vert C\vert \vert D\vert )^{1/2}}\right \} \asymp \frac{\vert A + B\vert \vert C + D\vert } {(\vert A\vert \vert B\vert \vert C\vert \vert D\vert )^{1/2}}, }$$

the last equality following from our assumption, and the result follows as in the proof of Theorem 3. □ 

2.2 Some Easier Ideas

The multiplicative energy of two finite sets A, B is defined as

$$\displaystyle{ E_{\times }(A,B) = \#\{a_{1},a_{2} \in A,\ b_{1},b_{2} \in B:\ a_{1}b_{1} = a_{2}b_{2}\} =\sum _{a,b\in B}\vert aA \cap bA\vert. }$$

By the Cauchy–Schwarz inequality we have E _×(A, B)² ≤ E _×(A, A)E _×(B, B). We also can write

$$\displaystyle{ E_{\times }(A,B) =\sum _{m}r_{AB}(m)^{2} =\sum _{ n}r_{A/B}(n)^{2} =\sum _{ n}r_{A/A}(n)r_{B/B}(n), }$$

and hence, by the Cauchy–Schwarz inequality

$$\displaystyle{ (\vert A\vert \vert B\vert )^{2} = \left (\sum _{ m}r_{AB}(m)\right )^{2} \leq \vert AB\vert \sum _{ m}r_{AB}(m)^{2} = \vert AB\vert E_{ \times }(A,B). }$$

(7)

Similarly ( | A | | B | )² ≤ | A∕B | E _×(A, B). Finally, if $A_{1} \cap A_{2} =\emptyset$, then $r_{(A_{1}\cup A_{2})B}(n) = r_{A_{1}B}(n) + r_{A_{2}B}(n)$ and so, by the Cauchy–Schwarz inequality,

$$\displaystyle\begin{array}{rcl} E_{\times }(A_{1} \cup A_{2},B)& =& \sum _{m}r_{(A_{1}\cup A_{2})B}(m)^{2} \\ & \leq & 2\sum _{m}(r_{A_{1}B}(n)^{2} + r_{ A_{2}B}(n)^{2}) = 2(E_{ \times }(A_{1},B) + E_{\times }(A_{2},B)).{}\end{array}$$

(8)

Proposition 2.3.

(Solymosi, [30]) If A and B are finite sets of real numbers, not containing {0}, then

$$\displaystyle{ E_{\times }(A,B) \leq 12\vert A + A\vert \vert B + B\vert \log (3\min \{\vert A\vert,\vert B\vert \}), }$$

(9)

and hence, by (7) ,

$$\displaystyle{ \vert A + A\vert \vert B + B\vert \min \{\vert A/B\vert,\vert AB\vert \}\geq (\vert A\vert \vert B\vert )^{2}/(12\log (3\min \{\vert A\vert,\vert B\vert \}). }$$

Remarks.

Note that there are examples with $0 \in A \cup B$ where this bound cannot hold. For example, if 0 ∈ B, then $E_{\times }(A,B) \geq \#\{a,a^{{\prime}}\in A: a0 = 0 = a^{{\prime}}0\} = \vert A\vert ^{2}$ whereas the bound in Proposition 2.3 is smaller than | A | ² if A and B are both arithmetic progressions with $\vert B\vert \ll \vert A\vert /\log \vert A\vert$.

Note also that this bound is, more-or-less, best possible in any example with | A + A | ≪ | A | and | B + B | ≪ | B | since, trivially, E _×(A, B) ≥ | A | | B | .

Proof.

We begin by proving this result when A and B are both finite sets of positive real numbers. Let $m:=\min \{ \vert A\vert,\vert B\vert \}$. If m = 1, then $E_{\times }(A,B) =\max \{ \vert A\vert,\vert B\vert \}$ and the result is easy, so we may assume m ≥ 2.

Let $R_{B/A}(\ell) =\{ (a,b) \in A \times B: b =\ell a\}$ which has size r _B∕A (ℓ), and note that r _B∕A (ℓ) ≤ m. Let $L_{k}:=\{\ell:\ 2^{k} \leq r_{B/A}(\ell) < 2^{k+1}\}$ and $K = [\log m/\log 2] + 1$. Then

$$\displaystyle{ \sum _{k=0}^{K-1}\sum _{ \begin{array}{c}\ell\in L_{k}\end{array}}r_{B/A}(\ell)^{2} =\sum _{\begin{array}{c}\ell\end{array}}r_{ B/A}(\ell)^{2} = E_{ \times }(A,B), }$$

and

$$\displaystyle{ \sum _{\begin{array}{c}k=0 \\ \vert L_{k}\vert =1\end{array}}^{K-1}\sum _{ \begin{array}{c}\ell\in L_{k}\end{array}}r_{B/A}(\ell)^{2} \leq \sum _{ k=0}^{K-1}2^{2k+2} < \frac{2^{2K+2}} {3} \leq \frac{16m^{2}} {3}. }$$

Hence there exists k with | L _k  | ≥ 2 for which

$$\displaystyle{ \sum _{\begin{array}{c}\ell\in L_{k}\end{array}}r_{B/A}(\ell)^{2} \geq \frac{1} {K}\left (E_{\times }(A,B) -\frac{16m^{2}} {3} \right ). }$$

Let L _k  = { ℓ ₁ < ℓ ₂ < … < ℓ _r } with r ≥ 2; we claim that the elements of

$$\displaystyle{ \bigcup _{i=1}^{r-1}(R_{ B/A}(\ell_{i}) + R_{B/A}(\ell_{i+1})) \subset A \times B + A \times B }$$

are distinct. For if i < j with $a_{i} + a_{i+1} = a_{j} + a_{j+1}$, then

$$\displaystyle{ \ell_{i}a_{i} +\ell _{i+1}a_{i+1} <\ell _{i+1}(a_{i} + a_{i+1}) \leq \ell_{j}(a_{j} + a_{j+1}) <\ell _{j}a_{j} +\ell _{j+1}a_{j+1}; }$$

and if $(a + a^{{\prime}},\ell_{i}a +\ell _{i+1}a^{{\prime}}) = (x,y)$, then a and $a^{{\prime}}$ are determined, and so unique.

Now, as $A \times B + A \times B = (A + A) \times (B + B)$, we deduce that

$$\displaystyle\begin{array}{rcl} \vert A + A\vert \vert B + B\vert & =& \vert A \times B + A \times B\vert \geq \sum _{i=1}^{r-1}r_{ B/A}(\ell_{i})r_{B/A}(\ell_{i+1}) {}\\ & \geq & (r - 1)2^{2k} \geq \frac{r} {2} \cdot 2^{2k} \geq \frac{1} {8}\sum _{i=1}^{r}r_{ B/A}(\ell_{i})^{2} {}\\ & \geq & \frac{1} {8K}\left (E_{\times }(A,B) -\frac{16m^{2}} {3} \right ). {}\\ \end{array}$$

From this we deduce that

$$\displaystyle{ E_{\times }(A,B) \leq \frac{8\log 2m} {\log 2} \ \vert A + A\vert \vert B + B\vert + \frac{16} {3} \min \{\vert A\vert,\vert B\vert \}^{2}, }$$

and then (9) follows for m ≥ 2 after a little calculation, using the fact that $\vert C + C\vert \geq 2\vert C\vert - 1$.

Now if A only has positive real numbers and 0 ∉ B, then write $B = B_{+} \cup B_{-}$ where B _± = { b ∈ B: ±b > 0}. Now $E_{\times }(A,B_{-}) = E_{\times }(A,-B_{-})$ by definition so, by (8) and then the case in which we have already proved (9), we have

$$\displaystyle\begin{array}{rcl} E_{\times }(A,B)& \leq & 2E_{\times }(A,B_{+}) + 2E_{\times }(A,-B_{-}) {}\\ & \leq & 12\vert A + A\vert (\vert B_{+} + B_{+}\vert + \vert B_{-} + B_{-}\vert )\log (3\min \{\vert A\vert,\vert B\vert \}) {}\\ \end{array}$$

which implies (9), since $B_{+} + B_{+}$ and $B_{-} + B_{-}$ are evidently disjoint subsets of B + B (as their elements are of different signs) (Fig. 1).

Fig. 1

The sum of (a, b) ∈ ℓ _i and (c, d) ∈ ℓ _i+1 is a unique point of the Cartesian product $(A + A) \times (B + B)$.

Finally, if $0\not\in A \cup B$, then (9) follows similarly from this last result by partitioning A as $A_{+} \cup A_{-}$. □ 

Remark.

We can deduce bounds on E _×(A, B), when $0 \in A \cup B$, from Proposition 2.3, using the following

If 0 ∉ A but $0 \in B = B_{0} \cup \{ 0\}$ then, by definition, $E_{\times }(A,B) = E_{\times }(A,B_{0}) + \vert A\vert ^{2}$ and $B + B = (B_{0} + B_{0}) \cup B$.

If $0 \in A = A_{0} \cup \{ 0\}$ and $0 \in B = B_{0} \cup \{ 0\}$, then $E_{\times }(A,B) = E_{\times }(A_{0},B_{0}) + (\vert A\vert + \vert B\vert - 1)^{2}$ with $A + A = (A_{0} + A_{0}) \cup A$ and $B + B = (B_{0} + B_{0}) \cup B$.

Corollary 2.4.

If A is any finite set of real numbers, then

$$\displaystyle{ E_{\times }(A,B) \leq 12\vert A + A\vert ^{2}\log (3\vert A\vert ), }$$

(10)

and hence, by (7) ,

$$\displaystyle{ \vert A + A\vert ^{2}\min \{\vert A/A\vert,\vert AA\vert \}\geq \vert A\vert ^{4}/(12\log (3\vert A\vert ). }$$

Proof.

If 0 ∉ A, then our bound follows from setting B = A in (9). If 0 ∈ A, then we use the information in the previous remark, together with (9), to obtain

$$\displaystyle\begin{array}{rcl} E_{\times }(A,A)& =& E_{\times }(A_{0},A_{0}) + (2\vert A\vert - 1)^{2} \leq 12\vert A_{ 0} + A_{0}\vert ^{2}\log (3\vert A\vert ) + (2\vert A\vert - 1)^{2} {}\\ & =& 12(\vert A + A\vert -\vert A\vert )^{2}\log (3\vert A\vert ) + (2\vert A\vert - 1)^{2} {}\\ & =& 12\vert A+A\vert ^{2}\log (3\vert A\vert )+12\log (3\vert A\vert )(\vert A\vert ^{2}-2\vert A\vert \vert A+A\vert )+(2\vert A\vert -1)^{2} {}\\ & \leq & 12\vert A + A\vert ^{2}\log (3\vert A\vert ) + 12\log (3\vert A\vert )(2\vert A\vert - 3\vert A\vert ^{2}) + (2\vert A\vert - 1)^{2} {}\\ \end{array}$$

as $\vert A + A\vert \geq 2\vert A\vert - 1$, which yields (10). □ 

A similar bound for complex numbers was obtained by Konyagin and Rudnev in [22]. Very recently Konyagin and Shkredov announced an improvement on the sum-product bound. They proved in [23] that

$$\displaystyle{\vert A + A\vert + \vert A \cdot A\vert \gg \vert A\vert ^{4/3+c}}$$

where $\frac{1} {20598} > c > 0$ is an absolute constant.

2.3 Small Product Sets

From Corollary 2.2 it follows that if the sumset is very small then the product set is almost quadratic. The opposite statement is surprisingly hard to prove. It was Chang’s observation [6] that one can use a powerful tool, the Subspace Theorem, to obtain such bound. For the history and more details about the Subspace Theorem we refer to the excellent survey paper of Yuri Bilu [3].

An important variant of the Subspace Theorem was proved by Evertse, Schlickewei, and Schmidt [9]. We present the version with the best known bound due to Amoroso and Viada [1].

Theorem 2.5.

Let K be a field of characteristic 0, Γ a subgroup of K ^∗ of rank r, and $a_{1},a_{2},\ldots,a_{n} \in K^{{\ast}}$ . Then the number of solutions of the equation

$$\displaystyle{ a_{1}z_{1} + a_{2}z_{2} +\ldots +a_{n}z_{n} = 1 }$$

(11)

with z _i ∈Γ and no subsum on the left-hand side vanishing is at most

$$\displaystyle{A(n,r) \leq (8n)^{4n^{4}(n+nr+1) }.}$$

We are going to use the following result of Freiman (Lemma 1.14 in [11]).

Proposition 1.

Let $A \subset \mathbb{C}$ . If |AA|≤ C|A|, then A is a subset of a multiplicative subgroup of $\mathbb{C}^{{\ast}}$ of rank at most r, where r is a constant depending on C.

Theorem 2.6.

Let $A \subset \mathbb{C}$ with |A| = n. Suppose |AA|≤ Cn. Then there is a constant $C^{{\prime}}$ depending only on C such that

$$\displaystyle{\vert A + A\vert \geq \frac{n^{2}} {2} + C^{{\prime}}n.}$$

Proof.

We consider solutions of $x_{1} + x_{2} = x_{3} + x_{4}$ with x _i  ∈ A. A solution of this equation corresponds to two pairs of elements from A that give the same element in A + A. Let us suppose that x ₁ + x ₂ ≠ 0 (there are at most | A |  = n solutions of the equation $x_{1} + x_{2} = 0$ with x ₁, x ₂ ∈ A).

First we consider the solutions with x ₄ = 0. Then by rearranging we get

$$\displaystyle{ \frac{x_{1}} {x_{3}} + \frac{x_{2}} {x_{3}} = 1. }$$

(12)

By Proposition 1 and Theorem 2.5 there are at most s ₁(C) solutions of $y_{1} + y_{2} = 1$ with no subsum vanishing. Each of these gives at most n solutions of (12) since there are n choices for x ₃. There are only two solutions of $y_{1} + y_{2} = 1$ with a vanishing subsum, namely y ₁ = 0 or y ₂ = 0, and each of these gives n solutions of (12). So we have a total of (s ₁(C) + 2)n solutions of (12).

For x ₄ ≠ 0 we get

$$\displaystyle{ \frac{x_{1}} {x_{4}} + \frac{x_{2}} {x_{4}} -\frac{x_{3}} {x_{4}} = 1. }$$

(13)

Again by Proposition 1 and Theorem 2.5, the number of solutions of this with no vanishing subsum is at most s ₂(C)n. If we have a vanishing subsum, then $x_{1} = -x_{2}$ which is a case we excluded earlier or x ₁ = x ₃ and then x ₂ = x ₄, or x ₂ = x ₃ and then x ₁ = x ₄. So we get at most 2n ² solutions of (13) with a vanishing subsum (these are the $x_{1} + x_{2} = x_{2} + x_{1}$ identities).

So, in total, we have at most 2n ² + s(C)n solutions of $x_{1} + x_{2} = x_{3} + x_{4}$ with x _i  ∈ A. Suppose $\vert A + A\vert = k$ and $A + A =\{\alpha _{1},\ldots,\alpha _{k}\}$. We may assume that α ₁ = 0. Recall that we ignore sums $a_{i} + a_{j} = 0$. Let

$$\displaystyle{P_{i} =\{ (a,b) \in A \times A: a + b =\alpha _{i}\},\quad 2 \leq i \leq k.}$$

Then

$$\displaystyle{\sum _{i=2}^{k}\vert P_{ i}\vert \geq n^{2} - n = n(n - 1).}$$

Also, a solution of $x_{1} + x_{2} = x_{3} + x_{4}$ corresponds to picking two values from P _i where $x_{1} + x_{2} =\alpha _{i}$. Thus

$$\displaystyle{2n^{2} + s(C)n \geq \sum _{ i=2}^{k}\vert P_{ i}\vert ^{2} \geq \frac{1} {k - 1}\left (\sum _{i=2}^{k}\vert P_{ i}\vert \right )^{2} \geq \frac{n^{2}(n - 1)^{2}} {k - 1} }$$

by the Cauchy-Schwarz inequality. The bound for $k = \vert A + A\vert$ follows.

2.4 Upper Bounds in the Sum-Product Inequality

One obvious way to obtain upper bounds is to select A to be a largish subset of {1, …, x} with lots of multiplicative structure. For example, we could let A be the set of integers ≤ x all of whose prime factors are ≤ y, so that | A |  = Ψ(x, y),   | AA | ≤ Ψ(x ², y), and | A + A | ≤ 2x. Roughly $\varPsi (x,y) = x((e + o(1))/u\log u)^{u}$ when x = y ^u; so that $\vert AA\vert /\vert A\vert ^{2} = (1/2 + o(1))^{2u}$ and $\vert A + A\vert /\vert A\vert ^{2} = (u\log u/(e + o(1)))^{2u}/x$. We select u so that these are roughly equal, that is, $u = \frac{\log x} {2\log \log x}\left (1 + \frac{1+o(1)} {\log \log x} \right )$, and thus $y \asymp (\log x)^{2}$. Therefore $\vert A\vert = x^{1/2}2^{(1+o(1))u}$. Hence we have an infinite family of examples in which, if | A |  = N then

$$\displaystyle{ \max \{\vert A + A\vert,\vert AA\vert \}\leq N^{2-\frac{\log 4+o(1)} {\log \log N} }. }$$

We can obtain this result without using any “machinery”: Let A be the set of $N:= \binom{\pi (y) + u}{u}$ integers composed of no more than u not necessarily distinct prime factors ≤ y. Then $A \subset [1,y^{u}]$ so that | A + A | ≤ 2y ^u, whereas $\vert AA\vert = \binom{\pi (y) + 2u}{2u}$. We select $u = [ey^{1/2}/2\log y]$ so that, by Stirling’s formula and the prime number theorem,

$$\displaystyle{ N = \left (\frac{e(y/\log y)} {u} \right )^{u}e^{O(u/\log y)} = \left (2y^{1/2}\right )^{u}e^{O(u/\log y)} = (u(\log u)^{O(1)})^{u}, }$$

and therefore $u \sim \log N/\log \log N$. Now, by similar calculations we find that

$$\displaystyle{ \vert AA\vert \ \text{and}\ \vert A + A\vert = \vert A\vert ^{2}/2^{(2+o(1))u}e^{O(u/\log y)} = N^{2-\frac{\log 4+o(1)} {\log \log N} }. }$$

3 Sum-Product Inequalities over Finite Fields

The Szemerédi–Trotter Theorem does not hold over $\mathbb{F}_{q}$ which renders all of the above results moot in this setting. However such results in finite fields are the most applicable, so we will now pursue this. The first thing to note is that we must modify (1) when the set A is large, hence Garaev conjectured that if $A \subset \mathbb{F}_{p}$ then

$$\displaystyle{ \vert A + A\vert + \vert A \cdot A\vert \gg \min \{\vert A\vert ^{2}/\sqrt{p},\sqrt{p\vert A\vert }\}\big/\vert A\vert ^{o(1)}. }$$

(14)

3.1 Upper Bounds in $\mathbb{F}_{p}$

We begin by showing that the lower bound in Garaev’s conjecture cannot, in general, be increased:

Proposition 3.1.

For any given integers I,J,N with 1 ≤ N ≤ I,J ≤ p, and N ≤⌈IJ∕p⌉, there exist $A \subset B,C \subset \mathbb{F}_{p}$ , with $\vert A\vert = N,\vert B\vert = J,\vert C\vert = I$ such that

$$\displaystyle{ \vert A + B\vert < 2\vert B\vert \ \text{and}\ \vert A \cdot C\vert < 2\vert C\vert. }$$

In particular, for any given N,1 ≤ N ≤ p, there exists $A \subset \mathbb{F}_{p}$ with |A| = N such that

$$\displaystyle{ \max \{\vert A + A\vert,\vert A \cdot A\vert \}\leq \min \{\vert A\vert ^{2},2\sqrt{p\vert A\vert } + 1\}. }$$

Remark.

If we have $\max \{\vert A + A\vert,\vert A \cdot A\vert \}\gg \vert A\vert ^{2-o(1)}$ for all sets $A \subset \mathbb{F}_{p}$ of size N, then the second part of Proposition 3.1 implies that $N \ll p^{1/3-o(1)}$.

Proof.

Let C: = { g ¹, …, g ^I} where g is a primitive root mod p, and $A_{x}:= C \cap B_{x}$ for each $x \in \mathbb{F}_{p}$ where $B_{x}:= x +\{ 1,\ldots,J\}$. Now

$$\displaystyle{ \sum _{x}\vert A_{x}\vert =\sum _{ i=1}^{I}\sum _{ j=1}^{J}\#\{x \in \mathbb{F}_{ p}:\ x = g^{i} - j\} = IJ, }$$

so that there exists x with | A _x  | ≥ IJ∕p. Let A be any subset of A _x of size N, and B = B _x . Therefore $A + A \subset A + B \subset B + B =\{ 2x + 2,\ldots,2x + 2J\}$, $A \cdot A \subset C \cdot C \subset \{ g^{2},\ldots,g^{2I}\}$ so that $\vert A + A\vert \leq \vert A + B\vert \leq \vert B + B\vert < 2J$ and | A ⋅ A | ≤ | A ⋅ C | ≤ | C ⋅ C |  < 2I, which completes the proof of the first part. Now, taking $I = J = \lceil \sqrt{pN}\rceil$ we find that $\vert A + A\vert,\vert A \cdot A\vert \leq 2\lceil \sqrt{pN}\rceil - 1$, which implies the second part. □ 

3.2 A Little Cauchying

Let us make note of a couple of inequalities, for characteristic functions of sets: By Cauchy we obtain

$$\displaystyle{ \left (\sum _{j}\left \vert A\left (\frac{j} {p}\right )\right \vert \left \vert \hat{B}\left (\frac{-j} {p} \right )\right \vert \right )^{2} \leq \sum _{ j}\left \vert A\left (\frac{j} {p}\right )\right \vert ^{2}\sum _{ j}\left \vert B\left (\frac{-j} {p} \right )\right \vert ^{2} = p\vert A\vert \cdot p\vert B\vert. }$$

(15)

By Cauchy we obtain

$$\displaystyle\begin{array}{rcl} \left \vert \sum _{a\in A}\sum _{b\in B}e\left (\frac{kab} {p} \right )\right \vert ^{2}& \leq & \sum _{ a\in A}1 \cdot \sum _{a\in A}\left \vert \sum _{b\in B}e\left (\frac{kab} {p} \right )\right \vert ^{2} \\ & \leq & \vert A\vert \cdot \sum _{a\in \mathbb{F}_{p}}\left \vert \sum _{b\in B}e\left (\frac{kab} {p} \right )\right \vert ^{2} = \vert A\vert \cdot p\vert B\vert,{}\end{array}$$

(16)

by Parseval.

3.3 Lower Bounds in $\mathbb{F}_{p}$

Theorem 4.

(Garaev) If $A,B,C \subset \mathbb{F}_{p}$ with 0∉C, then

$$\displaystyle{ \vert A + B\vert \cdot \vert A \cdot C\vert \geq \frac{\vert A\vert } {4} \cdot \min \left \{\frac{\vert A\vert \vert B\vert \vert C\vert } {p},2p\right \}. }$$

Remark.

Taking $I = J = [\sqrt{pN}]$ in Proposition 3.1, we obtain examples with | A + B |   | A ⋅ C | ≤ 4p | A | . Therefore Theorem 4 is best possible, up to a factor of 8, when | A | | B | | C | ≥ 2p ². In particular for $\vert A\vert = \vert B\vert = \vert C\vert \geq 2p^{2/3}$.

Theorem 4 and its proof remain valid, with suitable modifications, in $\mathbb{F}_{p} \times \mathbb{F}_{p}$ (changing both occurrences of p to q = p ² in the lower bound). If we select a set $D \subset \mathbb{F}_{p}$ such that $\vert D + D\vert,\vert DD\vert \asymp \min \{\vert D\vert ^{2},p\}$, then taking $A = B = C = D \times \mathbb{F}_{p}$ we have $\vert A + B\vert,\vert AC\vert \asymp p\min \{\vert D\vert ^{2},p\} =\min \{ \vert A\vert ^{2}/p,p^{2}\}$ so that $\vert A + A\vert \vert AA\vert \asymp \min \{\vert A\vert ^{4}/q,q^{2}\}$. Therefore Theorem 4 is best possible up to a constant factor when $q^{1/2} \leq \vert A\vert \leq q^{3/4}$, in this setting.

First by letting C → 1∕C above, and then by taking $A = B = C$ we deduce:

Corollary 3.2.

If $A,B,C \subset \mathbb{F}_{p}$ with 0∉C, then

$$\displaystyle{ \vert A + B\vert \cdot \vert A/C\vert \geq \frac{\vert A\vert } {4} \cdot \min \left \{\frac{\vert A\vert \vert B\vert \vert C\vert } {p},2p\right \}. }$$

If $A \subset \mathbb{F}_{p}$ with 0∉A, then

$$\displaystyle{ \vert A + A\vert \cdot \vert AA\vert,\ \vert A + A\vert \cdot \vert A/A\vert \geq \frac{\vert A\vert } {4} \cdot \min \left \{\frac{\vert A\vert ^{3}} {p},2p\right \}. }$$

If A is a multiplicative subgroup of $\mathbb{F}_{p}^{{\ast}}$ , then

$$\displaystyle{ \vert A + A\vert \geq \min \left \{\frac{\vert A\vert ^{3}} {4p},p/2\right \}. }$$

Proof of Theorem 4.

For any a ∈ A, b ∈ B, c ∈ C we have a distinct solution to

$$\displaystyle{ u/c + b = v }$$

(17)

with $u \in AC,c \in C,b \in B,\ v \in V = A + B$, where u = ac and $v = a + b$. Hence | A | | B | | C | is no more than the total number of solutions of (3.4), which equals

$$\displaystyle\begin{array}{rcl} & & \ \sum _{u\in AC}\sum _{c\in C}\sum _{b\in B}\sum _{v\in A+B}\ \frac{1} {p}\sum _{j=0}^{p-1}e\left (\frac{j(u/c + b - v)} {p} \right ) {}\\ & =& \frac{1} {p}\sum _{j=0}^{p-1}\hat{B}\left (\frac{j} {p}\right )\hat{V }\left (\frac{-j} {p} \right )\sum _{u\in AC}\sum _{c\in C}e\left (\frac{ju/c} {p} \right ) {}\\ & \leq & \frac{\vert B\vert \vert C\vert \vert A + B\vert \vert AC\vert } {p} + \frac{1} {p}\ \max _{k\neq 0}\left \vert \sum _{u\in AC}\sum _{c\in C}e\left (\frac{ku/c} {p} \right )\right \vert \sum _{j\neq 0}\left \vert \hat{B}\left (\frac{j} {p}\right )\right \vert \left \vert \hat{V }\left (\frac{-j} {p} \right )\right \vert {}\\ & \leq & \frac{\vert B\vert \vert C\vert \vert A + B\vert \vert AC\vert } {p} + \sqrt{p\vert B\vert \vert C\vert \vert A + B\vert \vert AC\vert } {}\\ \end{array}$$

by (15) with A replaced by V, and by (16) with A replaced by AC and B replaced by 1∕C, and the result follows. □ 

Theorem 5.

Suppose that $A,B,C,D \subset \mathbb{F}_{p}$ , and C does not contain 0.

If $\vert A + B\vert \vert C + D\vert \vert A/C\vert ^{2}\vert B\vert \vert D\vert \leq p^{4}$ , then

$$\displaystyle{ \vert A + B\vert \vert C + D\vert \geq \frac{(\vert A\vert \vert C\vert )^{2}\vert B\vert \vert D\vert } {4p^{2}}. }$$

If $\vert A + B\vert \vert C + D\vert \vert A/C\vert ^{2}\vert B\vert \vert D\vert > p^{4}$ , then

$$\displaystyle{ \vert A + B\vert \vert C + D\vert \vert A/C\vert \geq \frac{p} {2}\vert A\vert \vert C\vert. }$$

Corollary 3.3.

If $0\not\in A \subset \mathbb{F}_{p}$ and $\vert A + A\vert \vert A/A\vert \vert A\vert \leq p^{2}$ , then $\vert A + A\vert \geq \vert A\vert ^{3}/2p$ .

If |A + A|≤κ|A| and |A|≥ p ^2∕3 , then $\vert AA\vert,\vert A/A\vert \geq p/2\kappa$ (by Corollary  3.2 ).

If |A + A|≤κ|A| and $(2\kappa p)^{1/2} < \vert A\vert \leq p^{2/3}$ , then $\vert A/A\vert > p/2\kappa ^{2}$ .

Remark.

The first part is stronger than Garaev’s $\vert AA\vert \vert A + A\vert \geq \vert A\vert ^{4}/2p$ in this range.

Proof of Theorem 5.

Let us look at solutions to $u - b = m(v - d)$ with $b \in B,d \in D,u \in U = A + B,v \in V = C + D,m \in M = A/C$. For each (a, b, c, d) ∈ A × B × C × D we have the (distinct) solution $(b,d,u,v,m) = (b,d,a + b,c + d,a/c)$, so there are at least | A | | B | | C | | D | solutions. On the other hand we can give an exact count via the exponential sum

$$\displaystyle{ \sum _{b,d,u,v,m}\frac{1} {p}\sum _{j=0}^{p-1}e\left (\frac{j(u - b - m(v - d))} {p} \right ) = \frac{\vert B\vert \vert D\vert \vert U\vert \vert V \vert \vert M\vert + \text{Error}} {p}, }$$

where

$$\displaystyle{ \vert \text{Error}\vert \leq \max _{i\neq 0}\left \vert \sum _{m\in M}\hat{D}\left (\frac{im} {p} \right )\hat{V }\left (\frac{-im} {p} \right )\right \vert \cdot \left \vert \sum _{j=1}^{p-1}\hat{U}\left (\frac{j} {p}\right )\hat{B}\left (\frac{-j} {p} \right )\right \vert. }$$

By Cauchy–Schwarz this gives

$$\displaystyle{ \vert \text{Error}\vert ^{2} \leq \sum _{ m\in M}\left \vert \hat{D}\left (\frac{im} {p} \right )\right \vert ^{2} \cdot \sum _{ m\in M}\left \vert \hat{V }\left (\frac{-im} {p} \right )\right \vert ^{2} \cdot \sum _{ j=1}^{p-1}\left \vert \hat{U}\left (\frac{j} {p}\right )\right \vert ^{2} \cdot \sum _{ j=1}^{p-1}\left \vert \hat{B}\left (\frac{-j} {p} \right )\right \vert ^{2} }$$

which is ≤ p | D | p | V | p | U | p | B | by (15). Hence we have proved

$$\displaystyle{ \vert A\vert \vert B\vert \vert C\vert \vert D\vert \leq \frac{\vert B\vert \vert D\vert \vert U\vert \vert V \vert \vert M\vert } {p} + p\sqrt{\vert B\vert \vert D\vert \vert U\vert \vert V \vert }, }$$

and the result follows. □ 

Theorem 6 ([17]).

Suppose that $A,B,C,D \subset \mathbb{F}_{p}$ , and A,C do not contain 0.

If $\vert A + B\vert \vert C + D\vert \vert B\vert \vert D\vert \ll p^{3}$ , then

$$\displaystyle{ \vert AC\vert ^{2}\vert A + B\vert \vert C + D\vert \gg (\vert A\vert \vert C\vert )^{2}\vert B\vert \vert D\vert /p. }$$

If $\vert A + B\vert \vert C + D\vert \vert B\vert \vert D\vert \gg p^{3}$ , then

$$\displaystyle{ \vert AC\vert \vert A + B\vert \vert C + D\vert \gg p\vert A\vert \vert C\vert. }$$

Remark.

We claim that these bounds can be obtained trivially if | A | | C | ( | B | | D | )² ≪ p ³: The second case cannot hold since

$$\displaystyle{ \vert A\vert \vert C\vert (\vert B\vert \vert D\vert )^{2} = \vert A\vert \vert B\vert \vert C\vert \vert D\vert \vert B\vert \vert D\vert \geq \vert A + B\vert \vert C + D\vert \vert B\vert \vert D\vert \gg p^{3}, }$$

but then $\vert AC\vert ^{2}\vert A+B\vert \vert C+D\vert \geq \vert A\vert \vert C\vert \ \vert A\vert ^{2/3}\vert B\vert ^{1/3}\ \vert C\vert ^{2/3}\vert D\vert ^{1/3} = (\vert A\vert \vert C\vert )^{2}\vert B\vert \vert D\vert /p\cdot (p^{3}/(\vert A\vert \vert C\vert (\vert B\vert \vert D\vert )^{2})^{1/3} \gg (\vert A\vert \vert C\vert )^{2}\vert B\vert \vert D\vert /p$.

Proof.

There exists m ∈ AC such that r _AC (m) ≥ | A | | C | ∕ | AC | . Now in the set

$$\displaystyle{ \{(u,v) \in (A + B) \times (C + D),\ (b,d) \in B \times D:\ (u - b)(v - d) = m\} }$$

we evidently have the distinct points $((a + b,c + d),(b,d))$ for every b ∈ B, d ∈ D, and a ∈ A, c ∈ C with ac = m; a total of | B | | D | r _AC (m) ≥ | A | | B | | C | | D | ∕ | AC | points. To get an exact count, write $U = A + B,\ V = C + D$, to obtain

$$\displaystyle\begin{array}{rcl} & & \sum _{b,d,u,v}\sum _{\begin{array}{c}r,s \\ rs=m\end{array}}\frac{1} {p}\sum _{i}e\left (\frac{i(u - b - r)} {p} \right ) \cdot \frac{1} {p}\sum _{j}e\left (\frac{j(v - d - s)} {p} \right ) {}\\ & =& \frac{1} {p^{2}}\sum _{i,j}\hat{U}\left ( \frac{i} {p}\right )\hat{B}\left (\frac{-i} {p} \right )\hat{V }\left (\frac{j} {p}\right )\hat{D}\left (\frac{-j} {p} \right )\sum _{\begin{array}{c}r,s \\ rs=m\end{array}}e\left (\frac{-(ir + js)} {p} \right ). {}\\ \end{array}$$

The $i = j = 0$ term yields $\frac{p-1} {p^{2}} \vert U\vert \vert B\vert \vert V \vert \vert D\vert$, since there are exactly p − 1 solutions to rs = m. If j = 0 but i ≠ 0, then our final sum equals − 1, so that the sum over i ≠ 0 is $\frac{1} {p^{2}} \vert V \vert \vert D\vert (\vert U\vert \vert B\vert - p\vert U \cap B\vert )$. Similarly with i = 0. Finally if i ≠ 0 and j ≠ 0, then the final term is $\leq 2\sqrt{p}$ in absolute value by a well-known result on Kloosterman sums, and the total contribution is therefore

$$\displaystyle{ \leq \frac{2} {p^{3/2}}\sum _{i\neq 0}\left \vert \hat{U}\left ( \frac{i} {p}\right )\hat{B}\left (\frac{-i} {p} \right )\right \vert \ \sum _{j\neq 0}\left \vert \hat{V }\left (\frac{j} {p}\right )\hat{D}\left (\frac{-j} {p} \right )\right \vert, }$$

and by Cauchying the square of this is

$$\displaystyle{ \leq \frac{4} {p^{3}}\sum _{i}\left \vert \hat{U}\left ( \frac{i} {p}\right )\right \vert ^{2}\sum _{ i}\left \vert \hat{B}\left (\frac{-i} {p} \right )\right \vert ^{2}\ \sum _{ j}\left \vert \hat{V }\left (\frac{j} {p}\right )\right \vert ^{2}\ \sum _{ j}\left \vert \hat{D}\left (\frac{-j} {p} \right )\right \vert ^{2}=4p\vert U\vert \vert B\vert \vert D\vert \vert V \vert. }$$

Putting this altogether we obtain

$$\displaystyle{ \frac{\vert A\vert \vert B\vert \vert C\vert \vert D\vert } {\vert AC\vert } \leq \frac{p + 1} {p^{2}} \vert U\vert \vert B\vert \vert V \vert \vert D\vert + 2\sqrt{p\vert U\vert \vert B\vert \vert D\vert \vert V \vert }, }$$

which implies the result. □ 

Corollary 3.4.

Suppose that $0\not\in A \subset \mathbb{F}_{p}$ . If $\vert A + A\vert \vert A\vert \ll p^{3/2}$ , then

$$\displaystyle{ \vert AA\vert \vert A + A\vert \gg \vert A\vert ^{3}/\sqrt{p}. }$$

If $\vert A + A\vert \vert A\vert \gg p^{3/2}$ , then

$$\displaystyle{ \vert AA\vert \vert A + A\vert ^{2} \gg p\vert A\vert ^{2}. }$$

This is only non-trivial if | A | ≫ p ^1∕2.

4 Ruzsa–Plunnecke Type Inequalities

We begin with a key result of Ruzsa:

Proposition 4.1.

If $X,A_{1},\ldots,A_{k} \subset \mathbb{F}_{p}$ , then there exists a non-empty $Y \subset X$ such that

$$\displaystyle{ \frac{\vert Y + A_{1} +\ldots +A_{k}\vert } {\vert Y \vert } \leq \prod _{i=1}^{k}\ \frac{\vert X + A_{i}\vert } {\vert X\vert }. }$$

Corollary 4.2.

If $A,B,C \subset \mathbb{F}_{p}$ , then

$$\displaystyle{ \vert A \pm B\vert \leq \frac{\vert A + C\vert \vert B + C\vert } {\vert C\vert }. }$$

Proof.

We can define an injective map $\phi: (A - B) \times C \rightarrow (A + C) \times (B + C)$ as follows, so that the inequality $\vert A - B\vert \leq \vert A + C\vert \vert B + C\vert /\vert C\vert$ holds: If $\lambda \in A - B$, fix $a_{\lambda } \in A,\ b_{\lambda } \in B$ such that $\lambda = a_{\lambda } - b_{\lambda }$ and then define $\phi (\lambda,c) = (a_{\lambda } + c,b_{\lambda } + c)$. The map is injective since if $u = a_{\lambda } + c$ and $v = b_{\lambda } + c$ then $\lambda = u - v$ and then $c = u - a_{\lambda }$.

For the other case take $k = 2,A_{1} = A,A_{2} = B,X = C$ in Proposition 4.1 to obtain that there exists non-empty $Y \subset C$ such that

$$\displaystyle{ \vert A + B\vert \leq \vert Y + A + B\vert \leq \frac{\vert A + C\vert } {\vert C\vert } \cdot \frac{\vert B + C\vert } {\vert C\vert } \cdot \vert Y \vert \leq \frac{\vert A + C\vert } {\vert C\vert } \cdot \frac{\vert B + C\vert } {\vert C\vert } \cdot \vert C\vert. }$$

 □ 

Corollary 4.3.

If $X,A_{1},\ldots,A_{k} \subset \mathbb{F}_{p}$ , then there exists $Z \subset X$ such that $\vert Z\vert \geq \frac{1} {2}\vert X\vert$ and

$$\displaystyle{ \frac{\vert Z + A_{1} +\ldots +A_{k}\vert } {\vert Z\vert } \leq 2^{k}\prod _{ i=1}^{k}\ \frac{\vert X + A_{i}\vert } {\vert X\vert }. }$$

Proof.

By Proposition 4.1 we know that there exists a set $Z \subset X$ for which the inequality holds, so let $Z^{{\prime}}$ be the largest subset of X for which this inequality is satisfied and suppose that $\vert Z^{{\prime}}\vert \leq \frac{1} {2}\vert X\vert$. Apply Corollary 4.2 with $X^{{\prime}} = X\setminus Z^{{\prime}}$ in place of X. Noting that $\vert X^{{\prime}}\vert > \vert X\vert /2$, and each $\vert X^{{\prime}} + A_{i}\vert \leq \vert X + A_{i}\vert$ we deduce that there exists a non-empty $Y \subset X^{{\prime}}$ such that $\vert Y + A_{1} +\ldots +A_{k}\vert < 2^{k}\vert Y \vert \prod _{i=1}^{k}(\vert X + A_{i}\vert /\vert X\vert ).$ Now let $Z = Z^{{\prime}}\cup Y$ so that $\vert Z + A_{1} +\ldots +A_{k}\vert \leq \vert Z^{{\prime}} + A_{1} +\ldots +A_{k}\vert + \vert Y + A_{1} +\ldots +A_{k}\vert$, which is $\leq 2^{k}\prod _{i=1}^{k}(\vert X + A_{i}\vert /\vert X\vert )$ times $\vert Y \vert + \vert Z^{{\prime}}\vert = \vert Z\vert$, and thus our inequality is satisfied by Z which is larger than $Z^{{\prime}}$, contradicting the hypothesis. □ 

Corollary 4.4.

For any $a,b \in \mathbb{F}_{p}^{{\ast}}$ and $A,B \subset \mathbb{F}_{p}$ we have

$$\displaystyle{ \vert aA \pm bB\vert \leq \frac{\vert A + A\vert \vert B + B\vert } {\vert aA \cap bB\vert }, }$$

and

$$\displaystyle{ \vert aA \pm bB\vert \leq \frac{\vert A + A\vert \vert B + B\vert } {\max _{n\in \mathbb{F}_{p}}r_{aA+bB}(n)}. }$$

Proof.

In Corollary 4.2 replace A by aA, B by bB, and take $C = (x + aA) \cap bB$ for some $x \in \mathbb{F}_{p}$. We note that $aA + C \subset x + aA + aA$ which has the same size as A + A and, similarly, $bB + C \subset bB + bB$ which has the same size as B + B. The first result follows taking x = 0. Now $\vert C\vert = r_{bB-aA}(x)$, so writing $x = -n$ and changing b to − b, we get our second result. □ 

Corollary 4.5.

For any $a,b \in \mathbb{F}_{p}^{{\ast}}$ and $A,B \subset \mathbb{F}_{p}$ we have

$$\displaystyle{ \vert aA \pm bB\vert \leq \frac{\vert A + B\vert ^{2}} {\vert bA \cap aB\vert }, }$$

and

$$\displaystyle{ \vert aA \pm bB\vert \leq \frac{\vert A + B\vert ^{2}} {\max _{n\in \mathbb{F}_{p}}r_{aB+bA}(n)}. }$$

Proof.

In Corollary 4.2 now replace A by aA, B by bB, and take $C = (x + bA) \cap aB$ for some $x \in \mathbb{F}_{p}$. We note that $aA + C \subset aA + aB$ which has the same size as A + B and, similarly, $bB + C \subset x + bB + bA$ which also has the same size as A + B. The first result follows taking x = 0. Now $\vert C\vert = r_{aB-bA}(x)$, so changing b to − b, we get our second result □ 

5 Lower Bounds on the Size of A + tB

Lemma 5.1.

If $A,B \subset \mathbb{F}_{p}$ with |A||B| > p, then $\frac{A-A} {B-B} = \mathbb{F}_{p} \cup \{\infty \}$ .

Proof.

As | A | | B |  > p and each of | A | , | B | ≤ p hence | A | , | B |  > 1, that is, | A | , | B | ≥ 2. Hence $0 = (a - a)/(b_{1} - b_{2})$ and $\infty = (a_{1} - a_{2})/(b - b)$. If t ≠ 0, then there are | A | | B |  > p numbers a + tb so that two must be congruent mod p. Taking their difference implies the result. □ 

Remark.

One might expect that if $A,B \subset \mathbb{F}_{p}$ with | A | | B |  > p then $AB + AB = \mathbb{F}_{p}$. However if $A = B =\{ m\pmod p: (m/p) = 1\}$ where p is a prime $\equiv 3\pmod 4$, then evidently 0 ∉ AB + AB (and here $\vert A\vert,\vert B\vert = (p - 1)/2$). Hence the best we can hope for is that if | A | | B |  > p then $AB + AB + AB = \mathbb{F}_{p}$, and perhaps $AB + AB = \mathbb{F}_{p}^{{\ast}}$.

Glibichuk [14] proved that if | A | | B | ≥ 2p then $8AB = \mathbb{F}_{p}$ (so that if | A | | B | ≥ p then $8AB = \mathbb{F}_{p}$, since then | A + A | | B | ≥ 2p so that $16AB \supseteq 8(A + A)B = \mathbb{F}_{p}$, unless A is an arithmetic progression, which can be handled).

Let $T = \frac{A-A} {B-B}\setminus \{0,\infty \}$. We are interested in the size of A + tB when | A | , | B |  > 1. Evidently | A + tB | ≤ | A |   | B | with equality if and only if $t\not\in T \cup \{ 0\}$.

Let R(t) = R _A, B (t) denote the number of solutions a, c ∈ A,  b, d ∈ B to $a + tb = c + td$. We always have the the “diagonal solutions” where a = c and b = d to $a + tb = c + td$, so that R(t) ≥ | A | | B | . Equality holds, that is, R(t) =  | A | | B | , if and only if $t\not\in T \cup \{ 0\}$. Hence

$$\displaystyle{ \vert A + tB\vert = \vert A\vert \ \vert B\vert \ \Longleftrightarrow\ t\not\in T \cup \{ 0\}\ \Longleftrightarrow\ R(t) = \vert A\vert \vert B\vert. }$$

(18)

There is a link between | A + tB | that holds no matter what, which is given by the Cauchy–Schwarz inequality: Let $r_{t}(n) = \#\{a \in A,\ b \in B:\ n = a + tb\}$ so that

$$\displaystyle{ (\vert A\vert \ \vert B\vert )^{2} = \left (\sum _{ n\in A+tB}r_{t}(n)\right )^{2} \leq \vert A + tB\vert \ R_{ A,B}(t), }$$

(19)

since $R_{A,B}(t) =\sum _{n}r_{t}(n)^{2}$.

Proposition 5.2.

For any finite sets A,B,S with 0∉S, there exists t ∈ S for which

$$\displaystyle{ \vert A + tB\vert > \frac{1} {2}\ \min \{\vert S\vert,\vert A\vert \ \vert B\vert \}. }$$

If $A,B \in \mathbb{F}_{p}$ , then we also have

$$\displaystyle{ \vert A + tB\vert > \frac{1} {2}\ \min \left \{p, \frac{\vert A\vert \ \vert B\vert \ \vert S\vert } {p} \right \}. }$$

Proof.

Note that $\vert A + 0B\vert = \vert A\vert$ and R(0) =  | A |   | B | ². Since R(t) ≥ | A | | B | for all t hence

$$\displaystyle\begin{array}{rcl} \sum _{t\in S}(R(t) -\vert A\vert \vert B\vert )& \leq & \sum _{t\not =0}(R(t) -\vert A\vert \vert B\vert ) = \#\{a,c \in A,\ b,d \in B:\ b\neq d\ \text{and}\ a\neq c\} \\ & =& (\vert A\vert ^{2} -\vert A\vert )(\vert B\vert ^{2} -\vert B\vert ). {}\end{array}$$

(20)

Therefore there exists t ∈ S with

$$\displaystyle{ R(t) \leq \frac{(\vert A\vert ^{2} -\vert A\vert )(\vert B\vert ^{2} -\vert B\vert )} {\vert S\vert } + \vert A\vert \ \vert B\vert < 2\vert A\vert \vert B\vert \max \left \{\frac{\vert A\vert \vert B\vert } {\vert S\vert },1\right \}, }$$

whence, by (19),

$$\displaystyle{ \vert A\vert \ \vert B\vert \leq 2\vert A + tB\vert \ \max \left \{\frac{\vert A\vert \vert B\vert } {\vert S\vert },1\right \} }$$

and so the first result follows.

When we are working mod p, we have

$$\displaystyle{ R(t) =\sum _{n}r_{t}(n)^{2} = \frac{1} {p}\sum _{j=0}^{p-1}\vert \hat{A}(j/p)\vert ^{2}\vert \hat{B}(jt/p)\vert ^{2} \geq \frac{(\vert A\vert \ \vert B\vert )^{2}} {p}, }$$

taking the j = 0 term, since every term is non-negative. If | A | | B |  > p, then R(t) >  | A |   | B | and so $T = \mathbb{F}_{p}\setminus \{0\}$ by (18) giving another proof of the lemma above.

Now, rearranging (20) we obtain

$$\displaystyle{ \sum _{t\in S}\!\left (\!R(t) -\frac{(\vert A\vert \ \vert B\vert )^{2}} {p} \!\right )\! \leq \sum _{t\not =0}\left (\!R(t) -\frac{(\vert A\vert \ \vert B\vert )^{2}} {p} \!\right ) = p\vert A\vert \vert B\vert \left (1 -\frac{\vert A\vert } {p} \right )\left (\!1 -\frac{\vert B\vert } {p} \!\right )\!, }$$

so there exists t ∈ S with

$$\displaystyle{ \vert A\vert \ \vert B\vert \leq 2\vert A + tB\vert \ \max \left \{ \frac{p} {\vert S\vert }, \frac{\vert A\vert \ \vert B\vert } {p} \right \} }$$

by (19), and the result follows. □ 

Corollary 5.3.

Suppose that |A|,|B|≥ 2. If $\frac{A-A} {B-B} = \mathbb{F}_{p}$ , then there exist a ₁ ,a ₂ ∈ A,b ₁ ,b ₂ ∈ B such that

$$\displaystyle{ \vert (a_{1} - a_{2})B + (b_{1} - b_{2})A\vert > \frac{1} {2}\ \min \left \{p,\vert A\vert \ \vert B\vert \right \}. }$$

If $\frac{A-A} {B-B}\neq \mathbb{F}_{p}$ , then there exist a ₁ ,a ₂ ∈ A,b ₁ ,b ₂ ∈ B such that

$$\displaystyle{ \vert (a_{1} - a_{2} + b_{1} - b_{2})B + (b_{1} - b_{2})A\vert = \vert A\vert \ \vert B\vert. }$$

In other words, the elements $(a_{1} - a_{2} + b_{1} - b_{2})b + (b_{1} - b_{2})a$ with a ∈ A,b ∈ B, are distinct.

Proof.

For any t ∈ T, there exist a ₁, a ₂ ∈ A, b ₁, b ₂ ∈ B, for which $(a_{2} - a_{1}) + (b_{1} - b_{2})t = 0$. The first case follows immediately from Proposition 5.2 by multiplying through by b ₁ − b ₂.

Suppose that $T\neq \mathbb{F}_{p}^{{\ast}}$. Now T contains a non-zero element, say t, since A has at least two elements. Moreover we may assume 1 ≤ t < p∕2 since $T = -T$ (as may be seen by swapping a ₁ and a ₂). Hence there exists t ∈ T such that t + 1 ∉ T. Therefore $\vert A + (t + 1)B\vert = \vert A\vert \vert B\vert$ by (18) and the result follows by multiplying through by b ₁ − b ₂. □ 

Lemma 5.4.

Let $I(A,B):= (B - B)A + (A - A)B$.

• (i) If $t \in \frac{A-A} {B-B}$ , then |I(A,B)|≥|A + tB|.

• (ii) $AB - AB \subset I(A,B)$ , so that $\vert I(A,B)\vert \geq \min \{ p,2\vert AB\vert - 1\}$ .

Proof.

There exist a ₁, a ₂ ∈ A,  b ₁, b ₂ ∈ B for which $(a_{2} - a_{1}) + (b_{1} - b_{2})t = 0$. Each element of $S = (b_{1} - b_{2})(A + tB)$ can be written as $(b_{1} - b_{2})a + (b_{1} - b_{2})tb = (b_{1} - b_{2})a + (a_{1} - a_{2})b \in I(A,B)$ and (i) follows. Also if a ₁, a ₂ ∈ A,  b ₁, b ₂ ∈ B, then $a_{1}b_{1} - a_{2}b_{2} = (b_{1} - b_{2})a_{1} + (a_{1} - a_{2})b_{2} \in I(A,B)$, that is, $AB - AB \subset I(A,B)$, and (ii) follows from the Cauchy–Davenport theorem. □ 

Corollary 5.5.

If |A||B| > p, then there exists t ∈ T for which $\vert A + tB\vert > p/2$ . Hence |I(A,B)| > p∕2. We can rephrase this as: There exist b ₁ ,b ₂ ∈ B,a ₁ ,a ₂ ∈ A such that $\vert (b_{1} - b_{2})A + (a_{1} - a_{2})B\vert > p/2$ .

Proof.

By Lemma 5.1 we know that $\frac{A-A} {B-B} = \mathbb{F}_{p}$. Taking S = T in Proposition 5.2 we deduce that there exists t ∈ T with $\vert A + tB\vert > p/2$. The result then follows from Lemma 5.4. □ 

Proposition 5.6.

Let R _k (B) be the set of $n \in \mathbb{F}_{p}$ for which r _B∕B (n) ≥ k for 1 ≤ k ≤|B|; note that 1 ∈ R _k (B). Let G _k (B) be the multiplicative group generated by R _k (B), and then $H_{k}(B) = G_{k}(B)\frac{A-A} {B-B}$ . There exists t ∈ T for which $\vert A + tB\vert \gg \min \{ k\vert A\vert,\vert H_{k}\vert \}$ .

Proof.

If $H_{k}(B) = \frac{A-A} {B-B}$, then the result follows from Proposition 5.2 (since | B | ≥ k). Otherwise $\frac{A-A} {B-B} \subsetneq H_{k}(B)$ so there exist g ∈ G _k (B) and t ₀ ∈ T such that gt ₀ ∉ T. Now any g ∈ G _k (B) can be written as g = n ₁ n ₂ … n _ℓ where each n _j  ∈ R _k (B). Define $t_{j} = n_{j}t_{j-1}$ for each j, so that t ₀ ∈ T and t _ℓ  = gt ₀ ∉ T: hence there exist $t = t_{j-1} \in T$ and n = n _j  ∈ R _k (B) such that nt = t _j  ∉ T. But then $\vert A + ntB\vert = \vert A\vert \vert B\vert$ by (18); that is, the elements of A + ntB are all distinct. Now r _B∕B (n) ≥ k by the definition of R _k (B), and so there are at least k values of b ∈ B for which nb is also in B, and hence A + tB contains at least | A | k distinct elements. □ 

Lemma 5.7.

Let $B = B_{1} \cup B_{2}$ be a partition of B where b ₁ ∕b ₂ ∉G _k for any b ₁ ∈ B ₁ ,b ₂ ∈ B ₂ . Then |B ₁ ||B ₂ |≤ (k − 1)|B ₁ B ₂ |.

Proof.

If s ∉ B ₁∕B ₂, then $r_{B_{1}/B_{2}}(s) = 0$. If s ∈ B ₁∕B ₂, then s ∉ G _k by hypothesis, so that s ∉ R _k and hence $r_{B_{1}/B_{2}}(s) \leq r_{B/B}(s) < k$. Therefore

$$\displaystyle\begin{array}{rcl} (\vert B_{1}\vert \vert B_{2}\vert )^{2}& =& \left (\sum _{ s}r_{B_{1}B_{2}}(s)\right )^{2} \leq \vert B_{ 1}B_{2}\vert \sum _{s}r_{B_{1}B_{2}}(s)^{2} = \vert B_{ 1}B_{2}\vert \sum _{s}r_{B_{1}/B_{2}}(s)^{2} {}\\ & \leq & \vert B_{1}B_{2}\vert (k - 1)\sum _{s}r_{B_{1}/B_{2}}(s) = \vert B_{1}B_{2}\vert (k - 1)\vert B_{1}\vert \vert B_{2}\vert. {}\\ \end{array}$$

 □ 

Lemma 5.8.

Let $k = \vert B\vert ^{2}/100\vert BB\vert$ . There exists h ≠ 0 for which $\vert B \cap hG_{k}(B)\vert \geq \frac{49} {50}\vert B\vert$ .

Proof.

Let H be the set of cosets of G _k in $\mathbb{F}_{p}^{{\ast}}$. For any partition $H = H_{1} \cup H_{2}$ let $B_{j}:= \cup _{h\in H_{j}}(B \cap hG_{k})\vert$ for j = 1, 2 so that $B_{1} \cup B_{2}$ is a partition of B; note that $b_{1}/b_{2} \in (h_{1}/h_{2})G_{k}$ for some h ₁ ∈ H ₁, h ₂ ∈ H ₂ so that h ₁ ≠ h ₂ and thus b ₁∕b ₂ ∉ G _k . Now $\vert B_{1}\vert (\vert B\vert -\vert B_{1}\vert ) = \vert B_{1}\vert \vert B_{2}\vert < k\vert B_{1}B_{2}\vert < k\vert BB\vert = \frac{\vert B\vert ^{2}} {100}$ by Lemma 5.7, and so either | B ₁ | or | B ₂ | is $> \frac{49} {50}\vert B\vert$.

Now let H ₁ be a maximal subset of H such that | B ₁ |  <  | B | ∕50. Therefore for any h ∈ H ₂ we must have $\vert B_{1} \cup (B \cap hG_{k})\vert \geq \vert B\vert /50$ and hence $> \frac{49} {50}\vert B\vert$ by the previous paragraph, so that $\vert B \cap hG_{k}\vert \geq \frac{24} {25}\vert B\vert$. We deduce H ₂ has no more than one element, and thus exactly one element (since | B ₂ |  > 0). The result follows. □ 

Lemma 5.9.

Let $C \subset G$ , a subgroup of $\mathbb{F}_{p}^{{\ast}}$ , with $1 < \vert C\vert < \sqrt{p}$ . Then we have $\vert G(C - C)\vert \gg \vert C\vert ^{3/2}$ and $\vert G\vert \cdot \vert C - C\vert \gg \vert C\vert ^{5/2}$ .

Proof.

First note that | G(C − C) | ≥ | G | and | C − C | ≥ | C | so the results follow unless | C | ≥ 2 and | G | ≤ | C | ^3∕2, which we now assume.

Now, GS is a union of cosets of G for any set $S \in \mathbb{F}_{p}^{{\ast}}$, so we can write

$$\displaystyle{ G(C - C) =\{ 0\} \cup \cup _{i=1}^{m}t_{ i}G, }$$

where we order these cosets of G so that $r_{G-G}(t_{1}) \geq r_{G-G}(t_{2}) \geq \ldots \geq r_{G-G}(t_{m})$ (note that r _G−G (t _i ) takes the same value for any choice of t _i inside a fixed coset of G). Since $\vert G(C - C)\vert = \vert G\vert m + 1$, the first result follows unless $m \leq M:= [\vert C\vert ^{3/2}/\vert G\vert ]$.

If J ≤ M, then $J\vert G\vert ^{4} \leq M\vert G\vert ^{4} \leq \vert G\vert ^{3}\vert C\vert ^{3/2} \leq \vert C\vert ^{9/2}\vert C\vert ^{3/2} = \vert C\vert ^{6} \leq p^{3}$. Therefore

$$\displaystyle{ Jr_{G-G}(t_{J}) \leq \sum _{i=1}^{J}r_{ G-G}(t_{i}) \leq 4(J\vert G\vert )^{2/3} }$$

(21)

by Lemma 5 of [18] (with the constant ‘4’ made explicit) and so

$$\displaystyle{ \vert G(C - C)\vert > m\vert G\vert \geq \frac{1} {8}\left (\sum _{i=1}^{m}r_{ G-G}(t_{i})\right )^{3/2}. }$$

(22)

For any fixed c ₀ ∈ C the solutions to $h_{1} - h_{2} = t_{i}$ with h ₁, h ₂ ∈ G are in 1–1 correspondence with the solutions $h_{3} - c_{0} = t_{i}h_{4}$ with h ₃, h ₄ ∈ G, as may be seen by taking $h_{3} = h_{1}c_{0}/h_{2}$ and $h_{4} = c_{0}/h_{2}$. Hence

$$\displaystyle{ r_{G-G}(t_{i}) =\sum _{t\in t_{i}G}r_{G-c_{0}}(t) \geq \sum _{t\in t_{i}G}r_{C-c_{0}}(t). }$$

(23)

We then deduce

$$\displaystyle{ \sum _{i=1}^{m}r_{ G-G}(t_{i}) \geq \sum _{t\in (C-C)G\setminus \{0\}}r_{C-c_{0}}(t) = \vert C\vert - 1, }$$

and the first result follows from (22).

We now prove the second result, no longer assuming that m ≤ M: Since $r_{C-C}(t) \leq r_{G-G}(t) = r_{G-G}(t_{i})$ for all t ∈ t _i G, we have

$$\displaystyle{ \sum _{t\in t_{i}G}r_{C-C}(t)^{2} \leq r_{ G-G}(t_{i})\sum _{t\in t_{i}G}r_{C-C}(t) \leq r_{G-G}(t_{i})\sum _{c_{0}\in C}\sum _{t\in t_{i}G}r_{C-c_{0}}(t) \leq \vert C\vert r_{G-G}(t_{i})^{2} }$$

by (23). Therefore, using (21) for the bound $r_{G-G}(t_{J}) \leq 4\vert G\vert ^{2/3}/\min \{J,M\}^{1/3}$, we obtain

$$\displaystyle\begin{array}{rcl} \sum _{t\neq 0}r_{C-C}(t)^{2}& =& \sum _{ i=1}^{M}\sum _{ t\in t_{i}G}r_{C-C}(t)^{2} +\sum _{ i=M+1}^{m}\sum _{ t\in t_{i}G}r_{C-C}(t)^{2} {}\\ & \leq & \sum _{i=1}^{M}\vert C\vert r_{ G-G}(t_{i})^{2} +\sum _{ i=M+1}^{m}r_{ G-G}(t_{i})\sum _{t\in t_{i}G}r_{C-C}(t) {}\\ & \leq & \vert C\vert \sum _{i=1}^{M}16\vert G\vert ^{4/3}i^{-2/3} + 4\vert G\vert ^{2/3}M^{-1/3}\sum _{ i=M+1}^{m}\sum _{ t\in t_{i}G}r_{C-C}(t) {}\\ & \leq & 48\vert C\vert \vert G\vert ^{4/3}M^{1/3} + 4\vert C\vert ^{2}\vert G\vert ^{2/3}M^{-1/3} \asymp 52\vert C\vert ^{3/2}\vert G\vert. {}\\ \end{array}$$

Hence

$$\displaystyle{ (\vert C\vert ^{2} -\vert C\vert )^{2} = \left (\sum _{ t\neq 0}r_{C-C}(t)\right )^{2} \leq \vert C - C\vert \sum _{ t\neq 0}r_{C-C}(t)^{2} \ll \vert C - C\vert \vert C\vert ^{3/2}\vert G\vert, }$$

and the result follows. □ 

Theorem 7.

If $\vert A\vert < \sqrt{p}$ , then |I(A,A)|≫|A| ^3∕2 .

Proof.

We have | I(A, A) | ≥ 2 | AA | − 1 by Lemma 5.4(ii), and the result follows unless | AA | ≪ | A | ^3∕2, which we now assume.

Let $k = \vert A\vert ^{2}/100\vert AA\vert$ ( ≫ | A | ^1∕2), and define R _k (A), G _k (A), H _k (A) as above. By Lemma 5.8 there exists h ≠ 0 such that if $C =\{ g \in G_{k}(A):\ gh \in A\} = G_{k} \cap h^{-1}A$, then

$$\displaystyle{ \vert C\vert = \vert A \cap hG_{k}(A)\vert \geq \frac{49} {50}\vert A\vert. }$$

Therefore, using the fact that $H = G(A - A)/(A - A)$ we have

$$\displaystyle{ \vert H\vert + 1 \geq \vert G(A - A)\vert \geq \vert G(hC - hC)\vert = \vert G(C - C)\vert \gg \vert C\vert ^{3/2} \gg \vert A\vert ^{3/2} }$$

by Lemma 5.9. The result follows by Lemma 5.4 and Proposition 5.6 since now $\vert I(A,A)\vert \gg \min \{ k\vert A\vert,\vert H_{k}\vert \}\gg \vert A\vert ^{3/2}.$ □ 

Theorem 8.

We have

$$\displaystyle{ E_{\times }(A,A) \leq 4\vert A + A\vert ^{2}\max \left \{\frac{\vert A\vert ^{2}} {p}, \frac{p} {\vert A\vert }\right \}\log \vert A\vert, }$$

and

$$\displaystyle{ E_{\times }(A,A)^{4} < 32\vert A + A\vert ^{8}\vert A\vert ^{2}\max \left \{\frac{\vert A\vert ^{3}} {p},2\vert A + A\vert \right \}(\log \vert A\vert )^{4}. }$$

If $\vert A\vert \leq \sqrt{p}$, then $\vert A\vert ^{3}/p \leq \vert A\vert \leq \vert A + A\vert$, so the above becomes $E_{\times }(A,A)^{4} < 64\vert A + A\vert ^{9}\vert A\vert ^{2}(\log \vert A\vert )^{4}$. This yields a sum-product bound which is non-trivial for all $\vert A\vert \leq \sqrt{p}$:

Corollary 5.10.

We have

$$\displaystyle{ E_{\times }(A,B) \leq 4\vert A + A\vert \vert B + B\vert \log (\vert A\vert \vert B\vert )\left (\max \left \{\frac{\vert A\vert ^{2}} {p}, \frac{p} {\vert A\vert }\right \}\max \left \{\frac{\vert B\vert ^{2}} {p}, \frac{p} {\vert B\vert }\right \}\right )^{1/2}, }$$

and

$$\displaystyle\begin{array}{rcl} E_{\times }(A,B)^{8} < 2^{10}(\vert A + A\vert \vert B + B\vert \log \vert A\vert \vert B\vert )^{8}(\vert A\vert \vert B\vert )^{2}\max \left \{\frac{\vert A\vert ^{3}} {p},2\vert A + A\vert \right \}& & {}\\ \times \max \left \{\frac{\vert B\vert ^{3}} {p},2\vert B + B\vert \right \}& &, {}\\ \end{array}$$

which implies that if |A|,|B|≤ p ^1∕2 then

$$\displaystyle{ \vert AB\vert ^{8}(\vert A + A\vert \vert B + B\vert )^{9} > \frac{(\vert A\vert \vert B\vert )^{14}} {2^{12}(\log \vert A\vert \vert B\vert )^{8}}, }$$

Proof.

By the Cauchy–Schwarz inequality we have

$$\displaystyle{ E_{\times }(A,B)^{2} = \left (\sum _{ n}r_{A/A}(n)r_{B/B}(n)\right )^{2} \leq \sum _{ m}r_{A/A}(m)^{2}\sum _{ n}r_{B/B}(n)^{2} = E_{ \times }(A,A)E_{\times }(B,B) }$$

and then the first two results follow from Theorem 8. Now, if | A | , | B | ≤ p ^1∕2, then $\vert A\vert ^{3}/p \leq \vert A\vert < \vert A + A\vert$. Therefore, by the second inequality and (7), we obtain our third and final inequality □ 

If | A | , | B | ≥ p ^2∕3, then by the first inequality in Corollary 5.10, and (7), we obtain

$$\displaystyle{ \vert A + A\vert \vert B + B\vert \vert AB\vert \geq \frac{p\vert A\vert \vert B\vert } {4\log (\vert A\vert \vert B\vert }. }$$

which is weaker than Theorem 4.

Corollary 5.11.

If $4p^{4}/\vert A\vert ^{6} \geq \vert A + A\vert > \vert A\vert ^{3}/2p$ and |A|≤ 2p ^5∕9 , then

$$\displaystyle{ \vert AA\vert ^{4}\vert A + A\vert ^{9} \geq \frac{\vert A\vert ^{14}} {2^{6}(\log \vert A\vert )^{4}} }$$

If $\vert A + A\vert \leq \vert A\vert ^{3}/2p$ and $p^{1/2} \leq \vert A\vert \leq p^{5/9}$ , then

$$\displaystyle{ \vert AA\vert \vert A + A\vert ^{2} \geq \frac{\vert A\vert ^{11/4}p^{1/4}} {2^{5/4}\log \vert A\vert } }$$

Proof.

This follows by Theorem 8 and (7) with B = A, which gives

$$\displaystyle{ \vert A\vert ^{4} \leq \vert AA\vert E_{ \times }(A,A). }$$

 □ 

Proof of Theorem 8.

We begin by noting that

$$\displaystyle{ E_{\times }(A,A) =\sum _{b\in A}\sum _{k=0}^{[\log \vert A\vert ]}\sum _{ \begin{array}{c}a\in A \\ 2^{k}\leq \vert aA\cap bA\vert <2^{k+1}\end{array}}\vert aA \cap bA\vert }$$

where the logarithm here is in base 2. Hence there exists 2^k ≤ | A | for which there is $A_{1} \subset A$ and b ₀ ∈ A such that

$$\displaystyle{ 2^{k} \leq \vert aA \cap b_{ 0}A\vert < 2^{k+1} }$$

for every a ∈ A ₁, where $\vert A_{1}\vert 2^{k+1} \geq E_{\times }(A,A)/(\vert A\vert \log \vert A\vert )$.

By Proposition 5.2 with S = A ₁ there exists a ∈ A ₁ such that

$$\displaystyle{ \vert aA - b_{0}A\vert \geq \frac{1} {2}\min \{p,\vert A\vert ^{2}\vert A_{ 1}\vert /p\}; }$$

and $\vert aA - b_{0}A\vert \leq \vert A + A\vert ^{2}/\vert aA \cap b_{0}A\vert$ by Corollary 4.4. Hence

$$\displaystyle{ \vert A + A\vert ^{2} \geq \frac{E_{\times }(A,A)} {4\log \vert A\vert } \ \min \left \{ \frac{p} {\vert A_{1}\vert \vert A\vert }, \frac{\vert A\vert } {p} \right \}, }$$

and the first result follows.

If $\frac{A_{1}-A_{1}} {A_{1}-A_{1}} = \mathbb{F}_{p}$, then by Corollary 5.3 there exist a ₁, a ₂, a ₃, a ₄ ∈ A ₁ such that

$$\displaystyle{ \vert (a_{1} - a_{2})A_{1} + (a_{3} - a_{4})A_{1}\vert > \frac{1} {2}\ \min \left \{p,\vert A_{1}\vert ^{2}\right \}; }$$

By Proposition 4.1 we have $Y \subseteq b_{0}A$ such that

$$\displaystyle\begin{array}{rcl} \vert (a_{1} - a_{2})A + (a_{3} - a_{4})A\vert & \leq & \vert Y + a_{1}A - a_{2}A + a_{3}A - a_{4}A\vert \leq \vert Y \vert \prod _{i=1}^{4}\frac{\vert a_{i}A \pm b_{0}A\vert } {\vert b_{0}A\vert } {}\\ &\leq & \vert b_{0}A\vert \prod _{i=1}^{4} \frac{\vert A + A\vert ^{2}} {\vert b_{0}A\vert \ \vert a_{i}A \cap b_{0}A\vert } \leq \frac{\vert A + A\vert ^{8}} {\vert A\vert ^{3}\ 2^{4k}} {}\\ \end{array}$$

using Corollary 4.4. Hence

$$\displaystyle{ \vert A + A\vert ^{8} > \frac{(\vert A_{1}\vert 2^{k+1})^{4}} {32} \ \min \left \{p/\vert A\vert,\vert A\vert \right \}, }$$

and so $E_{\times }(A,A)^{4} \leq 32\vert A + A\vert ^{8}\vert A\vert ^{3}(\log \vert A\vert )^{4}\max \left \{1,\vert A\vert ^{2}/p\right \}$.

If $\frac{A_{1}-A_{1}} {A_{1}-A_{1}} \neq \mathbb{F}_{p}$, then by Corollary 5.3 there exist a ₁, a ₂, a ₃, a ₄ ∈ A ₁ such that if $A_{2} \subset A_{1}$ then

$$\displaystyle{ \vert (a_{1} - a_{2})A_{2} + (a_{1} - a_{2} + a_{3} - a_{4})A_{1}\vert = \vert A_{1}\vert \ \vert A_{2}\vert. }$$

By Corollary 4.3 there exists $(a_{1} - a_{2})A_{2} \subset (a_{1} - a_{2})A_{1}$ with $\vert A_{2}\vert \geq \frac{1} {2}\vert A_{1}\vert$ such that

$$\displaystyle\begin{array}{rcl} & & \vert (a_{1} - a_{2})A_{2} + (a_{1} - a_{2})A_{1} + (a_{3} - a_{4})A_{1}\vert {}\\ & &\leq 4\vert A_{2}\vert \frac{\vert A_{1} + A_{1}\vert } {\vert (a_{1} - a_{2})A_{1}\vert }\cdot \frac{\vert (a_{1} - a_{2})A_{1} + (a_{3} - a_{4})A_{1}\vert } {\vert (a_{1} - a_{2})A_{1}\vert }. {}\\ \end{array}$$

Bounding the last term as above we obtain $\vert A + A\vert ^{9} > (\vert A_{1}\vert 2^{k+1})^{4}\vert A\vert ^{2}/64$, so that $E_{\times }(A,A)^{4} \leq 64\vert A + A\vert ^{9}\vert A\vert ^{2}(\log \vert A\vert )^{4}$. □ 

Remark (A few ideas).

In the case that $\frac{A-A} {A-A} = \mathbb{F}_{p}$, we get in the above proof that there exist a ₁, a ₂, a ₃, a ₄ ∈ A such that

$$\displaystyle{ \frac{1} {2}\ \min \left \{p,\vert A\vert ^{2}\right \} \leq \vert (a_{ 1} - a_{2})A + (a_{3} - a_{4})A\vert \leq \vert bA\vert \prod _{i=1}^{4} \frac{\vert A + A\vert ^{2}} {\vert bA\vert \ \vert a_{i}A \cap bA\vert }. }$$

Now note that $\sum _{a,b\in A}\vert aA \cap bA\vert = E_{\times }(A,A) \geq \vert A\vert ^{4}/\vert AA\vert$ so $\vert aA \cap bA\vert$ is | A | ²∕ | AA | on average. If we somehow get that, even with the loss of a constant (or even | A | ^ε) for our $\vert a_{i}A \cap bA\vert$ then our bound here would be $\vert A + A\vert ^{8}\vert AA\vert ^{4} \gg \vert A\vert ^{11}\min \left \{p,\vert A\vert ^{2}\right \}$ which is what we get in Corollary 5.11, but in a less complicated way. If we could take b = a ₁ so we can replace one term in our product by $\vert A + A\vert /\vert A\vert$. Then we would get the bound $\vert A + A\vert ^{7}\vert AA\vert ^{3} \gg \vert A\vert ^{9}\min \left \{p,\vert A\vert ^{2}\right \}$; this improves the exponent from $\frac{13} {12}$ when $\vert A\vert \leq \sqrt{p}$ to $\frac{11} {10}$.

If $\frac{A-A} {A-A}\neq \mathbb{F}_{p}$, then we can change $\min \left \{p,\vert A\vert ^{2}\right \}$ to $\min \left \{\left \vert \frac{A-A} {A-A}\right \vert,\vert A\vert ^{2}\right \}$ using the same argument.

Combining all the results to this point, here are the results we obtained on sum-product in finite fields:

Corollary 5.12.

If $A \subseteq \mathbb{F}_{p}$ , then

$$\displaystyle{ \max \{\vert AA\vert,\vert A+A\vert \}\gg (\log \vert A\vert )^{O(1)}\cdot \left \{\begin{array}{@{}l@{\quad }l@{}} \sqrt{p\vert A\vert } \quad &\text{if}\ \vert A\vert \geq p^{2/3} \\ \vert A\vert ^{2}/\sqrt{p} \quad &\text{if}\ p^{2/3} > \vert A\vert \geq p^{7/13} \\ \vert A\vert ^{11/12}p^{1/12}\quad &\text{if}\ p^{7/13} > \vert A\vert \geq p^{13/25} \\ \vert A\vert ^{14/13} \quad &\text{if}\ p^{13/25} > \vert A\vert. \end{array} \right. }$$

As one can conjecture there is room for improvements. Indeed Rudnev recently published [26] a new bound

$$\displaystyle{\max \{\vert AA\vert,\vert A + A\vert \}\gg (\log \vert A\vert )^{O(1)} \cdot \vert A\vert ^{12/11}\text{ if}\ p^{1/2} > \vert A\vert.}$$

More strikingly after completing this survey we have learned that Roche-Newton, Rudnev, and Shkredov announced [24] a fantastic bound

$$\displaystyle{\max \{\vert AA\vert,\vert A + A\vert \}\gg \vert A\vert ^{6/5}\text{ if}\ p^{5/8} > \vert A\vert.}$$

In their proof they use incidence bounds in “Elekes style.” Misha Rudnev [25] used a result of Guth and Katz on point-line incidences in space (see in [15] and in [21]) to obtain an unexpectedly strong point-plain incidence bound in K ³ for arbitrary field K. This beautiful result led to new sum-product bounds in $\mathbb{F}_{p}$ even for composite p. 

5.1 Getting the Full Field

We now give a result of Glibichuk discussed at the start of this section:

Theorem 9.

If $\vert A\vert \vert B\vert \geq 3p/2 + \sqrt{p}$ , then $8AB = \mathbb{F}_{p}$ .

Proof.

Suppose | B | ≥ | A | , let $B_{+} =\{ b \in B: -b \in B\}$ and $B_{-} =\{ b \in B: -b\not\in B\} \cup \{ b \in B_{+}: 1 \leq b \leq \frac{p-1} {2} \}$. By definition B ₊ is symmetric ($b \in B_{+} \Leftrightarrow -b \in B_{+}$) and B ₋ is anti-symmetric ($b \in B_{-}\Rightarrow- b\not\in B_{-}$). Let B _∗ be the larger of the two. By a simple counting argument we know that $\vert B_{{\ast}}\vert =\max \{ \vert B_{+}\vert,\vert B_{-}\vert \}\geq \max \{ \frac{2\vert B\vert -1} {3},2\vert B\vert - p\}$. Note that $\vert A\vert \vert B_{{\ast}}\vert \geq \vert A\vert \cdot \frac{2\vert B\vert -1} {3} \geq p + 2$.

Noting that $a + tb = c + td$ iff $a - td = c - tb$ we have $R(t) = R(-t)$ in Proposition 5.2 so there exists t ≠ 0 such that $R(t) = R(-t) \leq \vert A\vert \vert B_{{\ast}}\vert + \vert A\vert ^{2}\vert B_{{\ast}}\vert ^{2}/(p - 1)$ so that

$$\displaystyle{ \vert A + tB_{{\ast}}\vert,\vert A - tB_{{\ast}}\vert \geq \frac{\vert A\vert ^{2}\vert B_{{\ast}}\vert ^{2}} {R(t)} \geq \frac{\vert A\vert ^{2}\vert B_{{\ast}}\vert ^{2}} {\vert A\vert \vert B_{{\ast}}\vert + \vert A\vert ^{2}\vert B_{{\ast}}\vert ^{2}/(p - 1)} > p/2 }$$

as | A | | B _∗ | ≥ p + 2. If $B_{{\ast}} = B_{+}$, then $I(A,B) = A(B + B) + B(A + A) \subset 4AB$ and so, by Lemma 5.4(i), we have $\vert 4AB_{+}\vert \geq \vert I(A,B_{+})\vert \geq \vert A + tB_{+}\vert > p/2$, and thus $8AB_{+} = \mathbb{F}_{p}$ by the pigeonhole principle. If $B_{{\ast}} = B_{-}$, then, by the pigeonhole principle, there exist a ₁, a ₂ ∈ A, b ₁, b ₂ ∈ B ₋ such that $a_{1} - tb_{1} = -(a_{2} - tb_{2})$ so that $t = (a_{1} + a_{2})/(b_{1} + b_{2})$ (and b ₁ + b ₂ ≠ 0 as B ₋ is anti-symmetric). But then $\vert 4AB_{-}\vert \geq \vert (b_{1} + b_{2})A + (a_{1} + a_{2})B_{-}\vert = \vert A + tB\vert > p/2$, and thus $8AB_{-} = \mathbb{F}_{p}$ by the pigeonhole principle.

The result follows. □ 

Corollary 5.13.

If $\vert A\vert \vert B\vert \geq 3p/4 + \sqrt{p}$ , then $16AB = \mathbb{F}_{p}$ .

Proof.

Suppose | B | ≥ | A | so that $\vert A\vert \vert B + B\vert \geq \vert A\vert (2\vert B\vert - 1) \geq 2\vert A\vert \vert B\vert -\sqrt{\vert A\vert \vert B\vert }\geq 3p/2 + \sqrt{p}$, and the result follows by applying Theorem 9 with B replaced by B + B, so that $16AB \subset 8A(B + B) = \mathbb{F}_{p}$. □ 

We now give a result of Hart and Iosevitch [16]:

Theorem 10.

If $\prod _{j=1}^{m}\vert A_{j}\vert \vert B_{j}\vert /p > (p - 1)$ , then $\sum _{i=1}^{m}A_{i}B_{i} \supseteq \mathbb{F}_{p}^{{\ast}}$ . In particular, if $\vert A\vert \vert B\vert > p(p - 1)^{1/m}$ , then $mAB \supseteq \mathbb{F}_{p}^{{\ast}}$ . If $\prod _{j=1}^{m}\vert A_{j}\vert \vert B_{j}\vert /p > (p - 1)^{2}$ , then $\sum _{i=1}^{m}A_{i}B_{i} \supseteq \mathbb{F}_{p}$ .

Proof.

Let r(t) be the number of representations of t as $\sum _{i=1}^{m}a_{i}b_{i}$, so that

$$\displaystyle{ r(t) =\sum _{\begin{array}{c}a_{i}\in A_{i} \\ b_{j}\in B_{j}\end{array}}\frac{1} {p}\sum _{k}e\left (\frac{k(\sum _{i}a_{i}b_{i} - t)} {p} \right ) = \frac{\prod _{i}\vert A_{i}\vert \vert B_{i}\vert } {p} + \frac{\text{Error}} {p}, }$$

where, by the Cauchy–Schwarz inequality, and writing $u \equiv k/l\pmod p$

$$\displaystyle\begin{array}{rcl} \vert \text{Error}\vert ^{2}& =& \left \vert \sum _{\begin{array}{c} a_{i}\in A_{i}\end{array}}\sum _{k\neq 0}e\left (\frac{-kt} {p} \right )\prod _{j}\sum _{\begin{array}{c}b_{j}\in B_{j}\end{array}}e\left (\frac{ka_{j}b_{j}} {p} \right )\right \vert ^{2} {}\\ & \leq & \sum _{\begin{array}{c}a_{i}\in A_{i}\end{array}}\left \vert \sum _{k\neq 0}e\left (\frac{-kt} {p} \right )\prod _{j}\sum _{\begin{array}{c}b_{j}\in B_{j}\end{array}}e\left (\frac{ka_{j}b_{j}} {p} \right )\right \vert ^{2} {}\\ & \leq & \prod _{i}\vert A_{i}\vert \cdot \sum _{\begin{array}{c}a_{i}\end{array}}\sum _{k,l\neq 0}e\left (\frac{(l - k)t} {p} \right )\prod _{j}\sum _{\begin{array}{c}b_{j},b_{j}^{{\prime}}\in B_{j}\end{array}}e\left (\frac{a_{j}(kb_{j} - lb_{j}^{{\prime}})} {p} \right ) {}\\ & \leq & \prod _{i}\vert A_{i}\vert \cdot \sum _{u,l\neq 0}e\left (\frac{(1 - u)lt} {p} \right )\prod _{j}p\sum _{\begin{array}{c}b_{j},ub_{j}\in B_{j}\end{array}}1. {}\\ \end{array}$$

Assume, for now, that t ≠ 0. If u ≠ 1, then the sum over l equals − 1, otherwise it equals p − 1. Hence the above is $\leq (p - 1)\prod _{i}\vert A_{i}\vert \cdot \prod _{j}p\sum _{\begin{array}{c}b_{j}\in B_{j}\end{array}}1 = (p - 1)p^{m}$ $\prod _{i}\vert A_{i}\vert \vert B_{i}\vert$. We deduce that $pr(t) \geq \prod _{i}\vert A_{i}\vert \vert B_{i}\vert - ((p - 1)p^{m}\prod _{i}\vert A_{i}\vert \vert B_{i}\vert )^{1/2}$ and the result follows.

If t = 0, the sum over l is p − 1 and it is feasible that ub _j  ∈ B _j for all u, j, so the above is $\leq (p - 1)^{2}p^{m}\prod _{i}\vert A_{i}\vert \vert B_{i}\vert$ and the result follows (one can also prove this bound more directly using (16)). □ 

6 Helfgott’s More General Bounds

Theorem 11 (Helfgott’s Theorem).

Let G be a group and Γ be an abelian group of automorphisms. Let $S \subset \varGamma$ with the property

$$\displaystyle{ \text{If}\ g^{\sigma } = g\ \text{for some}\ g \in G,\sigma \in S^{-1}S,\ \text{then}\ g = 1\ \text{or}\ \sigma = 1. }$$

(24)

Then for any $A \subset G$ we have one of the following:

• (i) There exists g ∈ A such that |Ag ^S | = |A| |S|

  Or there exist c ∈ A ⁻¹ A and $\lambda \neq \tau \in S$ such that

• (ii) There exists $b \in A \cup A^{-1}$ such that $\{(ab^{\sigma })^{\tau }c^{\sigma }(ab^{\sigma })^{-\lambda }:\ a \in A,\ \sigma \in S\}$ contains |A| |S| distinct elements.

Or (iii) There exists $\eta \in S \cup S^{-1}$ such that $\{a^{\tau }(c^{\eta })^{\sigma }a^{-\lambda }:\ a \in A,\ \sigma \in S\}$ contains |A| |S| distinct elements;

or (iv) $\{a^{\tau }c^{\sigma }a^{-\lambda }:\ a \in A,\ \sigma \in S\}$ contains $\geq \frac{1} {2}\min \{\vert A\vert \vert S\vert,\vert \mathcal{O}\vert \}$ distinct elements, where $\mathcal{O}$ is the union of the orbits of elements of A under the two maps a → ba for any $b \in A \cup A^{-1}$ , and a → a ^η for any $\eta \in S \cup S^{-1}$ .

Proof.

Define $U:=\{ g \in G:\ \text{There exists}\ \lambda \neq \tau \in S\ \text{such that}\ g^{\tau -\lambda }\in A^{-1}A\}$. For any g ∈ G define ϕ _g : A × S → G by $\phi _{g}(a,\sigma ) = ag^{\sigma }$. Note that ϕ _g is injective if and only if g ∉ U, and in this case | Ag ^S |  =  | A |   | S | .

Next define $\delta _{\lambda,\tau }(g) = g^{\tau -\lambda }$ for g ∈ G, for each $\lambda \neq \tau \in S$. This is always injective, for if $\delta _{\lambda,\tau }(g_{1}) =\delta _{\lambda,\tau }(g_{2})$, then $(g_{1}^{-1}g_{2})^{\lambda \tau ^{-1} } = g_{1}^{-1}g_{2}$, and so g ₁ = g ₂ by (24). Hence if g ∉ U, then $\vert \delta _{\lambda,\tau }(Ag^{S})\vert = \vert A\vert \ \vert S\vert$. We observe that

$$\displaystyle{ \delta _{\lambda,\tau }(ag^{\sigma }) = (ag^{\sigma })^{\tau -\lambda } = a^{\tau }g^{\sigma (\tau -\lambda )}a^{-\lambda }, }$$

(25)

using the fact that Γ is abelian.

Suppose that $\mathcal{O}\not\subset U$. By following how the orbits are created from A by applying the two maps, we consider the first element of $\mathcal{O}$ that is not in U. Then one of the following must be true:

• (i) There exists g ∈ A such that g ∉ U;

• (ii) There exists $u \in \mathcal{O}\cap U$ such that g = bu ∉ U with $b \in A \cup A^{-1}$;

• (iii) There exists $u \in \mathcal{O}\cap U$ such that g = u ^η ∉ U with $\eta \in S \cup S^{-1}$, where

In case (i) we have that ϕ _g is injective so that | Ag ^S |  =  | A |   | S | .

In cases (ii) and (iii) we have $u \in \mathcal{O}\cap U$ and so there exist $\lambda \neq \tau \in S$ and c ∈ A ⁻¹ A such that $u^{\tau -\lambda } = c$.

In case (ii) we then have $g^{\tau -\lambda } = (bu)^{\tau -\lambda } = b^{\tau }u^{\tau -\lambda }b^{-\lambda } = b^{\tau }cb^{-\lambda }$, and so $\delta _{\lambda,\tau }(ag^{\sigma }) = (ab^{\sigma })^{\tau }c^{\sigma }(ab^{\sigma })^{-\lambda }$ by (25) and the commutativity of Γ. Hence

$$\displaystyle{ \{(ab^{\sigma })^{\tau }c^{\sigma }(ab^{\sigma })^{-\lambda }:\ a \in A,\ \sigma \in S\} =\delta _{\lambda,\tau }(Ag^{S}) }$$

which has size $\vert \delta _{\lambda,\tau }(Ag^{S})\vert = \vert A\vert \ \vert S\vert$.

In case (iii) we then have $g^{\tau -\lambda } = u^{(\tau -\lambda )\eta } = c^{\eta }$ and so, proceeding as above,

$$\displaystyle{ \{a^{\tau }(c^{\eta })^{\sigma }a^{-\lambda }:\ a \in A,\ \sigma \in S\} =\delta _{\lambda,\tau }(Ag^{S}) }$$

which has size $\vert \delta _{\lambda,\tau }(Ag^{S})\vert = \vert A\vert \ \vert S\vert$.

Now suppose that $\mathcal{O}\subset U$ and define $R_{g}:=\{ a,b \in A,\lambda \neq \tau \in S:\ ag^{\lambda } = bg^{\tau }\}$. Note these are disjoint for if $(a,b,\lambda \tau ) \in R_{g} \cap R_{h}$, then $g^{\tau -\lambda } = b^{-1}a = h^{\tau -\lambda }$ which is impossible as $\delta _{\lambda,\tau }$ is injective. Therefore,

$$\displaystyle{ \min _{g\in U}\vert R_{g}\vert \leq \frac{1} {\vert U\vert }\#\{a,b \in A,\lambda \neq \tau \in S\} < \frac{(\vert A\vert \vert S\vert )^{2}} {\vert \mathcal{O}\vert } }$$

and, since

$$\displaystyle{ \sum _{n}r_{Ag^{S}}(n)^{2} = \#\{a,b \in A,\lambda,\tau \in S:\ ag^{\lambda } = bg^{\tau }\} = \vert R_{ g}\vert + \vert A\vert \vert S\vert, }$$

we deduce that for some g ∈ U,

$$\displaystyle{ \vert A\vert ^{2}\vert S\vert ^{2} = \left (\sum _{ n}r_{Ag^{S}}(n)\right )^{2} \leq \vert Ag^{S}\vert \sum _{ n}r_{Ag^{S}}(n)^{2} \leq \vert Ag^{S}\vert \left (\frac{(\vert A\vert \vert S\vert )^{2}} {\vert \mathcal{O}\vert } + \vert A\vert \vert S\vert \right ) }$$

by the Cauchy–Schwarz inequality. As g ∈ U, there exist $\lambda \neq \tau \in S$ and c ∈ A ⁻¹ A such that $g^{\tau -\lambda } = c$, and so, by (25),

$$\displaystyle{ \{a^{\tau }c^{\sigma }a^{-\lambda }:\ a \in A,\ \sigma \in S\} =\delta _{\lambda,\tau }(Ag^{S}) }$$

which has size

$$\displaystyle{ \vert \delta _{\lambda,\tau }(Ag^{S})\vert = \vert Ag^{S}\vert \geq \frac{\vert A\vert \vert S\vert \vert \mathcal{O}\vert } {\vert A\vert \vert S\vert + \vert \mathcal{O}\vert } \geq \frac{1} {2}\min \{\vert A\vert \vert S\vert,\vert \mathcal{O}\vert \}. }$$

 □ 

For further readings on the subject see [2, 4, 5, 8, 10, 12, 13, 19, 20, 31].