# Low-complexity approximations for sets defined by generalizations of affine
conditions

W. T. Gowers111Collège de France and Department of Pure Mathematics and
Mathematical Statistics, University of Cambridge. Email:
<EMAIL_ADDRESS>Thomas Karam222Mathematical Institute, University of
Oxford. This research was essentially carried out when that author was at the
Department of Pure Mathematics and Mathematical Sciences, University of
Cambridge. Email<EMAIL_ADDRESS>
###### Abstract

Let $p$ be a prime, let $S$ be a non-empty subset of $\mathbb{F}_{p}$ and let
$0<\epsilon\leq 1$. We show that there exists a constant $C=C(p,\epsilon)$
such that for every positive integer $k$, whenever
$\phi_{1},\dots,\phi_{k}:\mathbb{F}_{p}^{n}\rightarrow\mathbb{F}_{p}$ are
linear forms and $E_{1},\dots,E_{k}$ are subsets of $\mathbb{F}_{p}$, there
exist linear forms
$\psi_{1},\dots,\psi_{C}:\mathbb{F}_{p}^{n}\rightarrow\mathbb{F}_{p}$ and
subsets $F_{1},\dots,F_{C}$ of $\mathbb{F}_{p}$ such that the set $U=\\{x\in
S^{n}:\psi_{1}(x)\in F_{1},\dots,\psi_{C}(x)\in F_{C}\\}$ is contained inside
the set $V=\\{x\in S^{n}:\phi_{1}(x)\in E_{1},\dots,\phi_{k}(x)\in E_{k}\\}$,
and the difference $V\setminus U$ has density at most $\epsilon$ inside
$S^{n}$. We then generalize this result to one where $\phi_{1},\dots,\phi_{k}$
are replaced by homomorphisms $G^{n}\to H$ for some pair of finite Abelian
groups $G$ and $H$, and to another where they are replaced by polynomial maps
$\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}$ of small degree.

###### Contents

  1. 1 Introduction
  2. 2 Preliminary lemmas
  3. 3 Approximating sets of mod-$p$ conditions
  4. 4 More general finite Abelian groups
  5. 5 General finite Abelian groups with restricted alphabets
  6. 6 Polynomial conditions with restricted alphabets
  7. 7 Conclusion and open questions

##  1 Introduction

Let $p$ be a prime. If $\phi_{i}(x)=b_{i}$, $i=1,\dots,k$ is a system of
equations over some finite-dimensional vector space over $\mathbb{F}_{p}$,
then the solution set is either empty or an affine subspace with codimension
equal to $\dim\langle\phi_{1},\dots,\phi_{k}\rangle$, and therefore with
density equal to

$p^{-\dim\langle\phi_{1},\dots,\phi_{k}\rangle}.$

It follows that if the density of the set of solutions is at least $\delta$,
then there is a set of at most $\log_{p}\delta^{-1}$ equations with the same
solution set.

In this paper we shall generalize this simple observation in a number of ways.
Our initial motivation for doing this was that in the context of results such
as the density Hales-Jewett theorem [1, 5] certain generalizations of affine
subspaces occur naturally. Consider, for instance, the problem of
understanding triples of dense subsets $A,B$ and $C$ of $\\{0,1,2\\}^{n}$ such
that the set $A\times B\times C$ contains no combinatorial line. (One might
wish to do this with a view to obtaining a density increment argument.) One
large source of examples is constructed as follows. Pick a prime $p$ and three
subsets $U,V$ and $W$ of $\mathbb{F}_{p}$ such that $U\times V\times W$
contains no arithmetic progression (even degenerate), let
$\phi:\\{0,1,2\\}\to\mathbb{F}_{p}$ be the function where $\phi(x)$ is the
mod-$p$ sum of the coordinates of $x$, and let $A=\phi^{-1}(U),B=\phi^{-1}(V)$
and $C=\phi^{-1}(W)$. Since $\phi$ takes combinatorial lines to arithmetic
progressions in $\mathbb{Z}$, and therefore in $\mathbb{F}_{p}$, it follows
that $A\times B\times C$ has the desired property.

The above construction can be generalized further, and led us to consider sets
of the following form. Let $G$ be a finite Abelian group, let $S$ be a subset
of $G$, let $\phi_{1},\dots,\phi_{k}:G^{n}\to G$ be homomorphisms, and let
$E_{1},\dots,E_{k}$ be subsets of $G$. Then we take the subset

$\\{x\in G^{n}:\phi_{i}(x)\in E_{i},i=1,2,\dots,k\\},$

which is subspace-like, in that it is the intersection of sets defined by
linear-like conditions. One of our main results will be that, as in the simple
case where $G=\mathbb{F}_{p}$ and $E_{1},\dots,E_{k}$ are singletons, if the
above subset is dense, then we may replace it by a subset defined by a number
of conditions that is bounded above in terms of the density. However, the new
subset is not identical to the old one: in this set-up, the best one can hope
for is a good approximation, and that is what we shall obtain. The precise
statement will be given later.

When $G=\mathbb{F}_{p}$, we also prove a generalization in a different
direction, considering subsets of $S^{n}$ that are defined by low-degree
polynomial conditions on $\mathbb{F}_{p}^{n}$. Again we shall show that if
such a subset is dense, then it can be approximated by a subset of bounded
complexity, meaning that it is defined using a bounded number of low-degree
polynomial conditions. Again, we defer the precise statement till later.

The following examples indicate some of the complexities that arise when we
restrict linear conditions to subsets of the form $S^{n}$. For brevity, if
$\phi:G^{n}\to G$ and $E\subset G$, we write $(\phi,E)$ for the condition
$\phi(x)\in E$.

######  Example 1.

For $i=2,3,\dots,k$, let $\phi_{i}:\\{0,1\\}^{n}\to\mathbb{F}_{p}$ be the
linear form defined by $\phi_{i}(x)=x_{1}+x_{i}$ and let
$E_{i}\subset\mathbb{F}_{p}$ be the set $\\{0,1\\}$. Then the set of points of
$\\{0,1\\}^{n}$ satisfying the conditions $(\phi_{i},E_{i})$ consists of all
$x\in\\{0,1\\}^{n}$ such that either $x_{1}=0$, or $x_{1}=1$ and
$x_{2}=\dots=x_{k}=0$. The conditions are linearly independent, and the
density of this set is $1/2+1/2^{k}$. Given $\epsilon>0$, either
$k\leq\log_{2}(\epsilon^{-1})$ or we can approximate the set to within density
$\epsilon$ by the set of points satisfying the single condition $x_{1}=0$.

######  Example 2.

For $i=2,3,\dots,k$, let $\phi_{i}:\mathbb{Z}_{p}^{n}\to\mathbb{Z}_{p}^{2}$ be
the group homomorphism defined by $\phi_{i}(x)=(x_{1},x_{i})$ and let
$E_{i}\subset\mathbb{Z}_{p}^{2}$ be the set
$(\\{0\\}\times\mathbb{Z}_{p})\cup\\{(1,1)\\}$. Then the set of points of
$\mathbb{Z}_{p}^{n}$ satisfying the conditions $(\phi_{i},E_{i})$ consists of
all $x\in\mathbb{Z}_{p}^{n}$ such that either $x_{1}=0$, or
$x_{1}=x_{2}=\dots=x_{k}=1$. The density of this set is $1/p+1/p^{k}$, so it
can be approximated in a similar way.

######  Example 3.

For $i=2,3,\dots,k$, let $P:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}$ be the
degree-$2$ polynomial defined by $P(x)=x_{1}x_{i}$ and let
$E_{i}\subset\mathbb{F}_{p}$ be the set $\\{0\\}$. Then the set of points of
$\mathbb{F}_{p}^{n}$ satisfying the conditions $(\phi_{i},E_{i})$ consists of
all $x\in\mathbb{F}_{p}^{n}$ such that either $x_{1}=0$, or $x_{1}\neq 0$ and
$x_{2}=\dots=x_{k}=0$. The density of this set is $1/p+(p-1)/p^{k}$, so again
it can be approximated in a similar way.

Note that in each of the three examples, the low-complexity set that
approximates the solution set – that is, the set of points that satisfy the
conditions – is a subset of the solution set. Our main results will show that
this is a general phenomenon. To formulate them it will be useful to have a
few definitions.

######  Definition 1.1.

Let $X$ be a finite set and let $U,V$ be subsets of $X$. Then $U$ _internally
$\epsilon$-approximates_ $V$ if $U\subset V$ and $|V\setminus U|$ has density
at most $\epsilon$ in $X$. Given a set $Z$, a function $f:X\to Z$, and a
subset $E\subset Z$, we call the pair $(f,E)$ a _condition_ on $X$, and we say
that $x$ _satisfies the condition_ $(f,E)$ if $f(x)\in E$. If
$\mathcal{F}=\\{(f_{1},E_{1}),\dots,(f_{k},E_{k})\\}$ is a set of conditions
on $X$, the _satisfying set_ of the conditions of $\mathcal{F}$ is the set of
$x\in X$ that satisfy all the conditions in $\mathcal{F}$. If $\mathcal{F}$
and $\mathcal{G}$ are sets of conditions on $X$, we say that $\mathcal{G}$
_internally $\epsilon$-approximates_ $\mathcal{F}$ if the satisfying set of
$\mathcal{G}$ internally $\epsilon$-approximates the satisfying set of
$\mathcal{F}$. If $S\subset\mathbb{F}_{p}$, then a _mod- $p$ condition_ on
$S^{n}$ is a condition $(\phi,E)$ on $S^{n}$, where $\phi$ is the restriction
to $S^{n}$ of a linear form defined on $\mathbb{F}_{p}^{n}$ and $E$ is a
subset of $\mathbb{F}_{p}$.

Our first main result is the following theorem.

######  Theorem 1.2.

For every $\epsilon>0$, every prime $p$ and every non-empty
$S\subset\mathbb{F}_{p}$ there exists $K$ such that for every $n$, every set
of mod-$p$ conditions on $S^{n}$ can be internally $\epsilon$-approximated by
a set of at most $K$ mod-$p$ conditions.

In order to give some idea of why this might be an interesting statement, we
make a few remarks. Note first that if we set $p=2$, then the result is easy.
We can identify $\\{0,1\\}^{n}$ with $\mathbb{F}_{2}^{n}$, and the satisfying
set will take the form $\bigcap_{i=1}^{r}\\{x:\phi_{i}(x)\in E_{i}\\}$, where
each $\phi_{i}$ is a linear form on $\mathbb{F}_{2}^{n}$ and each $E_{i}$ is a
subset of $\mathbb{F}_{2}$. If $E_{i}=\mathbb{F}_{2}$, then we can discard the
condition $(\phi_{i},E_{i})$ without affecting the satisfying set, and if any
$E_{i}$ is empty then the satisfying set is empty, so we can obtain it using
just the condition $(\phi_{i},E_{i})$. So without loss of generality all the
sets $E_{i}$ are singletons and the satisfying set is an affine subspace. If
the codimension of the subspace is greater than $\log_{2}(\epsilon^{-1})$ then
we can internally $\epsilon$-approximate it by the empty set, which as above
just needs one condition. Otherwise, we can pick $k$ linearly independent
conditions that specify the subspace and we have a set of at most
$\log_{2}(\epsilon^{-1})$ conditions with the same satisfying set.

It is only slightly harder to prove the following closely related statement
about linear conditions on $\mathbb{F}_{p}^{n}$ with $p>2$, by which we mean
conditions $(\phi,E)$, where $\phi$ is a linear form on $\mathbb{F}_{p}^{n}$
and $E\subset\mathbb{F}_{p}$. However, the bound is slightly weaker, owing to
a crude argument at the end of the proof. We have not tried to improve the
bound, and indeed it is not obviously possible, because in this case
satisfying sets do not have to be affine subspaces.

######  Proposition 1.3.

For every $\epsilon>0$ and every $n$, every set of linear conditions on
$\mathbb{F}_{p}^{n}$ can be internally $\epsilon$-approximated by a set of at
most $(p\log\epsilon^{-1})^{p}$ linear conditions.

###### Proof.

Let the conditions be $(\phi_{i},E_{i})$ for $i=1,\dots,r$. As in the $p=2$
case we may assume that each $E_{i}$ is a non-empty proper subset of
$\mathbb{F}_{p}$. We may also assume that the $\phi_{i}$ are distinct, since
if $\phi_{i}=\phi_{j}$ then we may replace the two conditions
$(\phi_{i},E_{i})$ and $(\phi_{j},E_{j})$ by the single condition
$(\phi_{i},E_{i}\cap E_{j})$.

Now choose a maximal set $I$ such that the forms $\phi_{i}$ with $i\in I$ are
linearly independent. Then if we choose $x\in\mathbb{F}_{p}^{n}$ uniformly at
random, the events $\phi_{i}(x)\in E_{i}$ with $i\in I$ are independent, so
the probability that $x$ belongs to the satisfying set is at most $\prod_{i\in
I}|E_{i}|/p$, which is at most $(1-1/p)^{|I|}$. If $|I|>p\log(\epsilon^{-1})$,
then this is at most $\epsilon$, so we can internally $\epsilon$-approximate
the satisfying set by the empty set, which requires just one condition.
Otherwise, the forms $\phi_{1},\dots,\phi_{r}$ are contained in a linear
subspace of dimension at most $p\log(\epsilon^{-1})$, and there is at most one
condition for each $i$, so $r\leq(p\log(\epsilon^{-1}))^{p}$, which proves the
result. ∎

The key to the proofs above was that if a set satisfies $k$ non-trivial
linearly independent conditions, then its density must be at most $\alpha^{k}$
for some $\alpha<1$ that is independent of $n$. What makes Theorem 1.2 harder
is that this is no longer true for mod-$p$ conditions on $\\{0,1\\}^{n}$, as
Example 1 shows. Example 1 is a simple representative of a large class of
examples, but it illustrates the basic challenge that we have to deal with.

