# BOUNDS OF TRILINEAR AND QUADRILINEAR EXPONENTIAL SUMS

GIORGIS PETRIDIS AND IGOR E. SHPARLINSKI

**ABSTRACT.** We use an estimate of Aksoy Yazici, Murphy, Rudnev and Shkredov (2016) on the number of solutions of certain equations involving products and differences of sets in prime finite fields to give an explicit upper bound on trilinear exponential sums which improves the previous bound of Bourgain and Garaev (2009). We also obtain explicit bounds for quadrilinear exponential sums.

## 1. INTRODUCTION

1.1. **Background.** Let $p$ be a prime and let $\mathbb{F}_p$ be the finite field of $p$ elements. Now given three sets $\mathcal{X}, \mathcal{Y}, \mathcal{Z} \subseteq \mathbb{F}_p$, and three sequences of weights $\alpha = (\alpha_x)_{x \in \mathcal{X}}$, $\beta = (\beta_y)_{y \in \mathcal{Y}}$ and $\gamma = (\gamma_z)_{z \in \mathcal{Z}}$ supported on $\mathcal{X}, \mathcal{Y}$ and $\mathcal{Z}$, respectively, we consider exponential sums

$$ (1.1) \qquad S(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma) = \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} \sum_{z \in \mathcal{Z}} \alpha_x \beta_y \gamma_z \mathbf{e}_p(xyz), $$

where $\mathbf{e}_p(z) = \exp(2\pi i z/p)$. We recall that the bilinear analogues of these sums are classical and have been studied in several papers, in which case for any sets $\mathcal{X}, \mathcal{Y} \subseteq \mathbb{F}_p$ and any $\alpha = (\alpha_x)_{x \in \mathcal{X}}$, $\beta = (\beta_y)_{y \in \mathcal{Y}}$, with

$$ \sum_{x \in \mathcal{X}} |\alpha_x|^2 = A \quad \text{and} \quad \sum_{y \in \mathcal{Y}} |\beta_y|^2 = B, $$

we have

$$ (1.2) \qquad \left| \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} \alpha_x \beta_y \mathbf{e}_p(xy) \right| \le \sqrt{pAB}, $$

see, for example, [4, Equation 1.4] or [15, Lemma 4.1].

The trilinear sums (1.1) have been introduced and estimated by Bourgain and Garaev [4]. In particular, for and sets $\mathcal{X}, \mathcal{Y}, \mathcal{Z} \subseteq \mathbb{F}_p$

<footnote n="2010">2010 Mathematics Subject Classification. 11B30, 11L07, 11T23.</footnote>

<footnote>Key words and phrases. trilinear exponential sums, additive energy of differences.</footnote>
of cardinalities

$$ \#\mathcal{X} = X, \quad \#\mathcal{Y} = Y, \quad \#\mathcal{Z} = Z, $$

and weights with

$$ \max_{x \in \mathcal{X}} |\alpha_x| \le 1, \quad \max_{y \in \mathcal{Y}} |\beta_y| \le 1, \quad \max_{z \in \mathcal{Z}} |\gamma_z| \le 1, $$

by [4, Theorem 1.2] we have

$$ (1.3) \qquad |S(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma)| \le (XYZ)^{13/16} p^{5/18+o(1)}, $$

as $p \to \infty$. The bound (1.3) has been generalised and extended in various directions, see [2, 3, 6, 15, 32]. In particular, Bourgain [2] has obtained a bound on multilinear sums

$$ (1.4) \qquad \left| \sum_{x_1 \in \mathcal{X}_1} \dots \sum_{x_n \in \mathcal{X}_n} \mathbf{e}_p(x_1 \dots x_n) \right| \le X_1 \dots X_n p^{-\eta} $$

under an optimal condition

$$ \min_{i=1,\dots,n} X_i \ge p^{\delta} \quad \text{and} \quad \prod_{i=1}^{n} X_i \ge p^{1+\delta}, $$

of the sizes $X_i = \mathcal{X}_i$, $i = 1, \dots, n$, of the sets involved, where $\eta > 0$ depends only on the arbitrary parameter $\delta > 0$. The interest to multilinear exponential sums partially comes from applications to exponential sums over subgroups of small order over finite fields, which has been used in the celebrated work of Bourgain, Glibichuk and Konyagin [7]. We also note that several consecutive applications of the Cauchy inequality allow us to reduce general multilinear sums to sums without weights, see, for example, Lemma 2.10 below. Furthermore, the bound (1.4) has been extended to arbitrary finite fields by Bourgain and Glibichuk [6], see also [3, 32]. However, prior to the present work, the bound (1.3) has been the best known explicit bound on the sums (1.1).

We also note that Hegyvári [20, Theorem 3.1] has given estimates of some multilinear sums, without weights, over sets of special additive structure (for sets with small difference sets).

Here we use a different approach to estimating the sums (1.1) and a recent result of Aksoy Yazici, Murphy, Rudnev and Shkredov [1] to obtain a different bound, which, in particular, improves (1.3) when $p \to \infty$.

Furthermore, using a slightly different approach, based on another result of Aksoy Yazici, Murphy, Rudnev and Shkredov [1] (see also [33]) we consider sums with more general weights to which the above approach does not apply. We also consider their multivariate versions.
In particular, given $n$ sets $\mathcal{X}_i \subseteq \mathbb{F}_p$, and also $n$ sequences of weights $\omega_i = (\omega_i(\mathbf{x}))_{\mathbf{x} \in \mathbb{F}_p^n}$ such that $\omega_i(\mathbf{x})$ does not depend on the $i$th coordinate of the vector $\mathbf{x} = (x_1, \dots, x_n) \in \mathbb{F}_p^n$, $i = 1, \dots, n$, we consider multilinear exponential sums

$$ (1.5) \qquad T(\mathcal{X}_1, \dots, \mathcal{X}_n; \omega_1, \dots, \omega_n) \\ = \sum_{\mathbf{x} \in \mathcal{X}_1 \times \dots \times \mathcal{X}_n} \omega_1(\mathbf{x}) \dots \omega_n(\mathbf{x}) \mathbf{e}_p(x_1 \dots x_n). $$

As we have mentioned, if the strength of the bound is not of concern but only the range of non-triviality is important, then Bourgain [2] provides an optimal result (1.4) for sums with constant weights, which can be extended to sums (1.5) with several consecutive applications of the Cauchy inequality as in Lemma 2.10 below. However the saving in such a bound is rather small, while here we are interested in stronger and more explicit bounds.

Although we estimate the sums (1.5) only for $n = 3$ and $n = 4$ we develop some tools in Section 2.2 in full generality, which may be of use if the results of Section 2.1 get eventually extended to equations with more sets and variables.

Our method is based on a upper bound of Rudnev [38] on the number of incidences between a set of points and a set of planes in $\mathbb{F}_p^3$. Rudnev's paper, which undoubtedly will find many more applications, stems from the Guth and Katz [18] solution to the Erdős distinct distance problem for planar sets and the Klein-Plücker line geometry formalism [34, Chapter 2]. So Rudnev's work [38] indirectly depends on classical techniques such as the polynomial method (see [16] and [46, Chapter 9]) and properties of ruled surfaces (see [26]) and the Klein quadric (see [39]). A more detailed discussion can be found in the beginning of Section 2.1.

We also illustrate potential applications of our results on a example of a certain question from additive combinatorics complementing those of Sárközy [41] on nonlinear equations with variables from arbitrary sets and of Aksoy Yazici, Murphy, Rudnev and Shkredov [1] on sizes of polynomial images. In fact both are closely related and also both can be approached via the idea of Garaev [14] which links multilinear exponential sums, equation with variables from arbitrary sets and sums-product type results (see also [20] for some other applications of this idea). So it is not surprising that our results fit well into this approach, see Section 1.4. More precisely, our bounds of multilinear exponential sums, allow to derive results for multifold sums and
products, which have recently become a subject of quite active investigation. For example, to put our results of Section 1.4 in a proper context, we present one of the bounds of Roche-Newton, Rudnev and Shkredov [36]. Namely, by [36, Corollary 12] we have

$$ (\#(\mathcal{A} + \mathcal{A} + \mathcal{A}))^4 (\#(\mathcal{AA}))^9 \geq (\#\mathcal{A})^{16} $$

for any set $\mathcal{A} \subseteq \mathbb{F}_p$ with $\#\mathcal{A} = O(p^{18/35})$ (we refer to (1.8) for the definition sum and product sets); see also (1.9), (1.11) and (1.12) below.

Finally, we recall that the bound (1.2) has a full analogue for sums with a nontrivial multiplicative characters $\chi$ of $\mathbb{F}_p^*$ with two sets $\mathcal{X}, \mathcal{Y} \subseteq \mathbb{F}_p$. Chang [9] has given a better bound if one of these sets has a small sum set. More recently, Hanson [19], also using methods of additive combinatorics, has obtained a series of results which apply to trilinear character sums. Shkredov and Volostnov [43] have given further improvements of the results of [9, 19]. Unfortunately our approach does not seem to apply to multiplicative character sums.

## 1.2. Notation.
We always use the letter $p$ to denote a prime number and use the letter $q$ to denote a prime power.

Before we formulate our results, we recall that the notations $U = O(V)$, $U \ll V$ and $V \gg U$ are all equivalent to the assertion that the inequality $|U| \leq c|V|$ holds for some constant $c > 0$. We also write $U \asymp V$ if $U \ll V \ll U$. Throughout the paper, the implied constants in the symbols ‘O’, ‘$\ll$’ and ‘$\gg$’ are absolute.

## 1.3. New bounds of exponential sums.
We note that to simplify the results and exposition we assume that $0$ is excluded from the sets under consideration. This changes the absolute value of, say, the sum $S(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma)$ by at most $O(XY + XZ + YZ)$.

**Theorem 1.1.** For any sets $\mathcal{X}, \mathcal{Y}, \mathcal{Z} \subseteq \mathbb{F}_p^*$ of cardinalities $X, Y, Z$, respectively, with $X \geq Y \geq Z$ and any weights $\alpha = (\alpha_x), \beta = (\beta_y)$ and $\gamma = (\gamma_z)$ with

$$ \max_{x \in \mathcal{X}} |\alpha_x| \leq 1, \quad \max_{y \in \mathcal{Y}} |\beta_y| \leq 1, \quad \max_{z \in \mathcal{Z}} |\gamma_z| \leq 1, $$

we have

$$ S(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma) \ll p^{1/4} X^{3/4} Y^{3/4} Z^{7/8}. $$

Theorem 1.1 in nontrivial and improves the bound

$$ (1.6) \qquad |S(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma)| \leq p^{1/2} X^{1/2} Y^{1/2} Z, $$
which is instant from (1.2), if

$$X^{1/4}Y^{1/4}Z^{1/8} \gg p^{1/4} \quad \text{and} \quad X^{1/4}Y^{1/4}Z^{-1/8} \ll p^{1/4}.$$

We rewrite these inequalities as

$$pZ^{1/2} \gg XY \gg pZ^{-1/2}.$$

In particular if $X = Y = Z$, then

$$S(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma) \ll p^{1/4}X^{19/8},$$

which is nontrivial for $X \ge p^{2/5}$. This range of non-triviality is inferior to that obtained by Bourgain [2].

It is easy to see that Theorem 1.1 improves (1.3) for all cardinalities $X, Y, Z$ when $p \to \infty$, since without loss of generality we can assume that $X \ge Y \ge Z$ and then we have

$$\begin{aligned} p^{1/4}X^{3/4}Y^{3/4}Z^{7/8} &\le p^{5/18}X^{3/4}Y^{3/4}Z^{7/8} \\ &= p^{5/18}(XYZ)^{13/16}(Z/(XY))^{1/16} \\ &\le p^{5/18}(XYZ)^{13/16}. \end{aligned}$$

Also, to indicate the strength of Theorem 1.1 we compare it with the bound of Hegyvári [20, Corollary 2]. First we note that the bound of multilinear sums from [20, Theorem 3.1] makes use of only three sets and does not improve with the number of sets. Now for $X \asymp Y \asymp p^{1/2}$ and $Z \ge p^{3/8}$, ignoring very restrictive additive conditions on the sets $\mathcal{X}$, and $\mathcal{Y}$, the bound of [20, Corollary 2] takes form $O(p^{3/16}XYZ^{1/2}) = O(p^{19/16}Z^{1/2})$. Unlike Theorem 1.1, the set $\mathcal{Z}$ need not be the smallest set. Once $\mathcal{Z}$ is assumed to be the smallest set, then Theorem 1.1 gives the bound $O(pZ^{7/8})$, which is stronger in the range $Z < p^{1/2}$ (in which case $\mathcal{Z}$ is the smallest set anyway).

We also compare Theorem 1.1 with the bound of Garaev [15, Theorem 4.2], which work trilinear sums over arbitrary sets (but without weights). More precisely, by [15, Theorem 4.2], if $XY \gg p$ then

$$\left| \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} \sum_{z \in \mathcal{Z}} \mathbf{e}_p(xyz) \right| \le XYZ^{539/540+o(1)},$$

