###### Abstract

There exists an absolute constant $\delta>0$ such that for all $q$ and all
subsets $A\subseteq\mathbb{F}_{q}$ of the finite field with $q$ elements, if
$|A|>q^{2/3-\delta}$, then

$|(A-A)(A-A)|=|\\{(a-b)(c-d):a,b,c,d\in A\\}|>\frac{q}{2}.$

Any $\delta<1/13,542$ suffices for sufficiently large $q$. This improves the
condition $|A|>q^{2/3}$, due to Bennett, Hart, Iosevich, Pakianathan, and
Rudnev, that is typical for such questions.

Our proof is based on a qualitatively optimal characterisation of sets
$A,X\subseteq\mathbb{F}_{q}$ for which the number of solutions to the equation

$(a_{1}-a_{2})=x(a_{3}-a_{4})\,,\;a_{1},a_{2},a_{3},a_{4}\in A,x\in X$

is nearly maximum. A key ingredient is determining exact algebraic structure
of sets $A,X$ for which $|A+XA|$ is nearly minimum, which refines a result of
Bourgain and Glibichuk using work of Gill, Helfgott, and Tao.

We also prove a stronger statement for

$(A-B)(C-D)=\\{(a-b)(c-d):a\in A,b\in B,c\in C,d\in D\\}$

when $A,B,C,D$ are sets in a prime field, generalising a result of Roche-
Newton, Rudnev, Shkredov, and the authors.

title = Products of Differences over Arbitrary Finite Fields, author = Brendan
Murphy and Giorgis Petridis, plaintextauthor = Brendan Murphy, Giorgis
Petridis, keywords = sum product problem, finite fields, year=2018, number=18,
received=6 July 2017, published=7 November 2018, doi=10.19086/da.5098,

[classification=text]

##  1 Introduction

###  1.1 Overview

A manifestation of the sum-product phenomenon is expansion of polynomial
images. The principle asserts that if a polynomial does not have a specific
form, then it takes many distinct values on large finite Cartesian products.

The first such result was proved by Elekes over the real numbers for two-
variable polynomials [12]. Elekes and Rónyai proved a stronger result for
rational functions [13]. Their result, when restricted to polynomials, roughly
asserts that there exist absolute constants $c$ and $\delta$ such that if
$f(x,y)\in\mathbb{R}[x,y]$ is not similar to $x+y$ or $xy$, then for all
finite sets $A\subset\mathbb{R}$ we have $|f(A,A)|>c|A|^{1+\delta}$. One
cannot hope for such expansion for, say, $f(x,y)=x+3y$ as we see by letting
$A$ be an arithmetic progression. Strong qualitative bounds were given by Raz,
Sharir, and Solymosi, who showed that one may take $\delta=1/3$ [44].

Better quantitative bounds are known for what one could call natural expander
polynomials: $x+yz$ [55], $x(y+z)$ [38], $wx+yz$ [30], $(w-x)^{2}+(y-z)^{2}$
[19], and $(w-x)(y-z)$ [45].

Several formulations of polynomial expansion have also been studied over
finite fields.

We study a variation of what Tao calls (symmetric) moderate expanders [60],
focusing on quadratic polynomials with coefficients in $\\{0,\pm 1\\}$. The
precise expansion property we study is as follows: Given a polynomial
$f\in\mathbb{Z}[X_{1},\dots,X_{n}]$ we seek absolute constants $c,C$, and
$\alpha$ such that for all prime powers $q$ and for all sets
$A\subseteq\mathbb{F}_{q}$ that satisfy $|A|>Cq^{\alpha}$ we have

$|f(A,\dots,A)|>cq.$

Tao established an analogue of the Elekes–Rónyai theorem for two-variable
polynomials with $\alpha=15/16$ [60]. Earlier, Hart, Li, and Shen proved
stronger expansion for a smaller class of polynomials with the smaller
threshold $\alpha=3/4$ [24, Theorem 2.11]. Expansion conditional on $A$ having
few distinct sums was obtained even earlier by Solymosi [57, Corollary 4.4].
See also the papers [9, 20, 26, 54, 65].

Expansion has been established for many natural examples of expanding
polynomials with the smaller common threshold $\alpha=2/3$:

  * •

$x+yz$ [56, Inequality (9)] or [64, Theorem 3.2],

  * •

$x(y+z)$ [35],

  * •

$wx+y+z$ [52],

  * •

$wx+yz$ [22],

  * •

$(w-x)^{2}+(y-z)^{2}$ [10] (here we must require $q$ to be odd), and

  * •

$(w-x)(y-z)$ [3, Corollary 1.8].

Using standard notation for set addition and multiplication, one may state the
last result for $(w-x)(y-z)$ as: If $|A|>q^{2/3}$, then

$|(A-A)(A-A)|=|\\{(a-b)(c-d):a,b,c,d\in A\\}|>\frac{q}{2}.$

All of these results have straightforward proofs using the _completion method_
, which roughly involves replacing a sum of squares over a large set in a
space by the sum of squares over the whole space. This seemingly expensive
step allows one to take advantage of properties like character orthogonality
and produces non-trivial results for large sets. The completion method has
been applied to additive characters, multiplicative characters, and the
spectral theory of regular graphs.

A unifying approach for “pinned” versions of the results was presented in
[35]. The fact that two points in the two-dimensional vector space
$\mathbb{F}_{q}^{2}$ determine a unique line, combined with a second moment
argument, is used as a substitute for the so-called expander mixing lemma [21,
1]. The corresponding result for the polynomial $(w-x)(y-z)$ was omitted from
[35], but it is straightforward to prove that if $|A|>q^{2/3}$, then there
exist $a,b\in A$ such that

$|(A-a)(A-b)|=|\\{(c-a)(d-b):c,d\in A\\}|>\frac{q}{2}.$

###  1.2 Main result

Going below the $q^{2/3}$ threshold for any of the polynomials listed above
has proven to be surprisingly hard, even in prime order fields where there are
additional tools. Let us write $p$ for the order of the field when it is a
prime. When $A\subseteq\mathbb{F}_{p}$ is a multiplicative subgroup, Heath-
Brown and Konyagin applied Stepanov’s method [25] to show that
$|A+A|>c\min\\{p,|A|^{3/2}\\}$, matching the $p^{2/3}$ threshold (note that
$A+A=A+AA=A(A+A)$). Similarly, Pham, Vinh, and de Zeeuw used Rudnev’s point-
plane incidence bound in $\mathbb{F}_{p}^{3}$ [46, 66] to prove that
$|f(A,A,A)|>c\min\\{p,|A|^{3/2}\\}$ for a large class of quadratic polynomials
in three variables [42].

The first step in going below the $p^{2/3}$ threshold for prime $p$ was taken
in [40] for $(w-x)(y-z)$, where it was shown that there exists a constant $C$
such that if $|A|>Cp^{5/8}$, then $|(A-A)(A-A)|>p/2$. This argument does not
carry through to arbitrary $\mathbb{F}_{q}$, because it relies on non-trivial
bounds on the number of ordered solutions to the equation
$(a_{1}-a_{2})=x(a_{3}-a_{4})$ with the $a_{i}\in A$ and $x$ in an arbitrary
set $X\subseteq\mathbb{F}_{p}$. Bourgain [4, Theorem C] proved a non-trivial
bound in $\mathbb{F}_{p}$, but such a theorem is false in $\mathbb{F}_{q}$, in
general.

Roche-Newton, Rudnev, Shkredov, and the authors [37, Theorem 27] improved this
result, showing that $|A|>Cp^{3/5}$ implies the “pinned” result
$|(A-a)(A-b)|>p/2$ for some $a,b\in A$. The proof uses a bound on the number
of ordered collinear triples in $A\times A\subseteq\mathbb{F}_{p}^{2}$ that is
better than what follows from the completion method. In terms of incidence
geometry results, the method of proof combines Vinh’s point-line incidence
theorem [63] with a point-line incidence theorem of Stevens and de Zeeuw [58].
This method is also specific to prime fields and does not carry over in
arbitrary $\mathbb{F}_{q}$ either.

Our main theorem breaks the $q^{2/3}$ threshold over arbitrary finite fields.

######  Theorem A.

There exist absolute positive constants $C,k>0$ such that for all prime powers
$q$, if $A\subseteq\mathbb{F}_{q}$ satisfies

$|A|>Cq^{\tfrac{2}{3}-\tfrac{1}{13,542}}\log^{k}(q),$

then $|(A-A)(A-A)|>q/2$.

The proof of Theorem A uses most of the existing techniques for sum-product
questions in arbitrary finite fields at different stages of the proof: the
completion method in Section 3, the pivot method in Section 4, and character
sum estimates in Section 5.

Before discussing the proof of Theorem A in more detail, we make some remarks.

######  Remarks.

  1. 1.

Over prime finite fields $\mathbb{F}_{p}$ we prove a stronger result for
$(A-B)(C-D)$. Using a result in [37], we show that if
$(|A||B||C||D|)^{1/4}>p^{3/5}$, then $|(A-B)(C-D)|>cp$. This proves expansion
for rational functions such as $(w+x^{2})(y-z^{-1})$ with $|A|$ as small as
$p^{3/5}$.

  2. 2.

The proof of Theorem A contains a simple example of a set
$A\subset\mathbb{F}_{q}$ of cardinality $|A|=q^{2/3}$ with the property
$|(A-A)(A-A)|=(1+o(1))q/2$; see Proposition 11. This shows that $(A-A)(A-A)$
cannot have density greater than 1/2, in general. Hart, Iosevich, and Solymosi
[23] conjectured that there exists $\varepsilon>0$ such that if
$|A|>Cq^{1/2+\varepsilon}$, then $(A-A)(A-A)=\mathbb{F}_{q}$. The example
shows that $\varepsilon$ must be greater than $1/6$. The best known lower
bound on $|A|$ for this complementary question is $Cq^{3/4}$ and is due to
Hart, Iosevich, and Solymosi [23, Theorem 1.4].

  3. 3.

Vinh has obtained expansion with threshold $q^{5/8}$ for the four-variable
polynomial $wx+(y-z)^{2}$ [64] in finite fields $\mathbb{F}_{q}$ with odd
characteristic. Vinh’s elegant proof is based on ideas of Garaev [14] and
Solymosi [57] and strongly relies on having a polynomial where the additive
and multiplicative parts are separated.

  4. 4.

Rudnev, Stevens, and Shkredov have proved the strongest expansion result in
$\mathbb{F}_{p}$ we are aware of. They worked with the four-variable rational
function $(wx-y)(w-z)^{-1}$ [47] and showed there exist absolute constants
$c,C$, and $k$ such that if $A\subseteq\mathbb{F}_{p}$ satisfies
$|A|>C\log(p)^{k}p^{25/42}$, then $|f(A,A,A,A)|\geq cp$. The exponent $25/42$
is slightly smaller than the exponent $3/5$, which is known for $(w-x)(y-z)$
[37], the three variable rational function $(x-y)(x-z)^{-1}$ [37], and the
four variable rational functions covered by the forthcoming Theorem F.

###  1.3 Proof outline and structure of the paper

Theorem A is proved using a dichotomy argument, carried out in three steps: a
completion argument that works for generic sets, an exact structural
characterisation of sets for which the completion argument fails, and a
character sum argument that deals with the structured sets.

Standard results from arithmetic combinatorics used throughout the paper are
given in Section 2. To make the statements of the forthcoming theorems more
compact, we make one preliminary definition: for $A\subseteq\mathbb{F}_{q}$
and $\xi\in\mathbb{F}_{q}^{*}$ we use $E(A,\xi A)$ to denote the number of
ordered solutions to the equation

$(a_{1}-a_{2})=\xi(a_{3}-a_{4})$

with all variables $a_{1},\ldots,a_{4}$ in $A$.

#### Section 3: The generic sets completion argument

The first step is similar to arguments used to deal with large subsets of
finite fields. It mimics the argument in [40] to show that Theorem A holds
unless there exists a set $X\subset\mathbb{F}_{q}$ of cardinality roughly
$q/|A|$ such that $E(A,\xi A)$ is greater than $|A|^{3}/K$, for all $\xi\in X$
and some suitable $K$. This is is achieved by a careful analysis of a
completion argument.

Define the quantity

$D_{\times}(A)=|\\{(a_{1},\dots,a_{8})\in
A^{8}:(a_{1}-a_{2})(a_{3}-a_{4})=(a_{5}-a_{6})(a_{7}-a_{8})\\}|.$ (1)

By Cauchy-Schwarz, $|(A-A)(A-A)|\cdot D_{\times}(A)\geq|A|^{8}$. We aim to
show that $D_{\times}(A)$ is at most $2|A|^{8}/q$, under suitable conditions.

More precisely, we prove the following theorem in Section 3.

######  Theorem B.

Let $A$ be a subset of $\mathbb{F}_{q}$. Suppose that there is a positive
constant $K$ such that $|A|\leq q/(4K)$ and

$D_{\times}(A)\geq\frac{|A|^{8}}{q}+\frac{3q|A|^{5}}{K}.$

There exists a subset $X\subseteq\mathbb{F}_{q}$ such that $E(A,\xi
A)\geq|A|^{3}/K$ for all $\xi\in X$ and

$\frac{q}{K|A|}\leq|X|\leq\frac{4Kq}{3|A|}.$

It is easy to show, for example using multiplicative characters, that
$\displaystyle D_{\times}(A)=|A|^{8}/q+O(q|A|^{5})$, yielding the
$|A|>Cq^{2/3}$ threshold. The $|A|^{8}/q$ term, which comes from the principal
multiplicative character, is the expected value of $D_{\times}(A)$ for large
random sets.

#### Section 4: Inverse sum-product results

The next step in the proof is to show that the conclusion of Theorem B is
impossible for $K=q^{\delta}$ for some small $\delta>0$, unless $A$ has a
specific structure.

A result of Bourgain implies that the conclusion in Theorem B is never true in
$\mathbb{F}_{p}$ when $K$ is small power of $p$ and $|A||X|$ is about $p$.
Namely, [4, Theorem C] states that there exists an absolute constant $\eta>0$
such that for sets $A,X\subseteq\mathbb{F}_{p}$ satisfying $|A||X|<p$, we have

$\sum_{\xi\in X}E(A,\xi A)\leq|A|^{3}|X|^{1-\eta}.$

This suffices to go below $p^{2/3}$ in $\mathbb{F}_{p}$ [36, 40].

However, Bourgain’s result is not true over arbitrary finite fields. If $X$ is
contained in a proper subfield and $A$ is a vector space over the subfield,
then $E(A,\xi A)=|A|^{3}$ for all $\xi\in X$. Taking $q=p^{3}$, $X$ to be the
subfield isomorphic to $\mathbb{F}_{p}$ and $A$ to be a two-dimensional vector
space over $X$, produces a pair of sets $A$ and $X$ with $|A||X|=q$, where the
conclusion (and therefore the hypothesis) of Theorem B is false.

Therefore, we must deal with pairs of sets $A,X$ where

$\sum_{\xi\in X}E(A,\xi A)\geq\frac{|A|^{3}|X|}{K}$ (2)

for a parameter $K$ that will eventually be taken to be a small power of $q$.

Bourgain and Glibichuk proved in [6, Proposition 2] that if (2) holds, then
$X$ must have large intersection with the dilate of a subfield. This
characterisation is hard to apply in our context because we are more
interested in $A$ than in $X$. We strengthen this result to show that the
example given above is essentially the only way that (2) can hold: a large
subset of $X$ must be contained in a dilate of a subfield and $A$ must have a
large intersection with a vector space over the same subfield. Though $X$
itself may be small compared to the subfield, $A$ must have comparable size to
the vector space. This characterisation is qualitatively best possible.

The next theorem contains a precise statement of this result. For brevity, we
write $f\lesssim g$ if there exist constants $C,k$ such that $f\leq
C\log^{k}(q)\,g$.

######  Theorem C.

Let $A$ and $X$ be subsets of $\mathbb{F}_{q}^{*}$ and let $K\geq 1$ be a real
number such that $K^{1505}\lesssim|X|$. Suppose

$\sum_{\xi\in X}E(A,\xi A)\geq\frac{|A|^{3}|X|}{K}.$

There exists an element $\bar{a}$ in $A$, a subfield
$F\subseteq\mathbb{F}_{q}$, and an $F$-vector space $V\subseteq\mathbb{F}_{q}$
such that

$|V\cap(A-\bar{a})|\gtrsim\max\\{K^{-704}|V|,K^{-85}|A|\\}.$

