View source for Easy.tex

\section{Easy reductions} \label{sec:easy}

In this section we collect some easy reductions between various DHJ problems for use in our main proof.

\begin{proposition} \label{prop:edhj-equiv-dhj} For a given $k \geq 3$, the DHJ theorem is equivalent to the equal-slices DHJ theorem.
\end{proposition}
\begin{proof}
The fact that DHJ follows from equal-slices DHJ was sketched in Section~\ref{sec:outline-dist}; we give the full proof here, using Lemma~\ref{lem:distributions}.\ref{eqn:distrs-prd-eqs} and Proposition~\ref{prop:degen}.  The other direction has a very similar proof, using Lemma~\ref{lem:distributions}.\ref{eqn:distrs-eqs-prd}  and we omit it.

Suppose then that we have proven the equal-slices DHJ($k$).  Let $\unif_k^{\ot n}(A) \geq \delta$.  We use Lemma~\ref{lem:distributions}, taking $r =  n^{1/4} $, letting $J$ be an $[r, 4r]$-random subset of $[n]$, $x \sim \unif_k^{\otimes \barJ}$, $y \sim \eqs{k}^J$.  (Note that $2\ln n \leq r \leq n/2$ provided $n$ is at least a small universal constant.)  According to the lemma, the resulting distribution on the composite string $(x,y)$ is $\tau$-close to $\unif_k^{\ot n}$, where
\[
\tau = (2\sqrt{k - 1} + 2) \cdot r/\sqrt{n} \leq 2k\cdot r/\sqrt{n} = 2k/n^{1/4}.
\]
This is at most $\delta/3$ provided that $n \geq (6k/\delta)^4$.  In that case we conclude
\[
\Ex_{J,x}[\eqs{k}^J(A_x)] \geq \delta - \delta/3
\]
and so there must exist a restriction $(J,x)$ with $\abs{J} \geq r$ and $\eqs{k}^J(A_x) \geq 2\delta/3$.  By Proposition~\ref{prop:degen} the distributions $\eqs{k}^J$ and $\ens{k}^J$ have total variation distance at most $k(k-1)/r \leq k^2/n^{1/4}$, and this quantity is also at most $\delta/3$ provided $n \geq (3k(k-1)/\delta)^4$.  In that case $\ens{k}^J(A_x) \geq 2\delta/3 - \delta/3 = \delta/3$.  Finally, if $r \geq \edhj{k}{\delta/3}$ then we may use equal-slices DHJ($k$) to find a combinatorial line in $A_x$, and hence in $A$.  This holds provided $n \geq \edhj{k}{\delta/3}^4$.   Presuming that $\edhj{k}{\delta/3} \geq 3k(k-1)/\delta$, the last requirement on $n$ is strictest.  Hence we may take $\dhj{k}(\delta) = \edhj{k}{\delta/3}^4$.\noteryan{not the strongest of course, but it certainly doesn't matter for our bounds}
\end{proof}

The deduction of probabilistic multidimensional DHJ from the equal-slices version uses the handy property Lemma~\ref{lem:ens-compose}; we remark that we only need the $d = 1$ case for our overall proof:
\ignore{\begin{theorem}  \label{thm:dhj-dv} Let $m = n_{\ref{thm:dhj-d-ens}}(k,d,\delta/2,\ens{k})$.\noteryan{I.e., $m$ large enough that every set with $\ens{k}^m$ at least $\delta/2$ has a nondegen $d$-dim comb.\ subspace.}  Then for all $n \geq n_{\ref{thm:dhj-dv}}(k,d,\delta) := m$ and $A \subseteq [k]^n$, 
\[
\ens{k}^n(A) \geq \delta \quad\Rightarrow\quad \Pr_{\sigma \sim \ens{k+d}^n}[\sigma \subseteq A \text{ as a $d$-dimensional subspace}] \geq \eta_{\ref{thm:dhj-dv}}(k,d,\delta) := \frac{\delta}{2(k+d)^{2m}}.
\]
\end{theorem}}
\begin{proposition} \label{prop:pdhj-from-edhj}  For a given $k$, The probabilistic multidimensional DHJ theorem follows from the equal-slices multidimensional DHJ theorem.
\end{proposition}
\begin{proof}
We will show that one can take $\Pmdhj{k}{\delta}{d} = \emdhj{k}{\delta/2}{d}$. Let us write $m$ for this number. Let $x \sim \ens{m}^n$ and $y \sim \ens{k}^m$.\noteryan{Surely $m \geq k$.}  By Lemma~\ref{lem:ens-compose}, $y \circ x \sim \ens{k}^n$.  Hence if $A \subseteq [k]^n$ satisfies $\ens{k}^n(A) \geq \delta$, we get that $\ens{k}^m(A_x) \geq \delta/2$ with probability at least $\delta/2$ over $x$, where $A_x$ denotes $\{z \in [k]^m : z \circ x \in A\}$.  Call such $x$'s ``good''.  By our choice of $m$, for all good~$x$ we have that $A_x$ contains a $d$-dimensional subspace.  Thus by Proposition~\ref{prop:min-eqs}, a randomly drawn subspace $w \sim \ens{k+d}^m$ is in $A_x$ with probability at least $(k+d)^{-2m}$.  We conclude that with probability at least $\pmdhj{k}{\delta}{d} = (\delta/2)(k+d)^{-2m}$ over the choice of $x$ and $w$, the $d$-dimensional subspace $w \circ x$ is in $A$.  This completes the proof, since $w \circ x$ is distributed as $\ens{k+d}^n$ by Lemma~\ref{lem:ens-compose}.
\end{proof}

As we saw in Section~\ref{sec:prob-sperner}, there is an elementary proof of probabilistic DHJ($2$).  For completeness, we observe here that Lemma~\ref{lem:p-sperner} and Proposition~\ref{prop:degen} immediately\noteryan{pretty immediately} yield the following:
\begin{lemma} \label{lem:pdhj2} One may take $\Pdhj{2}{\delta} = 12/\delta^2$ and $\pdhj{2}{\delta} = \delta^2/2$.
\end{lemma}


\ignore{
\noteryan{The following \emph{could} be done under equal-slices, using Lemma~\ref{lem:distributions}.\ref{eqn:distrs-eqs-eqs}, if necessary.}
\begin{theorem}  \label{thm:dhj-d-prod} Let $d \in \N$, $0 < \delta < 1$, and let $\pi$ be a distribution on $[k]$.  Let $m_1 = n_{\ref{thm:dhj-d-prod}}(k,1,\delta/2,\pi)$\noteryan{Really, just a bound for DHJ(k) under $\pi^{\otimes n}$.}, $\eta = \delta/2(k+1)^{m_1}$, and $m_d = n_{\ref{thm:dhj-d-prod}}(k,d,\eta,\pi)$.  Then for all $n \geq n_{\ref{thm:dhj-d-prod}}(k,d+1,\delta,\pi) := m_1 + m_d$ and
and $A \subseteq [k]^n$,
\[
\pi^{\otimes n}(A) \geq \delta \quad\Rightarrow\quad  A \text{ contains a nondegenerate $(d+1)$-dimensional subspace.}
\]
\end{theorem}
\begin{proof}
Choose $J \subseteq [n]$ with $\abs{J} = m_1$ arbitrarily, and let $\barJ = [n] \setminus J$, so $|\barJ| \geq m_d$ by assumption.  Since $\pi^{\otimes n}(A) \geq \delta$, with probability at least $\delta/2$ over $y \sim \pi^{\otimes \barJ}$ we have $\pi^{\otimes J}(A_y) \geq \delta/2$.  Call such $y$'s ``good''.  Since $|J| \geq n_{\ref{thm:dhj-d-prod}}(k,1,\delta/2,\pi)$, we conclude that whenever $y$ is good, $A_y \subseteq [k]^J$ contains a nondegenerate line.  Since there are at most $(k+1)^{m_1}$ such lines in $[k]^J$, we conclude there must be a particular line  $\lambda$ over $[k]^J$ such that $\lambda \subseteq A_y$ for at least an $\eta$ fraction of $y \sim \pi^{\otimes \barJ}$.  Write $L$ for the set of such $y$'s.  Since $|\barJ| \geq n_{\ref{thm:dhj-d-prod}}(k,d,\eta,\pi)$, there must exist a nondegenerate $d$-dimensional subspace $\sigma$ over $[k]^{\barJ}$ such that $\sigma \subseteq L$.  Now $\lambda \times \sigma$ is a nondegenerate $(d+1)$-dimensional subspace contained in $A$.  
\end{proof}
}

The following observation was sketched in Section~\ref{sec:outline-insens}:

\begin{proposition} \label{prop:mdhj-insens}  The multidimensional DHJ($k$) theorem for $ab$-insensitive sets follows from the multidimensional DHJ($k-1$) theorem.  More precisely, let $k \geq 3$, $d \geq 1$, and assume we have established the multidimensional DHJ($k-1$) theorem.  Suppose $B \subseteq [k]^n$ is $ab$-insensitive on $I \subseteq [n]$ and has $\unif_k^{\otimes n}(B) \geq \delta$.  Then $B$ contains a $d$-dimensional subspace, provided $\abs{I} \geq 2\mdhj{k-1}{\delta/2}{d}$.
\end{proposition}
\begin{proof}
We may assume without loss of generality that $b = k$, by renaming symbols.  We may also assume $I = [n]$ without loss of generality; this is because we can always pass to a restriction $(I, x_{\overline{I}})$ on which $B$ has uniform density at least $\delta$.  So from now on we assume $B$ is an $ak$-insensitive subset of $[k]^n$, with $n \geq 2\mdhj{k-1}{\delta/2}{d}.$

Think of conditioning a draw from $\unif_k^{\otimes n}$ on the location of the symbols $k$.  In other words, draw $z \sim \unif_k^{\otimes n}$ as follows: first choose a $(1-1/k)$-random subset $J \subseteq [n]$, form the restriction $(J,x_\barJ)$ where $x_\barJ$ is the all-$k$'s substring, and finally draw $y \sim \unif_{k-1}^{\otimes J}$ and take $z = (x_\barJ,y)$.  We have $\unif_k(B) = \Ex_J[\unif_{k-1}(B_{x_\barJ})] \delta$ (where we may think of $B_{x_\barJ} \subseteq [k-1]^J$).  We also have $\Ex[\abs{J}] = (1-1/k)n$, and $\Pr[\abs{J} < n/2] \leq \exp(-n/48)$ by a standard Chernoff bound\noteryan{bother citing?}.  Thus there must exist a particular restriction $(J,x_\barJ)$ where $\abs{J} \geq n/2 \geq \mdhj{k-1}{\delta/2}{d}$ and $\unif_{k-1}^{\otimes J}(B_{x_\barJ}) \geq \delta - \exp(-n/48) \geq \delta/2$.\noteryan{This uses some extremely mild assumption about $\mdhj{k-1}{\delta/2}{d}$.}  By the multidimensional DHJ($k-1$) theorem, $B_{x_\barJ}$ contains a nondegenerate $d$-dimensional subspace of $[k-1]^J$.  Let us write the template for this subspace as $\sigma \in ([k-1] \cup \{k+1, \dots, k+d\})^J$, meaning that $\chg{\sigma}{(k+t)}{\ell} \in B_{x_\barJ}$ for each $t \in [d]$ and $\ell \in [k-1]$.

We can extend $\sigma$ from coordinates $J$ to all of $[n]$ in the natural way, filling in $k$'s, and the resulting template has $\chg{\sigma}{(k+t)}{\ell} \in B$ for all $\ell \in [k-1]$.  But $B$ is $ak$-sensitive by assumption, so each string $\chg{\sigma}{(k+t)}{k}$ is in $B$ because $\chg{\sigma}{(k+t)}{a}$ is.  Thus $\sigma$ is a nondegenerate $d$-dimensional subspace template in the usual sense with all its strings in $B$.\noteryan{not elegantly explained}
\end{proof}