Once we have proved Theorem 1.2, we shall generalize it to a similar statement
with $\mathbb{F}_{p}$ replaced by an arbitrary finite Abelian group. If $G$
and $H$ are finite Abelian groups and $n$ is a positive integer, then an
$H$-_condition_ on $G^{n}$ is a pair $(\phi,E)$, where $\phi:G^{n}\to H$ is a
homomorphism and $E\subset H$. The definition of an internal
$\epsilon$-approximation carries over in the obvious way: if $S\subset G$,
then we shall say that a set $\mathcal{F}$ of $H$-conditions on $G^{n}$
_internally $\epsilon$-approximates_ a set $\mathcal{G}$ of $H$-conditions on
$G^{n}$ if every point that satisfies $\mathcal{F}$ satisfies $\mathcal{G}$
and the difference of the satisfying sets has density at most $\epsilon$
inside $S^{n}$.

######  Theorem 1.4.

Let $G$ and $H$ be finite Abelian groups, let $S$ be a non-empty subset of
$G$, and let $\epsilon>0$. Then there exists $A=A(\epsilon,G,S,H)$ such that
every set of $H$-conditions can be $\epsilon$-approximated on $S^{n}$ by a set
of at most $A$ $k$-dimensional $H$-conditions.

This theorem turns out to need additional ideas even when $G=\mathbb{F}_{p}$
and $H=\mathbb{F}_{p}^{2}$.

The other generalization we shall prove is to polynomial conditions. If
$S\subset\mathbb{F}_{p}$, then a _$k$ -dimensional condition of degree at most
$d$_ on $S^{n}$ is a pair $(\phi,E)$, where
$\phi:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{k}$ is a polynomial map of degree
at most $d$ (that is, each coordinate of $\phi(x)$ is obtained by applying a
polynomial with degree at most $d$ to $x$) and $E\subset\mathbb{F}_{p}^{k}$.
We prove the following theorem, which has a weaker conclusion than in the
linear case, but still shows that a set defined by polynomial conditions can
be approximated by a set of bounded complexity defined by polynomial
conditions.

######  Theorem 1.5.

For every $\epsilon>0$, every prime $p$, and every pair of positive integers
$k$ and $d$ with $d<p$, there exists $M$ such that for every non-empty
$S\subset\mathbb{F}_{p}$, every set of $k$-dimensional conditions with degree
at most $d$ on $S^{n}$ can be internally $\epsilon$-approximated by a set
consisting of a single $m$-dimensional condition with degree at most $d$ on
$S^{n}$ with $m\leq M$.

##  2 Preliminary lemmas

The next section will be devoted to a proof of Theorem 1.2. To prepare for
this, we collect together some more technical statements that will be useful
in the proof. They will mainly concern the joint distribution of the values
$\phi_{1}(x),\dots,\phi_{k}(x)$, where each $\phi_{i}$ is a linear form from
$\mathbb{F}_{p}^{n}$ to $\mathbb{F}_{p}$ and $x$ is chosen uniformly from
$S^{n}$ for some subset $S$ of $\mathbb{F}_{p}$ of size at least 2. We begin
with a result that will help us with the case $k=1$. We write $\omega_{p}$ for
$\exp(2\pi i/p)$.

######  Lemma 2.1.

Let $p$ be a prime and let $S$ be a subset of $\mathbb{F}_{p}$ that contains
at least two elements. Then

$|\mathop{\mathbb{E}}_{x\in S}\omega_{p}^{tx}|\leq 1-p^{-2}$

for each $t\in\mathbb{F}_{p}^{*}$.

###### Proof.

By the triangle inequality, it is sufficient to prove the result in the case
$|S|=2$, since

$\mathop{\mathbb{E}}_{x\in S}\omega_{p}^{tx}=\mathop{\mathbb{E}}_{{T\subset
S}\atop{|T|=2}}\mathop{\mathbb{E}}_{x\in T}\omega_{p}^{tx}.$

But if $y\neq 0$, then

$|1+\omega_{p}^{y}|^{2}=2+2\cos(2\pi y/p)\leq 2+2\cos(2\pi/p).$

Using the bound $\cos\theta\leq 1-\theta^{2}/2+\theta^{4}/24$, which is at
most $1-\theta^{2}/4$ when $\theta\leq 2\pi/3$, we find that this is at most
$4-4\pi^{2}/4p^{2}=4-\pi^{2}/p^{2}=4(1-\pi^{2}/4p^{2})$. It follows that
$|1+\omega_{p}^{y}|/2\leq 1-\pi^{2}/8p^{2}\leq 1-1/p^{2}$, which implies the
result. ∎

From this lemma we deduce an upper bound on the Fourier coefficients of a
linear phase function restricted to $S^{n}$. Given a linear form $\phi$
defined by a formula $x\mapsto\sum_{i=1}^{n}\lambda_{i}x_{i}$, we define
$Z(\phi)$ to be $\\{i:\lambda_{i}\neq 0\\}$. We shall call this set the
_support_ of $\phi$, even though technically it is the support of the
coefficients of $\phi$ with respect to the standard basis. This should cause
no confusion, since the complement of the kernel of $\phi$ will play no role
in the paper.

Our bound shows that the Fourier coefficients are exponentially small in the
size of the support.

######  Proposition 2.2.

Let $p$ be a prime and let $S$ be a subset of $\mathbb{F}_{p}$ that contains
at least two elements. Let $\phi:\mathbb{F}_{p}^{n}\rightarrow\mathbb{F}_{p}$
be a linear form. Then

$|\mathop{\mathbb{E}}_{x\in
S^{n}}\omega_{p}^{\phi(x)}|\leq(1-p^{-2})^{|Z(\phi)|}.$

###### Proof.

If $\phi(x)=\sum_{i}\lambda_{i}x_{i}$, then the left-hand side splits as a
product

$\mathop{\mathbb{E}}_{x\in
S^{n}}\omega_{p}^{\phi(x)}=\prod_{i=1}^{n}\mathop{\mathbb{E}}_{x_{i}\in
S}\omega_{p}^{\lambda_{i}x_{i}}.$

The inner expectation of the right-hand side is equal to $1$ for every
$i\notin Z(\phi)$, and by Lemma 2.1 it has modulus at most $1-p^{-2}$ for
every $z\in Z(\phi)$. The result follows. ∎

######  Remark 2.3.

Note that the same conclusion holds for $t\phi$ for every non-zero $t$, since
in that case $Z(t\phi)=Z(\phi)$.

A standard calculation now gives us the equidistribution result we shall need.
Given a linear map $\phi:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{k}$ and an
element $a\in\mathbb{F}_{p}^{k}$, we write
$a.\phi:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}$ for the map that takes $x$ to
$a.\phi(x)$, where $a.b$ is notation for $\sum_{i=1}^{k}a_{i}b_{i}$.

######  Proposition 2.4.

Let $p$ be a prime, let $k$ be a positive integer, and let $S$ be a subset of
$\mathbb{F}_{p}$ that contains at least two elements. Let
$\phi:\mathbb{F}_{p}^{n}\rightarrow\mathbb{F}_{p}^{k}$ be a linear map and let
$x$ be chosen uniformly at random from $S^{n}$. Suppose that $|Z(a.\phi)|\geq
r$ for every non-zero $a\in\mathbb{F}_{p}^{k}$. Then for each
$z\in\mathbb{F}_{p}^{k}$,

$|\mathbb{P}[\phi(x)=z]-p^{-k}|\leq(1-p^{-2})^{r}.$

###### Proof.

Let $\delta_{z}$ be the function that takes the value $1$ at $z$ and 0
everywhere else. Then

$\mathbb{P}[\phi(x)=z]=\mathop{\mathbb{E}}_{x\in S^{n}}\delta_{z}(\phi(x)),$

which by the Fourier inversion formula is equal to

$\mathop{\mathbb{E}}_{x\in
S^{n}}\sum_{a\in\mathbb{F}_{p}^{k}}\hat{\delta_{z}}(a)\omega_{p}^{a.\phi(x)}=\sum_{a\in\mathbb{F}_{p}}\hat{\delta_{z}}(a)\mathop{\mathbb{E}}_{x\in
S^{n}}\omega_{p}^{a.\phi(x)}.$

But $\hat{\delta_{z}}(a)=p^{-k}\omega_{p}^{-a.z}$, so when $t=0$ it is equal
to $p^{-k}$, and otherwise it has size at most $p^{-k}$. The result now
follows from Proposition 2.2, the remark after it, and the triangle
inequality. ∎

If a linear form $\phi:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}$ takes a value
once, then it must take that value with probability at least $p^{-1}$. We now
show that something like this, but weaker, holds for the restriction of $\phi$
to a set of the form $S^{n}$.

######  Proposition 2.5.

Let $p$ be a prime and let $S$ be a non-empty subset of $\mathbb{F}_{p}$ that
contains at least two elements. For every linear form
$\phi:\mathbb{F}_{p}\rightarrow\mathbb{F}_{p}$ and every $y\in\mathbb{F}_{p}$
the probability $\mathbb{P}_{x\in S^{n}}(\phi(x)=y)$ is either $0$ or at least
$|S|^{-t}$, where $t=\lceil(p-1)/(|S|-1)\rceil$.

###### Proof.

Let $\phi:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}$ be a linear form given by the
formula $\phi(x)=\sum_{i=1}^{n}\lambda_{i}x_{i}$. Without loss of generality
there exists $m$ such that $\lambda_{1},\dots,\lambda_{m}$ are non-zero and
$\lambda_{m+1}=\dots=\lambda_{n}=0$.

Since there are $|S|^{m}$ distinct choices for $(x_{1},\dots,x_{m})$ if $x\in
S^{n}$, each value of $\phi(x)$ that is taken at all is taken with probability
at least $|S|^{-m}$.

We now prove a second upper bound that is less trivial. Write $\lambda.S$ for
the dilate $\\{\lambda u:u\in S\\}$ of $S$ by $\lambda$. By the Cauchy-
Davenport theorem, for every $r$ we have the inequality

$|\lambda_{1}.S+\lambda_{2}.S+\dots+\lambda_{r}.S|\geq\min\\{r(|S|-1)+1,p\\}.$

In particular, if $r(|S|-1)\geq p-1$, then
$\lambda_{1}.S+\dots+\lambda_{r}.S=\mathbb{F}_{p}$.

For such $r$, it follows that if $x$ is chosen uniformly at random from
$S^{n}$, then for every $u\in\mathbb{F}_{p}$, the probability that
$\lambda_{1}x_{1}+\dots+\lambda_{r}x_{r}=u$ is at least $|S|^{-r}$. By
conditioning on the value taken by
$\lambda_{r+1}x_{r+1}+\dots+\lambda_{n}x_{n}$ and applying the law of total
probability, we deduce that each element of $\mathbb{F}_{p}$ is equal to
$\phi(x)$ with probability at least $|S|^{-r}$.

Combining this with the first bound gives the result claimed. ∎

If $S=\\{0,1,\dots,h\\}$ and $h|(p-1)$, then the bound in Proposition 2.5 is
optimal, since the linear form $\phi$ defined by
$\phi(x)=x_{1}+\dots+x_{(p-1)/h}$ takes the value $p-1$ with probability
$|S|^{-(p-1)/h}$. Note that when $|S|=2$, the lower bound we obtain for each
non-zero probability is $2^{-(p-1)}$.

##  3 Approximating sets of mod-$p$ conditions

In this section we shall prove Theorem 1.2. From now on, we shall write
“$\epsilon$-approximated” to mean “internally $\epsilon$-approximated”, since
all the approximations we consider will be internal ones. (Of course, it is
then important to keep in mind that the relation “can be
$\epsilon$-approximated by” is not symmetric.)

Our basic strategy will be to start with a set of mod-$p$ conditions and
approximate it by sets with more and more structure until eventually we arrive
at a set of bounded size. In order to explain this strategy in more detail, we
need some definitions.

######  Definition 3.1.

Let $p$ be a prime. If $\phi_{0}:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}$ is a
linear form, then a _sunflower with centre_ $\phi_{0}$ is a set of forms
$\\{\phi_{0}+\phi_{i}:i\in I\\}$ such that the forms $\phi_{i}$ are disjointly
supported. A _symmetric family_ of forms is a set $\\{\phi_{i}:i\in I\\}$ that
are equal up to permutations of the coordinates – that is, for each $y$ the
number of coefficients of $\phi_{i}$ equal to $y$ is the same for each $i$. A
_symmetric sunflower_ is a sunflower $\\{\phi_{0}+\phi_{i}:i\in I\\}$ such
that the set $\\{\phi_{i}:i\in I\\}$ is a symmetric family. A set of forms
$\\{\phi_{i}:i\in I\\}$ is $r$-_separated_ if $|Z(\sum_{i\in
I}u_{i}\phi_{i})|\geq r$ for every non-zero $u\in\mathbb{F}_{p}^{I}$ – that
is, if the support size of every non-trivial linear combination of the
$\phi_{i}$ is at least $r$. The _support distance_ on the set of all linear
forms $\phi:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}$ is the metric given by the
formula $d(\phi,\psi)=|Z(\phi-\psi)|$. The _ball of radius $r$ about
$\phi_{0}$_ is the set of all $\phi$ such that $d(\phi_{0},\phi)\leq r$. We
say that a sunflower $\\{\phi_{0}+\phi_{i}:i\in I\\}$ _has radius at most_ $r$
if it is contained in the ball of radius $r$ about $\phi_{0}$.