Further, there is an element $x_{0}$ in $X$ and subsets $A_{1}\subseteq
A-\bar{a}$, $X^{\prime}\subseteq x_{0}^{-1}X$ such that $F$ is the subfield
generated by $X^{\prime}$, $V$ is the $F$-vector space generated by $A_{1}$,
and

$|A_{1}|\gtrsim K^{-85}|A|\qquad\mbox{and}\qquad|X^{\prime}|\gtrsim
K^{-5}|X|.$

Moreover, if $E(A,\xi A)\geq|A|^{3}/K$ for all $\xi\in X$ we have
$|X^{\prime}|\gtrsim K^{-4}|X|$ and only require $K^{1504}\lesssim|X|$.

Theorem C constitutes the biggest step towards the proof of Theorem A. Its
proof has two main parts. The first is, roughly speaking, to show that if

$\sum_{\xi\in X}E(A,\xi A)\geq\frac{|A|^{3}|X|}{K}$

then there exists an absolute constant $C$ and large subsets $A_{1}\subseteq
A$ and $X^{\prime}\subseteq X$ such that $|A_{1}+X^{\prime}A_{1}|\leq
K^{C}|A_{1}|$. This was proved by Bourgain [4, Proof of Theorem C], see also
[6, Proposition 2]. We prove a quantitatively stronger result in Proposition 4
in Appendix A.

The second part in the proof of Theorem C is to extract exact algebraic
structure for $A$ and $X$ when $|A+XA|$ is nearly minimum. Roughly, if $A+XA$
is small, then $A$ has large relative density in the vector space it spans
over the field generated by $X$. In Section 4 we prove the following more
precise result.

######  Theorem D.

Let $W$ be a subset of an $\mathbb{F}_{q}$-vector space, let
$X\subseteq\mathbb{F}_{q}$ be a set of scalars, and let $F=\langle X\rangle$
be the subfield generated by $X$. If

  1. 1.

$|W+XW|\leq K_{1}|W|$,

  2. 2.

$|W+W|\leq K_{2}|W|$,

  3. 3.

$|W+xW|\leq K_{3}|W|$ for all $x\in X$, and

  4. 4.

$K_{1}^{4}K_{2}K_{3}^{4}<|X|$,

then

$|W|\geq\frac{1}{2K_{1}^{2}K_{3}^{2}}|\mathrm{Span}_{F}(W)|,$

where $\mathrm{Span}_{F}(W)$ is the vector space over $F$ spanned by $W$.

In Theorem D we characterise the whole of $W$, whereas in Theorem C only a
large subset of $A$. This has to do with additive energy being a robust
measure of additive structure (perturbing the set a little makes little
difference), while cardinality is a delicate measure of additive structure
(perturbing the set a little can make a big difference).

In the context of Theorem A, where $|A|$ is $q^{2/3}$ (up to small powers of
$q$) and $|X|$ is $q^{1/3}$ (up to small powers of $q$) , we can extract from
Theorem C even more information and show that the example mentioned above
($q=p^{3}$, $X$ is a subset of the subfield isomorphic to $\mathbb{F}_{p}$ and
$A$ is a two-dimensional vector space over $\mathbb{F}_{p}$), is morally the
only way that (2) can occur.

######  Corollary 1.

Let $A,X\subseteq\mathbb{F}_{q}^{*}$ be sets and $K$ be a positive real
number. Suppose $K^{1504}\lesssim|X|$, $q^{1/4}K^{4}\lesssim|X|<q^{1/2}$,
$q^{1/2}K^{85}\lesssim|A|\leq q^{2/3}$ and $E(A,\xi A)\geq|A|^{3}/K$ for all
$\xi\in X$.

There exists a subfield $F$ of cardinality $q^{1/3}$, $\bar{a}$ in $A$, and a
two-dimensional vector space $V$ over $F$ such that $|(A-\bar{a})\cap
V|\gtrsim K^{-85}|A|$.

The proof of Theorem C combines the work of Bourgain and Glibichuk with ideas
of Glibichuk and Konyagin [16], Helfgott [27, 28, 29], Gill and Helfgott [15],
and Tao [61]. In the background is the work of Ruzsa [50] and Gowers [17, 18].

#### Section 5: Large subsets of a vector space

By Theorem B and Corollary 1 we are left to deal with the case where $q$ is a
cube, $F$ is the subfield of cardinality $q^{1/3}$, and a translate of $A$ has
large intersection with a two-dimensional vector space over $F$. To deal with
such sets we combine basic algebra with a character sum argument of Hart,
Iosevich, and Solymosi [23].

######  Theorem E.

Let $q$ be a cube. Suppose $F\subset\mathbb{F}_{q}$ is the subfield of
cardinality $q^{1/3}$ and $V\subset\mathbb{F}_{q}$ is a two-dimensional vector
space over $F$. If $A$ is a subset of $V$ such that
$|A|>\sqrt{2}|V|^{7/8}=\sqrt{2}q^{7/12}$, then

$|(A-A)(A-A)|=|VV|>\frac{q}{2}.$

One may compare Theorem E, which we prove in Section 5, to the result of Hart,
Iosevich and Solymosi [23, Theorem 1.4] and a result of Bennett, Hart,
Iosevich, Pakianathan and Rudnev [3, Corollary 1.8].

The former states that if $|A|>Cq^{3/4}$ for some absolute constant $C$, then
$(A-A)(A-A)=\mathbb{F}_{q}$. Theorem E is analogous because $\mathbb{F}_{q}$
is a one-dimensional vector space over itself and
$\mathbb{F}_{q}\mathbb{F}_{q}=\mathbb{F}_{q}$. The exponent in Theorem E is
worse because we work in a two-dimensional vector space.

The latter states that if $|A|>Cq^{2/3}$ for some absolute $C$, then
$(A-A)(A-A)$ determines a positive proportion of the elements of
$\mathbb{F}_{q}$. Restricting $A$ to subsets of $V$ allows one to get a
similar result for smaller sets.

To get the best possible lower bound on $|A|$ in Theorem E we apply Weil’s
bounds on Kloosterman sums. Kloosterman’s bounds, which are easier to derive,
could be used at no cost in the required lower bound on $|A|$ in Theorem A.

#### Structure of the rest of the paper

The derivation of Theorem A from Theorems B, Corollary 1, and Theorem E is
conducted in Section 6.

In Section 7 we prove a stronger result over prime order fields.

######  Theorem F.

For all constants $L>0$ there exists a constant $c>0$ such that for all primes
$p$ and all sets $A,B,C,D\subseteq\mathbb{F}_{p}$ that satisfy

$|A||B||C||D|>Lp^{12/5}$

and (assuming $|A|\leq|B|$, $|C|\leq|D|$, and $|B|\leq|D|)$

$|A||B|^{4}|C|\geq p^{2}|D|^{2},$

we have

$|(A-B)(C-D)|>cp.$

This leads to expansion for rational functions like

$f(w,x,y,z)=(w+x^{2})(y-z^{-1})$

with threshold $|A|\geq p^{3/5}$ (by simply noting
$|A||A^{2}||A||A^{-1}|\geq|A|^{4}/2$).

Bourgain’s version of Theorem C [4, Theorem C] over prime finite fields is a
powerful result, with many applications in the literature. In Section 8 we
discuss what is currently known and highlight the strong bounds that follow
from Rudnev’s point-plane incidence theorem [46].

Appendix A is dedicated to the proof of a sharper version of a result of
Bourgain and Glibichuk from [6]. It roughly asserts that if (2) holds, then
there are large subsets $A_{1}\subset A$ and $X^{\prime}\subset X$ such that
$|A_{1}+X^{\prime}A_{1}|\leq K^{C}|A^{\prime}|$.

In Appendix A, we also prove a version of the Balog-Szemerédi-Gowers theorem
[17, 18] that shows if $E(A,B)\geq(|A||B|)^{3/2}/K$, then
$|A^{\prime}+B^{\prime}|\lesssim K^{3}(|A||B|)^{1/2}$ for subsets
$A^{\prime}\subseteq A$, $B^{\prime}\subseteq B$ of relative density $\gtrsim
1/K$. This is slightly worse than the bounds achieved by Schoen [53] under the
hypothesis $E(A)\geq|A|^{3}/K$, however it applies to the case of distinct $A$
and $B$, and improves the bounds of Bourgain and Garaev [5].

###  1.4 Notation

For positive quantities $X$ and $Y$, we use $X\ll Y$ to mean that $X\leq CY$
for some constant $C>0$ and we use $X\lesssim Y$ to mean that $X\ll(\log
Y)^{k}Y$ for some constant $k>0$. The letter $p$ always denotes a prime and
$q$ a prime power; $\mathbb{F}_{q}$ is the finite field with $q$ elements and
$\mathbb{F}_{p}^{d}$ the $d$-dimensional vector space over $\mathbb{F}_{q}$.
For $x,y\in\mathbb{F}_{p}$ we sometimes write $\tfrac{x}{y}$ instead of
$xy^{-1}$ and implicitly assume $y\neq 0$. We use standard notation on set
operations. For example we denote by $A+B=\\{a+b:a\in A,b\in B\\}$. We use
representation functions like $r_{A+B}(x)$, which counts the number of ordered
ways $x\in\mathbb{F}_{q}$ can be expressed as a sum $a+b$ with $a\in A$ and
$b\in B$. Note that $A+B$ is the support of $r_{A+B}$. For a subset
$G\subseteq A\times B$ we define $A\stackrel{{\scriptstyle
G}}{{+}}B=\\{a+b:(a,b)\in G\\}$. For a subspace $W$ of a finite field, we
denote by $\mathrm{Span}_{F}(W)$ the vector space over a subfield $F$ spanned
by $W$ and by $\langle W\rangle$ the subfield generated by $W$.

##  2 Arithmetic combinatorics

In various stages of the proofs we utilise sumset cardinality inequalities
that follow from the work of of Plünnecke and Ruzsa [43, 48, 49, 50]. An
excellent reference is [51].

######  Lemma 2 (Sumset inequalities).

Let $A,B_{1},\dots,B_{h}$ be finite non-empty sets in a commutative group. The
following inequalities are true.

  1. 1.

Plünnecke’s inequality for different summands [51, Theorem 1.6.1] (see also
[43, 49]).

$|B_{1}+\dots+B_{h}|\leq\frac{|A+B_{1}|}{|A|}\cdots\frac{|A+B_{h}|}{|A|}\;|A|.$

  2. 2.

Plünnecke’s inequality for different summands with a large subset [32,
Corollary 1.5] (see also [51, Theorem 1.7.1]). There exists a subset
$Y\subseteq A$ of cardinality $|Y|\geq|A|/2$ such that

$|Y+B_{1}+\dots+B_{h}|\leq
2^{h}\frac{|A+B_{1}|}{|A|}\cdots\frac{|A+B_{h}|}{|A|}\;|A|.$

  3. 3.

Ruzsa’s triangle inequality [51, Theorem 1.8.1] (see also [48])

$|B_{1}-B_{2}|\leq\frac{|A+B_{1}|}{|A|}\,\frac{|A+B_{2}|}{|A|}\;|A|.$

  4. 4.

Plünnecke-Ruzsa inequality for different summands (see also [51, Theorem
1.1.1] and [43, 50, 39]).

$|\underbrace{B_{1}\pm B_{2}\pm\dots\pm B_{h}}_{h\text{
summands}}|\leq\left(\prod_{i=1}^{h}\frac{|A+B_{i}|}{|A|}\right)\;|A|.$

We also make heavy use of the notion of so-called additive energy.

######  Definition.

Let $A,B\subseteq F_{q}$ and $\xi\in\mathbb{F}_{q}^{*}$. The _additive energy_
of $A$ and $\xi B$ is defined in the following equivalent ways.

$\displaystyle E(A,\xi B)$ $\displaystyle=\sum_{x\in\mathbb{F}_{q}}r_{A\pm\xi
B}^{2}(x)$ $\displaystyle=|\\{(a_{1},a_{2},b_{1},b_{2})\in A\times A\times
B\times B:(a_{1}-a_{2})=\xi(b_{1}-b_{2})\\}.$

The Cauchy-Schwarz inequality and the identity $\sum_{x}r_{A+\xi B}(x)=|A||B|$
(each ordered pair $(a,b)\in A\times B$ contributes 1 to the sum) imply

$E(A,\xi B)\geq\frac{\left(\sum_{x}r_{A+\xi
B}(x)\right)^{2}}{|\mathrm{spt}(r_{A+\xi B})|}\geq\frac{|A|^{2}|B|^{2}}{q}.$
(3)

We will use repeatedly the following simple yet powerful lemma; see [8, Lemma
2.1], [33, Lemma 2] and [7, Lemma 3]. We need a straightforward generalisation
of additive energy to $\mathbb{F}_{q}$-vector spaces. Given a set $A$ and a
non-zero element $\xi$ in the vector space and a set
$B\subseteq\mathbb{F}_{q}^{*}$, we define the additive energy $E(A,\xi B)$
like in $\mathbb{F}_{q}$.

######  Lemma 3.

Let $V$ be a vector space over $\mathbb{F}_{q}$ . If $A$ and $S$ are finite
subsets of $V$, with $0\not\in S$, and $B\subseteq\mathbb{F}_{q}^{*}$ is a
collection scalars, then

$\sum_{\xi\in S}E(A,\xi B)\leq|A|^{2}|B|^{2}+|S||A||B|.$

Hence there exists $\xi\in S$ such that

$|A+\xi B|\geq\frac{1}{2}\min\\{|S|,|A||B|\\}.$

The lemma applied to $V=\mathbb{F}_{q}$, $S=\mathbb{F}_{q}^{*}$, and $A=B$
implies that $E(A,\xi A)>|A|^{3}/K$ for at most $Kq/|A|$ many $\xi$. The proof
of this fact is implicit in the proof of Theorem B. The majority of the
remainder of the paper is devoted to the task of refining this simple
corollary of Lemma 3.

##  3 Proof of Theorem B

In this section we prove Theorem B, which we recall here.

######  Theorem B.

Let $A$ be a set in $\mathbb{F}_{q}$ and $D_{\times}(A)$ be the quantity

$D_{\times}(A)=|\\{(a_{1},\ldots,a_{8})\in
A^{8}\colon(a_{1}-a_{2})(a_{3}-a_{4})=(a_{5}-a_{6})(a_{7}-a_{8})\\}|.$ (4)

Suppose that there is a positive constant $K$ such that $|A|\leq q/(4K)$ and

$D_{\times}(A)\geq\frac{|A|^{8}}{q}+\frac{3q|A|^{5}}{K}.$

There exists a set $X\subseteq\mathbb{F}_{q}$ such that $E(A,\xi
A)\geq|A|^{3}/K$ for all $\xi\in X$ and

$\frac{q}{K|A|}\leq|X|\leq\frac{4Kq}{3|A|}.$

###### Proof.

Let

$r(x)=r_{(A-A)(A-A)}(x)=|\\{(a_{1},\ldots,a_{4})\in
A^{4}\colon(a_{1}-a_{2})(a_{3}-a_{4})=x\\}|.$

Then

$D_{\times}(A)=\sum_{x\in\mathbb{F}_{q}}r^{2}(x).$

There are at most $4|A|^{6}$ solutions where either side of (4) is zero, thus

$\sum_{x\in\mathbb{F}_{q}}r^{2}(x)-\left|\left\\{\frac{a_{1}-a_{2}}{a_{5}-a_{6}}=\frac{a_{7}-a_{8}}{a_{3}-a_{4}}\not=0,\infty\right\\}\right|\leq
4|A|^{6}.$

For $\xi\in\mathbb{F}_{q}^{*}$, write

$Q_{\xi}=\left|\left\\{(a_{1},\ldots,a_{4})\in
A^{4}\colon\frac{a_{1}-a_{2}}{a_{3}-a_{4}}=\xi\right\\}\right|,$

so that

$\sum_{x\in\mathbb{F}_{q}}r^{2}(x)\leq\sum_{\xi\in\mathbb{F}_{q}^{*}}Q_{\xi}^{2}+4|A|^{6}.$
(5)

Note that $Q_{\xi}=E(A,\xi A)-|A|^{2}$, so by Lemma 3

$\sum_{\xi\in\mathbb{F}_{q}^{*}}Q_{\xi}\leq|A|^{4}.$ (6)

If we set

$E_{\xi}=E(A,\xi A)-\frac{|A|^{4}}{q},$

then by (3) the quantity $E_{\xi}$ is _positive_ for all $\xi$. For any subset
$S\subseteq\mathbb{F}_{q}^{*}$, Lemma 3 implies that

