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

\begin{align*} \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}. \end{align*}

But if $y\ne 0$ , then

\begin{align*} \big|1+\omega _p^y\big|^2=2+2\cos (2\pi y/p)\leq 2+2\cos (2\pi /p). \end{align*}

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.

Proof. If $\phi (x)=\sum _i\lambda _ix_i$ , then the left-hand side splits as a product

\begin{align*} \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 _ix_i}. \end{align*}

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.

Proof. Let $\delta _z$ be the function that takes the value $1$ at $z$ and 0 everywhere else. Then

\begin{align*} \mathbb{P}[\phi (x)=z]=\mathop {\mathbb{E}}_{x\in S^n}\delta _z(\phi (x)), \end{align*}

which by the Fourier inversion formula is equal to

\begin{align*} \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^k}\hat {\delta _z}(a)\mathop {\mathbb{E}}_{x\in S^n}\omega _p^{a.\phi (x)}. \end{align*}

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 modulus at most $p^{-k}$ . The result now follows from Proposition 2.2 and the triangle inequality.

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 _ix_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

\begin{align*} |\lambda _1.S+\lambda _2.S+\dots +\lambda _r.S|\geq \min \{r(|S|-1)+1,p\}. \end{align*}

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 _1x_1+\dots +\lambda _rx_r=u$ is at least $|S|^{-r}$ . By conditioning on the value taken by $\lambda _{r+1}x_{r+1}+\dots +\lambda _nx_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.

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

\begin{align*} \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], \end{align*}

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.

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 \ge 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 M}Z(\phi _i)$ be the union of those supports.

If $|M| \ge 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| \le 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

\begin{align*} 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})) \end{align*}

mod- $p$ conditions.

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 )$ .

Proof. The probability in question is equal to

\begin{align*} \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) \end{align*}

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)\ne 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

\begin{align*} \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)). \end{align*}

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}$ .

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

\begin{align*} \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) \end{align*}

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

\begin{align*} \theta (\psi )(xy)=\psi (xyH)=\psi (xHyH)=\psi (xH)\psi (yH)=\theta (\psi )(x)\theta (\psi )(y). \end{align*}

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$ .

Proof. Again, the probability in question is equal to

\begin{align*} \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)). \end{align*}

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

\begin{align*} (|K|/|\hat H|^k)\mathop {\mathbb{E}}_{(\chi _1,\dots ,\chi _k)\in K}\prod _{i=1}^k\chi _i(\!-y_i). \end{align*}

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$ .

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 \in H_1$ 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$ .

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'}\}$ , with $k'\leq k$ . Then for every $\phi _i$ there is a combination $(\chi \circ \phi _i)\prod _{j=1}^{k'}(\chi _j\circ \psi _j)$ that equals the trivial character, where all of $\chi _1,\dots ,\chi _{k'}$ 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'+1)$ -tuple $(\chi ,\chi _1,\dots ,\chi _{k'})$ 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.

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

\begin{align*} \mathbb{P}[\phi (x)=y]=\mathop {\mathbb{E}}_{x \in S^n} \mathop {\mathbb{E}}_{\chi \in \hat H}\chi (\phi (x)-y)=\mathop {\mathbb{E}}_{\chi \in \hat H}\chi (\!-y)\mathop {\mathbb{E}}_{x \in S^n} \chi (\phi (x))=\mathop {\mathbb{E}}_{\chi \in \hat H}\chi (\!-y)\prod _i\mathop {\mathbb{E}}_{x_i \in S}\chi (\phi _i(x_i)). \end{align*}

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 $||S|-1 + \exp (2\pi i/k)|/|S|$ , where $k$ is the order of $\chi$ in $\hat H$ . It is therefore at most $1-e(H)^{-2}/|S|$ , 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}/|S|)$ . So if $r$ is at least $|S|e(H)^2\log (2|H|)$ , then the probability that $\phi (x)=y$ is at least $|H|^{-1}/2$ for all $y$ .

With these observations in mind, let us prove Proposition 5.1 by induction on $|H|$ . 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 (over $x^2$ chosen at random in $S^{n-m}$ ) that $\phi (x^1+x^2)=y$ is, by the inductive hypothesis, at least $c(H_1)$ . It follows that we may take $c(H)$ to be $|S|^{-|S|e(H)^2\log (2|H|)}c(H_1)$ . Since $|H_1|\leq |H|/2$ and $e(H_1)\leq e(H)$ , we may therefore take $c(H)$ to be at least $|S|^{-|S|e(H)^2(\!\log (2|H|))^2}$ .

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 $F$ 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$ ,

