A second outline of a density-increment argument

From Polymath1Wiki

Contents 1 Introduction 2 Notation and definitions 3 A very broad outline of the proof 4 Step 1: a dense 1-set contains an abundance of combinatorial subspaces 5 Step 2: a dense 1-set can be almost entirely partitioned into large subspaces 5.1 Substep 2.1 5.2 Substep 2.2 5.3 Substep 2.3 6 Step 3: a dense 12-set can be almost entirely partitioned into large subspaces 7 How the proof works

Introduction

One of the proof strategies we have considered seriously is the density-increment method. The idea here is to prove that if is a subset of [3]ⁿ of density δ with no combinatorial line then there is a combinatorial subspace S of dimension tending to infinity with n such that the density of inside S is larger than δ by an amount that depends on δ 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 [3]ⁿ. Write U(x),V(x) and W(x) for the sets of i such that x_i = 1,2 and 3, respectively. These are called the 1-set, the 2-set and the 3-set of x. The map is a one-to-one correspondence between [3]ⁿ and the set of all triples (U,V,W) of sets that partition [n]. We shall use the notation x and also the notation (U,V,W) and will pass rapidly between them.

Let and be collections of subsets of [n]. We shall write for the collection of all sequences x such that and A set of the form will be called a 12-set. A 1-set is a set of the form and a 2-set is a set of the form The 12-set is the intersection of the 1-set defined by and the 2-set defined by

Let x be a sequence in [3]ⁿ and let be disjoint subsets of [n]. We shall write for the combinatorial subspace of all the 3^m sequences that are constant on each Z_i 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 Z_i.

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

A very broad outline of the proof

The idea is to exploit the fact, proved on a different page, that if is a dense subset of [3]ⁿ that contains no combinatorial lines, then there is a subspace S, and a 12-subset of that subspace, inside which 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 can be almost entirely partitioned into subspaces, we show first that can be almost entirely partitioned into subspaces, and then for each of those subspaces S we apply the same argument to 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 be a dense collection of subsets of [n], meaning that the 1-set has density θ > 0 in [3]ⁿ. 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 θ that A basic fact that we shall need is that if we choose a sequence at random, and then randomly choose disjoint subsets each of size at most r, of the 3-set W(x) of x, then there is a probability c(θ,r,m) > 0 that the combinatorial subspace is a subset of the 1-set

To make this assertion precise, we need to say how the random choice of 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 θ and m only. We need M to be large enough for the multidimensional Sperner theorem to hold with density θ / 3. That is, we need it to be true that every subset of [2]^m of density at least θ / 2 contains a combinatorial subspace of dimension m.

Next, we argue that if we randomly choose a sequence x, randomly choose a subset 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 θ / 3, when we choose our x and Z, the number of these overwritings that are contained in is at least θ2^M / 3. Therefore, by the multidimensional Sperner theorem we can find a combinatorial subspace (in the [2]ⁿ sense) of dimension m contained in the overwritings that give rise to points in

Let x and Z have this property and let be the resulting wildcard sets. Now form the combinatorial subspace (in the [3]^m sense). Then every point in this subspace has a 1-set that belongs to so the entire subspace is a subset of

Now the number of possible choices of m disjoint subsets of Z is at most some constant that depends on M and m (in fact, it is precisely (m + 1)^M), and hence on m and θ. Therefore, if we randomly choose x and Z as above, and then choose disjoint subsets uniformly at random from all possibilities, there is a probability of c(m,θ) > 0 that the combinatorial subspace is a subset of the 1-set

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 be a 1-set of density θ and let η > 0. Then, provided only that n is sufficiently large, we can find combinatorial subspaces all of which have dimension bounded below by some m that tends to infinity with n, that are disjoint and cover a subset of of density at least θ − η.

Substep 2.1

Step 1 says that if we randomly choose a sequence x and disjoint subsets of W(x), then there is a probability at least c = c(m,θ) > 0 that the subspace is a subset of Furthermore, the nature of the distribution on the sequences is such that their union has size at most M = M(m,θ).

It follows immediately that there exists a choice of with union Z, such that the density of such that is at least c.

Substep 2.2

Remove from all the subspaces that are contained in and partition the remainder of into 3^M sets according to the values taken by sequences on Z.

Corrected version: Let us write for the set of all sequences such that If then we have not removed any elements from If on the other hand then we have removed from all elements x such that Now if x' is another sequence in with the same 1-set as x, then the 1-sets of x+z' and x' + z' are the same for any from which it follows that x' has been discarded from 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 δ − c (as a proportion of 3ⁿ).

Old, incorrect version: Each of these sets is either empty or the intersection of 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 δ − c (as a proportion of 3ⁿ).

Substep 2.3

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

At each stage of this process, if the total mass of not yet placed into subspaces is at least γ, then the amount we place into subspaces at the next iteration is at least γc(m,η), since the proportion of subspaces that contain at least one of the points of that we have not yet discarded is at least γ and from each such subspace the proportion that we place into subspaces is at least c(m,η). Therefore, after at most log_{1 + c(m,η)}(2 / η) iterations, the total mass that has not been placed into subspaces is at most η / 2 + η / 2. This completes the proof of Step 2, provided that 4m / ηc(m,η) 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 be a dense 12-set and think of it as Then use Step 2 to partition almost all of into combinatorial subspaces S_i. The intersection of each S_i with is either sparse in S_i, in which case we discard it, or dense in S_i, in which case we use Step 2 (which of course applies just as well to 2-sets as to 1-sets) to partition S_i into subspaces that are contained in

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 such that whether or not y belongs to depends only on V(y). Now suppose we look at a subspace where x is a sequence defined on the complement of the union of the Z_i. Then whether or not belongs to depends only on Since x is fixed, this depends only on those η_i 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 be a line-free subset of [3]ⁿ of density δ.It is enough to prove that there is a large subspace inside which has density at least δ + η, for some positive η that depends on δ 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 inside which has density at least δ + cδ² 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 inside which has density at least δ + cδ². Apply Step 3 to partition all but cδ² / 2 of this set into large combinatorial subspaces. The total density of inside these subspaces is at least δ + cδ² / 2, so by averaging there is a subspace inside which has at least this density, and the proof is finished.