5 Finite field model

Theorem 5.1

If \(A_1,A_2,S\subseteq \mathbb {F}_q^n\) are such that \(A_1\) and \(A_2\) both have density at least \(\alpha \) then there is a subspace \(V\) of codimension

\[ \mathrm{codim}(V)\leq 2^{27}\mathcal{L}{(}\alpha )^2\mathcal{L}{(}\epsilon \alpha )^2\epsilon ^{-2} \]

such that

\[ \left\lvert \langle \mu _V\ast \mu _{A_1}\ast \mu _{A_2},1_{S}\rangle -\langle \mu _{A_1}\ast \mu _{A_2},1_{S}\rangle \right\rvert \leq \epsilon . \]

Proof ▶

(In this proof we write \(G=\mathbb {F}_q^n\).) Let \(k=\lceil \mathcal{L}{(}\epsilon \alpha /4)\rceil \). Note that \(\lvert A_1+G\rvert =\lvert G\rvert \leq \alpha ^{-1}\lvert A\rvert \). Furthermore, \(\lvert A_2\rvert /\lvert S\rvert \geq \alpha \). Therefore by Theorem 1.8 there exists some \(T\subseteq G\) with

\[ \lvert T\rvert \geq \exp (-2^{16}\mathcal{L}{(}\alpha )^2k^2\epsilon ^{-2})\lvert S\rvert \]

such that

\[ \| \mu _T^{(k)}\ast \mu _{A_1}\ast \mu _{A_2}\circ 1_{S}-\mu _{A_1}\ast \mu _{A_2}\circ 1_{S}\| _{\infty }\leq \epsilon /4. \]

Let \(\Delta =\Delta _{1/2}(\mu _T)\) and

\[ V = \{ x \in G : \gamma (x)=1\textrm{ for all }\gamma \in \Delta \} . \]

Note that

\[ \langle \mu _V\ast \mu _{A_1}\ast \mu _{A_2},1_{S}\rangle = \langle \mu _V,\mu _{A_1}\ast \mu _{A_2}\circ 1_{S}\rangle =\frac{1}{\left\lvert V\right\rvert }\sum _{v\in V}\mu _{A_1}\ast \mu _{A_2}\circ 1_{S}(v) \]

and

\[ \langle \mu _{A_1}\ast \mu _{A_2},1_{S}\rangle = \mu _{A_1}\ast \mu _{A_2}\circ 1_{S}(0). \]

Therefore

\[ \left\lvert \langle \mu _V\ast \mu _{A_1}\ast \mu _{A_2},1_{S}\rangle -\langle \mu _{A_1}\ast \mu _{A_2},1_{S}\rangle \right\rvert \leq \frac{1}{\left\lvert V\right\rvert }\sum _{v\in V}\left\lvert \mu _{A_1}\ast \mu _{A_2}\circ 1_{S}(v)-\mu _{A_1}\ast \mu _{A_2}\circ 1_{S}(0)\right\rvert . \]

In particular it suffices to show that, for any \(v\in V\),

\[ \left\lvert \mu _{A_1}\ast \mu _{A_2}\circ 1_{S}(v)-\mu _{A_1}\ast \mu _{A_2}\circ 1_{S}(0)\right\rvert \leq \epsilon . \]

By the triangle inequality and construction of \(T\), it suffices to show that

\[ \left\lvert \mu _T^{(k)}\ast \mu _{A_1}\ast \mu _{A_2}\circ 1_{S}(v)-\mu _T^{(k)}\ast \mu _{A_1}\ast \mu _{A_2}\circ 1_{S}(0)\right\rvert \leq \epsilon /2. \]

By the Fourier transform we have, for any \(x\in G\),

\[ \mu _T^{(k)}\ast \mu _{A_1}\ast \mu _{A_2}\circ 1_{S}(x)=\frac{1}{N}\sum _{\gamma \in \widehat{G}}\widehat{\mu _T}(\gamma )^k\widehat{\mu _{A_1}}(\gamma )\widehat{\mu _{A_2}}(\gamma )\widehat{1_{-S}}(\gamma )\gamma (x). \]

Therefore the left-hand side of the desired inequality is, by the triangle inequality, at most

\[ \frac{1}{N}\sum _{\gamma \in \widehat{G}}\left\lvert \widehat{\mu _T}(\gamma )\right\rvert ^k\left\lvert \widehat{\mu _{A_1}}(\gamma )\widehat{\mu _{A_2}}(\gamma )\widehat{1_{-S}}(\gamma )\right\rvert \left\lvert \gamma (v)-1\right\rvert . \]