Note that, contrary to what our terminology might at first suggest, the
condition that the forms are $r$-separated is stronger than simply saying that
$d(\phi_{i},\phi_{j})\geq r$ for every $i\neq j$: we need all non-trivial
linear combinations to have large support and not just differences between two
distinct forms.

We begin with the following simple observation, which we shall use repeatedly.

######  Remark 3.2.

Let $X$ be a finite set, let $q\geq 1$ be a positive integer and let
$\epsilon>0$. Let
$\mathcal{F}_{1},\dots,\mathcal{F}_{q},\mathcal{G}_{1},\dots,\mathcal{G}_{q}$
be sets of conditions on $X$. If $\mathcal{F}_{i}$ internally
$\epsilon$-approximates $\mathcal{G}_{i}$ for each $i\in[q]$ then
$\mathcal{F}_{1}\cup\dots\cup\mathcal{F}_{q}$ internally
$q\epsilon$-approximates $\mathcal{G}_{1}\cup\dots\cup\mathcal{G}_{q}$.

Theorem 1.2 concerns arbitrary sets of mod-$p$ conditions. We shall begin by
proving it under a strong additional hypothesis concerning those conditions,
and then we shall progressively weaken this hypothesis until we end up proving
the result in full generality. At each stage, if we have a proof for families
$\mathcal{F}$ of conditions that satisfy an additional property $P$ and we
would like a proof for families $\mathcal{E}$ of conditions that satisfy a
weaker property $Q$, it is sufficient to prove that every family $\mathcal{E}$
that satisfies $Q$ can be approximated by a family
$\mathcal{F}_{1}\cup\dots\cup\mathcal{F}_{q}$ such that $q$ is bounded and
each $\mathcal{F}_{i}$ satisfies $P$. Then using the remark above and the
result for families that satisfy $P$, we end up with a bounded number of
conditions that approximate $\mathcal{E}$.

Our first additional hypothesis will be that the set of forms is a symmetric
sunflower and that all the subsets of $\mathbb{F}_{p}$ are the same. Having
proved the result under that hypothesis, we shall then weaken the hypothesis
by no longer insisting that the set is a sunflower, but keeping the symmetry
and the assumption that the subsets of $\mathbb{F}_{p}$ are the same and
adding the condition that the set of forms has bounded radius. Finally, we
shall prove the result in full generality. These stages will be the contents
of Proposition 3.3, Proposition 3.4, and Theorem 1.2 respectively.

Given a linear form $\phi:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}$ with
coefficients $(\lambda_{1},\dots,\lambda_{n})$, let
$D_{\phi}:\mathbb{F}_{p}\to\mathbb{N}$ be defined by
$D_{\phi}(y)=|\\{i\in[n]:\lambda_{i}=y\\}|$. We shall call $D_{\phi}$ the
_coefficient distribution_ of $\phi$. Note that a symmetric family of forms is
one where all the forms have the same coefficient distribution.

We begin, then, by proving the result for symmetric sunflowers and identical
subsets of $\mathbb{F}_{p}$. This is a generalization of the example we gave
earlier where the forms were $x\mapsto x_{1}+x_{i}$, and as with that example
it will turn out that as long as there are enough forms, we can
$\epsilon$-approximate the set of conditions by a set of the form
$(\phi_{0},H)$, where $\phi_{0}$ is the centre of the sunflower.

######  Proposition 3.3.

Let $p$ be a prime, let $S$ be a subset of $\mathbb{F}_{p}$ that contains at
least two elements, let $\epsilon>0$, let $\\{\phi_{0}+\phi_{i}:i\in I\\}$ be
a symmetric sunflower, and let $E\subset\mathbb{F}_{p}$. Then there exists
$H\subset\mathbb{F}_{p}$ such that the condition $(\phi_{0},H)$
$p(1-2^{-(p-1)})^{|I|}$-approximates the set of conditions
$(\phi_{0}+\phi_{i},E)$.

###### Proof.

Let $V\subset\mathbb{F}_{p}$ be the set of all possible values taken by
$\phi_{i}(x)$ when $x\in S^{n}$, and note that by the symmetry condition $V$
is the same for all $i\in I$. We let $H$ be the set
$\\{t\in\mathbb{F}_{p}:V+t\subset E\\}$ and we let $T$ be the complement of
$H$. If $x\in S^{n}$ and $\phi_{0}(x)\in H$, then by the definition of $H$,
$\phi_{0}(x)+\phi_{i}(x)\in E$. This establishes that the satisfying set for
the single condition $(\phi_{0},H)$ is contained in the satisfying set for the
conditions $(\phi_{0}+\phi_{i},E)$, so it remains to obtain an upper bound for
the probability that $\phi_{0}(x)\in T$ and $\phi_{0}(x)+\phi_{i}(x)\in E$ for
every $i\in I$.

Let $t\in T$. Then

$\mathbb{P}[\phi_{0}(x)=t\ \wedge\ \forall i\in I\ \phi_{0}(x)+\phi_{i}(x)\in
E]\leq\mathbb{P}[\forall i\in I\ \phi_{i}(x)\in E-t]=\prod_{i\in
I}\mathbb{P}[\phi_{i}(x)\in E-t],$

where the last equality follows from the fact that the $\phi_{i}$ are
disjointly supported and hence the events $\phi_{i}(x)\in E-t$ are independent
(when $x$ is chosen uniformly at random from $S^{n}$).

Since $V+t$ is not contained in $E$, the probability that $\phi_{i}(x)\notin
E-t$ is non-zero, and therefore by Lemma 2.5 it is at least $2^{-(p-1)}$. It
follows that the product above is at most $(1-2^{-(p-1)})^{|I|}$. There are at
most $p$ possibilities for $t$, so the result follows. ∎

The proposition above implies that if the set of forms is a symmetric
sunflower, then either it is already a family of bounded size, or it can be
approximated by a family of size 1.

######  Proposition 3.4.

For every prime $p$, every non-negative integer $r$ and every $\epsilon>0$
there is a constant $A=A(p,r,\epsilon)$ such that for every pair of subsets
$S$ and $E$ of $\mathbb{F}_{p}$ with $|S|\geq 2$ and every symmetric family
$\\{\phi_{0}+\phi_{i}:i\in I\\}$ contained in the ball about $\phi_{0}$ of
radius $r$, the conditions $(\phi_{0}+\phi_{i},E)$ on $S^{n}$ can be
$\epsilon$-approximated by a set of at most $A$ mod-$p$ conditions.

###### Proof.

We prove the result by induction on $r$. The proof will be similar to the
proof by Erdős and Rado of the sunflower lemma (that is, their argument that
gives a factorial-type bound for the sunflower conjecture). When $r=0$, the
ball of radius $r$ about $\phi_{0}$ consists of $\phi_{0}$ only, so the result
holds with $A(p,0,\epsilon)=1$. Now let $r\geq 1$ and let us assume that the
result holds up to $r-1$. Let $M$ be a maximal subset of $I$ such that the
forms $\phi_{i}$ with $i\in M$ have disjoint supports, and let
$Z=\bigcup_{i\in I^{\prime}}Z(\phi_{i})$ be the union of those supports.

If $|M|\geq 2^{p-1}\log(p\epsilon^{-1})$ then by Proposition 3.3 there exists
a subset $H\subset\mathbb{F}_{p}$ such that the condition $(\phi_{0},H)$
$\epsilon$-approximates the conditions $(\phi_{0}+\phi_{i},E)$ with $i\in M$.
From the proof of Proposition 3.3 and the symmetry condition, $(\phi_{0},H)$
implies every condition $(\phi_{0}+\phi_{i},E)$ with $i\in I$, so it follows
that the condition $(\phi_{0},H)$ $\epsilon$-approximates the conditions
$(\phi_{0}+\phi_{i},E)$ with $i\in I$.

For each $i$, let the coefficients of $\phi_{i}$ be
$(\lambda_{i1},\dots,\lambda_{in})$. If instead $|M|\leq
2^{p-1}\log(p\epsilon^{-1})$ then for each $i\in I$ the support of $\phi_{i}$
intersects $Z$, so there is some $j\in Z$ and some non-zero
$y\in\mathbb{F}_{p}$ such that $\lambda_{ij}=y$. That is, if we set $I_{j,y}$
to be the set of $i\in I$ such that $\lambda_{ij}=y$, then
$I=\bigcup_{y\in\mathbb{F}_{p}^{*}}\bigcup_{j\in Z}I_{j,y}$.

Now let us fix $y$ and $j$ and consider the system of forms
$\\{\phi_{0}+\phi_{i}:i\in I_{j,y}\\}$. Since each $\lambda_{ij}$ with $i\in
I_{j,y}$ is equal to $y$, we can obtain the same system of forms by replacing
each $\lambda_{ij}$ with $i\in I_{j,y}$ by $\lambda_{ij}-y$ and replacing
$\lambda_{0j}$ by $\lambda_{0j}+y$. Since for each $\phi_{i}$ with $i\in
I_{j,y}$ the support size has been reduced by 1 and the coefficient we have
removed is $y$, the result is a symmetric family contained in a ball of radius
$r-1$ about the modification of $\phi_{0}$.

