4 Dependent random choice

Lemma 4.1

✓

Let \(p\geq 2\) be an even integer. Let \(B_1,B_2\subseteq G\) and \(\mu =\mu _{B_1}\circ \mu _{B_2}\). For any finite set \(A\subseteq G\) and function \(f:G\to \mathbb {R}_{\geq 0}\) there exist \(A_1\subseteq B_1\) and \(A_2\subseteq B_2\) such that

\[ \langle \mu _{A_1}\circ \mu _{A_2}, f\rangle \lVert 1_{A}\circ 1_{A}\rVert _{p(\mu )}^p\leq 2\langle (1_{A}\circ 1_{A})^p,f\rangle _\mu \]

and

\[ \min \left( \frac{\left\lvert A_1\right\rvert }{\left\lvert B_1\right\rvert },\frac{\left\lvert A_2\right\rvert }{\left\lvert B_2\right\rvert }\right)\geq \frac{1}{4}\left\lvert A\right\rvert ^{-2p}\lVert 1_{A}\circ 1_{A}\rVert _{p(\mu )}^{2p}. \]

Proof ▶

First note that the statement is trivially true (with \(A_1=B_1\) and \(A_2=B_2\), say) if \(\lVert 1_{A}\circ 1_{A}\rVert _{p(\mu )}^p=0\). We can therefore assume this is \(\neq 0\).

For \(s\in G^{p}\) let \(A_1(s)=B_1\cap (A+s_1)\cap \cdots \cap (A+s_{p})\), and similarly for \(A_2(s)\). Note that

\begin{align*} \langle (1_{A}\circ 1_{A})^p, f\rangle _\mu & =\sum _{x} \mu _{B_1}\circ \mu _{B_2}(x)(1_{A}\circ 1_{A}(x))^pf(x)\\ & =\sum _{b_1,b_2}\mu _{B_1}(b_1)\mu _{B_2}(b_2)1_{A}\circ 1_{A}(b_1-b_2)^{p}f(b_1-b_2)\\ & =\sum _{b_1,b_2}\mu _{B_1}(b_1)\mu _{B_2}(b_2)\left( \sum _{t\in G}1_{A+t}(b_1)1_{A+t}(b_2)\right)^{p}f(b_1-b_2)\\ & =\sum _{b_1,b_2}\mu _{B_1}(b_1)\mu _{B_2}(b_2)\sum _{s\in G^p}1_{A_1(s)}(b_1)1_{A_2(s)}(b_2)f(b_1-b_2)\\ & =\left\lvert B_1\right\rvert ^{-1}\left\lvert B_2\right\rvert ^{-1}\sum _{s\in G^p}\langle 1_{A_1(s)}\circ 1_{A_2(s)}, f\rangle . \end{align*}

In particular, applying this with \(f\equiv 1\) we see that

\[ \lVert 1_{A}\circ 1_{A}\rVert _{p(\mu )}^p=\left\lvert B_1\right\rvert ^{-1}\left\lvert B_2\right\rvert ^{-1}\sum _s\left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert \]

and

\[ \frac{\langle (1_{A}\circ 1_{A})^p,f\rangle _\mu }{\lVert 1_{A}\circ 1_{A}\rVert _{p(\mu )}^p}=\frac{\sum _{s}\langle 1_{A_1(s)}\circ 1_{A_2(s)}, f\rangle }{\sum _s \left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert }=\eta , \]

say. Let \(M{\gt}0\) be some parameter, and let

\[ g(s) = \begin{cases} 1& \textrm{ if }0{\lt}\left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert {\lt}M^2\textrm{ and }\\ 0& \textrm{ otherwise.}\end{cases} \]

Then we have

\[ \sum _s g(s)\left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert {\lt}\sum _s M\left\lvert A_1(s)\right\rvert ^{1/2}\left\lvert A_2(s)\right\rvert ^{1/2}. \]

To see why, note first that each summand on the left-hand side is \(\leq \) the corresponding summand on the right-hand side, arguing by cases on whether \(g(s)=1\) or not. It therefore suffices to show that there exists some \(s\) such that the summand on the left-hand side is \({\lt}\) the corresponding summand on the right-hand side.

If \(g(s)=0\) for all \(s\) then choose some \(s\) such that \(\left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert \geq M^2\) (this must exist or else \(\left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert =0\) for all \(s\), but then \(\lVert 1_A\circ 1_A\rVert _{p(\mu )}^p=0\) by the above calculation). Otherwise, choose some \(s\) such that \(g(s)=1\), and note that for this \(s\) we have, by definition of \(s\),

\[ \left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert {\lt}M\left\lvert A_1(s)\right\rvert ^{1/2}\left\lvert A_2(s)\right\rvert ^{1/2}. \]

We now choose

\[ M=\tfrac {1}{2}\left\lvert A\right\rvert ^{-p}(\left\lvert B_1\right\rvert \left\lvert B_2\right\rvert )^{1/2}\lVert 1_{A}\circ 1_{A}\rVert _{p(\mu )}^p, \]

so that, by the Cauchy-Schwarz inequality,

