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.

Remove all these subspaces [math]\displaystyle{ \{x\}\times S_1, }[/math] and partition [math]\displaystyle{ [k]^n }[/math] into the [math]\displaystyle{ 3^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]^{[n]\setminus 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 these two assumptions again, we have that [math]\displaystyle{ \mathcal{A}_y }[/math] and hence [math]\displaystyle{ \mathcal{A}_{1,y}=\mathcal{A}_y\setminus\mathcal{B}_1\in\mathbf{K}. }[/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][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]