# Small Sets with Large Difference Sets

Luka Milićević E-mail address<EMAIL_ADDRESS>Department of Pure Mathematics
and Mathematical Statistics
Wilberforce Road
Cambridge CB3 0WB
UK

###### Abstract

For every $\epsilon>0$ and $k\in\mathbb{N}$, Haight constructed a set
$A\subset\mathbb{Z}_{N}$ ($\mathbb{Z}_{N}$ stands for the integers modulo $N$)
for a suitable $N$, such that $A-A=\mathbb{Z}_{N}$ and $|kA|<\epsilon N$.
Recently, Nathanson posed the problem of constructing sets
$A\subset\mathbb{Z}_{N}$ for given polynomials $p$ and $q$, such that
$p(A)=\mathbb{Z}_{N}$ and $|q(A)|<\epsilon N$, where $p(A)$ is the set
$\\{p(a_{1},a_{2},\dots,a_{n})\colon a_{1},a_{2},\dots,a_{n}\in A\\}$, when
$p$ has $n$ variables. In this paper, we give a partial answer to Nathanson’s
question. For every $k\in\mathbb{N}$ and $\epsilon>0$, we find a set
$A\subset\mathbb{Z}_{N}$ for suitable $N$, such that $A-A=\mathbb{Z}_{N}$, but
$|A^{2}+kA|<\epsilon N$, where
$A^{2}+kA=\\{a_{1}a_{2}+b_{1}+b_{2}+\dots+b_{k}\hskip
2.0pt\colon\vspace{2pt}a_{1},a_{2},b_{1},\dots,b_{k}\in A\\}$. We also extend
this result to construct, for every $k\in\mathbb{N}$ and $\epsilon>0$, a set
$A\subset\mathbb{Z}_{N}$ for suitable $N$, such that $A-A=\mathbb{Z}_{N}$, but
$|3A^{2}+kA|<\epsilon N$, where
$3A^{2}+kA=\\{a_{1}a_{2}+a_{3}a_{4}+a_{5}a_{6}+b_{1}+b_{2}+\dots+b_{k}\hskip
2.0pt\colon\vspace{2pt}a_{1},\dots,a_{6},b_{1},\dots,b_{k}\in A\\}$.

00footnotetext: 2010 Mathematics Subject Classification: 11B13; 11P99

##  1 Introduction

The problem of comparing different expressions involving the same subset $A$
of an abelian group $G$ (e.g. $A+A$ and $A-A$) is one of the central topics in
additive combinatorics. For example, one of the starting points in the study
of this field is the Plünnecke-Ruzsa inequality that bounds $|kA-lA|$ in terms
of $|A|$ and $|A+A|$.

######  Theorem 1.1.

(Plünnecke-Ruzsa inequality, [10], [12]) Let $A$ be a subset of an abelian
group. Then, for any $k,l\geq 1$ we have

$|kA-lA||A|^{k+l-1}\leq|A+A|^{k+l}.$

To illustrate the difficulties in determining the right bounds for such
inequalities, we note that even for the comparison of $|A+A|$ and $|A-A|$ the
right exponents are not known. In fact, the best known lower bounds for
$|A+A|$ in terms of $|A-A|$ have not changed for more than 40 years.

######  Theorem 1.2 (Freiman, Pigaev; Ruzsa, [3], [11]).

Let $A$ be a subset of an abelian group. Then $|A-A|^{3/4}\leq|A+A|$.

In the opposite direction, the best known lower bound is given by the
following result.

######  Theorem 1.3 (Hennecart, Robert, Yudin, [7]).

There exist arbitrarily large sets $A\subset\mathbb{Z}$ such that
$|A+A|\leq|A-A|^{\alpha+o(1)}$, where
$\alpha\colon=\log(2)/\log(1+\sqrt{2})\approx 0.7864$.

In 1973, Haight [6] found for each $k$ and $\epsilon>0$, an integer $q$ and a
set $A\subset\mathbb{Z}_{q}$ such that $A-A=\mathbb{Z}_{q}$ and
$|kA|\leq\epsilon q$. Recently, Ruzsa [13] gave a similar construction, and
observed that Haight’s work even gives a constant $\alpha_{k}>0$ for each $k$
with the property that there are arbitrarily large $q$ with sets
$A\subset\mathbb{Z}_{q}$ such that $A-A=\mathbb{Z}_{q}$ and $|kA|\leq
q^{1-\alpha_{k}}$. The ideas in both constructions are relatively similar, but
Ruzsa’s argument is cosiderably more concise.

In [9], Nathanson applied Ruzsa’s method to construct sets $A\subset R$ with
$A-A=R$, but $kA$ small, for rings $R$ that are more general than
$\mathbb{Z}_{q}$. In the same paper, he posed the following more general
question. Given a polynomial $F(x_{1},x_{2},\dots,x_{n})$ with coefficients in
$\mathbb{Z}$, and a set $A\subset\mathbb{Z}_{N}$, write
$F(A)=\\{F(a_{1},a_{2},\dots,a_{n})\colon a_{1},\dots,a_{n}\in A\\}$. His
question can be stated as: given two polynomials $F,G$ over $\mathbb{Z}$ and
$\epsilon>0$, does there exist arbitrarily large $N$ and a set
$A\subset\mathbb{Z}_{N}$ such that $F(A)=\mathbb{Z}_{N}$, but $|G(A)|<\epsilon
N$?111Actually, Nathanson poses this question for more general rings $R$, but
for $R=\mathbb{Z}$, the formulation we give here is a natural one.

Let us now state the main result of this paper, which answers the first
interesting cases of Nathanson’s question. Once again we recall the notation

$A^{2}+kA=\\{a_{1}a_{2}+a^{\prime}_{1}+a^{\prime}_{2}+\dots+a^{\prime}_{k}\hskip
2.0pt\colon\vspace{2pt}a_{1},a_{2},a^{\prime}_{1},\dots,a^{\prime}_{k}\in
A\\},$

and more generally,

$lA^{2}+kA=\\{a_{1}a_{2}+\dots+a_{2l-1}a_{2l}+a^{\prime}_{1}+a^{\prime}_{2}+\dots+a^{\prime}_{k}\hskip
2.0pt\colon\vspace{2pt}a_{1},a_{2},\dots,a_{2l},a^{\prime}_{1},\dots,a^{\prime}_{k}\in
A\\}.$

######  Theorem 1.4.

Given $k\in\mathbb{N}_{0}$ and any $\epsilon>0$, there is a natural number $q$
and a set $A\subset\mathbb{Z}_{q}$ such that

$A-A=\mathbb{Z}_{q},\text{ but }|A^{2}+kA|\leq\epsilon q.$

In fact we prove rather more.

######  Theorem 1.5.

For $l\in\\{1,2,3\\}$, any $k\in\mathbb{N}_{0}$ and any $\epsilon>0$, there is
a natural number $q$ and a set $A\subset\mathbb{Z}_{q}$ such that

$A-A=\mathbb{Z}_{q},\text{ but }|lA^{2}+kA|<\epsilon q.$

Moreover, we can take $q$ to be a product of distinct primes, and we can take
the smallest prime dividing $q$ to be arbitrarily large.

We shall discuss each of the cases $l=1,2,3$ separately. Note also an
interesting phenomenon in the opposite direction. Namely, if we are not
allowed freedom in the choice of the modulus, a statement like the theorem
above cannot hold. The reason is that, by the result of Glibichuk and Rudnev
(Lemma 1 in [4]) whenever $A\subset\mathbb{F}_{p}$ for a prime $p$, is a set
of size at least $|A|>\sqrt{p}$, then $10A^{2}=\mathbb{F}_{p}$ (and
$A-A=\mathbb{F}_{p}$ certainly implies $|A|>\sqrt{p}$). Hence, unlike the
linear case, already for quadratic expressions we have strong obstructions.

In fact, this problem is comparable in spirit to sum-product phenomenon, which
can be stated as the following theorem.

######  Theorem 1.6.

(Bourgain, Katz, Tao [2], Sum-product estimate.) Let $\delta>0$ be given. Then
there is $\epsilon>0$ such that whenever $A\subset\mathbb{Z}_{q}$ for a prime
$q$ satisfies

$q^{\delta}<|A|<q^{1-\delta},$

then one has

$\max\\{|A^{2}|,|2A|\\}\geq|A|^{1+\epsilon}.$

This was further generalized to arbitrary modulus $q$.

######  Theorem 1.7.

(Bourgain [1], Sum-product estimate for composite moduli.) Given
$q,q^{\prime}$ such that $q^{\prime}|q$, write $\pi_{q^{\prime}}$ for the
natural projection from $\mathbb{Z}_{q}\to\mathbb{Z}_{q^{\prime}}$.
Let $\delta>0$ be given. We then have $\epsilon,\eta>0$ such that the
following holds. Whenever $A\subset\mathbb{Z}_{q}$ satisfies

$|A|\leq q^{1-\delta}$

and,

$|\pi_{q^{\prime}}(A)|\geq{q^{\prime}}^{\delta}\text{ for all
}q^{\prime}|q,\text{ with }q^{\prime}\geq q^{\eta},$

then

$\max\\{|A^{2}|,|2A|\\}\geq|A|^{1+\epsilon}.$

Hence, the sum-product phenomenon still holds in general $\mathbb{Z}_{N}$,
even when N is composite, and given the similarity of our problem, it could
well be that the result of Glibichuk and Rudnev stated above holds in the more
general setting as well. (Note that if $A-A=\mathbb{Z}_{q}$, then it satisfies
the technical condition in Theorem 1.7.)

######  Conjecture 1.8.

There is $l$ such that whenever $A\subset\mathbb{Z}_{q}$ and
$A-A=\mathbb{Z}_{q}$, then we have $lA^{2}+lA=\mathbb{Z}_{q}$.

###  1.1 Acknowledgements

I would like to thank Trinity College Cambridge and the Department of Pure
Mathematics and Mathematical Statistics of Cambridge University for their
generous support, and Imre Leader for encouragement and helpful discussions
concerning this paper.

##  2 Overview of the Construction

We begin the paper by reviewing Ruzsa’s construction and generalizing its main
ideas slightly to the context of polynomial expressions in $A$. As it turns
out, to be able to construct a set $A$ such that $A-A=\mathbb{Z}_{q}$, but
$|lA^{2}+kA|=o(q)$, it will suffice to consider expressions which are sums of
terms of the form $\alpha_{i}(x_{i})+cx_{i}$,
$(\alpha_{i}(x_{i})+cx_{i})(\alpha_{i}(x_{i})+c^{\prime}x_{i})$ and
$(\alpha_{i}(x_{i})+cx_{i})(\alpha_{j}(x_{j})+c^{\prime}x_{j})$, with
$c,c^{\prime}\in\\{0,1\\}$ and then choose the maps so that the number of
values attained by each expression is small. For example, one of the
expressions that we have to consider already for the case $l=1$ is
$\alpha_{1}(x_{1})\alpha_{2}(x_{2})+\alpha_{1}(x_{1})+x_{1}+\alpha(x_{3})$.
This discussion takes place in Section 3 and the rest of the paper is devoted
to constructions of maps for various expressions.

In Section 4, we construct sets $A$ such that $A-A=\mathbb{Z}_{q}$ but
$A^{2}+kA$ is small. In this construction, we come to a basic version of one
of the main ideas, which we call the _identification of coordinates_. Very
roughly, if $q$ is a product of distinct prime $p_{1}p_{2}\dots p_{n}$, using
approximate homomorphisms between $\mathbb{Z}_{p_{i}}$ and
$\mathbb{Z}_{p_{j}}$, we can essentially treat $\mathbb{Z}_{q}$ as a vector
space of dimension $n$. Then, altough we might not ensure that each coordinate
attains few values, we can ensure that their sum attains few values.

In Section 5, we construct sets $A$ such that $A-A=\mathbb{Z}_{q}$ but
$2A^{2}+kA$ is small. There, we improve our results for the expression that
involve a single variable using a variant of Weyl’s equidistribution theorem
for polynomials. Using this result, the identification of coordinates is
developped further and we conclude this section with the strongest form of
identification of coordinates.

The final part of the construction, finding sets $A$ with $3A^{2}+kA$ small,
is carried out in Section 6. There, we also touch upon some limitations of the
usual approach and therefore develop different ideas to treat some of the
remaining expressions. Namely, for certain choices of coefficients, in the
expression

$(\alpha(x)+c_{1}x)(\beta(y)+c_{2}y)+(\alpha(x)+c_{3}x)(\beta(y)+c_{4}y)+(\alpha(x)+c_{5}x)(\gamma(z)+c_{6}z)$

the identification of coordinates cannot work. For this expression, we give a
different, probabilistic argument.

The final section is devoted to some open problems and questions that
naturally arise, including the motivation for some of these. We have tried to
organize the paper so that methods used naturally develop from the case
$A^{2}+kA$ to the case $3A^{2}+kA$, highlighting the new difficulties that
arise and why the earlier arguments are not powerful enough for the later
expressions.

##  3 Overview of Ruzsa’s argument and Initial Steps

We now briefly discuss Ruzsa’s construction of sets $A\subset\mathbb{Z}_{q}$
such that $A-A=\mathbb{Z}_{q}$, but $|kA|=o(q)$. His ideas will be important
for the later constructions given in this paper.
Let us first analyse the requirement that $A-A=\mathbb{Z}_{q}$. Given any
$x\in\mathbb{Z}_{q}$, we thus have $y\in A$ such that $y+x\in A$. If we write
$\varphi(x)$ for such a $y$, this yields a map
$\varphi:\mathbb{Z}_{q}\to\mathbb{Z}_{q}$ with the property that all
$\varphi(x)$ and $\varphi(x)+x$ are contained in $A$. Removing all other
elements from $A$ does not change the equality $A-A=\mathbb{Z}_{q}$, and it
can only make $kA$ smaller, so Ruzsa’s starting point is to consider a set $A$
of the form

$\\{\varphi(x):x\in\mathbb{Z}_{q}\\}\cup\\{\varphi(x)+x:x\in\mathbb{Z}_{q}\\},$

where $\varphi$ is map from $\mathbb{Z}_{q}$ to itself. We shall do the same
in this paper as well, and throughout the paper we will devote ourselves to
finding suitable modulus $q$ and maps on $\mathbb{Z}_{q}$.

Thus, we have to understand how to find a suitable $q$ and a map $\varphi$
which then give rise to the desired set $A$. Let us now examine the elements
of $kA$. These are sums $a_{1}+a_{2}+\dots+a_{k}$, where $a_{i}\in A$. But
each element of $A$ is either $\varphi(x)$ or $\varphi(x)+x$ for some
$x\in\mathbb{Z}_{q}$. Hence, elements of $kA$ are of the form

$\sum_{i\in I}\varphi(x_{i})+\sum_{i\notin I}(\varphi(x_{i})+x_{i})$

for a subset $I\subset[k]$ and $x_{1},x_{2},\dots,x_{k}$. Immediately we see
that the number of different expressions here is bounded in terms of $k$ (in
fact, it equals $2^{k}$). Further, we consider which of the $x_{i}$ are equal,
grouping the corresponding terms $\varphi(x_{i})$ and $\varphi(x_{i})+x_{i}$
together, and renaming the variables along the path to
$y_{1},y_{2},\dots,y_{s}$. Hence, every element of $kA$ is of the form

$\sum_{i=1}^{s}(a_{i}\varphi(y_{i})+b_{i}y_{i}),$ (1)

where $s\leq k$, $k\geq a_{i}\geq b_{i}\geq 0$ and all $y_{1},\dots,y_{s}$ are
different. Once again, treating $y_{i}$ as formal variables, the number of
expressions we wrote is bounded in terms of $k$. The plan now is to make sure
that each such expression attains a small number of values, so that in total
only at most $\epsilon q$ values attained.

Ruzsa’s main idea in the costruction is the _separation of functions_ , which
we now discuss. In all these expressions we have the same map $\varphi$
occuring. However, we can turn the problem of constructing a single function
$\varphi$ that works for all expressions into a much easier problem of
constructing a function for each expression separately. We first list all the
expressions of the form (1), sorted in the asscending order by the number of
variables appearing. Thus, our list start from expressions of the form
$a\varphi(y)+b$. Next, we split $q$ as a product of coprime numbers
$q=q_{1}q_{2}\dots q_{r}$, with one $q_{i}$ for each expression so that by
Chinese Remainder Theorem we have
$\mathbb{Z}_{q}=\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{2}}\oplus\dots\oplus\mathbb{Z}_{q_{r}}$.

We promise that however we choose an expression and values of $y_{i}$, we get
at least one zero coordinate (which need not depend on the expression) and we
call this ZCP (Zero Coordinate Promise). If $i$-th expression has only one
variable appearing, thus it is of the form $a\varphi(y)+by$, we can easily
ensure ZCP by setting the $i$-th component of the function as
$\varphi_{i}(y)=-ba^{-1}y_{i}$. Now, take any expression

$\sum_{i=1}^{s}(a_{i}\varphi(y_{i})+b_{i}y_{i}),$

and assume that for every such expression with fewer than $s$ variables ZCP
holds. Let $q^{\prime}$ be the product of $q_{i}$ for the expressions with
fewer than $s$ variables. Note that, if we are given
$y_{1},y_{2},\dots,y_{s}$, and if any two among them have the same value in
$\mathbb{Z}_{q^{\prime}}$, by induction hypothesis, ZCP already holds. Hence,
we may assume not only that $y_{1},y_{2},\dots,y_{s}$ are different, but that
they are different modulo $q^{\prime}$. Write $y^{\prime}_{i}$ for the residue
of $y_{i}$ mod $q^{\prime}$. Then, looking at $j^{\text{th}}$ coordinate, we
have to define $\varphi_{j}$ such that

$\sum_{i=1}^{s}(a_{i}\varphi_{j}(y^{\prime}_{i},(y_{i})_{j})+b_{i}(y_{i})_{j})$

equals zero for all choices of $y_{1},\dots,y_{s}$ such that $y^{\prime}_{i}$
are different. But, we can rewriting $\varphi_{j}(y^{\prime}_{i},(y_{i})_{j})$
as $\varphi_{j,y^{\prime}_{i}}((y_{i})_{j})$ already tells us that we are
actually looking for a new function for each variable! Hence, our goal is to
find $s$ functions
$\varphi_{j,y^{\prime}_{1}},\dots\varphi_{j,y^{\prime}_{s}}$ such that the
expression is once again zero. But linear maps once again work.

We start our own work in this paper by slightly generalizing Ruzsa’s idea to
polynomial setting. In what follows, by an _$i$ -degree term_ we think of a
product of $i$ terms of the from $\alpha_{j}(x_{j})$ or
$(\alpha_{j}(x_{j})+x_{j})$, the only rule being that indices of the map and
variable to which it is applied (and which is possibly added) coincide. For
example, $(\alpha_{1}(x_{1})+x_{1})\alpha_{2}(x_{2})^{2}$ and
$\alpha_{1}(x_{1})(\alpha_{2}(x_{2})+x_{2})(\alpha_{3}(x_{3})+x_{3})$ are both
$3$-degree terms, but $\alpha_{1}(x_{2})\alpha_{2}(x_{3})\alpha_{3}(x_{1})$ is
not, since the indices are not valid.

######  Proposition 3.1.

Let $k$ be given, and let $a_{1},a_{2},\dots,a_{k}\in\mathbb{N}$. Suppose that
for every $\epsilon>0$ and every formal expression $E$ in functions
$\alpha_{i}$ and variables $x_{i}$ of the form