\begin{align*} \sum _s g(s)\left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert & {\lt} M \sum _s \left\lvert A_1(s)\right\rvert ^{1/2}\left\lvert A_2(s)\right\rvert ^{1/2}\\ & \leq M\left( \sum _s \sum _{x\in G}1_{A_1(s)}(x)\right)^{1/2}\left( \sum _s \sum _{x\in G}1_{A_2(s)}(x)\right)^{1/2}\\ & = M\left\lvert A\right\rvert ^p(\left\lvert B_1\right\rvert \left\lvert B_2\right\rvert )^{1/2}\\ & =\frac{1}{2}\sum _s \left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert \end{align*}

and so

\[ \sum _s (1-g(s))\left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert {\gt} \frac{1}{2}\sum _s \left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert \]

whence

\[ \sum _s\langle 1_{A_1(s)}\circ 1_{A_2(s)},f\rangle =\eta \sum \left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert {\lt} 2\eta \sum _s \left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert (1-g(s)). \]

In particular there must exist some \(s\) such that

\[ \langle 1_{A_1(s)}\circ 1_{A_2(s)},f\rangle {\lt} 2\eta \left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert (1-g(s)). \]

We claim this \(s\) meets the requirements. The first is satisfied since the right-hand side is \(\leq 2\eta \left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert \). The second is satisfied since the left-hand side is trivially \(\geq 0\) and hence such an \(s\) must satisfy \(g(s)=0\), whence either \( \left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert \geq M^2\), that is,

\[ \left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert \geq \frac{1}{4}\left\lvert A\right\rvert ^{-2p}\left\lvert B_1\right\rvert \left\lvert B_2\right\rvert \lVert 1_{A}\circ 1_{A}\rVert _{p(\mu )}^{2p}, \]

or \(\left\lvert A_1(s)\right\rvert \left\lvert A_2(s)\right\rvert =0\), which can’t happen because then the right-hand side is \(=0\).

The final bound now follows since \(xy \leq \min (x,y)\) when \(x,y\leq 1\).

Lemma 4.2

✓

Let \(\epsilon ,\delta {\gt}0\) and \(p\geq \max (2,\epsilon ^{-1}\log (2/\delta ))\) be an even integer. Let \(B_1,B_2\subseteq G\), and let \(\mu =\mu _{B_1}\circ \mu _{B_2}\). For any finite set \(A\subseteq G\), if

\[ S=\{ x\in G: 1_{A}\circ 1_{A}(x){\gt}(1-\epsilon )\lVert 1_{A}\circ 1_{A}\rVert _{p(\mu )}\} , \]

then there are \(A_1\subseteq B_1\) and \(A_2\subseteq B_2\) such that

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

and

Proof ▶

Apply Lemma 4.1 with \(f=1_{G\backslash S}\). This produces some \(A_1\subseteq B_1\) and \(A_2\subseteq B_2\) such that

\[ \langle \mu _{A_1}\circ \mu _{A_2}, 1_{G\backslash S}\rangle \leq 2\frac{\langle (1_{A}\circ 1_{A})^p,1_{G\backslash S}\rangle _\mu }{\lVert 1_{A}\circ 1_{A}\rVert _{p(\mu )}^p} \]

and

It then suffices to note that

\[ \langle \mu _{A_1}\circ \mu _{A_2},1_{S}\rangle =1-\langle \mu _{A_1}\circ \mu _{A_2},1_{G\backslash S}\rangle \]

and by definition of \(S\) we have

\[ \langle (1_{A}\circ 1_{A})^p,1_{G\backslash S}\rangle _\mu \leq (1-\epsilon )^p\lVert 1_{A}\circ 1_{A}\rVert _{p(\mu )}^p\sum _{x}\mu (x)=(1-\epsilon )^p\lVert 1_{A}\circ 1_{A}\rVert _{p(\mu )}^p. \]

Now use the fact that \(p\geq \epsilon ^{-1}\log (2/\delta )\) together with the inequality \(1-x\leq e^{-x}\) to deduce that the right-hand side is \(\leq \tfrac {\delta }{2}\lVert 1_{A}\circ 1_{A}\rVert _{p(\mu )}^p\).

Corollary 4.3

✓

Let \(\epsilon ,\delta {\gt}0\) and \(p\geq \max (2,\epsilon ^{-1}\log (2/\delta ))\) be an even integer and \(\mu \equiv 1/N\). If \(A\subseteq G\) has density \(\alpha \) and

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

then there are \(A_1,A_2\subseteq G\) such that

\[ \langle \mu _{A_1}\circ \mu _{A_2}, 1_S\rangle \geq 1-\delta \]

and both \(A_1\) and \(A_2\) have density

\[ \geq \frac{1}{4}\alpha ^{2p}. \]

Proof ▶

We apply Lemma 4.2 with \(B_1=B_2=G\). It remains to note that

\[ \| 1_A\circ 1_A\| _{p(\mu )}\geq \| 1_A\circ 1_A\| _{1(\mu )}=\lvert A\rvert ^2/N. \]