2. Proof overview for Theorem 1·2

In the same spirit as the arguments from [ Reference Frederickson and Yepremyan13, Reference Nelson and Nomoto19 ], our starting point will be the observation that in order to obtain an upper bound for $R_{\mathbb F_2}(2,d)$ , it will suffice to study a certain additive combinatorics problem.

Indeed, let us denote the additive group $\mathbb F_2^n$ by G and the identity vector $(0,\ldots,0)$ by $0_{G}$ for convenience, and then note that $R_{\mathbb F_2}(2,d)\gt n$ implies the existence of a partition of $G\setminus \{0_G\}$ into sets R and S such that:

• $R\cup \{0_G\} = G\setminus S$ does not contain a d-dimensional subspace;

• $S\cup \{0_G\}$ does not contain a 2-dimensional subspace.

The second bullet says that S does not contain any pattern of the form $x,y,x+y$ with $x,y \in \mathbb{F}_{2}^{n}$ and such that $x\neq y$ ; in other words, S is sum-free. This implies that $S+S\subset G\setminus S$ , which by the first bullet means that $S+S$ cannot contain a d-subspace.

We next note that the complement of S lacking d-dimensional subspaces tells us something about the density of S in G. To this end, we recall the following classical result going back to Bose and Burton [ Reference Bose and Burton7 ]:

The above result is sharp up to a factor of $\approx 2$ . Indeed, if $V^{\prime}\subset G$ has dimension $n+1-d$ , then $\dim(V^{\prime}\cap V)\geqslant 1$ for each $V\leqslant G$ with $\dim(V)=d$ . Thus, taking $S= V^{\prime}\setminus\{0_G\}$ , we have that $S^c$ contains no subspace with dimension d. In fact, [Reference Bose and Burton7, Theorem 2] shows that this construction of S is the worst-case scenario; however, for the sake of self-containment, we decided to instead state the slightly weaker version above in order to include a short probabilistic proof.

Proof. Sample $\mathbf{V}$ uniformly at random among all the d-dimensional subspaces of G. For every $s\in G\setminus \{0_G\}$ , we shall prove $P_s:\!= \mathbb P(s \in \mathbf{V})$ is equal to $(2^d-1)/(2^n-1)$ . Assuming this, the result follows by a union bound, since

$$ \mathbb P(\mathbf{V}\cap S\neq \emptyset)\leqslant |S|\frac{2^d-1}{2^n-1}\lt 1.$$

To start, note that for $s,s^{\prime}\in G\setminus \{0_G\}$ , there is an automorphism $\phi:G\to G$ sending s to s’ (by changing bases appropriately). Meanwhile, for any automorphism $\phi$ , the distribution of $\phi(\mathbf{V})$ should remain uniform over vector spaces of dimension d. Thus, there is some constant P such that $P_s = P$ for all $s\in G\setminus \{0_G\}$ . By double-counting, we get

\[2^d-1 = \mathbb E[|\mathbf{V}\setminus \{0_G\}|] = \sum_{s\in G\setminus\{0_G\}} \mathbb P(s\in \mathbf{V}) = (2^n-1)P,\]

which rearranges to give the result.

Putting together Observation 2·1 and Lemma 2·2, we arrive at the following reduction, first noted essentially in [ Reference Nelson and Nomoto19 ].

This naturally leads us to the following additive combinatorics problem, originally posed by Green in [ Reference Green15 ]: given a set $A \subset \mathbb{F}_{2}^{n}$ with density $\alpha \in [0,1]$ , what is the largest subspace that one can find in $A+A$ ?

In the case when $\alpha$ is fixed, the best known quantitative result for this problem comes from [ Reference Sanders22 ] (see also [ Reference Croot, Laba and Sisask10 ]).

Theorem 2·4 (Sanders). The exists an absolute constant $c\gt 0$ such that the following holds: for any subset $A\subset G\,:\!=\mathbb F_2^n$ , we have that $A+A$ contains a subset $V\leqslant G$ with

\[\dim(V)\geqslant c \mu(A) n.\]

Note that Theorem 2·4 combined with Observation 2·3 immediately tells us that

$$ R_{\mathbb F_2}(2,d) \leqslant \frac{d}{c}2^{d} \lt 2^{(1+o(1))d}.$$

In general, given $n\geqslant 1$ along with $\alpha\gt 0$ , define $f(n,\alpha)$ to be the maximal d such that: for every $A\subset \mathbb F_2^n$ with $\mu(A)\geqslant \alpha$ , there exists d-subspace $V\leqslant \mathbb{F}_{2}^{n}$ with $V\subset A+A$ . We briefly recall what is known here. Thus far in the literature, everyone has primarily focused on the regime where $\alpha\gt 0$ is fixed and then n tends to $\infty$ . Using this notation, Theorem 2·4 states that

