Theproof.tex

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