# Difference between revisions of "Theproof.tex"

(Undo revision 1772 by 67.186.58.92 (Talk)) |
|||

Line 1: | Line 1: | ||

\section{Completing the proof} | \section{Completing the proof} | ||

− | + | We now show how to deduce DHJ($k$) from DHJ($k-1$).\noteryan{put proper theorem refs} | |

− | \ | + | \begin{theorem} \label{thm:dens-incr} Suppose $A \subseteq [k]^n$ has $\pi(A) \geq \delta$, where $\pi$ denotes the uniform distribution on $[k]$, and $k \geq 3$. Assume $n \geq n_{\ref{thm:dens-incr}}(XXX) := XXX$. Then either $A$ contains a nondegenerate combinatorial line, or there is a combinatorial subspace $\sigma$ of dimension $d$ with $\pi(A_\sigma) \geq \delta + \delta \eta/10$, where $\eta = \eta_{\ref{thm:dhj-dv}}(k-1,1,\delta/10)$. |

− | + | \end{theorem} | |

− | \ | + | |

− | \end{ | + | |

\begin{proof} | \begin{proof} | ||

− | + | Let us first informally sketch the argument. Using Lemma~\ref{lem:distributions}, we can pass to a subspace on which $\eqs{k}(A) \gtrapprox \delta$. Using Lemma~\ref{lem:32} (and Proposition~\ref{prop:degen}), we can either get a density increment much bigger than needed, or pass to a further subspace on which both $\ens{k}(A) \gtrapprox \delta$ and $\ens{k-1}(A) \gtrapprox \delta$. Using Theorem~\ref{thm:correlate}, we can either find a line in $A$, or find a simple set $B$ with $\ens{k}(B) \gtrapprox \delta$ \emph{within} which $\ens{k}(A) \gtrapprox \delta + \delta \cdot \eta_{\ref{thm:dhj-dv}}(k-1,1,\delta) \approx \delta + \delta \eta$. By Lemma~\ref{lem:back-to-uniform}, we can obtain essentially the same relative density increment under the uniform distribution. We now use Theorem~\ref{thm:partition} --- more precisely, Corollary~\ref{cor:multi-partition} --- to obtain this density increment on a $d$-dimensional subspace, as desired. | |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | We | + | |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | Along the way, ``$n$'' shrinks. UNFINISHED | |

− | |||

\end{proof} | \end{proof} |

## Revision as of 20:20, 8 July 2009

\section{Completing the proof}

We now show how to deduce DHJ($k$) from DHJ($k-1$).\noteryan{put proper theorem refs}

\begin{theorem} \label{thm:dens-incr} Suppose $A \subseteq [k]^n$ has $\pi(A) \geq \delta$, where $\pi$ denotes the uniform distribution on $[k]$, and $k \geq 3$. Assume $n \geq n_{\ref{thm:dens-incr}}(XXX) := XXX$. Then either $A$ contains a nondegenerate combinatorial line, or there is a combinatorial subspace $\sigma$ of dimension $d$ with $\pi(A_\sigma) \geq \delta + \delta \eta/10$, where $\eta = \eta_{\ref{thm:dhj-dv}}(k-1,1,\delta/10)$. \end{theorem} \begin{proof} Let us first informally sketch the argument. Using Lemma~\ref{lem:distributions}, we can pass to a subspace on which $\eqs{k}(A) \gtrapprox \delta$. Using Lemma~\ref{lem:32} (and Proposition~\ref{prop:degen}), we can either get a density increment much bigger than needed, or pass to a further subspace on which both $\ens{k}(A) \gtrapprox \delta$ and $\ens{k-1}(A) \gtrapprox \delta$. Using Theorem~\ref{thm:correlate}, we can either find a line in $A$, or find a simple set $B$ with $\ens{k}(B) \gtrapprox \delta$ \emph{within} which $\ens{k}(A) \gtrapprox \delta + \delta \cdot \eta_{\ref{thm:dhj-dv}}(k-1,1,\delta) \approx \delta + \delta \eta$. By Lemma~\ref{lem:back-to-uniform}, we can obtain essentially the same relative density increment under the uniform distribution. We now use Theorem~\ref{thm:partition} --- more precisely, Corollary~\ref{cor:multi-partition} --- to obtain this density increment on a $d$-dimensional subspace, as desired.

Along the way, ``$n$* shrinks. UNFINISHED*

\end{proof}