while Theorem 1.1 applies to weighted sums and yields (under the same condition $XY \gg p$) the bound of the form $O(p^{1/4}X^{3/4}Y^{3/4}Z^{7/8}) = O(XYZ^{7/8})$.

As yet another evidence of the efficiency of our approach and the strength of Theorem 1.1 we note that one can easily recover the second bound of [36, Corollary 19].
We now obtain a bound of quadrilinear analogues of sums (1.1)

$$S(\mathcal{W}, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma, \delta) = \sum_{w \in \mathcal{W}} \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} \sum_{z \in \mathcal{Z}} \alpha_w \beta_x \gamma_y \delta_z \mathbf{e}_p(wxyz)$$

with four sets $\mathcal{W}, \mathcal{X}, \mathcal{Y}, \mathcal{Z} \subseteq \mathbb{F}_p^*$, and weights $\alpha = (\alpha_w)_{w \in \mathcal{W}}, \beta = (\beta_x)_{x \in \mathcal{X}}, \gamma = (\gamma_y)_{y \in \mathcal{Y}}$ and $\delta = (\delta_z)_{z \in \mathcal{Z}}$ supported on $\mathcal{W}, \mathcal{X}, \mathcal{Y}$ and $\mathcal{Z}$, respectively.

To simplify the exposition we now assume that all cardinalities are less than $p^{2/3}$.

**Theorem 1.2.** For any sets $\mathcal{W}, \mathcal{X}, \mathcal{Y}, \mathcal{Z} \subseteq \mathbb{F}_p^*$ of cardinalities $W, X, Y, Z$, respectively, with

$$p^{2/3} \ge W \ge X \ge Y \ge Z,$$

and any weights $\alpha = (\alpha_x), \beta = (\beta_y), \gamma = (\gamma_z)$ and $\delta = (\delta_z)$ with

$$\max_{w \in \mathcal{W}} |\alpha_w| \le 1, \quad \max_{x \in \mathcal{X}} |\beta_x| \le 1, \quad \max_{y \in \mathcal{Y}} |\gamma_y| \le 1, \quad \max_{z \in \mathcal{Z}} |\delta_z| \le 1,$$

we have

$$S(\mathcal{W}, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma, \delta) \ll p^{1/8} W^{7/8} X^{7/8} Y^{15/16} Z^{15/16}.$$

If $W = X = Y = Z$, the bound in Theorem 1.2 becomes

$$S(\mathcal{W}, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma, \delta) \ll p^{1/8} W^{29/8},$$

which is nontrivial for $W \ge p^{1/3}$. Once again, the range of non-triviality is inferior to that obtained by Bourgain [2].

Next we move to the case of sums (1.5) with more complicated weights.

**Theorem 1.3.** For any sets $\mathcal{X}, \mathcal{Y}, \mathcal{Z} \subseteq \mathbb{F}_p^*$ of cardinalities $X, Y, Z$, respectively, with $X \ge Y \ge Z$ and weights $\rho = (\rho_{x,y}), \sigma = (\sigma_{x,z})$ and $\tau = (\tau_{y,z})$ with

$$\max_{(x,y) \in \mathcal{X} \times \mathcal{Y}} |\rho_{x,y}| \le 1, \quad \max_{(x,z) \in \mathcal{X} \times \mathcal{Z}} |\sigma_{x,z}| \le 1, \quad \max_{(y,z) \in \mathcal{Y} \times \mathcal{Z}} |\tau_{y,z}| \le 1,$$

we have

$$T(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \rho, \sigma, \tau) \ll p^{1/8} X^{7/8} Y^{29/32} Z^{29/32}.$$

For $X = Y = Z$, Theorem 1.3 is nontrivial in the same range $X \ge p^{2/5}$ like Theorem 1.1.

We also present an explicit bound for multilinear sums with four sets. Again, we make a simplifying assumption that all cardinalities are less than $p^{2/3}$.
**Theorem 1.4.** For any sets $W, X, Y, Z \subseteq \mathbb{F}_p^*$ of cardinalities $W, X, Y, Z$, respectively, with

$$p^{2/3} \ge W \ge X \ge Y \ge Z,$$

and weights $\vartheta = (\vartheta_{w,x,y}), \rho = (\rho_{w,x,z}), \sigma = (\sigma_{w,y,z})$ and $\tau = (\tau_{x,y,z})$ with

$$\max_{(w,x,y) \in W \times X \times Y} |\vartheta_{w,x,y}| \le 1, \quad \max_{(w,x,z) \in W \times X \times Z} |\rho_{w,x,z}| \le 1,$$

$$\max_{(w,y,z) \in W \times Y \times Z} |\sigma_{w,y,z}| \le 1, \quad \max_{(x,y,z) \in X \times Y \times Z} |\tau_{x,y,z}| \le 1,$$

we have

$$T(W, X, Y, Z; \vartheta, \rho, \sigma, \tau) \ll p^{1/16} W^{15/16} (XY)^{61/64} Z^{31/32}.$$

For $W = X = Y = Z$, the bound of Theorem 1.4 becomes

$$T(W, X, Y, Z; \vartheta, \rho, \sigma, \tau) \ll p^{1/16} W^{61/16},$$

which is nontrivial for $W \ge p^{1/3}$ which is the same range as for Theorem 1.4 in the case of sets of equal cardinalities.

Note that although the bound of Theorems 1.3 and 1.4 are weaker than that of Theorems 1.1 and 1.2, they however apply to more general sums, including, for example, to sums of the form

$$(1.7) \quad \sum_{x \in X} \sum_{y \in Y} \sum_{z \in Z} e_p(F(x, y, z)), \quad \sum_{w \in W} \sum_{x \in X} \sum_{y \in Y} \sum_{z \in Z} e_p(G(w, x, y, z)),$$

for any cubic polynomial $F(x, y, z) \in \mathbb{F}_p[x, y, z]$ and quartic polynomial $G(w, x, y, z) \in \mathbb{F}_p[w, x, y, z]$ that contain a term of the form $axyz$ and $awxyz$, respectively, with $a \ne 0$.

**1.4. Applications.** Given two set $A, B \subseteq \mathbb{F}_q$ we define the sum, difference and product sets

$$A + B = \{a + b : a \in A, b \in B\},$$

$$(1.8) \qquad A - B = \{a - b : a \in A, b \in B\},$$

$$AB = \{ab : a \in A, b \in B\}.$$

These notations naturally extend to operations with any number of sets.

First we recall that by a result Sárközy [41], for any sets $A, B, C \subseteq \mathbb{F}_q^*$ of cardinalities $A, B, C$, we have

$$(1.9) \qquad \#(AB + C) = q + O\left(\frac{q^3}{ABC}\right),$$
see also [44, Equation (9)]. This immediately implies that there is an absolute constant $c_0$ such that for any sets $A, B, C, D \subseteq \mathbb{F}_q^*$ of cardinalities $A, B, C, D$ with $ABCD \ge c_0q^3$, we have

$$ (1.10) \qquad \mathcal{A}\mathcal{B} + \mathcal{C} + \mathcal{D} = \mathbb{F}_q. $$

Indeed, if there is $\lambda \in \mathbb{F}_q \setminus (\mathcal{A}\mathcal{B} + \mathcal{C} + \mathcal{D})$ then $(\mathcal{A}\mathcal{B} + \mathcal{C}) \cap (\lambda - \mathcal{D}) = \emptyset$ and thus

$$ D = \#(\lambda - \mathcal{D}) < q - \#(\mathcal{A}\mathcal{B} + \mathcal{C}) = O\left(\frac{q^3}{ABC}\right) $$

by (1.9). Furthermore, over a prime field $\mathbb{F}_p$, Roche-Newton, Rudnev and Shkredov [36, Theorem 1] give a lower bound

$$ (1.11) \qquad \#(\mathcal{A}\mathcal{B} + \mathcal{C}) \gg \min\{p, (ABC)^{1/2}, ABC/M\} $$

where $M = \max\{A, B, C\}$.

We now consider the related question, involving triple products and four sets.

**Theorem 1.5.** For any sets $A, B, C, D \subseteq \mathbb{F}_p^*$ of cardinalities $A, B, C, D$, respectively, with

$$ A \ge B \ge C, $$

we have

$$ \#(\mathcal{A}\mathcal{B}\mathcal{C} + \mathcal{D}) = p + O(p^{5/2}A^{-1/2}B^{-1/2}C^{-1/4}D^{-1}) $$

and

$$ \#(\mathcal{A}\mathcal{B}\mathcal{C} + \mathcal{D}) \gg \min\{p, p^{-1/2}A^{1/2}B^{1/2}C^{1/4}D\}. $$

In particular, we immediately derive a version of the property (1.10) for five sets in $\mathbb{F}_p$.

**Corollary 1.6.** There is an absolute constant $c_0$ such that for any sets $A, B, C, D, E \subseteq \mathbb{F}_p^*$ of cardinalities $A, B, C, D, E$ with

$$ ABC^{1/2}D^2E^2 \ge c_0p^5, $$

we have

$$ \mathcal{A}\mathcal{B}\mathcal{C} + \mathcal{D} + \mathcal{E} = \mathbb{F}_p. $$

Furthermore, we also define

$$ \mathcal{A}^k = \{a^k : a \in \mathcal{A}\} $$

(note that $\mathcal{A}^k$ is not the $k$-fold product set of $\mathcal{A}$ which sometimes is also denoted by $\mathcal{A}^k$).
Aksoy Yazici, Murphy, Rudnev and Shkredov [1, Corollary 2.13(1)] have shown that for any set $\mathcal{A} \subseteq \mathbb{F}_p$ of cardinality $A < p^{7/12}$ we have

$$ (1.12) \qquad \#((\mathcal{A} - \mathcal{A})^3 + (\mathcal{A} - \mathcal{A})^3) \gg A^{36/35}. $$

Here we obtain a related result involving four sets from $\mathbb{F}_p$.

