A general partitioning principle

Introduction

In the proof of DHJ(3), a key step was to show that a dense set of complexity 1 could be almost entirely partitioned into subspaces of dimension m, for some m that tends to infinity with n. The argument turned out not to depend too heavily on the precise definition of "set of complexity 1," which makes it easy to generalize. In this article we present a generalization that can be used in the proof of DHJ(k).

Definitions and statement of result

Hales-Jewett properties. Let [math]\displaystyle{ \mathbf{K} }[/math] be a collection of subsets of combinatorial subspaces of [math]\displaystyle{ [k]^n. }[/math] We shall say that [math]\displaystyle{ \mathbf{K} }[/math] is a Hales-Jewett property if it is invariant under isomorphisms between subspaces: that is, if [math]\displaystyle{ \phi }[/math] is an isomorphism from [math]\displaystyle{ S_1 }[/math] to [math]\displaystyle{ S_2 }[/math] and [math]\displaystyle{ \mathcal{A}\subset S_1 }[/math] is a set in [math]\displaystyle{ \mathbf{K}, }[/math] then [math]\displaystyle{ \phi(\mathcal{A})\in\mathbf{K} }[/math] as well.

Hereditary properties. We say that a Hales-Jewett property [math]\displaystyle{ \mathbf{K} }[/math] is hereditary if [math]\displaystyle{ \mathcal{A}\cap S\in\mathbf{K} }[/math] whenever [math]\displaystyle{ \mathcal{A} }[/math] is a subset of a combinatorial subspace T, [math]\displaystyle{ \mathcal{A}\in\mathbf{K} }[/math] and S is a combinatorial subspace of T.

Richness hypothesis. We shall call the property [math]\displaystyle{ \mathbf{K} }[/math] subspace rich if for every m and every [math]\displaystyle{ \delta }[/math] there are constants [math]\displaystyle{ M=M(m,\delta) }[/math] and [math]\displaystyle{ c=c(m,\delta)\gt 0 }[/math] such that the following statement holds for all sufficiently large n.

• Let [math]\displaystyle{ \mathcal{A}\in\mathbf{K} }[/math] have density [math]\displaystyle{ \delta }[/math] in [math]\displaystyle{ [k]^n. }[/math] Choose a random M-dimensional subspace [math]\displaystyle{ S_0 }[/math] of [math]\displaystyle{ [k]^n }[/math] by randomly fixing all coordinates outside a randomly chosen set Z of size M. Next, choose a subspace [math]\displaystyle{ S_1\subset S_0 }[/math] of dimension m, uniformly at random from all such subspaces. Then [math]\displaystyle{ S_1\subset\mathcal{A} }[/math] with probability at least [math]\displaystyle{ c. }[/math]

Note that since [math]\displaystyle{ \mathbf{K} }[/math] is a Hales-Jewett property we have a similar hypothesis (that is slightly less convenient to state) for subsets of arbitrary finite-dimensional combinatorial subspaces.