$\text{sum of }a_{k}\text{of }k\text{-degree terms}+\text{sum of
}a_{k-1}\text{of }(k-1)\text{-degree terms}+\dots+\text{sum of }a_{1}\text{of
}1\text{-degree terms},$

we can find a modulus $q$, which is a product of arbitrarily large distinct
primes, and functions $\theta_{i}:\mathbb{Z}_{q}\to\mathbb{Z}_{q}$, so that
the $E$ takes at most $\epsilon q$ values in $\mathbb{Z}_{q}$, when the
functions $\theta_{i}$ are substituted in $E$. Then, for every $\epsilon>0$,
there is a modulus $Q$, product of arbitrarily large distinct primes, and a
set $A\subset\mathbb{Z}_{Q}$ such that $A-A=\mathbb{Z}_{Q}$ and

$|a_{k}A^{k}+a_{k-1}A^{k-1}+\dots+a_{1}A|\leq\epsilon Q.$

###### Proof.

We proceed as in the Ruzsa’s construction (except that we do not insist of
only having zero value in a coordinate, small number of values suffices). As
before, we sort the expressions by the number of variables appearing, and
process them in groups of those having the same number of a variables. We now
turn to details.

Let $N=a_{1}+a_{2}+\dots+a_{k}$. Let $E_{1},E_{2},\dots,E_{r}$ be all the
expressions in variables $y_{1},y_{2},\dots,y_{N}$ of the following form. Each
expression is a sum of $a_{k}$ terms, each being a product of $k$ short terms
$\varphi(y_{i})$ or $\varphi(y_{i})+y_{i}$, followed by $a_{k-1}$ terms which
are products of $k-1$ short terms, etc. with a final contribution of $a_{1}$
terms, each being $\varphi(y_{i})$ or $\varphi(y_{i})+y_{i}$. As in the
discussion before, these are all expressions that naturally arise from
$a_{k}A^{k}+\dots+a_{1}A$, when $A$ is defined as $\\{\varphi(x)\colon
x\in\mathbb{Z}_{Q}\\}\cup\\{\varphi(x)+x\colon x\in\mathbb{Z}_{Q}\\}$.
Comparing these expressions with the expressions in the assumptions of this
proposition, we have that here only a single formal function appears, while in
the other expressions we have a separate function for each variable. Let
$m_{0}=0,m_{1},m_{2},\dots,m_{N}=r$ be indices such that if $m_{i}<j\leq
m_{i+1}$, then the number of different variables among $(y_{t})_{t=1}^{N}$
appearing in the expression $E_{j}$ is exactly $i+1$.

Fix an increasing sequence
$0<\epsilon_{1}<\epsilon_{2}<\dots<\epsilon_{N}=\epsilon$. We inductively
construct moduli $Q_{1},Q_{2},\dots,Q_{N}$ and functions $\varphi_{i}:Q_{i}\to
Q_{i}$ such that for every $i\leq N$ we have that union of all images of
expressions $E_{1},E_{2},\dots,E_{m_{i}}$ (that is all expressions futuring at
most $i$ variables) takes at most $\epsilon_{i}Q_{i}$ values (when
$\varphi_{i}$ is substituted in the expressions).

Base case: $i=1$. By the assumption, for every expression $E_{i}$ that has
only one variable, we have moduli $q_{i}$ with arbitrarily large distinct
prime factors, and a map $\theta^{(1)}_{i}$, such that $E_{i}$ takes only at
most $\epsilon_{1}q_{i}/{m_{1}}$ values. Thus, w.l.o.g.
$q_{1},q_{2},\dots,q_{m_{1}}$ are all coprime, with distinct arbitrarily large
prime factors. We set $Q_{1}=q_{1}q_{2}\dots q_{m_{1}}$ and identify
$\mathbb{Z}_{Q_{1}}$ with
$\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{2}}\oplus\dots\oplus\mathbb{Z}_{q_{m_{1}}}$,
and we define $\varphi_{1}$ coordinate-wise as
$\varphi_{1,i}(x):=\theta^{(1)}_{i}(x_{i})$, where $x_{i}$ is $i$-th
coordinate of $x$. Note that union of all values attained by these $m_{1}$
expressions with this definition of $Q_{1}$ and $\varphi_{1}$ has size bounded
by

$\sum_{i=1}^{m_{1}}|\operatorname{Im}E_{i}|\leq\sum_{i=1}^{m_{1}}\frac{\epsilon_{1}q_{i}}{m_{1}}\frac{Q_{1}}{q_{i}}=\epsilon_{1}Q_{1},$

as desired. (Here we write $\operatorname{Im}E_{i}$ for the resulting image of
the expression $E_{i}$, and we have a trivial bound for it – the expression
may only take at most $\epsilon_{1}q_{i}/m_{1}$ values on the $i^{\text{th}}$
coordinate.)

Inductive step. Suppose now that we have found
$\varphi_{s}:\mathbb{Z}_{Q_{s}}\to\mathbb{Z}_{Q_{s}}$ such that in total all
expressions with at most $s$ variables have a small image $V_{s}$, i.e. only
at most $\epsilon_{s}Q_{s}$ values are attained. We shall construct $Q_{s+1}$
as a product $Q_{s}R_{m_{s}+1}R_{m_{s}+2}\dots R_{m_{s+1}}$, where $R_{i}$ is
an auxiliary modulus for the expression $E_{i}$, with the property that either
$E_{i}$ takes one of the small number of values on $\mathbb{Z}_{Q_{s}}$ or a
value in another small set in $\mathbb{Z}_{R_{i}}$. Here we use Ruzsa’s
_separation of functions_ idea.
Fix an expression $E_{i}$ with exactly $s+1$ variables. If we take values of
these variables restricted to $\mathbb{Z}_{Q_{s}}$, and it happens so that at
least two such values coincide, then using the map $\varphi_{s}$ the value of
the expression $E_{i}$ (also restricted to $\mathbb{Z}_{Q_{s}}$) is actually a
value of one of the expressions we already considered, with at most $s$
variables, so it lies in the small set $V_{s}$. Hence, we only need to
consider the choices of $y_{1},y_{2},\dots,y_{s+1}$ (w.l.o.g. these are the
variables that appear) which differ in $\mathbb{Z}_{Q_{s}}$. We split the
expression $E_{i}$ further into cases on $y_{i}$ mod $Q_{s}$, thus into
further $L\leq Q_{s}^{s+1}$ cases. Pick an arbitrary choice $C$ of $s+1$
distinct values in $Q_{s}$. Look back at $E_{i}$ and change every appearance
of $\varphi(y_{t})$ by $\alpha_{t}(y_{t})$. By assumptions, we have a choice
of an integer $r_{C}$ with arbitrarily large distinct prime factors and maps
$\theta^{(C)}_{t}$ such that the modified $E_{i}$ takes only at most
$(\epsilon_{s+1}-\epsilon_{s})r_{C}/((m_{s+1}-m_{s})Q_{s}^{s+1})$ values in
$\mathbb{Z}_{r_{C}}$. Finally, define $R_{i}$ as the product of all these
$r_{C}$, and $(\varphi_{s+1})_{i}(x)$ as follows: for every $C$, take
$(\varphi_{s+1})_{i}(x)$ at the coordinate corresponding to $r_{C}$ to be zero
if $x$ modulo $\mathbb{Z}_{Q_{s}}$ is not in $C$, otherwise, if it is the
$j$-th residue, set $(\varphi_{s+1})_{i}(x):=\theta^{(C)}_{j}(x^{\prime})$,
where $x^{\prime}$ is the coordinate of $x$ corresponding to $r_{C}$. It
remains to check the size of images.
For every expression and every choice of values of $y_{1},y_{2},\dots,y_{N}$,
we either end up in
$A_{s}\times\mathbb{Z}_{R_{m_{s}+1}}\times\mathbb{Z}_{R_{m_{s}+2}}\times\dots\times\mathbb{Z}_{R_{m_{s+1}}}$,
which has size at most $\epsilon_{s}Q_{s+1}$, or one of the coordinates is in
a fixed subset of $\mathbb{Z}_{R_{t}}$ of size at most
$(\epsilon_{s+1}-\epsilon_{s})R_{t}/(m_{s+1}-m_{s})$. Summing everything
together, the image has at most $\epsilon_{s+1}Q_{s+1}$ values as desired.∎

The rest of the paper is therefore devoted to finding moduli $q$ and maps
$\alpha_{i}\colon\mathbb{Z}_{q}\to\mathbb{Z}_{q}$ under which the expressions
like
$(\alpha_{1}(x_{1})+x_{1})(\alpha_{2}(x_{2})+x_{2})+\alpha_{3}(x_{3})^{2}$ do
not take too many values. Along the way, we also discuss related problems and
questions.

Notation. Throughout the paper, greek letters $\alpha,\beta$ and $\gamma$ will
be used for the maps appearing in the expressions. The following functions
will be frequently used in our construction. For a prime $p$, we use the
standard projection homomorphism $\pi_{p}\colon\mathbb{Z}\to\mathbb{Z}_{p}$,
which sends integer $x$ to $x+p\mathbb{Z}$. Next, we define
$\iota_{p}\colon\mathbb{Z}_{p}\to\mathbb{Z}$ by sending $x\in\mathbb{Z}_{p}$
to the integer $\iota_{p}(x)\in\\{0,1,\dots,p-1\\}\subset\mathbb{Z}$ such that
$\pi_{p}\circ\iota_{p}(x)=x$. For two primes $p$ and $q$, we also define the
map $\operatorname{mod}_{p,q}\colon\mathbb{Z}_{p}\to\mathbb{Z}_{q}$ given by
$\operatorname{mod}_{p,q}=\pi_{q}\circ\iota_{p}$. Finally, in any abelian
group $Z$, and functions $f,g\colon S\to G$, from a set $S$ to $Z$, we write
$f\overset{M}{=}g$ to mean that $\\{f(s)-g(s)\colon s\in S\\}$ is a set of
size at most $M$. In particular, $f\overset{O(1)}{=}g$ means that
$\\{f(s)-g(s)\colon s\in S\\}$ has a bounded size as $S$ grows.

##  4 Sets $A$ with small $A^{2}+kA$

The main result of this section is the case $l=1$ of the Theorem 1.5.

######  Theorem 4.1.

For any $k\in\mathbb{N}_{0}$ and any $\epsilon>0$, there is a natural number
$q$, which is a product of distinct, arbitrarily large primes, and a set
$A\subset\mathbb{Z}_{q}$ such that $A-A=\mathbb{Z}_{q}$, while
$|A^{2}+kA|<\epsilon q$.

###### Proof.

We start from the Proposition 3.1. To be able to construct
$A\subset\mathbb{Z}_{q}$ with full difference set, but small $A^{2}+kA$, we
need to handle the expressions that are sums of the _quadratic part_ which is
a product of two terms of the form $\alpha_{i}(x_{i})+x_{i}$ or
$\alpha_{i}(x_{i})$, and a _linear part_ which is itself a sum of $k$
summands, each being of the form $\alpha_{i}(x_{i})+x_{i}$ or
$\alpha_{i}(x_{i})$. Note that for the terms in the linear part whose
variables do not appear in the quadratic part, we can define the corresponding
maps $\alpha_{i}$ to be affine so that the variables involved cancel out.
Therefore, w.l.o.g. we only consider expressions whose variables appear
already in the quadratic part. Note also that for the quadratic part we have
two cases: either only one variable, w.l.o.g. $x_{1}$, appears, or exactly two
variables, w.l.o.g. $x_{1}$ and $x_{2}$, appear. We treat these cases
separately.

Case 1: only one variable in the quadratic part. Thus, our goal now is to show
that if we are given a quadratic expression featuring only one variable, we
can find a modulus and function, so that the expression takes a small number
of values. In fact, here we do more and prove the claim for expressions of
arbitrary degree.

######  Lemma 4.2.

Let $d\in\mathbb{N}$ be given, and let $p>d$ be a prime. Then, given any maps
$c_{0},c_{1},\dots,c_{d}\colon\mathbb{Z}_{p}\to\mathbb{Z}_{p}$ and any set
$F\subset\mathbb{Z}_{p}$ of size less than $p/d$, we can find another map
$\alpha\colon\mathbb{Z}_{p}\to\mathbb{Z}_{p}$ such that the expression

$c_{d}(x)\alpha(x)^{d}+\dots c_{1}(x)\alpha(x)+c_{0}(x)$

does not take a value in $F$ for any $x$ that has at least one of
$c_{1}(x),c_{2}(x),\dots,c_{d}(x)$ non-zero.

###### Proof.

Suppose that for some $x$, we have that for every choice of $v=\alpha(x)$ we
have $c_{d}(x)v^{d}+\dots c_{1}(x)v+c_{0}(x)\in F$. By the pigeonhole
principle, some value $f\in F$ is hit at least $d+1$ times. Thus, the
polynomial

$c_{d}(x)v^{d}+\dots c_{1}(x)v+c_{0}(x)-f$

has at least $d+1$ zeros, making it a zero polynomial. Hence
$c_{1}(x),c_{2}(x),\dots,c_{d}(x)$ are simultaneously zero, proving the
lemma.∎

######  Corollary 4.3.

Let $E$ be an arbitrary $\mathbb{Z}$-linear combination of terms of the form
$\alpha(x)^{i}x^{j}$, where at least one of such terms with $i>0$ appears.
Given any $\epsilon>0$, we can find a modulus $q$, which is a product of
distinct arbirtrarily large primes, and a map
$\alpha\colon\mathbb{Z}_{q}\to\mathbb{Z}_{q}$ such that under $\alpha$ the
expression $E$ takes at most $\epsilon q$ values in $\mathbb{Z}_{q}$.

###### Proof.

Rewrite $E$ by grouping together a $\mathbb{Z}$-linear combination of $x^{j}$
that appear next to each $\alpha(x)^{i}$. Thus, we can write $E$ as
$\alpha(x)^{d}f_{d}(x)+\dots+\alpha(x)f_{1}(x)+f_{0}(x)$, where each
$f_{i}(x)$ is a polynomial in $x$ over $\mathbb{Z}$, and at least one of
$f_{1},f_{2},\dots,f_{d}$ is not a zero polynomial. Let $D=\max\deg f_{i}$.
Pick distinct arbitrarily large primes $p_{1},p_{2},\dots,p_{t}$, all w.l.o.g.
larger than $2d(D+1)$ and absolute values of coefficients of
$f_{1},f_{2},\dots,f_{d}$ (so that non-zero polynomials do not become zero
modulo $p_{i}$). By the Lemma 4.2, we may find a map
$\alpha_{i}\colon\mathbb{Z}_{p_{i}}\to\mathbb{Z}_{p_{i}}$ for each $i$ such
that the image of $E$ has size at most $(1-1/d)p_{i}+1$, when the variable $x$
ranges over values such that polynomials $f_{1},f_{2},\dots,f_{d}$ are not
simlutaneously zero. But there are at most $D$ values of $x$ such that
$f_{1}(x)=\dots=f_{d}(x)=0$, so we conclude that modulo each $p_{i}$, the
expression $E$ may take at most $(1-1/d)p_{i}+D+1\leq(1-1/2d)p_{i}$ values.
Finally, set $q=p_{1}p_{2}\dots p_{t}$ and take
$\alpha\colon\mathbb{Z}_{q}\to\mathbb{Z}_{q}$ to be
$\alpha=(\alpha_{1},\alpha_{2},\dots,\alpha_{t})$, where we as usual identify
$\mathbb{Z}_{q}$ with
$\mathbb{Z}_{p_{1}}\oplus\mathbb{Z}_{p_{2}}\oplus\dots\oplus\mathbb{Z}_{p_{t}}$.
Hence, modulo $q$, the expression takes at most $(1-1/2d)^{t}q$ values. Taking
$t$ large enough so that $(1-1/2d)^{t}<\epsilon$ proves the corollary.∎

The case 1 now follows by applying Corollary 4.3.

Case 2: the quadratic part has two variables. The quadratic part must look
like a product of two terms, each being either $\alpha_{i}(x_{i})+x_{i}$ or
$\alpha_{i}(x_{i})$. By suitably renaming the variables, and adding $x_{i}$ to
$\alpha_{i}(x_{i})$ if necessary, w.l.o.g. we only need to consider the case
when the quadratic part is $\alpha_{1}(x_{1})\alpha_{2}(x_{2})$, and the whole
expression is

$\alpha_{1}(x_{1})\alpha_{2}(x_{2})+L_{1}(x_{1})+L_{2}(x_{2})$

where each $L_{i}(x_{i})$ is a $\mathbb{Z}$-linear combination of
$\alpha_{i}(x_{i})$ and $x_{i}$. Note also that if $L_{i}(x_{i})$ is nonzero,
then $\alpha_{i}(x_{i})$ appears with a nonzero coefficient.

We have now come to an important point in this paper, and one of the key
ideas, which we shall now explain. We have to construct $q$ and maps
$\alpha_{1},\alpha_{2}\colon\mathbb{Z}_{q}\to\mathbb{Z}_{q}$ such that
$\alpha_{1}(x_{1})\alpha_{2}(x_{2})+L_{1}(x_{1})+L_{2}(x_{2})$ takes $o(q)$
values. Suppose for a moment that the linear terms $L_{i}$ are both zero.
Then, we have an easy way to make $\alpha_{1}(x_{1})\alpha_{2}(x_{2})$
constant, by setting one of the $\alpha_{i}$ to be zero. However, such an
approach cannot work in the case when $L_{1},L_{2}$ are not zero, as it would
force one of the $L_{i}$ to be an affine map, which is surjective. As a way to
overcome this, we can use both $\alpha_{1}=0$ and $\alpha_{2}=0$ to get
additional freedom. Thus, we set $q=q_{1}q_{2}$, where $q_{1},q_{2}$ are
coprime products of distinct primes, identify $\mathbb{Z}_{q}$ with
$\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{2}}$, and set $\alpha_{1}$ to be zero
on the first coordinate, and $\alpha_{2}$ to be zero on the second coordinate.
Hence if $L_{1}(x_{1})=\lambda_{1}\alpha_{1}(x_{1})+\mu_{1}x_{1}$ and
$L_{2}(x_{2})=\lambda_{2}\alpha_{2}(x_{2})+\mu_{2}x_{2}$, then the expression
becomes

$\left(\mu_{1}(x_{1})_{1}+\lambda_{2}(\alpha_{2})_{1}(x_{2})+\mu_{2}(x_{2})_{1},\lambda_{1}(\alpha_{1})_{2}(x_{1})+\mu_{1}(x_{1})_{2}+\mu_{2}(x_{2})_{2}\right).$
(2)

We now want to find $(\alpha_{1})_{2}$ and $(\alpha_{2})_{1}$ so that the
expression (2) does not take too many values in
$\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{2}}$. Suppose for a moment that
instead of coprime $q_{1}$ and $q_{2}$ we actually had $q_{1}=q_{2}$. Then, we
could have simply taken

$(\alpha_{1})_{2}(x_{1}):=-\lambda_{1}^{-1}\mu_{1}((x_{1})_{1}+(x_{1})_{2})$

and

$(\alpha_{2})_{1}(x_{2}):=-\lambda_{2}^{-1}\mu_{2}((x_{2})_{1}+(x_{2})_{2}),$

which ensures that every value taken by the expression is of the form $(v,-v)$
and hence it is in small subset $\\{(x,y):x+y=0\\}$ of
$\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{1}}$. It turns out that we can use the
same approach even if $q_{1}\not=q_{2}$. We shall refer to this idea as the
_identification of coordinates_ , which will appear at other places in this
paper as well. The following proposition and its proof formalize this
discussion. We slightly change the notation to make the reading easier.