$\sum_{\xi\in S}E_{\xi}\leq\sum_{\xi\in\mathbb{F}_{q}^{*}}E_{\xi}\leq
q|A|^{2}.$ (7)

Now we estimate the second moment of $Q_{\xi}$. First we replace one power of
$Q_{\xi}$ by $E_{\xi}$ and estimate the error using (6).

$\displaystyle\sum_{\xi\in\mathbb{F}_{q}^{*}}Q_{\xi}^{2}$
$\displaystyle=\sum_{\xi\in\mathbb{F}_{q}^{*}}Q_{\xi}\left(E(A,\xi
A)-|A|^{2}\right)$
$\displaystyle=\sum_{\xi\in\mathbb{F}_{q}^{*}}Q_{\xi}\left(E_{\xi}+\frac{|A|^{4}}{q}-|A|^{2}\right)$
$\displaystyle=\sum_{\xi\in\mathbb{F}_{q}^{*}}Q_{\xi}E_{\xi}+\left(\frac{|A|^{4}}{q}-|A|^{2}\right)\sum_{\xi\in\mathbb{F}_{q}^{*}}Q_{\xi}$
$\displaystyle\leq\frac{|A|^{8}}{q}+\sum_{\xi\in\mathbb{F}_{q}^{*}}Q_{\xi}E_{\xi}.$

Hence by (5)

$D_{\times}(A)\leq\frac{|A|^{8}}{q}+\sum_{\xi\in\mathbb{F}_{q}^{*}}Q_{\xi}E_{\xi}+4|A|^{6}.$
(8)

Now we estimate the remaining sum over $\xi$. Let

$X=\\{\xi\in\mathbb{F}_{q}^{*}\colon Q_{\xi}\geq|A|^{3}/K\\}.$

Then, using (7),

$\sum_{\xi\in\mathbb{F}_{q}^{*}}Q_{\xi}E_{\xi}\leq\sum_{\xi\in
X}Q_{\xi}E_{\xi}+\frac{|A|^{3}}{K}\sum_{\xi\in\mathbb{F}_{q}^{*}}E_{\xi}\leq\sum_{\xi\in
X}Q_{\xi}E_{\xi}+\frac{q|A|^{5}}{K}.$ (9)

Combining the lower bound on $D_{\times}(A)$ in the hypothesis of the theorem,
the upper bound $|A|\leq q/(4K)$ (which implies $4|A|^{6}\leq q|A|^{5}/K$),
and equations (8) and (9), we get

$\sum_{\xi\in X}Q_{\xi}E_{\xi}\geq\frac{q|A|^{5}}{K}.$ (10)

By the trivial bound $Q_{\xi}E_{\xi}\leq|A|^{6}$ we derive $|X|\geq q/(|A|K)$.

The final step is to obtain an upper bound on $|X|$. The bound $|A|\leq
q/(4K)$ implies that $E_{\xi}\geq Q_{\xi}-|A|^{4}/q\geq 3|A|^{3}/(4K)$ for all
$\xi\in X$. By (7) we get

$\frac{3|A|^{3}}{4K}|X|\leq\sum_{\xi\in X}E_{\xi}\leq q|A|^{2},$

which implies the desired bound $|X|\leq 4Kq/(3|A|)$. ∎

##  4 Proof of Theorems C and D

###  4.1 Two auxiliary results

The proof of Theorem C relies on two auxiliary results. The first roughly
speaking asserts that if the additive energy $E(A,\xi A)$ is large for many
$\xi$ in $X$, then $|A+XA|$ is small.

######  Proposition 4.

Let $A,X\subseteq\mathbb{F}_{q}^{*}$. If there is a positive real number $K>0$
such that

$\sum_{\xi\in X}E(A,\xi A)\geq\frac{|A|^{3}|X|}{K},$

then there exist elements $\bar{a}\in A$ and $x_{0}\in X$ and subsets
$A_{1}\subseteq A-\bar{a}$ and $X^{\prime}\subseteq x_{0}^{-1}X$ such that:

  1. (i)

$\displaystyle|A_{1}|\gtrsim K^{-85}|A|$ and $|X^{\prime}|\gtrsim K^{-5}|X|$.

  2. (ii)

$|A_{1}+X^{\prime}A_{1}|\lesssim K^{226}|A_{1}|$.

  3. (iii)

$\displaystyle|A_{1}\pm A_{1}|\lesssim K^{92}|A_{1}|$.

  4. (iv)

$\displaystyle|A_{1}\pm x^{\prime}A_{1}|\lesssim K^{126}|A_{1}|$ for all
$x^{\prime}\in X^{\prime}$.

Moreover, if $E(A,\xi A)\geq|A|^{3}/K$ for all $\xi\in X$, then
$|X^{\prime}|\gtrsim K^{-4}|X|$.

The proposition, which is proved in Appendix A, follows from a more careful
analysis of the arguments of Bourgain in [4, Theorem C] and Bourgain–Glibichuk
in [6, Proposition 2]. The structure of our argument is very similar to
Bourgain’s, though the quantitative aspects of the bounds we obtain are
stronger than what is found in [6, Proposition 2].

The second auxiliary result is Theorem D, which we restate here.

######  Theorem D.

Let $W$ be a subset of an $\mathbb{F}_{q}$-vector space, let
$X\subseteq\mathbb{F}_{q}$ be a set of scalars, and let $F=\langle X\rangle$
be the subfield generated by $X$. If

  1. 1.

$|W+XW|\leq K_{1}|W|$,

  2. 2.

$|W+W|\leq K_{2}|W|$,

  3. 3.

$|W+xW|\leq K_{3}|W|$ for all $x\in X$, and

  4. 4.

$K_{1}^{4}K_{2}K_{3}^{4}<|X|$,

then

$|W|\geq\frac{1}{2K_{1}^{2}K_{3}^{2}}|\mathrm{Span}_{F}(W)|.$

We also record the following specialization of Theorem D, which will be used
in the proof of Corollary 1.

######  Corollary 5.

Let $q>2^{12}$ be a prime power, let $W,X\subset\mathbb{F}_{q}$ be sets and
$K_{1},K_{2},K_{3}$ be a real numbers. Suppose that $q^{1/4}<|X|<q^{1/2}$ and
$q^{1/2}<|W|\leq q^{2/3}$. If $|W+XW|\leq K_{1}|W|$, $|W+W|\leq K_{2}|W|$,
$|W+xW|\leq K_{3}|W|$ for all $x\in X$, and $K_{1}^{4}K_{2}K_{3}^{4}<|X|$,
then there exists a subfield $F$ of cardinality $q^{1/3}$ and $v_{1},v_{2}\in
W\setminus\\{0\\}$ such that $W\subseteq Fv_{1}+Fv_{2}$, $X\subseteq F$ and

$|W|\geq\frac{|F|^{2}}{2K_{1}^{2}K_{2}^{2}}.$

Corollary 5 and Theorem D are both proved further down in this section. Let us
now deduce Theorem C and Corollary 1, assuming the auxiliary results.

###  4.2 Proof of Theorem C and Corollary 1

######  Theorem C.

Let $A$ and $X$ be subsets of $\mathbb{F}_{q}^{*}$ and let $K\geq 1$ be a real
number such that $K^{1505}\lesssim|X|$. Suppose

$\sum_{\xi\in X}E(A,\xi A)\geq\frac{|A|^{3}|X|}{K}.$

There exists an element $\bar{a}$ in $A$, a subfield
$F\subseteq\mathbb{F}_{q}$, and an $F$-vector space $V\subseteq\mathbb{F}_{q}$
such that

$|V\cap(A-\bar{a})|\gtrsim\max\\{K^{-704}|V|,K^{-85}|A|\\}.$

Further, there is an element $x_{0}$ in $X$ and subsets $A_{1}\subseteq
A-\bar{a},X^{\prime}\subseteq x_{0}^{-1}X$ such that $F$ is the subfield
generated by $X^{\prime}$ and $V$ is the $F$-vector space generated by
$A_{1}$, and

$|A_{1}|\gtrsim K^{-85}|A|\qquad\mbox{and}\qquad|X^{\prime}|\gtrsim
K^{-5}|X|.$

Moreover, if $E(A,\xi A)\geq|A|^{3}/K$ for all $\xi\in X$ we have
$|X^{\prime}|\gtrsim K^{-4}|X|$ and only require $K^{1504}\lesssim|X|$.

###### Proof.

We are given

$\sum_{\xi\in X}E(A,\xi A)\geq\frac{|A|^{3}|X|}{K}.$

By Proposition 4 there exist elements $\bar{a}\in A$ and $x_{0}\in X$ and
subsets $A_{1}\subseteq A-\bar{a}$ and $X^{\prime}\subseteq x_{0}^{-1}X$ such
that

$|A_{1}+X^{\prime}A_{1}|\lesssim K^{226}|A_{1}|,|A_{1}+A_{1}|\lesssim
K^{92}|A_{1}|,|A_{1}+x^{\prime}A_{1}|\lesssim K^{126}|A_{1}|\,\forall
x^{\prime}\in X^{\prime},$ $|A_{1}|\gtrsim
K^{-85}|A|\qquad\mbox{and}\qquad|X^{\prime}|\gtrsim K^{-5}|X|.$

Since $1505=(4\cdot 226+92+4\cdot 126)+5$, the hypothesis
$K^{1505}\lesssim|X|$ means

$(K^{226})^{4}K^{92}(K^{126})^{4}\lesssim K^{-5}|X|\lesssim|X^{\prime}|$

and we may apply Theorem D. Letting $F$ be the field generated by
$X^{\prime}$, we get

$|A_{1}|\gtrsim
K^{-2\cdot(226+126)}|\mathrm{Span}_{F}(A_{1})|=K^{-704}|\mathrm{Span}_{F}(A_{1})|.$

Setting $V=\mathrm{Span}_{F}(A_{1})$, the last equation implies that

$|V\cap(A-\bar{a})|\gtrsim K^{-704}|V|.$

For the second lower bound on $|V\cap(A-\bar{a})|$, observe that
$|V\cap(A-\bar{a})|\geq|A_{1}|$, since $A_{1}\subseteq V,A-\bar{a}$.

The special case where $E(A,\xi A)\geq|A|^{3}/K$ for all $\xi\in X$ is deduced
similarly from the last part of Proposition 4. ∎

######  Corollary 1.

Let $A,X\subseteq\mathbb{F}_{q}^{*}$ be sets and $K$ be a positive real
number. Suppose $K^{1504}\lesssim|X|$, $q^{1/4}K^{4}\lesssim|X|<q^{1/2}$,
$q^{1/2}K^{85}\lesssim|A|\leq q^{2/3}$ and $E(A,\xi A)\geq|A|^{3}/K$ for all
$\xi\in X$.

There exists a subfield $F$ of cardinality $q^{1/3}$, $\bar{a}$ in $A$, and a
two-dimensional vector space $V$ over $F$ such that $|(A-\bar{a})\cap
V|\gtrsim K^{-85}|A|$.

###### Proof.

Proceeding like in the proof of Theorem C, only using the special case of
Proposition 4, we get elements $\bar{a}\in A$ and $x_{0}\in X$ and subsets
$A_{1}\subseteq A-\bar{a}$ and $X^{\prime}\subseteq x_{0}^{-1}X$ such that

$|A_{1}+X^{\prime}A_{1}|\lesssim K^{226}|A_{1}|,|A_{1}+A_{1}|\lesssim
K^{92}|A_{1}|,|A_{1}+x^{\prime}A_{1}|\lesssim K^{126}|A_{1}|\,\forall
x^{\prime}\in X^{\prime},$ $|A_{1}|\gtrsim
K^{-85}|A|\qquad\mbox{and}\qquad|X^{\prime}|\gtrsim K^{-4}|X|.$

As observed in the proof of Theorem C, because $K^{1504}\lesssim|X|$, we may
apply Corollary 5 to $A^{\prime}$ and $X^{\prime}$ as long as

$q^{1/4}<|X^{\prime}|<q^{1/2}\qquad\mbox{and}\qquad q^{1/2}<|A^{\prime}|\leq
q^{2/3}.$ (11)

The condition $q>2^{12}$ is irrelevant in this context. Assuming (11) for now,
we conclude that there is a subfield $F$ of cardinality $q^{1/3}$ and a two-
dimensional vector space $V$ over $F$ such that $A_{1}\subseteq V$. Therefore

$|(A-\bar{a})\cap V|\geq|A_{1}|\gtrsim K^{-85}|A|,$

as desired.

To ensure (11), it suffices to take

$q^{1/4}K^{4}\lesssim|X|<q^{1/2}\qquad\mbox{and}\qquad
q^{1/2}K^{85}\lesssim|A|\leq q^{2/3}.$

∎

###  4.3 A pivot argument for vector spaces

We now prove Theorem D, which is a specialization of Gill and Helfgott’s pivot
theorem [15]. Our approach is inspired by Tao’s concept of involved elements
[61, Section 1.5]. Throughout the remaining of this section $\mathbb{F}$ is a
finite field and $V$ is a vector space over $\mathbb{F}$.

For a subset $X\subseteq\mathbb{F}$ we denote by $\langle X\rangle$ the
subfield generated by $X$. We use ${\langle X\rangle}_{+}$ and ${\langle
X\rangle}_{\times}$ to denote the additive group and the multiplicative group
(union $\\{0\\}$) generated by $X$, respectively, so that

$\langle X\rangle=\langle\langle X\rangle_{\times}\rangle_{+}.$

(This is because $\langle\langle X\rangle_{\times}\rangle_{+}$ contains
$X\cup\\{0,1\\}$, is closed under addition, and is closed under
multiplication, since products of sums of products are sums of products; since
$\langle\langle X\rangle_{\times}\rangle_{+}$ is finite, closure implies the
existence of inverses.) For a subset $W\subseteq V$ we denote by
$\mathrm{Span}_{X}(W)$ the vector space over $\langle X\rangle$ generated by
the vectors in $W$. The key definition is the following.

######  Definition (Pivots and involved elements).

Let $V$ be a vector space over a finite field $\mathbb{F}$, $W\subseteq V$ and
$X\subseteq\mathbb{F}$. For $\xi$ in $V$, define $\phi_{\xi}\colon W\times
X\to V$ by $\phi_{\xi}(v,\alpha)=v+\alpha\xi$. We say that $\xi$ is a _pivot_
for $(W,X)$ if $\phi_{\xi}$ is injective.

An element is _involved_ with the sets $W$ and $X$, if it is not a pivot. We
denote by $\mathcal{I}_{W,X}$ the set of involved elements.

The rest of this section is devoted to showing that the collection of involved
elements has an exact algebraic structure (namely, it is a vector space)
assuming that $W$ and $X$ have weak algebraic structure (namely, $|W+XW|$ is
close to minimum).

The next lemma shows that involved elements have low complexity in terms of
$W$ and $X$.

######  Lemma 6 (Properties of involved elements).

Let $V$ be a vector space over a finite field $\mathbb{F}$, $W\subseteq V$ and
$X\subseteq\mathbb{F}$. A vector $\xi\in V$ is an involved element for $(W,X)$
if and only if

  * •

there exist distinct scalars $\alpha_{1}\neq\alpha_{2}\in X$ and vectors
$v_{1},v_{2}\in W$ such that $\xi=(\alpha_{1}-\alpha_{2})^{-1}(v_{2}-v_{1})$;

  * •

$|W+X\xi|<|W||X|$.

###### Proof.

Both parts follow from the non-injectivity of $\phi_{\xi}$.

For the first part note that there exist distinct
$(v_{1},\alpha_{1}),(v_{2},\alpha_{2})\in W\times X$ such that
$\phi_{\xi}(v_{1},\alpha_{1})=\phi(v_{2},\alpha_{2})$ precisely when
$v_{1}-v_{2}=\xi(\alpha_{1}-\alpha_{2})$. We cannot have
$\alpha_{1}=\alpha_{2}$ (else $v_{1}=v_{2}$).

For the second part note $|W+X\xi|=|\phi_{\xi}(W,X)|$. ∎

Lemma 6 implies that $\mathcal{I}_{W,X}\subseteq\mathrm{Span}_{X}(W)$, since
every involved element $\xi$ can be written as
$\xi=(\alpha_{1}-\alpha_{2})^{-1}(v_{2}-v_{1})$ with $\alpha_{i}\in X,v_{i}\in
W$. The following proposition proves the reverse inclusion when $|W+XW|$ and
$|W+W|$ are sufficiently small.

######  Proposition 7.

Let $V$ be a vector space over a finite field $\mathbb{F}$, $W\subseteq V$ and
$X\subseteq\mathbb{F}$. In the notation used in this section, if

  1. 1.