**Theorem 1.7.** For any sets $\mathcal{A}, \mathcal{B}, \mathcal{C}, \mathcal{D} \subseteq \mathbb{F}_p^*$ of cardinalities $A, B, C, D$, respectively, with

$$ p^{2/3} \ge A \ge B \ge C, $$

we have

$$ \#((\mathcal{A} + \mathcal{B} + \mathcal{C})^3 + \mathcal{D}) = p + O(p^{9/4}A^{-1/4}B^{-3/16}C^{-3/16}D^{-1}) $$

and

$$ \#((\mathcal{A} + \mathcal{B} + \mathcal{C})^3 + \mathcal{D}) \gg \min\{p, p^{-1/4}A^{1/4}B^{3/16}C^{3/16}D\}. $$

In particular, if $A = B = C = D$ the lower bounds of Theorems 1.5 and 1.7 are nontrivial for $A \ge p^{2/5}$. We also obtain yet another analogue of (1.10):

**Corollary 1.8.** There is an absolute constant $c_0$ such that for any sets $\mathcal{A}, \mathcal{B}, \mathcal{C}, \mathcal{D}, \mathcal{E} \subseteq \mathbb{F}_p^*$ of cardinalities $A, B, C, D, E$ with

$$ AB^{3/4}C^{3/4}D^4E^4 \ge c_0p^9, $$

we have

$$ (\mathcal{A} + \mathcal{B} + \mathcal{C})^3 + \mathcal{D} + \mathcal{E} = \mathbb{F}_p. $$

Theorems 1.5 and 1.7 are based on bounds of exponential sums of Theorems 1.1 and 1.3, respectively. Using Theorems 1.2 and 1.4 one can obtain versions of Theorems 1.5 and 1.7 for more complicated sets such as $\mathcal{A}\mathcal{B}\mathcal{C}\mathcal{D} + \mathcal{E}$ and $(\mathcal{A} + \mathcal{B} + \mathcal{C} + \mathcal{D})^4 + \mathcal{E}$.

Our final application is an extension of the following inequality of Garaev [14, Theorem 1] to triple products

$$ \#(\mathcal{A}\mathcal{A})\#(\mathcal{A} + \mathcal{A}) \gg \min \left\{ pA, \frac{A^4}{p} \right\}. $$

**Theorem 1.9.** Let $\mathcal{A}, \mathcal{B}, \mathcal{C}, \mathcal{D} \subseteq \mathbb{F}_p^*$ be sets of cardinalities $A, B, C$ and $D$, respectively. Consider the sets

$$ \mathcal{U} = \mathcal{A}\mathcal{B}\mathcal{C} \quad \text{and} \quad \mathcal{V} = \mathcal{A} + \mathcal{D} $$

of cardinalities $\mathcal{U}$ and $\mathcal{V}$, respectively. Then we have

$$ UV \gg pA \quad \text{or} \quad U^3V^2 \gg A^4BC^{1/2}D^2p^{-1}. $$
In particular Theorem 1.9 implies that

$$ \max\{U, V\} \gg \min\{p^{1/2}A^{1/2}, A^{4/5}B^{1/5}C^{1/10}D^{2/5}p^{-1/5}\}. $$

Furthermore, if $\mathcal{G} \subseteq \mathbb{F}_p^*$ is a multiplicative subgroup of $\mathbb{F}_p^*$ of order $T$ then for any set $\mathcal{S} \subseteq \mathbb{F}_p^*$ with $\#\mathcal{S} = S$, by Theorem 1.9 we have

$$ (1.13) \qquad \#(\mathcal{G} + \mathcal{S}) \gg \min\{p, ST^{5/4}p^{-1/2}\}, $$

which improves the trivial universal lower bound $S$ for $T \geq Cp^{2/5}$ with any a sufficiently large constant $C$.

As before, we note that using Theorem 1.2 one can obtain analogues of Theorem 1.9 for more complicated sets. For example, Theorem 1.2 allows to deal with the sets

$$ \mathcal{U} = \mathcal{A}\mathcal{B}\mathcal{C}\mathcal{D} \quad \text{and} \quad \mathcal{V} = \mathcal{A} + \mathcal{E} $$

with $\mathcal{A}, \mathcal{B}, \mathcal{C}, \mathcal{D}, \mathcal{E} \subseteq \mathbb{F}_p^*$. In turn one can obtain the following version of (1.13)

$$ \#(\mathcal{G} + \mathcal{S}) \gg \min\{p, ST^{3/4}p^{-1/4}\}, $$

which is now nontrivial for $T \geq Cp^{1/3}$ with any a sufficiently large constant $C$.

**1.5. Recent development.** Our results depend on the forthcoming bounds on the quantity $T(\mathcal{U})$, c.f. Lemma 2.8. The recent work [30] contains an improvement when $p^{1/2} \leq U \leq p^{3/5}$, which leads to improved bounds for the exponential sum we consider in certain ranges of the cardinalities $X, U, V, W$.

## 2. PRELIMINARIES

**2.1. Background from arithmetic combinatorics.** Some of the results of this section apply to arbitrary fields $\mathbb{F}_q$ of $q$ elements so we formulate them in this form.

The proofs of Theorems 1.1–1.4 come down to non-trivial upper bounds on the number of solutions to equations with variables in prescribed sets in $\mathbb{F}_p^*$. Of particular importance in our considerations is the following such quantity.

**Definition 2.1.** Let $\mathcal{U}, \mathcal{V}, \mathcal{W} \subseteq \mathbb{F}_q^*$. Then $N(\mathcal{U}, \mathcal{V}, \mathcal{W})$ denotes the number of solutions to

$$ u_1(v_1 - w_1) = u_2(v_2 - w_2) $$

with $u_1, u_2 \in \mathcal{U}$, $v_1, v_2 \in \mathcal{V}$ and $w_1, w_2 \in \mathcal{W}$.
A trivial upper bound for $N(U, V, W)$ in terms of the cardinalities $U = \#U, V = \#V, W = \#W$ is

$$N(U, V, W) \leq UV^2W^2 + U^2VW.$$

This is because for each 5-tuple $(u_1, v_1, v_2, w_1, w_2)$ where $v_1 \neq w_1$ and $v_2 \neq w_2$ there is at most one $u_2$ satisfying $u_1(v_1 - w_1) = u_2(v_2 - w_2)$; while if $v_1 = w_1$ there is no solution unless $v_2 = w_2$ and in this case all $u_2 \in U$ work. Our method for obtaining non-trivial upper bounds for the modulus of exponential sums relies on non-trivial upper bounds for $N(U, V, W)$. The first non-trivial upper bound (for the special case $U = V = W \le p^{2/3}$) can be traced back to the breakthrough paper of Bourgain, Katz and Tao [8] on sum-product questions in $\mathbb{F}_p$. Bourgain, Katz and Tao have shown [8, Theorem 6.2] that, under mild conditions, a set of $n$ points in $\mathbb{F}_p^2$ and a set of $n$ lines in $\mathbb{F}_p^2$ determine $O(n^{3/2-c})$ points-lines incidences for an absolute albeit small $c > 0$. From this a non-trivial upper bound for $N(U, V, W)$ follows easily, for example, by modifying [10, Lemma 3.5.1] in Dvir's survey [10]. Progress over the years to the Bourgain-Katz-Tao result, see [4, 13, 21, 23, 27, 29, 31, 37] and references therein, leads implicitly to improved upper bounds for $N(U, V, W)$.

The most recent and significant progress in estimating $N(U, V, W)$ has its roots in a bound of Rudnev [38] on the number of incidences between a set of points in $\mathbb{F}_p^3$ and a set of planes in $\mathbb{F}_p^3$. Rudnev's work [38] is based on a theorem of Guth and Katz [18, Theorem 2.10] from their solution to the Erdős distinct distance conjecture for planar sets and on the 19th century Plücker-Klein formalism for projective line geometry [34]. Applying the incidence theorem of Rudnev [38] to $N(U, V, W)$ requires an elegant trick and has been done by Aksoy Yazici, Murphy, Rudnev and Shkredov [1, Theorem 1]. Given the importance of Rudnev's points-planes incidence theorem to our results, it should be noted that the theorem is essentially sharp. Existing points-lines incidence results in $\mathbb{F}_p^3$ (see [12, 28] and also [17]) do not seem to work as well for bounding quantities as $N(U, V, W)$.

We begin our thorough examination of $N(U, V, W)$ with an easy upper bound based on multiplicative characters in $\mathbb{F}_q$.

**Lemma 2.2.** Let $U, V, W \subseteq \mathbb{F}_q^*$ with cardinalities $U, V, W$, respectively. The following inequality holds:

$$\left| N(U, V, W) - \frac{U^2V^2W^2}{q-1} \right| \le qUVW.$$
*Proof.* Clearly, the number of zero-solutions, that is, solutions with $u_1(v_1 - w_1) = u_2(v_2 - w_2) = 0$ is at most $U^2VW$, because we must have $v_1 = w_1$ and $v_2 = w_2$. We use standard properties of multiplicative characters to bound the number $N(U, V, W)^*$ of non-zero solutions. Let $\Omega$ denote the set of all $q-1$ multiplicative characters of $\mathbb{F}_q$ and let $\Omega^*$ be the set of nonprincipal characters; we refer to [22, Chapter 3] for a background on characters. In particular, using the orthogonality of characters, we write

$$ 
\begin{aligned}
N(U, V, W)^* &= \frac{1}{q-1} \sum_{\chi \in \Omega} \sum_{u_1, u_2 \in U} \sum_{v_1, v_2 \in V} \sum_{w_1, w_2 \in W} \chi \left( \frac{u_1(v_1 - w_1)}{u_2(v_2 - w_2)} \right) \\
&= \frac{1}{q-1} \sum_{\chi \in \Omega} \left| \sum_{u \in U} \sum_{v \in V} \sum_{w \in W} \chi(u(v-w)) \right|^2 \\
&= \frac{U^2 V^2 W^2}{q-1} + \frac{1}{q-1} \sum_{\chi \in \Omega^*} \left| \sum_{u \in U} \chi(u) \right|^2 \left| \sum_{v \in V} \chi(v-w) \right|^2.
\end{aligned}
$$

Recalling the well-known analogue of (1.2):

$$ (2.1) \qquad \max_{\chi \in \Omega^*} \left| \sum_{\substack{v \in V \\ w \in W}} \chi(v-w) \right| \le \sqrt{qVW}, $$

we obtain

$$ \left| N(U, V, W)^* - \frac{U^2 V^2 W^2}{q-1} \right| \le \frac{qVW}{q-1} \sum_{\chi \in \Omega^*} \left| \sum_{u \in U} \chi(u) \right|^2. $$

Using the orthogonality of characters again, we derive

$$ 
\begin{aligned}
\left| N(U, V, W)^* - \frac{U^2 V^2 W^2}{q-1} \right| &\le \frac{qVW}{q-1} \left( \sum_{\chi \in \Omega} \left| \sum_{u \in U} \chi(u) \right|^2 - U^2 \right) \\
&\le qUVW - U^2VW,
\end{aligned}
$$

which concludes the proof. □

<figure><img src="image_1.png" /></figure>

The next step is to obtain a complementary bound for small sets $U, V, W \subseteq \mathbb{F}_p^*$ in a prime field $\mathbb{F}_p$. It is based on the points-planes incidence bound of Rudnev [38] and in particular on its application described by Aksoy Yazici, Murphy, Rudnev and Shkredov [1, Theorem 1].
**Lemma 2.3.** Let $\mathcal{U}, \mathcal{V}, \mathcal{W} \subseteq \mathbb{F}_p^*$ with cardinalities $U, V, W$, respectively, and set $M = \max\{U, V, W\}$. Suppose that $UVW \ll p^2$. The following inequality holds:

$$N(\mathcal{U}, \mathcal{V}, \mathcal{W}) \ll U^{3/2}V^{3/2}W^{3/2} + MUVW.$$

*Proof.* The result follows from [1, Theorem 11] by setting $A = \mathcal{U}$ and $L \simeq \mathcal{V} \times \mathcal{W}$ to be the set of lines $\{y = vx + vw : v \in \mathcal{V}, w \in \mathcal{W}\}$. $\square$

Combining the two results gives an upper bound on $N(\mathcal{U}, \mathcal{V}, \mathcal{W})$ over $\mathbb{F}_p$.

**Corollary 2.4.** Let $\mathcal{U}, \mathcal{V}, \mathcal{W} \subseteq \mathbb{F}_p^*$ with cardinalities $U, V, W$, respectively, and set $M = \max\{U, V, W\}$. The following inequality holds.

$$N(\mathcal{U}, \mathcal{V}, \mathcal{W}) \ll \frac{U^2V^2W^2}{p} + U^{3/2}V^{3/2}W^{3/2} + MUVW.$$

*Proof.* When $UVW \ge p^2$ we apply Lemma 2.2. It is easy to see that in this range the $U^2V^2W^2/p$ term dominates the other two. When $UVW < p^2$ we apply Lemma 2.3. $\square$

In particular, we see from Corollary 2.4 that when $U = V = W$ we have

$$N(\mathcal{U}, \mathcal{V}, \mathcal{W}) \ll \frac{U^6}{p} + U^{9/2}.$$

We also need two other quantities similar to $N(\mathcal{U}, \mathcal{V}, \mathcal{W})$. We recall that the multiplicative energy $E_\times(\mathcal{U})$ of a set $\mathcal{U} \subseteq \mathbb{F}_p$, is defined as the number of solutions to the equation

$$u_1u_2 = u_3u_4, \quad u_1, u_2, u_3, u_4 \in \mathcal{U}.$$

It is known to play a crucial role in bounds of various exponential sums, see, for example, [15]. However, here our argument relies on bounds of the multiplicative energy of the difference set with multiplicities counted.

**Definition 2.5.** Let $\mathcal{U} \subseteq \mathbb{F}_q^*$. Then $D_\times(\mathcal{U})$ denotes the number of solutions to the equation

$$(u_1 - v_1)(u_2 - v_2) = (u_3 - v_3)(u_4 - v_4), \quad u_i, v_i \in \mathcal{U}, i = 1, 2, 3, 4.$$

An essentially optimal upper bound for $D_\times(\mathcal{U})$ over the real numbers has been obtained by Roche-Newton and Rudnev [35] by an application of the Guth–Katz theorem [18]. The quantity $D_\times(\mathcal{U})$ does not seem to have been studied in the finite field context until recently (see [33]). We will present a different bound, which depends on a third quantity that,
moreover, features an autonomous role in the proofs of the exponential sum estimates is the following.

**Definition 2.6.** Let $\mathcal{U} \subseteq \mathbb{F}_q^*$. Then $T(\mathcal{U})$ denotes the number of solutions to the equation

$$ \frac{u_1 - v}{u_2 - v} = \frac{u_3 - w}{u_4 - w}, \quad u_i, v, w \in \mathcal{U}, i = 1, 2, 3, 4. $$

The notation reflects the fact that the function $T(\mathcal{U})$ counts the number of collinear triplets of points in $\mathcal{U} \times \mathcal{U} \subseteq \mathbb{F}_q^2$. A more or less optimal upper bound for $T(\mathcal{U})$ over the real numbers has been obtained by Elekes and Ruzsa in [11] by an application of the Szemerédi–Trotter theorem [45]. In the finite field context, $T(\mathcal{U})$ is studied by Aksoy Yazici, Murphy, Rudnev and Shkredov in [1].

We begin our examination of $D_\times(\mathcal{U})$ and $T(\mathcal{U})$ with the following elementary estimate that relates the two quantities.

**Lemma 2.7.** For any set $\mathcal{U} \subseteq \mathbb{F}_p$ of cardinality $\#\mathcal{U} = U$, we have

$$ D_\times(\mathcal{U}) \ll U^2 T(\mathcal{U}) + U^6. $$

*Proof.* Clearly $D_\times(\mathcal{U}) = D_\times^*(\mathcal{U}) + O(U^6)$ where $D_\times^*(\mathcal{U})$ is the number of solutions to the equation

$$ \frac{u_1 - v_1}{u_2 - v_2} = \frac{u_3 - v_3}{u_4 - v_4} \neq 0, \quad u_i, v_i, \in \mathcal{U}, i = 1, 2, 3, 4. $$

Let $J(\lambda)$ be the number of quadruples $(u_1, u_2, v, w) \in \mathcal{U}^4$ with

$$ (2.2) \qquad \frac{u_1 - v}{u_2 - w} = \lambda $$

and let $J_{v,w}(\lambda)$ be the number of pairs $(u_1, u_2) \in \mathcal{U}^4$ for which (2.2) holds.

Then, by the Cauchy inequality, we have

$$ \begin{aligned} D_{\times}^{*}(\mathcal{U}) &= \sum_{\lambda \in \mathbb{F}_{p}^{*}} J(\lambda)^{2} = \sum_{\lambda \in \mathbb{F}_{p}^{*}} \left( \sum_{v,w \in \mathcal{U}} J_{v,w}(\lambda) \right)^{2} \\ &\le U^{2} \sum_{\lambda \in \mathbb{F}_{p}^{*}} \sum_{v,w \in \mathcal{U}} J_{v,w}(\lambda)^{2} = U^{2} \sum_{v,w \in \mathcal{U}} \sum_{\lambda \in \mathbb{F}_{p}^{*}} J_{v,w}(\lambda)^{2}. \end{aligned} $$

Using that

$$ \begin{aligned} \sum_{\lambda \in \mathbb{F}_p^*} J_{v,w}(\lambda)^2 &= \sum_{\lambda \in \mathbb{F}_p^*} \# \left\{ (u_1, u_2, u_3, u_4) \in \mathcal{U}^4 : \frac{u_1 - v}{u_2 - w} = \frac{u_3 - v}{u_4 - w} = \lambda \right\} \\ &= \# \left\{ (u_1, u_2, u_3, u_4) \in \mathcal{U}^4 : \frac{u_1 - v}{u_3 - v} = \frac{u_2 - w}{u_4 - w} \neq 0 \right\}, \end{aligned} $$
and renaming the variables $(v, w) \to (u_3, u_2)$, we immediately obtain the desired result. □

We now need the bound on $T(\mathcal{U})$ given by Petridis [33], which (for $U \le p^{2/3}$) is based on a result of Aksoy Yazici, Murphy, Rudnev and Shkredov [1, Proposition 2.5] (see also [42, Theorem 10]).

**Lemma 2.8.** For any set $\mathcal{U} \subseteq \mathbb{F}_p$ of cardinality $U$, we have

$$T(\mathcal{U}) \ll \frac{U^6}{p} + U^{9/2}.$$

Thus combining Lemmas 2.7 and 2.8 we obtain

**Corollary 2.9.** For any set $\mathcal{U} \subseteq \mathbb{F}_p$ of cardinality $U$, we have

$$D_{\times}(\mathcal{U}) \ll \frac{U^8}{p} + U^{13/2}.$$

In particular, we see from Corollary 2.9 that when $U \le p^{2/3}$ then the second term dominates and we derive $D_{\times}(\mathcal{U}) \ll U^{13/2}$. We also remark that Rudnev, Shkredov and Stevens [40, Theorem 6] have given a related result.

**2.2. Exponential sums and differences.** We now link multilinear exponential sums (1.5) to exponential sums with differences. For a technical reason it is also convenient for us to prove this in the setting of arbitrary finite fields and additive characters. This may also be useful in further applications.

Namely, for sets $\mathcal{X}_1, \dots, \mathcal{X}_n \subseteq \mathbb{F}_q$, weights $\omega_1, \dots, \omega_n$ and an additive character $\psi$ of $\mathbb{F}_q$, we define

$$T_{\psi}(\mathcal{X}_1, \dots, \mathcal{X}_n; \omega_1, \dots, \omega_n) = \sum_{\mathbf{x} \in \mathcal{X}_1 \times \dots \times \mathcal{X}_n} \dots \sum_{\mathbf{x} \in \mathcal{X}_n} \omega_1(\mathbf{x}) \dots \omega_n(\mathbf{x}) \psi(x_1 \dots x_n).$$

Note that our bound is uniform in $\psi$ (and is actually trivial when $\psi = \psi_0$ is the principal character).

**Lemma 2.10.** Let $n \ge 2$. For any additive character $\psi$ of $\mathbb{F}_q$, sets $\mathcal{X}_i \subseteq \mathbb{F}_q$ of cardinalities $\#\mathcal{X}_i = X_i$, and weights $\omega_i = (\omega_i(\mathbf{x}))_{\mathbf{x} \in \mathbb{F}_p^n}$ such that $\omega_i(\mathbf{x})$ does not depend on the $i$th coordinate of $\mathbf{x} = (x_1, \dots, x_n)$ and

$$\max_{\mathbf{x} \in \mathbb{F}_p^n} |\omega_i(\mathbf{x})| \le 1,$$
for $i = 1, \dots, n$, we have

$$|T_{\psi}(\mathcal{X}_1, \dots, \mathcal{X}_n; \omega_1, \dots, \omega_n)|^{2^{n-1}} \\ \le X_1^{2^{n-1}-1} (X_2 \dots X_n)^{2^{n-1}-2} \sum_{x_2, y_2 \in \mathcal{X}_2} \dots \sum_{x_n, y_n \in \mathcal{X}_n} \\ \left| \sum_{x_1 \in \mathcal{X}_1} \psi(x_1(x_2 - y_2) \dots (x_n - y_n)) \right|$$

*Proof.* For every complex number $\xi$ we write $|\xi|^2 = \xi \bar{\xi}$.

We first establish the result for $n = 2$. Let us begin by eliminating $\omega_2$ by applying the triangle inequality.

$$|T_{\psi}(\mathcal{X}_1, \mathcal{X}_2; \omega_1, \omega_2)| = \left| \sum_{x_1 \in \mathcal{X}_1} \omega_2(x_1) \sum_{x_2 \in \mathcal{X}_2} \omega_1(x_2) \psi(x_1 x_2) \right| \\ \le \sum_{x_1 \in \mathcal{X}_1} |\omega_2(x_1)| \left| \sum_{x_2 \in \mathcal{X}_2} \omega_1(x_2) \psi(x_1 x_2) \right|.$$

Squaring both sides and applying the Cauchy inequality gives

$$|T_{\psi}(\mathcal{X}_1, \mathcal{X}_2; \omega_1, \omega_2)|^2 \le X_1 \sum_{x_1 \in \mathcal{X}_1} \left| \sum_{x_2 \in \mathcal{X}_2} \omega_1(x_2) \psi(x_1 x_2) \right|^2 \\ = X_1 \sum_{x_1 \in \mathcal{X}_1} \sum_{x_2, y_2 \in \mathcal{X}_2} \omega_1(x_2) \overline{\omega_1(y_2)} \psi(x_1(x_2 - y_2)) \\ = X_1 \sum_{x_2, y_2 \in \mathcal{X}_2} \omega_1(x_2) \overline{\omega_1(y_2)} \sum_{x_1 \in \mathcal{X}_1} \psi(x_1(x_2 - y_2)) \\ \le X_1 \sum_{x_2, y_2 \in \mathcal{X}_2} \left| \sum_{x_1 \in \mathcal{X}_1} \psi(x_1(x_2 - y_2)) \right|.$$