(1) \begin{equation} f(n,\alpha) \gg \alpha n.\end{equation}

The best known upper bound for fixed $\alpha \in (0,1/2)$ is

\[f(n,\alpha) \leqslant n-(C_{\alpha}-o(1)) \sqrt{n},\]

where $C_{\alpha}\gt 0$ is chosen such that if $X\sim \mathcal N(0,1)$ is a standard Gaussian, then $\mathbb P(X\lt -C_{\alpha})=\alpha$ ; this is due to a beautiful “niveau-set construction” where A is taken to be set of vectors with Hamming weight at most $n/2-(C_{\alpha}/2-o(1)) \sqrt{n}$ . We refer to [Reference Sanders22, section 3] for more details. Despite the general belief that this upper bound is closer to the truth (i.e., that $f(n,\alpha)\geqslant (1-o(1))n$ ), Theorem 2·4 remains the ‘state-of-the-art’ in the fixed density regime.

Nevertheless, for the purposes of estimating $R_{\mathbb F_2}(2,d)$ it turns out that the density $\alpha$ goes to 0 very fast as n grows, and in this case our Theorem 1·3 improves substantially upon the result of Sanders. Using the new notation, Theorem 1·3 states the following: given $n\geqslant 1$ and $\alpha\gt 0$ ,

(2) \begin{equation} f(n,\alpha)+1\gg \left(\frac{n}{\mathcal L (\alpha)^5}\right)^{1/2}.\end{equation}

Indeed, note that (2) instantly implies that there exists an absolute constant $C\gt 0$ such that $f(Cd^7, 2^{-d})\geqslant d$ , and by Observation 2·3 this subsequently yields that $R_{\mathbb F_2}(2,d) = O(d^{7})$ .

2.1. Proof of Theorem 1·3

The new lower bound for $f(n,\alpha)$ from (2) can be proven using recent “approximate Bogolyubov–Ruzsa results”, which have been made possible by the recent breakthrough paper by Kelley and Meka [ Reference Kelley and Meka17 ].

Roughly speaking, an “exact Bogolyubov–Ruzsa result” takes a dense subset A, and then finds a large subspace V contained in some type of sumset of A (say $A-A$ ); meanwhile, an “approximate Bogolyubov–Ruzsa result” instead finds a large subspace V, such that the intersection of V with $A-A$ is at least a $(1-\epsilon)$ -fraction of V.

The specific result we need is the following lemma. Results like the one below are known to those familiar with the work of Kelley and Meka [ Reference Kelley and Meka17 ], but for completeness we note it follows from a more general result that we prove in the next section (see Remark 3·7).

Lemma 2·5. Let $G = \mathbb F_2^n$ and $A\subset G$ with $\alpha\,:\!=\mu(A)\gt 0$ . Given $\gamma\gt 0$ , we can find $V\leqslant G$ with $\mathrm{codim}(V)\ll \mathcal L (\alpha)^5\mathcal L (\gamma)^2$ , such that writing

\[D:\!= \left\{v\in V\,:\,\mu_A\circ \mu_A(v) \geqslant \frac{1}{2}\mu(V)^2\right\}\]

to denote the set of “locally popular diffences”, we have

\[\mu_V(D)\geqslant 1-\gamma.\]

Remark 2·6. To prove Theorem 1·3, it would be satisfactory to replace ‘D’ by ‘ $A-A$ ’. However, the proof easily gives this stronger form, so we saw no reason not to mention it.

The important property here is that the dependence on the codimension is polylogarithmatically-efficient with respect to both $1/\alpha$ and $1/\gamma$ (which should be optimal, up to the powers of logs).

Given Lemma 2·5, along with Lemma 2·2 from before, we may quickly obtain Theorem 1·3.

Proof of Theorem 1·3 assuming Lemma 2·5. Let $C_0$ be the implicit absolute constant from Lemma 2·5.

Then suppose we are given a non-empty subset $A\subset G\,:\!= \mathbb F_2^n$ , and write $\alpha\,:\!=\mu(A)\gt 0$ . Now, let C be some sufficiently large absolute constant. If $n\lt C\mathcal L (\alpha)^5$ , then the conclusion of Theorem 1·3 is trivially satisfied by taking $V = \{0_G\}$ which has dimension $0 \geqslant ({1}/{C})({n}/({\mathcal L (\alpha)^5}))^{1/2}-1$ .