\begin{align*} E_{\theta _i(x)}=E_{\gamma (x)+\zeta _i(x)}=H_1, \end{align*}

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)}\ne H_1$ . That is, there exist $x\in S^n$ and $w\in H$ such that $\zeta _i(x)=w$ and $E_{y+w}\ne 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|^{-|S|e(H)^2(\!\log (2|H|))^2}$ , from which it follows that the probability that $E_{y+\zeta _i(x)}\ne H_1$ is at least $|S|^{-|S|e(H)^2(\!\log (2|H|))^2}$ . Let $N(x)$ be the number of $i$ such that $E_{y+\zeta _i(x)}\ne 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$ . Since the maps $\psi _i$ are $(rm+r')$ -separated, it follows that the maps $\psi _i\circ \pi _W$ are $r'$ -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 $(w_1,\dots ,w_m)\in H_1^m$ the probability that $\psi _i(\pi _Wx)=w_i$ for $i=1,2,\dots ,m$ differs from $|H_1|^{-m}$ by at most $\exp (\!-r'e(H_1)^{-2}/|S|)$ , since $e(H^m)=e(H)$ . Let us condition on the restriction $\pi _Z(x)$ of $x$ to $Z$ . In the following calculation, we emphasize that the values $N(x)$ and $\zeta _i(x)$ only depend on $\pi _Z(x)$ . Applying the law of total probability with respect to the possibilities for $\pi _W(x)$ we find that the probability that $\psi _i(x)\in E_{y+\zeta _i(x)}$ for every $i$ is at most

\begin{align*} \sum _{w_1 \in E_{y+\zeta _1(x)},\dots , w_m \in E_{y+\zeta _m(x)}} (|H_1|^{-m} + \exp (\!-r'e(H_1)^{-2}/|S|)) \end{align*}

which in turn is bounded above by

\begin{align*} (1-|H_1|^{-1})^{N(x)}+|H_1|^m\exp (\!-r'e(H_1)^{-2}/|S|) \end{align*}

since the number $|E_{y+\zeta _1(x)}| \dots |E_{y+\zeta _m(x)}|$ of summands is at most $|H_1|^m (1-|H_1|^{-1})^{N(x)}$ .

We now drop the conditioning on $\pi _Z(x)$ . Let $q=|S|^{-|S|e(H)^2(\!\log (2|H|))^2}$ . The probability that $\psi _i(x)\in E_{y+\zeta _i(x)}$ for every $i$ is at most

\begin{align*} \sum _{j=0}^m \mathbb{P}_{z \in S^Z}(N(z) = j) (1-|H_1|^{-1})^j + |H_1|^m\exp (\!-r'e(H_1)^{-2}/|S|). \end{align*}

Because $(1-|H_1|^{-1})^j$ decreases with $j$ , the first sum is at most $\sum _{j=0}^m A(j) (1-|H_1|^{-1})^j$ whenever a probability distribution $A$ satisfies

\begin{align*} \sum _{u=0}^j \mathbb{P}_{z \in S^Z}(N(z) = u) \le \sum _{u=0}^j A(u) \end{align*}

for every $j=0,\dots ,m$ . By definition of $q$ (and because $q \le 1/2$ ) we may take $A(j) = \binom {m}{j} (1-q)^{m-j} q^j$ . The probability that $\psi _i(x)\in E_{y+\zeta _i(x)}$ for every $i$ is therefore at most

\begin{align*} &\sum _{j=0}^m\binom mj(1-q)^{m-j}q^j(1-|H_1|^{-1})^{j}+|H_1|^m\exp (\!-r'e(H_1)^{-2}/|S|)\\ &\quad=(1-q|H_1|^{-1})^m+|H_1|^m\exp (\!-r'e(H_1)^{-2}/|S|)\\ &\quad\leq \exp (\!-mq|H_1|^{-1})+|H_1|^m\exp (\!-r'e(H_1)^{-2}/|S|), \end{align*}

where the equality follows from the binomial theorem.

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

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 \gt 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^n$ to $H$ , each $\psi _i$ is a map from $G^n$ 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} \gt 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 \gt 0$ and for all pairs $(H_2,r)$ such that $H_2$ is a strict subgroup of $H_1$ , or such that $H_2=H_1$ and $r \lt r_{H_1}$ . Let $\epsilon \gt 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|^{|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}'\!)$ -separated for $r_{H_1}' = \lceil \log (2|H||H_1|^m/\epsilon )|S|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 the union $Z$ of the supports of the maps $\zeta _j$ with $j \in M$ , 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}'$ from a product of the form $\prod _{m\in M}\chi _m\circ \psi _m$ , meaning that the set of $j$ such that

\begin{align*} x_j \to \chi (\psi _{ij}(x_j)) \bigg(\prod _{m \in M} \chi _m(\psi _{mj}(x_j))\bigg)^{-1} \end{align*}

is non-constant on $S$ has size at most $r_{H_1}t_{H_1}+r_{H_1}'$ . 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 $r_{H_1}|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 $\zeta _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 '\,:\,G^n\to H$ be the homomorphism that takes $x$ to $\gamma + \xi (x_z)$ . Then each map $\theta _i-\gamma '$ with $i\in I_{(\xi ,z)}$ is a homomorphism of support size at most $r_{H_1}-1$ , so the homomorphisms $\theta _i= \gamma ' + (\theta _i-\gamma ')$ live in a ball of radius at most $r_{H_1}-1$ with centre $\gamma '$ . By Remark 5.3 it suffices to approximate each set $\{(\theta _i + \psi _i, E)\,:\, 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}'$ 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}')$ , and therefore we can write $\psi -\psi _0$ as a sum of a map $\theta '$ of support size at most $2(r_{H_1}t_{H_1}+r_{H_1}')$ and a map $\psi '$ 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'+\psi _0+\psi _i'$ , where the $\theta _i$ form a symmetric sunflower of radius at most $r_{H_1}$ , the $\theta _i'$ have support size at most $2(r_{H_1}t_{H_1}+r_{H_1}'\!)$ , $\psi _0$ is fixed, and the $\psi _i'$ take values in $H_2$ . Note that the maps $\theta _i+\theta _i'+\psi _0$ are contained in a ball of radius at most $r_{H_2}=r_{H_1}(2t_{H_1}+1)+2r_{H_1}'$ .

Let us write $\theta _i+\theta _i'+\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.