Partitioning.tex

\section{Partitioning \texorpdfstring{$ij$}{ij}-insensitive sets}

{\tiny \textbf{[[Ryan: In what follows, I use some notation ``$n_{\ref{thm:dhj-d-prod-insens}}(k,d,\eta/2,\pi)$ to mean a number large enough that, when $n \geq n_{\ref{thm:dhj-d-prod-insens}}()$, every $ij$-insensitive set $B \subseteq [k]^{n}$ with $\pi^{\otimes}(B) \geq \eta/2$ contains a nondegenerate $d$-dimensional subspace.]]}}\\

\begin{theorem} \label{thm:partition} Let $\pi$ be a distribution on $[k]$ and assume $\alpha = \min(\pi) > 0$. Let $B \subseteq [k]^n$ be $ij$-insensitive on $I$, and assume \[ |I| \geq n_{\ref{thm:partition}}(k,d,\eta,\pi) := 2m \left(\frac{k+d}{\alpha}\right)^m \ln(1/\eta), \] where \[ m = n_{\ref{thm:dhj-d-prod-insens}}(k,d,\eta/2,\pi). \] Then $B$ can be partitioned into a collection $\calS$ of disjoint nondegenerate $d$-dimensional subspaces, along with an error set $E$ satisfying $\pi^{\otimes n}(E) \leq \eta$. \end{theorem} \begin{proof} The proof proceeds in ``rounds, $t = 1, 2, 3, \dots$. In each round, we remove some disjoint subspaces from $B$ and put them into $\calS$; and, the set $I$ shrinks by $m$ coordinates. We will show that after the $t$th round, \begin{equation} \label{eqn:B-shrinks} \pi^{\otimes n}(B) \leq \left(1 - \frac{\alpha^m}{2(k+d)^m}\right)^t. \end{equation} We continue the process until $\pi^{\otimes n}(B) \leq \eta$, at which point we may stop and set $E = B$. Because of~\eqref{eqn:B-shrinks}, the process stops after at most $T = 2(\frac{k+d}{\alpha})^m \ln(1/\eta)$ rounds. By our choice of $n_{\ref{thm:partition}}(k,d,\eta,\pi) = mT$, the set $I$ never ``runs out of coordinates.\\

Suppose we are about to begin the $t$th round; hence, writing $\delta = \pi^{\otimes n}(B)$ we have \[ \eta < \delta \leq \left(1 - \frac{\alpha^m}{2(k+d)^m}\right)^{t-1}. \] The round begins by choosing an arbitrary $J \subseteq I$ with $|J| = m$. We have \[ \delta = \Pr_{x \sim \pi^{\otimes n}}[x \in B] = \Ex_{y \sim \pi^{\otimes \barJ}}[\pi^{\otimes J}(B_y)]. \] \ignore{where we have written $\barJ = [n] \setminus J$ and $B_y = \{z \in [k]^J : (y,z) \in B\}$.} Hence $\pi^{\otimes J}(B_y) \geq \delta/2$ for at least a $\delta/2$ probability mass of $y$'s (under $\pi^{\otimes \barJ}$); call these $y$'s ``good. Since $J \subseteq I$ and $B$ is $ij$-insensitive on $I$, it follows that each $B_y$ is $ij$-insensitive on $J$. Since $|J| = m = n_{\ref{thm:dhj-d-prod-insens}}(k,d,\eta/2,\pi) \geq n_{\ref{thm:dhj-d-prod-insens}}(k,d,\delta/2,\pi)$, it follows from Theorem~\ref{thm:dhj-d-prod-insens} that for each good $y$ there must exist a nondegenerate $d$-dimensional subspace $\rho \subseteq B_y$. Since the number of $d$-dimensional subspaces in $[k]^m$ is at most $(k+d)^m$, there must exist a \emph{fixed} nondegenerate $d$-dimensional subspace $\rho_0 \subseteq [k]^J$ such that \begin{equation} \label{eqn:B-mass-decr} \Pr_{y \sim \pi^{\otimes \barJ}}[\rho_0 \subseteq B_y] \geq \frac{\delta}{2(k+d)^m}. \end{equation} Let $R \subseteq [k]^{\barJ}$ be the set of $y$'s with $\rho_0 \subseteq B_y$. Since $B$ is $ij$-insensitive on $I$, it is easy to see\noteryan{Honest.} that $R$ is $ij$-insensitive on $I \setminus J$. Thus $R \times \rho_0$ is $ij$-insensitive on $I \setminus J$; hence so too is $B \setminus (R \times \rho_0)$. We therefore complete the round by setting $I = I \setminus J$ and transferring $R \times \rho_0$ (a disjoint union of subspaces $\{y\} \times \rho_0$) from $B$ into $\calS$. This shrinks the number of coordinates in $I$ by $m$, as promised. And since we can crudely bound $\pi^{\otimes J}(\rho_0) \geq \alpha^m$, we conclude \[ \pi^{\otimes n}(R \times \rho_0) \geq \frac{\delta}{2(k+d)^m} \cdot \alpha^m, \] as required to establish~\eqref{eqn:B-shrinks} inductively. \end{proof}

\begin{corollary} \label{cor:partition} Let $\pi$ be a distribution on $[k]$ and assume $k \leq d$ and $\alpha = \min(\pi) \geq 1/d$. Let $0 < \eta \leq 1/2$ and define $m = n_{\ref{thm:dhj-d-prod-insens}}(k,d,\eta/2,\pi)$. If $B \subseteq [k]^n$ is $ij$-insensitive and $n \geq d^{3m}$, then the conclusion of Theorem~\ref{thm:partition} holds. \end{corollary} \begin{proof} \textbf{Some parameter setting, which I hope is right. Makes some reasonable assumptions about the hugeness of $m$.} \end{proof}

\begin{corollary} \label{cor:multi-partition} Let $\pi$ be a distribution on $[k]$ and assume $k \leq d$ and $\alpha = \min(\pi) \geq 1/d$. Let $B \subseteq [k]^n$ be expressible as $B = B_1 \cap \cdots \cap B_\ell$, where each $B_s$ is $i_sj_s$-insensitive. Let $0 < \eta \leq 1/2$ and write $f(d) = d^{3m(d)}$, where $m(d) = n_{\ref{thm:dhj-d-prod-insens}}(k,d,\eta/2,\pi)$. If $n \geq f^{(\ell)}(d)$\noteryan{that's $f$ iterated $t$ times} then the conclusion of Theorem~\ref{thm:partition} holds with error bound $\ell \eta$. \end{corollary} \begin{proof} The proof is an induction on $\ell$, with Corollary~\ref{cor:partition} serving as the base case. In the general case, since $n \geq f(f^{(\ell-1)}(d))$, by induction we can partition $B' = (B_1 \cap \cdots \cap B_{\ell-1})$ into a collection $\calS'$ of disjoint nondegenerate $f^{(\ell-1)}(d)$-dimensional subspaces, along with an error set $E'$ satisfying $\pi^{\otimes{n}}(E') \leq (\ell-1)\eta$.\noteryan{I think we're using $f^{(\ell-1)}(d) \geq d$ so that the hypotheses of Corollary~\ref{cor:partition} hold} For each $\sigma \in \calS$, define $C_\sigma = B_\ell \cap \sigma$. Note that $C_\sigma$ is a an $i_\ellj_\ell$-insensitive subset of $\sigma$\noteryan{justify?}. UNFINISHED \end{proof}