Otherwise, by the largeness of C, we will have that $({n}/({2C_0\mathcal L (\alpha)^5}))\gt ({C}/({2C_0}))\gt 1$ . In which case we may take $\gamma\in (0,1)$ so that $C_0 \mathcal L (\alpha)^5\mathcal L (\gamma)^2 = n/2$ , meaning

\[\log_2(1/\gamma) = \left(\frac{n}{2C_0\mathcal L (\alpha)^5}\right)^{1/2}.\]

Write $d\,:\!=\lfloor ({n}/{2C_0\mathcal L (\alpha)^5}))^{1/2}\rfloor$ , so that $\gamma \leqslant 2^{-d}$ .

Applying Lemma 2·4 (which holds with the constant $C_0$ ) to the set A and the constant $\gamma$ , we can find some subspace $V\leqslant G$ with $\dim(V)\geqslant n/2$ , such that defining

\[D\,:\!=\left\{v\in V\,:\,\mu_A\circ \mu_A(v)\geqslant \frac{1}{2}\mu(V)^2\right\}\]

to be the set of locally popular differences, we have $\mu_V(D)\geqslant 1-\gamma$ . Noting that $D\subset A-A = A+A$ (recall that $A=-A$ , as $G=\mathbb F_2^n$ ), it will suffice to show that D contains a d-space (recalling $d\gg (n/\mathcal L (\alpha)^5)^{1/2}$ ).

We shall prove this using Lemma 2·2. Let $S\,:\!=V\setminus D$ , so that $D = S^c$ (where the complement is taken with respect to V). Clearly, $\mu_V(S)\leqslant \gamma \leqslant 2^{-d}$ ; so we will be done if we can confirm that the trivial non-degeneracy assumptions in Lemma 2·2 are also satisfied.

First, note that $\mu_A\circ\mu_A(0_V) = 1/\alpha \geqslant 1$ , thus $0_V\not \in S$ , as desired. Also, without loss of generality, we may suppose $n\geqslant 4$ . Whence, $d \leqslant n/2\leqslant \dim(V)$ (recalling $d\leqslant n^{1/2}$ ). This establishes the two non-degeneracy assumptions, and thus the result.

3. Proof of Theorem 1·4

A key ingredient of this section is the following density-increment result.

Then there exists a coset $U = t+V^{\prime}$ where $\mathrm{codim}(V^{\prime})\ll \mathcal L (\alpha)^4\mathcal L (\gamma)^2$ and $\mu_U(A)\geqslant (1+1/128)\alpha$ .

Our main result will be a variant of a “sparsity-expansion dichotomy” established by Chapman and Prendiville [Reference Chapman and Prendiville8, theorem 2·1].

With Proposition 3·3 in hand, it will be easy to deduce our multi-colour result. This can be done by setting $\alpha=\gamma\,:\!=({1}/{10r2^{r}})$ , and using the same sorts of reductions as in the last section. We defer the formal details to the end of this section, and first handle the proof of Proposition 3·3. As in [ Reference Chapman and Prendiville8, Reference Sanders23 ], let us start by first considering the following quantity.

Definition 3.4. Given a group G and subsets $S,X\subset G$ , denote by

$$ \mu_X^*(S)\,:\!=\max_{g\in G}\left\{\frac{|(g+X)\cap S|}{|X|}\right\}$$

the so-called maximal density of S within (translates of) X.

Whenever the underlying group G is the additive group $\mathbb{F}_{2}^{n}$ , we will actually only consider this quantity when X is a subspace of $\mathbb F_2^n$ . In this particular situation, we record the following simple observation.

Lemma 3·5. Consider subspaces $V^{\prime} \subset V \subset \mathbb{F}_{2}^{n}$ . Then

\[\mu_{V^{\prime}}^*(S)\geqslant \mu_V^*(S)\]

for every $S\subset \mathbb{F}_{2}^{n}$ .

Proof. This follows from an averaging argument. For convenience, let us write again $G:=\mathbb{F}_{2}^{n}$ . Pick $g_0 \in G$ such that

$$ \mu_V^*(S) = \mu_V(g_0+S) = \mu_{V-g_0}(S).$$

Since $V^{\prime} \subset V$ , we can pick $v_1,\dots,v_{\ell}\in V$ so that

\[\bigsqcup_{i=1}^\ell v_i+V^{\prime} = V.\]

Therefore,