######  Proposition 4.4.

(Basic identification of coordinates.) Let
$\lambda_{0},\lambda_{1},\lambda_{2},\mu_{1},\mu_{2}\in\mathbb{Z}$ be given
and let $p\leq q$ be primes greater than $|\lambda_{1}|,|\lambda_{2}|$.
Suppose that if $\lambda_{1}=0$ then $\mu_{1}=0$ and if $\lambda_{2}=0$ then
$\mu_{2}=0$. Then we have
$\alpha,\beta\colon\mathbb{Z}_{p}\oplus\mathbb{Z}_{q}\to\mathbb{Z}_{p}\oplus\mathbb{Z}_{q}$
such that

$f\colon(x,y)\mapsto\lambda_{0}\alpha(x)\beta(y)+\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta(y)+\mu_{2}y$

takes at most $O(q)$ values, when $x,y$ range over all pairs of values in
$\mathbb{Z}_{p}\oplus\mathbb{Z}_{q}$.

Recall the definition of map $\iota_{p}$ as the natural embedding of
$\mathbb{Z}_{p}$ into $\mathbb{Z}$, the natural projection
$\pi_{p}\colon\mathbb{Z}\to\mathbb{Z}_{p}$, and finally, the composition
$\operatorname{mod}_{p,q}\colon\mathbb{Z}_{p}\to\mathbb{Z}_{q}$, given by
$\operatorname{mod}_{p,q}=\pi_{q}\circ\iota_{p}$. Before proceeding with the
proof, it is useful to note some easy properties of the maps $\iota_{p}$ and
$\operatorname{mod}_{p,q}$.

######  Lemma 4.5.

Let $p,p^{\prime},p_{1},p_{2},p_{3}$ be primes. Then

  * (1) Given $z\in\mathbb{Z}$, we have $p|\iota_{p}(\pi_{p}(z))-z$. Also, $\iota_{p}(\pi_{p}(z))\leq z$, when $z\geq 0$.

  * (2) Given $x,y\in\mathbb{Z}_{p}$, we have $\iota_{p}(x)+\iota_{p}(y)-\iota_{p}(x+y)\in\\{0,p\\}.$

  * (3) Given $x,y\in\mathbb{Z}_{p}$, we have

$\operatorname{mod}_{p,p^{\prime}}(x)+\operatorname{mod}_{p,p^{\prime}}(y)-\operatorname{mod}_{p,p^{\prime}}(x+y)\in\\{0,\pi_{p^{\prime}}(p)\\}\subset\mathbb{Z}_{p^{\prime}}.$

  * (4) Provided that $p_{3}<(t+1)p_{2}$, we have

$\operatorname{mod}_{p_{2},p_{1}}\circ\operatorname{mod}_{p_{3},p_{2}}(x)-\operatorname{mod}_{p_{3},p_{1}}(x)\in\\{-t\pi_{p_{1}}(p_{2}),-(t-1)\pi_{p_{1}}(p_{2}),\dots,0\\}\subset\mathbb{Z}_{p_{1}}.$

###### Proof.

(1) Applying $\pi_{p}$, we have
$\pi_{p}(\iota_{p}(\pi_{p}(z))-z)=\pi_{p}\circ\iota_{p}(\pi_{p}(z))-\pi_{p}(z)=0$,
thus $p|\iota_{p}(\pi_{p}(z))-z$. If $z\geq 0$, then
$\iota_{p}(\pi_{p}(z))-z\leq p-1$, so the claim follows.

(2) Let $x^{\prime}=\iota_{p}(x),y^{\prime}=\iota_{p}(y)\in\mathbb{Z}$. Note
that $\pi_{p}(x^{\prime}+y^{\prime})=x+y$ and
$x^{\prime}+y^{\prime}\in\\{0,1,\dots,2p-2\\}$. From definition,
$\pi_{p}(\iota_{p}(x+y))=x+y$ and $\iota_{p}(x+y)\in\\{0,1,\dots,p-1\\}$.
Hence, if we set $v=\iota_{p}(x)+\iota_{p}(y)-\iota_{p}(x+y)$, we have $p|v$
and $v\in\\{-(p-1),-(p-2),\dots,2p-2\\}$, so $v\in\\{0,p\\}$.

(3) The statement follows by applying $\pi_{p^{\prime}}$ to
$\iota_{p}(x)+\iota_{p}(y)-\iota_{p}(x+y)\in\\{0,p\\}$, noting that
$\pi_{p^{\prime}}$ is an additive homomorphism and recalling that
$\operatorname{mod}_{p,p^{\prime}}=\pi_{p^{\prime}}\circ\iota_{p}$.

(4) From the definition, we have

$\operatorname{mod}_{p_{2},p_{1}}\circ\operatorname{mod}_{p_{3},p_{2}}(x)-\operatorname{mod}_{p_{3},p_{1}}(x)=\pi_{p_{1}}(\iota_{p_{2}}(\pi_{p_{2}}(\iota_{p_{3}}(x))))-\pi_{p_{1}}(\iota_{p_{3}}(x))=\pi_{p_{1}}(\iota_{p_{2}}(\pi_{p_{2}}(\iota_{p_{3}}(x)))-\iota_{p_{3}}(x)).$

Write $v=\iota_{p_{2}}(\pi_{p_{2}}(\iota_{p_{3}}(x)))-\iota_{p_{3}}(x)$. Using
the previous work, we know that $p_{2}|v$, $v\geq-(p_{3}-1)$ and $v\leq 0$,
since $\iota_{p_{3}}(x)\geq 0$. So $v\in\\{-tp_{2},-(t-1)p_{2},\dots,0\\}$,
and the claim follows after applying $\pi_{p_{1}}$.∎

###### Proof of Proposition 4.4.

Observe immediately that if $\lambda_{0}=0$, we can ensure that
$\lambda_{1}\alpha(x)+\mu_{1}x=0$ and $\lambda_{2}\beta(y)+\mu_{2}y=0$,
proving the claim. Therefore, we may assume $\lambda_{0}\not=0$, w.l.o.g.
$\lambda_{0}=1$. If $\mu_{1}=\mu_{2}=0$ holds, then the function becomes
$f\colon(x,y)\mapsto\alpha(x)\beta(y)+\lambda_{1}\alpha(x)+\lambda_{2}\beta(y)$,
which can be made zero, by choosing zero maps for $\alpha$ and $\beta$. If
exactly one of $\mu_{1},\mu_{2}$ vanishes, $\mu_{1}=0$ say, then we can pick
$\beta$ to ensure that $\lambda_{2}\beta(y)+\mu_{2}y=0$, and set $\alpha(x)=0$
to get $f=0$. From now on, assume that
$\lambda_{1},\lambda_{2},\mu_{1},\mu_{2}\not=0$.
Set $\alpha_{1}(x)=0$ and $\beta_{2}(y)=0$. This makes $\alpha(x)\beta(y)=0$
for all choices of $x,y$. It remains to pick $\alpha_{2}(x),\beta_{1}(y)$ so
that
$(\mu_{1}x_{1}+\lambda_{2}\beta_{1}(y)+\mu_{2}y_{1},\lambda_{1}\alpha_{2}(x)+\mu_{1}x_{2}+\mu_{2}y_{2})$
takes a small number of values.
Set
$\beta_{1}(y)=-\lambda_{2}^{-1}(\mu_{1}\operatorname{mod}_{q,p}(y_{2})+\mu_{2}y_{1})$
and
$\alpha_{2}(x)=-\lambda_{1}^{-1}(\mu_{2}\operatorname{mod}_{p,q}(x_{1})+\mu_{1}x_{2})$.
Hence $f$ becomes

$f(x,y)=(\mu_{1}(x_{1}-\operatorname{mod}_{q,p}(y_{2})),\mu_{2}(y_{2}-\operatorname{mod}_{p,q}(x_{1}))).$

Let $\Phi\colon\mathbb{Z}_{p}\oplus\mathbb{Z}_{q}\to\mathbb{Z}$ be given by
$\Phi(u,v)=\iota_{p}(\mu_{1}^{-1}u)+\iota_{q}(\mu_{2}^{-1}v)$, noting that
$\mu_{1},\mu_{2}\not=0$. Then,

$\Phi(f(x,y))=\iota_{p}(x_{1}-\operatorname{mod}_{q,p}(y_{2}))+\iota_{q}(y_{2}-\operatorname{mod}_{p,q}(x_{1})).$

Fixing the set $S=\\{-p,0,p\\}+\\{-q,0,q\\}$, from Lemma 4.5 we have

$\iota_{p}(x_{1}-\operatorname{mod}_{q,p}(y_{2}))+\iota_{q}(y_{2}-\operatorname{mod}_{p,q}(x_{1}))\in\iota_{p}(x_{1})-\iota_{p}(\operatorname{mod}_{q,p}(y_{2}))+\iota_{q}(y_{2})-\iota_{q}(\operatorname{mod}_{p,q}(x_{1}))+S$

or, under our notation introduced earlier,

$\Phi(f(x,y))\overset{O(1)}{=}\iota_{p}(x_{1})-\iota_{p}(\operatorname{mod}_{q,p}(y_{2}))+\iota_{q}(y_{2})-\iota_{q}(\operatorname{mod}_{p,q}(x_{1}))=\iota_{p}(x_{1})-\iota_{q}(\pi_{q}(\iota_{p}(x_{1})))+\iota_{q}(y_{2})-\iota_{p}(\pi_{p}(\iota_{q}(y_{2})))$

Lemma 4.5 also implies that
$\iota_{p}(\pi_{p}(v))\overset{O(\frac{q}{p})}{=}v$ and
$\iota_{q}(\pi_{q}(v))\overset{O(1)}{=}v$, when $|v|=O(q)$, from which we
conclude that

$\Phi(f(x,y))\overset{O(\frac{q}{p})}{=}\iota_{p}(x_{1})-\iota_{p}(x_{1})+\iota_{q}(y_{2})-\iota_{q}(y_{2})=0,$

so the image of the function $f$ is a subset of a preimage of $\Phi$ of a set
of size $O(1)$. Fibers of $\Phi$ are of size at most $p$, so the claim
follows.∎

Applying the Proposition 4.4 finishes the proof of the Theorem 4.1.∎

###  4.1 Using affine maps in the case of two variables

In this subsection, we further discuss some quadratic expressions involving
two variables. A natural map we can try is an affine map $x\mapsto ax+b$, for
constants $a,b$. However, if we look at expression
$\alpha(x)\beta(y)+\alpha(x)+x+\beta(y)+y$, which was among the ones necessary
to discuss in the proof of Theorem 4.1, it is easy to see that choosing affine
maps from $\mathbb{Z}_{q}$ to $\mathbb{Z}_{q}$ for $\alpha$ and $\beta$ yields
full image, for every $q$. Here we ask ourselves the question when we can use
such maps to get a small image of the function defined by the expression.

As we shall see later in the paper, in the construction of $A$ with small
$2A^{2}+kA$, one of the expressions we shall consider has quadratic part of
the form
$\alpha_{1}(x_{1})\alpha_{2}(x_{2})+(\alpha_{1}(x_{1})+c_{1}x_{1})(\alpha_{2}(x_{2})+c_{2}x_{2})$,
with $c_{1},c_{2}\not=0$. It turns out that in this case the affine maps can
be used as desired maps. We discuss these maps before the construction of $A$
with small $2A^{2}+kA$, so that we can focus better on the new ideas needed
for that case.

######  Lemma 4.6.

(Affine maps solution.) Let $\nu_{1},\nu_{2}\not=0$ and
$\lambda_{1},\lambda_{2},\mu_{1},\mu_{2}$ be integers. Then, for any prime $p$
greater than absolute values of all the given integers, we can find affine
maps $\alpha,\beta\colon\mathbb{Z}_{p}\to\mathbb{Z}_{p}$ such that

$\alpha(x)\beta(y)+(\alpha(x)+\nu_{1}x)(\beta(y)+\nu_{2}y)+\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta(y)+\mu_{2}y$

is constant.

###### Proof.

Let $\alpha(x):=ax+b$ and $\beta(y):=cy+d$, with $a,b,c,d$ to be determined.
With this choice of maps, the expression above becomes

$(ac+(a+\nu_{1})(c+\nu_{2}))xy+(2ad+d\nu_{1}+\lambda_{1}a+\mu_{1})x+(2bc+b\nu_{2}+\lambda_{2}c+\mu_{2})y+(2bd+\lambda_{1}b+\lambda_{2}d).$

Hence, we need to make sure that

$2ac+\nu_{2}a+\nu_{1}c+\nu_{1}\nu_{2}=0,$
$2ad+\nu_{1}d+\lambda_{1}a+\mu_{1}=0,$

and

$2bc+\nu_{2}b+\lambda_{2}c+\mu_{2}=0.$

This is equivalent to

$b=-(\lambda_{2}c+\mu_{2})/(2c+\nu_{2}),$
$a=-(\nu_{1}c+\nu_{1}\nu_{2})/(2c+\nu_{2})$

and

$d=\left(\mu_{1}(2c+\nu_{2})-\lambda_{1}\nu_{1}(c+\nu_{2})\right)/\left(\nu_{1}\nu_{2}\right).$

Hence, we can pick $a,b,c,d$ so that affine maps make our expression equal to
constant iff $\nu_{1},\nu_{2}$ are non-zero. ∎

##  5 Sets $A$ with small $2A^{2}+kA$

This section is devoted to the proof of the case $l=2$ of the Theorem 1.5.

######  Theorem 5.1.

For any $k\in\mathbb{N}_{0}$ and any $\epsilon>0$, there is a natural number
$q$, which is a product of distinct, arbitrarily large primes, and a set
$A\subset\mathbb{Z}_{q}$ such that $A-A=\mathbb{Z}_{q}$, while
$|2A^{2}+kA|<\epsilon q$.

###### Proof.

The approach here is similar to the one in the proof of the Theorem 4.1,
however the expressions that arise in this case are more complicated and
require new ideas. Once again, the proof is based on the Proposition 3.1. As
before, we split all expressions in their quadratic and linear parts, and we
may assume that if a variable appears at all in an expression, it must appear
in the quadratic part. Next, we consider all the possible cases for the
quadratic part, and explain how to make the image of the expression small in
each case separately. They are listed sorted by the support size and then by
structure. We also have the freedom of renaming the variables. Again, we
change the notation slightly; instead of $x_{1},x_{2},x_{3},x_{4}$ and
$\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4}$ we use $x,y,z,w$ and
$\alpha,\beta,\gamma,\delta$ respectively. The possible cases, w.l.o.g. are
(all the $c_{i}$ are in $\\{0,1\\}$)

  1. 1.

Support of size 1.

    1. (a)

The non-linear part must look like
$(\alpha(x)+c_{1}x)(\alpha(x)+c_{2}x)+(\alpha(x)+c_{3}x)(\alpha(x)+c_{4}x)$.

  2. 2.

Support of size 2. We have a few possibilities here.

    1. (a)

$(\alpha(x)+c_{1}x)(\alpha(x)+c_{2}x)+(\alpha(x)+c_{3}x)(\beta(y)+c_{4}y)$

    2. (b)

$(\alpha(x)+c_{1}x)(\beta(y)+c_{2}y)+(\alpha(x)+c_{3}x)(\beta(y)+c_{4}y)$

    3. (c)

$(\alpha(x)+c_{1}x)(\alpha(x)+c_{2}x)+(\beta(y)+c_{3}y)(\beta(y)+c_{4}y)$

  3. 3.

Support of size 3. We have a few possibilities here.

    1. (a)

$(\alpha(x)+c_{1}x)(\alpha(x)+c_{2}x)+(\beta(y)+c_{3}y)(\gamma(z)+c_{4}z)$

    2. (b)

$(\alpha(x)+c_{1}x)(\beta(y)+c_{2}y)+(\alpha(x)+c_{3}x)(\gamma(z)+c_{4}z)$

  4. 4.

Support of size 4.

    1. (a)

The non-linear part must look like
$(\alpha(x)+c_{1}x)(\beta(y)+c_{2}y)+(\gamma(z)+c_{3}z)(\delta(w)+c_{4}w)$.

We discuss each of these case separately. However, we use a different order
than stated above and deal with easier cases first.

Case 1(a). This is immediate from Corollary 4.3.

Case 2(b). If $c_{1}=c_{3}$ or $c_{2}=c_{4}$, modifying $\alpha(x)$ by adding
a suitable multiple $\lambda x$ to it, and modyfing $\beta(y)$ accordingly, we
may assume that the quadratic expression is exactly $2\alpha(x)\beta(y)$,
which we have already done in Proposition 4.4 (notice that the condition on
coefficients in that proposition is satisfied). Hence, w.l.o.g.
$c_{1}\not=c_{3}$ and $c_{2}\not=c_{4}$. Then, (after a suitable modification
of $\alpha_{i}$ by affine maps to make $c_{1}=c_{2}=0$, $c_{3},c_{4}\not=0$),
we can apply the Lemma 4.6, to finish the proof in this case.

Case 2(c). The whole expression in this case is of the form
$f_{1}(x)+f_{2}(y)$, where $f_{1}$ is a polynomial of degree at most 2 in $x$
and $\alpha(x)$ and $f_{2}$ is a polynomial of degree at most 2 in $y$ and
$\beta(y)$. Note that we cannot use our arguments about single variable
expressions here, as we would only get two sets
$S_{1},S_{2}\subset\mathbb{Z}_{q}$ of size $o(q)$ such that $f_{i}$ always
takes values in $S_{i}$, so we would only know that the whole expression takes
values in $S_{1}+S_{2}$ which could easily be the whole set of residues.
Instead, we recall that the polynomials always attain a small value. This is
the content of the next lemma, which is a well-known consequence of Weyl’s
inequality on exponential sums. Similar results appear in [5], we include a
proof for completness.

######  Lemma 5.2.

Let $d$ be fixed. Then there is an absolute constant $C_{d}$ such that the
following holds. Let $p$ be a prime, and let
$a_{d},a_{d-1},\dots,a_{0}\in\mathbb{Z}_{p}$ be given, with $a_{d}$ non-zero.
Then the polynomial $a_{d}x^{d}+\dots+a_{1}x+a_{0}$ attains a value in
$\\{-C_{d}p^{1-2^{-d}},\dots,C_{d}p^{1-2^{-d}}\\}$.

Write $e_{p}(t)$ for the function $\exp(2\pi it/p)$. The proof uses discrete
Fourier transforms of functions $f\colon\mathbb{Z}_{p}\to\mathbb{C}$, which we
define as $\hat{f}\colon\mathbb{Z}_{p}\to\mathbb{C}$ with
$\hat{f}(r)=\sum_{x\in\mathbb{Z}_{p}}f(x)e_{p}(-rx)$. We refer readers to [5]
for more details.

###### Proof.

Write $f(x)$ for the polynomial $a_{d}x^{d}+\dots+a_{1}x+a_{0}$. We begin by
stating (a special case of) Weyl’s inequality.

######  Theorem 5.3.

(Weyl’s inequality. [14]) For every $\epsilon>0$, and $d\in\mathbb{N}$, there
is a constant $C_{\epsilon,d}$ such that for all primes $p$

$\left|\sum_{x\in\mathbb{Z}_{p}}e_{p}(g(x))\right|\leq
C_{\epsilon,d}p^{1+\epsilon-2^{1-d}}$

