A second outline of a density-increment argument

Introduction

One of the proof strategies we have considered seriously is the density-increment method. The idea here is to prove that if [math]\displaystyle{ \mathcal{A} }[/math] is a subset of [math]\displaystyle{ [3]^n }[/math] of density [math]\displaystyle{ \delta }[/math] with no combinatorial line then there is a combinatorial subspace S of dimension tending to infinity with n such that the density of [math]\displaystyle{ \mathcal{A} }[/math] inside S is larger than [math]\displaystyle{ \delta }[/math] by an amount that depends on [math]\displaystyle{ \delta }[/math] only. If we can prove such a result, then we can drop down to S and repeat the argument. If the initial dimension n is large enough, then we push the density up to 1 before we run out of dimensions, and thereby obtain a contradiction.

Notation and definitions

Let x be an element of [math]\displaystyle{ [3]^n. }[/math] Write [math]\displaystyle{ U(x),V(x) }[/math] and [math]\displaystyle{ W(x) }[/math] for the sets of i such that [math]\displaystyle{ x_i=1,2 }[/math] and 3, respectively. These are called the 1-set, the 2-set and the 3-set of x. The map [math]\displaystyle{ x\mapsto(U(x),V(x),W(x)) }[/math] is a one-to-one correspondence between [math]\displaystyle{ [3]^n }[/math] and the set of all triples [math]\displaystyle{ (U,V,W) }[/math] of sets that partition [math]\displaystyle{ [n]. }[/math] We shall use the notation x and also the notation [math]\displaystyle{ (U,V,W) }[/math] and will pass rapidly between them.

Let [math]\displaystyle{ \mathcal{U} }[/math] and [math]\displaystyle{ \mathcal{V} }[/math] be collections of subsets of [math]\displaystyle{ [n]. }[/math] We shall write [math]\displaystyle{ \mathcal{U}\otimes\mathcal{V} }[/math] for the collection of all sequences [math]\displaystyle{ x }[/math] such that [math]\displaystyle{ U(x)\in\mathcal{U} }[/math] and [math]\displaystyle{ V(x)\in\mathcal{V}. }[/math] A set of the form [math]\displaystyle{ \mathcal{U}\otimes\mathcal{V} }[/math] will be called a 12-set. A 1-set is a set of the form [math]\displaystyle{ \mathcal{U}\otimes[2]^n=\{x:U(x)\in\mathcal{U}\}, }[/math] and a 2-set is a set of the form [math]\displaystyle{ [2]^n\otimes\mathcal{V}=\{x:V(x)\in\mathcal{V}\}. }[/math] The 12-set [math]\displaystyle{ \mathcal{U}\otimes\mathcal{V} }[/math] is the intersection of the 1-set defined by [math]\displaystyle{ \mathcal{U} }[/math] and the 2-set defined by [math]\displaystyle{ \mathcal{V}. }[/math]

Let x be a sequence in [math]\displaystyle{ [3]^n }[/math] and let [math]\displaystyle{ Z_1,\dots,Z_m }[/math] be disjoint subsets of [n]. We shall write [math]\displaystyle{ x+\langle Z_1,\dots,Z_m\rangle }[/math] for the combinatorial subspace of all the [math]\displaystyle{ 3^m }[/math] sequences that are constant on each [math]\displaystyle{ Z_i }[/math] and agree with x everywhere else.

In general, if X is a finite set and A and B are subsets of X, we define the density of A in B to be [math]\displaystyle{ |A\cap B|/|B|. }[/math]

A very broad outline of the proof

The idea is to exploit the fact, proved on a different page, that if [math]\displaystyle{ \mathcal{A} }[/math] is a dense subset of [math]\displaystyle{ [3]^n }[/math] that contains no combinatorial lines, then there is a subspace S, and a 12-subset of that subspace, inside which [math]\displaystyle{ \mathcal{A} }[/math] has an increased density. We show also that any 12-set can be almost entirely partitioned into subspaces, so by averaging this density increase is passed down to one of those subspaces, and the proof is complete. In order to prove that [math]\displaystyle{ \mathcal{U}\otimes\mathcal{V} }[/math] can be almost entirely partitioned into subspaces, we show first that [math]\displaystyle{ \mathcal{U}\otimes[2]^n }[/math] can be almost entirely partitioned into subspaces, and then for each of those subspaces S we apply the same argument to [math]\displaystyle{ S\cap([2]^n\otimes\mathcal{V}), }[/math] which is a 2-subset of S.

This proof is modelled on a modification of the Ajtai-Szemerédi argument. It may be helpful to read that argument first.

Step 1: a dense 1-set contains an abundance of combinatorial subspaces

Let [math]\displaystyle{ \mathcal{U} }[/math] be a dense collection of subsets of [math]\displaystyle{ [n], }[/math] meaning that the 1-set [math]\displaystyle{ \mathcal{U}\otimes[2]^n }[/math] has density [math]\displaystyle{ \theta\gt 0 }[/math] in [math]\displaystyle{ [3]^n. }[/math] This is equivalent to saying that if you choose a set U by taking each element independently with probability 1/3, then there is a probability [math]\displaystyle{ \theta }[/math] that [math]\displaystyle{ U\in\mathcal{U}. }[/math] A basic fact that we shall need is that if we choose a sequence [math]\displaystyle{ x\in[3]^n }[/math] at random, and then randomly choose disjoint subsets [math]\displaystyle{ Z_1,\dots,Z_m, }[/math] each of size at most r, of the 3-set [math]\displaystyle{ W(x) }[/math] of x, then there is a probability [math]\displaystyle{ c(\theta,r,m)\gt 0 }[/math] that the combinatorial subspace [math]\displaystyle{ x+\langle Z_1,\dots,Z_m\rangle }[/math] is a subset of the 1-set [math]\displaystyle{ \mathcal{U}\otimes[2]^n. }[/math]