By the inductive hypothesis, we can therefore
$\epsilon/(2^{p-1}pr\log(p\epsilon^{-1}))$-approximate each family
$\\{\phi_{0}+\phi_{i}:i\in I_{j,y}\\}$ by a family of at most
$A(p,r-1,\epsilon/(2^{p-1}pr\log(p\epsilon^{-1}))$ mod-$p$ conditions. By
Remark 3.2 and the fact that $|\mathbb{F}_{p}^{*}\times Z|\leq
2^{p-1}pr\log(p\epsilon^{-1})$, it follows that we can $\epsilon$-approximate
the family $\\{\phi_{0}+\phi_{i}:i\in I\\}$ by a family of at most

$A(p,r,\epsilon)=2^{p-1}pr\log(p\epsilon^{-1})A(p,r-1,\epsilon/(2^{p-1}pr\log(p\epsilon^{-1}))$

mod-$p$ conditions. ∎

A back-of-envelope calculation shows that $A(p,r,\epsilon)$ is at most
$(2p)^{2r^{2}p}(\log(\epsilon^{-1}))^{r}$. (We have not attempted to optimize
this bound.)

We have now shown that symmetric families of bounded radius can be
approximated. It remains to prove that an arbitrary family can be approximated
by a union of boundedly many symmetric families of bounded radius. That will
be the content of the rest of the argument in this section.

###### Proof of Theorem 1.2.

Let the set of conditions to be approximated be $\\{(\phi_{i},E_{i}):i\in
I\\}$. We may assume that each $E_{i}$ is a proper subset of $\mathbb{F}_{p}$.
Let $r=2p^{3}(\log p)\log(2/\epsilon)$.

Case 1. Suppose that there exists a subset $I^{\prime}$ of $I$ of size at
least $p\log(2/\epsilon)$ such that the linear forms $\phi_{i}$ with $i\in I$
are $r$-separated. Pick such a set that also satisfies the upper bound
$|I^{\prime}|\leq 2p\log(2/\epsilon)$. By Proposition 2.4 and our choice of
$r$,

$\mathbb{P}[\forall i\in I^{\prime},\phi_{i}=y_{i}]\leq
p^{-|I^{\prime}|}+(1-p^{-2})^{r}\leq 2p^{-|I^{\prime}|}$

for each $y\in\mathbb{F}_{p}^{I^{\prime}}$.

It follows that

$\mathbb{P}[\forall i\in I^{\prime}\ \phi_{i}\in E_{i}]\leq(\prod_{i\in
I^{\prime}}|E_{i}|)(2p^{-|I^{\prime}|})\leq
2(1-p^{-1})^{|I^{\prime}|}\leq\epsilon$

so the set of conditions $\\{(\phi_{i},E_{i}):i\in I\\}$ is
$\epsilon$-approximated by the condition $(x_{1},S^{c})$ (or the condition
$(\phi,\emptyset)$ for any form $\phi$).

Case 2. Now suppose that there does not exist such a subset $I^{\prime}$. Let
$M$ be a maximal $r$-separated subset of $I$. Then by hypothesis $M$ has size
at most $p\log(2/\epsilon)$, and for every $i\in I$ there exists
$a\in\mathbb{F}^{M}$ such that $\phi_{i}-\sum_{m\in M}a_{m}\phi_{m}$ has
support size at most $r$.

As in the proof of Proposition 3.4, we now divide the set of conditions into
families. This time, given a subset $E\subset\mathbb{F}_{p}$, an element
$a\in\mathbb{F}^{M}$, and a function $D:\mathbb{F}_{p}\to\mathbb{N}$ such that
$\sum_{y}D(y)=n$ and $\sum_{y\neq 0}D(y)\leq r$, we let $I_{E,a,D}$ be the set
of $i$ such that $E_{i}=E$, and $\phi_{i}-\sum_{m\in M}a_{m}\phi_{m}$ has
coefficient distribution $D$. There are at most $2^{p}$ choices of $E$, at
most $p^{M}$ choices of $a$, and at most $r^{p}$ choices of
$D:\mathbb{F}_{p}\to\mathbb{N}$ such that $\sum_{y}D(y)=n$ and $\sum_{y\neq
0}D(y)\leq r$, so the number of families $I_{E,a,D}$ we need to approximate is
bounded independently of $n$. Also, the forms in each family are a symmetric
family of radius at most $r$ and within each family the subsets of
$\mathbb{F}_{p}$ are the same.

Therefore, by Proposition 3.4 we can
$(2^{p}p^{|M|}r^{p})^{-1}\epsilon$-approximate each set of conditions
$\\{(\phi_{i},E_{i}):i\in I_{E,a,D}\\}$ by a set of at most
$A(p,r,(2^{p}p^{|M|}r^{p})^{-1}\epsilon)$ conditions. The number of triples
$(E,a,D)$ is at most

$2^{p}p^{|M|}r^{p}\leq 2^{p}p^{p\log(2/\epsilon)}(2p^{3}(\log
p)\log(2/\epsilon))^{p}\leq p^{4p\log(2/\epsilon)},$

so the result now follows by Remark 3.2, and the number of conditions needed
for the approximation is at most

$p^{4p\log(2/\epsilon)}A(p,2p^{3}\log
p\log(2/\epsilon),p^{-4p\log(2/\epsilon)}\epsilon).$

After a back-of-envelope calculation we can bound this above by
$2^{16p^{8}\log(2/\epsilon)^{2}}$. Thus, for fixed $p$ the number of
conditions needed for the approximation depends quasipolynomially on
$1/\epsilon$. ∎

##  4 More general finite Abelian groups

In this and the next section we shall prove Theorem 1.4. This needs extra
ideas, but it turns out that those ideas are already needed for the simpler
case where $S=G$, so in this section we shall prove that special case, and
then in the next section we shall combine the proof method of this section
with the ideas about sunflowers from the previous section in order to obtain a
proof for general $S$.

The following definition will be central to the proof.

######  Definition 4.1.

Given homomorphisms $\phi_{1},\dots,\phi_{k}:G^{b}\to H$ and characters
$\chi_{1},\dots,\chi_{k}\in\hat{H}$, the map
$x\mapsto\prod_{i=1}^{k}\chi_{i}(\phi_{i}(x))$ defines a character on $G$. Let
us call $\phi_{1},\dots,\phi_{k}$ _independent_ if the only way for
$\prod_{i}\chi_{i}\circ\phi_{i}$ to be the trivial character is if all the
$\chi_{i}$ are the trivial character.

######  Proposition 4.2.

Let $\phi_{1},\dots,\phi_{k}$ be independent homomorphisms from $G^{n}$ to
$H$. Then for every $y\in H$,

$\mathbb{P}_{x\in G^{n}}[\forall i\ \phi_{i}(x)=y_{i}]=|H|^{-k}.$

###### Proof.

The probability in question is equal to

$\mathop{\mathbb{E}}_{x}\mathop{\mathbb{E}}_{\chi_{1},\dots,\chi_{k}\in\hat{H}}\prod_{i=1}^{k}\chi_{i}(\phi_{i}(x)-y_{i})$

since if $\phi_{i}(x)=y_{i}$ for each $i$, then the inner expectation is equal
to 1, and if for some $i$ we have $\phi_{i}(x)\neq y_{i}$, then
$\mathop{\mathbb{E}}_{\chi_{i}}\chi_{i}(\phi_{i}(x)-y_{i})=0$, so the whole
expectation is 0.

We can rewrite this expression as

$\mathop{\mathbb{E}}_{\chi_{1},\dots,\chi_{k}\in\hat{H}}\prod_{i=1}^{k}\chi_{i}(-y_{i})\mathop{\mathbb{E}}_{x}\prod_{i=1}^{k}\chi_{i}(\phi_{i}(x)).$

If $\chi_{1},\dots,\chi_{k}$ are all equal to the trivial character, then the
expression being averaged over is equal to 1. Otherwise, by hypothesis,
$\prod_{i}\chi_{i}\circ\phi_{i}$ is not the trivial character on $G^{n}$,
which implies that $\mathop{\mathbb{E}}_{x}\prod_{i}\chi_{i}\circ\phi_{i}=0$.
Therefore, the probability is $|\hat{H}|^{-k}=|H|^{-k}$. ∎

The next definition and lemma are standard, but we recall them here for
convenience.

######  Definition 4.3.

Given an Abelian group $G$, a subgroup $H\subset G$, and a character
$\chi\in\hat{G}$, say that $\chi$ _annihilates_ $H$ if $\chi(x)=1$ for every
$x\in H$. The _annihilator_ of $H$, denoted $H^{\perp}$, is the subgroup of
$\hat{G}$ that consists of all $\chi$ that annihilate $H$. Similarly, if
$\hat{H}$ is a subgroup of $\hat{G}$, we say that $x\in G$ _annihilates_
$\hat{H}$ if $\chi(x)=1$ for every $\chi\in\hat{H}$, and the _annihilator_ of
$\hat{H}$ is the subgroup of all $x\in G$ that annihilate $\hat{H}$.

######  Lemma 4.4.

Let $G$ be a finite Abelian group and let $H$ be a subgroup of $G$. Then
$H^{\perp}\cong\widehat{G/H}$.

###### Proof.

Define a map $\iota:H^{\perp}\to\widehat{G/H}$ by $\iota(\chi)(xH)=\chi(x)$.
Note that this is well defined, since if $xy^{-1}\in H$, then
$\chi(y)=\chi((xy^{-1})y)=\chi(x)$. It is also a homomorphism, since

$\iota(\chi_{1}\chi_{2})(xH)=\chi_{1}\chi_{2}(x)=\chi_{1}(x)\chi_{2}(x)=\iota(\chi_{1})(xH)\iota(\chi_{2})(xH)$

for every $x\in G$.

Now let $\psi:G/H\to\mathbb{C}$ be a character. Define
$\theta(\psi):G\to\mathbb{C}$ by $\theta(\psi)(x)=\psi(xH)$. Then
$\theta(\psi)$ is a character on $G$, since

$\theta(\psi)(xy)=\psi(xyH)=\psi(xHyH)=\psi(xH)\psi(yH)=\theta(\psi)(x)\theta(\psi)(y).$

It also annihilates $H$, since if $x\in H$, then $\theta(\psi)(x)=\psi(H)=1$.
Finally, for any character $\chi$ that annihilates $H$, we have that
$\theta\iota\chi(x)=\iota\chi(xH)=\chi(x)$ for every $x$, so $\theta$ is a
left inverse for $\iota$. In the other direction, if $\psi:G/H\to\mathbb{C}$
is a character, then $\iota\theta\psi(xH)=\theta\psi(x)=\psi(xH)$, so $\theta$
is also a right inverse for $\iota$. ∎

######  Proposition 4.5.

Let $\phi_{1},\dots,\phi_{k}$ be homomorphisms from $G^{n}$ to $H$. Let
$K\subset\hat{H}^{k}$ be the subgroup that consists of all $k$-tuples
$(\chi_{1},\dots,\chi_{k})$ such that $\prod_{i=1}^{k}\chi_{i}\circ\phi_{i}$
is the trivial character on $G^{n}$. Let $Y\subset H^{k}$ be the annihilator
of $K$. Then

$\mathbb{P}[\forall i\ \phi_{i}(x)=y_{i}]=\begin{cases}|Y|^{-1}&y\in Y\\\
0&y\notin Y\\\ \end{cases}$

###### Proof.

Again, the probability in question is equal to

$\mathop{\mathbb{E}}_{\chi_{1},\dots,\chi_{k}\in\hat{H}}\prod_{i=1}^{k}\chi_{i}(-y_{i})\mathop{\mathbb{E}}_{x}\prod_{i=1}^{k}\chi_{i}(\phi_{i}(x)).$

If $(\chi_{1},\dots,\chi_{k})\notin K$, then
$\prod_{i=1}^{k}\chi_{i}\circ\phi_{i}$ is not the trivial character, so the
expectation over $x$ is 0. Therefore, the probability is equal to

$(|K|/|\hat{H}|^{k})\mathop{\mathbb{E}}_{(\chi_{1},\dots,\chi_{k})\in
K}\prod_{i=1}^{k}\chi_{i}(-y_{i}).$

If $(y_{1},\dots,y_{k})\in Y$, then $\prod_{i=1}^{k}\chi_{i}(y_{i})=1$ for
every $(\chi_{1},\dots,\chi_{k})\in K$, and therefore we end up with
$(|K|/|\hat{H}|^{k})$. But by Lemma 4.4 (and Pontryagin duality),
$|\hat{H}|^{k}/|K|=|Y|$, so this equals $|Y|^{-1}$.

If $(y_{1},\dots,y_{k})\notin Y$, then the evaluation map
$(\chi_{1},\dots,\chi_{k})\mapsto\prod_{i=1}^{k}\chi_{i}(y_{i})$ is a non-
trivial character on $K$, and therefore its average is 0. ∎

######  Proposition 4.6.

Let $\phi+\phi_{1},\dots,\phi+\phi_{k}$ be homomorphisms from $G^{n}$ to $H$,
let $E\subset H$, and let $K$ be a subgroup of $\hat{H}$. Suppose that each
$\phi_{i}$ takes values in a subgroup $H_{1}$ of $H$ and that the $\phi_{i}$
are independent when considered as homomorphisms to $H_{1}$. Then there is a
subset $F\subset H$ such that the condition $(\phi,H)$ $\epsilon$-approximates
the set of conditions $(\phi+\phi_{i},E)$, where
$\epsilon=(1-|K|/|\hat{H}|)^{k}$.

###### Proof.

Let $F=\\{z\in H:z+H_{1}\subset E\\}$. Then if $\phi(x)\in F$, we have for all
$i$ that $\phi(x)+\phi_{1}(x)\in F+H_{1}\subset E$. Thus, the single condition
$(\phi,F)$ implies all the conditions $(\phi+\phi_{i},E)$.

Now let us fix some $z\notin F$ and condition on the event that $\phi(x)=z$.
Let $w$ be such that $z+w\notin E$. Then the probability that
$\phi(x)+\phi_{1}(x),\dots,\phi(x)+\phi_{k}(x)\in E$ given that $\phi(x)=z$ is
at most the probability that none of the $\phi_{i}(x)$ is equal to $w$.

But each $\psi_{i}$ takes values in $H_{1}$, and by hypothesis the $\phi_{i}$
are independent when considered as homomorphisms to $H_{1}$, so by Proposition
4.2 the probability that none of them take the value $w$ is at most
$(1-1/|H_{1}|)^{k}$. ∎

######  Theorem 4.7.

Let $G$ and $H$ be finite Abelian groups and let $\epsilon>0$. Then there
exists a constant $C$ such that for every $n$, every set of $H$-conditions on
$G^{n}$ can be $\epsilon$-approximated by at most $C$ $H$-conditions.

###### Proof.

We note first that the number of subsets of $H$ is bounded, so by the usual
partitioning argument it is sufficient to prove the result in the case that
they are all equal to a single set $E$.

We prove the result by induction on the size of a subgroup $H_{1}$ of $H$. The
inductive hypothesis is that if the homomorphisms are of the form
$\phi+\phi_{i}$, where each $\phi_{i}$ takes values in $H_{1}$, then the
result holds. Let us write $C(G,H_{1},\epsilon)$ for the number of conditions
needed for an $\epsilon$-approximation in this case.

If $H_{1}$ is the trivial subgroup $\\{0\\}$, then all the homomorphisms are
the same, so all the conditions are the same, and the result is trivial.

Suppose now that the homomorphisms are of the given form and that we know the
result for all proper subgroups of $H_{1}$. If it is possible to find $k$ of
the homomorphisms $\phi_{i}$ that are independent, where
$(1-|H_{1}|^{-1})^{k}\leq\epsilon$, then by the first paragraph of the proof
of Lemma 4.6 there is a single condition that approximates the entire set of
conditions.

If it is not possible to find more than $k$ of the $\phi_{i}$ that are
independent, then pick a maximal independent set
$\\{\psi_{1},\dots,\psi_{k^{\prime}}\\}$, with $k^{\prime}\leq k$. Then for
every $\phi_{i}$ there is a combination
$(\chi\circ\phi_{i})\prod_{j=1}^{k^{\prime}}(\chi_{j}\circ\psi_{j})$ that
equals the trivial character, where all of $\chi_{1},\dots,\chi_{k^{\prime}}$
and $\chi$ are characters on $H_{1}$ and $\chi$ is not the trivial character.
By the usual partitioning argument we can assume that the
$(k^{\prime}+1)$-tuple $(\chi,\chi_{1},\dots,\chi_{k^{\prime}})$ is the same
for every $\phi_{i}$. So that gives us a character $\gamma:G^{n}\to\mathbb{C}$
and a character $\chi\in\hat{H}_{1}$ such that $\chi\circ\phi_{i}=\gamma$ for
every $i$.

Let us write $\xi_{i}=\phi_{i}-\phi_{1}$ for each $i$. Then
$\phi_{i}=\phi_{1}+\xi_{i}$, and $\chi\circ\xi_{i}=0$ for every $i$. It
follows that each $\xi_{i}$ takes values in the subgroup $H_{2}=\\{y\in
H_{1}:\chi(y)=0\\}$, which is a proper subgroup of $H_{1}$, as $\chi$ is a
non-trivial character on $H_{1}$. Therefore, by the inductive hypothesis, the
conditions $(\phi_{i},E)$ can be $\epsilon$-approximated (by at most
$C(G,H_{2},\epsilon)$ conditions), and we are done. ∎

##  5 General finite Abelian groups with restricted alphabets

We now show how to combine the methods of proof of the last two sections to
give a proof of Theorem 1.4, which generalizes Theorem 4.7 to the
corresponding statement for restricted alphabets.

Before we start on this, we briefly mention a set-up that appears to be more
general than that of Theorem 1.4 but is in fact equivalent to it. Suppose that
$H$ is a finite Abelian group, $S$ is a non-empty finite set (so not
necessarily a subset of a finite Abelian group), and $\phi_{1},\dots,\phi_{n}$
are functions from $S$ to $H$. We can define a function $\phi:S^{n}\to H$ by
$\phi(x)=\sum_{i=1}^{n}\phi_{i}(x_{i})$, and if $E\subset H$, then we can
consider the condition $(\phi,E)$ on $S^{n}$, which is the condition
$\phi(x)\in E$. This more general looking situation is covered by Theorem 1.4,
because for every $k$ we can find a finite Abelian group $G$ and a subset
$S\subset G$ of size $k$ such that every function from $S$ to $H$ can be
extended to a homomorphism from $G$ to $H$. Then if we extend functions
$\phi_{1},\dots,\phi_{n}$ to homomorphisms $\psi_{1},\dots,\psi_{n}$, we find
that the map $\phi$ defined above is the restriction to $S^{n}$ of the
homomorphism $\psi:G^{n}\to H$ defined by $\psi(x)=\sum_{i=1}^{n}\psi_{i}(x)$.
Thus, in a certain sense Theorem 4.7 is not really about subsets of $G$ but
more about particular kinds of functions from a product $S^{n}$ to a finite
Abelian group $H$. However, the embedding of $S$ into a group $G$ is
convenient.

Now let us turn to the proof. We begin with some definitions that will
generalize those that we used in the case $G=H=\mathbb{F}_{p}$. Given a
homomorphism $\phi:G^{n}\to H$, we can express it in the form
$\phi(x)=\sum_{i}\phi_{i}(x_{i})$, where each $\phi_{i}$ is a homomorphism
from $G$ to $H$. If $S\subset G$ is non-empty, then we say that the _support
of $\phi$ with respect to $S$_ (or just the support of $\phi$ if $S$ is clear
from the context) is the set of all $i$ such that $\phi_{i}$ is not constant
on $S$. We call the maps $\phi_{i}|_{S}$ the _coefficients_ of $\phi$ (with
respect to $S$), and the _coefficient distribution_ of $\phi$ is the function
that takes each function $\psi:S\to H$ to the number of $i$ such that
$\phi_{i}|_{S}=\psi$. The definitions of “sunflower”, “ball”, and “symmetric
sunflower” carry over word for word from our earlier definitions (see
Definition 3.1) once the words and phrases “support” and “coefficient
distribution” are interpreted in these generalized senses. We say that
homomorphisms $\phi_{i}:G^{n}\to H$ defined by
$\phi_{i}(x)=\sum_{j=1}^{n}\phi_{ij}x_{j}$ for every $i\in I$ are
$r$-separated if whenever $\chi_{i}\in\hat{H}$ are characters for each $i\in
I$ that are not all trivial, the homomorphism

$\prod_{i\in I}\chi_{i}\circ\phi_{i}:x\to\prod_{j=1}^{n}\prod_{i\in
I}\chi_{i}(\phi_{ij}(x_{j}))$

has support size at least $r$ (with the support being the number of $j$ such
that $\prod_{i\in I}\chi_{i}(\phi_{ij}(x_{j}))$ is not constant on $S$).

We begin by proving an analogue of Proposition 2.5, but with a less
satisfactory bound.

######  Proposition 5.1.

Let $G$ and $H$ be finite Abelian groups, let $S$ be a non-empty subset of
$G$, let $n$ be a positive integer, and let $\phi:G^{n}\to H$ be a
homomorphism. Let $x$ be an element of $S^{n}$, chosen uniformly at random.
Then for every $y\in H$, the probability that $\phi(x)=y$ is either 0 or at
least $c$, where $c=c(H)$ is a positive constant that depends only on $H$ (and
on $S$).

###### Proof.

Let $Z$ be the support of $\phi$. Then $\phi(x)$ depends only on $x|_{Z}$, so
each value $y$ that is taken with non-zero probability is taken with
probability at least $|S|^{-|Z|}$.

We also have that

$\mathbb{P}[\phi(x)=y]=\mathop{\mathbb{E}}_{x}\mathop{\mathbb{E}}_{\chi\in\hat{H}}\chi(\phi(x)-y)=\mathop{\mathbb{E}}_{\chi\in\hat{H}}\chi(-y)\mathop{\mathbb{E}}_{x}\chi(\phi(x))=\mathop{\mathbb{E}}_{\chi\in\hat{H}}\chi(-y)\prod_{i}\mathop{\mathbb{E}}_{x_{i}}\chi(\phi_{i}(x_{i})).$

Note that $\chi\circ\phi$ is a homomorphism and its support is the number of
$i$ such that $\chi\circ\phi_{i}$ is not constant on $S$. For each such $i$,
$|\mathop{\mathbb{E}}_{x_{i}}\chi(\phi_{i}(x_{i}))|$ is at most $|1+\exp(2\pi
i/k)|/2$, where $k$ is the order of $\chi$ in $\hat{H}$. It is therefore at
most $1-e(H)^{-2}$, where $e(H)$ is the exponent of $H$.

It follows that if for each non-trivial character $\chi$ the support size of
$\chi\circ\phi$ is at least $r$, then for every $y$ the difference between
$\mathbb{P}[\phi(x)=y]$ and $|H|^{-1}$ is at most $\exp(-re(H)^{-2})$. So if
$r$ is at least $e(H)^{2}\log(2|H|)$, then the probability that $\phi(x)=y$ is
at least $|H|^{-1}/2$ for all $y$.

Suppose that there is some non-trivial character $\chi$ such that
$\chi\circ\phi$ has support size less than $r$. Without loss of generality the
support of $\chi$ is $\\{1,2,\dots,m\\}$ for some $m\leq r$. Let us write
$x=x^{1}+x^{2}$ where $x^{1}=(x_{1},\dots,x_{m},0,\dots,0)$ and
$x^{2}=(0,\dots,0,x_{m+1},\dots,x_{n})$. Then $\chi(\phi(x))$ depends only on
$x^{1}$, or to put it another way, $\phi(x^{2})$ belongs to a certain coset of
$H_{1}=\ker\chi$. Thus, for each coset $z+H_{1}$, either there is no $x$ with
$\phi(x)\in z+H_{1}$ or the probability that $\phi(x)\in z+H_{1}$ is at least
$|S|^{-r}$. Suppose now that there exists $x$ with $\phi(x)\in z+H_{1}$ and
pick $x^{1}$ such that $\phi(x^{1}+x^{2})\in z+H_{1}$ for every $x^{2}$. Then
for each $y\in z+H_{1}$ such that there exists $x^{2}$ with
$\phi(x^{1}+x^{2})=y$, the probability that $\phi(x^{1}+x^{2})=y$ is, by
induction on $|H|$, at least $c(H_{1})$. It follows that we may take $c(H)$ to
be $|S|^{-e(H)^{2}\log(2|H|)}c(H_{1})$. Since $|H_{1}|\leq|H|/2$ and
$e(H_{1})\leq e(H)$, an easy induction shows that we may therefore take $c(H)$
to be at least $|S|^{-e(H)^{2}(\log(2|H|))^{2}}$. ∎

The next lemma and its proof combine Proposition 3.3 with Proposition 4.6. We
stress that, consistent with the definition that we have given, maps
$\theta_{i}$ consisting merely of the same map repeated several times form a
sunflower.

######  Lemma 5.2.

Let $G$ and $H$ be finite Abelian groups, let $S$ be a non-empty subset of
$G$, and let $H_{1}$ be a subgroup of $H$. Let
$\Phi=\\{\phi_{1},\dots,\phi_{m}\\}$ be a set of $m$ homomorphisms from
$G^{n}$ to $H$ and suppose that we can write $\phi_{i}=\theta_{i}+\psi_{i}$ in
such a way that the maps $\theta_{i}$ form a symmetric sunflower contained in
a ball of radius $r$, that the maps $\psi_{i}$ take values in $H_{1}$ and are
$(rm+r^{\prime})$-separated. Then for every proper subset $E\subset H$ the
conditions $(\phi_{i},E)$, regarded as conditions on $S^{n}$, can be
$\epsilon$-approximated by a single condition, where

$\epsilon=|H|\Big{(}\exp\big{(}-m|S|^{-e(H)^{2}(\log(2|H|))^{2}}|H_{1}|\big{)}+|H_{1}|^{m}\exp\big{(}-r^{\prime}e(H_{1})^{-2}\big{)}\Big{)}.$

###### Proof.

Let $\theta_{i}=\gamma+\zeta_{i}$, where the $\zeta_{i}$ have disjoint
supports of size at most $r$ and the same coefficient distribution. For each
$x\in H$, let $E_{x}=\\{y\in H_{1}:x+y\in E\\}$. We now let $F\subset H$ be
the set of $t\in H$ such that $E_{t+\zeta_{i}(x)}=H_{1}$ for every $x\in
S^{n}$. Note that since the $\zeta_{i}$ have the same coefficient
distribution, their images are the same, so $H$ does not depend on $i$.

We shall now show that the single condition $(\gamma,F)$
$\epsilon$-approximates the set of conditions $(\phi_{i},E)$. First, observe
that if $\gamma(x)\in F$, then for every $i$,

$E_{\theta_{i}(x)}=E_{\gamma(x)+\zeta_{i}(x)}=H_{1},$

and therefore, since $\psi_{i}$ takes values in $H_{1}$,
$\phi_{i}(x)=\theta_{i}(x)+\psi_{i}(x)\in E$. Thus the condition $(\gamma,F)$
implies all the other conditions.

It remains to prove that the set of $x\in S^{n}$ such that $\gamma(x)\notin F$
and $\phi_{i}(x)\in E$ for every $i$ has density at most $\epsilon$. For this
purpose let us fix $y\notin F$ and obtain an upper bound for the probability
that $\gamma(x)=y$ and $\phi_{i}(x)\in E$ for every $i$. Note that if
$\gamma(x)=y$, then $\phi_{i}(x)\in E$ if and only if $\psi_{i}(x)\in
E_{y+\zeta_{i}(x)}$ for every $i$. Since $y\notin F$, there exists $x\in
S^{n}$ such that $E_{y+\zeta_{i}(x)}\neq H_{1}$. That is, there exist $x\in
S^{n}$ and $w\in H$ such that $\zeta_{i}(x)=w$ and $E_{y+w}\neq H_{1}$. By
Proposition 5.1 the probability that $\zeta_{i}(x)=w$, when $x$ is chosen
uniformly from $S^{n}$, is at least $|S|^{-e(H)^{2}(\log(2|H|))^{2}}$, from
which it follows that the probability that $E_{y+\zeta_{i}(x)}\neq H_{1}$ is
at least $|S|^{-e(H)^{2}(\log(2|H|))^{2}}$. Let $m(x)$ be the number of $i$
such that $E_{y+\zeta_{i}(x)}\neq H_{1}$.

Now let $Z$ be the union of the supports of the maps $\zeta_{i}$. Then $Z$ has
cardinality at most $rm$. Let us write $W$ for $Z^{c}$ and $\pi_{Z}$ and
$\pi_{W}$ for the coordinate projections onto $Z$ and $W$. Then since the maps
$\psi_{i}$ are $(rm+r^{\prime})$-separated, it follows that the maps
$\psi_{i}\circ\pi_{W}$ are $r^{\prime}$-separated. Applying the beginning of
the proof of Proposition 5.1 to the map
$\psi=(\psi_{1}\circ\pi_{W},\dots,\psi_{m}\circ\pi_{W})$, we find that for
each $(z_{1},\dots,z_{m})\in H_{1}^{m}$ the probability that
$\psi_{i}(\pi_{W}x)=z_{i}$ for $i=1,2,\dots,m$ differs from $|H_{1}|^{-m}$ by
at most $\exp(-r^{\prime}e(H_{1})^{-2})$, since $e(H^{m})=e(H)$. Therefore, by
conditioning on the restriction of $x$ to $Z$ and applying the law of total
probability we find that the probability that $\psi_{i}(x)\in
E_{y+\zeta_{i}(x)}$ for every $i$ is at most
$(1-|H_{1}|^{-1})^{m(x)}+|H_{1}|^{m}\exp(-r^{\prime}e(H_{1})^{-2})$.

We now drop the conditioning. Let $q=|S|^{-e(H)^{2}(\log(2|H|))^{2}}$. Then
from the above calculations it follows that the probability that
$\psi_{i}(x)\in E_{y+\zeta_{i}(x)}$ for every $i$ is at most

$\displaystyle\sum_{j=0}^{m}\binom{m}{j}(1-q)^{m-j}$ $\displaystyle
q^{j}(1-|H_{1}|^{-1})^{j}+|H_{1}|^{m}\exp(-r^{\prime}e(H_{1})^{-2})$
$\displaystyle=(1-q|H_{1}|)^{m}+|H_{1}|^{m}\exp(-r^{\prime}e(H_{1})^{-2})$
$\displaystyle\leq\exp(-mq|H_{1}|)+|H_{1}|^{m}\exp(-r^{\prime}e(H_{1})^{-2}),$

where the equality follows from the binomial theorem.

Since there are at most $|H|$ possibilities for $y$, we obtain the bound
stated. ∎

######  Remark 5.3.

Note that if we wish to obtain an $\epsilon$-approximation, then it is
sufficient if $m\geq\log(2|H|/\epsilon)|S|^{e(H)^{2}(\log(2|H|))^{2}}|H_{1}|$
and $r^{\prime}\geq\log(2|H||H_{1}|^{m}/\epsilon)e(H_{1})^{2}$. Note also that
the proof that the condition $(\gamma,F)$ implies all the other conditions
used only the fact that the $\theta_{i}$ have the same coefficient
distribution, so if
$t=\lceil\log(2|H|/\epsilon)|S|^{e(H)^{2}(\log(2|H|))^{2}}|H_{1}|\rceil$, then
to obtain an $\epsilon$-approximation it is sufficient if the $\theta_{i}$
belong to a symmetric ball of radius $r$ and we can find $t$ of them that form
a sunflower. Taking the contrapositive, if the $\theta_{i}$ belong to a
symmetric ball and $(\gamma,F)$ does _not_ $\epsilon$-approximate the set of
conditions $(\phi_{i},E)$, then it is not possible to find a set $I$ of size
$t$ such that the conditions $\theta_{i}$ with $i\in I$ form a sunflower and
the conditions $\psi_{i}$ with $i\in I$ are
$\log(2|H||H_{1}|^{t}/\epsilon)e(H_{1})^{2}$-separated.

We are now ready to prove the main result of the section.

###### Proof of Theorem 1.4.

We prove by induction on the size of $|H_{1}|$ and on the radius $r_{H_{1}}$
that for every $\epsilon>0$ the theorem holds (with bounds depending only on
$\epsilon$, $G$, $S$, $H$, $H_{1}$, $r_{H_{1}}$) for every set of conditions
$(\theta_{i}+\psi_{i},E)$ such that each $\theta_{i}$ is a map from $G$ to
$H$, each $\psi_{i}$ is a map from $G$ to $H_{1}$, and the $\theta_{i}$ are
contained in a symmetric ball of radius at most $r_{H_{1}}$.

We again write $\theta_{i}=\gamma+\zeta_{i}$, where the $\zeta_{i}$ have
disjoint supports of size at most $r_{H_{1}}$ and the same coefficient
distribution.

We first describe the inductive step in the case where $r_{H_{1}}>0$ and
$H_{1}$ is not the trivial subgroup. The cases where $H_{1}=\\{e\\}$ or
$r_{H_{1}}=0$ can be dealt with by a degenerate version of the same argument,
as we will explain at the end of the proof.

Suppose that the result holds for all $\epsilon>0$ and for all pairs $(H,r)$
such that $H$ is a strict subgroup of $H_{1}$, or such that $H=H_{1}$ and
$r<r_{H_{1}}$. Let $\epsilon>0$. Then by Lemma 5.2 (and Remark 5.3) we are
done if we can find
$t_{H_{1}}=\lceil\log(2|H|/\epsilon)|S|^{e(H)^{2}(\log(2|H|))^{2}}|H_{1}|\rceil$
of the maps such that the maps $\theta_{i}$ form a sunflower with centre
$\gamma$ and the maps $\psi_{i}$ are
$(r_{H_{1}}t_{H_{1}}+r_{H_{1}}^{\prime})$-separated for
$r_{H_{1}}^{\prime}=\lceil\log(2|H||H_{1}|^{m}/\epsilon)e(H_{1})^{2}\rceil$.
If we cannot find such a set of maps which is that large, then let $M$ be a
maximal set of such maps.

Then for each $i$, the support of the map $\zeta_{i}$ contains a support
element inside $Z$, or there exists a non-trivial character
$\chi\in\hat{H}_{1}$ such that $\chi\circ\psi_{i}$ has support distance at
most $r_{H_{1}}t_{H_{1}}+r_{H_{1}}^{\prime}$ from a product of the form
$\prod_{m\in M}\chi_{m}\circ\psi_{m}$, meaning that the set of $j$ such that

$x_{j}\to\chi_{i}(\psi_{ij}(x_{j}))(\prod_{m\in
M}\chi_{i}(\psi_{mj}(x_{j})))^{-1}$

is constant on $S$ has size at most $r_{H_{1}}t_{H_{1}}+r_{H_{1}}^{\prime}$.
By Remark 3.2 we may assume that the first situation occurs for all $i$, or
that the second situation occurs for all $i$.

Assume that we are in the first situation. Let $d$ be the minimal size of a
generating set of $G$. The number of homomorphisms from $G$ to $H$ is at most
$|H|^{d}$, so the number of pairs $(\xi,z)$ where $\xi$ is a non-zero
homomorphism from $G$ to $H$ and $z$ is an element of $Z$ is at most
$|H|^{d}|M|$. We now partition the set of indices $i$ into sets $I_{(\xi,z)}$
in such a way that for every pair $(\xi,z)$, the coefficient of the map
$\xi_{i}$ at $z$ is equal to $\xi$, in our generalized sense of the word
“coefficient”.

We claim now that each set $\\{\theta_{i}:i\in I_{(\xi,z)}\\}$ is contained in
a ball of radius at most $r_{H_{1}}-1$. To see this, pick $\xi$ and $z$ as
above, and let $\gamma^{\prime}:G^{n}\to H$ be the homomorphism that takes $x$
to $\gamma+\xi(x_{q})$. Then each map $\theta_{i}-\gamma^{\prime}$ with $i\in
I_{(\xi,z)}$ is a homomorphism of support size at most $r_{H_{1}}-1$, so the
homomorphisms $\theta_{i}=\gamma^{\prime}+(\theta_{i}-\gamma^{\prime})$ live
in a ball of radius at most $r_{H_{1}}-1$ with centre $\gamma^{\prime}$. By
Remark 5.3 it suffices to approximate each set
$\\{(\theta_{i}+\psi_{i},E_{i}):i\in I_{(\xi,z)}\\}$, which in turn we can do
by the inductive hypothesis.

Assume that we are instead in the second situation. There are at most
$|H_{1}|^{t_{H_{1}}+1}$ choices for $\chi$ and the $\chi_{m}$ with $m\in M$,
and therefore by Remark 3.2 we may assume that these choices are the same for
each $j$. We write $\Phi$ for the corresponding set of maps
$\phi_{i}=\theta_{i}+\psi_{i}$. We now have that there exist a non-trivial
character $\chi\in\hat{H}_{1}$ and a character $\chi_{m}$ for each $m\in M$
such that for every $\phi=\theta+\psi\in\Phi$ the composition $\chi\circ\psi$
is within support distance $r_{H_{1}}t_{H_{1}}+r_{H_{1}}^{\prime}$ of
$\prod_{m\in M}\chi_{m}\circ\psi_{m}$.

Let us now choose an arbitrary $\phi_{0}=\theta_{0}+\psi_{0}\in\Phi$. Then for
each $\phi=\theta+\psi\in\Phi$, the homomorphism $\chi\circ(\psi-\psi_{0})$
has support size at most $2(r_{H_{1}}t_{H_{1}}+r_{H_{1}}^{\prime})$, and
therefore we can write $\psi-\psi_{0}$ as a sum of a map $\theta^{\prime}$ of
support size at most $2(r_{H_{1}}t_{H_{1}}+r_{H_{1}}^{\prime})$ and a map
$\psi^{\prime}$ that takes values in the subgroup $H_{2}=\ker\chi$ of $H_{1}$.
Since $\chi$ is not the trivial character, $H_{2}$ is not the whole of
$H_{1}$.

To summarize, we can write each $\phi_{i}=\theta_{i}+\psi_{i}$ as
$\theta_{i}+\theta_{i}^{\prime}+\psi_{0}+\psi_{i}^{\prime}$, where the
$\theta_{i}$ form a symmetric sunflower of radius at most $r_{H_{1}}$, the
$\theta_{i}^{\prime}$ have support size at most
$2(r_{H_{1}}t_{H_{1}}+r_{H_{1}}^{\prime})$, $\psi_{0}$ is fixed, and the
$\psi_{i}^{\prime}$ take values in $H_{2}$. Note that the maps
$\theta_{i}+\theta_{i}^{\prime}+\psi_{0}$ are contained in a ball of radius at
most $r_{H_{2}}=r_{H_{1}}(2t_{H_{1}}+1)+2r_{H_{1}}^{\prime}$.

Let us write $\theta_{i}+\theta_{i}^{\prime}+\psi_{0}=\gamma+\eta_{i}$, where
$\gamma$ is the centre of the ball and $\eta_{i}$ is a map of support size at
most $r_{H_{2}}$. There are at most $|H|^{d}$ homomorphisms from $G$ to $H$
(where again $d$ is the minimal size of a generating set of $G$), and
therefore at most $|H|^{dr_{H_{2}}}$ possible coefficient distributions for
the $\eta_{i}$. So by Remark 3.2 we may assume that the $\eta_{i}$ have the
same coefficient distribution, and then conclude by the inductive hypothesis.
The inductive step is now complete.

In the case where $H_{1}=\\{e\\}$ and $r_{H_{1}}=0$, which is the base case of
the induction, the result is immediate. If only the first or only the second
of these equalities hold, then the inductive step is as described above, but
with only the second situation or only the first situation, respectively,
rather than both of them.

It remains to remark that we assumed that there was a set $E$ such that
$E_{i}=E$ for all the conditions $(\phi_{i},E_{i})$ in the collection. As
usual, this is permissible by Remark 3.2. ∎

##  6 Polynomial conditions with restricted alphabets

The approximation results we have proved so far have concerned linear
conditions. The aim of this section is to prove an approximation result for
polynomial conditions. Let $V$ be a $k$-dimensional vector space over
$\mathbb{F}_{p}$. We shall call a map $\phi:\mathbb{F}_{p}^{n}\to V$ a
_polynomial map of degree at most_ $d$ if the map
$a^{*}\phi:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}$ defined by $x\mapsto
a^{*}\phi(x)$ is a polynomial of degree at most $d$ for each $a^{*}\in V^{*}$.
If $V=\mathbb{F}_{p}^{k}$, then we can regard a polynomial map
$\phi:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{k}$ as a $k$-tuple
$(\phi_{1},\dots,\phi_{k})$ of polynomials on $\mathbb{F}_{p}^{n}$, as we did
in the introduction, in which case the degree is simply the maximum degree of
the $\phi_{i}$, but for most of the argument it will be convenient to think of
polynomials in this more basis-free way. (However, we do not replace
$\mathbb{F}_{p}^{n}$ by an arbitrary $n$-dimensional vector space, since we
are considering sets of the form $S^{n}$, which are tied to the standard basis
of $\mathbb{F}_{p}^{n}$.)

Thus, we now define a _$k$ -dimensional condition with degree at most $d$_ to
be a pair $(\phi,E)$, where $\phi:\mathbb{F}_{p}^{n}\to V$ for some
$k$-dimensional vector space $V$ over $\mathbb{F}_{p}$, $\phi$ is a polynomial
map of degree at most $d$, and $E\subset V$. We shall prove Theorem 1.5, which
stated that for every $\epsilon>0$, every prime $p$, every subset
$S\subset\mathbb{F}_{p}$, every positive integer $k$ and every positive
integer $d$ there exists $K$ such that every set of $k$-dimensional conditions
with degree at most $d$ on $S^{n}$ can be $\epsilon$-approximated by a
polynomial condition of degree at most $d$ and dimension at most $K$.

As commented in the introduction, this result is a little different from our
earlier approximation results, since we approximate by a single condition, but
to pay for that we allow the dimension of that condition to be larger than the
dimensions of the conditions we started with. It is not clear whether the
natural direct generalization of our linear results is true – there does not
seem to be an obvious analogue of the sunflower structure that played an
important role in the proofs.

Given a $k$-dimensional space $V$ and a polynomial map
$\phi:\mathbb{F}_{p}^{n}\to V$ of degree at most $d$, for each $0\leq i\leq d$
let $W_{i}^{*}\subset V^{*}$ be the space of all $a^{*}\in V^{*}$ such that
$a^{*}\phi$ has degree at most $i$. We can take a basis of $W_{0}^{*}$, extend
it to a basis of $W_{1}^{*}$, and so on. Let $V_{i}^{*}$ be the subspace of
$V^{*}$ spanned by the basis vectors that belong to $W_{i}^{*}\setminus
W_{i-1}^{*}$. (Since the basis is not uniquely determined, the subspaces
$V_{i}^{*}$ are not uniquely determined either, but this will not matter to
us.) Let $k_{i}=\dim V_{i}^{*}$ and note that
$V^{*}=V_{0}^{*}\oplus\dots\oplus V_{d}^{*}$, so $k_{0}+k_{1}+\dots+k_{d}=k$.
We shall call the sequence $(k_{0},k_{1},\dots,k_{d})$ the _degree profile_ of
the polynomial $\phi$. Let $V=V_{0}\oplus\dots\oplus V_{d}$ be the
corresponding decomposition of $V$ – that is, we take the dual basis and the
subspaces spanned by the corresponding subsets. Let $P_{i}$ be the projection
from $V$ to $V_{i}$ (that is, the coordinate projection with respect to this
basis) and note that if $a^{*}$ is a non-zero element of $V_{i}^{*}$, then
$a^{*}P_{i}\phi$ has degree exactly $i$.

We shall prove Theorem 1.5 by induction on the degree profile in the colex
ordering. That is, we shall prove the result for polynomial conditions where
the polynomials have a given degree profile $(k_{0},k_{1},\dots,k_{d})$
assuming the result for polynomial conditions with degree profile
$(k_{0}^{\prime},k_{1}^{\prime},\dots,k_{d}^{\prime})$ such that there exists
$i$ for which $k_{i}^{\prime}<k_{i}$ and $k_{j}^{\prime}=k_{j}$ for every
$j>i$.

The proof will appear somewhat simpler than several of the proofs in earlier
sections. This is partly because allowing the dimension to increase gives us
considerable extra flexibility, but the simplicity is also partly illusory, as
the proof relies on the main result of [2], which in turn relies on one of the
main results of [4].

The result from [2] concerns the equidistribution of high rank polynomials on
sets of the form $S^{n}$, where $S\subset\mathbb{F}_{p}$ is non-empty. When
$S=\mathbb{F}_{p}$ it is a result of Green and Tao [3, Theorem 1.7]. Before
stating it, let us define a notion of rank for polynomials on restricted
alphabets. The definition we give here is less granular than the one we gave
in the paper [2], but it suffices for our purposes and will be slightly more
convenient to use.

######  Definition 6.1.

Let $p$ be a prime, let $d$ be a nonnegative integer, and let
$P:\mathbb{F}_{p}^{n}\rightarrow\mathbb{F}_{p}$ be a polynomial with degree at
most $d$. We define the _degree- $d$ rank_ $\operatorname{rk}_{d}P$ of $P$ as
follows.

  1. 1.

If $d=0$ then $\operatorname{rk}_{d}P=0$.

  2. 2.

If $d=1$ then $\operatorname{rk}_{d}P$ is the number of indices $i\in[n]$ such
that $a_{i}\neq 0$ when we represent $P$ in the form
$P(x)=c+\sum_{i=1}^{n}a_{i}x_{i}$, where
$c,a_{1},\dots,a_{n}\in\mathbb{F}_{p}$ – that is, the size of the support of
the linear form that differs from $P$ by an additive constant.

  3. 3.

If $d\geq 2$ then $\operatorname{rk}_{d}P$ is the smallest nonnegative integer
$r$ such that there exists a function
$F:\mathbb{F}_{p}^{r}\rightarrow\mathbb{F}_{p}$ and polynomials
$P_{1},\dots,P_{r}:\mathbb{F}_{p}^{n}\rightarrow\mathbb{F}_{p}$ each with
degree strictly smaller than $\deg P$ such that $P=F(P_{1},\dots,P_{r})$.

If $S$ is a non-empty subset of $\mathbb{F}_{p}$, then the _degree- $d$ rank
of $P$ with respect to $S$_, denoted by $\operatorname{rk}_{d,S}P$, is
$\min_{P_{0}}\operatorname{rk}_{d}(P-P_{0})$, where the minimum is taken over
all polynomials $P_{0}:\mathbb{F}_{p}^{n}\rightarrow\mathbb{F}_{p}$ such that
$P_{0}(S^{n})=\\{0\\}$. Equivalently, it is the minimum degree-$d$ rank of any
polynomial $Q$ that agrees with $P$ on $S^{n}$.

The next result is very similar to Theorem 1.4 of [2] and is an immediate
consequence of it. It shows that the values of a high-rank polynomial are
approximately equidistributed on sets of the form $S^{n}$.

######  Theorem 6.2.

For every prime $p$, every non-empty subset $S\subset\mathbb{F}_{p}$, every
positive integer $d<p$, and every $\epsilon>0$ there exists $\tau$ such that
if $P:\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}$ is any polynomial of degree $d$
with $\operatorname{rk}_{d,S}(P)\geq\tau$, then $|\mathop{\mathbb{E}}_{x\in
S^{n}}\omega_{p}^{P(x)}|\leq\epsilon$.