holds for every polynomial $g\in\mathbb{Z}_{p}[X]$ of degree $d$.

Write $F(x)$ for the number of times the polynomial $f$ attains the value $x$.
Hence, by Weyl’s inequality, there is a constant $C$, independent of $p$ such
that $|\hat{F}(r)|\leq Cp^{1-2^{-d}}$ for $r\not=0$, and $\hat{F}(0)=p$. Let
$I$ be interval $\\{-k,-k+1,\dots,k\\}$. Suppose that $f$ attains no value in
$\\{-2k,-2k+1,\dots,2k\\}$. We have

$\sum_{x}F(x)I\ast I(x)=0.$

Applying Parseval’s formula and noting that $\hat{I}(r)\in\mathbb{R}$, we get
that

$0=\sum_{r}\hat{F}(r)\hat{I}(r)^{2}=\hat{F}(0)\hat{I}(0)^{2}+\sum_{r\not=0}\hat{F}(r)\hat{I}(r)^{2}=p(2k+1)^{2}+\sum_{r\not=0}\hat{F}(r)\hat{I}(r)^{2}.$

Thus,

$p(2k+1)^{2}\leq\sum_{r\not=0}|\hat{F}(r)|\hat{I}(r)^{2}\leq\left(\max_{r\not=0}|\hat{F}(r)|\right)\sum_{s}\hat{I}(s)^{2}\leq
Cp^{1-2^{-d}}p(2k+1).$

From this we conclude that $2k+1\leq Cp^{1-2^{-d}}$, as desired. ∎

Write $N$ for $C_{d}p^{1-2^{-d}}$. Now, consider $f_{1}(x)$ as a polynomial in
$\alpha(x)$ for every fixed $x$. The lemma guarantees that we can define
$\alpha(x)$ so that $f_{1}(x)\in\\{-N,-N+1,\dots,N\\}$. Similarly, for every
$y$, we can pick $\beta(y)$ so that $f_{2}(y)\in\\{-N,-N+1,\dots,N\\}$, hence
we always have $f_{1}(x)+f_{2}(y)\in\\{-2N,-2N+1,\dots,2N\\}$, as desired.

Case 3(a). We shall take $q$ of the form $q_{1}q_{2}q_{3}$, where
$q_{1},q_{2},q_{3}$ are coprime, and each is a product of distinct arbitrarily
large primes. As always, we identify
$\mathbb{Z}_{q}\cong\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{2}}\oplus\mathbb{Z}_{q_{3}}$,
and we aim to use the identification of coordinates idea. Thus, we set
$\alpha_{1}(x):=-c_{1}x_{1},\alpha_{2}(x):=-c_{2}x_{2}$, so that
$(\alpha(x)+c_{1}x)(\alpha(x)+c_{2}x)$ has second and third coordinates equal
to zero. We also set $\beta_{1}(y):=-c_{3}y_{1},\beta_{3}(y):=-c_{3}y_{3}$ and
$\gamma_{2}(z):=-c_{4}z_{2},\gamma_{3}(z):=-c_{4}z_{3}$. Note that we still
have freedom of choice for $\alpha_{3},\beta_{2},\gamma_{1}$. Let the linear
part of the expression be
$d_{1}\alpha(x)+d_{2}x+d_{3}\beta(y)+d_{4}y+d_{5}\gamma(z)+d_{6}z$, where the
coefficients $d_{i}$ have the property that $d_{2i}\not=0$ implies
$d_{2i-1}\not=0$ (since the linear part comes from $\mathbb{N}$-linear
combination of $\alpha(x)$ and $\alpha(x)+x$, etc.). The expression becomes

$\begin{split}&((-d_{1}c_{1}+d_{2})x_{1}+(-d_{3}c_{3}+d_{4})y_{1}+d_{5}\gamma_{1}(z)+d_{6}z_{1},\\\
&(-d_{1}c_{2}+d_{2})x_{2}+d_{3}\beta_{2}(y)+d_{4}y_{2}+(-c_{4}d_{5}+d_{6})z_{2},\\\
&(\alpha_{3}(x)+c_{1}x_{3})(\alpha_{3}(x)+c_{2}x_{3})+d_{1}\alpha_{3}(x)+d_{2}x_{3}+(-d_{3}c_{3}+d_{4})y_{3}+(-d_{5}c_{4}+d_{6})z_{3}).\end{split}$

We combine the identification of coordinates idea with the fact that
polynomials have relatively dense sets of values in the next proposition.

######  Proposition 5.4.

(Strong version of the identification of coordinates) Fix $n,d\in\mathbb{N}$.
Then there are constants $\epsilon,C>0$ such that the following holds. Let
$d_{1},d_{2},\dots,d_{n}\in\mathbb{N}$ all be at most $d$. Let
$2p_{n}>p_{1}\geq p_{2}\geq\dots\geq p_{n}$ be primes. Write
$r=p_{1}p_{2}\dots p_{n}$. Next, let
$f_{i,j}\colon\mathbb{Z}_{r}\to\mathbb{Z}_{p_{j}}$ be arbitrary maps for every
$1\leq i,j\leq n$. Let for every $1\leq i\leq n$,
$c_{i}\in\mathbb{Z}_{p_{i}}^{\times}$. Finally, let
$g_{i,j}\colon\mathbb{Z}_{r}\to\mathbb{Z}_{p_{i}}$ be also arbitrary functions
for every $1\leq i\leq n,1\leq j\leq d_{i}-1$. Then, we can find maps
$\alpha_{i}\colon\mathbb{Z}_{r}\to\mathbb{Z}_{p_{i}}$ such that the expression

$\begin{split}(&f_{1,1}(x_{1})+f_{2,1}(x_{2})+\dots+f_{n,1}(x_{n})+c_{1}\alpha_{1}(x_{1})^{d_{1}}+g_{1,d_{1}-1}(x_{1})\alpha_{1}(x_{1})^{d_{1}-1}+\dots+g_{1,1}(x_{1})\alpha_{1}(x_{1}),\\\
&f_{1,2}(x_{1})+f_{2,2}(x_{2})+\dots+f_{n,2}(x_{n})+c_{2}\alpha_{2}(x_{2})^{d_{2}}+g_{2,d_{2}-1}(x_{2})\alpha_{2}(x_{2})^{d_{2}-1}+\dots+g_{2,1}(x_{2})\alpha_{2}(x_{2}),\\\
&\vdots\\\
&f_{1,n}(x_{1})+f_{2,n}(x_{2})+\dots+f_{n,n}(x_{n})+c_{n}\alpha_{n}(x_{n})^{d_{n}}+g_{n,d_{n}-1}(x_{n})\alpha_{n}(x_{n})^{d_{n}-1}+\dots+g_{n,1}(x_{n})\alpha_{n}(x_{n}))\end{split}$

takes at most $Cp_{n}^{-\epsilon}p_{1}p_{2}\dots p_{n}$ values as
$x_{1},x_{2},\dots,x_{n-1}$ and $x_{n}$ range over all values in
$\mathbb{Z}_{r}$.

Throughout the paper, we will use the prime number theorem ([8]) without
explicitly mentioning it.

###### Proof.

Write $q$ for $p_{n}$ (in fact any prime close to $p_{1},p_{2},\dots,p_{n}$
would work). The main idea is to pick $\alpha_{1},\dots,\alpha_{n}$ so that
every value $(v_{1},v_{2},\dots,v_{n})$ attained by the expression satisfies
$\sum_{i=1}^{n}\mod_{p_{i},q}(v_{i})\in S$, for a small subset
$S\subset\mathbb{Z}_{q}$. Partitioning
$\mathbb{Z}_{p_{1}}\oplus\mathbb{Z}_{p_{2}}\oplus\dots\oplus\mathbb{Z}_{p_{n}}$
into cosets of $\\{0\\}\times\dots\times\\{0\\}\times\mathbb{Z}_{p_{n}}$, we
see the set of values of the expression can take only at most $|S|$ values on
each coset, and thus a small number of values in total.

We use the Lemma 5.2 in order to define $\alpha_{i}$. Recall that the lemma
gives $C^{\prime},\epsilon>0$ such that every non-constant polynomial of
degree at most $d$ in $\mathbb{Z}_{p_{i}}$ for any $i$, takes a value in
$\\{0,1,\dots,C^{\prime}q^{1-\epsilon}\\}$ (modify the constant coefficient if
necessary). For every $i$, we define $\alpha_{i}$ as follows. We apply the
lemma for every fixed
$x_{i}\in\mathbb{Z}_{p_{1}}\oplus\mathbb{Z}_{p_{2}}\oplus\dots\oplus\mathbb{Z}_{p_{n}}$
to the polynomial

$c_{i}t^{d_{i}}+\sum_{j=1}^{d_{i}-1}g_{i,j}(x_{i})t^{j}+\sum_{j=1}^{n}\operatorname{mod}_{p_{j},p_{i}}(f_{i,j}(x_{i})).$

Hence, we can pick $t$, such that this expression takes value in
$\\{0,1,\dots,C^{\prime}q^{1-\epsilon}\\}\subset\mathbb{Z}_{p_{i}}$. We set
$\alpha_{i}(x_{i}):=t$. Therefore, we have defined
$\alpha_{i}\colon\mathbb{Z}_{p_{1}}\oplus\mathbb{Z}_{p_{2}}\oplus\dots\oplus\mathbb{Z}_{p_{n}}\to\mathbb{Z}_{p_{i}}$,
so that

$\operatorname{mod}_{p_{i},q}\left(c_{i}\alpha_{i}(x_{i})^{d_{i}}+\sum_{j=1}^{d_{i}-1}g_{i,j}(x_{i})\alpha_{i}(x_{i})^{j}+\sum_{j=1}^{n}\operatorname{mod}_{p_{j},p_{i}}(f_{i,j}(x_{i}))\right)\in
S\subset\mathbb{Z}_{q},$

where
$S=\operatorname{mod}_{p_{i},q}(\\{0,1,\dots,C^{\prime}q^{1-\epsilon}\\})=\\{0,1,\dots,C^{\prime}q^{1-\epsilon}\\}$.
To finish the proof, we apply the Lemma 4.5.

Note that we have

$\begin{split}&\sum_{i=1}^{n}\operatorname{mod}_{p_{i},q}\left(\sum_{j=1}^{n}f_{j,i}(x_{j})+c_{i}\alpha_{i}(x_{i})^{d_{i}}+\sum_{j=1}^{d_{i}-1}g_{i,j}(x_{i})\alpha_{i}(x_{i})^{j}\right)\\\
\overset{O_{n}(1)}{=}&\sum_{i=1}^{n}\left(\sum_{j=1}^{n}\operatorname{mod}_{p_{i},q}(f_{j,i}(x_{j}))+\operatorname{mod}_{p_{i},q}(c_{i}\alpha_{i}(x_{i})^{d_{i}})+\sum_{j=1}^{d_{i}-1}\operatorname{mod}_{p_{i},q}(g_{i,j}(x_{i})\alpha_{i}(x_{i})^{j})\right)\\\
\overset{O_{n}(1)}{=}&\left(\sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname{mod}_{p_{j},q}\circ\operatorname{mod}_{p_{i},p_{j}}(f_{j,i}(x_{j}))\right)+\left(\sum_{i=1}^{n}\left(\operatorname{mod}_{p_{i},q}(c_{i}\alpha_{i}(x_{i})^{d_{i}})+\sum_{j=1}^{d_{i}-1}\operatorname{mod}_{p_{i},q}(g_{i,j}(x_{i})\alpha_{i}(x_{i})^{j})\right)\right)\\\
=&\left(\sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname{mod}_{p_{i},q}\circ\operatorname{mod}_{p_{j},p_{i}}(f_{i,j}(x_{i}))\right)+\left(\sum_{i=1}^{n}\left(\operatorname{mod}_{p_{i},q}(c_{i}\alpha_{i}(x_{i})^{d_{i}})+\sum_{j=1}^{d_{i}-1}\operatorname{mod}_{p_{i},q}(g_{i,j}(x_{i})\alpha_{i}(x_{i})^{j})\right)\right)\\\
=&\sum_{i=1}^{n}\operatorname{mod}_{p_{i},q}\left(\operatorname{mod}_{p_{j},p_{i}}(f_{i,j}(x_{i}))+c_{i}\alpha_{i}(x_{i})^{d_{i}}+\sum_{j=1}^{d_{i}-1}g_{i,j}(x_{i})\alpha_{i}(x_{i})^{j}\right)\in
nS\end{split}$ (3)

We conclude that values $(v_{1},v_{2},\dots,v_{n})$ attained by the expression
with the maps $\alpha_{i}$ defined as above satisfy

$\sum_{i=1}^{n}\operatorname{mod}_{p_{i},q}(v_{i})\in nS+T,$

for a set $T$ of size at most $O_{n}(1)$. Since
$nS=\\{0,1,\dots,nC^{\prime}q^{1-\epsilon}\\}\subset\mathbb{Z}_{q}$, the
expression takes at most $O_{n,d}(p_{1}p_{2}\dots p_{n-1}p_{n}^{1-\epsilon})$
values, as desired.∎

The case 3(a) now follows from a straightforward application of the
Proposition 5.4.

We deal with the remaining cases in a similar fashion.

Case 2(a). Let the linear part of the expression be
$\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta(y)+\mu_{2}y$. We shall take
$q=q_{1}q_{2}$, for coprime $q_{1}$ and $q_{2}$, with
$\mathbb{Z}_{q}\cong\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{2}}$. We set
$\alpha_{1}(x):=-c_{3}x_{1}$ and $\beta_{2}(y):=-c_{4}y_{2}$. It remains to
choose
$\alpha_{2}\colon\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{2}}\to\mathbb{Z}_{q_{2}}$
and
$\beta_{1}\colon\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{2}}\to\mathbb{Z}_{q_{1}}$
so that the expression

$\begin{split}(&(c_{1}-c_{3})(c_{2}-c_{3})x_{1}^{2}-c_{3}\lambda_{1}x_{1}+\mu_{1}x_{1}+\lambda_{2}\beta_{1}(y)+\mu_{2}y_{1},\\\
&(\alpha_{2}(x)+c_{1}x_{2})(\alpha_{2}(x)+c_{2}x_{2})+\lambda_{1}\alpha_{2}(x)+\mu_{1}x_{2}-c_{4}\lambda_{2}y_{2}+\mu_{2}y_{2})\\\
=(&(c_{1}-c_{3})(c_{2}-c_{3})x_{1}^{2}+(\mu_{1}-c_{3}\lambda_{1})x_{1}+\mu_{2}y_{1}+\lambda_{2}\beta_{1}(y),\\\
&c_{1}c_{2}x_{2}^{2}+\mu_{1}x_{2}+(\mu_{2}-c_{4}\lambda_{2})y_{2}+\alpha_{2}(x)^{2}+((c_{1}+c_{2})x_{2}+\lambda_{1})\alpha_{2}(x))\\\
\end{split}$

takes small number of values. But, recalling that $\lambda_{2}=0$ implies
$\mu_{2}=0$, this follows directly from the Proposition 5.4, and we may take
$q_{1},q_{2}$ to be prime.

Case 3(b). Let the linear part of the expression be
$\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta(y)+\mu_{2}y+\lambda_{3}\gamma(z)+\mu_{3}z$.
We shall take $q=q_{1}q_{2}q_{3}$, for coprime $q_{1},q_{2}$ and $q_{3}$, with
$\mathbb{Z}_{q}\cong\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{2}}\oplus\mathbb{Z}_{q_{3}}$.
We set
$\alpha_{1}(x):=-c_{1}x_{1},\alpha_{2}(x):=-c_{3}x_{2},\beta_{2}(y):=-c_{2}y_{2},\beta_{3}(y):=-c_{2}y_{3},\gamma_{1}(z):=-c_{4}z_{1}$
and $\gamma_{3}(z):=-c_{4}z_{3}$. It remains to choose
$\alpha_{3}\colon\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{2}}\oplus\mathbb{Z}_{q_{3}}\to\mathbb{Z}_{q_{3}},\beta_{1}\colon\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{2}}\oplus\mathbb{Z}_{q_{3}}\to\mathbb{Z}_{q_{1}}$
and
$\gamma_{2}\colon\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{2}}\oplus\mathbb{Z}_{q_{3}}\to\mathbb{Z}_{q_{2}}$
so that the expression

$\begin{split}(&(-c_{1}\lambda_{1}+\mu_{1})x_{1}+\lambda_{2}\beta_{1}(y)+\mu_{2}y_{1}+(-c_{4}\lambda_{3}+\mu_{3})z_{1},\\\
&(-c_{3}\lambda_{1}+\mu_{1})x_{2}+(-c_{2}\lambda_{2}+\mu_{2})y_{2}+\lambda_{3}\gamma_{2}(z)+\mu_{3}z_{2},\\\
&\lambda_{1}\alpha_{3}(x)+\mu_{1}x_{3}+(-c_{2}\lambda_{2}+\mu_{2})y_{3}+(-c_{4}\lambda_{3}+\mu_{3})z_{3})\end{split}$

takes small number of values. Once again, recalling that $\lambda_{i}=0$
implies $\mu_{i}=0$, this follows directly from the Proposition 5.4, and we
may take $q_{1},q_{2}$ and $q_{3}$ to be prime.

Case 4(a). Let the linear part of the expression be
$\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta(y)+\mu_{2}y+\lambda_{3}\gamma(z)+\mu_{3}z+\lambda_{4}\delta(w)+\mu_{4}w$.
We shall take $q=q_{1}q_{2}q_{3}q_{4}$, for coprime $q_{1},q_{2},q_{3}$ and
$q_{4}$, with
$\mathbb{Z}_{q}\cong\mathbb{Z}_{q_{1}}\oplus\mathbb{Z}_{q_{2}}\oplus\mathbb{Z}_{q_{3}}\oplus\mathbb{Z}_{q_{4}}$.
We set

$\begin{split}&\beta_{1}(y):=-c_{2}y_{1},\gamma_{1}(z)\colon=-c_{3}z_{1},\delta_{1}(w)\colon=-c_{4}w_{1},\\\
&\alpha_{2}(x)\colon=-c_{1}x_{2},\gamma_{2}(z)\colon=-c_{3}z_{2},\delta_{2}(w)\colon=-c_{4}w_{2},\\\
&\alpha_{3}(x)\colon=-c_{1}x_{3},\beta_{3}(y):=-c_{2}y_{3},\delta_{3}(w)\colon=-c_{4}w_{3},\\\
&\alpha_{4}(x)\colon=-c_{1}x_{4},\beta_{4}(y):=-c_{2}y_{4},\gamma_{4}(z)\colon=-c_{3}z_{4}.\end{split}$

We use the Proposition 5.4 to find
$\alpha_{1},\beta_{2},\gamma_{3},\delta_{4}$ so that the expression

$\begin{split}(&\lambda_{1}\alpha_{1}(x)+\mu_{1}x_{1}+(-c_{2}\lambda_{2}+\mu_{2})y_{1}+(-c_{3}\lambda_{3}+\mu_{3})z_{1}+(-c_{4}\lambda_{4}+\mu_{4})w_{1},\\\
&(-c_{1}\lambda_{1}+\mu_{1})x_{2}+\lambda_{2}\beta_{2}(y)+\mu_{2}y_{2}+(-c_{3}\lambda_{3}+\mu_{3})z_{2}+(-c_{4}\lambda_{4}+\mu_{4})w_{2},\\\
&(-c_{1}\lambda_{1}+\mu_{1})x_{3}+(-c_{2}\lambda_{2}+\mu_{2})y_{3}+\lambda_{3}\gamma_{3}(z)+\mu_{3}z_{3}+(-c_{4}\lambda_{4}+\mu_{4})w_{3},\\\
&(-c_{1}\lambda_{1}+\mu_{1})x_{4}+(-c_{2}\lambda_{2}+\mu_{2})y_{4}+(-c_{3}\lambda_{3}+\mu_{3})z_{4}+\lambda_{4}\delta_{4}(w)+\mu_{4}w_{4})\end{split}$

