Difference between revisions of "Partitioning.tex"

From Polymath1Wiki
Jump to: navigation, search
Line 1: Line 1:
\section{Partitioning \texorpdfstring{$ij$}{ij}-insensitive sets}
+
\section{Partitioning \texorpdfstring{$ab$}{ab}-insensitive sets}
  
\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  
+
The last tool we need is the result described in Section~\ref{sec:outline-partition}; given the multidimensional DHJ($k-1$) theorem, we show that $ab$-insensitive subsets of $[k]^n$ can be almost completely partitioned into disjoint $d$-dimensional subspaces.
 +
 
 +
\begin{theorem}  \label{thm:partition} Let $k \geq 3$, $d \geq 1$, $0 < \eta < 1/2$.  Let $C \subseteq [k]^n$ be $ab$-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),
+
\abs{I} \geq m \bigl(k(k+d)\bigr)^m \ln(1/\eta),
 
\]  
 
\]  
 
where  
 
where  
 
\[
 
\[
m = n_{\ref{thm:dhj-d-prod-insens}}(k,d,\eta/2,\pi).
+
m = 2\mdhj{k-1}{\eta/4}{d}.
 
\]   
 
\]   
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$.
+
Then $C$ can be partitioned into a collection $\calS$ of disjoint $d$-dimensional subspaces, along with an error set $E$ satisfying $\unif_k^{\ot n}(E) \leq \eta$.
 
\end{theorem}
 
\end{theorem}
 
\begin{proof}
 
\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,  
+
\noteryan{Maybe change all the $\unif_k^{\otimes n}$'s just to $\unif$'s, for typographical simplicity.}
\begin{equation} \label{eqn:B-shrinks}
+
The proof proceeds in ``rounds'', $t = 1, 2, 3, \dots$.  In each round, we remove some disjoint subspaces from $C$ and put them into $\calS$; and, the set $I$ shrinks by $m$ coordinates.  We will show that after the $t$th round,  
\pi^{\otimes n}(B) \leq \left(1 - \frac{\alpha^m}{2(k+d)^m}\right)^t.
+
\begin{equation} \label{eqn:C-shrinks}
 +
\unif_k^{\otimes n}(C) \leq \left(1 - \bigl(k(k+d)\bigr)^{-m}\right)^t.
 
\end{equation}
 
\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''.\\
+
We continue the process until $\unif_k^{\otimes n}(C) \leq \eta$, at which point we may stop and set $E = C$.  Because of~\eqref{eqn:C-shrinks}, the process stops after at most $T = \bigl(k(k+d)\bigr)^m \ln(1/\eta)$ rounds.  Since we insisted $\abs{I} \geq mT$ initially, 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
+
Suppose we are about to begin the $t$th round; hence, writing $\alpha = \unif_k^{\otimes n}(C)$ we have
 
