Outline of first paper

Here is a proposed outline of the first paper, which will focus on the new density increment proof of DHJ(3) and DHJ(k).

Metadata

• Author: D.H.J. Polymath
• Address: http://michaelnielsen.org/polymath1/index.php (Do we need a more stable address?)
• Title: A new proof of the density Hales-Jewett theorem

Abstract

(A draft proposal - please edit)

The density Hales-Jewett theorem of Furstenberg and Katznelson [cite] asserts that if [math]\displaystyle{ k \geq 2 }[/math] and [math]\displaystyle{ 0 \lt \delta \leq 1 }[/math], and n is sufficiently large depending on k and [math]\displaystyle{ \delta }[/math], then any subset A of [math]\displaystyle{ [k]^n := \{1,\ldots,k\}^n }[/math] of density [math]\displaystyle{ |A|/k^n }[/math] at least [math]\displaystyle{ \delta }[/math] contains a combinatorial line (see introduction for a definition of this term). This theorem implies a number of other results in density Ramsey theory, such as Szemeredi's theorem [cite] that any set of integers of positive upper density contains arbitrarily long arithmetic progressions.

The argument of Furstenberg and Katznelson used a correspondence principle that reformulated the density Hales-Jewett theorem as an infinitary statement in ergodic theory. As such, this argument does not obviously provide quantitative bounds on how large n has to be depending on k and [math]\displaystyle{ \delta }[/math]. In this paper we present a new, and purely combinatorial, proof of the density Hales-Jewett theorem, using a "density increment" strategy inspired by an argument of Ajtai and Szemeredi [cite]. In particular, the argument gives yet another proof of Szemeredi's theorem. [Perhaps describe the type of bounds we get with this argument?]

Sections

Introduction

Basic definitions and statement of the theorem. Definitions and notational conventions include

• [k] = {1, 2, ..., k}
• Subsets of [k]^n are called A
• definition of combinatorial line

History of and motivation for the problem.

Discussion of related results, including the corners theorem.

• Do we want to have a subsection here about what Polymath1 is? Do we also want to list contributors?

Notation

(Note: not all of these conventions need necessarily go in the main notation section; for some, it would make more sense to place the notation next to where they are first used.)

• Define combinatorial subspace
• Define equal-slices measure (and note relationship to random ordered k-partitions)

• what “Polya Urn” measure should actually be called? (e.g., do probabilists already call this something else?)
• how to denote drawing a random line or a random subspace from them?
• what letter to use for these measures? what letter to use for the uniform distribution? ([math]\displaystyle{ \mu,\nu,\rho,\pi,\ell,\ldots }[/math])
• unify terminology of ij-set, (special) set of complexity t, ij-insensitive set, etc.
• what short words/phrases can we use to indicate
  • Non-negligible subsets of [k]^n contain a line
  • Non-negligible subsets of [k]^n contain a medium-dimensional subspace
  • Non-negligible subsets of [k]^n contain a non-negligible fraction of lines
  • Non-negligible subsets of [k]^n contain a non-negligible fraction of medium-dimensional subspaces?

A sketch proof of the corners theorem

A fairly detailed sketch of the modified Ajtai-Szemer\’edi argument.

Different measures on [math]\displaystyle{ [k]^n }[/math].

Definition of equal-slices measure and the P\’olya urn measure.

Motivation for considering these other measures.

Proofs that dense sets in any of those two measures or the uniform measure can be restricted to subspaces where they retain their density in any other of the measures.

A proof of the general theorem

Discussion

• Discuss quantitative bounds?
• Discuss other proofs?