$|W+XW|\leq K_{1}|W|$,

  2. 2.

$|W+W|\leq K_{2}|W|$,

  3. 3.

$|W+xW|\leq K_{3}|W|$ for all $x\in X$, and

  4. 4.

$K_{1}^{4}K_{2}K_{3}^{4}<|X|$,

then $\mathrm{Span}_{X}(W)\subseteq\mathcal{I}_{W,X}$ and therefore
$\mathrm{Span}_{X}(W)=\mathcal{I}_{W,X}$.

In the proof of Proposition 7 we will repeatedly use a key observation: if
$\xi$ is an involved element, then we may strengthen the bound
$|W+X\xi|<|X||W|$ by exploiting the low complexity of $\xi$.

######  Lemma 8.

Let $V$ be a vector space over a finite field $\mathbb{F}$, $W\subseteq V$ and
$X\subseteq\mathbb{F}$. Suppose that $|W+XW|\leq K_{1}|W|$ and $|W+xW|\leq
K_{3}|W|$ for all $x\in X$. If $\xi$ is an involved element, then

$|W+X\xi|\leq K_{1}^{2}K_{3}^{2}|W|.$

###### Proof.

Since $\xi$ is an involved element, there exist $x_{1},x_{2}\in
X,w_{1},w_{2}\in W$ such that

$\xi=(x_{1}-x_{2})^{-1}(w_{2}-w_{1}).$

Thus

$(x_{1}-x_{2})[W+X\xi]=(x_{1}-x_{2})W+X(w_{2}-w_{1})\subseteq
x_{1}W-x_{2}W+XW-XW.$

By the Plünnecke–Ruzsa inequality for different summands in Lemma 2 we have

$|W+X\xi|\leq\left(\frac{|W+x_{1}W|}{|W|}\right)\left(\frac{|W+x_{2}W|}{|W|}\right)\left(\frac{|W+WX|}{|W|}\right)^{2}|W|\leq
K_{1}^{2}K_{3}^{2}|W|.$

∎

We apply Lemma 8 to prove that the set of involved elements is closed under
both addition and scalar multiplication, under suitable conditions on sumset
cardinalities.

######  Lemma 9 (Closure of involved elements under addition).

Let $V$ be a vector space over a finite field $\mathbb{F}$, $W\subseteq V$ and
$X\subseteq\mathbb{F}$. If $|W+XW|\leq K_{1}|W|$, $|W+W|\leq K_{2}|W|$, and
$|W+xW|\leq K_{3}|W|$ for all $x\in X$, where $K_{1}^{4}K_{2}K_{3}^{4}<|X|$,
then $\mathcal{I}_{W,X}\pm\mathcal{I}_{W,X}\subseteq\mathcal{I}_{W,X}$.

###### Proof.

Let $\xi_{1}$ and $\xi_{2}$ be elements of $\mathcal{I}_{W,X}$. By Lemma 6, to
show that $\xi_{1}+\xi_{2}\in\mathcal{I}_{W,X}$ we must establish
$|W+X(\xi_{1}+\xi_{2})|<|X||W|$.

Note $|W+X(\xi_{1}+\xi_{2})|\leq|W+X\xi_{1}+X\xi_{2}|$. To bound this sumset
we use Plünnecke’s inequality for different summands in Lemma 2 and Lemma 8.

$|W+X\xi_{1}+X\xi_{2}|\leq\frac{|W+W|}{|W|}\,\frac{|W+X\xi_{1}|}{|W|}\,\frac{|W+X\xi_{2}|}{|W|}\;|W|\leq
K_{1}^{4}K_{2}K_{3}^{4}|W|.$

Thus if $K_{1}^{4}K_{2}K_{3}^{4}<|X|$, we have the desired inequality

$|W+X(\xi_{1}+\xi_{2})|<|X||W|.$

We must also show that $\xi\in\mathcal{I}_{W,X}$ if and only if
$-\xi\in\mathcal{I}_{W,X}$. It is enough to prove that if
$\xi\in\mathcal{I}_{W,X}$, then $-\xi\in\mathcal{I}_{W,X}$. This follows from
Lemma 2, Lemma 8 and Lemma 6

$|W+X(-\xi)|\leq\frac{|W+W||W+X\xi|}{|W|}\leq
K_{1}^{2}K_{2}K_{3}^{2}|W|<|X||W|.$

∎

######  Lemma 10 (Closure of involved elements under scalar multiplication).

Let $V$ be a vector space over a finite field $\mathbb{F}$, $W\subseteq V$ and
$X\subseteq\mathbb{F}$. If $|W+XW|\leq K_{1}|W|$, $|W+W|\leq K_{2}|W|$, and
$|W+xW|\leq K_{3}|W|$ for all $x\in X$, where $K_{1}^{2}K_{3}^{3}<|X|$, then
$\mathcal{I}_{W,X}$ is closed under multiplication by $\langle
X\rangle_{\times}$.

###### Proof.

By Lemma 6 it is enough to show that, if $\xi$ is an involved element and
$\alpha\in X$, then

$|W+X(\alpha\xi)|\leq
K_{1}^{2}K_{3}^{3}|W|\qquad\mbox{and}\qquad|W+X(\alpha^{-1}\xi)|\leq
K_{1}^{2}K_{3}^{3}|W|.$

Indeed,

$|W+X(\alpha\xi)|\leq\frac{|W+\alpha W||\alpha W+X(\alpha\xi)|}{|\alpha
W|}=\frac{|W+\alpha W||W+X\xi|}{|W|}\leq K_{1}^{2}K_{3}^{3}|W|$

and, similarly,

$|W+X(\alpha^{-1}\xi)|=|\alpha W+X\xi|\leq\frac{|W+\alpha W||W+X\xi|}{|W|}\leq
K_{1}^{2}K_{3}^{3}|W|.$

It follows by induction that if $\alpha_{1},\ldots,\alpha_{n}\in X$ and
$\xi\in\mathcal{I}_{W,X}$, then

$\alpha_{1}^{\pm 1}\cdots\alpha_{n}^{\pm 1}\xi\in\mathcal{I}_{W,X}.$

∎

We now prove Proposition 7.

###### Proof of Proposition 7.

We want to show that the set $\mathcal{I}_{W,X}$ of involved elements contains
$\mathrm{Span}_{X}(W)$, where $\langle X\rangle$ is the subfield of
$\mathbb{F}$ generated by $X$.

First, we show that $\mathcal{I}_{W,X}$ contains $W$. If $\xi\in W$, then

$|W+X\xi|\leq|W+XW|<K_{1}|W|<|X||W|.$

Hence $\xi$ is an involved element by Lemma 6.

Now by Lemma 10, we have $\langle
X\rangle_{\times}W\subseteq\mathcal{I}_{W,X}$, and hence by Lemma 9 we have
for sums of any finite length

$\pm\langle X\rangle_{\times}W\pm\cdots\pm\langle
X\rangle_{\times}W\subseteq\mathcal{I}_{W,X},$

hence

$\langle\langle X\rangle_{\times}\rangle_{+}W\subseteq\mathcal{I}_{W,X}.$

Further,

$\langle X\rangle W+\cdots+\langle X\rangle W\subseteq\mathcal{I}_{W,X}$

for sums of any finite length, which implies that
$\mathrm{Span}_{X}(W)\subseteq\mathcal{I}_{W,X}$. ∎

###  4.4 Proof of Theorem D and Corollary 5

###### Proof of Theorem D.

Proposition 7 implies that $\mathcal{I}_{W,X}=\mathrm{Span}_{F}(W)$. Hence by
Lemma 3 applied to $S=\mathrm{Span}_{F}(W)$, there is an involved element
$\xi_{0}$ such that

$|W+X\xi_{0}|\geq\frac{1}{2}\min(|\mathrm{Span}_{F}(W)|,|X||W|).$

On the other hand, since $\xi_{0}$ is an involved element, Lemma 8 implies
that

$|W+X\xi_{0}|\leq K_{1}^{2}K_{3}^{2}|W|\leq|X|^{1/2}|W|<|X||W|/2,$

because $|X|>K_{1}^{4}K_{2}K_{3}^{4}\geq 1$. Therefore we have

$\frac{1}{2}|\mathrm{Span}_{F}(W)|\leq|W+X\xi_{0}|\leq K_{1}^{2}K_{3}^{2}|W|,$

which proves the theorem. ∎

Since $W\subseteq\mathrm{Span}_{F}(W)$, the lower bound on $|W|$ is fairly
tight. The inclusion $X\subseteq F$ implies $|X|\leq|F|$. The next step is to
show that, under suitable cardinality constraints on $X$ and $W$, $W$ must
have additional structure.

###### Proof of Corollary 5.

Let $q=p^{r}$ and $F=\langle X\rangle$, so that $|F|=p^{k}$ for $k\mid r$.
Also let $d=\dim(\mathrm{Span}_{F}(W))$. Our aim is to show that $d=2$ and
$|F|=q^{1/3}$.

Theorem D gives $|W|\geq K_{1}^{-2}K_{3}^{-2}|\mathrm{Span}_{F}(W)|/2$. This
implies

$|W|^{1/d}\leq|F|\leq(2K_{1}^{2}K_{3}^{3}|W|)^{1/d}.$ (12)

We know that $|F|\geq|X|>q^{1/4}$ and so $|F|$ must be one of
$q^{1/3},q^{1/2}$ or $q$.

Note next that $d>1$, because $d=1$ means $F=\mathrm{Span}_{F}(W)$. Therefore

$\frac{|F|}{2K_{1}^{2}K_{3}^{2}}\leq|W|\leq|F|.$

The constrains on $|W|$ and $|F|$ immediately prohibit $F$ from being anything
but $\mathbb{F}_{q}$. However, $F=\mathbb{F}_{q}$ is not possible either
because it would imply

$\frac{q^{3/4}}{2}\leq\frac{q}{2|X|^{1/2}}<\frac{q}{2K_{1}^{2}K_{3}^{3}}\leq|W|\leq
q^{2/3}.$

Thus $d\geq 2$ and inequality (12) implies

$|F|<(2|X|^{1/2}|W|)^{1/2}<(2q^{11/12})^{1/2}\leq q^{1/2}.$

Therefore $|F|=q^{1/3}$.

Going back to (12) we get

$q^{d/3}\leq 2K_{1}^{2}K_{3}^{2}|W|<2q^{11/12}\leq q.$

Therefore $d<3$ and so $d=2$.

We conclude $W\subseteq\mathrm{Span}_{F}(W)=Fv_{1}+Fv_{2}$ for linearly
independent $v_{1},v_{2}\in W$. ∎

##  5 Proof of Theorem E

The set up for this section is as follows: $q$ is a cube, $F$ is the subfield
of cardinality $q^{1/3}$, $V$ is a two-dimensional vector space over $F$, and
$A\subseteq V$. Theorem E asserts that if $|A|\gg q^{7/12}$, then
$|(A-A)(A-A)|>q/2$. It is proved in two steps: first we prove $|VV|>q/2$; then
we prove that if $|A|>\sqrt{2}q^{7/12}$, then $(A-A)(A-A)=VV$.

###  5.1 Basic facts

We begin with some basic facts about $\mathbb{F}_{q}$, $V$ and $\widehat{V}$,
the dual group of $V$ viewed as a commutative group under addition.

Let $\xi\in V\setminus F$. Note that $\\{1,\xi\\}$ is a linearly independent
set in $V$ and forms a basis of $V$. Hence $V=F+F\xi$. Moreover,
$\\{1,\xi,\xi^{2}\\}$ is linearly independent in $\mathbb{F}_{q}$ (if
$\xi^{2}$ were a non-trivial linear combination of $\\{1,\xi\\}$, then $V$
would be closed under multiplication and therefore would be a subfield of
cardinality $q^{2/3}$). This means that $\mathbb{F}_{q}=F+F\xi+F\xi^{2}$.

Suppose now that $V$ is a vector space over a field $F$. Let
$\psi\in\widehat{F}$ be a non-trivial additive character of $F$. The dual
group $\widehat{V}$ of additive characters of $V$ consists of characters of
the form $v\mapsto\psi(v\cdot m)$, where $m$ is an element of $V$. The
orthogonality of characters implies that