\[
 
\[
\eta < \delta \leq \left(1 - \frac{\alpha^m}{2(k+d)^m}\right)^{t-1}.
+
\eta < \alpha \leq \left(1 - \bigl(k(k+d)\bigr)^{-m}\right)^{t-1}.
 
\]
 
\]
The round begins by choosing an arbitrary $J \subseteq I$ with $|J| = m$.  We have  
+
The round begins by choosing an arbitrary $J \subseteq I$ with $\abs{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)].
+
\alpha = \Pr_{x \sim \unif_k^{\otimes n}}[x \in C] = \Ex_{y \sim \unif_k^{\otimes \barJ}}[\unif_k^{\otimes J}(C_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  
+
where we have written $C_y = \{z \in [k]^J : (y,z) \in C\}$. Hence $\unif_k^{\otimes J}(C_y) \geq \alpha/2$ for at least a $\alpha/2$ probability mass of $y$'s (under $\unif_k^{\otimes \barJ}$); call these $y$'s ``good''.  Since $J \subseteq I$ and $C$ is $ab$-insensitive on $I$, it follows that each $C_y$ is $ab$-insensitive on $J$.  Since $\abs{J} = m = 2\mdhj{k-1}{(\eta/2)/2}{d} \geq 2\mdhj{k-1}{(\alpha/2)/2}{d}$, it follows from Proposition~\ref{prop:mdhj-insens} that for each good $y$ there must exist a $d$-dimensional subspace $\rho \subseteq C_y$.  Since the number of $d$-dimensional subspaces in $[k]^m$ is at most $(k+d)^m$, there must exist a \emph{fixed} $d$-dimensional subspace $\rho_0 \subseteq [k]^J$ such that  
\begin{equation} \label{eqn:B-mass-decr}
+
\begin{equation} \label{eqn:C-mass-decr}
\Pr_{y \sim \pi^{\otimes \barJ}}[\rho_0 \subseteq B_y] \geq \frac{\delta}{2(k+d)^m}.
+
\Pr_{y \sim \unif_k^{\otimes \barJ}}[\rho_0 \subseteq C_y] \geq \frac{\alpha}{2(k+d)^m}.
 
\end{equation}
 
\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 \[
+
Let $R \subseteq [k]^{\barJ}$ be the set of $y$'s with $\rho_0 \subseteq C_y$.  Since $C$ is $ab$-insensitive on $I$, it is easy to see\noteryan{Honest.} that $R$ is $ab$-insensitive on $I \setminus J$. Thus $R \times \rho_0$ is $ab$-insensitive on $I \setminus J$; hence so too is $C \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 $C$ into $\calS$.  This shrinks the number of coordinates in $I$ by $m$, as promised.  And since we can crudely bound $\unif_k^{\otimes J}(\rho_0) = k^{d-m} \geq 2k^{-m}$, we conclude \[
\pi^{\otimes n}(R \times \rho_0) \geq \frac{\delta}{2(k+d)^m} \cdot \alpha^m,
+
\unif_k^{\otimes n}(R \times \rho_0) \geq \frac{\alpha}{\bigl(k(k+d)\bigr)^m},
 
\]
 
\]
as required to establish~\eqref{eqn:B-shrinks} inductively.  
+
as required to establish~\eqref{eqn:C-shrinks} inductively.  
 
\end{proof}
 
\end{proof}
  
 +
We conclude this section by simplifying parameters slightly, then deducing Theorem~\ref{thm:partition} for intersections of $ab$-insensitive sets.
  
\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.
+
\begin{corollary}  \label{cor:partition} Let $d \geq k \geq 3$, $0 < \eta < 1/2$, and define $m$ as in Theorem~\ref{thm:partition}.  If $C \subseteq [k]^n$ is $ab$-insensitive and $n \geq d^{3m}$, then the conclusion of Theorem~\ref{thm:partition} holds.
 
\end{corollary}
 
\end{corollary}
 
\begin{proof}
 
\begin{proof}
\textbf{[[Some parameter setting, which I hope is right. Makes some reasonable assumptions about the hugeness of $m$.]]}
+
We only need check that $d^{3m} \geq m \bigl(k(k+d)\bigr)^m \ln(1/\eta)$.  We use the bounds $k \leq d$ and $m \geq 4/\eta$ (which is certainly necessary), and hence must show $d^{3m} \geq m \ln(m/4) (2d^2)^m$. This holds for every $d \geq 3$ and $m > 4$.\noteryan{I checked}
 
\end{proof}
 
\end{proof}
  
\begin{corollary}  \label{cor:multi-partition} Let $\pi$ denote the uniform distribution on $[k]$ and assume $k \leq 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 $\ell$ times} then the conclusion of Theorem~\ref{thm:partition} holds with error bound $\ell \eta$.
+
\begin{corollary}  \label{cor:multi-partition} Let $d, k, \eta, m$ be as in Corollary~\ref{cor:partition}, and write $f(d) = d^{3m(d)}$, treating $m$ as a function of $d$, with $k$ and $\eta$ fixed.  Let $C \subseteq [k]^n$ be expressible as $C = C_1 \cap \cdots \cap C_\ell$, where each $C_s$ is $a_sb_s$-insensitive.  If $n \geq f^{(\ell)}(d)$\noteryan{that's $f$ iterated $\ell$ times} then the conclusion of Theorem~\ref{thm:partition} holds with error bound $\ell \eta$.
 
\end{corollary}
 
\end{corollary}
 
\begin{proof}
 
\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^{(\ell-1)}(f(d))$, by induction we can partition $B' = (B_1 \cap \cdots \cap B_{\ell-1})$ into a collection $\calS'$ of disjoint nondegenerate $f(d)$-dimensional subspaces, along with an error set $E'$ satisfying $\pi^{\otimes{n}}(E') \leq (\ell-1)\eta$. For each $\sigma \in \calS'$, define $C_\sigma = B_\ell \cap \sigma$.  If we identify $\sigma$ with $[k]^{f(d)}$ then we may think of $C_\sigma$ as an $i_\ell j_\ell$-insensitive subset of $[k]^{f(d)}$\noteryan{justify?}.  Thus we may apply Corollary~\ref{cor:partition} and partition $C_\sigma$ into a collection $\calS_\sigma$ of nondegenerate $d$-dimensional subspaces, along with an error set $E_\sigma$ satisfying $\pi^\sigma(E_\sigma) \leq \eta$.\noteryan{bad invented notation}  Note that in the original space $[k]^n$ we have $\pi^{\otimes n}(E_\sigma) \leq \eta \cdot \pi^{\otimes n}(\sigma)$.\noteryan{This is a subtlety.}  Hence we may complete the induction by taking $\calS$ to be $\{C_\sigma : \sigma \in \calS'\}$\noteryan{Point out that a $d$-dim subspace of a subspace is a $d$-dim subspace?} and $E$ to be $E' \cup \bigcup \{E_\sigma : \sigma \in \calS'\}$, observing that $\pi^{\otimes n}(E) \leq (\ell-1)\eta + \eta (\sum_{\sigma \in \calS'} \pi^{\otimes n}(\sigma)) \leq \ell \eta$ as required.
+
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^{(\ell-1)}(f(d))$, by induction we can partition $C' = (C_1 \cap \cdots \cap C_{\ell-1})$ into a collection $\calS'$ of disjoint nondegenerate $f(d)$-dimensional subspaces, along with an error set $E'$ satisfying $\unif_k^{\otimes n}(E') \leq (\ell-1)\eta$. For each $\sigma \in \calS'$, define $D_\sigma = C_\ell \cap \sigma$.  If we identify $\sigma$ with $[k]^{f(d)}$ then we may think of $D_\sigma$ as an $a_\ell b_\ell$-insensitive subset of $[k]^{f(d)}$\noteryan{justify?}.  Thus we may apply Corollary~\ref{cor:partition} and partition $D_\sigma$ into a collection $\calS_\sigma$ of nondegenerate $d$-dimensional subspaces, along with an error set $E_\sigma$ satisfying ``$\unif_k^\sigma(E_\sigma)$'' $\leq \eta$.\noteryan{bad invented notation}  Note that in the original space $[k]^n$ we have $\unif_k^{\otimes n}(E_\sigma) \leq \eta \cdot \unif_k^{\otimes n}(\sigma)$.\noteryan{$ = \eta \cdot k^{f(d)-n}$.  There's a slight subtlety here.}  Hence we may complete the induction by taking $\calS$ to be $\{D_\sigma : \sigma \in \calS'\}$\noteryan{Point out that a $d$-dim subspace of a subspace is a $d$-dim subspace?} and $E$ to be $E' \cup \bigcup \{E_\sigma : \sigma \in \calS'\}$, observing that $\unif_k^{\otimes n}(E) \leq (\ell-1)\eta + \eta (\sum_{\sigma \in \calS'} \unif_k^{\otimes n}(\sigma)) \leq \ell \eta$ as required.
 