takes small number of values. This completes the proof of the Theorem 5.1.∎

###  5.1 Further discussion of the identification of coordinates idea

As we have seen in the proof of the Theorem 5.1, the Proposition 5.4 was used
in a very similar fashion for several cases of expressions. The goal of this
short subsection is to take this approach further and see what expressions can
be handled using this idea.

We temporarily return to the notation of $x_{i}$ for the variables and
$\alpha_{i}$ for the maps. The value of $x_{i}$ at coordinate $c$ is denoted
by $x_{i,c}$. Observe that when we use Proposition 5.4, we have to pick some
of the maps $\alpha_{i,c}$ to cancel out the mixed quadratic terms like
$\alpha_{1,c}(x_{1})(\alpha_{2,c}(x_{2})+x_{2,c})$. In the proof of the
Theorem 5.1 in the last few cases, given an expression, we used a different
coordinate $c$ for every variable $x_{i}$, and we picked $\alpha_{j,c}$ for
$j\not=i$, so that the mixed quadratic terms dissappear. Our goal now is to
put all these ideas together in a single proposition. First, we need to set up
some useful definitions.

Fix an expression $E$ in variables $x_{1},x_{2},\dots,x_{n}$. Define a graph
$G_{E}$ on vertices $\\{x_{1},x_{2},\dots,x_{n}\\}$ by adding an edge
$x_{i}x_{j}$ for every term of the form
$(\alpha_{i}(x_{i})+cx_{i})(\alpha_{j}(x_{j})+dx_{j})$ with $i\not=j$, with
multiple edges allowed (so $x_{i}x_{j}$ appears the same number of times the
relevant terms occur in $E$).

######  Proposition 5.5.

(Acyclic version of the identification of the coordinates.) Let $E$ be a
quadratic expression such that $G_{E}$ has no cycles (in particular, no
repeated edges). Then there is an absolute constant $\epsilon>0$ such that the
following holds. We can find $q$, a product of distinct, arbitrarily large
primes, and maps
$\alpha_{1},\dots,\alpha_{n}\colon\mathbb{Z}_{q}\to\mathbb{Z}_{q}$ such that
$E$ takes at most $O(q^{1-\epsilon})$ values.

###### Proof.

As promised, we will take $q=q_{1}q_{2}\dots q_{n}$, with $q_{i}$ coprime
products of distinct primes, suitably chosen. As always, view $\mathbb{Z}_{q}$
as the direct sum $\mathbb{Z}_{q_{1}}\oplus\dots\oplus\mathbb{Z}_{q_{n}}$. Let
$c\in[n]$ be an arbitrary coordinate. We start from $x_{c}$ and traverse the
graph $G_{E}$. (If $G_{E}$ is disconnected, pick arbitrary vertices in all
other components to start the traversal from. For each such starting vertex
$x_{i}$, $i\not=c$, set $\alpha_{i,c}=0$.) Since the graph is acyclic, we
reach every variable at most once, and we visit every edge. When we move along
the edge $x_{i}x_{j}$, from $x_{i}$ to $x_{j}$, that means that there is a
term $(\alpha_{i}(x_{i})+ax_{i})(\alpha_{j}(x_{j})+bx_{j})$ in the expression,
and we set $\alpha_{j,c}(x_{j})\colon=-bx_{j,c}$, to make the term vanish.
Since this is the first time we reach $x_{j}$, there are no issues with
defining $\alpha_{j,c}$.
After this procedure, we have defined $\alpha_{i,j}$ for $i\not=j$, so that
for every coordinate $c$, the expression $E_{c}$ no longer has mixed quadratic
terms. We still have the freedom of choosing $\alpha_{c,c}$, so we now may
apply the Proposition 5.4 to finish the proof.∎

As we shall see later, depending on the structure of the graph $G_{E}$, it is
not always possible to choose some of the maps $\alpha_{i,c}$ so that the
mixed quadratic terms vanish, so there is no obvious way to make the
Proposition 5.5 more general.

##  6 Sets $A$ with small $3A^{2}+kA$

In this section we prove the final case of the main theorem.

######  Theorem 6.1.

For any $k\in\mathbb{N}_{0}$ and any $\epsilon>0$, there is a natural number
$q$, which is a product of distinct, arbitrarily large primes, and a set
$A\subset\mathbb{Z}_{q}$ such that $A-A=\mathbb{Z}_{q}$, while
$|3A^{2}+kA|<\epsilon q$.

###### Proof.

We proceed like in the proofs of Theorems 4.1 and 5.1, except that the details
become once again more complicated and the ideas we developed so far,
culminating in Proposition 5.5, do not suffice. As usual, the proof is based
on Proposition 3.1. We split all expressions in their quadratic and linear
parts, and we may assume that if a variable appears at all in an expression,
it must appear in the quadratic part. In the first part of the discussion of
the possible expressions, we use the notation $x_{i}$ for variables and
$\alpha_{i}$ for maps, as there can be upto 6 variables involved. Later, we
again switch to $x,y,z$ and $\alpha,\beta,\gamma$ notation.

Firstly, by Corollary 4.3, we only need to consider expressions with at least
two varaibles. Next, we use the Proposition 5.5 to treat the expressions with
at least 4 variables. We look at the graph $G_{E}$. Note that if we have an
isolated vertex $x_{i}$ in $G_{E}$, since $x_{i}$ appears in the quadratic
part, we must have term of the form
$(\alpha_{i}(x_{i})+c_{1}x_{i})(\alpha_{i}(x_{i})+c_{2}x_{i})$ in $E$. Hence,
the number of isolated vertices $v_{is}$ plus the number of edges $e$ is at
most 3, which is the number of quadratic terms in $E$.

Expression $E$ with exactly 6 variables. We look at $G_{E}$. It is a graph on
6 vertices, with $v_{is}+e\leq 3$. Hence, it is a perfect matching, which is
acyclic, so the Proposition 5.5 applies.

Expression $E$ with exactly 5 variables. Looking at $G_{E}$, which is a graph
on 5 vertices with $v_{is}+e\leq 3$, we see that at most one vertex can have
degree greater than 1. The graph $G_{E}$ is acyclic, so the Proposition 5.5
applies.

Expression $E$ with exactly 4 variables. Once again, we analyse $G_{E}$. It is
a graph on 4 vertices with $v_{is}+e\leq 3$. The only way to get a cycle is if
the graph has a double edge $x_{1}x_{2}$ and an edge $x_{3}x_{4}$ (after a
suitable renaming of variables). Thus, the quadratic part of $E$ is of the
form

$(\alpha_{1}(x_{1})+c_{1}x_{1})(\alpha_{2}(x_{2})+c_{2}x_{2})+(\alpha_{1}(x_{1})+c^{\prime}_{1}x_{1})(\alpha_{2}(x_{2})+c^{\prime}_{2}x_{2})+(\alpha_{3}(x_{3})+c_{3}x_{3})(\alpha_{4}(x_{4})+c_{4}x_{4}),$

where $c_{1},c_{2},c^{\prime}_{1},c^{\prime}_{2},c_{3},c_{4}\in\\{0,1\\}$. If
$c_{1}=c^{\prime}_{1}$ or $c_{2}=c^{\prime}_{2}$, we can rewrite the quadratic
part as a linear combination of only two quadratic terms, so that the graph
$G_{E}$ becomes a matching, and therefore acyclic. Thus, assume that
$c_{1}\not=c^{\prime}_{1}$ and $c_{2}\not=c^{\prime}_{2}$. But, using the
affine maps solution from the Lemma 4.6 we can cancel all the terms in $E$
that involve $x_{1}$ and $x_{2}$. Then, w.l.o.g. $E$ becomes an expression
with quadratic term

$(\alpha_{3}(x_{3})+c_{3}x_{3})(\alpha_{4}(x_{4})+c_{4}x_{4})$

which we have already done using the basic version of the identification of
coordinates idea in Lemma 4.4.

Hence, we may assume that the expression $E$ has either two or three
variables. We treat these cases separately. From now on, we use the notation
$x,y,z$ for the variables and $\alpha,\beta,\gamma$ for maps.

###  6.1 $E$ has two variables $x$ and $y$

Observe that if there is at most one mixed quadratic term
$(\alpha(x)+c_{1}x)(\beta(y)+c_{2}y)$ in the quadratic part, then once again
Proposition 5.5 applies. Hence, we may assume that there are at least two such
terms in $E$. Suppose now that there all three quadratic terms are of this
form, hence the quadratic part is

$(\alpha(x)+c_{1}x)(\beta(y)+c_{2}y)+(\alpha(x)+c_{3}x)(\beta(y)+c_{4}y)+(\alpha(x)+c_{5}x)(\beta(y)+c_{6}y),$

where $c_{1},c_{2},\dots,c_{6}\in\\{0,1\\}$. This constraint on coefficients
is crucial. By pigeonhole principle, there are at least two equal coefficients
among $c_{1},c_{3},c_{5}$, w.l.o.g. $c_{1}=c_{3}$. The quadratic part of $E$
may be written as

$(\alpha(x)+c_{1}x)(2\beta(y)+(c_{2}+c_{4})y)+(\alpha(x)+c_{5}x)(\beta(y)+c_{6}y),$

which we treat using Lemma 4.4 if this factorizes further, or using Lemma 4.6
otherwise.

It remains to treat the case when there are exactly two mixed terms, so the
quadratic part is w.l.o.g.

$(\alpha(x)+c_{1}x)(\alpha(x)+c_{2}x)+(\alpha(x)+c_{3}x)(\beta(y)+c_{4}y)+(\alpha(x)+c_{5}x)(\beta(y)+c_{6}y).$

However, we can no longer use the affine maps to cancel out quadratic terms to
modify the expression and then apply the Proposition 5.5. Instead, we have to
use a different argument, which unfortunately gives significantly worse
bounds.

######  Lemma 6.2.

Let $E$ be a quadratic expression with quadratic part of the form

$n_{1}\alpha(x)^{2}+\alpha(x)(n_{2}x+n_{3}\beta(y)+n_{4}y)+x(n_{5}x+n_{6}\beta(y)+n_{7}y),$

with $n_{1},n_{2},\dots,n_{7}\in\mathbb{Z}$ and $n_{1},n_{3}\not=0$. Then, for
every sufficiently large prime $p$, we can find
$\alpha,\beta\colon\mathbb{Z}_{p}\to\mathbb{Z}_{p}$ such that the expression
does not attain every value in $\mathbb{Z}_{p}$.

Immediately, we have the following corollary.

######  Corollary 6.3.

Let $E$ be a quadratic expression with quadratic part of the form

$n_{1}\alpha(x)^{2}+\alpha(x)(n_{2}x+n_{3}\beta(y)+n_{4}y)+x(n_{5}x+n_{6}\beta(y)+n_{7}y),$

with $n_{1},n_{2},\dots,n_{7}\in\mathbb{Z}$ and $n_{1},n_{3}\not=0$. Let
$\epsilon>0$. Then, there is $q$, product of distinct, arbitrarily large
primes, and maps $\alpha,\beta\colon\mathbb{Z}_{q}\to\mathbb{Z}_{q}$ such that
the expression attains at most $\epsilon q$ values.

###### Proof.

Let $N$ be the bound in Lemma 6.2 such that for all primes $p>N$ we have
$\alpha^{(p)},\beta^{(p)}\colon\mathbb{Z}_{p}\to\mathbb{Z}_{p}$ such that the
expression evades one value, i.e. all values are confined to a set $S_{p}$ of
size $p-1$. If we now take $q=p_{1}p_{2}\dots p_{n}$, a product of distinct
primes greater than $N$, then, once again identifying
$\mathbb{Z}_{q}\cong\mathbb{Z}_{p_{1}}\oplus\dots\oplus\mathbb{Z}_{p_{n}}$,
and defining $\alpha,\beta\colon\mathbb{Z}_{q}\to\mathbb{Z}_{q}$
coordinatewise using $\alpha^{(p_{i})},\beta^{(p_{i})}$, we have that the
expression in $\mathbb{Z}_{q}$ attains values in $S_{p_{1}}\times
S_{p_{2}}\times\dots\times S_{p_{n}}$. Hence, it takes at most
$(p_{1}-1)\dots(p_{n}-1)$ values. A standard calculation reveals that for $n$
sufficiently large, the number of values becomes $o(q)$. (The $p$ that appears
in the sums and products below ranges over primes only.) Indeed,

$\begin{split}\prod_{N<p<M}\frac{p-1}{p}&=\operatorname{exp}\left(\sum_{N<p<M}\log\left(1-\frac{1}{p}\right)\right)=\operatorname{exp}\left(\sum_{N<p<M}-\frac{1}{p}+O\left(\frac{1}{p^{2}}\right)\right)\\\
&=O\left(\operatorname{exp}\left(-\sum_{N<p<M}\frac{1}{p}\right)\right)\to
0\end{split}$

as $M\to\infty$, since $\sum_{p}\frac{1}{p}=\infty$.∎

###### Proof of Lemma 6.2..

Let $\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta(y)+\mu_{2}y$ be the linear
part of the expression. We will define
$\alpha\colon\mathbb{Z}_{p}\to\mathbb{Z}_{p}$ essentially by setting each
$\alpha(y)$ uniformly independently at random (for technical reasons, for
every $x$ we will forbid one value in $\mathbb{Z}_{p}$). Our aim is to define
$\beta$ accordingly so that the expression evades zero value. Hence, for every
$y$, we want to find $\beta(y)$ such that there is no $x$ with

$\beta(y)(n_{3}\alpha(x)+n_{6}x+\lambda_{2})+\alpha(x)(n_{1}\alpha(x)+n_{2}x+n_{4}y+\lambda_{1})+n_{5}x^{2}+n_{7}xy+\mu_{1}x+\mu_{2}y=0.$
(4)

In other words, provided $n_{3}\alpha(x)+n_{6}x+\lambda_{2}\not=0$ always, we
want a value of $\beta(y)$ such that

$\beta(y)\not=-\frac{1}{n_{3}\alpha(x)+n_{6}x+\lambda_{2}}\left(y(n_{4}\alpha(x)+n_{7}x+\mu_{2})+\alpha(x)(n_{1}\alpha(x)+n_{2}x+\lambda_{1})+n_{5}x^{2}+\mu_{1}x\right),$
(5)

for all $x\in\mathbb{Z}_{p}$. Hence, this becomes the requirement that for
every fixed $y$, the set

$S_{y}\colon=\left\\{-\frac{1}{n_{3}\alpha(x)+n_{6}x+\lambda_{2}}\left(y(n_{4}\alpha(x)+n_{7}x+\mu_{2})+\alpha(x)(n_{1}\alpha(x)+n_{2}x+\lambda_{1})+n_{5}x^{2}+\mu_{1}x\right)\colon
x\in\mathbb{Z}_{p}\right\\}$

is not the whole set $\mathbb{Z}_{p}$. We now define
$\alpha\colon\mathbb{Z}_{p}\to\mathbb{Z}_{p}$ by setting each $\alpha(x)$
independently to be a uniform random variable on
$\mathbb{Z}_{p}\setminus\\{-\frac{n_{6}x+\lambda_{2}}{n_{3}}\\}$ (which is
fine, as $n_{3}\not=0$).

Let $B_{y}$ be the event that the set $S_{y}$ is the whole $\mathbb{Z}_{p}$,
i.e. for every $v$ there is $x$ such that

$0=v(n_{3}\alpha(x)+n_{6}x+\lambda_{2})+\left(y(n_{4}\alpha(x)+n_{7}x+\mu_{2})+\alpha(x)(n_{1}\alpha(x)+n_{2}x+\lambda_{1})+n_{5}x^{2}+\mu_{1}x\right).$
(6)

Suppose that $B_{y}$ occurs. We cannot use the same $x$ for two values of $v$,
so by counting, for every $v$, we have exactly one $x=x(v)$ such that (6)
holds. Suppose that we already know this permutation $x(v)=\pi(v)$. The
equation is further equivalent to

$n_{1}\alpha(\pi(v))^{2}+\alpha(\pi(v))(n_{2}\pi(v)+n_{4}y+n_{3}v+\lambda_{1})+n_{5}\pi(v)^{2}+n_{6}\pi(v)v+n_{7}\pi(v)y+\mu_{1}\pi(v)+y\mu_{2}+v\lambda_{2}=0.$

Hence, for every $v$, we know that $\alpha(\pi(v))$ must take one of the two
values depending only on $v$, since $n_{1}\not=0$. So, given $\pi$, there are
at most $2^{p}$ choices for $\alpha$. Hence, the probability of $B_{y}$ is
$\mathbb{P}(B_{y})\leq p!2^{p}/(p-1)^{p}$. By Stirling’s formula,

$\mathbb{P}(B_{y})=O\left(\sqrt{p}\left(\frac{2}{e}\right)^{p}\right).$

By the union bound, the probability $\mathbb{P}(\cup_{y}B_{y})=o(1)$, so there
is a choice of $\alpha$ such that for all $y$ we have
$S_{y}\not=\mathbb{Z}_{p}$. For such $\alpha$, we can define $\beta$ so that
the expression does not attain every value, proving the lemma. ∎

Returning to our main argument, the case when the quadratic part is of the
form

$(\alpha(x)+c_{1}x)(\alpha(x)+c_{2}x)+(\alpha(x)+c_{3}x)(\beta(y)+c_{4}y)+(\alpha(x)+c_{5}x)(\beta(y)+c_{6}y).$

follows directly from Corollary 6.3, since $n_{1}=1,n_{3}=2$.

###  6.2 $E$ has three variables

Finally, we address the case when the quadratic part of $E$ has exactly three
variables. Once again, we only need to consider the situation when $G_{E}$ has
a cycle. We know that $G_{E}$ is a graph on three vertices, with $v_{is}+e\leq
3$. The only there such graphs that have cycles are $xy,xy$ (a repeated edge
and an isolated vertex), $xy,xy,xz$ (a repeated edge and an additional edge)
and $xy,yz,zx$ (a cycle of length 3).

$G_{E}$ is a repeated edge.In this case, the quadratic part of the expression
is w.l.o.g.

$(\alpha(x)+c_{1}x)(\beta(y)+c_{2}y)+(\alpha(x)+c_{3}x)(\beta(y)+c_{4}y)+(\gamma(z)+c_{5}z)(\gamma(z)+c_{6}z).$

If $c_{1}=c_{3}$ or $c_{2}=c_{4}$, we can further factorize the expression and
apply the Proposition 5.5, to finish the proof. Thus assume that
$c_{1}\not=c_{3}$ and $c_{2}\not=c_{4}$.
Let the linear part of the expression be
$\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta(y)+\mu_{2}y+\lambda_{3}\gamma(z)+\mu_{3}z$.
Fix a prime $p$, and apply Lemma 4.6 to the expression

$(\alpha(x)+c_{1}x)(\beta(y)+c_{2}y)+(\alpha(x)+c_{3}x)(\beta(y)+c_{4}y)+\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta(y)+\mu_{2}y$

to make it constant. Hence, it remains to pick
$\gamma\colon\mathbb{Z}_{p}\to\mathbb{Z}_{p}$ so that the expression