To make this assertion precise, we need to say how the random choice of [math]\displaystyle{ Z_1,\dots,Z_m }[/math] is made. That will become clear from the proof.

To prove the assertion, we begin by choosing a large integer M, depending on [math]\displaystyle{ \theta }[/math] and m only. We need M to be large enough for the multidimensional Sperner theorem to hold with density [math]\displaystyle{ \theta/3. }[/math] That is, we need it to be true that every subset of [math]\displaystyle{ [2]^m }[/math] of density at least [math]\displaystyle{ \theta/2 }[/math] contains a combinatorial subspace of dimension m.

Next, we argue that if we randomly choose a sequence x, randomly choose a subset [math]\displaystyle{ Z\subset[n] }[/math] of size M, and randomly overwrite the coordinates in Z with 1s or 2s, then the resulting point is approximately uniformly distributed.

It follows that with probability at least [math]\displaystyle{ \theta/3, }[/math] when we choose our x and Z, the number of these overwritings that are contained in [math]\displaystyle{ \mathcal{U}\otimes[2]^n }[/math] is at least [math]\displaystyle{ \theta 2^M/3. }[/math] Therefore, by the multidimensional Sperner theorem we can find a combinatorial subspace (in the [math]\displaystyle{ [2]^n }[/math] sense) of dimension m contained in the overwritings that give rise to points in [math]\displaystyle{ \mathcal{U}\otimes[2]^n. }[/math]

Let x and Z have this property and let [math]\displaystyle{ Z_1,\dots,Z_m }[/math] be the resulting wildcard sets. Now form the combinatorial subspace [math]\displaystyle{ x+\langle Z_1,\dots,Z_m\rangle }[/math] (in the [math]\displaystyle{ [3]^m }[/math] sense). Then every point in this subspace has a 1-set that belongs to [math]\displaystyle{ \mathcal{U}, }[/math] so the entire subspace is a subset of [math]\displaystyle{ \mathcal{U}\otimes[2]^n. }[/math]

Now the number of possible choices of m disjoint subsets [math]\displaystyle{ Z_1,\dots,Z_m }[/math] of Z is at most some constant that depends on M and m (in fact, it is precisely [math]\displaystyle{ (m+1)^M }[/math]), and hence on m and [math]\displaystyle{ \theta. }[/math] Therefore, if we randomly choose x and Z as above, and then choose disjoint subsets [math]\displaystyle{ Z_1,\dots,Z_m }[/math] uniformly at random from all possibilities, there is a probability of [math]\displaystyle{ c(m,\theta)\gt 0 }[/math] that the combinatorial subspace [math]\displaystyle{ x+\langle Z_1,\dots,Z_m\rangle }[/math] is a subset of the 1-set [math]\displaystyle{ \mathcal{U}\otimes[2]^n. }[/math]

Step 2: a dense 1-set can be almost entirely partitioned into large subspaces

This is the analogue of Step 4 of the modified Ajtai-Szemerédi argument. However, it is noticeably more complicated: this is the one point where we really feel that we are working in a more hostile environment where sets have to be disjoint and so on. The argument is an elaboration of comment 879, which arose from trying to work out what was really going on in comment 861, which came from an attempt to understand the argument in comment 837.2, which was itself inspired by comment 832 and the responses to it.

Here is a slightly more precise statement of what we are aiming to show. Let [math]\displaystyle{ \mathcal{U}\otimes[2]^n }[/math] be a 1-set of density [math]\displaystyle{ \theta }[/math] and let [math]\displaystyle{ \eta\gt 0. }[/math] Then, provided only that n is sufficiently large, we can find combinatorial subspaces [math]\displaystyle{ S_1,\dots,S_N, }[/math] all of which have dimension bounded below by some m that tends to infinity with n, that are disjoint and cover a subset of [math]\displaystyle{ \mathcal{U}\otimes[2]^n }[/math] of density at least [math]\displaystyle{ \theta-\eta. }[/math]

Substep 2.1

Step 1 says that if we randomly choose a sequence x and disjoint subsets [math]\displaystyle{ Z_1,\dots,Z_m }[/math] of [math]\displaystyle{ W(x), }[/math] then there is a probability at least [math]\displaystyle{ c=c(m,\theta)\gt 0 }[/math] that the subspace [math]\displaystyle{ x+\langle Z_1,\dots,Z_m\rangle }[/math] is a subset of [math]\displaystyle{ \mathcal{U}\otimes[2]^n. }[/math] Furthermore, the nature of the distribution on the sequences [math]\displaystyle{ Z_1,\dots,Z_m }[/math] is such that their union has size at most [math]\displaystyle{ M=M(m,\theta). }[/math]

It follows immediately that there exists a choice of [math]\displaystyle{ Z_1,\dots,Z_m }[/math] with union Z, such that the density of [math]\displaystyle{ x\in[3]^{[n]\setminus Z} }[/math] such that [math]\displaystyle{ x+\langle Z_1,\dots,Z_m\rangle\subset\mathcal{U}\otimes[2]^n }[/math] is at least [math]\displaystyle{ c. }[/math] [math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math]