\[\mu_{V-g_0}(S) = \mathbb E_{i\in [\ell]}[\mu_{V^{\prime}+v_i-g_0}(S)].\]

It follows that there must be some outcome i where $\mu_{V^{\prime}+v_i-g_0}(S)\geqslant \mu_{V-g_0}(S)$ , so

\[\mu_{V^{\prime}}^*(S) \geqslant \mu_{V^{\prime}+v_i-g_0}(S)\geqslant \mu_{V-g_0}(S) = \mu_V^*(S)\]

as desired.

We can now prove our main iteration lemma.

Next, take

\[D^{\prime}\,:\!=\left\{v\in V\,:\,\mu_{A^{\prime}}\circ \mu_{A^{\prime}}(v)\geqslant \frac{1}{2}\right\}.\]

Some renormalising gives the pointwise bound $\mu_A\circ \mu_A(x)\geqslant \mu_{A^{\prime}}\circ \mu_{A^{\prime}}(x)\cdot \mu(V)^2$ for $x\in G$ . Indeed, we have $\mu_A\circ\mu_A(x)\geqslant (\mu(A^{\prime})/\mu(A))^2 \mu_{A^{\prime}}\circ \mu_{A^{\prime}}(x)$ (as $A^{\prime}\subset A$ ), while $\mu(A^{\prime})\geqslant \mu(V)\mu(A)$ follows from unravelling definitions. Note $\mu(A^{\prime}) = \mu(V)\mu_V(A^{\prime})$ . By definition of A ^′ $\mu(A^{\prime})=\mu_V^*(A)$ . Finally Lemma 3·5 gives $\mu_V^*(A)\geqslant \mu_G^*(A) = \mu(A)$ .

It follows that the inclusion

\[D_i = \left\{v\in V\,:\,\mu_A\circ \mu_A(v)\geqslant \frac{1}{2}\mu(V)^2\right\}\supset D^{\prime},\]

thus our second assumption implies that $\mu_V(D^{\prime}) \leqslant 1-\gamma$ .

Take $C\,:\!=V\setminus D^{\prime}$ . We have that $\mu(C) \geqslant \gamma$ . Meanwhile, we have that $\langle \mu_{A^{\prime}}\circ \mu_{A^{\prime}},\mu_C\rangle \leqslant 1/2$ , whence we can apply Lemma 3·1 to find a coset $U=t+V^{\prime}$ with $V^{\prime}\leqslant V$ and $\mathrm{codim}(V^{\prime})-\mathrm{codim}(V)\ll \mathcal L (\alpha)^4\mathcal L (\gamma)^2$ , so that

\[\mu_U(A^{\prime}) \geqslant (1+1/128)\mu_V(A^{\prime}) =(1+1/128)\mu_V^*(A).\]

Noting that $\mu_{V^{\prime}}^*(A) \geqslant \mu_{V^{\prime}}((g-t)+A) \geqslant (1+1/128)\mu_V^*(A)$ completes the claim. (For $j\in [r]\setminus\{i\}$ , we get $\mu_{V^{\prime}}^*(A_j)\geqslant \mu_V^*(A_j)$ by Lemma 3·5.)

Now our main proposition follows from running an increment argument.

Proof of Proposition 3·3. Fix $A_1,\dots,A_r \subset G$ and $\alpha,\gamma$ as in the prompt.

Initialize with $V_0\,:\!=\mathbb F_2^n$ . Then at time $t = 0,1,\dots,$ we take

\[i_t\,:\!= \inf\left\{i\in [r]\,:\,\mu_{V_t}^*(A_i) \geqslant \alpha\text{ and }\mu_{V_t}(\{v\in V_t\,:\,\mu_{A_t}\circ \mu_{A_t}(v) \geqslant \frac{1}{2}\mu(V_t)^2\})\leqslant 1-\gamma\right\};\]

if $i_t = \infty$ (i.e., there are no such indices as above), then we halt at time $\tau\,:\!=t$ . Otherwise, we can invoke Proposition 3·6 to find some $V^{\prime}\leqslant V_t$ where $\mathrm{codim}(V^{\prime})-\mathrm{codim}(V_t) \ll \mathcal L (\alpha)^4\mathcal L (\gamma)^2$ , so that $\mu^*_{V^{\prime}}(A_{i_t})\geqslant (1+1/128)\mu_{V_t}^*(A_{i_t})$ . We define $V_{t+1}\,:\!=V^{\prime}$ and continue iterating the above (until we halt).