$(\gamma(z)+c_{5}z)(\gamma(z)+c_{6}z)+\lambda_{3}\gamma(z)+\mu_{3}z$

attains a small number of values, which we can ensure if we apply Lemma 5.2
for each $z$ to the polynomial
$\gamma(z)^{2}+(c_{5}z+c_{6}z+\lambda_{3})\gamma(z)+c_{5}c_{6}z^{2}+\mu_{3}z$.
Provided $p$ is large enough, $\gamma(z)$ can be chosen so that the value of
the polynomial is small. This completes the proof in this case.

$G_{E}$ is a 3-cycle. In this case, the quadratic part of $E$ has three mixed
terms, one for each pair of variables among $x,y,z$. More precisely, it is

$(\alpha(x)+c_{1}x)(\beta(y)+c_{2}y)+(\beta(y)+c_{3}y)(\gamma(z)+c_{4}z)+(\gamma(z)+c_{5}z)(\alpha(x)+c_{6}x),$

where $c_{1},\dots,c_{6}\in\\{0,1\\}$. Let the linear part be

$\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta(y)+\mu_{2}y+\lambda_{3}\gamma(z)+\mu_{3}z.$

First, assume that no further factorization is possible, i.e.
$c_{1}\not=c_{6},c_{2}\not=c_{3}$ and $c_{4}\not=c_{5}$. We set
$\alpha(x)=-c_{1}x+d_{1},\beta(y)=-c_{3}y+d_{2},\gamma(z)=-c_{5}z+d_{3}$, so
that the expression becomes

$\begin{split}d_{1}((c_{2}-c_{3})y+d_{2})&+d_{2}((c_{4}-c_{5})z+d_{3})+d_{3}((c_{6}-c_{1})x+d_{1})+(\mu_{1}-c_{1}\lambda_{1})x+(\mu_{2}-c_{3}\lambda_{2})y+(\mu_{3}-c_{5}\lambda_{3})z\\\
&+(\lambda_{1}d_{1}+\lambda_{2}d_{2}+\lambda_{3}d_{3}).\end{split}$

Rearranging further,

$\begin{split}&x(d_{3}(c_{6}-c_{1})+\mu_{1}-c_{1}\lambda_{1})+y(d_{1}(c_{2}-c_{3})+\mu_{2}-c_{3}\lambda_{2})+z(d_{2}(c_{4}-c_{5})+\mu_{3}-c_{5}\lambda_{3})\\\
+&(\lambda_{1}d_{1}+\lambda_{2}d_{2}+\lambda_{3}d_{3}+d_{1}d_{2}+d_{2}d_{3}+d_{3}d_{1}).\end{split}$

Setting $d_{1}=\frac{\mu_{2}-c_{3}\lambda_{2}}{c_{3}-c_{2}}$,
$d_{2}=\frac{\mu_{3}-c_{5}\lambda_{3}}{c_{5}-c_{4}}$ and
$d_{3}=\frac{\mu_{1}-c_{1}\lambda_{1}}{c_{1}-c_{6}}$, the expression becomes
constant.

Now, suppose that w.l.o.g. $c_{1}=c_{6}$. Assume for now that
$(c_{3}-c_{2})(c_{4}-c_{5})=0$, we will address the case when this product
does not vanish later. The expression becomes

$(\alpha(x)+c_{1}x)(\beta(y)+c_{2}y+\gamma(z)+c_{5}z)+(\beta(y)+c_{3}y)(\gamma(z)+c_{4}z)+\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta(y)+\mu_{2}y+\lambda_{3}\gamma(z)+\mu_{3}z.$

We use the identification of coordinates approach. We will take
$q=p_{1}p_{2}p_{3}$, where $p_{1}<p_{2}<p_{3}<2p_{1}$ are arbitrarily large
primes. Identify
$\mathbb{Z}_{q}\cong\mathbb{Z}_{p_{1}}\oplus\mathbb{Z}_{p_{2}}\oplus\mathbb{Z}_{p_{3}}$.
Our first step is to set

$\alpha_{1}(x)=-c_{1}x_{1},\beta_{1}(y)=-c_{3}y_{1}+1-\lambda_{3},\alpha_{2}(x)=-c_{1}x_{2},\gamma_{2}(z)=-c_{4}z_{2}+1-\lambda_{2}.$

This way, the quadratic terms vanish in the first two coordinates, and we
still have freedom of choosing $\beta_{2},\gamma_{1}$ to cancel the linear
terms in $y,z$. We want to do the same for $\alpha_{3}$, so we set
$\beta_{3}(y)=-c_{2}y_{3}+1-\lambda_{1},\gamma_{3}(z)=-c_{5}z_{3}$. However,
with such a choice, the third coordinate of the expression is

$\begin{split}&(1-\lambda_{1})(\alpha_{3}(x)+c_{1}x_{3})+((c_{3}-c_{2})y_{3}+1-\lambda_{1})((c_{4}-c_{5})z_{3})+\lambda_{1}\alpha_{3}(x)+\mu_{1}x_{3}+y_{3}(\mu_{2}-\lambda_{2}c_{2})+z_{3}(\mu_{3}-\lambda_{3}c_{5})\\\
+&\lambda_{2}(1-\lambda_{1})\\\
=&\alpha_{3}(x)+((1-\lambda_{1})c_{1}+\mu_{1})x_{3}+(c_{3}-c_{2})(c_{4}-c_{5})y_{3}z_{3}+(\mu_{2}-\lambda_{2}c_{2})y_{3}+(\mu_{3}-\lambda_{3}c_{5}+(1-\lambda_{1})(c_{4}-c_{5}))z_{3}+\lambda_{2}(1-\lambda_{1}).\end{split}$

Since $(c_{3}-c_{2})(c_{4}-c_{5})=0$, the expression becomes

$\begin{split}(&(\mu_{1}-c_{1}\lambda_{1})x_{1}+(\mu_{2}-c_{3}\lambda_{2})y_{1}+\gamma_{1}(z)+(\mu_{3}+(1-\lambda_{3})c_{4})z_{1}+\lambda_{2}(1-\lambda_{3})\\\
&(\mu_{1}-c_{1}\lambda_{1})x_{2}+\beta_{2}(y)+(\mu_{2}+c_{3}(1-\lambda_{2}))y_{2}+(\mu_{3}-c_{4}\lambda_{3})z_{2}+\lambda_{3}(1-\lambda_{2})\\\
&\alpha_{3}(x)+((1-\lambda_{1})c_{1}+\mu_{1})x_{3}+(\mu_{2}-\lambda_{2}c_{2})y_{3}+(\mu_{3}-\lambda_{3}c_{5}+1-\lambda_{1})z_{3}+\lambda_{2}(1-\lambda_{1})).\end{split}$

We may now apply the identification of coordfinates idea, using Proposition
5.4, to finish the proof in this case.

Now assume that $(c_{3}-c_{2})(c_{4}-c_{5})\not=0$. We shall take
$q=p_{1}p_{2}p_{3}p_{4}p_{5}$ and use the additional fourth and fifth
coordinates to cancel out the $y_{3}z_{3}$ term. Also, using the prime number
theorem, we can find arbitrarily large primes such that
$p_{1}<\dots<p_{5}<p_{1}+O(\log p_{i})$. In the work below it will be
essential that all the primes are close in value (although it will not be
important to have them this close). Writing $E$ also for the resulting map
defined by $\alpha,\beta,\gamma$ and the expression, our aim is to show that

$\sum_{i=1}^{5}\operatorname{mod}_{p_{i},p_{3}}(E_{i})$

takes few values in $\mathbb{Z}_{p_{3}}$.
We use the same choices of
$\alpha_{1},\alpha_{2},\beta_{1},\beta_{3},\gamma_{2},\gamma_{3}$ as in the
case when $(c_{3}-c_{2})(c_{4}-c_{5})=0$. Next, we set
$\alpha_{4}(x)=-c_{1}x_{4},\beta_{4}(y)=-\operatorname{mod}_{p_{3},p_{4}}(y_{3})-c_{3}y_{4},\gamma_{4}(y)=\operatorname{mod}_{p_{3},p_{4}}(z_{3})-c_{4}z_{4}$.
Observe that

$\begin{split}&\operatorname{mod}_{p_{4},p_{3}}\left((\beta_{4}(y)+c_{3}y_{4})(\gamma_{4}(y)+c_{4}z_{4})\right)+\operatorname{mod}_{p_{3},p_{3}}(y_{3}z_{3})=\\\
&\operatorname{mod}_{p_{4},p_{3}}(-\operatorname{mod}_{p_{3},p_{4}}(y_{3})\operatorname{mod}_{p_{3},p_{4}}(z_{3}))+y_{3}z_{3}=\\\
&\pi_{p_{3}}\circ\iota_{p_{4}}(-\pi_{p_{4}}\circ\iota_{p_{3}}(y_{3})\pi_{p_{4}}\circ\iota_{p_{3}}(z_{3}))+y_{3}z_{3}\end{split}$

Let $\overline{y_{3}}=\iota_{p_{3}}(y_{3})$ and
$\overline{z_{3}}=\iota_{p_{3}}(z_{3})$. Hence
$\overline{y_{3}},\overline{z_{3}}\in\\{0,1,\dots,p_{3}-1\\}$ are integers
such that $\pi_{p_{3}}(\overline{y_{3}})=y_{3}$ and
$\pi_{p_{3}}(\overline{z_{3}})=z_{3}$ hold. We also have
$\iota_{p_{4}}(-\pi_{p_{4}}\circ\iota_{p_{3}}(y_{3})\pi_{p_{4}}\circ\iota_{p_{3}}(z_{3}))=\iota_{p_{4}}(-\pi_{p_{4}}(\overline{y_{3}})\pi_{p_{4}}(\overline{z_{3}}))=\iota_{p_{4}}(\pi_{p_{4}}(-\overline{y_{3}}\hskip
1.0pt\overline{z_{3}}))$. But the
$\iota_{p_{4}}(\pi_{p_{4}}(-\overline{y_{3}}\hskip 1.0pt\overline{z_{3}}))$ is
an integer $w\in\\{0,1,\dots,p_{4}-1\\}$ such that
$\pi_{p_{4}}(w)=\pi_{p_{4}}(-\overline{y_{3}}\hskip 1.0pt\overline{z_{3}})$,
thus $w=-\overline{y_{3}}\hskip 1.0pt\overline{z_{3}}+p_{4}t$, for
$t=\lceil\frac{\overline{y_{3}}\hskip 1.0pt\overline{z_{3}}}{p_{4}}\rceil$.
Therefore, with this choice of $t$ we have

$\begin{split}&\operatorname{mod}_{p_{4},p_{3}}((\beta_{4}(y)+c_{3}y_{4})(\gamma_{4}(y)+c_{4}z_{4}))+\operatorname{mod}_{p_{3},p_{3}}(y_{3}z_{3})=\\\
&\pi_{p_{3}}\circ\iota_{p_{4}}(-\pi_{p_{4}}\circ\iota_{p_{3}}(y_{3})\pi_{p_{4}}\circ\iota_{p_{3}}(z_{3}))+y_{3}z_{3}=\\\
&\pi_{p_{3}}(-\overline{y_{3}}\hskip
1.0pt\overline{z_{3}}+p_{4}t)+\pi_{p_{3}}(\overline{y_{3}})\pi_{p_{3}}(\overline{z_{3}})=\\\
&\pi_{p_{3}}(p_{4}t)=\pi_{p_{3}}((p_{4}-p_{3})t)\end{split}$

Proceeding further, we use the fifth coordinate to approximate
$(p_{4}-p_{3})t$. To this end, write $M=\lfloor\sqrt{p_{4}}\rfloor$,
$\overline{y_{3}}=uM+u^{\prime},\overline{z_{3}}=vM+v^{\prime}$, where
$u^{\prime},v^{\prime}\in\\{0,1,\dots,M-1\\}$, $u,v=O(M)$. Observe that $uv$
is a good approximation to $t$

$\begin{split}&\left|t-uv\right|=\left|\lceil\frac{\overline{y_{3}}\hskip
1.0pt\overline{z_{3}}}{p_{4}}\rceil-uv\right|\leq
1+\left|\frac{\overline{y_{3}}\hskip
1.0pt\overline{z_{3}}-p_{4}uv}{p_{4}}\right|=1+\left|\frac{(uM+u^{\prime})(vM+v^{\prime})-p_{4}uv}{p_{4}}\right|\\\
\leq&1+\left|\frac{u^{\prime}vM+uv^{\prime}M+u^{\prime}v^{\prime}}{p_{4}}\right|+\left|\frac{uv(p_{4}-M^{2})}{p_{4}}\right|\leq
C_{1}\sqrt{p_{4}}\end{split}$

for some absolute constant $C_{1}$, since
$u,v,u^{\prime},v^{\prime},M,|p_{4}-M^{2}|=O(\sqrt{p_{4}})$. Therefore, we set
$\alpha_{5}=-c_{1}x_{5},\beta_{5}(y)=-\pi_{p_{5}}(u)-c_{3}y_{5},\gamma_{5}(z)=\pi_{p_{5}}(v(p_{4}-p_{3}))-c_{4}z_{5}$.
Note that $\beta_{5},\gamma_{5}$ are well defined, as $u$ depends on $y$ only,
and $v$ depends on $z$ only. With $\beta_{5}$ and $\gamma_{5}$ so defined we
have

$\begin{split}&\operatorname{mod}_{p_{5},p_{3}}((\beta_{5}(y)+c_{3}y_{5})(\gamma_{5}(z)+c_{4}z_{5}))+\pi_{p_{3}}(t(p_{4}-p_{3}))=\\\
&\pi_{p_{3}}(\iota_{p_{5}}(-\pi_{p_{5}}(u)\pi_{p_{5}}(v(p_{4}-p_{3})))+t(p_{4}-p_{3}))=\\\
&\pi_{p_{3}}(\iota_{p_{5}}(\pi_{p_{5}}(-uv(p_{4}-p_{3})))+t(p_{4}-p_{3}))\end{split}$

We also have that $\iota_{p_{5}}(\pi_{p_{5}}(-uv(p_{4}-p_{3})))$ is an integer
$s\in\\{0,1,\dots,p_{5}-1\\}$ such that
$\pi_{p_{5}}(s)=\pi_{p_{5}}(-uv(p_{4}-p_{3}))$, thus
$s=-uv(p_{4}-p_{3})+p_{5}t^{\prime}$, where
$t^{\prime}=\lceil\frac{uv(p_{4}-p_{3})}{p_{5}}\rceil\leq C_{2}\log p_{3}$,
for an absolute constant $C_{2}$. Therefore,

$\begin{split}&\operatorname{mod}_{p_{5},p_{3}}((\beta_{5}(y)+c_{3}y_{5})(\gamma_{5}(z)+c_{4}z_{5}))+\pi_{p_{3}}(t(p_{4}-p_{3}))=\\\
&\pi_{p_{3}}(\iota_{p_{5}}(\pi_{p_{5}}(-uv(p_{4}-p_{3})))+t(p_{4}-p_{3}))=\\\
&\pi_{p_{3}}(-uv(p_{4}-p_{3})+p_{5}t^{\prime}+t(p_{4}-p_{3}))=\\\
&\pi_{p_{3}}((t-uv)(p_{4}-p_{3})+p_{5}t^{\prime})\end{split}$

Summing up the work done so far we conclude that

$\begin{split}\operatorname{mod}_{p_{3},p_{3}}(&y_{3}z_{3})+\operatorname{mod}_{p_{4},p_{3}}(\beta_{4}(y)+c_{3}y_{4})(\gamma_{4}(y)+c_{4}z_{4}))+\operatorname{mod}_{p_{5},p_{3}}((\beta_{5}(y)+c_{3}y_{5})(\gamma_{5}(z)+c_{4}z_{5}))\\\
=&y_{3}z_{3}+\operatorname{mod}_{p_{4},p_{3}}(-\operatorname{mod}_{p_{3},p_{4}}(y_{3})\operatorname{mod}_{p_{3},p_{4}}(z_{3}))+\operatorname{mod}_{p_{5},p_{3}}(\pi_{p_{5}}(-uv(p_{4}-p_{3})))\in
S_{1},\end{split}$

where $S_{1}\subset\mathbb{Z}_{p_{3}}$ is the set defined by
$\\{\pi_{p_{3}}(a(p_{4}-p_{3})+p_{5}b)\colon a,b\in\mathbb{Z},|a|\leq
C_{1}\sqrt{p_{4}},|b|\leq C_{2}\log p_{3}\\}$. In particular
$|S_{1}|=O(\sqrt{p_{3}}\log^{2}p_{3})$. Finally, we put everything together,
using the Lemma 4.5. Recall the definitions (the maps $\beta_{4},\gamma_{4}$
and $\gamma_{5}$ below are slightly modified to cancel the term
$(c_{3}-c_{2})(c_{4}-c_{5})y_{3}z_{3}$ instead of just $y_{3}z_{3}$)

$\begin{split}\alpha_{1}(x)&=-c_{1}x_{1},\beta_{1}(y)=-c_{3}y_{1}+1-\lambda_{3},\\\
\alpha_{2}(x)&=-c_{1}x_{2},\gamma_{2}(z)=-c_{4}z_{2}+1-\lambda_{2},\\\
\beta_{3}(y)&=-c_{2}y_{3}+1-\lambda_{1},\gamma_{3}(z)=-c_{5}z_{3},\\\
\alpha_{4}(x)&=-c_{1}x_{4},\beta_{4}(y)=-(c_{3}-c_{2})\operatorname{mod}_{p_{3},p_{4}}(y_{3})-c_{3}y_{4},\gamma_{4}(y)=(c_{4}-c_{5})\operatorname{mod}_{p_{3},p_{4}}(z_{3})-c_{4}z_{4},\\\
\alpha_{5}&=-c_{1}x_{5},\beta_{5}(y)=-\pi_{p_{5}}(u)-c_{3}y_{5},\gamma_{5}(z)=\pi_{p_{5}}(v(p_{4}-p_{3})(c_{3}-c_{2})(c_{4}-c_{5}))-c_{4}z_{5}.\end{split}$

Thus,

