2.1 Proof of Varnavides’s theorem

Note that for every equation $E$ , there is a constant $C$ such that for every prime $p\geq Cn$ every solution of $E$ with integers $x_i \in [n]$ over $\mathbb{F}_p$ is also a solution over $\mathbb{R}$ . Since we can always find a prime $Cn \leq p \leq 2Cn$ , this means that we can assume that $n$ itself is primeFootnote ³ and count solutions over $\mathbb{F}_n$ . So let $S$ be a subset of $\mathbb{F}_n$ of size $\varepsilon n$ and let $R=R_E(\varepsilon/2)$ . For $b=(b_0,b_1) \in (\mathbb{F}_n)^2$ and $x \in [R]$ let $f_{b}(x)=b_1x+b_0$ andFootnote ⁴ $f_{b}([R])=\{x \in [R]\,{:}\, f_{b}(x) \in S\}$ . Pick $b_0$ and $b_1$ uniformly at random from $\mathbb{F}_n$ and note that for any $x \in [R]$ the integer $f_{b}(x)$ is uniformly distributed in $\mathbb{F}_n$ . Hence,

\begin{equation*} \mathbb {E}|\,f_{b}([R])|=\varepsilon R\;. \end{equation*}

It is also easy to see that for every $x \neq y$ the random variables $f_b(x)$ and $f_b(y)$ are pairwise independent. Hence,

\begin{equation*} \mathrm {Var}|\,f_{b}([R])| \leq \varepsilon R\;. \end{equation*}

Therefore, by Chebyshev’s Inequality we have

\begin{equation*} \mathbb {P}\left [|\,f_{b}([R])| \leq \frac {\varepsilon }{2} R\right ] \leq \frac {\varepsilon R}{\varepsilon ^2 R^2/4} \leq 1/2\;. \end{equation*}

In other words, at least $n^2/2$ choices of $b$ are such that $|\,f_{b}([R])| \geq \frac{\varepsilon }{2}R$ . By our choice of $R$ , this means that $f_{b}([R])$ contains three distinct integers $x_1,x_2,x_3$ which satisfy $E$ and such that $f_{b}(x_i) \in S$ . Note that if $x_1,x_2,x_3$ satisfy $E$ , then so do $f_{b}(x_1),f_{b}(x_2),f_{b}(x_3)$ . Let us denote the triple $(f_{b}(x_1),f_{b}(x_2),f_{b}(x_3))$ by $s_{b}$ . We have thus obtained $n^2/2$ solutions $s_b$ of $E$ in $S$ . To conclude the proof, we just need to estimate the number of times we have double counted each solution $s_{b}$ . Observe that for every choice of $s_{b}=\{s_1,s_2,s_3\}$ and distinct $x_1,x_2,x_3 \in [R]$ , there is exactly one choice of $b=(b_0,b_1) \in (\mathbb{F}_n)^2$ for which $b_1x_i+b_0=s_i$ for every $1 \leq i \leq 3$ . Since $[R]$ contains at most $R^2$ solutions of $E$ this means that for every solution $s_1,s_2,s_3 \in S$ , there are at most $R^2$ choices of $b$ for which $s_{b}=\{s_1,s_2,s_3\}$ . We conclude that $S$ contains at least $n^2/2R^2$ distinct solutions, thus completing the proof.

2.2 Proof of Theorem 1.1

As in the proof above, we assume that $n$ is a prime and count the number of solutions of the equation $E:\,\sum ^4_{i=1}a_ix_i=0$ over $\mathbb{F}_n$ . Let $S$ be a subset of $\mathbb{F}_n$ of size $\varepsilon n$ , and let $d$ and $t$ be integers to be chosen later and let $X$ be some subset of $[t]^d$ to be chosen later as well. For every $b=(b_0,\ldots,b_d)\in (\mathbb{F}_n)^{d+1}$ and $x=(x_1,\ldots,x_d) \in X$ , we use $f_b(x)$ to denote $b_0+\sum ^d_{i=1}b_ix_i$ and $f_b(X)=\{x \in X\,{:}\,\, f_b(x) \in S\}$ . We call $b$ good if $|\,f_b(X)| \geq \varepsilon |X|/2$ . We claim that at least half of all possible choices of $b$ are good. To see this, pick $b=(b_0,\ldots,b_{d})$ uniformly at random from $(\mathbb{F}_n)^{d+1}$ , and note that for any $x \in X$ the integer $f_b(x)$ is uniformly distributed in $\mathbb{F}_n$ . Hence,