Note that this process must halt after $\tau\ll r\mathcal L (\alpha)$ steps, since for each $i\in [r]$ , there can be at most $128\mathcal L (\alpha)$ times t where $i_t = i$ . Indeed, if $\#(t^{\prime}\lt t:i_{t^{\prime}} = i) = m\gt 0$ , we get that

\[1\geqslant \mu_{V_t}(A_i)\geqslant (1+1/128)^m\alpha \geqslant 2^{m/128} \alpha.\]

Meanwhile, we have that $\mathrm{codim}(V_\tau) = \sum_{t=1}^\tau \mathrm{codim}(V_t)-\mathrm{codim}(V_{t-1}) \leqslant \tau O(\mathcal L (\alpha)^4\mathcal L (\gamma)^2)$ . Thus $\mathrm{codim}(V_\tau) \ll r \mathcal L (\alpha)^5\mathcal L (\gamma)^2$ . This gives the desired result since the sparsity-expansion dichotomy holds for $V_\tau$ .

3·1. Proof of Theorem 1·4 given Proposition 3·3

Let $\alpha = \gamma\,:\!={1}/{10r2^{d}}$ , and note that $L\,:\!=\mathcal L (\alpha) = \mathcal L (\gamma) = O(\log(r)+d)$ . Let $C_0$ be the implicit constant from Proposition 3·3, and consider $n\,:\!=2C_0 r\mathcal L (\alpha)^5\mathcal L (\gamma)^2= 2C_0rL^7 = O(r(\log(r)+d)^7)$ .

Furthermore, consider $G\,:\!= \mathbb F_2^n$ any choice of colour classes $A_1,\dots,A_r\subset G$ where each $A_i$ is sum-free (in particular, this implies $0\not\in A_i$ for each i). By Proposition 3·3 (with our sets $A_1,\dots,A_r$ and parameters $\alpha,\gamma$ ), we can find some subspace $V\leqslant G$ with $\dim(V)\geqslant n/2$ , so that the desired sparsity-expansion dichotomy holds. Then, for $i\in [r]$ , if $\mu_V(A_i)\lt \alpha$ , we set $S_i\,:\!=A_i$ , and otherwise we take

\[S_i\,:\!=\left\{v\in V: \mu_{A_i}\circ \mu_{A_i}(v) \lt\frac{1}{2}\mu(V)^2\right\}.\]

By the sparsity-expansion dichotomy, we have that $\mu_V(S_i) \leqslant {1}/{10r2^d}$ for each $i\in [r]$ ; and deterministically we have that $0\not \in S_i$ (since $0\not \in A_i$ by assumption, and if $A_i$ is non-empty, then $\mu_{A_i}\circ \mu_{A_i}(0) = 1/\alpha\geqslant 1\geqslant ({1}/{2})\mu(V)^2$ ).

Thus, writing

\[S\,:\!=\bigcup_{i=1}^r S_i,\]

we have that $0\not\in S$ and $\mu_V(S)\leqslant {1}/{10 2^d}$ (by union bound). Finally, recalling that $\dim(V)\geqslant n/2\geqslant d$ , we can invoke Lemma 2·2 to deduce that $S^c\,:\!=V\setminus S$ contains a subspace $V^{\prime}\leqslant V$ with $\dim(V^{\prime})\geqslant d$ , which is disjoint from S.

For each $i\in [r]$ , we have that $S \supset S_i$ , which implies V’ is disjoint from $A_i$ . Indeed, either we have that $S_i\,:\!=A_i$ (which directly implies disjointness), or $S_i \supset V\setminus (A_i-A_i)$ (which implies $V^{\prime}\subset A_i-A_i$ , meaning V ^′ should be disjoint from $A_i$ by sum-freeness). So, it follows that $V^{\prime}\subset G\setminus \bigcup_{i=1}^r A_i$ , which implies the claim.

4. Another application

In this section, we would like to note that our methods can be extended further to provide an even stronger form of Theorem 1·4 (namely, Theorem 4·1), which gives similar results for arbitrary finite-fields.

Given a prime $p \geqslant 2$ , let us say that a set $S\subset \mathbb F_p^n$ is solution-free, if there exists some choice $a,b\in \{1,\dots,p-1\}$ such that there is no $x,y,z\in S$ satisfying $a\cdot (x-y) = b\cdot z$ . Note that every sum-free set $A\subset \mathbb F_p^n$ is a solution-free set (by taking $a=b=1$ , and rearranging $(x-y)=z$ as $x=y+z$ ).