We shall also simplify the argument in a superficial way by being less
explicit about how various bounds depend on each other. Given a property
$\kappa$ of polynomial conditions such that every condition that satisfies
$\kappa$ has degree at most $d$, let us say that conditions that satisfy
$\kappa$ are _boundedly approximable on $S^{n}$_, or simply that they are
_approximable_ , if for every $\epsilon>0$ there exists
$K=K(\epsilon,\kappa,S)$ such that every set of polynomial conditions that
satisfy $\kappa$ can be approximated by a polynomial condition of degree at
most $d$ and dimension at most $K$. We shall frequently make implicit use of
the following lemma, which is very similar to Remark 3.2.

######  Lemma 6.3.

Let $\kappa$ be a property of polynomial conditions, and let $\mathcal{P}$ be
a family of properties of polynomial conditions. Suppose that there exists a
constant $M=M(\kappa,S)$ such that every set of conditions $\mathcal{C}$ that
satisfy $\kappa$ is a union of at most $M$ sets of conditions each satisfying
a property of $\mathcal{P}$. If for every $\lambda\in\mathcal{P}$, conditions
that satisfy $\lambda$ are approximable on $S^{n}$, then conditions that
satisfy $\kappa$ are approximable on $S^{n}$.

###### Proof.

Let $\epsilon>0$ and let $\mathcal{C}$ be a set of conditions that satisfy
$\kappa$ and write $\mathcal{C}$ as
$\mathcal{C}_{1}\cup\dots\cup\mathcal{C}_{m}$, where $m\leq M$ and the
conditions in each $\mathcal{C}_{i}$ satisfy $\lambda_{i}$. For each set
$\mathcal{C}_{i}$, let $(\phi_{i},E_{i})$ be a condition that
$(\epsilon/m)$-approximates $\mathcal{C}_{i}$ (or more precisely, the set
$\\{(\phi_{i},E_{i})\\}$ approximates $\mathcal{C}_{i}$), where
$E_{i}\subset\mathbb{F}_{p}^{k_{i}}$ for some $k_{i}\leq K$. Then let
$k=k_{1}+\dots+k_{m}$, let $\phi:S^{n}\to\mathbb{F}_{p}^{k}$ be defined by
$\phi(x)=(\phi_{1}(x),\dots,\phi_{m}(x))$, and let $E=E_{1}\times\dots\times
E_{m}$. Then $x$ satisfies $(\phi,E)$ if and only if it satisfies
$(\phi_{i},E_{i})$ for each $i$. Also, if $x$ satisfies $\mathcal{C}$ but not
$(\phi,E)$, then there is some $i$ such that it fails to satisfy
$(\phi_{i},E_{i})$ but satisfies $\mathcal{C}_{i}$. For each $i$, the density
of such $x$ is at most $\epsilon/m$, so we are done by a union bound. ∎