$\begin{split}\sum_{i=1}^{5}&\operatorname{mod}_{p_{i},p_{3}}(E_{i})=\sum_{i=1}^{5}\operatorname{mod}_{p_{i},p_{3}}((\alpha_{i}(x)+c_{1}x_{i})(\beta_{i}(y)+c_{2}y_{i}+\gamma_{i}(z)+c_{5}z_{i})+(\beta_{i}(y)+c_{3}y_{i})(\gamma_{i}(z)+c_{4}z_{i})\\\
&+\lambda_{1}\alpha_{i}(x)+\mu_{1}x_{i}+\lambda_{2}\beta_{i}(y)+\mu_{2}y_{i}+\lambda_{3}\gamma_{i}(z)+\mu_{3}z_{i})\\\
=&\operatorname{mod}_{p_{1},p_{3}}(\gamma_{1}(z)+(\mu_{1}-c_{1}\lambda_{1})x_{1}+(\mu_{2}-c_{3}\lambda_{2})y_{1}+(\mu_{3}+c_{4}(1-\lambda_{3}))z_{1}+\lambda_{2}(1-\lambda_{3}))\\\
&+\operatorname{mod}_{p_{2},p_{3}}(\beta_{2}(y)+(\mu_{1}-c_{1}\lambda_{1})x_{2}+(\mu_{2}+c_{3}(1-\lambda_{2}))y_{2}+(\mu_{3}-c_{4}\lambda_{3})z_{2}+\lambda_{3}(1-\lambda_{2}))\\\
&+\alpha_{3}(x)+y_{3}z_{3}(c_{3}-c_{2})(c_{4}-c_{5})+x_{3}(c_{1}(1-\lambda_{1})+\mu_{1})+(\mu_{2}-\lambda_{2}c_{2})y_{3}+((1-\lambda_{1})(c_{4}-c_{5})-c_{5}\lambda_{3}+\mu_{3})z_{3}\\\
&+\lambda_{2}(1-\lambda_{1})\\\
&+\operatorname{mod}_{p_{4},p_{3}}(-(c_{3}-c_{2})(c_{4}-c_{5})\operatorname{mod}_{p_{3},p_{4}}(y_{3})\operatorname{mod}_{p_{3},p_{4}}(z_{3})+(\mu_{1}-\lambda_{1}c_{1})x_{4}-(c_{3}-c_{2})\lambda_{2}\operatorname{mod}_{p_{3},p_{4}}(y_{3})\\\
&+(\mu_{2}-c_{3}\lambda_{2})y_{4}+(c_{4}-c_{5})\lambda_{3}\operatorname{mod}_{p_{3},p_{4}}(z_{3})+(\mu_{3}-\lambda_{3}c_{4})z_{4})\\\
&+\operatorname{mod}_{p_{5},p_{3}}(-\pi_{p_{5}}(u)\pi_{p_{5}}(v(p_{4}-p_{3})(c_{3}-c_{2})(c_{4}-c_{5}))+(\mu_{1}-\lambda_{1}c_{1})x_{5}-\lambda_{2}\pi_{p_{5}}(u)+(\mu_{2}-\lambda_{2}c_{3})y_{5}\\\
&+\lambda_{3}\pi_{p_{5}}(v(p_{4}-p_{3})(c_{3}-c_{2})(c_{4}-c_{5}))+(\mu_{5}-\lambda_{3}c_{4})z_{5})\\\
\overset{O(1)}{=}&\pi_{p_{3}}(\iota_{p_{3}}(\alpha_{3}(x))+(\mu_{1}-c_{1}\lambda_{1})\iota_{p_{1}}(x_{1})+(\mu_{1}-c_{1}\lambda_{1})\iota_{p_{2}}(x_{2})+(c_{1}(1-\lambda_{1})+\mu_{1})\iota_{p_{3}}(x_{3})+(\mu_{1}-\lambda_{1}c_{1})\iota_{p_{4}}(x_{4})\\\
&+(\mu_{1}-\lambda_{1}c_{1})\iota_{p_{5}}(x_{5})\\\
&+\iota_{p_{2}}(\beta_{2}(y))+(\mu_{2}-c_{3}\lambda_{2})\iota_{p_{1}}(y_{1})+(\mu_{2}+c_{3}(1-\lambda_{2}))\iota_{p_{2}}(y_{2})+(\mu_{2}-\lambda_{2}c_{2})\iota_{p_{3}}(y_{3})-(c_{3}-c_{2})\lambda_{2}\iota_{p_{4}}(\operatorname{mod}_{p_{3},p_{4}}(y_{3}))\\\
&+(\mu_{2}-c_{3}\lambda_{2})\iota_{p_{4}}(y_{4})-\lambda_{2}\iota_{p_{5}}(\pi_{p_{5}}(u))+(\mu_{2}-\lambda_{2}c_{3})\iota_{p_{5}}(y_{5})\\\
&+\iota_{p_{1}}(\gamma_{1}(z))+(\mu_{3}+c_{4}(1-\lambda_{3}))\iota_{p_{1}}(z_{1})+(\mu_{3}-c_{4}\lambda_{3})\iota_{p_{2}}(z_{2})+((1-\lambda_{1})(c_{4}-c_{5})-c_{5}\lambda_{3}+\mu_{3})\iota_{p_{3}}(z_{3})\\\
&+(c_{4}-c_{5})\lambda_{3}\iota_{p_{4}}(\operatorname{mod}_{p_{3},p_{4}}(z_{3}))+(\mu_{3}-\lambda_{3}c_{4})\iota_{p_{4}}(z_{4})+\lambda_{3}\iota_{p_{5}}(\pi_{p_{5}}(v(p_{4}-p_{3})(c_{3}-c_{2})(c_{4}-c_{5})))+(\mu_{5}-\lambda_{3}c_{4})\iota_{p_{5}}(z_{5}))\\\
&+(c_{3}-c_{2})(c_{4}-c_{5})(y_{3}z_{3}-\operatorname{mod}_{p_{4},p_{3}}(\operatorname{mod}_{p_{3},p_{4}}(y_{3})\operatorname{mod}_{p_{3},p_{4}}(z_{3}))-\operatorname{mod}_{p_{5},p_{3}}(\pi_{p_{5}}(uv(p_{4}-p_{3})))).\end{split}$

Finally, we set $\alpha_{3},\beta_{2},\gamma_{1}$ to cancel the linear $x,y,z$
terms respectively:

$\begin{split}\alpha_{3}(x)&=-\pi_{p_{3}}((\mu_{1}-c_{1}\lambda_{1})\iota_{p_{1}}(x_{1})+(\mu_{1}-c_{1}\lambda_{1})\iota_{p_{2}}(x_{2})+(c_{1}(1-\lambda_{1})+\mu_{1})\iota_{p_{3}}(x_{3})+(\mu_{1}-\lambda_{1}c_{1})\iota_{p_{4}}(x_{4})\\\
&+(\mu_{1}-\lambda_{1}c_{1})\iota_{p_{5}}(x_{5}))\\\
\beta_{2}(y)&=-\pi_{p_{2}}((\mu_{2}-c_{3}\lambda_{2})\iota_{p_{1}}(y_{1})+(\mu_{2}+c_{3}(1-\lambda_{2}))\iota_{p_{2}}(y_{2})+(\mu_{2}-\lambda_{2}c_{2})\iota_{p_{3}}(y_{3})-(c_{3}-c_{2})\lambda_{2}\iota_{p_{4}}(\operatorname{mod}_{p_{3},p_{4}}(y_{3}))\\\
&+(\mu_{2}-c_{3}\lambda_{2})\iota_{p_{4}}(y_{4})-\lambda_{2}\iota_{p_{5}}(\pi_{p_{5}}(u))+(\mu_{2}-\lambda_{2}c_{3})\iota_{p_{5}}(y_{5})))\\\
\gamma_{1}(z)&=-\pi_{p_{1}}((\mu_{3}+c_{4}(1-\lambda_{3}))\iota_{p_{1}}(z_{1})+(\mu_{3}-c_{4}\lambda_{3})\iota_{p_{2}}(z_{2})+((1-\lambda_{1})(c_{4}-c_{5})-c_{5}\lambda_{3}+\mu_{3})\iota_{p_{3}}(z_{3})\\\
&+(c_{4}-c_{5})\lambda_{3}\iota_{p_{4}}(\operatorname{mod}_{p_{3},p_{4}}(z_{3}))+(\mu_{3}-\lambda_{3}c_{4})\iota_{p_{4}}(z_{4})+\lambda_{3}\iota_{p_{5}}(\pi_{p_{5}}(v(p_{4}-p_{3})(c_{3}-c_{2})(c_{4}-c_{5})))\\\
&+(\mu_{5}-\lambda_{3}c_{4})\iota_{p_{5}}(z_{5})))\end{split}$

With this choice of $\alpha,\beta,\gamma$ we have

$\sum_{i=1}^{5}\operatorname{mod}_{p_{i},p_{3}}(E_{i})\overset{O(1)}{=}(c_{3}-c_{2})(c_{4}-c_{5})(y_{3}z_{3}-\operatorname{mod}_{p_{4},p_{3}}(\operatorname{mod}_{p_{3},p_{4}}(y_{3})\operatorname{mod}_{p_{3},p_{4}}(z_{3}))-\operatorname{mod}_{p_{5},p_{3}}(\pi_{p_{5}}(uv(p_{4}-p_{3}))))$

which takes small number of values.

$G_{E}$ is has a repeated edge and another single edge. In this case, the
quadratic part of the expression is w.l.o.g.

$(\alpha(x)+c_{1}x)(\beta(y)+c_{2}y)+(\alpha(x)+c_{3}x)(\beta(y)+c_{4}y)+(\alpha(x)+c_{5}x)(\gamma(z)+c_{6}z).$

If $c_{1}=c_{3}$ or $c_{2}=c_{4}$, we can further factorize the expression and
apply the Proposition 5.5, to finish the proof. Thus assume that
$c_{1}\not=c_{3}$ and $c_{2}\not=c_{4}$. Since all $c_{i}\in\\{0,1\\}$, we
must have $c_{5}\in\\{c_{1},c_{3}\\}$, so w.l.o.g. $c_{5}=c_{1}$.

We now discuss a limitation of the usual approach based on the identification
of coordinates idea. Basically, we always try to cancel out the quadratic
terms by taking some of the $\alpha_{i},\beta_{i},\gamma_{i}$ to be affine,
while we use the rest to cancel out the linear terms in $x_{i},y_{i},z_{i}$.
Let us try the same strategy here. Temporarily we work in
$\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}\oplus\dots\oplus\mathbb{Z}_{p}$ to ignore
the difficulties that arise from moving from one modulus to another one. For
technical reasons, we use a slightly unusual indexing of $n+2$ coordinates by
$-1,0,\dots,n$. Start by using the coordinate -1 to get a free $\gamma_{-1}$
which is later used to cancel the linear terms involving $z$. Thus, we set
$\alpha_{-1}(x)=-c_{1}x_{-1}$ and $\beta_{-1}(y)=-c_{4}y_{-1}$. Similarly, try
to use the coordinate 0 to get a free $\beta_{0}$ map. Rewriting the
expression as

$\beta(y)(2\alpha(x)+(c_{1}+c_{3})x)+y((c_{2}+c_{4})\alpha(x)+(c_{1}c_{2}+c_{3}c_{4})x)+(\alpha(x)+c_{5}x)(\gamma(z)+c_{6}z),$

we see that we need to set $\alpha_{0}(x)=-\frac{c_{1}+c_{3}}{2}x_{0}+C$, for
a constant $C$ and $\gamma_{0}(z)=-c_{6}z_{0}$. The issue is that we get a
term $x_{0}y_{0}$ with a non-zero coefficient. The natural thing to do now is
to try to cancel somehow this term. During this digression, we forget about
the linear terms (in any case, we can cancel them by remaining free
$\alpha_{i},\beta_{i},\gamma_{i}$).

The most natural thing is to set $\gamma_{i}(z)=-c_{6}z_{i}$ for
$i=1,2,\dots,n$ (as further mixed quadratic terms involving $z$ seem even
harder to cancel). Hence, the question is whether we can find linear maps
$\alpha_{1},\dots,\alpha_{n},\beta_{1},\dots,\beta_{n}$, each a linear
combination of $x_{0},x_{1},\dots,x_{n}$ or $y_{0},y_{1},\dots,y_{n}$ such
that (w.l.o.g. $c_{1}=c_{2}=0$ and $c_{3}=c_{4}=1$)

$\sum_{i=1}^{n}\alpha_{i}(x)\beta_{i}(x)+(\alpha_{i}(x)+x_{i})(\beta_{i}(y)+y_{i})=0.$
(7)

Write $\alpha_{i}(x)=\sum_{j=0}^{n}A_{ij}x_{j}$ and
$\beta_{i}(y)=\sum_{j=0}^{n}B_{ij}y_{j}$. Let $\delta_{ij}$ equal 1 if $i=j$
and zero otherwise. Expanding the (7) we obtain

$\begin{split}\sum_{i=1}^{n}\left(\left(\sum_{j=0}^{n}A_{ij}x_{j}\right)\left(\sum_{k=0}^{n}B_{ik}y_{k}\right)+\left(\sum_{j=0}^{n}(A_{ij}+\delta_{ij})x_{j}\right)\left(\sum_{k=0}^{n}(B_{ik}+\delta_{ik})y_{k}\right)\right)=\\\
\sum_{j=0}^{n}\sum_{k=0}^{n}\left(\sum_{i=1}^{n}2A_{ij}B_{ik}+A_{ij}\delta_{ik}+\delta_{ij}B_{ik}+\delta_{ij}\delta_{ik}\right)x_{j}y_{k}.\end{split}$
(8)

Hence, we require that for every $j,k\in\\{0,1,\dots,n\\}$, which are not both
zero, we have
$\sum_{i=1}^{n}2A_{ij}B_{ik}+A_{ij}\delta_{ik}+\delta_{ij}B_{ik}+\delta_{ij}\delta_{ik}=0$,
while for $j=k=0$ this expression is non-zero (to cancel the initial
$x_{0}y_{0}$ term). We now define two $(n+1)\times(n+1)$ matrices $P,Q$, with
entries indexed by $\\{0,1\dots,n\\}\times\\{0,1,\dots,n\\}$, by setting
$P_{ji}=A_{ij}$ when $i\geq 1$ and $P_{j0}=0$, and $Q_{ik}=B_{ik}$ if $i\geq
1$ and $Q_{0k}=0$. Let $I^{\prime}$ be the matrix of all zeros except
$I^{\prime}_{ii}=1$ for $i\geq 1$, and let $J$ be the matrix consisting of
zeros only, except $J_{00}=1$. We rewrite (8) as a matrix equation

$2PQ+PI^{\prime}+QI^{\prime}+I^{\prime}=\lambda J$

for some non-zero $\lambda$. However, this is the same as

$(2P+I^{\prime})(2Q+I^{\prime})=2\lambda J-I^{\prime}.$

But comparing ranks we have

$\operatorname{rank}(2\lambda
J-I^{\prime})=\operatorname{rank}((2P+I^{\prime})(2Q+I^{\prime}))\leq\operatorname{rank}(2P+I^{\prime})\leq
n<n+1=\operatorname{rank}(2\lambda J-I^{\prime})$

which is a contradiction. Hence, this case requires a different approach.

Finally, we construct the desired maps for this expression. By adding linear
terms to $\alpha,\beta,\gamma$, we may assume that the expression is

$\alpha(x)\beta(y)+(\alpha(x)+c_{1}x)(\beta(y)+c_{2}y)+\alpha(x)\gamma(z)+\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta(y)+\mu_{2}y+\lambda_{3}\gamma(z)+\mu_{3}z$
(9)

for some coefficients
$c_{1},c_{2}\in\\{-1,1\\},\lambda_{1},\lambda_{2},\lambda_{3}\in\mathbb{N}_{0},\mu_{1},\mu_{2},\mu_{3}\in\mathbb{Z}$.
Let us begin by observing that in most cases there is a rather simple
solution, which strangely we could not generalize to work for all choices of
coefficients. Try setting $\alpha(x)=A,\beta(y)=-c_{2}y+B$, for some constants
$A,B$ and suppose we work in $\mathbb{Z}_{q}$, where $q$ is a product of
distinct, arbitrarily large primes (so that all the coefficients and related
expressions are coprime with $q$). With these choices, the expression (9)
becomes

$\begin{split}&A(-c_{2}y+B)+(A+c_{1}x)B+A\gamma(z)+\lambda_{1}A+\mu_{1}x+\lambda_{2}(-c_{2}y+B)+\mu_{2}y+\lambda_{3}\gamma(z)+\mu_{3}z=\\\
&y(-c_{2}A-c_{2}\lambda_{2}+\mu_{2})+x(c_{1}B+\mu_{1})+\gamma(z)(A+\lambda_{3})+\mu_{3}z+(2AB+\lambda_{1}A+\lambda_{2}B).\end{split}$

Further, set $B=-\mu_{1}c_{1}$, (recall that $c_{1},c_{2}\in\\{-1,1\\}$ so
$c_{1}^{-1}=c_{1},c_{2}^{-1}=c_{2}$) so that the coefficient of $x$ above
vanishes. We try to pick $A$ such that coefficient of $y$ also becomes zero,
setting $A=c_{2}\mu_{2}-\lambda_{2}$. If $A+\lambda_{3}\not=0$, then we can
pick $\gamma_{3}$ to cancel the $z$ term, and the expression actually becomes
constant. Otherwise, assume that $c_{2}\mu_{2}-\lambda_{2}+\lambda_{3}=0$. In
this case, we prove the following proposition, and the full result is then a
consequence of a simple number-theoretic calculation.

######  Proposition 6.4.

Let
$c_{1},c_{2},\lambda_{1},\lambda_{2},\lambda_{3},\mu_{1},\mu_{2},\mu_{3}\in\mathbb{Z}$
be some fixed coefficients, such that $c_{1},c_{2}\in\\{-1,1\\}$ and
$c_{2}\mu_{2}-\lambda_{2}+\lambda_{3}-c_{2}\not=0$. Then, for all sufficiently
large primes $p,q$, obeying $q<p<2q$, we may find maps
$\alpha,\beta,\gamma\colon\mathbb{Z}_{pq}\to\mathbb{Z}_{pq}$ such that the
expression (9) misses at least $p-q$ values.

###### Proof.

As always, $\mathbb{Z}_{pq}$ is viewed as
$\mathbb{Z}_{p}\oplus\mathbb{Z}_{q}$. In the first coordinate, we set
$\alpha_{1}(x)=c_{2}\mu_{2}-\lambda_{2}-c_{2},\beta_{1}(y)=-c_{2}y-\mu_{1}c_{1},\gamma_{1}(z)=\frac{-\mu_{3}z+\delta_{1}(z)+D}{c_{2}\mu_{2}+\lambda_{3}-\lambda_{2}-c_{2}}$,
with $\delta_{1}(z)$ to be chosen and a constant $D$. After a suitable choice
of $D$, the first coordinate of the expression becomes $y_{1}-\delta_{1}(z)$.
On the other hand, we shall use the second coordinate to evade some of the
values. To this end, we generalize the Lemma 6.2, with a similar proof.

######  Lemma 6.5.

Let $S$ be a set, and $q$ a prime. Let $f\colon S\to\mathbb{Z}_{q}$ be any
map, and let
$c_{1},c_{2},\lambda_{1},\lambda_{2},\mu_{1},\mu_{2}\in\mathbb{Z}$ be any
coefficients. Then, provided $|S|q^{2}\cdot q!<(q-1)^{q}$ we may pick
$\alpha,\beta_{s}\colon\mathbb{Z}_{q}\to\mathbb{Z}_{q}$ for all $s\in S$, such
that

$\alpha(x)\beta_{s}(y)+(\alpha(x)+c_{1}x)(\beta_{s}(y)+c_{2}y)+\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta_{s}(y)+\mu_{2}y+f(s)$
(10)

never takes value zero.

###### Proof of Lemma 6.5..

We proceed similarly as in the proof of Lemma 6.2, starting by defining each
$\alpha(x)$ independently, uniformly at random in
$\mathbb{Z}_{q}\setminus\\{-2^{-1}(c_{1}x+\lambda_{2})\\}$, with this single
value omitted for technical reasons.
For each $y$ and $s\in S$, we want to pick $\beta_{s}(y)$, so that (10) does
not vanish for any $x$. Let $E_{y,s}$ be the event that we cannot do this,
i.e. that, having fixed $y,s$ for every value $\beta$, we can find $x$ such
that

$\alpha(x)\beta+(\alpha(x)+c_{1}x)(\beta+c_{2}y)+\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta+\mu_{2}y+f(s).$
(11)

If $E_{y,s}$ occurs, observe that (11) cannot hold for distinct
$\beta_{1},\beta_{2}$ with the same choice of $x$, since this equation can be
rewritten as