This definition is motivated by “homogeneous partition-regular equations” (discussed below). Obtaining quantitative bounds for colouring problems related to these equations is an important topic in additive combinatorics, as such questions represent generalisations of the celebrated theorem of Schur (which states that for any finite colouring of $\mathbb Z_{\gt 0}$ , there must be a colour class which is not sum-free). We will establish nearly sharp bounds in the finite-field setting for such problems.

In the integer setting, it is known that for any fixed $a,b\in \mathbb Z_+$ , and any $r\geqslant 1$ , there exists some finite N so that for any r-colouring $C:[N]\to [r]$ , we can find some monochromatic triple x,y,z such that $a(x-y) = bz$ . Specialising to the case of $a=b=1$ , this is the content of Schur’s Theorem (which alternatively says that [N] cannot be covered by r sum-free sets (assuming N is large enough with respect to r)). In [ Reference Cwalina and Schoen11 ], Cwalina and Schoen studied the growth of $N= N_{a,b}(r)$ for any fixed $a,b\in \mathbb Z_+$ as $r\to \infty$ . They demonstrated that

\[\exp(\Omega_{a,b}(r)) \leqslant N_{a,b}(r) \leqslant \exp(O_{a,b}(r^4\log(r)^4)).\]

We defer the interested reader to [ Reference Cwalina and Schoen11 ] for further motivation on the study of such quantities; here, we will provide some nearly sharp bounds to a finite-field analogue of this problem.

This in particular tells us that $\mathbb F_p^n \setminus \{0\}$ cannot be covered by $\ll n^{1-c}$ sum-free sets for any absolute constant $c\gt 0$ (recalling that sum-free sets are solution-free). By considering using dyadic intervals to cover each of the n coordinates, it is not hard to see that $O(\log(p)n)$ sum-free sets suffice to cover $\mathbb F_p^n$ , thus this is nearly sharp. It is conjectured that $\Omega(\log(p) n)$ sets are also required, due to connections with conjectures regarding the asymptotic growth of the r-colour Ramsey $R(3,\ldots,3)$ .

Previously, the best-known additive proofFootnote ¹ could only prove that $n^{1/3}$ sum-free sets are not sufficient to cover $\mathbb F_2^n\setminus \{0\}$ [Reference Chapman and Prendiville8, section 2]. For more general solution free-sets, the aforementioned upper bound of Cwalina–Schoen in the integer setting morally says that $n^{1/4-c}$ solution-free sets should not be enough to cover $\mathbb F_p^n\setminus \{0\}$ for any absolute constant $c\gt 0$ [Reference Cwalina and Schoen11, theorem 1·7].

The starting point (for proving Theorem 4·1) is [Reference Bloom and Sisask5, proposition 9].

Repeating the arguments from the last section, it is not difficult to establish the following more general result.

We will leave the details of establishing Proposition 4·3 to the interested reader. We now include the main ideas for how to prove Theorem 4·1 (at a high level).

The rough idea is that if $A_i$ is a solution-free set, with no solutions to $a\cdot (x-y) = b\cdot z$ , then defining $A_i^{\prime}\,:\!=a\cdot A_i$ , we have that $0\not\in A_i^{\prime}$ , and for any subspace $V\leqslant G$ , $\mu_V(A_i^{\prime}) = \mu_V(A_i)$ and $V\subset A_i^{\prime}-A_i^{\prime}$ implies $V\cap A_i = \emptyset$ . Meanwhile, similarly to Lemma 2·2, if $S\subset V\cong \mathbb F_p^n$ is a set with $0\not\in S$ and $\mu_V(S) \lt p^{-d}$ for some $d\leqslant n$ , then we have that there exists a subspace $V^{\prime}\subset V\setminus S$ with $\dim(V^{\prime})\geqslant d$ . One can now hope to argue in the same way as in Subsection 3.1 (now taking $\alpha = \gamma:\!= {1}/{10r p^d}$ ). We outline the argument below.

Proof sketch of Theorem 4·1. Consider $r,d\geqslant 1$ , and set $\alpha= \gamma:\!= {1}/{10 r p^d}$ . Note that $\mathcal L (\alpha) = O_p((\log(r)+d))$ .

Assume that $n\gt C_p r\mathcal L (\alpha)^5\mathcal L (\gamma)^2$ for some sufficiently large constant $C_p$ (which is allowed to depend on p); note that the lower bound on the right-hand side is $O_p(r(\log(r)+d)^7)$ .

Now consider any solution-free sets $A_1,\dots,A_r\subset \mathbb F_p^n$ . For each i, we can find some $a,b\in \{1,\dots,p-1\}$ , so that there is no $x,y,z\in A_i$ satisfying $a\cdot (x-y)=b\cdot z$ ; set $A_i^{\prime}\,:\!=a\cdot A_i$ .