By choice of \(v\in V\) the summand vanishes when \(\gamma \in \Delta \). When \(\gamma \not\in \Delta \) the summand is bounded above by

\[ 2^{1-k}\left\lvert \widehat{\mu _{A_1}}(\gamma )\widehat{\mu _{A_2}}(\gamma )\widehat{1_{-S}}(\gamma )\right\rvert . \]

Therefore the left-hand side of the desired inequality is at most

\[ 2^{1-k}\frac{1}{N}\sum _{\gamma }\left\lvert \widehat{\mu _{A_1}}(\gamma )\widehat{\mu _{A_2}}(\gamma )\widehat{1_{-S}}(\gamma )\right\rvert \leq 2^{1-k}\left\lvert S\right\rvert \frac{1}{N}\sum _{\gamma }\left\lvert \widehat{\mu _{A_1}}(\gamma )\widehat{\mu _{A_2}}(\gamma )\right\rvert \]

using the trivial bound \(\lvert \widehat{1_{S}}\rvert \leq \left\lvert S\right\rvert \). By the Cauchy-Schwarz inequality the sum on the right is at most

\[ \left( \sum _\gamma \left\lvert \widehat{\mu _{A_1}}\right\rvert ^2\right)^{1/2}\left( \sum _\gamma \left\lvert \widehat{\mu _{A_2}}\right\rvert ^2\right)^{1/2}. \]

By Parseval’s identity this is at most \(\alpha ^{-1}\). Therefore the desired inequality follows from

\[ 2^{1-k}\left\lvert S\right\rvert \frac{1}{N}\alpha ^{-1}\leq 2^{1-k}\alpha ^{-1}\leq \epsilon /2. \]

