https://michaelnielsen.org/polymath/index.php?action=history&feed=atom&title=Theproof.tex 2026-06-16T02:49:59Z Revision history for this page on the wiki MediaWiki 1.42.3 https://michaelnielsen.org/polymath/index.php?title=Theproof.tex&diff=1896&oldid=prev 2009-07-08T20:27:15Z

<p></p> <a href="https://michaelnielsen.org/polymath/index.php?title=Theproof.tex&amp;diff=1896&amp;oldid=1886">Show changes</a>

Ryanworldwide https://michaelnielsen.org/polymath/index.php?title=Theproof.tex&diff=1886&oldid=prev 2009-07-08T20:20:09Z

<p>Undo revision 1772 by <a href="/polymath/index.php?title=Special:Contributions/67.186.58.92" title="Special:Contributions/67.186.58.92">67.186.58.92</a> (<a href="/polymath/index.php?title=User_talk:67.186.58.92" title="User talk:67.186.58.92">Talk</a>)</p> <a href="https://michaelnielsen.org/polymath/index.php?title=Theproof.tex&amp;diff=1886&amp;oldid=1772">Show changes</a>

Ryanworldwide https://michaelnielsen.org/polymath/index.php?title=Theproof.tex&diff=1772&oldid=prev 2009-06-25T04:23:16Z

<p></p> <a href="https://michaelnielsen.org/polymath/index.php?title=Theproof.tex&amp;diff=1772&amp;oldid=1630">Show changes</a>

67.186.58.92 https://michaelnielsen.org/polymath/index.php?title=Theproof.tex&diff=1630&oldid=prev 2009-06-11T20:07:01Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 13:07, 11 June 2009</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Line 1:</td> <td colspan="2" class="diff-lineno">Line 1:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>\section{Completing the proof}</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>\section{Completing the proof}</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">We now show how to deduce DHJ($k$) from DHJ($k-1$).\noteryan{put proper theorem refs}</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">\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)$.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">\end{theorem}</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">\begin{proof}</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">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.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Along the way, ``$n$'' shrinks.  UNFINISHED</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">\end{proof}</ins></div></td></tr> </table>

Ryanworldwide https://michaelnielsen.org/polymath/index.php?title=Theproof.tex&diff=1619&oldid=prev 2009-06-10T17:26:25Z

<p>New page: \section{Completing the proof}</p> <p><b>New page</b></p><div>\section{Completing the proof}</div>

Ryanworldwide