Insensitive.tex

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

\noteryan{Rewrite the below theorem to handle Varnavides-ising the multidim version too. The proof follows almost trivially from Lemma~\ref{lem:ens-compose}.} \begin{theorem} \label{thm:dhj-v} Assume that for all $n \geq n_{\ref{thm:dhj}}(k,\delta)$, every subset of $[k]^n$ of density at least $\delta$ contains a nondegenerate combinatorial line. Then for all $n \geq n_{\ref{thm:dhj-v}}(k,\delta) := XXX$, if $A \subseteq [k]^n$ has density at least $\delta$, then a random equal-slices line is in $A$ with probability at least $\eta_{\ref{thm:dhj-v}}(k,\delta) := XXX$. I.e., if $x \sim \eqs{k+1}^n$, then with probability at least $\eta_{\ref{thm:dhj-v}}$ it holds that $\chg{x}{k+1}{i} \in A$ for all $i \in [k]$. \end{theorem}

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