If we have a set of conditions that we wish to approximate, this lemma allows
us to partition it into a bounded number of pieces and approximate each piece.
We have done this several times already in the paper, but from now on we shall
not bother to give a careful justification each time we do so.

We shall also use the following more elaborate version of the principle, which
relies heavily on the fact that we allow ourselves to increase the dimensions
of conditions as we approximate. If $\kappa$ is a property of polynomials, we
shall say that a set of conditions satisfies $\kappa$ if the corresponding
polynomials satisfy $\kappa$.

######  Lemma 6.4.

Let $p$ be a prime, let $S$ be a non-empty subset of $\mathbb{F}_{p}$, let $k$
and $d$ be positive integers, let $V$ be a $k$-dimensional vector space over
$\mathbb{F}_{p}$, let $\rho:\mathbb{F}_{p}^{n}\to V$ be a polynomial map of
degree at most $d$, and let $\kappa$ and $\lambda$ be properties of
polynomials that imply that they have degree at most $d$. Suppose that $k$ is
bounded above by a function of $p,S$ and $d$. Suppose also that for every
$y\in V$ and every polynomial $\phi$ that satisfies $\kappa$ there is a
polynomial $\psi$ that satisfies $\lambda$ such that $\phi$ and $\psi$ agree
on the set $\\{x\in\mathbb{F}_{p}^{n}:\rho(x)=y\\}$. Finally, suppose that
polynomial conditions that satisfy $\lambda$ are approximable on $S^{n}$. Then
polynomial conditions that satisfy $\kappa$ are approximable on $S^{n}$.