It remains to check the codimension of \(V\). For this, let \(\Delta '\subseteq \Delta \) be as provided by Chang’s lemma, Lemma 2.12, so that

\[ \Delta \subseteq \left\{ \sum _{\gamma \in \Delta '}c_\gamma \gamma : c_\gamma \in \{ -1,0,1\} \right\} . \]

Let

\[ W= \{ x \in G : \gamma (x)=1\textrm{ for all }\gamma \in \Delta '\} . \]

It follows that \(W\leq V\), so it suffices to bound the codimension of \(W\). This we can bound trivially using the bound from Chang’s lemma and the fact that \(\mathcal{L}{(}\delta )=\log (e^2/\delta )\leq 2+\log (1/\delta )\leq 4\log (1/\delta )\), provided \(\log (1/\delta )\geq 1\), so

\[ \left\lvert \Delta '\right\rvert \leq \lceil 4e\mathcal{L}(\delta )\rceil \leq 2^7\log (1/\delta ), \]

where

\[ \delta =\left\lvert T\right\rvert /N\geq \exp (-2^{16}\mathcal{L}{(}\alpha )^2k^2\epsilon ^{-2}), \]

\[ \mathrm{codim}(V)\leq \left\lvert \Delta '\right\rvert \leq 2^{23}\mathcal{L}{(}\alpha )^2k^2\epsilon ^{-2}\leq 2^{25}\mathcal{L}{(}\alpha )^2\mathcal{L}{(}\epsilon \alpha /4)^2\epsilon ^{-2}, \]

and now use \(\mathcal{L}{(}\epsilon \alpha /4)\leq 2\mathcal{L}{(}\epsilon \alpha )\), say.

Lemma 5.2

✓

For any function \(f:G\to \mathbb {C}\) and integer \(k\geq 1\)

\[ \| f\ast f\| _{2k}\leq \| f\circ f\| _{2k}. \]

Proof ▶

To finish, similar trick to unbalancing.

Lemma 5.3

✓

For any function \(f\) with \(\sum f(x)=1\)

\[ f\ast f-1/N = (f-1/N)\ast (f-1/N). \]

Proof ▶

Expand everything out.

Lemma 5.4

✓

For any function \(f\) with \(\sum f(x)=1\)

\[ f\circ f-1/N = (f-1/N)\circ (f-1/N). \]

Proof ▶

Expand everything out.

Lemma 5.5

✓

Let \(\epsilon {\gt}0\) and \(\mu \equiv 1/N\). If \(A,C\subseteq G\), where \(C\) has density at least \(\gamma \), and

\[ \left\lvert N\langle \mu _A\ast \mu _A,\mu _C\rangle -1\right\rvert {\gt}\epsilon \]

then, if \(f=(\mu _A-1/N)\), \(\lVert f\circ f\rVert _{p(\mu )} \geq \epsilon /2N\) for \(p=2\lceil \mathcal{L}{(}\gamma )\rceil \).

Proof ▶

By Hölder’s inequality, for any \(p\geq 1\)

\[ \epsilon {\lt} \left\lvert N\langle \mu _A \ast \mu _A - 1/N, \mu _C \rangle \right\rvert \leq \lVert \mu _A\ast \mu _A-1/N\rVert _p\gamma ^{-1/p}N^{1-1/p}. \]

In particular if we choose \(p=2\lceil \mathcal{L}{(}\gamma )\rceil \) then \(\gamma ^{-1/p}\leq e^{1/2}\leq 2\) and so we deduce that, by Lemma 5.3,

\[ \lVert f\ast f\rVert _{p}\geq \tfrac {1}{2}\epsilon N^{1/p-1}. \]

It remains to use Lemmas 5.3 and 5.4 and apply Lemma 5.2, and note that we can pass from the \(L^p\) norm to the \(L^p(\mu )\) norm losing a factor of \(N^{1/p}\).

Proposition 5.6

✓

Let \(\epsilon \in (0,1)\). If \(A,C\subseteq \mathbb {F}_q^n\), where \(C\) has density at least \(\gamma \), and

\[ \left\lvert N\langle \mu _A\ast \mu _A,\mu _C\rangle -1\right\rvert {\gt} \epsilon \]

then there is a subspace \(V\) of codimension

\[ \leq 2^{171}\epsilon ^{-24}\mathcal{L}{(}\alpha )^4\mathcal{L}{(}\gamma )^4. \]

such that \(\lVert 1_{A}\ast \mu _V\rVert _\infty \geq (1+\epsilon /32)\alpha \).

Proof ▶

By Lemma 5.5, if \(f=\mu _A-1/N\),

\[ \lVert f\circ f\rVert _{p(\mu )}\geq \epsilon /2N, \]

where \(p=2\lceil \mathcal{L}{(}\gamma )\rceil \leq 4\mathcal{L}{(}\gamma )\). By Lemma 3.2 there exists some \(p'\) such that

\[ p'\leq 128\epsilon ^{-1}\log (96/\epsilon )\mathcal{L}{(}\gamma ) \]

such that

\[ \lVert f\circ f+1/N\rVert _{p'(\mu )}\geq (1+\epsilon /4)/N. \]

By Lemma 5.4 \(f\circ f+1/N=\mu _A\circ \mu _A\).

Let \(q=2\lceil p'+2^8\epsilon ^{-2}\log (64/\epsilon )\rceil \). By Corollary 4.3, there are \(A_1,A_2\), both of density \(\geq \alpha ^{2q}\) such that

\[ \langle \mu _{A_1}\circ \mu _{A_2},1_{S}\rangle \geq 1-\epsilon /32 \]

where

\[ S=\{ x : \mu _A\circ \mu _A(x)\geq (1-\epsilon /16)\| \mu _A\circ \mu _A\| _{q(\mu )}\} . \]

Since

\[ \| \mu _A\circ \mu _A\| _{q(\mu )}\geq \| \mu _A\circ \mu _A\| _{p'(\mu )}\geq (1+\epsilon /4)/N \]

we know

\[ S\subseteq S'=\{ x : \mu _A\circ \mu _A(x)\geq (1+\epsilon /8)/N\} . \]

By Theorem 5.1 (applied with \(\epsilon \) replaced by \(\epsilon /32\)) there is a subspace \(V\) of codimension

\[ \leq 2^{37}\mathcal{L}{(}\alpha ^{2q})^2\mathcal{L}{(}\epsilon \alpha ^{2q}/32)^2\epsilon ^{-2} \]

such that

\[ \langle \mu _V\ast \mu _{A_1}\circ \mu _{A_2},1_{S'}\rangle \geq 1-\tfrac {1}{16}\epsilon . \]

Using \(\mathcal{L}{(}xy)\leq x^{-1}\mathcal{L}{(}y)\) we have

\[ \mathcal{L}{(}\epsilon \alpha ^{2q}/32)\leq 32\epsilon ^{-1}\mathcal{L}{(}\alpha ^{2q}), \]

and we also use \(\mathcal{L}{(}x^y)\leq y\mathcal{L}{(}x)\) to simplify the codimension bound to

\[ \leq 2^{51}q^4\mathcal{L}{(}\alpha )^4\epsilon ^{-4}. \]

We further note that (using \(\log x\leq x\) say)

\[ q\leq 2^{10}p'\epsilon ^{-2}\log (64/\epsilon )\leq 2^{30}\epsilon ^{-5}\mathcal{L}{(}\gamma ). \]

Therefore the desired codimension bound follows. Finally, by definition of \(S'\), it follows that

\begin{align*} (1+\epsilon /32)/N & \leq ((1+\epsilon /8)/N)(1-\epsilon /16)\\ & \leq \langle \mu _V\ast \mu _{A_1}\circ \mu _{A_2},\mu _A\circ \mu _A\rangle \\ & \leq \lVert \mu _V\ast \mu _A\rVert _\infty \lVert \mu _{A}\ast \mu _{A_2}\circ \mu _{A_1}\rVert _1\\ & = \lVert \mu _V\ast 1_{A}\rVert _\infty \left\lvert A\right\rvert ^{-1}, \end{align*}

and the proof is complete.

Lemma 5.7

✓

If \(A\subseteq G\) has no non-trivial three-term arithmetic progressions and \(G\) has odd order then

\[ \langle \mu _A\ast \mu _A,\mu _{2\cdot A}\rangle = 1/\left\lvert A\right\rvert ^2. \]

Proof ▶

Expand out using definitions.

Theorem 5.8

✓

Let \(q\) be an odd prime power. If \(A\subseteq \mathbb {F}_q^n\) with \(\alpha =\left\lvert A\right\rvert /q^n\) has no non-trivial three-term arithmetic progressions then

\[ n \ll \mathcal{L}{(}\alpha )^9. \]

Proof ▶

Let \(t\geq 0\) be maximal such that there is a sequence of subspaces \(\mathbb {F}_q^n=V_0\geq \cdots \geq V_t\) and associated \(A_i\subseteq V_i\) with \(A_0=A\) such that

for \(0\leq i\leq t\) there exists \(x_i\) such that \(A_i\subseteq A-x_i\),
with \(\alpha _i=\left\lvert A_i\right\rvert /\left\lvert V_i\right\rvert \) we have

\[ \alpha _{i+1}\geq \frac{65}{64}\alpha _i \]

for \(0\leq i{\lt}t\), and
\[ \mathrm{codim} (V_{i+1}) \leq \mathrm{codim}(V_i)+O(\mathcal{L}{(}\alpha )^8) \]

for \(0\leq i{\lt}t\). (here the second summand should be replaced with whatever explicit codimension bound we get from the above).

Note this is well-defined since \(t=0\) meets the requirements, and this process is finite and \(t \ll \mathcal{L}{(}\alpha )\), since \(\alpha _i\leq 1\) for all \(i\). Therefore

\[ \mathrm{codim}(V_t) \ll \mathcal{L}{(}\alpha )^9. \]

Suppose first that

\[ \lvert V_t\rvert \langle \mu _{A_t}\ast \mu _{A_t},\mu _{2\cdot A_t}\rangle {\lt}1/2. \]

In this case we now apply Proposition 5.6 to \(A_t\subseteq V_t\) with \(\epsilon =1/2\) (note that \(N=\lvert V_t\rvert \) and all inner product, \(\mu \) etc, are relative to the ambient group \(V_t\) now). Therefore there is a subspace \(V\leq V_t\) of codimension (relative to \(V_t\)) \(\ll \mathcal{L}{(}\alpha )^8\) such that there exists some \(x\in V_t\) with

\[ \frac{\lvert (A_t-x)\cap V\rvert }{\lvert V\rvert }=1_{A_t}\ast \mu _V(x)=\| 1_{A_t}\ast \mu _V\| _\infty \geq (1+1/64)\alpha _t, \]

which contradicts the maximality of \(t\), letting \(V_{t+1}=V\) and \(A_{t+1}=(A_t-x)\cap V_t\).

Therefore

\[ \lvert V_t\rvert \langle \mu _{A_t}\ast \mu _{A_t},\mu _{2\cdot A_t}\rangle \geq 1/2. \]

By Lemma 5.7 the left-hand side is equal to \(\lvert V_t\rvert /\lvert A_t\rvert ^2\), and therefore

\[ \alpha ^2 \leq \alpha _t^2 \leq 2/\lvert V_t\rvert . \]

By the codimension bound the right-hand side is at most

\[ 2q^{O(\mathcal{L}{(}\alpha )^9)-n}. \]

If \(\alpha ^2 \leq 2q^{-n/2}\) we are done, otherwise we deduce that \(\mathcal{L}{(}\alpha )^9 \gg n\) as required.