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. We shall use the same notation if x is defined not on all of [n] but just on points outside the [math]\displaystyle{ Z_i. }[/math]

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. A different argument, with explicit bounds, is given in the page on Sperner's theorem.

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{B}=\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{B} }[/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{B}. }[/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{B} }[/math] is at least [math]\displaystyle{ c. }[/math]

Substep 2.2

Remove from [math]\displaystyle{ \mathcal{B} }[/math] all the subspaces [math]\displaystyle{ x+\langle Z_1,\dots,Z_m\rangle }[/math] that are contained in [math]\displaystyle{ \mathcal{B} }[/math] and partition the remainder of [math]\displaystyle{ \mathcal{B} }[/math] into [math]\displaystyle{ 3^M }[/math] sets according to the values taken by sequences on Z.

Corrected version: Let us write [math]\displaystyle{ \mathcal{B}_z }[/math] for the set of all sequences [math]\displaystyle{ x\in[3]^{[n]\setminus Z} }[/math] such that [math]\displaystyle{ (x,z)\in\mathcal{B}. }[/math] If [math]\displaystyle{ z\notin\langle Z_1,\dots,Z_m\rangle }[/math] then we have not removed any elements from [math]\displaystyle{ \mathcal{B}_z. }[/math] If on the other hand [math]\displaystyle{ z\in\langle Z_1,\dots,Z_m\rangle, }[/math] then we have removed from [math]\displaystyle{ \mathcal{B}_z }[/math] all elements x such that [math]\displaystyle{ x+\langle Z_1,\dots,Z_m\rangle\subset\mathcal{B}. }[/math] Now if [math]\displaystyle{ x' }[/math] is another sequence in [math]\displaystyle{ [3]^{[n]\setminus Z} }[/math] with the same 1-set as x, then the 1-sets of x+z' and [math]\displaystyle{ x'+z' }[/math] are the same for any [math]\displaystyle{ z'\in\langle Z_1,\dots,Z_m\rangle, }[/math] from which it follows that [math]\displaystyle{ x' }[/math] has been discarded from [math]\displaystyle{ \mathcal{B}_z }[/math] if and only if x has. Therefore, after we remove the subspaces, the restriction to any subspace that consists of all vectors with some fixed restriction to Z is still a 1-subset of that subspace. Therefore, we have a union of 1-subsets of subspaces, of total mass at most [math]\displaystyle{ \delta-c }[/math] (as a proportion of [math]\displaystyle{ 3^n). }[/math]

Old, incorrect version: Each of these sets is either empty or the intersection of [math]\displaystyle{ \mathcal{B} }[/math] with a combinatorial subspace. In the latter case, it is a 1-subset of that subspace. Therefore, we have a union of 1-subsets of subspaces, of total mass at most [math]\displaystyle{ \delta-c }[/math] (as a proportion of [math]\displaystyle{ 3^n). }[/math]

Substep 2.3

This allows us to run an iterative procedure as follows. At the kth stage we have a union of 1-subsets [math]\displaystyle{ \mathcal{B}_i }[/math] of subspaces [math]\displaystyle{ S_i. }[/math] For each i such that [math]\displaystyle{ \mathcal{B}_i }[/math] has density at most [math]\displaystyle{ \eta/2 }[/math] in [math]\displaystyle{ S_i }[/math] do nothing. For all other i, apply substeps 2.1 and 2.2 to partition [math]\displaystyle{ S_i }[/math] into further subspaces, in such a way that a subset of [math]\displaystyle{ S_i }[/math] of density at least [math]\displaystyle{ c(m,\eta)\gt 0 }[/math] is contained in subspaces that are subsets of [math]\displaystyle{ \mathcal{B}_i }[/math] and hence of [math]\displaystyle{ \mathcal{B}. }[/math]

At each stage of this process, if the total mass of [math]\displaystyle{ \mathcal{B} }[/math] not yet placed into subspaces is at least [math]\displaystyle{ \gamma, }[/math] then the amount we place into subspaces at the next iteration is at least [math]\displaystyle{ \gamma c(m,\eta), }[/math] since the proportion of subspaces that contain at least one of the points of [math]\displaystyle{ \mathcal{B} }[/math] that we have not yet discarded is at least [math]\displaystyle{ \gamma }[/math] and from each such subspace the proportion that we place into subspaces is at least [math]\displaystyle{ c(m,\eta). }[/math] Therefore, after at most [math]\displaystyle{ \log_{1+c(m,\eta)}(2/\eta) }[/math] iterations, the total mass that has not been placed into subspaces is at most [math]\displaystyle{ \eta/2+\eta/2. }[/math] This completes the proof of Step 2, provided that [math]\displaystyle{ 4m/\eta c(m,\eta) }[/math] is less than n.

Step 3: a dense 12-set can be almost entirely partitioned into large subspaces

This is an easy deduction from Step 2. Let [math]\displaystyle{ \mathcal{U}\otimes\mathcal{V} }[/math] be a dense 12-set and think of it as [math]\displaystyle{ (\mathcal{U}\otimes[2]^n)\cap([2]^n\otimes\mathcal{V}). }[/math] Then use Step 2 to partition almost all of [math]\displaystyle{ \mathcal{U}\otimes[2]^n }[/math] into combinatorial subspaces [math]\displaystyle{ S_i. }[/math] The intersection of each [math]\displaystyle{ S_i }[/math] with [math]\displaystyle{ [2]^n\otimes\mathcal{V} }[/math] is either sparse in [math]\displaystyle{ S_i, }[/math] in which case we discard it, or dense in [math]\displaystyle{ S_i, }[/math] in which case we use Step 2 (which of course applies just as well to 2-sets as to 1-sets) to partition [math]\displaystyle{ S_i }[/math] into subspaces that are contained in [math]\displaystyle{ [2]^n\otimes\mathcal{V}. }[/math]

It is crucial to this argument that the intersection of a subspace with a 2-set is a 2-set in the subspace, so let me quickly prove that (just to reassure myself, even though I know it's true). A 2-set is a set [math]\displaystyle{ \mathcal{C} }[/math] such that whether or not y belongs to [math]\displaystyle{ \mathcal{C} }[/math] depends only on [math]\displaystyle{ V(y). }[/math] Now suppose we look at a subspace [math]\displaystyle{ S=x+\langle Z_1,\dots,Z_m\rangle, }[/math] where x is a sequence defined on the complement of the union of the [math]\displaystyle{ Z_i. }[/math] Then whether or not [math]\displaystyle{ x+\sum_{i=1}^m\eta_iZ_i }[/math] belongs to [math]\displaystyle{ \mathcal{C} }[/math] depends only on [math]\displaystyle{ V(x+\sum_{i=1}^m\eta_iZ_i). }[/math] Since x is fixed, this depends only on those [math]\displaystyle{ \eta_i }[/math] that equal 2, and this agrees with the definition of a 2-set inside the subspace S.

How the proof works

We now have all the ingredients we need to translate the modification of the Ajtai-Szemerédi argument into an argument for DHJ(3). Let [math]\displaystyle{ \mathcal{A} }[/math] be a line-free subset of [math]\displaystyle{ [3]^n }[/math] of density [math]\displaystyle{ \delta. }[/math]It is enough to prove that there is a large subspace inside which [math]\displaystyle{ \mathcal{A} }[/math] has density at least [math]\displaystyle{ \delta+\eta, }[/math] for some positive [math]\displaystyle{ \eta }[/math] that depends on [math]\displaystyle{ \delta }[/math] only.

As a first step, we use the main result of this page to drop to a subspace S inside which we can find a dense 12-set [math]\displaystyle{ \mathcal{U}\otimes\mathcal{V} }[/math] inside which [math]\displaystyle{ \mathcal{A} }[/math] has density at least [math]\displaystyle{ \delta+c\delta^2 }[/math] for an absolute constant c.

There is a technicality to deal with, because the densities here are with respect to equal-slices measure. However, by passing to a further subspace we can get the same conclusion for uniform measure. The details of this step are to be found in Section 5.3 of this page. (At some stage this part of the argument needs tidying up. For instance, I now think we can avoid equal-slices measure and do things with a localization instead, which would be nice as it's more consistent with the rest of the proof.)

So now, after having passed to a subspace, we have a 12-set [math]\displaystyle{ \mathcal{U}\otimes\mathcal{V} }[/math] inside which [math]\displaystyle{ \mathcal{A} }[/math] has density at least [math]\displaystyle{ \delta+c\delta^2. }[/math] Apply Step 3 to partition all but [math]\displaystyle{ c\delta^2/2 }[/math] of this set into large combinatorial subspaces. The total density of [math]\displaystyle{ \mathcal{A} }[/math] inside these subspaces is at least [math]\displaystyle{ \delta+c\delta^2/2, }[/math] so by averaging there is a subspace inside which [math]\displaystyle{ \mathcal{A} }[/math] has at least this density, and the proof is finished.

[math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math]