\end{proof}
 
\end{proof}

Revision as of 21:22, 24 June 2009

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

The last tool we need is the result described in Section~\ref{sec:outline-partition}; given the multidimensional DHJ($k-1$) theorem, we show that $ab$-insensitive subsets of $[k]^n$ can be almost completely partitioned into disjoint $d$-dimensional subspaces.

\begin{theorem} \label{thm:partition} Let $k \geq 3$, $d \geq 1$, $0 < \eta < 1/2$. Let $C \subseteq [k]^n$ be $ab$-insensitive on $I$, and assume \[ \abs{I} \geq m \bigl(k(k+d)\bigr)^m \ln(1/\eta), \] where \[ m = 2\mdhj{k-1}{\eta/4}{d}. \] Then $C$ can be partitioned into a collection $\calS$ of disjoint $d$-dimensional subspaces, along with an error set $E$ satisfying $\unif_k^{\ot n}(E) \leq \eta$. \end{theorem} \begin{proof} \noteryan{Maybe change all the $\unif_k^{\otimes n}$'s just to $\unif$'s, for typographical simplicity.} The proof proceeds in ``rounds, $t = 1, 2, 3, \dots$. In each round, we remove some disjoint subspaces from $C$ 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:C-shrinks} \unif_k^{\otimes n}(C) \leq \left(1 - \bigl(k(k+d)\bigr)^{-m}\right)^t. \end{equation} We continue the process until $\unif_k^{\otimes n}(C) \leq \eta$, at which point we may stop and set $E = C$. Because of~\eqref{eqn:C-shrinks}, the process stops after at most $T = \bigl(k(k+d)\bigr)^m \ln(1/\eta)$ rounds. Since we insisted $\abs{I} \geq mT$ initially, the set $I$ never ``runs out of coordinates.

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