$\frac{1}{|V|}\sum_{m\in V}\psi(v\cdot
m)=\left\\{\begin{array}[]{lll}1&\mbox{if}&v=0\\\ 0&\mbox{if}&v\neq
0\end{array}\right..$

For a set $A\subseteq V$ we denote by $A(v)$ the indicator function on $A$ and
write

$\widehat{A}(m)=\sum_{v\in V}A(v)\psi(-v\cdot m)=\sum_{v\in A}\psi(-v\cdot m)$

for the Fourier coefficients of $A$.

###  5.2 The product set of the vector space

######  Proposition 11.

Let $q$ be a cube. Suppose $F\subset\mathbb{F}_{q}$ is the subfield of
cardinality $q^{1/3}$ and $V\subset\mathbb{F}_{q}$ is a two-dimensional vector
space over $F$.

  1. (i)

In odd characteristic: $\displaystyle|VV|=\frac{|F|^{3}+2|F|^{2}-|F|}{2}$.

  2. (ii)

In even characteristic: $\displaystyle|VV|=\frac{|F|^{3}+|F|^{2}}{2}$.

In particular, $|V|>q/2$ and $|VV|=(1+o(1))q/2$.

###### Proof.

We first note $0\in VV$. For non-zero elements
$a+b\xi+c\xi^{2}\in\mathbb{F}_{q}$ we seek $u,v\in V$ such that
$uv=a+b\xi+c\xi^{2}$. After scaling we may assume that $u=1+cz^{-1}\xi$ and
$v=a+z\xi$ for some $z\in F^{*}$. Next we observe that

$a+b\xi+c\xi^{2}=(1+cz^{-1}\xi)(a+z\xi)$

precisely when $z^{2}-bz+ac=0$. This means that $a+b\xi+c\xi^{2}\in VV$
precisely when the quadratic monic polynomial $z^{2}-bz+ac$ has a root in $F$
(the case $a=b=c=0$ is included here). We treat the cases of even and odd
characteristic separately.

Odd characteristic: The quadratic polynomial above has a root precisely when
its discriminant $b^{2}-4ac$ is a square. We set $S=\\{x^{2}:x\in F\\}$ to be
the set of squares and count the number of ordered triples $(a,b,c)\in F\times
F\times F$ such that $b^{2}-4ac\in S$. To this end, for $y\in F$, we write
$r(y)=|\\{(a,c)\in F\times F:y=4ac\\}|$ for the number of ordered
representations of $y$ as a product $4ac$ with $a,c\in F$. Observe that
$r(y)=|F|-1$ for non-zero $y$ and $r(0)=2|F|-1$.

The number of ordered triples $(a,b,c)\in F\times F\times F$ such that
$(a,b,c)\in VV$ equals

$\displaystyle\sum_{b\in F}\sum_{s\in S}r(b^{2}-s)$ $\displaystyle=\sum_{b\in
F}\left(r(0)+\sum_{s\in S\setminus\\{b^{2}\\}}r(b^{2}-s)\right)$
$\displaystyle=|F|(2|F|-1+(|F|-1)(|S|-1))$ $\displaystyle=|F|(|F||S|+|F|-|S|)$
$\displaystyle=\frac{|F|^{3}+2|F|^{2}-|F|}{2}.$

Even characteristic: Let $|F|=2^{n}$. Recall that the Galois group of $F$ over
$\mathbb{F}_{2}$ is generated by $\sigma\colon x\mapsto x^{2}$. The trace
function $\mathrm{Tr}:F\to\mathbb{F}_{2}$ is defined by

$\mathrm{Tr}(x)=\sum_{i=0}^{n-1}\sigma^{i}(x)=x+x^{2}+x^{4}+\dots+x^{2^{n-1}}.$

Since $\sigma$ is $\mathbb{F}_{2}$-linear, we may view $\mathrm{Tr}$ as a
$\mathbb{F}_{2}$-linear functional on $F$. Let $S=\\{x\in
F:\mathrm{Tr}(x)=0\\}$ be its kernel. In particular note that $|S|=|F|/2$
because $\mathrm{Tr}$ is non-trivial.

To solve the equation

$z^{2}+bz+ac=0$ (13)

we consider two cases.

First, suppose that $b=0$. Then (13) becomes $z^{2}=ac$, which has the unique
solution $z=\sigma^{-1}(ac)$.

Second, suppose that $b\not=0$. Then by replacing $z$ with $z/b$ we may put
(13) in the form

$z^{2}+z+\frac{ac}{b^{2}}=0\implies z^{2}+z=\frac{ac}{b^{2}}.$ (14)

Note that $z^{2}+z=z-\sigma(z)$. Hilbert’s Theorem 90 [34, Theorem 6.3] states
that for cyclic extensions, $w=z-\sigma(z)$ if and only the trace of $w$ is
zero. Hence (14) has a solution if and only if $ac/b^{2}\in S$.

To summarize: the quadratic polynomial has a root precisely when $b=0$ or
$ac\in b^{2}S$.

Writing $r(y)=|\\{(a,c)\in F\times F:y=ac\\}|$ for the number of ordered
representations of $y$ as a product $ac$ with $a,c\in F$ and noting that
$r(y)=|F|-1$ for non-zero $y$ and $r(0)=2|F|-1$ we see that the number of
ordered triples $(a,b,c)\in F\times F\times F$ such that $(a,b,c)\in VV$
equals

$\displaystyle|F|^{2}+\sum_{b\in F^{*}}\sum_{s\in S}r(b^{2}s)$
$\displaystyle=|F|^{2}+\sum_{b\in F^{*}}\left(r(0)+\sum_{s\in
S\setminus\\{0\\}}r(b^{2}s)\right)$
$\displaystyle=|F|^{2}+(|F|-1)(2|F|-1+(|F|-1)(|S|-1))$
$\displaystyle=|F|(|F||S|+|F|-|S|)$ $\displaystyle=\frac{|F|^{3}+|F|^{2}}{2}.$

∎

###  5.3 Large subsets of vector spaces

The second step in the proof of Theorem E is to prove that if $|A|\gg
V^{7/8}=q^{7/12}$, then $(A-A)(A-A)=VV$. We begin with a generalisation of a
result of Hart, Iosevich, and Solymosi [23, Theorem 1.4]. Its importance in
our setting will become clear in the forthcoming corollary.

######  Proposition 12.

Let $V$ be a vector space over a field $F$, $u,v\in V\setminus\\{0\\}$ be non-
zero vectors and $A\subseteq V$ be a set in $V$. Suppose
$|A|\geq\sqrt{2}|V|/|F|^{1/4}.$ There exists $x\in F^{*}$ such that both $xu$
and $x^{-1}v$ belong to $A-A$.

###### Proof.

Writing

$r_{A-A}(t)=|\\{(a,b)\in A\times A:t=a-b\\}|$

for the number of ordered ways to express $t\in V$ as difference in $A-A$, we
must prove

$\sum_{x\in F^{*}}r_{A-A}(xu)r_{A-A}(x^{-1}v)>0.$ (15)

Recall that $\psi\in\widehat{F}$ is a non-trivial additive character of $F$
and that, for all $m\in V$, the function $v\to\psi(m\cdot v)$ is an additive
character of $V$. By character orthogonality

$\displaystyle r_{A-A}(t)$ $\displaystyle=\frac{1}{|V|}\sum_{m\in
V}\sum_{a,b\in A}\psi((t+a-b)\cdot m)$ $\displaystyle=\frac{1}{|V|}\sum_{m\in
V}\left|\sum_{a\in A}\psi(a\cdot m)\right|^{2}\psi(t\cdot m)$
$\displaystyle=\frac{1}{|V|}\sum_{m\in V}|\widehat{A}(m)|^{2}\psi(t\cdot m).$

Therefore, after some rearranging, the left side of (15) equals

$\displaystyle\frac{1}{|V|^{2}}\sum_{m\in V}\sum_{m^{\prime}\in
V}|\widehat{A}(m)|^{2}|\widehat{A}(m^{\prime})|^{2}\left(\sum_{x\in
F^{*}}\psi(x(u\cdot m)+x^{-1}(v\cdot m^{\prime}))\right).$ (16)

If $m\cdot u\neq 0$ or $m^{\prime}\cdot v\neq 0$, then the bracketed sum is a
Kloosterman sum or a Ramanujan sum and its modulus is at most $2|F|^{1/2}$,
see [31, Theorem 11.11] and [11] for even characteristic. Otherwise, when
$m\cdot u=m^{\prime}\cdot v=0$, the bracketed sum equals $|F|-1$. Substituting
in (16), we see that the left side of (15) equals

$\displaystyle\frac{|F|-1}{|V|^{2}}\sum_{\begin{subarray}{c}m\cdot u=0\\\
m^{\prime}\cdot
v=0\end{subarray}}|\widehat{A}(m)|^{2}|\widehat{A}(m^{\prime})|^{2}+$
$\displaystyle\quad\frac{1}{|V|^{2}}\sum_{\begin{subarray}{c}m\cdot u\neq 0\\\
\text{ or }\\\ m^{\prime}\cdot v\neq
0\end{subarray}}|\widehat{A}(m)|^{2}|\widehat{A}(m^{\prime})|^{2}\left(\sum_{x\in
F^{*}}\psi(x(u\cdot m)+x^{-1}(v\cdot m^{\prime}))\right).$

The first summand is bounded from below by the contribution coming from
$m=m^{\prime}=0$ (noting that the remaining terms are all positive), which is
$(|F|-1)|A|^{4}/|V|^{2}$. The modulus of the second summand is at most

$2|F|^{1/2}\frac{1}{|V|^{2}}\sum_{m\neq 0}\sum_{m^{\prime}\neq
0}|\widehat{A}(m)|^{2}|\widehat{A}(m^{\prime})|^{2}=2|F|^{1/2}\left(|A|-\frac{|A|^{2}}{|V|}\right)^{2}.$

Therefore the left side of (15) is positive if

$\frac{(|F|-1)|A|^{4}}{|V|^{2}}>2|F|^{1/2}\left(|A|-\frac{|A|^{2}}{|V|}\right)^{2},$

which holds when $|A|^{2}|F|^{1/2}>2|V|^{2}$. ∎

######  Corollary 13.

Let $\mathbb{F}_{q}$ be a finite field, $F$ a subfield of $\mathbb{F}_{q}$,
$V\subseteq\mathbb{F}_{q}$ be a vector space over $F$, and $A\subseteq V$ be a
set in $V$. If $|A|\geq\sqrt{2}|V|/|F|^{1/4}$, then $(A-A)(A-A)=VV$.

In particular, if $\mathbb{F}_{q}$ is a cubic extension of $F$ and $V$ is a
two dimensional vector space over $F$, then
$|A|\geq\sqrt{2}|V|^{7/8}=\sqrt{2}q^{7/12}$ implies $(A-A)(A-A)=VV$.

###### Proof.

The origin $0$ belongs to both $(A-A)(A-A)$ and $VV$. Given $w\in
VV\setminus\\{0\\}$, there exist $u,v\in V\setminus\\{0\\}$ such that $w=uv$.
By Proposition 12 there exists $x\in F^{*}$ such that both $xu,x^{-1}v\in
A-A$. Therefore $w=uv=(xu)(x^{-1}v)\in(A-A)(A-A)$. ∎

######  Remark.

The proof has the curious characteristic that we use additive characters of
$V$ to deduce something about elements of $\mathbb{F}_{q}$ that may not belong
to $V$.

##  6 Proof of Theorem A

At last we are ready to prove Theorem A.

######  Theorem A.

For all $q$ and all sets $A\subseteq\mathbb{F}_{q}$ that satisfy
$\displaystyle|A|\gtrsim q^{\tfrac{2}{3}-\tfrac{1}{13,542}}$, we have
$|(A-A)(A-A)|>q/2$.

We consider separately two cases. The first is loosely speaking the case where
$D_{\times}(A)$ is large and is where Theorem B, Corollary 1, and Theorem E
are used. The second case, where $D_{\times}(A)$ is small, only requires a
simple second moment argument.

A peculiarity of the argument is that the first case leads to a better lower
bound for $|A|$. The explanation for this is that in order to apply Corollary
1 we need $D_{\times}(A)-|A|^{8}/q$ to be very large. Once we assume this and
apply the corollary, we are in the regime of Theorem E and the rest of the
argument is fairly efficient. The price for assuming that
$D_{\times}(A)-|A|^{8}/q$ is large is paid when applying the complimentary
second moment argument. It is not possible to balance the two parts of the
argument because the first part stops working before it can it be balanced
with the second.

###  6.1 Case I: Large $D_{\times}(A)$

We assume that

$D_{\times}(A)\geq\frac{|A|^{8}}{q}+\frac{3q|A|^{5}}{K}\text{ for
}K\lesssim\left(\frac{q}{|A|}\right)^{1/1505}.$

To be able easily confirm that the various mild constraints appearing in
Theorem B, Corollary 1, and Theorem E are indeed satisfied, we assume that
$q^{3/5}\leq|A|\leq q^{2/3}$ (the result of Bennett, Hart, Iosevich,
Pakianathan, and Rudnev [3] deals with larger $|A|$). This gives the generous
bound $K\lesssim q^{1/3,000}$, which is adequate for this purpose.

In particular, we have $|A|\ll q/K$. Theorem B gives a set $X$ such that
$E(A,\xi A)\geq|A|^{3}/K$ for all $\xi\in X$ and

$\frac{q}{K|A|}\leq|X|\leq\frac{4Kq}{3|A|}\ll Kq^{2/5}<q^{1/2}.$

We now apply Corollary 1. The constraints on $|X|$ and $|A|$ are satisfied
because of the constraints on $|A|$ and $|X|$ and $K$. The, more restrictive,
condition $K^{1504}\lesssim|X|$ is satisfied because of the assumption
$K^{1505}\lesssim q/|A|$:

$K^{1504}\lesssim\frac{q}{K|A|}\leq|X|.$

Corollary 1 now gives a subfield $F$ of cardinality $q^{1/3}$, a two-
dimensional vector space $V$ over $F$ and $\bar{a}\in A$ such that
$|(A-\bar{a})\cap V|\gtrsim K^{-85}|A|$.

The final step is to apply Theorem E to the set $A_{\bar{a}}=(A-\bar{a})\cap
V$. If $|A_{\bar{a}}|\gg|V|^{7/8}=q^{7/12}$, then

$|(A-A)(A-A)|\geq|(A_{\bar{a}}-A_{\bar{a}})(A_{\bar{a}}-A_{\bar{a}})|>\frac{q}{2}.$

The condition $|A_{\bar{a}}|\gg q^{7/12}$ is satisfied when

$|A|\left(\frac{|A|}{q}\right)^{85/1505}\gtrsim q^{7/12}\impliedby|A|\gtrsim
q^{2,311/3,816}.$

Note here that $2,311/3,816<2/3-1/13,542$ and so the theorem holds in this
case.

###  6.2 Case II: Small $D_{\times}(A)$

We assume that

$D_{\times}(A)\leq\frac{|A|^{8}}{q}+\frac{3q|A|^{5}}{K}\text{ for
}K\gtrsim\left(\frac{q}{|A|}\right)^{1/1505}.$

In particular, if $|A|\gtrsim q^{3,009/4,514}=q^{2/3-1/13,542}$, then

$\frac{3q|A|^{5}}{K}\leq\frac{|A|^{8}}{q}.$

A few basic observations are now adequate: $(A-A)(A-A)$ is the support of the
function $r_{(A-A)(A-A)}$ and

$\sum_{x\in\mathbb{F}_{q}}r_{(A-A)(A-A)}(x)=|A|^{4}\qquad\mbox{and}\qquad\sum_{x\in\mathbb{F}_{q}}r_{(A-A)(A-A)}(x)^{2}=D_{\times}(A).$

The Cauchy-Schwarz inequality implies

$|(A-A)(A-A)|\geq\frac{\left(\sum_{x}r_{(A-A)(A-A)}(x)\right)^{2}}{\sum_{x}r_{(A-A)(A-A)}(x)^{2}}=\frac{|A|^{8}}{D_{\times}(A)}>\frac{q}{2}.\qed$

##  7 Proof of Theorem F

We prove a generalisation of [37, Theorem 27].

######  Theorem F.

For all constants $L>0$ there exists a constant $c>0$ such that for all primes
$p$ and all sets $A,B,C,D\subseteq\mathbb{F}_{p}$ that satisfy
$|A||B||C||D|>Lp^{12/5}$ and (assuming $|A|\leq|B|$, $|C|\leq|D|$, and
$|B|\leq|D|)$ $|A||B|^{4}|C|\geq p^{2}|D|^{2}$ , we have

$|(A-B)(C-D)|>cp.$

The result can be applied to sets like $(A+A^{2})(A-A^{-1})$.

We use the following generalisation of the quantity $D_{\times}(A)$. Given
four sets $A,B,C,D\subseteq\mathbb{F}_{p}$ we denote by $D_{\times}(A,B,C,D)$
the number of ordered solutions to the equation

$(a_{1}-b_{1})(c_{1}-d_{1})=(a_{2}-b_{2})(c_{2}-d_{2})$

with $a_{1},a_{2}\in A$, $b_{1},b_{2}\in B$, $c_{1},c_{2}\in C$ and
$d_{1},d_{2}\in D$. We continue to write $D_{\times}(A)$ in place of
$D_{\times}(A,A,A,A)$.

The proof is broken down in three steps. We first relate $D_{\times}(A,B,C,D)$
to $D_{\times}(A)$, $D_{\times}(B)$, $D_{\times}(C)$, and $D_{\times}(D)$;
then we use a recent result of Roche-Newton, Rudnev, Shkredov, and the authors
on collinear triples to bound $D_{\times}(A)$ [37]; the proof is then
completed by the standard second moment argument given in Section 6.2. The
middle step, where all the non-trivial work lies, depends on Rudnev’s points-
planes incidence bound [46] and Lemma 3.

Let $D_{\times}(A)^{*}$ denote the non-zero solutions to $D_{\times}(A)$.

######  Lemma 14.

Let $q$ be a prime power and $A,B,C,D$ be sets in $\mathbb{F}_{q}$. Suppose
$|A|\leq|B|$, $|C|\leq|D|$ and $|B|\leq|D|$.

$\displaystyle D_{\times}(A,B,C,D)$
$\displaystyle\leq(D_{\times}(A)^{*}\,D_{\times}(B)^{*}\,D_{\times}(C)^{*}\,D_{\times}(D)^{*})^{1/4}$
$\displaystyle\quad\quad+4|A|^{2}|C|^{2}|D|^{2}.$

###### Proof.

We decompose $D_{\times}(A,B,C,D)$ in two parts: $D_{\times}(A,B,C,D)^{0}$,
which is the number of zero solutions to the equation defining
$D_{\times}(A,B,C,D)$; and $D_{\times}(A,B,C,D)^{*}$ which is the number of
non-zero solutions to the equation defining $D_{\times}(A,B,C,D)$.

We first bound $D_{\times}(A,B,C,D)^{0}$: It is at most

$\displaystyle|A|^{2}|C|^{2}|D|^{2}+2|A|^{2}|B||C|^{2}|D|+|A|^{2}|B|^{2}|C|^{2}$
$\displaystyle=|A|^{2}|C|^{2}(|B|+|D|)^{2}$ $\displaystyle\leq
4|A|^{2}|C|^{2}|D|^{2}.$

To bound $D_{\times}(A,B,C,D)^{*}$ we use an argument similar to that in the
proof of Theorem B. The first step is to show

$D_{\times}(A,B,C,D)^{*}\leq(D_{\times}(A,B,A,B)^{*})^{1/2}(D_{\times}(C,D,C,D)^{*})^{1/2}.$

Indeed

$\displaystyle D_{\times}(A,B,C,D)^{*}$
$\displaystyle=\sum_{\xi\in\mathbb{F}_{q}^{*}}r_{\frac{A-B}{A-B}}(\xi)\,r_{\frac{C-D}{C-D}}(\xi)$
$\displaystyle\leq\left(\sum_{\xi\in\mathbb{F}_{q}^{*}}r_{\frac{A-B}{A-B}}(\xi)^{2}\right)^{1/2}\left(\sum_{\xi\in\mathbb{F}_{q}^{*}}r_{\frac{C-D}{C-D}}(\xi)^{2}\right)^{1/2}$
$\displaystyle(D_{\times}(A,B,A,B)^{*})^{1/2}(D_{\times}(C,D,C,D)^{*})^{1/2}.$

We proceed by showing, say,

$D_{\times}(A,B,A,B)^{*}\leq(D_{\times}(A)^{*})^{1/2}(D_{\times}(B)^{*})^{1/2}.$

Indeed,

$\displaystyle D_{\times}(A,B,A,B)^{*}$
$\displaystyle=\sum_{\xi\in\mathbb{F}_{q}^{*}}r_{\frac{A-B}{A-B}}(\xi)^{2}$
$\displaystyle=\sum_{\xi\in\mathbb{F}_{q}^{*}}\sum_{x\in\mathbb{F}_{q}}r_{A-\xi
A}(x)\,r_{B-\xi B}(x)$
$\displaystyle\leq\sum_{\xi\in\mathbb{F}_{q}^{*}}\left(\sum_{x\in\mathbb{F}_{q}}r_{A-\xi
A}(x)^{2}\right)^{1/2}\left(\sum_{x\in\mathbb{F}_{q}}r_{B-\xi
B}(x)^{2}\right)^{1/2}$
$\displaystyle\leq\left(\sum_{\xi\in\mathbb{F}_{q}^{*}}\sum_{x\in\mathbb{F}_{q}}r_{A-\xi
A}(x)^{2}\right)^{1/2}\left(\sum_{\xi\in\mathbb{F}_{q}^{*}}\sum_{x\in\mathbb{F}_{q}}r_{B-\xi
B}(x)^{2}\right)^{1/2}$
$\displaystyle\leq\left(\sum_{\xi\in\mathbb{F}_{q}^{*}}r_{A-A}(\xi)^{2}\right)^{1/2}\left(\sum_{\xi\in\mathbb{F}_{q}^{*}}r_{B-B}(\xi)^{2}\right)^{1/2}$
$\displaystyle=(D_{\times}(A)^{*})^{1/2}(D_{\times}(B)^{*})^{1/2}.$

Therefore

$D_{\times}(A,B,C,D)^{*}\leq(D_{\times}(A)^{*})^{1/4}(D_{\times}(B)^{*})^{1/4}(D_{\times}(C)^{*})^{1/4}(D_{\times}(D)^{*})^{1/4},$

which finishes the proof of the lemma. ∎

We now state the upper bound on $D_{\times}(A)$ given in [37]. This time the
bound only holds in $\mathbb{F}_{p}$.

######  Theorem 15.

Let $p$ be a prime and $A\subseteq\mathbb{F}_{p}$ be a set.

$D_{\times}(A)-\frac{|A|^{8}}{p}\ll p^{1/2}|A|^{11/2}.$

###### Proof.

Let

$T(A)=|\\{(a_{1},\dots,a_{6})\in
A^{6}:(a_{1}-a_{2})(a_{3}-a_{4})=(a_{1}-a_{5})(a_{3}-a_{6})\\}|.$

An application of Cauchy-Schwarz (see [41, Lemma 2.7]) gives

$D_{\times}(A)\leq|A|^{2}\,T(A).$

Theorem 10 (1) in [37] states

$T(A)-\frac{|A|^{6}}{p}\ll p^{1/2}|A|^{7/2}.$

Combining the two inequalities proves the theorem. ∎

Proving Theorem F is now straightforward.

###### Proof of Theorem F.

$(A-B)(C-D)$ is the support of $r_{(A-B)(C-D)}$. Similarly to the second part
of the proof of Theorem A we have

$|(A-B)(C-D)|\geq\frac{\left(\sum_{x}r_{(A-B)(C-D)}(x)\right)^{2}}{\sum_{x}r_{(A-B)(C-D)}(x)^{2}}=\frac{|A|^{2}|B|^{2}|C|^{2}|D|^{2}}{D_{\times}(A,B,C,D)}.$

By Lemma 14 and Theorem 15 we have

$\displaystyle D_{\times}(A,B,C,D)^{4}$ $\displaystyle\ll
D_{\times}(A)^{*}\,D_{\times}(B)^{*}D_{\times}(C)^{*}\,D_{\times}(D)^{*}+(|A||B||D|)^{8}$
$\displaystyle\ll\frac{(|A||B||C||D|)^{8}}{p^{4}}+p^{2}(|A||B||C||D|)^{11/2}+(|A||C||D|)^{8}.$

The first term dominates when $|A||B||C||D|\gg p^{12/5}$. For sufficiently
large $C$ we get that if $|A||B||C||D|>Cp^{12/5}$, then
$D_{\times}(A,B,C,D)\ll(|A||B||C||D|)^{2}/p$, in which case $|(A-B)(C-D)|\gg
p$. ∎

##  8 Theorem C over prime order fields

Over prime finite fields there are quantitatively strong versions of the
results of Bourgain [4] and Bourgain–Glibichuk [6]. We briefly state two such
results for prime fields, for reference and comparison to the results in this
paper. The first was shown to the authors by Rudnev.

######  Theorem 16 (Rudnev).

Let $p$ be a prime, $A\subseteq\mathbb{F}_{p}$, and
$X\subseteq\mathbb{F}_{p}^{*}$. Suppose that $|A|^{2}|X|\ll p^{2}$.

$\displaystyle\sum_{\xi\in X}E(A,\xi A)$ $\displaystyle\ll
E(A)^{1/2}\,(|A|^{3/2}|X|^{3/4}+|A||X|).$

A careful analysis shows that the above implies that if $|A|\geq p^{1/2}$,
then

$D_{\times}(A)-\frac{|A|^{8}}{p}\ll p^{2/3}|A|^{10/3}E(A)^{2/3}.$

This is stronger than Theorem 15 when $E(A)\leq p^{-1/4}|A|^{13/4}$.

The second result is in [36]. It is stronger than Theorem 16 when
$E(A)\geq|A|^{3}/|X|^{1/6}\gg|A|^{5/2}$.

######  Theorem 17.

Let $p$ be a prime, $A\subseteq\mathbb{F}_{p}$, and
$X\subseteq\mathbb{F}_{p}^{*}$. Suppose that $|A|\ll p^{2/3}$ and
$|X|\ll|A|^{3}$.

$\displaystyle\sum_{\xi\in X}E(A,\xi A)$ $\displaystyle\ll|A|^{3}|X|^{2/3}.$

## Appendix

##  Appendix A Proof of Proposition 4

###  A.1 Two combinatorial lemmata

Many of the quantitative improvements we offer to existing results in the
literature are based on the following elementary lemma. These results are well
known, but we state them here for precision in their application.

######  Lemma 18 (Popularity principle).

Fix a number $0<\lambda<1$, let $S$ be a finite set, and let $f$ be a function
such that $f(x)\geq 0$ for all $x$ in $S$.

  1. 1.

Suppose that

$\sum_{x\in S}f(x)\geq\mu.$

Let $P_{\lambda}=\\{x\in S\colon f(x)\geq\lambda\mu/|S|\\}$. Then

$\sum_{x\in P_{\lambda}}f(x)\geq(1-\lambda)\mu.$ (17)

Further, if $f(x)\leq M$ for all $x$ in $S$, then
$|P_{\lambda}|\geq(1-\lambda)\mu/M$.

  2. 2.

Suppose that for all $x$ in $S$, we have $w(x)\geq 0$ and $f(x)\leq M$. Let
$W=\sum_{x\in S}w(x)$. If

$\sum_{x\in S}f(x)w(x)\geq\mu,$

then there exists a subset $P_{*}\subseteq S$ and a number $N$ such that

$\displaystyle N$ $\displaystyle\leq f(x)<2N\qquad\forall x\in P_{*}$
$\displaystyle\frac{\lambda\mu}{W}$ $\displaystyle\leq N\leq M$ (18)
$\displaystyle\frac{(1-\lambda)\mu}{\log_{2}M}$ $\displaystyle\leq\sum_{x\in
P_{*}}f(x)w(x)\leq 2N\sum_{x\in P_{*}}w(x)\leq 2NW.$

When $w(x)=1$ for all $x\in S$, the second part of this lemma is just a dyadic
pigeonholing argument applied after the first part of lemma. The general
statement of the second part follows from dyadic pigeonholing applied after a
weighted version of the first part.

We also use a standard combinatorial lemma.

######  Lemma 19 (Cauchy-Schwarz intersection lemma).

Let $S$ be a finite index set and let $T_{s}$ be a family of subsets of a set
$T$. Then

$\left(\sum_{s\in S}|T_{s}|\right)^{2}\leq|T|\sum_{s,s^{\prime}\in
S}|T_{s}\cap T_{s^{\prime}}|.$

Further, if there exists $\delta>0$ such that

$\sum_{s\in S}|T_{s}|\geq\delta|S||T|,$

then there exists a subset $P\subseteq S\times S$ such that

  1. 1.

$|T_{s}\cap T_{s^{\prime}}|\geq\delta^{2}|T|/2$ for all pairs $(s,s^{\prime})$
in $P$.

  2. 2.

$|P|\geq\delta^{2}|S|^{2}/2$.

###  A.2 The Balog-Szemerédi-Gowers Theorem

Before proving Proposition 4 we present a corollary of the Balog-Szemerédi-
Gowers Theorem [2, 17] that suits our purposes. Proposition 21, below,
improves a result of Bourgain and Garaev [5, Lemmata 2.3 and 2.4].

We follow Sudakov, Szemerédi, and Vu’s graph-theoretic method [59], using a
slight improvement due to Tao and Vu [62, Corollary 6.20].

######  Lemma 20 (Paths of length three).

Let $K$ be a positive number, and let $G=G(A,B,E)$ be a bipartite graph with
$|B|\leq|A|$ and $|E|=|A||B|/K$. There exist subsets $A^{\prime}\subseteq A$
and $B^{\prime}\subseteq B$ such that

$|A^{\prime}|\geq\frac{|A|}{4\sqrt{2}K}\qquad\mbox{and}\qquad|B^{\prime}|\geq\frac{|B|}{4K},$

and for each $a\in A^{\prime},b\in B^{\prime}$ there are
$|A||B|/(2^{12}K^{5})$ paths of length 3 with endpoints $a$ and $b$.

Note that there is a typo in the print version of [62]—the factor $K^{4}$
should be $K^{5}$; the errata can be found on the first author’s webpage.

We combine Lemma 20 with Lemma 18 to prove the following.

######  Proposition 21.

Let $K$ be a positive number, and let $A$ and $B$ be finite subsets of a
commutative group such that $|B|\leq|A|$ and $E(A,B)=(|A||B|)^{3/2}/K$.

Then there exist subsets $A^{\prime}\subseteq A$ and $B^{\prime}\subseteq B$
such that

$|A^{\prime}|\gtrsim\frac{|A|}{K}\qquad\mbox{and}\qquad|B^{\prime}|\gtrsim\frac{|B|}{K},$

and

$|A^{\prime}+B^{\prime}|\lesssim K^{3}(|A||B|)^{1/2}\lesssim
K^{4}(|A^{\prime}||B^{\prime}|)^{1/2}.$

Schoen [53] proved stronger results for the symmetric case of
$E(A)\geq|A|^{3}/K$.

###### Proof.

For short, let $E=E(A,B)$ and $L=\log_{2}|B|$. Since

$E=E(A,B)=\sum_{x}r_{A+B}^{2}(x),$

by the popularity principle ((2) in Lemma 18 with $\lambda=1/2$, $S=A\times
B$, $f(x)=w(x)=r_{A+B}(x)$, $M=|B|$, $W=|A||B|$, $\mu=E$), there exists a
number $N$ satisfying

$\frac{E}{2|A||B|}\leq N\leq|B|$ (19)

such that the subset $G\subseteq A\times B$ defined by

$G=\\{(a,b)\in A\times B\colon N\leq r_{A+B}(a+b)<2N\\}$ (20)

satisfies

$\sum_{(a,b)\in G}r_{A+B}^{2}(a+b)=\sum_{x\in A\stackrel{{\scriptstyle
G}}{{+}}B}r_{A+B}^{2}(x)\geq\frac{E}{2L}.$ (21)

Above, we denoted by $x\in A\stackrel{{\scriptstyle G}}{{+}}B$ the statement
$x=a+b$ with $(a,b)\in G$. By (20) and (21) we have

$\frac{E}{4L}\leq N|G|$ (22)

and

$N|A\stackrel{{\scriptstyle G}}{{+}}B|\leq|G|.$ (23)

Now we apply Lemma 20 with $E=G$, and $K_{0}=|A||B|/|G|$ to find subsets
$A^{\prime}\subseteq A,B^{\prime}\subseteq B$ such that

$|A^{\prime}|\geq\frac{|A|}{4\sqrt{2}K_{0}}\qquad\mbox{and}\qquad|B^{\prime}|\geq\frac{|B|}{4K_{0}},$

and each pair $a\in A^{\prime}$ and $b\in B^{\prime}$ is connected by at least
$|A||B|/(2^{12}K_{0}^{5})$ paths of length 3.

If $(a,b^{\prime},a^{\prime},b)$ is such a path, then we have

$a+b=(a+b^{\prime})-(a^{\prime}+b^{\prime})+(a^{\prime}+b)=x-x^{\prime}+x^{\prime\prime}$

with $x,x^{\prime},x^{\prime\prime}$ in $A\stackrel{{\scriptstyle G}}{{+}}B$.
Double counting the number of solutions to the above equation yields

$\frac{|A||B|}{2^{12}K_{0}^{5}}|A^{\prime}+B^{\prime}|\leq|A\stackrel{{\scriptstyle
G}}{{+}}B|^{3}.$

By (23) we have $|A\stackrel{{\scriptstyle G}}{{+}}B|\leq|G|/N$. Since
$K_{0}=|A||B|/|G|$, we get

$|A^{\prime}+B^{\prime}|\leq\frac{2^{12}K_{0}^{5}}{|A||B|}|A\stackrel{{\scriptstyle
G}}{{+}}B|^{3}\leq\frac{2^{12}|A|^{4}|B|^{4}}{|G|^{2}N^{3}}.$

By (22), $1/(|G|^{2}N^{2})\leq(4L/E)^{2}$ and by (19), $1/N\leq 2|A||B|/E$, so

$|A^{\prime}+B^{\prime}|\leq
2^{12}|A|^{4}|B|^{4}\frac{2^{4}L^{2}}{E^{2}}\cdot\frac{2|A||B|}{E}=\frac{2^{17}|A|^{5}|B|^{5}L^{2}}{E^{3}}=2^{17}K^{3}L^{2}(|A||B|)^{1/2}.$

This proves the last claim.

Finally, equations (22) and (19) imply that

$|G|\geq\frac{E}{4LN}\geq\frac{E}{4L|B|}=\frac{|A|^{3/2}|B|^{3/2}}{4LK|B|}\geq\frac{|A||B|}{4LK},$

which yields $K_{0}=|A||B|/|G|\leq 4LK$. Hence

$|A^{\prime}|\geq\frac{|A|}{4\sqrt{2}K_{0}}\geq\frac{|A|}{16\sqrt{2}LK}\qquad\mbox{and}\qquad|B^{\prime}|\geq\frac{|B|}{4K_{0}}\geq\frac{|B|}{2^{4}LK}.$

∎

###  A.3 Proof of Proposition 4

We now prove Proposition 4, which we restate here. The argument is essentially
due to Bourgain [4, Proof of Theorem C]. Quantitative aspects were worked out
by Bourgain and Glibichuk [6, Proof of Proposition 2]. We offer further
quantitative improvements by a more careful analysis.

######  Proposition 4.

Let $A,X\subseteq\mathbb{F}_{q}^{*}$. If there is a positive real number $K>0$
such that

$\sum_{\xi\in X}E(A,\xi A)\geq\frac{|A|^{3}|X|}{K},$

then there exist elements $\bar{a}\in A$ and $x_{0}\in X$ and subsets
$A_{1}\subseteq A-\bar{a}$ and $X^{\prime}\subseteq x_{0}^{-1}X$ such that:

  1. (i)

$\displaystyle|A_{1}|\gtrsim K^{-85}|A|$ and $|X^{\prime}|\gtrsim K^{-5}|X|$.

  2. (ii)

$|A_{1}+X^{\prime}A_{1}|\lesssim K^{226}|A_{1}|$.

  3. (iii)

$\displaystyle|A_{1}\pm A_{1}|\lesssim K^{92}|A_{1}|$.

  4. (iv)

$\displaystyle|A_{1}\pm x^{\prime}A_{1}|\lesssim K^{126}|A_{1}|$ for all
$x^{\prime}\in X^{\prime}$.

Moreover, if $E(A,\xi A)\geq|A|^{3}/K$ for all $\xi\in X$, then
$|X^{\prime}|\gtrsim K^{-4}|X|$.

As a comparison we state what can be read off of the proof of [6, Proposition
2]: $|A_{1}|\gg K^{-441}|A|$, $|X^{\prime}|\gg K^{-8}|X|$, and
$|A_{1}+A_{1}X^{\prime}|\ll K^{1490}|A_{1}|$.

The proof of Proposition 4 follows from two lemmata.

######  Lemma 22.

Let $A$ and $B$ be subsets of $\mathbb{F}_{q}^{*}$ and let $K$ be a positive
constant. Suppose that

$\sum_{b\in B}E(A,bA)\geq\frac{|A|^{3}|B|}{K}.$

There exist subsets $A^{\prime}\subseteq A$ and $B^{\prime}\subseteq
b_{0}^{-1}B$ for some $b_{0}$ in $B$ such that

$|A^{\prime}\pm bA^{\prime}|\lesssim K^{42}|A^{\prime}|\quad\forall b\in
B^{\prime},$ $|A^{\prime}\pm A^{\prime}|\lesssim K^{8}|A^{\prime}|,$
$|A^{\prime}|\gtrsim\frac{|A|}{K}\qquad\mbox{and}\qquad|B^{\prime}|\gtrsim\frac{|B|}{K^{5}}.$

Moreover, if $E(A,bA)\geq|A|^{3}/K$ for all $b\in B$, then we have the same
conclusion with $|B^{\prime}|\gtrsim|B|/K^{4}$.

######  Lemma 23.

Let $A$ and $B$ be subsets of $\mathbb{F}_{q}^{*}$ and let $K,K_{0}$ be a
positive constants. Suppose that $|A\pm bA|\leq K|A|$ for all $b$ in $B$, and
that $|A\pm A|\leq K_{0}|A|$. There exists an element $\bar{a}$ in $A$ and a
subset $A_{1}\subseteq A-\bar{a}$ such that

$|A_{1}|\gtrsim\frac{|A|}{K^{2}}\qquad\mbox{and}\qquad|A\pm BA_{1}|\lesssim
K^{5}K_{0}^{2}|A_{1}|.$

###### Proof of Proposition 4.

$\sum_{\xi\in X}E(A,\xi A)\geq\frac{|A|^{3}|X|}{K}.$

By Lemma 22 there exist subsets $A^{\prime}\subseteq A$ and
$X^{\prime}\subseteq x_{0}^{-1}X$ such that

$|A^{\prime}\pm\xi A^{\prime}|\lesssim K^{42}|A^{\prime}|\quad\forall\xi\in
X^{\prime},$ $|A^{\prime}\pm A^{\prime}|\lesssim K^{8}|A^{\prime}|,$
$|A^{\prime}|\gtrsim K^{-1}|A|\qquad\mbox{and}\qquad|X^{\prime}|\gtrsim
K^{-5}|X|.$

The second part of (i) has been established.

We now apply Lemma 23 to $A=A^{\prime}$, $B=X^{\prime}$, $K\lesssim K^{42}$
and $K_{0}\lesssim K^{8}$. There is an element $\bar{a}$ in $A^{\prime}$ and a
subset $A_{1}\subseteq A^{\prime}-\bar{a}$ such that

$|A_{1}|\gg K^{-2\cdot 42}|A^{\prime}|=K^{-84}|A^{\prime}|\gtrsim K^{-85}|A|$

and

$|A_{1}\pm X^{\prime}A_{1}|\leq|A^{\prime}\pm X^{\prime}A_{1}|\ll K^{5\cdot
42}K^{2\cdot 8}|A_{1}|\lesssim K^{226}|A_{1}|.$

This proves (ii) and the first part of (i).

For (iii) note

$|A_{1}\pm A_{1}|\leq|A^{\prime}\pm A^{\prime}|\lesssim
K^{8}|A^{\prime}|\lesssim K^{92}|A_{1}|.$

Similarly, for (iv) note

$|A_{1}\pm x^{\prime}A_{1}|\leq|A^{\prime}\pm x^{\prime}A^{\prime}|\lesssim
K^{42}|A^{\prime}|\lesssim K^{126}|A_{1}|.$

The proof of the special case where $E(A,\xi A)\geq|A|^{3}/K$ for all $\xi\in
X$ is similar, the only difference is in the relative density of $X^{\prime}$.
∎

###  A.4 Proof of Lemma 22

###### Proof of Lemma 22.

We are given

$\sum_{b\in B}E(A,bA)\geq\frac{|A|^{3}|B|}{K}.$

By the popularity principle ((17) in Lemma 18 with $\lambda=1/2$, $S=B$,
$f(b)=E(A,bA)$, $\mu=|A|^{3}|B|/K$) there is a subset $B_{1}\subseteq B$ such
that

$E(A,bA)\geq\frac{|A|^{3}}{2K}\qquad\forall b\in
B_{1}\qquad\mbox{and}\qquad|B_{1}|\geq\frac{|B|}{2K}.$

For each $b$ in $B_{1}$, we apply Proposition 21 with $A=A,B=bA$ and $K=2K$ to
find $A^{(b)}_{1},A^{(b)}_{2}\subseteq A$ such that

$|A^{(b)}_{1}+bA^{(b)}_{2}|\lesssim
K^{3}|A|\qquad\mbox{and}\qquad|A^{(b)}_{1}|,|A^{(b)}_{2}|\gtrsim\frac{|A|}{K}.$
(24)

Now we find a large common subset of the $A^{(b)}_{i}$ by applying Lemma 19 to
the sets $A^{(b)}_{1}\times A^{(b)}_{2}\subseteq A\times A$ (we take
$T=A\times A$, $S=B_{1}$, and $T_{s}=A_{1}^{(s)}\times A_{2}^{(s)}$). Since

$\sum_{b\in B_{1}}|A^{(b)}_{1}\times A^{(b)}_{2}|\gtrsim
K^{-2}|A|^{2}|B_{1}|,$

there is a subset $P\subseteq B_{1}\times B_{1}$ such that

$|(A^{(b)}_{1}\cap A^{(b^{\prime})}_{1})\times(A^{(b)}_{2}\cap
A^{(b^{\prime})}_{2})|\gtrsim K^{-4}|A|^{2}$

for all pairs $(b,b^{\prime})$ in $P$, and $|P|\gtrsim K^{-4}|B_{1}|^{2}$.

Pigeonholing over $b^{\prime}$ yields an element $b^{*}$ in $B_{1}$ such that

$|(A^{(b)}_{1}\cap A^{(b^{*})}_{1})\times(A^{(b)}_{2}\cap
A^{(b^{*})}_{2})|\gtrsim K^{-4}|A|^{2}$ (25)

for all $b$ in $B_{2}\subseteq B_{1}$ and

$|B_{2}|\gtrsim K^{-4}|B_{1}|\gtrsim K^{-5}|B|.$ (26)

We will write $A_{i}^{*}$ for $A^{(b^{*})}_{i}$.

Next we apply (24) and the sumset cardinality inequalities in Lemma 2 to show
that

$|A_{2}^{*}\pm A_{2}^{*}|\lesssim K^{7}|A|$ (27)

and for all $b\in B_{2}$

$|b^{*}A^{*}_{2}\pm bA^{*}_{2}|\lesssim K^{41}|A|\quad\forall b\in B_{2}.$
(28)

First we prove a stronger version of (27): Let $b\in B_{1}$

$|A_{2}^{(b)}+A_{2}^{(b)}|=|bA_{2}^{(b)}+bA_{2}^{(b)}|\leq\frac{|A_{1}^{(b)}+bA_{2}^{(b)}|^{2}}{|A_{1}^{(b)}|}\overset{\eqref{eq:BG24}}{\lesssim}K^{6}\frac{|A|^{2}}{|A_{1}^{(b)}|}\overset{\eqref{eq:BG24}}{\lesssim}K^{7}|A|.$
(29)

This proves (27) by taking $b=b^{*}$, which is an element of $B_{1}$.
Similarly, for all $b\in B_{1}$,

$|A_{1}^{(b)}\pm
A_{1}^{(b)}|\leq\frac{|A_{1}^{(b)}+bA_{2}^{(b)}|^{2}}{|A_{2}^{(b)}|}\lesssim
K^{7}|A|.$ (30)

Now we prove (28).

$\displaystyle|b^{*}A^{*}_{2}\pm bA^{*}_{2}|$
$\displaystyle\leq\frac{|A^{*}_{1}+b^{*}A_{2}^{*}||A_{1}^{*}+bA_{2}^{*}|}{|A_{1}^{*}|}$
$\displaystyle\overset{\eqref{eq:BG24}}{\lesssim}K^{4}|A_{1}^{*}+bA_{2}^{*}|$
$\displaystyle\lesssim
K^{4}\frac{|A_{1}^{*}+A_{1}^{(b)}||A_{1}^{(b)}+bA_{2}^{*}|}{|A_{1}^{(b)}|}$
$\displaystyle\lesssim
K^{4}\frac{|A_{1}^{*}+A_{1}^{(b)}||A_{1}^{(b)}+bA_{2}^{(b)}||A_{2}^{(b)}+A_{2}^{*}|}{|A_{1}^{(b)}||A_{2}^{(b)}|}$
$\displaystyle\overset{\eqref{eq:BG24}}{\lesssim}K^{9}\frac{|A_{1}^{*}+A_{1}^{(b)}||A_{2}^{*}+A_{2}^{(b)}|}{|A|}.$

x We use (24), (25), (29) and (30) to estimate the remaining sumsets:

$\displaystyle|A_{1}^{*}+A_{1}^{(b)}||A_{2}^{*}+A_{2}^{(b)}|$
$\displaystyle\leq\frac{|A_{1}^{*}+A_{1}^{*}||A_{1}^{(b)}+A_{1}^{(b)}||A_{2}^{*}+A_{2}^{*}||A_{2}^{(b)}+A_{2}^{(b)}|}{|A_{1}^{*}\cap
A_{1}^{(b)}||A_{2}^{*}\cap A_{2}^{(b)}|}$
$\displaystyle\lesssim\frac{(K^{7}|A|)^{4}}{K^{-4}|A|^{2}}\lesssim
K^{32}|A|^{2}.$

Combined with the previous chain of inequalities, this proves (28).

Setting $A^{\prime}=A_{2}^{*}$ and $B^{\prime}=(b^{*})^{-1}B_{2}$, we have by
(24) and (28)

$|A^{\prime}\pm b(b^{*})^{-1}A^{\prime}|=|b^{*}A_{2}^{*}\pm
bA_{2}^{*}|\lesssim K^{41}|A|\lesssim K^{42}|A^{\prime}|$

for all $b(b^{*})^{-1}$ in $B^{\prime}$; and by (27)

$|A^{\prime}\pm A^{\prime}|\lesssim K^{7}|A|\lesssim K^{8}|A^{\prime}|.$

Setting $b_{0}=b^{*}$ and invoking (26) completes the proof of the most
general statement.

If $E(A,bA)\geq|A|^{3}/K$ for all $b\in B$, then we may take $B_{1}=B$ and so
the lower bound on $|B_{2}|$ in (26) becomes $|B|/K^{4}$. ∎

###  A.5 Proof of Lemma 23

###### Proof of Lemma 23.

We begin with a simple observation we use further down: we may without loss of
generality assume that $|B|\geq 32K_{0}K^{3}$ because otherwise the conclusion
follows immediately with $A_{1}=A$:

$|A\pm BA|\leq\sum_{b\in B}|A\pm bA|\leq K|B||A|\ll K^{4}K_{0}|A|.$

For a number $\tau\geq|B|/(2K^{2})$ we say that a non-zero $\xi\neq 0$ is
_$\tau$ -involved_ if

$\min_{\begin{subarray}{c}B^{\prime}\subseteq B,|B^{\prime}|\geq\tau\\\
Y\subseteq A,|Y|\geq|A|/2\end{subarray}}|Y+B^{\prime}\xi|\leq 4K_{0}K|A|.$
(31)

If $|Y+B^{\prime}\xi|\leq 4K_{0}K|A|$ for some $B^{\prime}\subseteq B$ and
$Y\subseteq A$ satisfying $|B^{\prime}|\geq\tau,|Y|\geq|A|/2$, we say that
$\xi$ is _witnessed_ by $B^{\prime}$.

Let $\Omega$ denote the set of $\tau$-involved elements. We obtain an upper
bound on $\Omega$. First observe that for any subsets $A^{\prime}\subseteq
A,B^{\prime}\subseteq B$ we have

$E(A,\xi B)-|A||B|\geq E(A^{\prime},\xi B^{\prime})-|A^{\prime}||B^{\prime}|,$

because, say, $E(A,\xi B)-|A||B|$ is the number of non-zero ordered solutions
to $(a-a^{\prime})=\xi(b-b^{\prime})$ with $a,a^{\prime}\in A$ and
$b,b^{\prime}\in B$. For any involved $\xi$, we have

$\displaystyle E(A,\xi B)-|A||B|$ $\displaystyle\geq E(Y,\xi
B^{\prime})-|Y||B^{\prime}|$
$\displaystyle\geq\frac{|Y|^{2}|B^{\prime}|^{2}}{|Y+B^{\prime}\xi|}-|Y||B^{\prime}|$
$\displaystyle\geq\frac{|A||B^{\prime}|}{2}\left(\frac{|B^{\prime}|}{8K_{0}K}-1\right).$

We may assume $|B|\geq 32K_{0}K^{3}$, as detailed at the beginning of the
proof, and so we have $|B^{\prime}|\geq|B|/(2K^{2})\geq 16K_{0}K$. Thus
$|B^{\prime}|/(8K_{0}K)-1\geq|B^{\prime}|/(16K_{0}K)$ and we get for all
involved $\xi$

$E(A,\xi
B)-|A||B|\geq\frac{|A||B^{\prime}|^{2}}{32K_{0}K}\geq\frac{|A|\tau^{2}}{32K_{0}K}.$

Hence we get the following upper bound on $\Omega$ via Lemma 3

$|\Omega|\leq\frac{32KK_{0}}{|A|\tau^{2}}\sum_{\xi}(E(A,\xi
B)-|A||B|)\leq\frac{32KK_{0}}{|A|\tau^{2}}|A|^{2}|B|^{2}\leq\frac{64K^{3}K_{0}|A||B|}{\tau}.$
(32)

We use this upper bound on $|\Omega|$ further down. Our next task is to find
elements in $\Omega$. To do so, we must find particular $\xi$, $B^{\prime}$,
and $Y$ for which (31) holds. Our aim is to identify two $\xi$ for each $b\in
B$. We begin with an averaging argument. Since $|A+bA|\leq K|A|$ for all $b$
in $B$, we have

$\sum_{b\in B}E(A,bA)\geq\frac{|A|^{3}|B|}{K}.$

By pigeonholing, there exist $\bar{a},\bar{\bar{a}}\in A$ such that

$|\\{(a_{1},a_{2},b)\in A^{2}\times B\colon
a_{2}-\bar{\bar{a}}=b(a_{1}-\bar{a})\\}|\geq\frac{|A||B|}{K}.$

For each $a$ in $A$, let

$B_{a}=\\{b\in B\colon b(a-\bar{a})\in A-\bar{\bar{a}}\\}.$

In this notation we have

$\sum_{a\in A}|B_{a}|\geq\frac{|A||B|}{K},$

and so, by the first part of Lemma 19,

$\sum_{(a,a^{\prime})\in A\times A}|B_{a}\cap
B_{a^{\prime}}|\geq\frac{|A|^{2}|B|}{K^{2}}.$

Thus by the popularity principle ((2) in Lemma 18 with $S=A\times A$,
$f(a,a^{\prime})=|B_{a}\cap B_{a^{\prime}}|$,
$w(a,a^{\prime})=1,W=|A|^{2},M=|B|$, $\mu=|A|^{2}|B|/K^{2}$, $\lambda=1/2$)
there exists a subset $P_{*}\subseteq A\times A$ and a number
$|B|/(2K^{2})\leq\tau\leq|B|$ such that

$\tau\leq|B_{a}\cap B_{a^{\prime}}|<2\tau$ (33)

for all $(a,a^{\prime})\in P_{*}$ and

$\frac{|A|^{2}|B|}{2K^{2}\log_{2}|B|}\leq\sum_{(a,a^{\prime})\in
P_{*}}|B_{a}\cap B_{a^{\prime}}|\leq 2\tau|P_{*}|.$ (34)

Now fix $b\in B$. For each pair $(a,a^{\prime})$ in $P_{*}$, we define

$\xi_{\pm}=(a^{\prime}-\bar{a})\pm b(a-\bar{a}).$

We show that both elements $\xi_{\pm}$ belong to $\Omega$ because they are
witnessed by the set $B^{\prime}=B_{a}\cap B_{a^{\prime}}$, which, by (33) has
cardinality at least $\tau\geq|B|/(2K^{2})$. To see why $\xi_{\pm}$ are
witnessed by $B^{\prime}$, recall that by its definition, $B_{a}$ is the set
of $b$ such that $b(a-\bar{a})\in A-\bar{\bar{a}}$. Therefore for any set $Y$
we have

$|Y+B^{\prime}\xi_{\pm}|\leq|Y+B_{a^{\prime}}(a^{\prime}-\bar{a})\pm
bB_{a}(a-\bar{a})|\leq|Y+A\pm bA|.$

By Plünnecke’s inequality for different summands with a large subset in Lemma
2, there exists a subset $Y\subseteq A$ such that $|Y|\geq|A|/2$ and

$\displaystyle|Y+A\pm bA|\leq 4\,\frac{|Y+A|}{|A|}\,\frac{|Y\pm
bA|}{|A|}\;|A|\leq 4K_{0}K|A|,$

which confirms (31).

This proves that $\xi_{\pm}\in\Omega$. This is true for all $b\in B$ and
therefore

$(a^{\prime}-\bar{a})\pm
B(a-\bar{a})\subseteq\Omega\quad\forall(a,a^{\prime})\in P.$ (35)

The final step of the proof is to get an upper bound on $|A+A_{1}B|$ for some
suitable set $A_{1}$ (of relative density $\gtrsim 1/K^{2}$ in $A$) by double-
counting the number of representations of elements of $A+A_{1}B$ as a sum of
elements in $A-A_{1}$ and $\Omega$.

Let $P(a)=\\{a^{\prime}\in A\colon(a,a^{\prime})\in P_{*}\\}$, so that by (34)

$|P_{*}|=\sum_{a\in A}|P(a)|\geq\frac{|A|^{2}|B|}{4\tau K^{2}\log_{2}|B|}.$

By the popularity principle ((2) in Lemma 18 with
$\lambda=1/2,S=A,f(a)=|P(a)|$, $w(a)=1,W=|A|,M=|A|$, and $\mu=|P_{*}|$) there
is a subset $A_{*}\subseteq A$ and an integer $|A|/4K^{2}\leq N\leq|A|$ such
that $N\leq|P(a)|<2N$ for all $a$ in $A_{*}$ and

$\frac{|A|^{2}|B|}{\tau K^{2}}\lesssim|P_{*}|\lesssim N|A_{*}|.$ (36)

Note that

$|A_{*}|\gtrsim\frac{|A|}{K^{2}}$ (37)

since $N\leq|A|$ and $\tau\leq|B|$.

Set $A_{1}=A_{*}-\bar{a}$ and $r(x):=r_{(A-A+\bar{a})+\Omega}(x)$. We show
that for all $x$ in $A+A_{1}B$

$r(x)\geq N\quad\forall x\in A+A_{1}B.$ (38)

To see why consider $x=\tilde{a}\pm(a-\bar{a})b\in A\pm A_{1}B$ (so $a\in
A_{*}$). For all $a^{\prime}\in P(a)$, inclusion (35) gives

$x=\tilde{a}\pm(a-\bar{a})b=[\tilde{a}-(a^{\prime}-\bar{a})]+[(a^{\prime}-\bar{a})\pm(a-\bar{a})b]\in(A-A+\bar{a})+\Omega.$

Distinct $a^{\prime}\in P(a)$ give distinct representations and so we indeed
get $r(x)\geq|P(a)|\geq N$.

Now we double count:

$\displaystyle N|A\pm A_{1}B|$ $\displaystyle\overset{\eqref{eq:bou-
gli17}}{\leq}\sum_{x\in(A-A+\bar{a})+\Omega}r(x)$
$\displaystyle\leq|A-A||\Omega|$ $\displaystyle\overset{\eqref{eq:bou-
gli12}}{\leq}(K_{0}|A|)(2^{6}K^{3}K_{0}|A||B|\tau^{-1}).$

We are ready to conclude the proof. By (37), $|A_{1}|=|A_{*}|\gtrsim|A|/K^{2}$
and by the above inequality and (36)

$|A\pm A_{1}B|\ll\frac{K^{3}K_{0}^{2}|A|^{2}|B|}{\tau
N}\lesssim\frac{K^{3}K_{0}^{2}|A|^{2}|B||A_{*}|}{\tau|P_{*}|}\lesssim
K^{5}K_{0}^{2}|A_{1}|.$

∎

## Acknowledgments

The authors are grateful to the anonymous reviewers, as well as Brandon
Hanson, Alex Iosevich, Olly Roche-Newton, Misha Rudnev, and Igor Shparlinski.

## References

  * [1] N. Alon and F. K. R. Chung.  Explicit construction of linear sized tolerant networks.  Discrete Math., 72(1):15–19, 1988.
  * [2] A. Balog and E. Szemerédi.  A statistical theorem of set addition.  Combinatorica, 14:585–613, 1994.
  * [3] M. Bennett, D. Hart, A. Iosevich, J. Pakianathan, and M. Rudnev.  Group actions and geometric combinatorics in $\mathbb{F}_{q}^{d}$.  Forum Math., 29(1):91–110, 2017.
  * [4] J. Bourgain.  Multilinear exponential sums in prime fields under optimal entropy condition on the sources.  Geom. Funct. Anal., 18:1477–1502, 2009.
  * [5] J. Bourgain and M. Z. Garaev.  On a variant of sum-product estimates and explicit exponential sum bounds in prime fields.  Math. Proc. Cambridge Philos. Soc., 146(1):1–21, 2009.
  * [6] J. Bourgain and A. Glibichuk.  Exponential sum estimates over a subgroup in an arbitrary finite field.  J. Anal. Math., 115(1):51–70, 2011.
  * [7] J. Bourgain, A. A. Glibichuk, and S. V. Konyagin.  Estimates for the number of sums and products and for exponential sums in fields of prime order.  J. London Math. Soc. (2), 73:380–398, 2006.
  * [8] J. Bourgain, N. H. Katz, and T. Tao.  A sum-product estimate in finite fields, and applications.  Geom. Funct. Anal., 14(1):27–57, 2004.
  * [9] B. Bukh and J. Tsimerman.  Sum-product estimates for rational functions.  Proc. Lond. Math. Soc. (3), 104(1):1–26, 2012.
  * [10] J. Chapman, M. B. Erdoğan, D. Hart, A. Iosevich, and D. Koh.  Pinned distance sets, $k$-simplices, Wolff’s exponent in finite fields and sum-product estimates.  Math. Z., 271(1-2):63–93, 2012.
  * [11] K. Conrad.  On Weil’s proof of the bound for Kloosterman sums.  J. Number Theory, 97(2):439–446, 2002.
  * [12] G. Elekes.  A combinatorial problem on polynomials.  Discrete Comput. Geom., 19(3):383–389, 1998.
  * [13] G. Elekes and L. Rónyai.  A combinatorial problem on polynomials and rational functions.  J. Combin. Theory Ser. A, 89(1):1–20, 2000.
  * [14] M. Z. Garaev.  The sum-product estimate for large subsets of prime fields.  Proc. Amer. Math. Soc., 136(8):2735–2739, 2008.
  * [15] N. Gill and H. A. Helfgott.  Growth in solvable subgroups of ${\rm GL}_{r}(\mathbb{Z}/p\mathbb{Z})$.  Math. Ann., 360(1-2):157–208, 2014.
  * [16] A. A. Glibichuk and S. V. Konyagin.  Additive properties of product sets in fields of prime order.  In A. Granville, M. B. Nathanson, and J. Solymosi, editors, Additive Combinatorics, CRM Proceedings & Lecture Notes 43, pages 279–286, Providence, R.I., 2007. Amer. Math. Soc.
  * [17] W. T. Gowers.  A new proof of Szemerédi’s theorem for arithmetic progressions of length four.  Geom. Funct. Anal., 8(3):529–551, 1998.
  * [18] W. T. Gowers.  A new proof of Szemerédi’s theorem.  Geom. Funct. Anal., 11(3):465–588, 2001.
  * [19] L. Guth and N. H. Katz.  On the Erdős distinct distances problem in the plane.  Ann. of Math. (2), 181(1):155–190, 2015.
  * [20] K. Gyarmati and A. Sárközy.  Equations in finite fields with restricted solution sets. II (algebraic equations).  Acta Math. Hungar., 119(3):259–280, 2008.
  * [21] W. H. Haemers.  Eigenvalue techniques in design and graph theory.  PhD thesis, Technische Hogeschool Eindhoven, 1979.
  * [22] D. Hart and A. Iosevich.  Sums and products in finite fields: an integral geometric viewpoint.  In Radon Transforms, Geometry, and Wavelets, AMS Contemporary Mathematics 464, pages 129–136. AMS RI, 2008.
  * [23] D. Hart, A. Iosevich, and J. Solymosi.  Sum-product estimates in finite fields via Kloosterman sums.  Int. Math. Res. Not. IMRN, 2007:Art. ID rnm007, 14, 2007.
  * [24] D. Hart, L. Li, and C.-Y. Shen.  Fourier analysis and expanding phenomena in finite fields.  Proc. Amer. Math. Soc., 141(2), 2013.
  * [25] D. R. Heath-Brown and S. V. Konyagin.  New bounds for Gauss sums derived from $k$th powers, and for Heilbronn’s exponential sum.  Q. J. Math., 52(2):221–235, 2000.
  * [26] N. Hegyvári and F. Hennecart.  Conditional expanding bounds for two-variable functions over prime fields.  European J. Combin., 34(8):1365–1382, 2013.
  * [27] H. A. Helfgott.  Growth and generation in ${\rm SL}_{2}(\mathbb{Z}/p\mathbb{Z})$.  Ann. of Math. (2), 167(2):601–623, 2008.
  * [28] H. A. Helfgott.  Growth in ${\rm SL}_{3}(\mathbb{Z}/p\mathbb{Z})$.  J. Eur. Math. Soc. (JEMS), 13(3):761–851, 2011.
  * [29] H. A. Helfgott.  Growth in groups: ideas and perspectives.  Bull. Amer. Math. Soc. (N.S.), 52(3):357–413, 2015.
  * [30] A. Iosevich, O. Roche-Newton, and M. Rudnev.  On discrete values of bilinear forms.  Mat. Sb., 209(10):71–88, 2018.
  * [31] H. Iwaniec and E. Kowalski.  Analytic Number Theory.  Amer. Math. Soc., Providence, R.I., 2004.
  * [32] N. H. Katz and C.-Y. Shen.  A slight improvement to Garaev’s sum product estimate.  Proc. Amer. Math. Soc., 136(7):2499–2504, 2008.
  * [33] S. Konyagin.  A sum-product estimate in fields of prime order.  http://arXiv:math/0304217arXiv:math/0304217, 2003.
  * [34] S. Lang.  Algebra, volume 211 of Graduate Texts in Mathematics.  Springer-Verlag, New York, third edition, 2002.
  * [35] B. Murphy and G. Petridis.  A point-line incidence identity in finite fields, and applications.  Mosc. J. Comb. Number Theory, 6(1):63–94, 2016.
  * [36] B. Murphy and G. Petridis.  A second wave of expanders over finite fields.  In Combinatorial and additive number theory. II, 215–238, Springer Proc. Math. Stat., 220, Springer, Cham, 2017.
  * [37] B. Murphy, G. Petridis, O. Roche-Newton, M. Rudnev, and I. D. Shkredov.  New results on sum-product type growth over fields.  http://arxiv.org/abs/1702.01003arXiv:1702.01003, 2017.
  * [38] B. Murphy, O. Roche-Newton, and I. D. Shkredov.  Variations on the sum-product problem II.  SIAM J. Discrete Math., 31(3):1878–1894, 2017.
  * [39] G. Petridis.  New proofs of Plünnecke-type estimates for product sets in groups.  Combinatorica, 32(6):721–733, 2012.
  * [40] G. Petridis.  Products of differences in prime order finite fields.  http://arxiv.org/abs/1602.02142arXiv:1602.02142, 2016.
  * [41] G. Petridis and I. E. Shparlinski.  Bounds on trilinear and quadrilinear exponential sums.  Accepted in J. Anal. Math. http://arxiv.org/abs/1604.08469arXiv:1604.08469, 2016.
  * [42] T. Pham, L. A. Vinh, and F. de Zeeuw.  Three-variable expanding polynomials and higher-dimensional distinct distances.  Combinatorica.  To appear.
  * [43] H. Plünnecke.  Eine zahlentheoretische anwendung der graphtheorie.  J. Reine Angew. Math., 243:171–183, 1970.
  * [44] O. E. Raz, M. Sharir, and J. Solymosi.  Polynomials vanishing on grids: the Elekes-Rónyai problem revisited.  Amer. J. Math., 138(4):1029–1065, 2016.
  * [45] O. Roche-Newton and M. Rudnev.  On the minkowski distances and products of sum sets.  Israel J. Math., 209:507–526, 2015.
  * [46] M. Rudnev.  On the number of incidences between planes and points in three dimensions.  Combinatorica, 38(1):219–254, 2018.
  * [47] M. Rudnev, I. D. Shkredov, and S. Stevens.  On the energy variant of the sum-product conjecture.  Preprint. http://arxiv.org/abs/1607.05053arXiv:1607.05053.
  * [48] I. Z. Ruzsa.  On the cardinality of ${A}+{A}$ and ${A}-{A}$.  In A. Hajnal and V. T. Sós, editors, Combinatorics (Keszthely 1976) Coll. Math. Soc. J. Bolyai, vol 18, pages 933–938. North-Holland – Bolyai Társulat, 1978.
  * [49] I. Z. Ruzsa.  An application of graph theory to additive number theory.  Scientia, Ser. A, 3:97–109, 1989.
  * [50] I. Z. Ruzsa.  Arithmetical progressions and the number of sums.  Period. Math. Hungar., 25(1):105–111, 1992.
  * [51] I. Z. Ruzsa.  Sumsets and structure.  In Combinatorial Number Theory and Additive Group Theory, Adv. Courses Math. CRM Barcelona, pages 87–210. Birkhäuser Verlag, Basel, 2009\.
  * [52] A. Sárközy.  On sums and products of residues modulo $p$.  Acta Arith., 118(4):40–409, 2005.
  * [53] T. Schoen.  New bounds in Balog-Szemerédi-Gowers theorem.  Combinatorica, 35(6):695–701, 2015.
  * [54] I. D. Shkredov.  On monochromatic solutions of some nonlinear equations in $\mathbb{Z}/p\mathbb{Z}$.  Mathematical Notes, 88(3):603–611, 2010.
  * [55] I. D. Shkredov.  On a question of A. Balog.  Pacific J. Math., 280(1):227–240, 2016.
  * [56] I. E. Shparlinski.  On the solvability of bilinear equations in finite fields.  Glasg. Math. J., 50(3):523–529, 2008.
  * [57] J. Solymosi.  Incidences and the spectra of graphs.  In M. Grötschel, G.O.H. Katona, and G. Sági, editors, Building Bridges: between mathematics and computer science, Bolyai Society Mathematical Studies Vol. 19, pages 499–513. Springer, Berlin Heidelberg, 2008.
  * [58] S. Stevens and F. de Zeeuw.  An improved point-line incidence bound over arbitrary fields.  Bull. Lond. Math. Soc., 49(5):842–858, 2017.
  * [59] B. Sudakov, E. Szemerédi, and V. H. Vu.  On a question of Erdős and Moser.  Duke Math. J., 129(1):129–155, 2005.
  * [60] T. Tao.  Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets.  Contrib. Discrete Math., 10(1):22–98, 2015.
  * [61] T. Tao.  Expansion in finite simple groups of Lie type, volume 164 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2015.
  * [62] T. Tao and V. H. Vu.  Additive combinatorics, volume 105 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 2010.
  * [63] L. A. Vinh.  The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields.  European J. Combin., 32(8):1177–1181, 2011.
  * [64] L. A. Vinh.  On four-variable expanders in finite fields.  SIAM J. Discrete Math., 27(4):2038–2048, 2013.
  * [65] V. H. Vu.  Sum-product estimates via directed expanders.  Math. Res. Lett., 15(2):375–378, 2008.
  * [66] F. de Zeeuw.  A short proof of Rudnev’s point-plane incidence bound.  http://arxiv.org/abs/1612.02719arXiv:1612.02719, 2016.

[bm] Brendan Murphy
School of Mathematics
University of Bristol
Bristol, United Kingdom
brendanmurphybristolacuk
http://www.bristol.ac.uk/maths/people/brendan-m-murphy/overview.html [gp]
Giorgis Petridis
Department of Mathematics
University of Georgia
Athens, GA 30602
USA
giorgiscantabnet
https://faculty.franklin.uga.edu/petridis/