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 [math]\displaystyle{ \bigcup_{n=1}^\infty[k]^n. }[/math] We shall say that [math]\displaystyle{ \mathbf{K} }[/math] is hereditary if [math]\displaystyle{ \mathcal{A}\cap S\in\mathcal{K} }[/math] whenever [math]\displaystyle{ \mathcal{A}\in\mathbf{K} }[/math] and S is a combinatorial subspace of [math]\displaystyle{ [k]^n. }[/math] We shall call it 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.

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]

Lemma. Let [math]\displaystyle{ \mathbf{K} }[/math] be a hereditary and subspace-rich class of subsets of [math]\displaystyle{ [k]^n. }[/math] 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. [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]