\documentclass[11pt]{article}
\usepackage{dhj}


\begin{document}

\title{Simplified GRS}

Here is a simplified version of the GRS theorem, with slightly better parameters.  It gives no improvement for our DHJ results, but might be worth including to illustrate some ideas.

\begin{theorem} Let $A \subseteq \{0,1\}^n$ have uniform density $\mu(A) = \delta \leq 1/2$ and assume $n \geq 30 \cdot (1/\delta)^{2^d}$. Then $A$ contains a $d$-dimensional subspace.
\end{theorem}
\begin{proof} (Sketch.)  Partition $[n] = I_1 \cup I_2 \cup \cdots \cup I_{d-1} \cup E$, where $\abs{I_j} = \lfloor n/4^{d-j} \rfloor$.  It follows that $\abs{E} \geq (2/3)n$.  

Let $C$ be a random chain over $\{0,1\}^{I_1}$, from $0^{I_1}$ up to $1^{I_1}$. Let $s$ and $t$ be i.i.d.\ Binomial$(\abs{I_1}, 1/2)$ random variables. We write $C(s)$ for the $s$th string in chain $C$.  Thus $C(s)$ and $C(t)$ are each uniformly random strings in $\{0,1\}^{I_1}$; they are not independent though, since they always form a (possibly degenerate) line.  We write $A_{C(s)}$ for $\{y \in \{0,1\}^{\overline{I_1}} : (C(s),y) \in A\}$.  Let $z$ be a uniformly random string in $\{0,1\}^{\overline{I_1}}$.  We have
\begin{multline*}
\Ex_{C, s, t}[\mu(A_{C(s)} \cap A_{C(t)})] = \Pr_{C,s,t,z}[(C(s),z), (C(t),z) \in A] = \Ex_{C,z}\left[\Pr_{s,t}[(C(s),z), (C(t),z) \in A]\right] \\
= \Ex_{C,z}\left[\Pr_{s}[(C(s),z) \in A]^2\right] \geq \Ex_{C,z}\left[\Pr_{s}[(C(s),z) \in A]\right]^2 = \Pr_{C,s,z}[(C(s),z) \in A]^2 = \Pr_{x \sim \mu}[x \in A] = \delta^2,
\end{multline*}
where on the second line we used the fact that $s$ and $t$ are i.i.d., and then used Cauchy-Schwarz.  We have 
\[
\Pr[s = t] = \Pr[\text{Bin}(2\abs{I_1},1/2) = \abs{I_1}] \leq \frac{1}{\sqrt{n/4^{d-1}}} = \frac{2^{d-1}}{\sqrt{n}},
\]
and hence
\[
\Ex_{C, s, t}[\mu(A_{C(s)} \cap A_{C(t)}) \mid s \neq t] \geq \delta^2 - \frac{2^{d-1}}{\sqrt{n}}.
\]
We can therefore fix distinct strings $x_1^{(0)} \prec x_1^{(1)} \in \{0,1\}^{I_1}$ and pass to a subset $A' \subseteq \{0,1\}^{\overline{I_1}}$ such that $(x_1^{(i)}, z) \in A$ for all $i = 0, 1$, $z \in A'$, and such that $\mu(A') \geq \delta^2 - 2^{d-1}/\sqrt{n}$. 

We now repeat this argument for the index set $I_2$.  This will give us another pair of distinct strings $x_2^{(0)} \prec x_2^{(1)} \in \{0,1\}^{I_2}$, and let us pass to a subset $A' \subseteq \{0,1\}^{\overline{I_1 \cup I_2}}$ with
\[
\mu(A') \geq \left(\delta^2 - \frac{2^{d-1}}{\sqrt{n}}\right)^2 - \frac{2^{d-2}}{\sqrt{n}} \geq \delta^4 - 2\delta^2 \cdot \frac{2^{d-1}}{\sqrt{n}} - \frac{2^{d-2}}{\sqrt{n}} \geq \delta^4 - \frac{2^{d-1}}{\sqrt{n}}.
\]
Continuing the argument we get $x_3^{(0)} \prec x_3^{(1)}$ and
\[
\mu(A') \geq \left(\delta^4 - \frac{2^{d-1}}{\sqrt{n}}\right)^2 - \frac{2^{d-3}}{\sqrt{n}} \geq \delta^8 - 2\delta^4 \cdot \frac{2^{d-1}}{\sqrt{n}} - \frac{2^{d-3}}{\sqrt{n}} \geq \delta^8 - \frac{2^{d-2}}{\sqrt{n}}.
\]

Etc.  Having repeated the argument $d-1$ times, we have a $(d-1)$-dimensional subspace $X \subseteq \{0,1\}^{I_1 \cup \cdots \cup I_{d-1}}$ and a subset $A' \subseteq \{0,1\}^E$, where $(x,y) \in A$ for all $x \in X$, $y \in A'$, and $\mu(A') \geq \delta^{2^{d-1}} - 4/\sqrt{n}$.  Now if this last quantity is at least $1/\sqrt{\abs{E}}$ then $A'$ contains a line by Sperner's theorem, and we consequently get a $d$-dimensional subspace in $A$.  But 
\[
\frac{1}{\sqrt{\abs{E}}} \leq \frac{1}{\sqrt{(2/3)n}} \leq \frac{1.3}{\sqrt{n}},
\]
and even this quantity is at most $\delta^{2^{d-1}} - 4/\sqrt{n}$, because $n \geq (5.3)^2/\delta^{2^{d}}$ by our initial assumption.
\end{proof}
\end{document}