\begin{equation*} \mathbb {E}|\,f_b(X)|=\varepsilon |X|\;. \end{equation*}

It is also easy to see that for every $x \neq y \in X$ the random variables $f_b(x)$ and $f_b(y)$ are pairwise independent. Hence,

\begin{equation*} \mathrm {Var}|\,f_b(X)| \leq \varepsilon |X|\;. \end{equation*}

Therefore, by Chebyshev’s Inequality we haveFootnote ⁵

(1) \begin{equation} \mathbb{P}\left [ |\,f_b(X) | \leq \frac{\varepsilon }{2}|X|\right ] \leq 4/\varepsilon |X| \leq 1/2\;, \end{equation}

implying that at least half of the $b$ ’s are good. To finish the proof, we need to make sure that every such choice of a good $b$ will “define” a solution $s_b$ in $S$ in a way that $s_b$ will not be identical to too many other $s_{b'}$ . This will be achieved by a careful choice of $d$ , $t$ , and $X$ .

We first choose $X$ to be the largest subset of $[t]^d$ containing no three points on one line. We claim that

(2) \begin{equation} |X| \geq t^{d-2}/d\;. \end{equation}

Indeed, for an integer $r$ let $B_r$ be the points $x \in [t]^d$ satisfying $\sum ^d_{i=1}x^2_i=r$ . Then every point of $[t]^d$ lies on one such $B_r$ , where $1 \leq r \leq dt^2$ . Hence, at least one such $B_r$ contains at least $t^{d-2}/d$ of the points of $[t]^d$ . Furthermore, since each set $B_r$ is a subset of a sphere, it does not contain three points on one line.

We now turn to choose $t$ and $d$ . Let $C$ be such that $R_E(\varepsilon ) \leq (1/\varepsilon )^C$ . Set $a=\sum ^4_{i=1}|a_i|$ and pick $t$ and $d$ satisfying

(3) \begin{equation} (1/\varepsilon )^{2C} \geq t^d \geq \left (\frac{2dt^2a^d}{\varepsilon }\right )^C\;. \end{equation}

Taking $t=2^{\sqrt{\log 1/\varepsilon }}$ and $d=2C\sqrt{\log 1/\varepsilon }$ satisfiesFootnote ⁶ the above for all small enough $\varepsilon$ . Note that by (3) and our choice of $C$ , we have $R_E\left (\frac{\varepsilon }{2dt^2a^d}\right ) \leq t^d$ .

Let us call a collection of four vectors $x^1,x^2,x^3,x^4 \in X$ helpful if they are distinct, and they satisfy $E$ in each coordinate, that is, for every $1 \leq i \leq d$ we have $\sum ^4_{j=1}a_jx^j_i=0$ . We claim that for every good $r$ , there are useful $x^1,x^2,x^3,x^4 \in f_r(X)$ . To see this let $M$ denote the integers $1,\ldots,(at)^d$ and note that (2) along with the fact that $r$ is good implies that

(4) \begin{equation} |\,f_r(X)| \geq \varepsilon |X|/2 \geq \frac{\varepsilon t^d}{2t^2d} = \frac{\varepsilon }{2dt^2a^d}\cdot |M| \end{equation}

Now think of every $d$ -tuple $x \in X$ as representing an integer $p(x) \in [M]$ written in base $at$ . So we can also think of $f_r(X)$ as a subset of $[M]$ of density at least $\varepsilon/2dt^2a^d$ . By (3), we have

\begin{equation*} M = (at)^d \geq t^d \geq R_E\left (\frac {\varepsilon }{2dt^2a^d}\right )\;, \end{equation*}

implying that there are distinct $x^1,x^2,x^3,x^4 \in f_r(X)$ for which $\sum ^4_{j=1}a_j\cdot p(x^j)=0$ . But note that since the entries of $x^1,x^2,x^3,x^4$ are from $[t]$ , there is no carry when evaluating $\sum ^4_{j=1}a_j\cdot p(x^j)$ in base $at$ , implying that $x^1,x^2,x^3,x^4$ satisfy $E$ in each coordinate. Finally, the fact that $\sum _ja_j=0$ and that $x_i^1,x_i^2,x_i^3,x_i^4$ satisfy $E$ for each $1 \leq i \leq d$ allows us to deduce that

\begin{equation*} \sum ^4_{j=1}a_j \cdot f_b(x^j)=\sum ^4_{j=1}a_j \cdot \left(b_0+\sum ^d_{i=1}b_ix^j_i\right)=\sum ^d_{i=1}b_i\cdot \left(\sum ^4_{j=1}a_jx^j_i\right)=0\;, \end{equation*}

which means that $f_b(x^1),f_b(x^2),f_b(x^3),f_b(x^4)$ forms a solution of $E$ . So for every good $b$ , let $s_b$ be (some choice of) $f_b(x^1),f_b(x^2),f_b(x^3),f_b(x^4) \in S$ as defined above. We know from (1) that at least $n^{d+1}/2$ of all choices of $b$ are good, so we have thus obtained $n^{d+1}/2$ solutions $s_b$ of $E$ in $S$ . To finish the proof, we need to bound the number of times we have counted the same solution in $S$ , that is, the number of $b$ for which $s_b$ can equal a certain $4$ -tuple in $S$ satisfying $E$ .

Fix $s=\{s_1,s_2,s_3,s_4\}$ and recall that $s_{b}=s$ only if there is a helpful $4$ -tuple $x^1,x^2,x^3,x^4$ (as defined just before equation (4)) such that $f_{b}(x^i)=s_i$ . We claim that for every helpful $4$ -tuple $x^1,x^2,x^3,x^4$ , there are at most $n^{d-2}$ choices of $b=(b_0,\ldots,b_d)$ for which $s_b=s$ . Indeed recall that by our choice of $X$ the vectors $x^1,x^2,x^3$ are distinct and do not lie on one line. Hence, they are affine independentFootnote ⁷ over $\mathbb{R}$ . But since the entries of $x^i$ belong to $[t]$ and $t \leq 1/\varepsilon$ , we see that for large enough $n$ the vectors $x^1,x^2,x^3$ are also affine independent over $\mathbb{F}_n$ . This means that the system of three linear equations:

\begin{align*} b_0+b_1x^1_1+\ldots +b_dx^1_d=s_1 \\ b_0+b_1x^2_1+\ldots +b_dx^2_d=s_2 \\ b_0+b_1x^3_1+\ldots +b_dx^3_d=s_3 \end{align*}

(in $d+1$ unknowns $b_0,\ldots,b_d$ over $\mathbb{F}_n$ ) has only $n^{d-2}$ solutions, implying the desired bound on the number of choices of $b$ . Since $|X| \leq t^d \leq (1/\varepsilon )^{2C}$ by (3), we see that $X$ contains at most $(1/\varepsilon )^{8C}$ helpful $4$ -tuples. Altogether this means that for every $s_1,s_2,s_3,s_4 \in S$ satisfying $E$ , there are at most $(1/\varepsilon )^{8C}n^{d-2}$ choices of $b$ for which $s_b=s$ . Since we have previously deduced that $S$ contains at least $\frac 12n^{d+1}$ solutions $s_b$ , we get that $S$ contains at least $\frac 12\varepsilon ^{8C}n^3$ distinct solutions, as needed.