Using Proposition 4·3, we can find $V\leqslant \mathbb F_p^n$ with $\dim(V)\geqslant n/2 \geqslant d$ , and a partition $[r] = I_1\sqcup I_2$ , so that:

1. (1) $\mu_V(A_i^{\prime}) \leqslant\alpha$ for $i\in I_1$ ;

2. (2) $\mu_V(V\setminus (A_i^{\prime}-A_i^{\prime}))\leqslant \gamma$ for $i\in I_2$ .

For $i\in I_1$ , set $S_i\,:\!=A_i^{\prime}$ , and for $i\in I_2$ , set $S_i\,:\!=V\setminus (A_i^{\prime}-A_i^{\prime})$ . As discussed above, since $A_i$ is solution-free, if $V^{\prime}\leqslant V$ is disjoint from $S_i$ , then V’ is disjoint from $A_i$ .

Now, taking $S\,:\!=\bigcup_{i=1}^r S_i$ , we get that $\mu_V(S) \leqslant \sum_{i=1}^r \mu_V(S_i) \leqslant {1}/{10rp^d}\lt p^{-d}$ . Furthermore, it is easy to show that $0\not\in S$ . Thus (using the analog of Lemma 2·2 which we discussed previously) there exists some $V^{\prime}\leqslant V$ with $\dim(V^{\prime})\geqslant d$ which is disjoint from S, proving the theorem.

5. Concluding remarks and open problems

In this paper, we proved that $R_{\mathbb{F}_{2}}(2,d) =O(d^{7})$ , and more generally that

$$ R_{\mathbb F_2}^{(r)}(2;\,d)=O_{r}(d^{7})$$

holds for all $r \geqslant 2$ . We would like to begin this section by contrasting our multi-colour result with the following result of Alon and Rödl from [ Reference Alon and Rödl2 ], generalising the works of Ajtai-Komloś-Szemerédi [ Reference Ajtai, Komloś and Szemerédi1 ] and Kim [ Reference Kim18 ] about the usual off-diagonal Ramsey number R(3, m).

Theorem 5·1 (Alon-Rödl). Let $R^{(r)}(3;\,m)$ denote the r-colour Ramsey number $R(3,\ldots,3;\,m)$ . For every $r \geqslant 2$ , we have that

$$ R^{(r)}(3;\,m) = \Theta(m^{r}/ \operatorname{poly log} m).$$

For convenience, $\operatorname{poly log} m$ here stands for an unspecified polynomial factor in $\log m$ . For $r=2$ , $R^{(2)}(3;\,m)=R(3,m)$ , in which case Theorem 5·1 recovers (up to this polylogarithmic factor) the fact that $R(3,m) = \Theta(m^2 / \log m)$ . For every $r \geqslant 3$ , Theorem 5·1 implies for instance that

$$ \lim_{m \to \infty} \frac{R^{(r)}(3;\,m)}{R^{(r-1)}(3;\,m)} = \infty,$$

formerly a conjecture of Erdös and Sós [ Reference Erdös and Sós12 ] already in the case $r=3$ . It would be tempting to make the analogous conjecture for $R_{\mathbb{F}_{2}}^{(r)}(2;\,d)$ , namely that for every $r \geqslant 3$ ,

(3) \begin{equation} \lim_{d \to \infty} \frac{R_{\mathbb F_2}^{(r)}(2;\,d)}{R_{\mathbb F_2}^{(r-1)}(2;\,d)} = \infty\end{equation}

must always hold. However, despite the successful analogies between $R_{\mathbb{F}_{2}}(2,d)$ and R(3,m) thus far, we suspect (3) should not hold. Instead, we would like to make the following competing conjecture regarding the growth of $R_{\mathbb F_2}(2,d)$ .

Conjecture 1.

$$ R_{\mathbb F_2}(2,d) = \Theta(d).$$

A standard probabilistic construction can be used to see thatFootnote ² $R_{\mathbb F_2}(2,d) = \Omega(d)$ , so in order to prove Conjecture 1 it would suffice to show that $R_{\mathbb F_2}(2,d) = O(d)$ . Furthermore, note that

$$ R_{\mathbb F_2}^{(r)}(2;\,d) \leqslant R_{\mathbb F_2}^{(r-1)}(2;R_{\mathbb F_2}(2,d))$$