Sigma-algebra properties. We shall say that [math]\displaystyle{ \mathbf{K} }[/math] is a sigma-algebra property if whenever [math]\displaystyle{ \mathcal{A} }[/math] and [math]\displaystyle{ \mathcal{A}' }[/math] are subsets of a subspace S that belong to [math]\displaystyle{ \mathbf{K}, }[/math] then [math]\displaystyle{ \mathcal{A}\cap\mathcal{A'} }[/math] and [math]\displaystyle{ \mathcal{A}\setminus\mathcal{A'} }[/math] belong to [math]\displaystyle{ \mathbf{K}. }[/math]

The main result to be proved on this page is the following.

Lemma. Let [math]\displaystyle{ \mathbf{K} }[/math] be a Hales-Jewett property and suppose that [math]\displaystyle{ \mathbf{K} }[/math] is hereditary, subspace rich and a sigma-algebra property. Then for every [math]\displaystyle{ \delta\gt 0 }[/math] and every positive integer m there exists n such that for every set [math]\displaystyle{ \mathcal{A}\subset[k]^n }[/math] that belongs to [math]\displaystyle{ \mathbf{K} }[/math] there is a decomposition of [math]\displaystyle{ \mathcal{A} }[/math] into subsets [math]\displaystyle{ \mathcal{A}'\cup\mathcal{A}'' }[/math] such that [math]\displaystyle{ \mathcal{A}' }[/math] is a disjoint union of m-dimensional subspaces and [math]\displaystyle{ \mathcal{A}'' }[/math] has density at most [math]\displaystyle{ \delta. }[/math]

To put this more loosely: every set that belongs to [math]\displaystyle{ \mathbf{K} }[/math] can be almost entirely partitioned into m-dimensional subspaces.

Proof of the lemma

Let [math]\displaystyle{ M=M(m,\delta/2) }[/math] and let [math]\displaystyle{ c=c(m,\delta/2). }[/math] We shall iteratively remove subspaces from [math]\displaystyle{ \mathcal{A} }[/math] until the density of what remains is at most [math]\displaystyle{ \delta/2. }[/math]

First step of the iteration

If [math]\displaystyle{ \mathcal{A} }[/math] has density less than [math]\displaystyle{ \delta }[/math] then we are done. Otherwise, by the richness hypothesis and averaging, there is a set Z of size M and a subspace [math]\displaystyle{ S_1\subset[k]^Z }[/math] such that the density of [math]\displaystyle{ x\in[k]^{[n]\setminus Z} }[/math] for which [math]\displaystyle{ \{x\}\times S_1\subset\mathcal{A} }[/math] is at least c.

Put all these subspaces [math]\displaystyle{ \{x\}\times S_1 }[/math] (which are disjoint) into [math]\displaystyle{ \mathcal{A}' }[/math] and partition [math]\displaystyle{ [k]^n }[/math] into the [math]\displaystyle{ k^M }[/math] subspaces of the form [math]\displaystyle{ S_y=\{y\}\times[k]^{[n]\setminus Z} }[/math] with [math]\displaystyle{ y\in[k]^Z. }[/math] Let [math]\displaystyle{ \mathcal{A}_1 }[/math] be the set [math]\displaystyle{ \mathcal{A} }[/math] with the subspaces removed, and for each [math]\displaystyle{ y\in[k]^Z }[/math] let [math]\displaystyle{ \mathcal{A}_{1,y} }[/math] be the set of all [math]\displaystyle{ x\in[k]^{[n]\setminus Z} }[/math] such that [math]\displaystyle{ (x,y)\in\mathcal{A}_1. }[/math] Let [math]\displaystyle{ \mathcal{B}_1 }[/math] be the set of all points [math]\displaystyle{ x\in[k]^{[n]\setminus Z} }[/math] such that [math]\displaystyle{ \{x\}\times S_1\subset\mathcal{A}. }[/math]

Second step of the iteration

Since [math]\displaystyle{ \mathbf{K} }[/math] is a hereditary property, the intersection [math]\displaystyle{ \mathcal{A}_y }[/math] of [math]\displaystyle{ \mathcal{A} }[/math] with [math]\displaystyle{ S_y }[/math] belongs to [math]\displaystyle{ \mathbf{K} }[/math] for every [math]\displaystyle{ y\in[k]^{Z}. }[/math] If [math]\displaystyle{ y\notin S_1, }[/math] then no points have been removed from [math]\displaystyle{ \mathcal{A}_y, }[/math] so [math]\displaystyle{ \mathcal{A}_{1,y}=\mathcal{A}_y. }[/math] If [math]\displaystyle{ y\in S_1, }[/math] then [math]\displaystyle{ \mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1. }[/math]

Now [math]\displaystyle{ \mathcal{B}_1=\bigcap_{y\in S_1}\mathcal{A}_y. }[/math] Therefore, since [math]\displaystyle{ \mathbf{K} }[/math] is hereditary and a sigma-algebra property, [math]\displaystyle{ \mathcal{B}_1\in\mathbf{K}. }[/math] And then, using the sigma-algebra assumption again, we have that [math]\displaystyle{ \mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1\in\mathbf{K}. }[/math]

For every y such that [math]\displaystyle{ \mathcal{A}_{1,y} }[/math] has density at least [math]\displaystyle{ \delta/2 }[/math] in [math]\displaystyle{ S_y, }[/math] we return to the first iteration. For this to work, we need n-M to be large enough for the conclusion of the richness hypothesis to be satisfied. For every y such that [math]\displaystyle{ \mathcal{A}_{1,y} }[/math] has density less than [math]\displaystyle{ \delta/2 }[/math] we put [math]\displaystyle{ \mathcal{A}_{1,y} }[/math] into the "error set" [math]\displaystyle{ \mathcal{A}''. }[/math]

How does the iteration finish?

At each stage of the iteration, we have split [math]\displaystyle{ \mathcal{A} }[/math] into three sets. One of these sets consists of parts of [math]\displaystyle{ \mathcal{A} }[/math] that have had density at most [math]\displaystyle{ \delta/2 }[/math] in some subspace. Thus, the density of this set never exceeds [math]\displaystyle{ \delta/2. }[/math] Another part consists of a union of disjoint m-dimensional subspaces. The rest of [math]\displaystyle{ \mathcal{A} }[/math] we think of as the "unfinished" part. For this part, if we have reached the sth stage of the iteration, then we have a partition of [math]\displaystyle{ [k]^n }[/math] into subspaces of codimension [math]\displaystyle{ sM, }[/math] and any point in the unfinished part of [math]\displaystyle{ \mathcal{A} }[/math] belongs to a subspace from this collection inside which it has density at least [math]\displaystyle{ \delta/2. }[/math]

It follows that, by the next iteration, the total density of the unfinished part is multiplied by a factor of at most [math]\displaystyle{ 1-c, }[/math] since from each subspace into which we have partitioned the unfinished part we remove a union of subspaces of density at least [math]\displaystyle{ c. }[/math] Therefore, if we continue for [math]\displaystyle{ c^{-1}\log(2/\delta) }[/math] iterations, then the measure of the unfinished part is at most [math]\displaystyle{ \delta/2. }[/math] At this point we put it into [math]\displaystyle{ \mathcal{A}''. }[/math]

In order to be able to continue for this many iterations, we need [math]\displaystyle{ n-Mc^{-1}\log(2/\delta) }[/math] to be sufficiently large for it to be possible to appeal to the richness hypothesis.

[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]