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

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.

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. We shall call the property [math]\displaystyle{ \mathbf{K}\lt \math\gt ''subspace rich'' if for every m and every \lt math\gt \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.

Richness hypothesis. 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.

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

Lemma. Let [math]\displaystyle{ \mathbf{K} }[/math] be a hereditary and subspace-rich Hales-Jewett 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}_1\cup\mathcal{A}_2 }[/math] such that [math]\displaystyle{ \mathcal{A}_1 }[/math] is a disjoint union of m-dimensional subspaces and [math]\displaystyle{ \mathcal{A}_2 }[/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]

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] [math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math]