###### Proof.

Let $\mathcal{C}$ be a set of conditions that satisfy $\kappa$. For each $y\in
V$ and each condition $(\phi,E)\in\mathcal{C}$, where $E$ is a subset of a
vector space $W$, let

$E_{y}=\\{(v,w)\in V\times W:v=y\implies w\in E\\},$

so that $((\rho,\phi),E_{y})$ is the condition $\rho(x)=y\implies\phi(x)\in
E$.

For each $y\in V$, let $\mathcal{C}_{y}$ be the set of conditions
$\\{((\rho,\phi),E_{y}):(\phi,E)\in\mathcal{C}\\}$. If $x$ satisfies
$(\phi,E)$ then it clearly satisfies $((\rho,\phi),E_{y})$ for every $y\in V$,
and the converse is true as well, since if we let $y=\rho(x)$, then the fact
that $x$ satisfies $((\rho,\phi),E_{y})$ guarantees that $\phi(x)\in E$, as
noted above. Therefore, the satisfying sets of $\mathcal{C}$ and
$\bigcup_{y\in V}\mathcal{C}_{y}$ are the same.

By Lemma 6.3 it is therefore sufficient to prove that each set
$\mathcal{C}_{y}$ of conditions is approximable. Let us fix $y\in V$, and for
each $(\phi,E)\in\mathcal{C}$ let $\tilde{\phi}$ be a polynomial that
satisfies $\lambda$ and that agrees with $\phi$ on
$\\{x\in\mathbb{F}_{p}^{n}:\rho(x)=y\\}$. Let $\mathcal{D}_{y}$ be the set of
conditions $(\tilde{\phi},E):(\phi,E)\in\mathcal{C}\\}$ and let
$\tilde{\mathcal{C}}_{y}$ be the set of conditions
$\\{((\rho,\tilde{\phi}),E_{y}):(\phi,E)\in\mathcal{C}_{y}\\}$. Note that the
satisfying set of $\tilde{\mathcal{C}}_{y}$ is the same as that of
$\mathcal{C}_{y}$.

Since the polynomials $\tilde{\phi}$ satisfy $\lambda$, and polynomial
conditions that satisfy $\lambda$ are approximable, $\mathcal{D}_{y}$ is
approximable by a condition $(\theta,F)$. It follows that
$\tilde{\mathcal{C}}_{y}$ is approximable by the condition
$((\rho,\theta),F_{y})$. ∎

We are now ready to begin the proof in earnest. The basic strategy is the same
as it has been with our earlier proofs: either the conditions we wish to
approximate contain a large set of “sufficiently independent” conditions, in
which case the satisfying set has small density, or there is a small set of
conditions that in some suitable sense “approximately generates” all the other
conditions, in which case we can use Lemma 6.4 to reduce to a simpler case
that is covered by an inductive hypothesis.

Let us begin with a standard condition for determining whether a function
taking values in a $k$-dimensional vector space over $\mathbb{F}_{p}$ is
approximately equidistributed.

######  Lemma 6.5.

Let $X$ be a finite set, let $p$ be a prime, let $k$ be a positive integer,
let $V$ be a $k$-dimensional vector space over $\mathbb{F}_{p}$, and let
$\phi:X\to V$. Then for every $y\in V$,

$\mathbb{P}[\phi(x)=y]-p^{-k}|\leq p^{-k}\sum_{{a^{*}\in V^{*}}\atop{a^{*}\neq
0}}|\mathop{\mathbb{E}}_{x}\omega_{p}^{a^{*}(\phi(x))}|.$

###### Proof.

Note first that
$\mathbb{P}[\phi(x)=y]=\mathop{\mathbb{E}}_{x}\mathbbm{1}_{y}(\phi(x))$, where
we write $\mathbbm{1}_{y}$ for the characteristic function of the singleton
set $\\{y\\}$. By the Fourier inversion formula,

$\mathop{\mathbb{E}}_{x}\mathbbm{1}_{y}(\phi(x))=\mathop{\mathbb{E}}_{x}\sum_{a^{*}\in
V^{*}}\widehat{\mathbbm{1}_{y}}(a^{*})\omega_{p}^{a^{*}(\phi(x))}=p^{-k}\sum_{a^{*}\in
V^{*}}\mathop{\mathbb{E}}_{x}\omega_{p}^{a^{*}(\phi(x)-y)}.$

The result follows. ∎

The above lemma immediately implies a version for several functions, but it is
convenient to state it separately.

######  Corollary 6.6.

Let $X$ be a finite set, let $p$ be a prime, let $r$ and $k_{1},\dots,k_{r}$
be positive integers, let $k=\sum_{i}k_{i}$, for each $i\leq r$ let $V_{i}$ be
a vector space over $\mathbb{F}_{p}$ of dimension $k_{i}$, and let
$\phi_{i}:X\to V_{i}$. Then for every $(y_{1},\dots,y_{r})\in
V_{1}\times\dots\times V_{r}$,

$|\mathbb{P}[\forall i\ \phi_{i}(x)=y_{i}]-p^{-r}|\leq p^{-r}\sum_{{a^{*}\in
V_{1}^{*}\times\dots\times V_{r}^{*}}\atop{a^{*}\neq
0}}|\mathop{\mathbb{E}}_{x}\omega_{p}^{\sum_{i}a_{i}^{*}(\phi_{i}(x))}|.$

###### Proof.

We can apply the lemma to the map $\phi:X\to V_{1}\times\dots\times V_{r}$
defined by $x\mapsto(\phi_{1}(x),\dots,\phi_{r}(x))$. ∎

A simple further consequence of this corollary and Theorem 6.2 is the
following result.

######  Corollary 6.7.

For every $\epsilon>0$, every pair of positive integers $d$ and $k$, every
prime $p$ and every non-empty subset $S\subset\mathbb{F}_{p}$ there exist
$R,\tau$ such that for every $r\geq R$, every sequence $V_{1},\dots,V_{r}$ of
vector spaces over $\mathbb{F}_{p}$ with $\dim V_{i}\leq k$ for each $i$,
every sequence of polynomial maps $\phi_{1},\dots,\phi_{r}$ of degree at most
$d$ with $\phi_{i}:\mathbb{F}_{p}^{n}\to V_{i}$, and every sequence
$E_{1},\dots,E_{r}$ with $E_{i}$ a proper subset of $V_{i}$, if the satisfying
set of the conditions $(\phi_{i},E_{i})$ has density greater than $\epsilon$,
then there exist $a_{1}^{*},\dots,a_{r}^{*}$ with $a_{i}^{*}\in V_{i}^{*}$,
not all zero, such that $\sum_{i}a_{i}^{*}\phi_{i}$ is a polynomial of degree
$d^{\prime}\leq d$ with
$\operatorname{rk}_{d^{\prime},S}(\sum_{i}a_{i}^{*}\phi_{i})\leq\tau$.

###### Proof.

If $(1-p^{-k})^{R}\leq\epsilon/2$, then the density of the set
$E_{1}\times\dots\times E_{r}$ in $V_{1}\times\dots\times V_{r}$ is at most
$\epsilon/2$, so by Corollary 6.6 with $X=S^{n}$ we find that

$\mathbb{P}_{x\in S^{n}}[(\phi_{1}(x),\dots,\phi_{r}(x))\in
E_{1}\times\dots\times E_{r}]\leq\epsilon/2+\sum_{{a^{*}\in
V_{1}^{*}\times\dots\times V_{r}^{*}}\atop{a^{*}\neq
0}}|\mathop{\mathbb{E}}_{x}\omega_{p}^{\sum_{i}a_{i}^{*}(\phi_{i}(x))}|.$