This proves the result for $n = 2$. For $n > 2$ the argument is similar, though it requires the Hölder inequality. Using that $\omega_n(\mathbf{x})$ does not depend on $x_n$, we get

$$|T_{\psi}(\mathcal{X}_1, \dots, \mathcal{X}_n; \omega_1, \dots, \omega_n)| \\ \le \sum_{x_1 \in \mathcal{X}_1} \dots \sum_{x_{n-1} \in \mathcal{X}_{n-1}} \left| \sum_{x_n \in \mathcal{X}_n} \omega_1(\mathbf{x}) \dots \omega_{n-1}(\mathbf{x}) \psi(x_1 \dots x_n) \right|.$$
Hence, by the Cauchy inequality we derive

$$
\begin{align*}
& |T_{\psi}(\mathcal{X}_1, \dots, \mathcal{X}_n; \omega_1, \dots, \omega_n)|^2 \\
& \le X_1 \dots X_{n-1} \sum_{x_1 \in \mathcal{X}_1} \dots \sum_{x_{n-1} \in \mathcal{X}_{n-1}} \\
& \qquad \left| \sum_{x_n \in \mathcal{X}_n} \omega_1(\mathbf{x}) \dots \omega_{n-1}(\mathbf{x}) \psi(x_1 \dots x_n) \right|^2 \\
& = X_1 \dots X_{n-1} \sum_{x_1 \in \mathcal{X}_1} \dots \sum_{x_{n-1} \in \mathcal{X}_{n-1}} \\
& \qquad \sum_{x_n, y_n \in \mathcal{X}_n} \omega_1(\mathbf{x}) \bar{\omega}_1(\mathbf{y}) \dots \omega_{n-1}(\mathbf{x}) \bar{\omega}_{n-1}(\mathbf{y}) \\
& \qquad \qquad \qquad \psi(x_1 \dots x_{n-1}(x_n - y_n)),
\end{align*}
$$

where $\mathbf{y} = (x_1, \dots, x_{n-1}, y_n)$ (and as before $\mathbf{x} = (x_1, \dots, x_n)$). By
changing the order of summation, we obtain

$$
|T_{\psi}(\mathcal{X}_1, \dots, \mathcal{X}_n; \omega_1, \dots, \omega_n)|^2 \le X_1 \dots X_{n-1} \sum_{x_n, y_n \in \mathcal{X}_n} \mathfrak{T}(x_n, y_n),
$$

where

$$
\begin{align*}
\mathfrak{T}(x_n, y_n) &= \sum_{x_1 \in \mathcal{X}_1} \dots \sum_{x_{n-1} \in \mathcal{X}_{n-1}} \omega_1(\mathbf{x}) \bar{\omega}_1(\mathbf{y}) \dots \omega_{n-1}(\mathbf{x}) \bar{\omega}_{n-1}(\mathbf{y}) \\
&\qquad \qquad \qquad \qquad \psi(x_1 \dots x_{n-1}(x_n - y_n)).
\end{align*}
$$

Now, raising both sides to the 2<sup>n-2</sup>th power and using the Hölder
inequality, we obtain

$$
(2.3) \qquad |T_{\psi}(\mathcal{X}_1, \dots, \mathcal{X}_n; \omega_1, \dots, \omega_n)|^{2^{n-1}} \\
\le (X_1 \dots X_{n-1})^{2^{n-2}} X_n^{2(2^{n-2}-1)} \sum_{x_n, y_n \in \mathcal{X}_n} |\mathfrak{T}(x_n, y_n)|^{2^{n-2}}.
$$

We apply the inductive hypothesis to bound $|\mathfrak{T}(x_n, y_n)|^{2^{n-2}}$ for every
$x_n, y_n \in \mathcal{X}_n$. For each $j = 1, \dots, n-1$, the weights

$$
\omega_j(\mathbf{x}) \bar{\omega}_j(\mathbf{y}) = \omega_j((x_1, \dots, x_{n-1}, x_n)) \bar{\omega}_j((x_1, \dots, x_{n-1}, y_n))
$$

satisfy the necessary conditions with respect to $x_1, \dots, x_{n-1}$. Applying the inductive hypothesis to the above character sum (where the character $\psi(u)$ is replaced by the character $\psi_{x_n, y_n}(u) = \psi(u(x_n - y_n))$) gives
$$|\mathcal{T}(x_n, y_n)|^{2n-2} \le X_1^{2n-2-1} (X_2 \dots X_{n-1})^{2n-2-2} \sum_{x_2, y_2 \in \mathcal{X}_2} \dots \sum_{x_{n-1}, y_{n-1} \in \mathcal{X}_{n-1}} \left| \sum_{x_1 \in \mathcal{X}_1} \psi(x_1(x_2-y_2) \dots (x_{n-1}-y_{n-1})(x_n-y_n)) \right|.$$

Substituting in (2.3) completes the inductive step and thus finishes the proof. □

### 3. PROOFS OF BOUNDS OF EXPONENTIAL SUMS

#### 3.1. Proof of Theorem 1.1. Recall that

$$S(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma) = \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} \sum_{z \in \mathcal{Z}} \alpha_x \beta_y \gamma_z \mathbf{e}_p(xyz).$$

We begin by eliminating $\alpha_x$ and $\gamma_z$.

$$\begin{aligned} |S(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma)| &= \left| \sum_{x \in \mathcal{X}} a_x \sum_{z \in \mathcal{Z}} \gamma_z \sum_{y \in \mathcal{Y}} \beta_y \mathbf{e}_p(xyz) \right| \\ &\le \sum_{x \in \mathcal{X}} \sum_{z \in \mathcal{Z}} \left| \sum_{y \in \mathcal{Y}} \beta_y \mathbf{e}_p(xyz) \right|. \end{aligned}$$

We proceed as in the proof of Lemma 2.10 and, using the Cauchy inequality, derive

$$\begin{aligned} |S(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma)|^2 &\le XZ \sum_{x \in \mathcal{X}} \sum_{z \in \mathcal{Z}} \left| \sum_{y \in \mathcal{Y}} \beta_y \mathbf{e}_p(xyz) \right|^2 \\ &= XZ \sum_{x \in \mathcal{X}} \sum_{z \in \mathcal{Z}} \sum_{y_1, y_2 \in \mathcal{Y}} \beta_{y_1} \bar{\beta}_{y_2} \mathbf{e}_p(xz(y_1 - y_2)). \end{aligned}$$

For $\lambda \in \mathbb{F}_p$, we now denote

$$\tilde{J}(\lambda) = \sum_{\substack{(y_1, y_2, z) \in \mathcal{Y}^2 \times \mathcal{Z} \\ (y_1 - y_2)z = \lambda}} \beta_{y_1} \bar{\beta}_{y_2}$$

thus we have

$$|S(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma)|^2 \le XZ \sum_{\lambda \in \mathbb{F}_p} \sum_{x \in \mathcal{X}} \tilde{J}(\lambda) \mathbf{e}_p(\lambda x).$$

Clearly, $|\tilde{J}(\lambda)| \le J(\lambda)$, where $J(\lambda)$ is the number of triples $(y_1, y_2, z) \in \mathcal{Y}^2 \times \mathcal{Z}$ with the same value of the product $(y_1 - y_2)z = \lambda \in \mathbb{F}_p$. It is
also clear that

$$ (3.1) \qquad \sum_{\lambda \in \mathbb{F}_p} J(\lambda)^2 = N(\mathcal{Z}, \mathcal{Y}, \mathcal{Y}), $$

where $N(\mathcal{U}, \mathcal{V}, \mathcal{W})$ is as in Definition 2.1 in Section 2.1.

Thus applying (1.2) together with (3.1) we obtain

$$ |S(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma)|^2 \le XZ \sqrt{pXN(\mathcal{Z}, \mathcal{Y}, \mathcal{Y})}. $$

Using Corollary 2.4, we derive

$$ S(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma) \ll X^{3/4}YZ + p^{1/4}X^{3/4}Y^{3/4}Z^{7/8}. $$

Our final task is to remove the first term $X^{3/4}YZ$. This first term dominates the second term only when $p \le YZ^{1/2}$. In this range, however, we deploy the classical bound following from the triangle inequality and (1.2)

$$ \begin{aligned} |S(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma)| &\le p^{1/2} X^{1/2} Y^{1/2} Z \le p^{1/4} (YZ^{1/2})^{1/4} X^{1/2} Y^{1/2} Z \\ &= p^{1/4} X^{1/2} Y^{3/4} Z^{9/8} = p^{1/4} X^{3/4} Y^{3/4} Z^{7/8} (Z/X)^{1/4} \\ &\le p^{1/4} X^{3/4} Y^{3/4} Z^{7/8}. \end{aligned} $$

Therefore the term $X^{3/4}YZ$ can be dropped from the final bound.

3.2. **Proof of Theorem 1.2.** As in the proof of Theorem 1.1, after an application of the Cauchy inequality, we arrive to

$$ \begin{aligned} |S(\mathcal{W}, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma, \delta)|^2 &\le WYZ \sum_{w \in \mathcal{W}} \sum_{y \in \mathcal{Y}} \sum_{z \in \mathcal{Z}} \sum_{x_1, x_2 \in \mathcal{X}} \beta_{x_1} \bar{\beta}_{x_2} \mathbf{e}_p(\text{wyz}(x_1 - x_2)) \\ &\le WYZ \sum_{x_1, x_2 \in \mathcal{X}} \sum_{y \in \mathcal{Y}} \sum_{z \in \mathcal{Z}} \left| \sum_{w \in \mathcal{W}} \mathbf{e}_p(\text{wyz}(x_1 - x_2)) \right|. \end{aligned} $$

Applying the Cauchy inequality one more time, we derive

$$ \begin{aligned} |S(\mathcal{W}, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma, \delta)|^4 &\le (WYZ)^2 X^2 Y Z \sum_{x_1, x_2 \in \mathcal{X}} \sum_{y \in \mathcal{Y}} \sum_{z \in \mathcal{Z}} \left| \sum_{w \in \mathcal{W}} \mathbf{e}_p(\text{wyz}(x_1 - x_2)) \right|^2 \\ &= W^2 X^2 Y^3 Z^3 \sum_{w_1, w_2 \in \mathcal{X}} \sum_{x_1, x_2 \in \mathcal{X}} \sum_{y \in \mathcal{Y}} \sum_{z \in \mathcal{Z}} \mathbf{e}_p(\text{yz}(w_1 - w_2)(x_1 - x_2)). \end{aligned} \quad (3.2) $$
We now collect together triples $(w_1, w_2, y) \in W^2 \times \mathcal{Z}$ with the same value of the product $y(w_1 - w_2) = \lambda \in \mathbb{F}_p$ and denote by $I(\lambda)$ the number of such triples.

Similarly, we collect together triples $(x_1, x_2, z) \in \mathcal{X}^2 \times \mathcal{Z}$ with the same value of the product $z(x_1 - x_2) = \mu \in \mathbb{F}_p^*$ and denote by $J(\mu)$ the number of such triples.

Hence we can rewrite (3.2) as