holds for every $r \geqslant 3$ . Therefore, if $R_{\mathbb F_2}(2,d) = O(d)$ , then $R_{\mathbb F_2}^{(r)}(2;\,d)=O_r(d)$ follows for every $r \geqslant 3$ as well. Moreover, it is clear that $R_{\mathbb F_2}^{(r)}(2,d) \geqslant R_{\mathbb F_2}^{(r-1)}(2,d)$ holds for every $r \geqslant 3$ , thus Conjecture 1 implies that $R_{\mathbb F_2}^{(r)}(2;\,d) = \Theta_{r}(d)$ holds for every $r \geqslant 2$ .

That being said, we still believe that it would be interesting to distinguish quantitatively between, say, $R_{\mathbb F_2}(2,d)$ and $R_{\mathbb F_2}(2,2,d)$ . For example, if (3) is too much to ask for, can one at least show that

$$ \lim_{d \to \infty}\left(R_{\mathbb F_2}^{(r)}(2;\,d) - R_{\mathbb F_2}^{(r-1)}(2;\,d)\right) = \infty$$

for every $r \geqslant 3$ ? In light of the additive combinatorics approach developed in this paper, an important problem that is directly relevant to the faith of Conjecture 1 seems to be the question of determining whether or not there exists some absolute constant $C\gt 0$ such that $f(Cd,2^{-d})\geqslant d$ for all $d\geqslant 1$ .

There are also several natural open problems that one may pose about the general behaviour of $R_{\mathbb{F}_{p}}(s,d)$ for other choices of $p,s \geqslant 2$ (as d goes to $\infty$ ). We would like to share a few of our favorite ones.

Conjecture 2. For every $s \geqslant 2$ , there exists some $C=C(s)\gt 0$ such that

$$ R_{\mathbb{F}_{2}}(s,d)=O(d^{C}).$$

In other words, we believe that $R_{\mathbb{F}_{2}}(s,d)$ is polynomial in d for every $s \geqslant 2$ . We suggest a possible approach, which could potentially extend the ideas of this paper. Given $n,k\geqslant 1$ and $\alpha \gt 0$ , define $f_k(n,\alpha)$ to be the largest d, such that given any $A\subset G\,:\!= \mathbb F_2^n$ with $\mu(A)\geqslant \alpha$ , we have that there exist some $V\leqslant G$ with $\dim(V) \geqslant d$ , such that for each $v_1,\dots,v_k\in V$ , there exists $a\in A\setminus V$ such that the parallelepiped

\[\left\{a+\sum_{i\in I} v_i\,:\,I\subset [k]\right\}\]

is contained entirely inside A. Note that $f_1(n,\alpha)$ is equal to the function $f(n,\alpha)$ we introduced previously.

Using arguments like before, one can show that if

\[f_{s-1}(n,2^{-d})\geqslant R_{\mathbb F_2}(s-1,d),\]

then we have that $R_{\mathbb F_2}(s,d)\leqslant n$ . Indeed, either the first colour class will be “sparse” (density $\lt 2^{-d}$ ), which implies a dimension d subspace in the complement, or one should be able to pass to some subspace V where every $(s-1)$ -dimensional V’ subspace has some disjoint ‘coset’/parallelepiped which can extend V’ to a s-subspace (thus V should be coloured to not have a red $(s-1)$ -subspace nor blue d-subspace, allowing us to iterate). Thus, if for each $k\geqslant 1$ , one could show that $f_k(Cd^C,2^{-d})\geqslant d $ for some constant $C=C_k$ , then $R_{\mathbb F_2}(s,d) \ll d^{O_s(1)}$ for every $s \geqslant 2$ . Furthermore, if $f_k(C_k d,2^{-d}) \geqslant d$ holds for some constant $C_k$ , the sketch above would readily imply that $R_{\mathbb F_2}(s,d)=O_s(d)$ for every $s \geqslant 2$ .

Last but not least, it would also be interesting to get reasonable bounds for the off-diagonal numbers in different finite fields. For example, it is already not clear how to extend the arguments of this paper to show that $R_{\mathbb F_3}(2,d)$ is polynomial in d. This presents new challenges, as now there is a difference between the set of 1-dimensional subspaces of $\mathbb F_3^n$ , and the set of non-zero points in this space (indeed, one can define a 2-colouring $C:\mathbb F_3^n\setminus \{0\}\to \{1,2\}$ so that $C(v)\neq C(2\cdot v)$ for all non-zero v, in which case every non-trivial subspace of $\mathbb F_3^n$ receives multiple colours). We currently do not have ideas for any additive combinatorial result that would readily give polynomial bounds in this setting.