Insensitive.tex

\section{Easy deductions, and \texorpdfstring{$ij$}{ij}-insensitive sets}

\begin{theorem} \label{thm:dhj-dv} Assume that for all $n \geq n_{\ref{thm:dhj}}(k,d,\delta)$, \[ \ens{k}^n(A) \geq \delta \quad\Rightarrow\quad \text{$A$ contains a nondegenerate $d$-dimensional combinatorial subspace}. \] Then for all $n \geq n_{\ref{thm:dhj-dv}}(k,d,\delta) := XXX$, \[ \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-v}}(k,d,\delta) := XXX. \] \end{theorem} \begin{proof} Let $m = n_{\ref{thm:dhj}}(k,d,\delta/2)$. Let $x \sim \ens{m}^n$ and $y \sim \ens{k}^m$.\noteryan{Surely $k \leq m \leq n$.} 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 \ens{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 nondegenerate $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 BLAH. We conclude that with probability at least $(\delta/2)BLAH$ over the choice of $x$ and $w$, the nondegenerate $d$-dimensional subspace $w \circ x$ is in $A$. This completes the proof, as $w \circ x$ is distributed as $\ens{k+d}^n$ by Lemma~\ref{lem:ens-compose}. \end{proof}

\begin{definition} Let $i, j \in [k]$ be distinct, and $I \subseteq [n]$. We say that $A \subseteq [k]^n$ is \emph{$ij$-insensitive on~$I$} if the following condition holds: $x \in A$ iff $\chg{x}{i}{j} \in A$. \end{definition} \begin{remark} This definition is symmetric in $i$ and $j$. It is perhaps easier to understand the condition as follows: ``altering some $i$'s to $j$'s and some $j$'s to $i$'s does not affect presence/absence in $A$. \end{remark}

\noteryan{Just putting the following statement of subspace-DHJ(k) under product distributions here for the future} \begin{theorem} \label{thm:subsp} Let $d \in \N$, $0 < \eta < 1$, and let $\pi$ be a distribution on $[k]$. Then assuming \[ n \geq n_{\ref{thm:subsp}}(k,d,\eta,\pi) := to be determined, \] every set $A \subseteq [k]^n$ with $\pi^{\otimes n}(A) \geq \eta$ contains a nondegenerate $d$-dimensional subspace. \end{theorem}