$$ (3.3) \qquad S(W, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma, \delta)^4 \ll W^2 X^2 Y^3 Z^3 \sum_{\lambda, \mu \in \mathbb{F}_p} I(\lambda) J(\mu) \mathbf{e}_p(\lambda \mu). $$

Using analogues of the identity (3.1), we note that by Lemma 2.3 and by the assumption $p^{2/3} \ge W \ge X \ge Y \ge Z$,

$$ \sum_{\lambda \in \mathbb{F}_p} I(\lambda)^2 \ll W^3 Y^{3/2} + W^3 Y \ll W^3 Y^{3/2} $$

and

$$ \sum_{\mu \in \mathbb{F}_p} J(\mu)^2 \ll X^3 Z^{3/2} + X^3 Z \ll X^3 Z^{3/2}. $$

Therefore, using the bound on bilinear sums (1.2), we obtain

$$ \begin{aligned} S(W, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \alpha, \beta, \gamma, \delta)^4 &\ll W^2 X^2 Y^3 Z^3 \sqrt{pW^3 X^3 Y^{3/2} Z^{3/2}}, \\ &= p^{1/2} W^{7/2} X^{7/2} Y^{15/4} Z^{15/4}, \end{aligned} $$

which concludes the proof.

3.3. **Proof of Theorem 1.3.** First we observe that by the classical bound (1.2) we have

$$ T(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \rho, \sigma, \tau) \ll \sqrt{pXYZ}, $$

which implies Theorem 1.3 provided that

$$ p^{1/8} X^{7/8} Y^{29/32} Z^{29/32} \ge \sqrt{pXYZ} $$

or, equivalently,

$$ X^{3/8} Y^{13/32} Z^{-3/32} \ge p^{3/8}. $$

We now note that for $X \ge Y > p^{2/3}$ we have

$$ X^{3/8} Y^{13/32} Z^{-3/32} \ge X^{3/8} Y^{5/16} \ge Y^{11/16} \ge p^{11/24} > p^{3/8}. $$

For this reason, we can assume that

$$ (3.4) \qquad Z \le Y \le p^{2/3}. $$
Now, by Lemma 2.10 (with $n = 3$ and $\psi = e_p$) we have

$$|T(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \rho, \sigma, \tau)|^4 \\ \le X^3 Y^2 Z^2 \sum_{y_1, y_2 \in \mathcal{Y}} \sum_{z_1, z_2 \in \mathcal{Z}} \left| \sum_{x \in \mathcal{X}} e_p(x(y_1 - y_2)(z_1 - z_2)) \right|.$$

The number of quadruples $(y_1, y_2, z_1, z_2) \in \mathcal{Y}^2 \times \mathcal{Z}^2$ which satisfy $(y_1 - y_2)(z_1 - z_2) = 0$ is at most $YZ^2 + Y^2Z \le 2Y^2Z$. For such quadruples the inner sums is equal to $X$. Hence,

$$T(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \rho, \sigma, \tau)^4 \\ \le X^3 Y^2 Z^2 \sum_{\substack{y_1, y_2 \in \mathcal{Y} \\ y_1 \ne y_2}} \sum_{\substack{z_1, z_2 \in \mathcal{Z} \\ z_1 \ne z_2}} \left| \sum_{x \in \mathcal{X}} e_p(x(y_1 - y_2)(z_1 - z_2)) \right| \\ + X^4 Y^4 Z^3.$$

We now collect together quadruples $(y_1, y_2, z_1, z_2) \in \mathcal{Y}^2 \times \mathcal{Z}^2$ with the same value of the product $(y_1 - y_2)(z_1 - z_2) = \lambda \in \mathbb{F}_p^*$ and denote by $J(\lambda)$ the number of such quadruples. Hence we can rewrite (3.5) as

$$(3.6) \quad T(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \rho, \sigma, \tau)^4 \ll X^3 Y^2 Z^2 \sum_{\lambda \in \mathbb{F}_p^*} J(\lambda) \left| \sum_{x \in \mathcal{X}} e_p(\lambda x) \right| + X^4 Y^4 Z^3.$$

Yet another application of the Cauchy inequality leads to the bound

$$T(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \rho, \sigma, \tau)^8 \ll X^6 Y^4 Z^4 K \sum_{\lambda \in \mathbb{F}_p} \left| \sum_{x \in \mathcal{X}} e_p(\lambda x) \right|^2 + X^8 Y^8 Z^6,$$

where

$$K = \sum_{\lambda \in \mathbb{F}_p^*} J(\lambda)^2.$$

By the orthogonality of exponential functions, we get

$$(3.7) \qquad \sum_{\lambda \in \mathbb{F}_p} \left| \sum_{x \in \mathcal{X}} e_p(\lambda x) \right|^2 = pX.$$

Thus we have

$$(3.8) \quad T(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \rho, \sigma, \tau)^8 \ll pX^7Y^4Z^4K + X^8Y^8Z^6.$$
It now remains to estimate $K$. Clearly $K$ is the number of solutions to the equation

$$ (y_1 - y_2)(z_1 - z_2) = (y_3 - y_4)(z_3 - z_4) \neq 0, \\ (y_i, z_i) \in \mathcal{Y} \times \mathcal{Z}, \quad i = 1, 2, 3, 4. $$

We express $K$ in terms of multiplicative characters as follows. See [22, Chapter 3] for a background on multiplicative characters.

$$ K = \sum_{y_1, y_2, y_3, y_4 \in \mathcal{Y}} \sum_{z_1, z_2, z_3, z_4 \in \mathcal{Z}} \frac{1}{p-1} \sum_{\chi \in \Omega} \chi((y_1 - y_2)(z_1 - z_2)) \bar{\chi}((y_3 - y_4)(z_3 - z_4)). $$

The inner sums is over all $p-1$ distinct multiplicative characters $\chi$ of $\mathbb{F}_p$. Simple transformations lead to the formula

$$ K = \frac{1}{p-1} \sum_{\chi \in \Omega} \left| \sum_{y_1, y_2, \in \mathcal{Y}} \chi(y_1 - y_2) \right|^2 \left| \sum_{z_1, z_2 \in \mathcal{Z}} \chi(z_1 - z_2) \right|^2. $$

Now, using the Cauchy inequality, we obtain

$$ K^2 \le \sum_{\chi \in \Omega} \left| \sum_{y_1, y_2, \in \mathcal{Y}} \chi(y_1 - y_2) \right|^4 \sum_{\chi \in \Omega} \left| \sum_{z_1, z_2 \in \mathcal{Z}} \chi(z_1 - z_2) \right|^4 \le D_{\times}(\mathcal{Y}) D_{\times}(\mathcal{Z}), $$

where $D_{\times}(\mathcal{U})$ is as in Definition 2.5 in Section 2.1, see [5, Lemma 4] for a similar argument. Recalling Corollary 2.9, we obtain

$$ (3.9) \qquad K \ll (Y^4 p^{-1/2} + Y^{13/4}) (Z^4 p^{-1/2} + Z^{13/4}). $$

One easily verifies that under the condition (3.4) we have

$$ Y^4 p^{-1/2} \le Y^{13/4} \quad \text{and} \quad Z^4 p^{-1/2} \le Z^{13/4}. $$

Hence, the bound (3.9) simplifies as

$$ (3.10) \qquad K \ll Y^{13/4} Z^{13/4}. $$

Using this bound together with (3.8), we obtain

$$ T(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \rho, \sigma, \tau)^8 \ll p X^7 Y^{29/4} Z^{29/4} + X^8 Y^8 Z^6. $$

This implies

$$ T(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \rho, \sigma, \tau) \ll p^{1/8} X^{7/8} Y^{29/32} Z^{29/32} + X Y Z^{3/4}. $$

Our final task is to remove the second summand from the upper bound. The second summand dominates the first when $p^4 Z^5 \le X^4 Y^3$ or equivalently $(p/X)^4 \le Y^3/Z^5$. In this range we apply the triangle inequality
and the bilinear estimate (1.2)

$$
\begin{align*}
|T(\mathcal{X}, \mathcal{Y}, \mathcal{Z}; \rho, \sigma, \tau)| &\le p^{1/2} X^{1/2} Y^{1/2} Z \\
&= p^{1/8} X^{7/8} Y^{29/32} Z^{29/32} \left( \frac{p^{12} Z^3}{X^{12} Y^{13}} \right)^{1/32} \\
&\le p^{1/8} X^{7/8} Y^{29/32} Z^{29/32} \left( \frac{1}{Y^4 Z^{12}} \right)^{1/32} \\
&\le p^{1/8} X^{7/8} Y^{29/32} Z^{29/32}.
\end{align*}
$$

3.4. **Proof of Theorem 1.4.** First we permute the variables and write

$$
T(\mathcal{W}, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \vartheta, \rho, \sigma, \tau) = T(\mathcal{Z}, \mathcal{W}, \mathcal{X}, \mathcal{Y}; \tau, \vartheta, \rho, \sigma)
$$

Then, by Lemma 2.10 (with $n=4$) we have

$$
\begin{equation} \tag{3.11}
\begin{split}
& |T(W, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \vartheta, \rho, \sigma, \tau)|^8 \\
& \le (WXY)^6 Z^7 \sum_{w_1,w_2 \in W} \sum_{x_1,x_2 \in \mathcal{X}} \\
& \qquad \left| \sum_{y_1,y_2 \in \mathcal{Y}} \left| \sum_{z \in \mathcal{Z}} e_p(z(w_1-w_2)(x_1-x_2)(y_1-y_2)) \right| \right|.
\end{split}
\end{equation}
$$

We separate the cases where in the argument in the exponential we
have $x_1 = x_2$ or $y_1 = y_2$. Recalling that $W \ge X \ge Y \ge Z$, we see
there are $O(W^2XY^2Z + W^2X^2YZ) = O(W^2X^2YZ)$ such terms, each
contributing 1 to the sum. We can thus rewrite (3.11) as

$$
\begin{align*}
& T(W, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \vartheta, \rho, \sigma, \tau)^8 \\
& \ll (WXY)^6 Z^7 \sum_{w_1,w_2 \in W} \sum_{\substack{x_1,x_2 \in \mathcal{X} \\ x_1 \neq x_2}} \\
& \phantom{\ll (WXY)^6 Z^7 \sum_{w_1,w_2 \in W} \sum_{\substack{x_1,x_2 \in \mathcal{X} \\ x_1 \neq x_2}} } \left| \sum_{\substack{y_1,y_2 \in \mathcal{Y} \\ y_1 \neq y_2}} \left| \sum_{z \in \mathcal{Z}} e_p(z(w_1-w_2)(x_1-x_2)(y_1-y_2)) \right| \right| \\
& \phantom{\ll (WXY)^6 Z^7 \sum_{w_1,w_2 \in W} \sum_{\substack{x_1,x_2 \in \mathcal{X} \\ x_1 \neq x_2}} } + (WXZ)^8 Y^7.
\end{align*}
$$

We now collect together triples $(w_1, w_2, z) \in W^2 \times \mathcal{Z}$ with the same value of the product $z(w_1 - w_2) = \lambda \in \mathbb{F}_p$ and denote by $I(\lambda)$ the number of such triples.

Similarly, we collect together quadruples $(x_1, x_2, y_1, y_2) \in \mathcal{X}^2 \times \mathcal{Y}^2$
with the same value of the product $(x_1 - x_2)(y_1 - y_2) = \mu \in \mathbb{F}_p^*$ and
denote by $J(\mu)$ the number of such quadruples.
Hence we obtain the following version of (3.3)

