Density increment method

The basic idea of the density increment method is as follows. Suppose that you have some structure [math]\displaystyle{ S }[/math] that has many substructures of a similar general nature to [math]\displaystyle{ S }[/math]. (Examples of such structures are combinatorial subspaces, grids, arithmetic progressions, complete graphs, etc.) Suppose also that you want to prove that every dense subset [math]\displaystyle{ A }[/math] of [math]\displaystyle{ S }[/math] contains a configuration of a certain kind. You try to prove it using a three-stage argument of the following kind.

• If [math]\displaystyle{ A }[/math] is quasirandom (in some sense that you have to devise), then [math]\displaystyle{ A }[/math] contains a configuration of the desired kind. Therefore, if [math]\displaystyle{ A }[/math] does not contain a configuration of the desired kind, then [math]\displaystyle{ A }[/math] is not quasirandom.

• If [math]\displaystyle{ A }[/math] is not quasirandom, then there is a set [math]\displaystyle{ T }[/math] of a kind one can describe such that [math]\displaystyle{ |A\cap T|/|T| }[/math] is significantly larger than the density of [math]\displaystyle{ A }[/math]. (More generally, we can find a function [math]\displaystyle{ f }[/math] of average zero that we can describe such that the average of [math]\displaystyle{ f }[/math] over [math]\displaystyle{ A }[/math] is bounded away from zero.)

• The characteristic function of [math]\displaystyle{ T }[/math] can be approximated by a positive linear combination of characteristic functions of substructures of [math]\displaystyle{ S }[/math]. Therefore, by averaging, there is a substructure [math]\displaystyle{ S' }[/math] of [math]\displaystyle{ S }[/math] such that [math]\displaystyle{ |A\cap S'|/|S'| }[/math] is significantly greater than the density of [math]\displaystyle{ A }[/math].

With these three steps in place, a simple iteration argument completes the proof.

A simple example of the method

A basic example of this method is Roth's original proof of Roth's theorem. Here the structure [math]\displaystyle{ S }[/math] is an arithmetic progression of length [math]\displaystyle{ n }[/math], the similar substructures are subprogressions of length [math]\displaystyle{ m }[/math] (for some [math]\displaystyle{ m }[/math] that tends to infinity with [math]\displaystyle{ n }[/math]), and the desired configuration is an arithmetic progression of length 3. A brief outline of the proof then runs as follows. (For convenience I am expressing it in a slightly different way from the standard one.)

• Let [math]\displaystyle{ A }[/math] be a subset of [math]\displaystyle{ \mathbb{Z}_N }[/math] of density [math]\displaystyle{ \delta }[/math]. Then [math]\displaystyle{ A }[/math] is said to be quasirandom if the number of quadruples [math]\displaystyle{ (x,x+a,x+b,x+a+b) }[/math] such that all four terms lie in [math]\displaystyle{ A }[/math] is significantly larger than [math]\displaystyle{ \delta^4N^3 }[/math] (which can be shown with the help of the Cauchy-Schwarz inequality to be a lower bound -- the lower bound is approximately attained if [math]\displaystyle{ A }[/math] is random).

*If [math]\displaystyle{ A }[/math] is not quasirandom, then there is a trigonometric function [math]\displaystyle{ \tau(x)=\exp(2\pi irx) }[/math] such that [math]\displaystyle{ \mathbb{E}_x1_A(x)\tau(x) }[/math] is not small. From this it is not hard to deduce that there is a linear-sized mod-[math]\displaystyle{ N }[/math] arithmetic progression [math]\displaystyle{ P }[/math] such that [math]\displaystyle{ |A\cap P|/|P| }[/math] is significantly larger than the density of [math]\displaystyle{ A }[/math]. This follows because we can partition [math]\displaystyle{ \mathbb{Z}_N }[/math] into linear-sized mod-[math]\displaystyle{ N }[/math] arithmetic progressions on each of which [math]\displaystyle{ \tau }[/math] is approximately constant, and then an averaging argument does the rest.

• It can be shown that every mod-[math]\displaystyle{ N }[/math] arithmetic progression can be approximately partitioned into genuine arithmetic progressions of length proportional to [math]\displaystyle{ \sqrt{N} }[/math]. So by averaging we can find a genuine arithmetic progression [math]\displaystyle{ Q }[/math] such that [math]\displaystyle{ |A\cap Q|/|Q| }[/math] is significantly larger than the density of [math]\displaystyle{ A }[/math].

• Now a simple iteration argument finishes off the proof.

Difficulties in applying the method to density Hales-Jewett

Summary of Varnavides thread and discussion of localization, alternative measures, etc.

Known obstructions to uniformity for density Hales-Jewett

Summary of obstructions-to-uniformity thread.