|
|
| Line 1: |
Line 1: |
| \section{Completing the proof} | | \section{Completing the proof} |
|
| |
|
| In this section, we show how to deduce DHJ($k$) from DHJ($k-1$). We will treat $k = 3$ separately, since we have better bounds in this case due to the Gunderson-R\"{o}dl-Sidirenko theorem (and the probabilistic Sperner theorem).
| | We now show how to deduce DHJ($k$) from DHJ($k-1$).\noteryan{put proper theorem refs} |
|
| |
|
| \subsection{The \texorpdfstring{$k = 3$}{k=3} case} | | \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)$. |
| As described in Section~\ref{sec:outline-incr}, to establish DHJ($3$) it suffices to establish the density increment theorem stated therein. (One also needs the rigorous reduction from DHJ($3$) to the equal-slices version, Proposition~\ref{prop:edhj-equiv-dhj}.) For the reader's convenience, we restate the density increment theorem:
| | \end{theorem} |
| \begin{named}{Theorem~\ref{thm:incr3}} Assume $n \geq 2 \uparrow^{(7)} (1/\delta)$. If $\ens{3}^n(A) \geq \delta$, then either $A$ contains a combinatorial line, or we may pass to a subspace of dimension at least $\log^{(7)} n$ on which $\ens{3}(A) \geq \delta + \Omega(\delta^3)$. | |
| \end{named} | |
| \begin{proof} | | \begin{proof} |
| Throughout the proof we may assume $\delta \leq 2/3$, as otherwise DHJ($3$) is easy. By Proposition~\ref{prop:degen}, we have $\eqs{3}^n(A) \geq \delta - 6/n \geq \delta - \delta^{50}$, by our assumption on $n$.
| | 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. |
| | |
| Let $\theta = 2\delta^{50}$. (We will not be especially economical when it comes to parameters which do not matter.) Applying Lemma~\ref{lem:32}\noteryan{not bothering to point out that the hypothesis holds}, we pass to subspace of dimension at least $(\delta^{50}/7.5) \sqrt{n} \geq n^{1/3}$ on which either $\eqs{3}(A) \geq \delta + \delta^{50}$, or both $\eqs{3}(A) \geq \delta - 4\delta^{13}$ and $\eqs{2}(A) \geq \delta - 4\delta^{25}$. We repeat this step until either the second conclusion obtains or until the step has been repeated $\lfloor 1/\delta^{47}\rfloor$ times. In either case, the dimension $n$ becomes no smaller than $n' = n \uparrow 3 \uparrow (-1/\delta^{47})$. Having done this, we either have $\eqs{3}(A) \geq \delta + \Omega(\delta^3)$ and may stop (as $n' \gg \log^{(7)} n$ by the assumption on $n$), or we have $\eqs{3}(A), \eqs{2}(A) \geq \delta - 4.5\delta^{13}$. \noteryan{$4.5$ is weird, I know, I messed up the constants earlier and was too lazy to readjust them} With another application of Proposition~\ref{prop:degen} we may obtain $\ens{3}(A), \ens{2}(A) \geq \delta - 5 \delta^{13}$, reducing $n'$ to at most, say, $n \uparrow 3 \uparrow (-1/\delta^{48})$.
| |
| | |
| Next, we apply Theorem~\ref{thm:correlate}, taking $\delta_k = \delta_{k-1} = \delta - 5\delta^{13}$. Note that we have proved the probabilistic DHJ($2$) theorem in Lemma~\ref{lem:pdhj2}. We certainly have $n' \geq \pdhj{2}{\delta_{k-1}} = \Theta(1/\delta^2)$, and thus we either obtain a combinatorial line in $A$, or a set $B \subseteq [3]^{n'}$ with $\ens{3}(B) \geq \delta - 5 \delta^{13}$ and
| |
| \[
| |
| \frac{\ens{3}(A \cap B)}{\ens{3}(B)} \geq \delta - 5\delta^{13} + (\delta - 5\delta^{13})(\delta - 5\delta^{13})^2/2 \geq \delta + \delta^3/2 - 12.5\delta^{13} \geq \delta + \delta^3/4,
| |
| \]
| |
| where we used $\pdhj{2}{\delta_{k-1}} = \delta_{k-1}^2/2$. \noteryan{check these calculations} Also, $B$ may be written as $B_1 \cup B_2$, where $B_a$ is $a3$-insensitive. We henceforth write $A$ instead of $A \cap B$.
| |
| | |
| We now return to the uniform distribution by applying Lemma~\ref{lem:back-to-uniform}. Its $\beta$ satisfies $\beta \geq \delta - 5\delta^{13}$, and its $\delta$ needs (crucially) to be replaced by $\delta + \delta^3/4$. We choose its $\eta = \delta^3/8$. Note that the resulting $r = (\beta \eta/15k)\sqrt{n'}$ indeed satisfies $r \gg 2 \ln n$, by the initial assumption on $n$.\noteryan{I think I checked.} We now pass to a restriction on some $n' \geq r \geq n \uparrow 3 \uparrow (-1/\delta^{49})$ coordinates on which we have, say,
| |
| \begin{equation} \label{eqn:3inc}
| |
| \unif_3(B) \geq \delta^4/50, \quad \unif_3(A) \geq (\delta + \delta^3/8) \unif_3(B).
| |
| \end{equation}
| |
| Crucially, since $B$ was the union of a $13$-insensitive set and a $23$-insensitive set before, it remains so in the restriction. We also now apply Lemma~\ref{lem:switch} to partition $B$ into sets $C_1$ and $C_2$, where $C_1$ is $13$-insensitive and $C_2$ is an intersection of $13$- and $23$-insensitive sets.
| |
| | |
| Nearing the end, we now apply Corollary~\ref{cor:multi-partition} twice; once with $C = C_1$ and once with $C = C_2$. We choose $\eta = \delta^7/4000$ and for simplicity we take $\ell = 2$ both times. We will select the parameter $d$ and check the hypothesis on $n'$ later. We can therefore partition each of $C_1$, $C_2$ into disjoint $d$-dimensional combinatorial subspaces, along with error sets, $E_1$, $E_2$. Writing $E = E_1 \cup E_2$ we have
| |
| \begin{equation} \label{eqn:3err}
| |
| \unif_3(E) \leq 2\eta + 2\eta \leq \frac{\delta^7}{1000} \leq \frac{\delta^3}{20} \unif_3(B).
| |
| \end{equation}
| |
| We now simply discard the strings in $E$ from $A$ and $B$. Then $B$ is perfectly partitioned into disjoint $d$-dimensional subspaces, and some arithmetic shows that, whereas we had $\unif_3(A)/\unif_3(B) \geq \delta + \delta^3/8$ in~\eqref{eqn:3inc}, we now still have
| |
| \[
| |
| \frac{\unif_3(A)}{\unif_3(B)} \geq \delta + \delta^3/8 - \frac{\unif_3(E)}{\unif_3(B) - \unif_3(E)},
| |
| \]
| |
| and the fraction on the right is easily seen to be at most $\delta^3/19$, using~\eqref{eqn:3err}. Thus we have $\unif_3(A)/\unif_3(B) \geq \delta + \delta^3/20$, with $B$ perfectly partitioned into disjoint $d$-dimensional subspaces. It follows that we can pass to at least one $d$-dimensional subspace on which $\unif_3(A) \geq \delta + \delta^3/20$.
| |
| | |
| We come now to the final setting of parameters. To execute the partitioning argument, we required that | |
| \begin{equation} \label{eqn:crazy3}
| |
| n' \geq \left(d^{3m(d)}\right)^{3m(d^{3m(d)})},
| |
| \end{equation}
| |
| where
| |
| \[
| |
| m(d) = 2\mdhj{2}{\delta^7/16000}{d} = 2(10d)^{d2^d}(16000/\delta^7)^{2^d},
| |
| \]
| |
| using the Gunderson-R\"{o}dl-Sidirenko theorem. We will ensure that
| |
| \begin{equation} \label{eqn:sat-me}
| |
| d \geq 800/\delta^7,
| |
| \end{equation}
| |
| so that we may bound $m(d) \leq (20d)^{2d2^d} \leq 2 \uparrow 4 \uparrow d$. Then the right-hand side of~\eqref{eqn:crazy3} is at most $2 \uparrow^{(6)} (3d)$, and with $n' \geq n \uparrow 3 \uparrow (-1/\delta^{49})$ we get that~\eqref{eqn:crazy3} is satisfied so long as $d \ll \log^{(6)} n$, using also the initial assumption on $n$.\noteryan{Getting pretty out of control at this point.} Thus we set, say,
| |
| \[
| |
| d \approx (\log^{(7)} n)^{100}
| |
| \]
| |
| and we've satisfied~\eqref{eqn:sat-me} using the initial assumption $n \geq 2 \uparrow^{(7)} (1/\delta)$.
| |
| | |
| It remains to note that, having passed to a $(\log^{(7)} n)^{100}$-dimensional subspace on which $\unif_3(A) \geq \delta + \delta^3/20$, we can pass to a further subspace of dimension at least the claimed $\log^{(7)} n$ on which $\unif_3(A) \geq \delta + \delta^3/40$ via the embedding argument sketched in Section~\ref{sec:outline-dist}, justified by Lemma~\ref{lem:distributions}.
| |
| \end{proof}
| |
| | |
| \subsection{The general \texorpdfstring{$k$}{k} case}
| |
| | |
| For general $k \geq 4$ we will need to use the inductive deduction of the multidimensional DHJ($k-1$) theorem from the DHJ($k-1$) theorem, given in Proposition~\ref{prop:mdhj-from-dhj}. Because the overall argument then becomes a double-induction\noteryan{I think}, the resulting bounds for DHJ($k$) are of Ackermann-type \noteryan{I think}, and we do not work them out precisely.\noteryan{cop-out}.
| |
| | |
| \begin{theorem} The general $k$ case of the density Hales--Jewett theorem follows from the $k-1$ case.
| |
| \end{theorem}
| |
| \begin{proof} (Sketch.) Having proved DHJ($k-1$), we deduce the multidimensional version via Proposition~\ref{prop:mdhj-from-dhj}, the equal-slices version via Proposition~\ref{prop:edhj-equiv-dhj}, and the probabilistic version from Proposition~\ref{prop:pdhj-from-edhj} (only the $d = 1$ case is necessary). The overall goal for proving DHJ($k$) is, as in the $k = 3$ case, to show that for $n$ sufficiently large as a function of $\delta$, we can either find a line in $A$ or can obtain a density increment of $\Omega(\eps)$ on a combinatorial subspace of dimension $d'$, where $\eps = \delta \cdot \pdhj{k-1}{\delta/2}$ depends only on $\delta$ and $k$, and where $d' = \omega_1(n)$.
| |
| | |
| Beginning with $\ens{k}(A) \geq \delta$, we choose $\theta = 2\eps^C$ for some large constant $C$; note that $\theta$ only depends on $\delta$ and $k$. We pass from $\ens{k}(A)$ to $\eqs{k}(A)$ via Proposition~\ref{prop:degen}, incurring density loss only $\eps^c$ by assuming $n$ large enough ($n$ becomes slightly smaller here). We next apply Lemma~\ref{lem:32}. This gives us either a density increment of $\eps^c$, or achieves $\eqs{k}(A), \eqs{k-1}(A) \geq \delta - \eps^c$ for some smaller but still large constant $c$. We can repeat this step $1/\eps^c$ times, eventually achieving a density increment of $\Omega(\eps)$ and stopping if the first outcome keeps happening; otherwise achieving $\eqs{k}(A), \eqs{k-1}(A) \geq \delta - O(\eps^c)$. This brings $n$ down to some fractional power $n'$, but the fraction depends only on $\eps^c$ and hence on $\delta$ and $k$; thus we may continue to assume it is ``large enough''. \noteryan{guess I'm getting pretty sketchy here} This lets us ensure that $\ens{k}(A), \ens{k-1}(A) \geq \delta - O(\eps^c) \geq \delta/2$.
| |
| | |
| We now apply Theorem~\ref{thm:correlate} with $\delta_k = \delta_{k-1} = \delta/2$. This requires $n'$ to be larger than $\Pdhj{k-1}{\delta/2}$, which will be a very large but still ``constant'' quantity, depending only on $\delta$ and $k$. Having applied the theorem, we either get a combinatorial line, or a density increment of $\delta_k \cdot \pdhj{k-1}{\delta/2} = \Omega(\eps)$ on some set $B$. Note that $\Omega(\eps) \gg O(\eps^c)$, so are able to obtain the desired relative density increment. The set $B$ has $\ens{k}(B) \geq \delta/2$ and is a union of $ak$-insensitive sets, as in the theorem statement. We can preserve this relative density increment under the uniform distribution by passing to another subspace according to Lemma~\ref{lem:back-to-uniform} with $\eta = \eps^C$. The dimension $n'$ continues to decrease to some $r$, but this is still $\omega_n(1)$ as we have only involved ``constant'' factors depending on $\delta$ and $k$. As in the DHJ($3$) proof, $B$ still has the special structure as a union of $ak$-insensitive sets. We again apply Lemma~\ref{lem:switch} to write it as a disjoint union of $k$ sets, each of which is an intersection of up to $k$ many $ak$-insensitive sets.
| |
|
| |
|
| We now apply Corollary~\ref{cor:multi-partition} to each of these sets, taking $\eta = \eps^C$ again and $\ell = k$ each time for simplicity. It suffice now to analyze what parameter $d$ we may choose; the remainder of the proof is essentially the same as in the DHJ($3$) case. At this point, the original $n$ has shrunk to some $n'$ which is some fractional power of $n$ depending on $\delta$ and $k$ only, and this $n'$ is required to be large enough compared to $\pdhj{k-1}{\delta/2}$, a very large function of $\delta$ and $k$ only. The function $m(d)$ arising in the corollary depends on $\eta$ and hence on $\delta$ and $k$, and also on $d$; the dependence of $f(d) = d^{3m(d)}$ on $d$ will be quite bad due to the inductive argument Proposition~\ref{prop:mdhj-from-dhj}. Still, when we iterate it $\ell = k$ times, the function $f^{(k)}(d)$ is just another (huge) function of $k$, $\delta$, and $d$. We will then have some demand on how large $n'$ needs to be as a function of $d$. Crucially, we may take $d$ to be some function $\omega_n(1)$ which satisfies this demand.
| | Along the way, ``$n$'' shrinks. UNFINISHED |
|
| |
|
| Finally, we need to take our uniform-distribution density increment of $\Omega(\eps)$ on a $d$-dimensional subspace, and produce an equal-slices density increment of $\Omega(\eps)$. This will require reducing $d$ further to some $d'$, a function of $d$ and $\eps$ (hence $\delta$ and $k$), but this $d'$ will still be $\omega_n(1)$. \noteryan{this is all poorly explained and probably wrongly explained in several places :) luckily it's right overall :)}
| |
| \end{proof} | | \end{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}
\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}