$$ T(W, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \vartheta, \rho, \sigma, \tau)^8 \\ \ll (WXY)^6 Z^7 \sum_{\mu \in \mathbb{F}_p^*} J(\mu) \left| \sum_{\lambda \in \mathbb{F}_p} I(\lambda) \mathbf{e}_p(\lambda\mu) \right| + (WXZ)^8 Y^7 \\ \ll (WXY)^6 Z^7 \sum_{\mu \in \mathbb{F}_p^*} \sum_{\lambda \in \mathbb{F}_p} J(\mu) \eta_{\mu} I(\lambda) \mathbf{e}_p(\lambda\mu) + (WXZ)^8 Y^7, $$

where $\eta_{\mu}, \mu \in \mathbb{F}_p^*$, is a complex number with $|\eta_{\mu}| = 1$ (which can be expressed via the argument of the inner sum). We note that by Lemma 2.3 and by the assumption $p^{2/3} \ge W \ge X \ge Y \ge Z$,

$$ \sum_{\lambda \in \mathbb{F}_p} I(\lambda)^2 \ll W^3 Z^{3/2} + W^3 Z \ll W^3 Z^{3/2}. $$

Similarly to (3.10) we also have

$$ \sum_{\mu \in \mathbb{F}_p^*} J(\mu)^2 \ll X^{13/4} Y^{13/4}. $$

Therefore, using the bound on bilinear sums (1.2), we obtain

$$ T(W, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \vartheta, \rho, \sigma, \tau)^8 \ll p^{1/2} W^{15/2} (XY)^{61/8} Z^{31/4} + (WXZ)^8 Y^7, $$

which implies

$$ T(W, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \vartheta, \rho, \sigma, \tau) \ll p^{1/16} W^{15/16} (XY)^{61/64} Z^{31/32} + WXY^{7/8} Z. $$

Our final task is to remove the second summand. The process is identical to that at the end of Theorem 1.1 and of Theorem 1.3. The second summand dominates when $p^4 Y^5 \le W^4 X^3 Z^2$. However, in this range we apply the triangle inequality and the bilinear bound (1.2) to obtain

$$ |T(W, \mathcal{X}, \mathcal{Y}, \mathcal{Z}; \vartheta, \rho, \sigma, \tau)| \le p^{1/2} W^{1/2} X^{1/2} Y Z. $$

The condition $p^4 Y^5 \le W^4 X^3 Z^2$ implies

$$ p^{1/2} W^{1/2} X^{1/2} Y Z \le p^{1/16} W^{15/16} (XY)^{61/64} Z^{31/32} $$

and the proof is completed.

## 4. PROOFS OF EXPANSION OF POLYNOMIAL IMAGES

### 4.1. General approach.
Our proof strategy is modeled from that of Garaev [14]. Namely, each time we consider the number of solutions to an appropriately chosen equation and use our new bounds of exponential sums to obtain an asymptotic formula for the number of its solutions. On the other hand, using the specially designed structure of
this equation, we are able to explicitly produce a large family of solutions. Both the asymptotic formula and the size of the family of explicit solutions depend on the cardinalities of the image sets of interest and lead to the desired results.

4.2. **Proof of Theorem 1.5.** We let $\mathcal{E} = \mathbb{F}_p \setminus (\mathcal{A}\mathcal{B}\mathcal{C} + \mathcal{D})$ be of cardinality $E$ and define $N$ as the number of solutions to the equation

$$abc + d - e = 0, \quad (a, b, c, d, e) \in \mathcal{A} \times \mathcal{B} \times \mathcal{C} \times \mathcal{D} \times \mathcal{E},$$

for which we obviously have $N = 0$. On the other hand, using the orthogonality of exponential functions we express $N$ as

$$N = \sum \dots \sum_{(a,b,c,d,e) \in \mathcal{A} \times \mathcal{B} \times \mathcal{C} \times \mathcal{D} \times \mathcal{E}} \frac{1}{p} \sum_{\lambda \in \mathbb{F}_p} \mathbf{e}_p(\lambda(abc + d - e)).$$

Changing the order of summation and separating the term $ABCDE/p$ corresponding to $\lambda = 0$, we obtain

$$N = \frac{ABCDE}{p} + \frac{1}{p} \sum_{\lambda \in \mathbb{F}_p^*} \sum_{(a,b,c) \in \mathcal{A} \times \mathcal{B} \times \mathcal{C}} \mathbf{e}_p(\lambda abc) \sum_{d \in \mathcal{D}} \mathbf{e}_p(\lambda d) \sum_{e \in \mathcal{E}} \mathbf{e}_p(-\lambda e).$$

Hence, applying Theorem 1.1, we derive

$$N - \frac{ABCDE}{p} \ll p^{-3/4} A^{3/4} B^{3/4} C^{7/8} \sum_{\lambda \in \mathbb{F}_p^*} \left| \sum_{d \in \mathcal{D}} \mathbf{e}_p(\lambda d) \right| \left| \sum_{e \in \mathcal{E}} \mathbf{e}_p(\lambda e) \right|.$$

Now applying the Cauchy inequality and then analogues of the orthogonality relation (3.7), we obtain

$$N - \frac{ABCDE}{p}$$

$$ (4.1) \quad \begin{aligned} & \ll p^{-3/4} A^{3/4} B^{3/4} C^{7/8} \left( \sum_{\lambda \in \mathbb{F}_p} \left| \sum_{d \in \mathcal{D}} \mathbf{e}_p(\lambda d) \right|^2 \sum_{\lambda \in \mathbb{F}_p} \left| \sum_{e \in \mathcal{E}} \mathbf{e}_p(\lambda e) \right|^2 \right)^{1/2} \\ & = p^{-3/4} A^{3/4} B^{3/4} C^{7/8} (pD)^{1/2} (pE)^{1/2} \\ & = p^{1/4} A^{3/4} B^{3/4} C^{7/8} D^{1/2} E^{1/2}. \end{aligned} $$

Recalling that $N = 0$ we obtain

$$ABCDE \ll p^{5/4} A^{3/4} B^{3/4} C^{7/8} D^{1/2} E^{1/2},$$

which concludes the proof of the asymptotic formula.

For the lower bound, we consider the number $J(\eta)$ of solutions to the equation

$$abc + d = \eta, \quad (a, b, c, d) \in \mathcal{A} \times \mathcal{B} \times \mathcal{C} \times \mathcal{D}.$$
Clearly

$$ (4.2) \qquad \sum_{\eta \in \mathbb{F}_p} J(\eta) = ABCD. $$

Furthermore, by the Cauchy inequality

$$ (4.3) \qquad \left( \sum_{\eta \in \mathbb{F}_p} J(\eta) \right)^2 \le \#(\mathcal{ABC} + \mathcal{D}) \sum_{\eta \in \mathbb{F}_p} J(\eta)^2 = \#(\mathcal{ABC} + \mathcal{D}) J, $$

where $J$ is the number of solutions to the equation

$$ a_1 b_1 c_1 + d_1 = a_2 b_2 c_2 + d_2, \quad (a_\nu, b_\nu, c_\nu, d_\nu) \in \mathcal{A} \times \mathcal{B} \times \mathcal{C} \times \mathcal{D}, \nu = 1, 2. $$

As before, we write

$$ \begin{aligned} J &= \sum \dots \sum_{(a_\nu, b_\nu, c_\nu, d_\nu) \in \mathcal{A} \times \mathcal{B} \times \mathcal{C} \times \mathcal{D} \atop \nu=1,2} \frac{1}{p} \sum_{\lambda \in \mathbb{F}_p} \mathbf{e}_p \left( \lambda(a_1 b_1 c_1 - a_2 b_2 c_2 + d_1 - d_2) \right) \\ &= \frac{1}{p} \sum_{\lambda \in \mathbb{F}_p} \left| \sum \dots \sum_{(a,b,c) \in \mathcal{A} \times \mathcal{B} \times \mathcal{C}} \mathbf{e}_p (\lambda abc) \right|^2 \left| \sum_{d \in \mathcal{D}} \mathbf{e}_p (\lambda d) \right|^2 \\ &= \frac{A^2 B^2 C^2 D^2}{p} + \frac{1}{p} \sum_{\lambda \in \mathbb{F}_p^*} \left| \sum \dots \sum_{(a,b,c) \in \mathcal{A} \times \mathcal{B} \times \mathcal{C}} \mathbf{e}_p (\lambda abc) \right|^2 \left| \sum_{d \in \mathcal{D}} \mathbf{e}_p (\lambda d) \right|^2. \end{aligned} $$

We now recall Theorem 1.1 and derive

$$ \begin{aligned} J &\ll \frac{A^2 B^2 C^2 D^2}{p} + p^{-1/2} A^{3/2} B^{3/2} C^{7/4} \sum_{\lambda \in \mathbb{F}_p} \left| \sum_{d \in \mathcal{D}} \mathbf{e}_p(\lambda d) \right|^2 \\ &= \frac{A^2 B^2 C^2 D^2}{p} + p^{1/2} A^{3/2} B^{3/2} C^{7/4} D. \end{aligned} $$

Substituting this bound in (4.3) and recalling (4.2) we obtain the desired lower bound.

4.3. **Proof of Theorem 1.7.** We proceed as in the proof of Theorem 1.5.

Let $\mathcal{E} = \mathbb{F}_p \setminus ((\mathcal{A} + \mathcal{B} + \mathcal{C})^3 + \mathcal{D})$ be of cardinality $E$. Then for the number $N$ of solutions to the equation

$$ (a + b + c)^3 + d - e = 0, \quad (a, b, c, d, e) \in \mathcal{A} \times \mathcal{B} \times \mathcal{C} \times \mathcal{D} \times \mathcal{E} $$

we obviously have $N = 0$. On the other hand, using the orthogonality of exponential functions we express $N$ as

$$ N = \sum \dots \sum_{(a,b,c,d,e) \in \mathcal{A} \times \mathcal{B} \times \mathcal{C} \times \mathcal{D} \times \mathcal{E}} \frac{1}{p} \sum_{\lambda \in \mathbb{F}_p} \mathbf{e}_p(\lambda((a+b+c)^3 + d - e)). $$
Changing the order of summation and separating the term $ABCDE/p$ corresponding to $\lambda = 0$, we obtain

$$N = \frac{ABCDE}{p} + \frac{1}{p} \sum_{\lambda \in \mathbb{F}_p^*} \sum_{(a,b,c) \in \mathcal{A} \times \mathcal{B} \times \mathcal{C}} \mathbf{e}_p (\lambda(a+b+c)^3) \sum_{d \in \mathcal{D}} \mathbf{e}_p(\lambda d) \sum_{e \in \mathcal{E}} \mathbf{e}_p(-\lambda e).$$

We now note that the sum over triples $(a, b, c)$ is of the same types as in (1.7) hence Theorem 1.3 applies. Recalling that $N = 0$ we arrive to the bound

$$ABCDE \ll p^{1/8} A^{7/8} B^{29/32} C^{29/32} \sum_{\lambda \in \mathbb{F}_p^*} \left| \sum_{d \in \mathcal{D}} \mathbf{e}_p(\lambda d) \right| \left| \sum_{e \in \mathcal{E}} \mathbf{e}_p(\lambda e) \right|.$$

Now applying the Cauchy inequality and then analogues of (3.7), we obtain

$$\begin{aligned} ABCDE & \ll p^{1/8} A^{7/8} B^{29/32} C^{29/32} (pD)^{1/2} (pE)^{1/2} \\ & = p^{9/8} A^{7/8} B^{29/32} C^{29/32} D^{1/2} E^{1/2}. \end{aligned}$$

