Insensitive.tex

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

\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{proof} 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 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 $(k+d)^{-2m}$. We conclude that with probability at least $(\delta/2)(k+d)^{-2m}$ over the choice of $x$ and $w$, the nondegenerate $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}

In the particular case of $k = 2$, $d = 1$, this theorem can be proved directly.\noteryan{Something like the following should appear somewhere in Section~\ref{sec:sperner}.} \begin{theorem} \label{thm:sperner-v} For $n \geq 2$, \[ \ens{k}^n(A) \geq \delta \quad\Rightarrow\quad \Pr_{\sigma \sim \ens{3}^n}[\sigma \subseteq A \text{ as a line}] \geq \delta^2 - \frac{10}{n}. \] \noteryan{Not sure the $10$ is exactly what follows from Proposition~\ref{prop:degen}, but whatever.} In particular, we can take $n_{\ref{thm:dhj-dv}}(2,1,\delta) = 20/\delta^2$ and $\eta_{\ref{thm:dhj-dv}}(2,1,\delta) = \delta^2/2$. \end{theorem}

\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 $|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}

In the particular case of $k = 2$ and $\pi$ uniform, we can use a significantly better bound due to Gunderson, R{\"o}dl, and Sidorenko~\cite{GRS99}:\noteryan{And I think it \emph{will} be important to use it to get a good bound for DHJ(k).} \begin{theorem} Let $A \subseteq [2]^n$ have (uniform) density at least $\delta$, and assume $n \geq (10d)^{d2^d} \cdot (1/\delta)^{2^d}$. Then $A$ contains a nondegenerate $d$-dimensional subspace. \end{theorem} \begin{proof} Theorem 4.2 and equation~(8) of~\cite{GRS99} taken together state that the maximum density of a $d$-dimensional subspace-free subset of $[2]^n$ is at most \[ c(d) \cdot n^{-1/2^d}, \quad \text{where } c(d) = 10^d 2^{-1/2^{d-1}}d^{d - 1/2^d}. \] Note that $c(d) < (10d)^d$. Hence it suffices to check that our lower bound on $n$ implies $\delta \geq (10d)^d n^{-1/2^d}$. \end{proof}

\subsection{\texorpdfstring{$ij$}{ij}-insensitive sets}

\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}

\begin{remark} If $A$ and $B$ are $ij$-insensitive on $I$, then so too are $\overline{A}$\noteryan{Okay to use this as $A$-complement?}, $A \cap B$, $A \cup B$.\noteryan{Redundant, I know} \end{remark}

\begin{theorem} \label{thm:dhj-d-prod-insens} Let $k \geq 3$. Suppose $A \subseteq [k]^n$ is $ij$-insensitive and has $\pi_k(A) \geq \delta$, where $\pi_k$ denotes the uniform distribution on $[k]$. If $n \geq 2n_{\ref{thm:dhj-d-prod}}(k-1,d,\delta/2,\pi_{k-1})$, then $A$ contains a nondegenerate $d$-dimensional subspace. \end{theorem} \begin{proof} We may assume without loss of generality that $j = k$. Think of conditioning a draw from $\pi_k^{\otimes n}$ on the location of the symbols $k$. In other words, draw $z \sim \pi_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 \pi^{\otimes J}_{k-1}$ and take $z = (x_\barJ,y)$. We have $\pi_k(A) = \Ex_J[\pi_{k-1}(A_{x_\barJ})] \delta$ (where we may think of $A_{x_\barJ} \subseteq [k-1]^J$). We also have $\Ex[|J|] = (1-1/k)n$, and $\Pr[|J| < n/2] \leq \exp(-n/48)$ by a standard large-deviation bound\noteryan{bother citing?}. Thus there must exist a particular restriction $(J,x_\barJ)$ where $|J| \geq n/2 \geq n_{\ref{thm:dhj-d-prod}}(k-1,d,\delta/2,\pi_{k-1})$ and $\pi^{\otimes J}_{k-1}(A_{x_\barJ}) \geq \delta - \exp(-n/48) \geq \delta/2$.\noteryan{This uses some extremely mild assumption about $n_{\ref{thm:dhj-d-prod}}()$.} By Theorem~\ref{thm:dhj-d-prod}, $A_{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 A_{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 A$ for all $\ell \in [k-1]$. But $A$ is $ik$-sensitive by assumption, so each string $\chg{\sigma}{(k+t)}{k}$ is in $A$ because $\chg{\sigma}{(k+t)}{i}$ is. Thus $\sigma$ is a nondegenerate $d$-dimensional subspace template in the usual sense with all its strings in $A$.\noteryan{not elegantly explained} \end{proof}