Therefore, if the satisfying set of the conditions has density at least
$\epsilon$, then there exists a non-zero $a^{*}\in V_{1}^{*}\times\dots\times
V_{r}^{*}$ such that

$|\mathop{\mathbb{E}}_{x}\omega_{p}^{\sum_{i}a_{i}^{*}(\phi_{i}(x))}|\geq\epsilon/2p^{rk}.$

Let $\psi=\sum_{i}a_{i}^{*}\phi_{i}$ and let $d^{\prime}$ be the degree of
$\psi$. By Theorem 6.2 there is a constant $\tau$ depending only on
$p,S,\epsilon,r$ and $k$ such that
$\operatorname{rk}_{d^{\prime},S}(\psi)\leq\tau$, which proves the result. ∎

We now prove an easy result that will turn out to be the base case of an
inductive argument. It also has a very similar structure to that of the main
proof. Let us define the _support_ $Z(\phi)$ of a linear map
$\phi:\mathbb{F}_{p}^{n}\to V$ to be the set of coordinates on which $\phi$
depends. That is, if $e_{1},\dots,e_{n}$ is the standard basis, then
$Z(\phi)=\\{i:\phi(e_{i})\neq 0\\}$. If $\phi$ is an affine map, then we
define $Z(\phi)$ to be the support of its linearization, and we also call it
the support.

######  Lemma 6.8.

Let $p$ be a prime, let $s$ and $k$ be positive integers and let $S$ be a non-
empty subset of $\mathbb{F}_{p}$. Then conditions of the form $(\phi,E)$ where
$\phi$ is an affine map from $\mathbb{F}_{p}^{n}$ to some vector space $V$ of
dimension at most $k$, $E\subset V$, and $\phi$ has support size at most $s$,
are approximable on $S^{n}$.

###### Proof.

We prove the result by induction on $s$, observing that it is trivial when
$s=0$. We now assume that the result holds for $s-1$ and prove it for $s$.

Let $\epsilon>0$ and let $\mathcal{C}$ be a set of $k$-dimensional affine
conditions of support size at most $s$. We may assume that each $(\phi,E)$ is
such that there exists $x\in S^{n}$ with $\phi(x)\notin E$, since we can throw
away all conditions that do not satisfy this property.

Now let $\\{(\phi_{1},E_{1}),\dots,(\phi_{r},E_{r})\\}$ be a maximal subset of
$\mathcal{C}$ such that the maps $\phi_{1},\dots,\phi_{r}$ are disjointly
supported. Then the events $\phi_{i}(x)\in E_{i}$ are independent, and each
holds with probability at most $1-2^{-s}$. Therefore, if
$(1-2^{-s})^{r}<\epsilon$, we can approximate $\mathcal{C}$ by a single
condition $(\phi,\emptyset)$.

If $(1-2^{-s})^{r}\geq\epsilon$, then for every $(\phi,E)\in\mathcal{C}$ the
support of $\phi$ intersects the union $Z$ of the supports of
$\phi_{1},\dots,\phi_{r}$. It follows that $\phi$ agrees with a map of support
size at most $s-1$ on each set of the form $\\{x:\forall j\in Z\
x_{j}=y_{i}\\}$. By the inductive hypothesis and Lemma 6.4 we are done. ∎

###### Proof of Theorem 1.5.

There are at most $(d+1)^{k}$ degree profiles that the polynomials can have,
so by Lemma 6.3 we may assume that they all have the same degree profile. We
may also throw away all conditions $(\phi,E)$ where $E=\mathbb{F}_{p}^{k}$. As
promised in the introduction to this section, we now prove the result by
induction on the degree profile, with respect to the colex order.

Let $\epsilon>0$ and let $\mathcal{C}$ be a set of $k$-dimensional polynomial
conditions $(\phi,E)$ such that each polynomial $\phi$ has degree profile
$(k_{0},k_{1},\dots,k_{d})$. If the satisfying set of $\mathcal{C}$ in $S^{n}$
has density less than $\epsilon$, then we can approximate it with a single
condition of the form $(\phi,\emptyset)$. Otherwise, Corollary 6.7 gives us
$R$ and $\tau$ such that for any $r$ polynomials $\phi_{1},\dots,\phi_{r}$
involved in the conditions in $\mathcal{C}$, if $r>R$ then there exist
$a_{1}^{*},\dots,a_{r}^{*}$ such that $\sum_{i=1}^{r}a_{i}^{*}\phi_{i}$ has
rank at most $\tau$. (By this we mean it has degree $d^{\prime}$ for some
$d^{\prime}\leq d$ and $(d^{\prime},S)$-rank at most $\tau$.)

Let $\phi_{1},\dots,\phi_{r}$ be a maximal set of polynomials coming from the
conditions in $\mathcal{C}$ for which that is _not_ the case, and suppose that
$\phi_{i}:\mathbb{F}_{p}^{n}\to V_{i}$. Then for every
$(\phi,E)\in\mathcal{C}$ with $\phi:\mathbb{F}_{p}^{n}\to V$ there exist
$a_{1}^{*},\dots,a_{r}^{*}$ and $b^{*}$ with $a_{i}^{*}\in V_{i}^{*}$ and
$b^{*}\in V^{*}\setminus\\{0\\}$ such that
$\sum_{i=1}^{r}a_{i}^{*}\phi_{i}+b^{*}\phi$ has rank at most $\tau$.

After a further application of Lemma 6.3, we may assume that
$(a_{1}^{*},\dots,a_{r}^{*},b^{*})$ is the same for each
$(\phi,E)\in\mathcal{C}$. Let $\psi$ be the polynomial
$\sum_{i=1}^{r}a_{i}^{*}\phi_{i}$, so $\psi+b^{*}\phi$ has rank at most $\tau$
for each $(\phi,E)\in\mathcal{C}$.

Let us now fix $(\phi,E)\in\mathcal{C}$. On each set $\\{x\in
S^{n}:\psi(x)=y\\}$, the polynomials $b^{*}\phi$ and $\psi+b^{*}\phi-y$ agree,
so $b^{*}\phi$ agrees with a polynomial of rank at most $\tau$. Let
$V^{*}=V_{0}^{*}\oplus\dots\oplus V_{d}^{*}$ be a decomposition as described
at the beginning of the section, so $\dim V_{i}^{*}=k_{i}$ and $w^{*}\phi$ has
degree exactly $i$ for every $w^{*}\in V_{i}^{*}$. Let
$b^{*}=b_{0}^{*}+b_{1}^{*}+\dots+b_{d}^{*}$ with $b_{i}^{*}\in V_{i}^{*}$.

Then if $b^{*}\phi$ has degree $d^{\prime}$, it follows that
$b_{d^{\prime}}^{*}\neq 0$ and $b_{i}^{*}=0$ for every $i>d^{\prime}$. Now
pick $w\in V_{d^{\prime}}$ such that $b_{d^{\prime}}^{*}(w)=1$. Then we can
write

$\phi(x)=b_{d^{\prime}}^{*}\phi(x)w+(\phi(x)-b_{d^{\prime}}^{*}\phi(x)w)$

and the image of the polynomial map $\phi(x)-b_{d^{\prime}}^{*}\phi(x)w$ lies
in the kernel of $b_{d^{\prime}}^{*}$.

Since $b^{*}\phi$ agrees with a polynomial of degree $d^{\prime}$ and rank at
most $\tau$, and since $(b_{0}^{*}+\dots+b_{d^{\prime}-1}^{*})\phi$ has degree
less than $d^{\prime}$, $b_{d^{\prime}}^{*}\phi$ has rank at most $\tau+1$. We
can therefore write it in the form $F(\gamma_{1},\dots,\gamma_{t})$ with
$t\leq\tau+1$ and with $\gamma_{1},\dots,\gamma_{t}$ all of degree less than
$d^{\prime}$. This allows us to replace the condition $(\phi,E)$ by a
condition with a degree profile that comes earlier than
$(k_{0},k_{1},\dots,k_{d})$ and that agrees with $\phi$ on $\\{x\in
S^{n}:\psi(x)=y\\}$. Let $\tilde{\phi}$ be the polynomial
$\phi-(b_{d^{\prime}}^{*}\phi)w$, regarded as taking values in
$\ker(b_{d^{\prime}}^{*})$, and note that $\tilde{\phi}$ has degree profile
$(k_{0},k_{1},\dots,k_{d^{\prime}-1},k_{d^{\prime}}-1,k_{d^{\prime}+1},\dots,k_{d})$.
Let $\iota:\ker(b_{d^{\prime}}^{*})\to V$ be the inclusion map, and let
$\theta:\ker(b_{d^{\prime}}^{*})\times\mathbb{F}_{p}^{t}\to V$ be the map
$(u,a)\mapsto\iota u+aw$. Now let us take the polynomial
$(\tilde{\phi},\gamma_{1},\dots,\gamma_{t})$ and let
$H\subset\ker(b_{d^{\prime}}^{*})\times\mathbb{F}_{p}^{t}$ be the set
$\\{(v,u):\theta(v,F(u))\in E\\}$.

Then $(\tilde{\phi},\gamma_{1},\dots,\gamma_{t})(x)\in H$ if and only if
$\iota\tilde{\phi}(x)+F(\gamma_{1}(x),\dots,\gamma_{t}(x))\in E$, which is
true if and only if
$\phi(x)-b_{d^{\prime}}^{*}\phi(x)w+F(\gamma_{1}(x),\dots,\gamma_{t}(x))w\in
E$, which is true if and only if $\phi(x)\in E$. Thus, the condition
$(\phi,E)$ is equivalent to the condition
$((\tilde{\phi},\gamma_{1},\dots,\gamma_{t}),H)$. But $\tilde{\phi}$ has
degree profile
$(k_{0},k_{1},\dots,k_{d^{\prime}-1},k_{d^{\prime}}-1,k_{d^{\prime}+1},\dots,k_{d})$,
as already noted, and since each $\gamma_{i}$ has degree less than
$d^{\prime}$, the degree profile of
$(\tilde{\phi},\gamma_{1},\dots,\gamma_{t})$ precedes that of $\phi$ in colex
order. Furthermore, since $t$ is bounded independently of $n$, all the degrees
in the degree profile of $(\tilde{\phi},\gamma_{1},\dots,\gamma_{t})$ are
bounded independently of $n$. Hence we are done by the inductive hypothesis
and Lemma 6.4, once we have established the base case.

Recall that for polynomials of degree 1, we define the rank to be the size of
the support of the linearization. So the inductive argument just given allows
us to reduce to the case where all the polynomials are linear and have bounded
support size. This case is dealt with by Lemma 6.8. ∎

##  7 Conclusion and open questions

We finish by mentioning two questions to which we do not know the answers. One
is the obvious one of improving the bounds in our approximation results. Even
in the most basic approximation result, Proposition 1.3, the question of the
optimal bounds is not yet settled.

######  Question 7.1.

Can we replace the bound $(p\log\epsilon^{-1})^{p}$ by
$O_{p}(\log\epsilon^{-1})$ in Proposition 1.3?

If this is indeed possible, then we may ask whether we can also take bounds
$O(\log\epsilon^{-1})$ in Theorem 1.2, Theorem 1.4, and Theorem 1.5. In the
case of Theorem 1.5 it would probably help to first have linear bounds
$H_{p,d,S}(\epsilon)=O_{p,d,S}(\log\epsilon^{-1})$ in Theorem 6.2 on the
equidistribution of polynomials.

In a second direction, our first approximation result for linear forms
$\mathbb{F}_{p}^{n}\rightarrow\mathbb{F}_{p}$, Proposition 1.2, involves
internal approximation. We can also ask for an external approximation, where
it also does not seem obviously unreasonable to require the conditions to
belong to the original family of conditions. (In the case of internal
approximations, it is not possible to add this additional requirement, as it
would imply that the set of $x\in S^{n}$ satisfying the approximating set of
conditions is exactly the same as that satisfying the original set of
conditions, which is not always possible, as can be seen with an example we
gave earlier, where we take $S$ to be $\\{0,1\\}$ and the family of linear
forms to be $\\{(x_{1}+x_{i},\\{0,1\\}):i\in[2,n]\\}$.)

######  Conjecture 7.2.

Let $p$ be a prime, let $S$ be a non-empty subset of $\mathbb{F}_{p}$, and let
$\epsilon>0$. There there exists a constant $A=A(p,S,\epsilon)$ such that for
every set $\mathcal{F}$ of mod-$p$ conditions on $S^{n}$ there is a subset
$\mathcal{G}$ of $\mathcal{F}$ such that the satisfying set of $\mathcal{G}$
$\epsilon$-externally approximates that of $\mathcal{F}$ (meaning that the
density of points that satisfy $\mathcal{G}$ but not $\mathcal{F}$ is at most
$\epsilon$).

## References

  * [1] H. Furstenberg and Y. Katznelson, A density version of the Hales-Jewett theorem, J. Anal. Math. 57 (1991), 64-119.
  * [2] W. T. Gowers and T. Karam, Equidistribution of high rank polynomials with variables restricted to subsets of $\mathbb{F}_{p}$, arXiv:2209.04932 (2022).
  * [3] B. Green and T. Tao, The distribution of polynomials over finite fields, with applications to the Gowers norms. Contributions to Discrete Mathematics, 4 (2009), no. 2, 1-36.
  * [4] T. Karam, High-rank subtensors of high-rank tensors, arXiv:2207.08030 (2022).
  * [5] D. H. J. Polymath, A new proof of the density Hales-Jewett theorem, Ann. Math. 175 (2012), 1283-1327.