The asymptotic formula follows.

For the lower bound, we consider the number $J(\eta)$ of solutions to the equation

$$(a + b + c)^3 + d = \eta, \quad (a, b, c, d) \in \mathcal{A} \times \mathcal{B} \times \mathcal{C} \times \mathcal{D},$$

and again proceed as in the proof of Theorem 1.5 however using Theorem 1.3 instead of Theorem 1.1. In particular, for

$$J = \sum_{\eta \in \mathbb{F}_p} J(\eta)^2$$

we obtain

$$J \ll \frac{A^2 B^2 C^2 D^2}{p} + p^{1/4} A^{7/4} B^{29/16} C^{29/16} D,$$

from which the desired result follows.

4.4. **Proof of Theorem 1.9.** Let $N$ be the number of solutions to the equation

$$(4.4) \qquad u/(bc) + d = v, \quad (b, c, d, u, v) \in \mathcal{B} \times \mathcal{C} \times \mathcal{D} \times \mathcal{U} \times \mathcal{V}.$$

Clearly the quintuples $(b, c, d, abc, a+d)$ with $(a, b, c, d) \in \mathcal{A} \times \mathcal{B} \times \mathcal{C} \times \mathcal{D}$ are pairwise distinct solutions to (4.4). Hence

$$(4.5) \qquad N \geq ABCD.$$
On the other hand, similarly to (4.1), we infer from Theorem 1.1 that

$$ (4.6) \quad N = BCDUV/p + O(p^{1/4}U^{3/4}B^{3/4}C^{7/8}D^{1/2}V^{1/2}). $$

Hence, we see from comparing (4.5) and (4.6), that either

$$ ABCD \ll BCDUV/p $$

or

$$ ABCD \ll p^{1/4}U^{3/4}B^{3/4}C^{7/8}D^{1/2}V^{1/2} $$

and we obtain the result.

## 5. COMMENTS

We now recall a result of Karatsuba [24] (see also [25, Chapter VIII, Problem 9]) that for the character sums in (2.1) we have

$$ \max_{\chi \in \Omega^*} \left| \sum_{\substack{v \in V \\ w \in W}} \chi(v-w) \right| \ll V^{1-1/2r} W q^{1/4r} + V^{1-1/2r} W^{1/2} q^{1/2r}, $$

where the implied constant depends only on the arbitrary parameter $r = 1, 2, \dots$. Used instead of (2.1), this allows us to improve Lemma 2.2 for some ranges of $U, V, W$, however not in ranges which are relevant for our applications to the trilinear sums (1.1).

Furthermore, [33] also contains the bound

$$ D_{\times}(\mathcal{U}) \ll \frac{U^8}{p} + p^{2/3}U^{16/3}, $$

which is better than that of Corollary 2.9 when $U \ge p^{4/7}$. It turns out, however, that in this range applying the classical bound works better.

Finally, we note that some of our bounds can be refined and expressed in terms of $\mathcal{L}^2$-norms of some weights instead of their $\mathcal{L}^{\infty}$-norms.

## ACKNOWLEDGEMENTS

The authors would like to thank Moubariz Garaev and Misha Rudnev for their comments and suggestions. The authors are also very grateful to the referee for the careful reading of the manuscript and valuable comments.

During the preparation of this paper, the first author was supported by the NSF DMS Grant 1500984, the second author was supported by ARC Grant DP140100118.
REFERENCES

[1] E. Aksoy Yazici, B. Murphy, M. Rudnev and I. D. Shkredov, ‘Growth estimates in positive characteristic via collisions’, *Preprint*, 2015 (see http://arxiv.org/abs/1512.06613).

[2] J. Bourgain, ‘Multilinear exponential sums in prime fields under optimal entropy condition on the sources’, *Geom. and Funct. Anal.*, **18** (2009), 1477–1502.

[3] J. Bourgain, ‘On exponential sums in finite fields’, *Bolyai Soc. Math. Stud.*, **21**, János Bolyai Math. Soc., Budapest, 2010, 219–242.

[4] J. Bourgain and M. Z. Garaev, ‘On a variant of sum-product estimates and explicit exponential sum bounds in prime fields’, *Math. Proc. Cambridge Phil. Soc.*, **146** (2009), 1–21.

[5] J. Bourgain, M. Z. Garaev, S. V. Konyagin and I. E. Shparlinski, ‘On congruences with products of variables from short intervals and applications’, *Proc. Steklov Inst. Math.*, **280** (2013), 61–90 (Transl. from *Trudy Mat. Inst. Steklov*).

[6] J. Bourgain and A. Glibichuk, ‘Exponential sum estimates over a subgroup in an arbitrary finite field’, *J. D'Analyse Math.*, **115** (2011), 51–70.

[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. Lond. Math. Soc.*, **73** (2006), 380–398.

[8] J. Bourgain, N. H. Katz and T. Tao, ‘A sum-product estimate in finite fields, and applications’, *Geom. Funct. Anal.*, **14** (2004), 27–57.

[9] M.-C. Chang, ‘On a question of Davenport and Lewis and new character sum bounds in finite fields’, *Duke Math. J.*, **145** (2008), 409–442.

[10] Z. Dvir, ‘Incidence theorems and their applications’, *Foundations and Trends in Theoretical Computer Science*, **6** (2012), 257–393.

[11] G. Elekes and I. Z. Rúzsa, ‘Few sums, many products’, *Studia Sci. Math. Hungar.*, **40** (2003), 301–308.

[12] J. S. Ellenberg and M. Hablicsek, ‘An incidence conjecture of Bourgain over fields of positive characteristic’, *Forum of Mathematics, Sigma*, (to appear).

[13] M. Z. Garaev, ‘An explicit sum-product estimate in $\mathbb{F}_p$’, *Int. Math. Res. Not. IMRN*, **2007** (2007), 1–11.

[14] M. Z. Garaev, ‘The sum-product estimate for large subsets of prime fields’, *Proc. Amer. Math. Soc.*, **136** (2008), 2735–2739.

[15] M. Z. Garaev, ‘Sums and products of sets and estimates of rational trigonometric sums in fields of prime order’, *Russian Math. Surveys*, **65** (2010), 599–658 (Transl. from *Uspekhi Mat. Nauk*).

[16] L. Guth, *Polynomial methods in combinatorics*, Amer. Math. Soc., Providence, RI, 2016.

[17] L. Guth and N. H. Katz, ‘Algebraic methods in discrete analogs of the Kakeya problem’, *Adv. Math.*, **225** (2010), 2828–2839.

[18] L. Guth and N. H. Katz, ‘On the Erdős distinct distances problem in the plane’, *Ann. of Math.* **181** (2015), 155–190.

[19] B. Hanson, ‘Estimates for characters sums with various convolutions’, *Preprint*, 2015 (see http://arxiv.org/abs/1509.04354).

[20] N. Hegyvári, ‘Some remarks on multilinear exponential sums with an application’, *J. Number Theory*, **132** (2012), 94–102.
[21] H. Helfgott and M. Rudnev, 'An explicit incidence theorem in $\mathbb{F}_p$, *Mathe- matika*, **57** (2011), 135–145.

[22] H. Iwaniec and E. Kowalski, *Analytic number theory*, Amer. Math. Soc., Providence, RI, 2004.

[23] T. G. F. Jones, 'An improved incidence bound for fields of prime order', *European J. Combin.*, **52** (2016), 136–145.

[24] A. A. Karatsuba, 'The distribution of values of Dirichlet characters on additive sequences', *Doklady Acad. Sci. USSR*, **319** (1991), 543–545 (in Russian).

[25] A. A. Karatsuba, *Basic analytic number theory*, Springer-Verlag, Berlin, 1993.

[26] N. H. Katz, 'The flecnode polynomial: A central object in incidence geometry', *Preprint*, 2014 (see https://arxiv.org/abs/1404.3412).

[27] N. H. Katz and C.-Y. Shen, 'A slight improvement to Garaev's sum product estimate', *Proc. Amer. Math. Soc.*, **136** (2008), 2499–2504.

[28] J. Kollár, 'Szemerédi–Trotter-type theorems in dimension 3', *Adv. Math.*, **271** (2015), 30–61.

[29] L. Li, 'Slightly improved sum-product estimates in fields of prime order', *Acta Arith.* **147** (2011), 153–160.

[30] B. Murphy, G. Petridis, O. Roche-Newton, M. Rudnev and I. D. Shkredov, 'New results on sum-product type growth over fields', *Preprint*, 2017 (see http://arxiv.org/abs/1702.01003).

[31] L. Li and O. Roche-Newton, 'An improved sum-product estimate for general finite fields' *SIAM J. Discrete Math.* **25** (2011), 1286–1296.

[32] A. Ostafe, 'Polynomial values in affine subspaces over finite fields', *J. D'Analyse Math.*, (to appear).

[33] G. Petridis, 'Products of differences in prime order finite fields', *Preprint*, 2016 (see http://arxiv.org/abs/1602.02142).

[34] H. Pottmann and J. Wallner, *Computational line geometry*, Springer-Verlag, Berlin, 2001.

[35] O. Roche-Newton and M. Rudnev, 'On the Minkowski distances and products of sum sets', *Israel J. Math.*, **209** (2015), 507–526.

[36] O. Roche-Newton, M. Rudnev and I. D. Shkredov, 'New sum-product type estimates over finite fields', *Adv. Math.*, **293** (2016), 589–605.

[37] M. Rudnev, 'An improved sum-product inequality in fields of prime order', *Int. Math. Res. Not.* **IMRN**, **2012** (2012), 3693–3705.

[38] M. Rudnev, 'On the number of incidences between planes and points in three dimensions', *Combinatorica*, (to appear).

[39] M. Rudnev and J. M. Selig, 'On the use of the Klein quadric for geometric incidence problems in two dimensions', *SIAM J. Discrete Math.*, **30** (2016), 934–954.

[40] M. Rudnev, I. D. Shkredov and S. Stevens, 'On the energy variant of the sum-product conjecture', *Preprint*, 2016 (see http://arxiv.org/abs/1607.05053).

[41] A. Sárközy, 'On sums and products of residues modulo $p$, *Acta Arith.*, **118** (2005), 403–409.

[42] I. D. Shkredov, 'Difference sets are not multiplicatively closed', *Preprint*, 2016 (see http://arxiv.org/abs/1602.02360).
[43] I. D. Shkredov and A. S. Volostnov, ‘Sums of multiplicative characters with additive convolutions’, *Preprint*, 2016 (see http://arxiv.org/abs/1606.00358).

[44] I. E. Shparlinski, ‘On the solvability of bilinear equations in finite fields’, *Glasgow Math. J.*, **50** (2008), 523–529.

[45] E. Szemerédi and W. T. Trotter, ‘Extremal problems in discrete geometry’, *Combinatorica*, **3** (1983), 381–392.

[46] T. Tao and V. Vu, *Additive combinatorics*, Cambridge Stud. Adv. Math., **105**, Cambridge University Press, Cambridge, 2006.

DEPARTMENT OF MATHEMATICS, UNIVERSITY OF GEORGIA, ATHENS, GA 30602, USA

E-mail address: giorgis@cantab.net

DEPARTMENT OF PURE MATHEMATICS, UNIVERSITY OF NEW SOUTH WALES, SYDNEY, NSW 2052, AUSTRALIA

E-mail address: igor.shparlinski@unsw.edu.au