We conclude this section by simplifying parameters slightly, then deducing Theorem~\ref{thm:partition} for intersections of $ab$-insensitive sets.

\begin{corollary} \label{cor:partition} Let $d \geq k \geq 3$, $0 < \eta < 1/2$, and define $m$ as in Theorem~\ref{thm:partition}. If $C \subseteq [k]^n$ is $ab$-insensitive and $n \geq d^{3m}$, then the conclusion of Theorem~\ref{thm:partition} holds. \end{corollary} \begin{proof} We only need check that $d^{3m} \geq m \bigl(k(k+d)\bigr)^m \ln(1/\eta)$. We use the bounds $k \leq d$ and $m \geq 4/\eta$ (which is certainly necessary), and hence must show $d^{3m} \geq m \ln(m/4) (2d^2)^m$. This holds for every $d \geq 3$ and $m > 4$.\noteryan{I checked} \end{proof}

\begin{corollary} \label{cor:multi-partition} Let $d, k, \eta, m$ be as in Corollary~\ref{cor:partition}, and write $f(d) = d^{3m(d)}$, treating $m$ as a function of $d$, with $k$ and $\eta$ fixed. Let $C \subseteq [k]^n$ be expressible as $C = C_1 \cap \cdots \cap C_\ell$, where each $C_s$ is $a_sb_s$-insensitive. If $n \geq f^{(\ell)}(d)$\noteryan{that's $f$ iterated $\ell$ 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^{(\ell-1)}(f(d))$, by induction we can partition $C' = (C_1 \cap \cdots \cap C_{\ell-1})$ into a collection $\calS'$ of disjoint nondegenerate $f(d)$-dimensional subspaces, along with an error set $E'$ satisfying $\unif_k^{\otimes n}(E') \leq (\ell-1)\eta$. For each $\sigma \in \calS'$, define $D_\sigma = C_\ell \cap \sigma$. If we identify $\sigma$ with $[k]^{f(d)}$ then we may think of $D_\sigma$ as an $a_\ell b_\ell$-insensitive subset of $[k]^{f(d)}$\noteryan{justify?}. Thus we may apply Corollary~\ref{cor:partition} and partition $D_\sigma$ into a collection $\calS_\sigma$ of nondegenerate $d$-dimensional subspaces, along with an error set $E_\sigma$ satisfying ``$\unif_k^\sigma(E_\sigma)$ $\leq \eta$.\noteryan{bad invented notation} Note that in the original space $[k]^n$ we have $\unif_k^{\otimes n}(E_\sigma) \leq \eta \cdot \unif_k^{\otimes n}(\sigma)$.\noteryan{$ = \eta \cdot k^{f(d)-n}$. There's a slight subtlety here.} Hence we may complete the induction by taking $\calS$ to be $\{D_\sigma : \sigma \in \calS'\}$\noteryan{Point out that a $d$-dim subspace of a subspace is a $d$-dim subspace?} and $E$ to be $E' \cup \bigcup \{E_\sigma : \sigma \in \calS'\}$, observing that $\unif_k^{\otimes n}(E) \leq (\ell-1)\eta + \eta (\sum_{\sigma \in \calS'} \unif_k^{\otimes n}(\sigma)) \leq \ell \eta$ as required. \end{proof}