$\beta(2\alpha(x)+c_{1}x+\lambda_{2})+y(c_{2}\alpha(x)+c_{1}c_{2}x+\mu_{2})+\lambda_{1}\alpha(x)+\mu_{1}x+f(s)$

and by the choice of $\alpha$, the coefficient of $\beta$ is never zero.
Hence, if $\pi\colon\mathbb{Z}_{q}\to\mathbb{Z}_{q}$ is the map that sends
each $\beta$ to the corresponding value of $x$ for which the (11) vanishes, we
must have $\pi$ injective, which is thus a bijection.
Suppose furthermore that we know $\pi$ as well. Note that in this case we can
almost determine $\alpha$. Indeed, for all $\beta$ we have

$\begin{split}0=&\beta(2\alpha(\pi(\beta))+c_{1}\pi(\beta)+\lambda_{2})+y(c_{2}\alpha(\pi(\beta))+c_{1}c_{2}\pi(\beta)+\mu_{2})+\lambda_{1}\alpha(\pi(\beta))+\mu_{1}\pi(\beta)+f(s)\\\
=&\alpha(\pi(\beta))(2\beta+yc_{2}+\lambda_{1})+\beta(c_{1}\pi(\beta)+\lambda_{2})+y(c_{1}c_{2}\pi(\beta)+\mu_{2})+\mu_{1}\pi(\beta)+f(s)\end{split}$

Substituting $\beta=\pi^{-1}(\beta^{\prime})$, we obtain

$\alpha(\beta^{\prime})(2\pi^{-1}(\beta^{\prime})+yc_{2}+\lambda_{1})+\pi^{-1}(\beta^{\prime})(c_{1}\beta^{\prime}+\lambda_{2})+y(c_{1}c_{2}\beta^{\prime}+\mu_{2})+\mu_{1}\beta^{\prime}+f(s)=0$

for all $\beta^{\prime}\in\mathbb{Z}_{q}$, so $\alpha(\beta^{\prime})$ is
uniquely determined for all $\beta^{\prime}$ such that
$2\pi^{-1}(\beta^{\prime})+yc_{2}+\lambda_{1}\not=0$, i.e. for $q-1$ values.
So there are at most $q$ ways to pick $\alpha$, and in conclusion, the
probability of $E_{y,s}$ is $\mathbb{P}(E_{y,s})\leq q\cdot q!/(q-1)^{q}$.
Finally, we have

$\mathbb{P}(\cup_{y,s}E_{y,s})\leq\sum_{y,s}\mathbb{P}(E_{y,s})\leq|S|q^{2}\frac{q!}{(q-1)^{q}}<1,$

so it is possible to choose $\alpha$ for which all other maps can be defined
so that (10) never vanishes. ∎

Set $\gamma_{2}=0$. Let
$\overline{y_{1}}=\iota_{p}(y_{1}),t=\iota_{q}(\mu_{3}z_{2})\in\mathbb{Z}$. We
define $\delta_{1}(z)=\pi_{p}(t)$, so the first coordinate becomes
$\pi_{p}(\overline{y_{1}}-t)$. We set
$f\colon\mathbb{Z}_{p}\to\mathbb{Z}_{q}$, by
$f(y_{1})=\pi_{q}(\overline{y_{1}})$. Apply Lemma 6.5 to the $\mathbb{Z}_{q}$,
$S=\mathbb{Z}_{p}$, and the expression

$\alpha_{2}(x_{2})\beta_{2,y_{1}}(y_{2})+(\alpha_{2}(x_{2})+c_{1}x_{2})(\beta_{2,y_{1}}(y_{2})+c_{2}y_{2})+\lambda_{1}\alpha_{2}(x_{2})+\mu_{1}x_{2}+\lambda_{2}\beta_{2,y_{1}}(y_{2})+\mu_{2}y_{2}+f(y_{1})$

to define $\alpha_{2},\beta_{2,y_{1}}\colon\mathbb{Z}_{q}\to\mathbb{Z}_{q}$ to
make it non-zero always. Note that we may apply the lemma since
$pq^{2}q!<(q-1)^{q}$, whenever $q<p<2q$, for sufficiently large $q$. We define
$\beta_{2}(y)$ as $\beta_{2,y_{1}}(y_{2})$. Finally, we show that values
$(\pi_{p}(r),-\pi_{q}(r))\in\mathbb{Z}_{p}\oplus\mathbb{Z}_{q}$ are not
attained for $r\in\\{0,1,\dots,p-q-1\\}$.

Suppose that $r\in\\{0,1,\dots,p-q-1\\}$ and suppose that the expression takes
value $(\pi_{p}(r),-\pi_{q}(r))$. Thus, the first coordinate gives
$\pi_{p}(\overline{y_{1}}-t)=\pi_{p}(r)$, so $p$ divides
$\overline{y_{1}}-t-r$, so either $\overline{y_{1}}\leq t+r-p$,
$\overline{y_{1}}=t+r$, or $\overline{y_{1}}\geq t+r+p$. But,
$\overline{y_{1}}\in\\{0,1,\dots,p-1\\},t\in\\{0,1,\dots,q-1\\}$ and
$r\in\\{0,1,\dots,p-q-1\\}$, so we must have $\overline{y_{1}}=t+r$.

Next, let $v$ stand for the value of

$\alpha_{2}(x_{2})\beta_{2,y_{1}}(y_{2})+(\alpha_{2}(x_{2})+c_{1}x_{2})(\beta_{2,y_{1}}(y_{2})+c_{2}y_{2})+\lambda_{1}\alpha_{2}(x_{2})+\mu_{1}x_{2}+\lambda_{2}\beta_{2,y_{1}}(y_{2})+\mu_{2}y_{2}.$

By the definition of $\alpha_{2},\beta_{2,y_{1}}$, we always have
$v+f(y_{1})\not=0$. If the second coordinate equals $-\pi_{q}(r)$, then we
have
$0=v+\mu_{3}z_{2}+\pi_{q}(r)=v+\pi_{q}(t)+\pi_{q}(r)=v+\pi_{q}(t+r)=v+\pi_{q}(\overline{y_{1}})=v+f(y_{1})$,
which is impossible. ∎

######  Corollary 6.6.

Let
$c_{1},c_{2},\lambda_{1},\lambda_{2},\lambda_{3},\mu_{1},\mu_{2},\mu_{3}\in\mathbb{Z}$
be some fixed coefficients, such that $c_{1},c_{2}\in\\{-1,1\\}$ and
$c_{2}\mu_{2}-\lambda_{2}+\lambda_{3}-c_{2}\not=0$. Let $\epsilon>0$ be any
small real. Then, we can find $q$, a product of arbitrarily large distinct
primes and maps $\alpha,\beta,\gamma\colon\mathbb{Z}_{q}\to\mathbb{Z}_{q}$
such that the expression (9) takes at most $\epsilon q$ values in
$\mathbb{Z}_{q}$.

###### Proof.

We proceed as follows. Look at all the primes
$2^{k}<q_{1}<q_{2}<\dots<q_{m}<(1+\frac{1}{3})2^{k}$ and
$(1+\frac{2}{3})2^{k}<p_{1}<p_{2}<\dots<p_{n}<2^{k+1}$. For $k$ sufficiently
large, by the prime number theorem, $n,m\geq\Omega(2^{k}/k)$. For $k$
sufficiently large, pairs of primes $p_{i},q_{i}$ satisfy the conditions of
Proposition 6.4, which we apply to obtain
$\alpha_{i},\beta_{i},\gamma_{i}\colon\mathbb{Z}_{p_{i}q_{i}}\to\mathbb{Z}_{p_{i}q_{i}}$
so that the expression (9) misses at least $p_{i}-q_{i}$ values in
$\mathbb{Z}_{p_{i}q_{i}}$. In other words, the expression (9) takes at most
$(1-\frac{1}{10p_{i}})p_{i}q_{i}$ values in $\mathbb{Z}_{p_{i}q_{i}}$. Let
$P_{k}=\\{p_{1},p_{2},\dots,p_{\min\\{m,n\\}}\\}$, and let $Q_{k}$ be the
product of all $p_{i}q_{i}$. Viewing $\mathbb{Z}_{Q_{k}}$ as a direct sum of
$\mathbb{Z}_{p_{i}q_{i}}$, we can therefore define
$\alpha,\beta,\gamma\colon\mathbb{Z}_{Q_{k}}\to\mathbb{Z}_{Q_{k}}$
coordinatewise using $\alpha_{i},\beta_{i},\gamma_{i}$, so that the expression
(9) attains at most $\prod_{p\in
P_{k}}(1-\frac{1}{10p})Q_{k}\leq\exp(-\frac{c}{k})Q_{k}$ values in
$\mathbb{Z}_{Q_{k}}$, for some positive constant $c$.
Finally, taking
$\mathbb{Z}_{Q_{k}}\oplus\mathbb{Z}_{Q_{k+1}}\oplus\dots\oplus\mathbb{Z}_{Q_{N}}$,
and using the maps $\alpha,\beta,\gamma$ on each $\mathbb{Z}_{Q_{i}}$
separately, makes the expression (9) take at most
$\prod_{i=k}^{N}\exp(-\frac{c}{i})=\exp(-c\sum_{i=k}^{n}\frac{1}{i})$
proportion of values in
$\mathbb{Z}_{Q_{k}}\oplus\mathbb{Z}_{Q_{k+1}}\oplus\dots\oplus\mathbb{Z}_{Q_{N}}$,
which goes to zero as $N$ goes to infinity, as desired.∎

This finishes the proof of the Theorem 6.1.∎

##  7 Concluding remarks

We conclude the paper with some problems and several questions related to the
intgredients used in our construction. Firstly, the main question here is
still the following.

######  Question 7.1.

Suppose that $A\subset\mathbb{Z}_{q}$ has $A-A=\mathbb{Z}_{q}$ and let
$a_{k},a_{k-1},\dots,a_{1}\in\mathbb{N}$. How small can
$a_{k}A^{k}+a_{k-1}A^{k}+\dots+a_{1}A$ be? What is the answer when $q$ is
square-free/product of $O(1)$ primes/prime? When can we get a power saving,
i.e. $|a_{k}A^{k}+a_{k-1}A^{k}+\dots+a_{1}A|\leq q^{1-\epsilon}$?

The next natural question is about the number of values attained by
expressions.

######  Question 7.2.

Let $k\in\mathbb{N}$ be given. We consider expressions in variables
$x_{1},x_{2},\dots,x_{k}$ and maps
$\alpha_{1}(x_{1}),\alpha_{2}(x_{2}),\dots,\alpha_{k}(x_{k})$. Let $E$ be any
$\mathbb{N}$-linear combination of products of terms of the form
$\alpha_{i}(x_{i})$ or $\alpha_{i}(x_{i})+x_{i}$. Is there a choice of a
$q\in\mathbb{N}$ and maps $\alpha_{i}\colon\mathbb{Z}_{q}\to\mathbb{Z}_{q}$
such that $E$ attains only $o(q)$ values in $\mathbb{Z}_{q}$? Is there a
choice for which we have a power-saving, i.e. $E$ attains only
$O(q^{1-\epsilon})$ values? What if $q$ is square-free/product of $O(1)$
primes/prime?

We remark that in our construction, there was a power-saving choice for most
of the expressions. In fact, the only ones for which our arguments do not lead
to a power-saving are

$\alpha(x)^{2}+\alpha(x)\beta(y)+(\alpha(x)+x)(\beta(y)+y)+\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta(y)+\mu_{2}y+\lambda_{3}\gamma(z)+\mu_{3}z$

and

$\alpha(x)\gamma(z)+\alpha(x)\beta(y)+(\alpha(x)+x)(\beta(y)+y)+\lambda_{1}\alpha(x)+\mu_{1}x+\lambda_{2}\beta(y)+\mu_{2}y+\lambda_{3}\gamma(z)+\mu_{3}z,$

(for a specific choice of $\lambda_{i},\mu_{i}$).

Returning once again to the identification of coordinates idea, it turns out
that Proposition 4.4 is nearly optimal for some expressions, provided $p$ and
$q$ are close. Namely, consider expression
$E=\alpha^{\prime}(x)\beta^{\prime}(y)+(\alpha^{\prime}(x)+x)+(\beta^{\prime}(y)+y)+1$.
Putting $\alpha(x)=\alpha^{\prime}(x)+1,\beta(y)=\beta^{\prime}(y)+1$, the
expression becomes $E=\alpha(x)\beta(y)+x+y$.

######  Observation 7.3.

Let $p$ and $q$ be distinct primes. Given any maps
$\alpha,\beta\colon\mathbb{Z}_{pq}\to\mathbb{Z}_{pq}$, the expression
$\alpha(x)\beta(y)+x+y$ attains at least $\Omega(\min\\{p,q\\})$ values in
$\mathbb{Z}_{pq}$.

###### Proof.

We begin by observing that if $\alpha(x)$ is not invertible for some choice of
$x$, viewing $\mathbb{Z}_{pq}$ as $\mathbb{Z}_{p}\oplus\mathbb{Z}_{q}$, for
some coordinate $c\in\\{1,2\\}$, we have $E_{c}=x_{c}+y_{c}$. Letting $y_{c}$
vary, we obtain at least $\min\\{p,q\\}$ values.
Therefore, assume that all $\alpha(x)$ are invertible in
$\mathbb{Z}_{pq}\cong\mathbb{Z}_{p}\oplus\mathbb{Z}_{q}$. Fix some $x$.
Consider all values $v_{1},v_{2},\dots,v_{r}$ of $E(x,y)$, (where $E(x,y)$ is
evaluation of the expression for the given choice of $x,y$), as $y$ ranges
over $\mathbb{Z}_{pq}$. We may assume $r\leq\frac{1}{10}\min\\{p,q\\}$,
otherwise we are done. Hence, we obtain a partition $Y_{1}\cup
Y_{2}\cup\dots\cup Y_{r}=\mathbb{Z}_{pq}$, where $E(x,y)=v_{i}$ if $y\in
Y_{i}$. Call a pair $y_{1},y_{2}$ _invertible_ if $y_{1}-y_{2}$ is invertible
in $\mathbb{Z}_{pq}$. Observe that in each set $Y_{i}$, there are at least
$\max\\{|Y_{i}|(|Y_{i}|-p-q+1)/2,0\\}$ invertible pairs. However, if
$E(x,y_{1})=E(x,y_{2})$ for an invertible pair $y_{1},y_{2}$, then
$\alpha(x)\beta(y_{1})+y_{1}=\alpha(x)\beta(y_{2})+y_{2}$, so
$\beta(y_{1})-\beta(y_{2})$ is invertible, and
$\alpha(x)=\frac{y_{1}-y_{2}}{\beta(y_{2})-\beta(y_{1})}$. Thus, for every
invertible pair $y_{1},y_{2}$ there is a value $w(y_{1},y_{2})$ such that
$E(x,y_{1})=E(x,y_{2})$ implies $\alpha(x)=w(y_{1},y_{2})$.
For a fixed $w$, take $x$ such that $\alpha(x)=w$, and consider the partition
$Y_{1}\cup\dots\cup Y_{r}=\mathbb{Z}_{pq}$ as above. Firstly, take $R$ to be
the set of indiced $i$ such that $|Y_{i}|\geq 2(p+q)$. Thus, $\sum_{i\notin
R}|Y_{i}|<r\cdot 2(p+q)\leq\frac{1}{5}\min\\{p,q\\}(p+q)\leq\frac{2}{5}pq$.
Hence, $\sum_{i\in R}|Y_{i}|>\frac{3}{5}pq$. Therefore, we obtain that the
number of invertible pairs $\\{y_{1},y_{2}\\}$ that have value
$w(y_{1},y_{2})=\alpha(x)=w$ is at least

$\sum_{i=1}^{r}\max\\{|Y_{i}|(|Y_{i}|-p-q+1)/2,0\\}\geq\sum_{i\in
R}|Y_{i}|(|Y_{i}|-p-q+1)/2\geq\sum_{i\in
R}|Y_{i}|(p+q)/2\geq\frac{3}{10}pq(p+q).$

If $\alpha$ attains at most $2(p+q)$ values, we simply consider $E(x,y)$ for
fixed $y$. The expression then attains at least $pq/2(p+q)$ values, thus the
claim follows, so we may assume that $\alpha$ attains more than $2(p+q)$
values. But then, for every value $w$ of $\alpha$, we have at least
$\frac{3}{10}pq(p+q)$ invertible pairs $\\{y_{1},y_{2}\\}$ with
$w(y_{1},y_{2})=w$, so the total number of invertible pairs is at least
$\frac{3}{10}pq(p+q)\cdot 2(p+q)>p^{2}q^{2}$, which is a contradiction.∎

It could be interesting to better understand the minimum image size for this
expression. Furthermore, recall that in the case of prime modulus, we only
achieved that $E$ is not surjective.

######  Question 7.4.

Let $\alpha,\beta\colon\mathbb{Z}_{p}\to\mathbb{Z}_{p}$ be maps and $p$ prime.
What is the smallest number of values that the expression
$\alpha(x)\beta(y)+x+y$ must attain?

Finally, we pose the question of improving the bounds in Lemma 4.2.

######  Question 7.5.

Suppose that $c_{1},c_{2},\dots,c_{d}$ are never simultaneously zero. How
large a set $F$ can we take?

## References

  * [1] J. Bourgain, The sum-product theorem in $\mathbb{Z}_{q}$ with $q$ arbitrary, Journal d’Analyse Mathématique 106.1 (2008): 1–93.
  * [2] J. Bourgain, N. Katz, T. Tao, A sum-product estimate in finite fields, and applications, Geometric and Functional Analysis 14.1 (2004): 27–57.
  * [3] G.A. Freiman, V.P. Pigaev, The relation between the invariants R and T (in Russian), Kalinin. Gos. Univ. Moscow, (1973), 172-174
  * [4] A.A. Glibichuk, Sums of powers of subsets of an arbitrary finite field, Izv. Math. 75 253, 2011
  * [5] W.T. Gowers, A new proof of Szemeredi’s theorem, GAFA 11 (2001), 465–588
  * [6] J.A. Haight, Difference covers which have small k-sums for any k, Mathematika 20 (1973), 109-118
  * [7] F. Hennecart, G. Robert, A. Yudin, On the number of sums and differences, Astérisque 258, 1999, p. 173–178
  * [8] A. Ivić, _The Riemann Zeta-Function. Theory and Applications. Dover Publications_ , New York, 2003, reprint of the 1985 original
  * [9] M.B. Nathanson, The Haight-Ruzsa Method for Sets with More Differences Than Multiple Sums, https://arxiv.org/abs/1604.03015
  * [10] H. Plünnecke, Eine zahlentheoretische anwendung der graphtheorie. J. Reine Angew. Math., 243:171–183, 1970
  * [11] I. Z. Ruzsa, On the cardinality of $A+A$ and $A-A$, in: Coll. Math. Soc. Bolyai, 18 Combinatorics (Keszthely, 1976), Akadémiai Kiadó (Budapest, 1979), pp. 933–938.
  * [12] I.Z. Ruzsa, An application of graph theory to additive number theory. Scientia, Ser. A, 3:97-109, 1989
  * [13] I.Z. Ruzsa, More Differences Than Multiple Sums, https://arxiv.org/abs/1601.04146
  * [14] R.C. Vaughan, _The Hardy-Littlewood Method (2nd ed.)_ , Cambridge Tracts in Mathematics 125, CUP 1997