Proof of DHJ(3) via density-increment

Introduction

This article is intended to contain a proof outline of DHJ([math]\displaystyle{ 3 }[/math]) via the density-increment method. The proofs of each step in the outline will appear in separate articles. The goal is to rigorously codify the "second outline" proof. A secondary goal is to write the proof in such a way that it becomes "easy" to see the generalization to DHJ([math]\displaystyle{ k }[/math]). Each step of the outline has a "Proofread By" section to which people can add their names.

Notation and definitions

We'll call the main probability distribution we work with the Pólya Urn distribution. As a distribution on [math]\displaystyle{ [k]^n }[/math], we'll write it as [math]\displaystyle{ \nu_k^n }[/math], or as [math]\displaystyle{ \nu_k }[/math] or [math]\displaystyle{ \nu }[/math] if it's clear from context. (Note: even if one only wants to prove DHJ([math]\displaystyle{ 3 }[/math]), one needs to define [math]\displaystyle{ \nu_k^n }[/math] for general [math]\displaystyle{ k }[/math].) One way to define it is as follows: Order the coordinates [math]\displaystyle{ [n] }[/math] in a list according to a random permutation. Now choose [math]\displaystyle{ k-1 }[/math] distinct "partition points" uniformly at random from the [math]\displaystyle{ \binom{n+1}{k-1} }[/math] possibilities. This partitions the list of coordinates into [math]\displaystyle{ k }[/math] sublists; take the [math]\displaystyle{ 1 }[/math]st sublist of coordinates to be [math]\displaystyle{ 1 }[/math]'s, the [math]\displaystyle{ 2 }[/math]nd sublist to be [math]\displaystyle{ 2 }[/math]'s, etc. Note that any string drawn from the Pólya Urn distribution is nondegenerate, meaning it contains at least one of each character in [math]\displaystyle{ [3] }[/math].

A closely related distribution is called the Equal Slices distribution. We will denote this distribution by [math]\displaystyle{ \overline{\nu}_k^n }[/math]. It has the same definition as the Pólya Urn definition just given, except that the [math]\displaystyle{ k-1 }[/math] partition points are "allowed to be equal"; more precisely, we choose the [math]\displaystyle{ 1 }[/math]st partition point uniformly from the [math]\displaystyle{ n+1 }[/math] possibilities, then we choose the [math]\displaystyle{ 2 }[/math]nd partition point uniformly from the [math]\displaystyle{ n+2 }[/math] possibilities, etc. It should be clear from these definitions that the total variation distance between [math]\displaystyle{ \nu_k^n }[/math] and [math]\displaystyle{ \overline{\nu}_k^n }[/math] is small. Here is a proof that it is [math]\displaystyle{ O(k^2/n) }[/math].

We identify combinatorial lines in [math]\displaystyle{ [3]^n }[/math] with strings in [math]\displaystyle{ [4]^n }[/math], where the [math]\displaystyle{ 4 }[/math] character is treated as identifying the "wildcard" set. Similarly, we identify [math]\displaystyle{ 2 }[/math]-dimensional combinatorial subspaces in [math]\displaystyle{ [3]^n }[/math] with strings in [math]\displaystyle{ [5]^n }[/math], where the characters [math]\displaystyle{ 4 }[/math] and [math]\displaystyle{ 5 }[/math] identify the [math]\displaystyle{ 2 }[/math] wildcard sets. Etc. Note that a combinatorial line in [math]\displaystyle{ [3]^n }[/math] drawn from [math]\displaystyle{ \nu_4^n }[/math] is automatically nondegenerate. Henceforth, whenever we say "combinatorial line" or "combinatorial subspace" without qualification, the object is assumed to be nondegenerate.

Although we will prove DHJ([math]\displaystyle{ 3 }[/math]) for sets that are dense under [math]\displaystyle{ \nu_3 }[/math], this also proves it for sets that are dense under the usual uniform distribution; this should be explicated in the article on passing between measures.

Proof Outline

Here is the sequence of statements we prove:

1. Dense sets in [math]\displaystyle{ [2]^n }[/math] contain lines (i.e., DHJ([math]\displaystyle{ 2 }[/math])).

2. Dense sets in [math]\displaystyle{ [2]^n }[/math] contain large subspaces.

3. Dense ij-insensitive sets in [math]\displaystyle{ [3]^n }[/math] contain large subspaces.

4. Dense [math]\displaystyle{ ij }[/math]-insensitive sets in [math]\displaystyle{ [3]^n }[/math] are large-subspace rich.

5. Dense [math]\displaystyle{ ij }[/math]-insensitive sets in [math]\displaystyle{ [3]^n }[/math] are large-subspace partitionable.

6. Dense intersections of [math]\displaystyle{ ij }[/math]-insensitive sets in [math]\displaystyle{ [3]^n }[/math] are large-subspace partitionable.

7. Line-free sets in [math]\displaystyle{ [3]^n }[/math] have density increments on dense intersections of [math]\displaystyle{ ij }[/math]-insensitive sets.

8. Line-free sets in [math]\displaystyle{ [3]^n }[/math] have density increments on large subspaces.

9. Dense sets in [math]\displaystyle{ [3]^n }[/math] contain lines (i.e., DHJ([math]\displaystyle{ 3 }[/math])).

1. Sets in [math]\displaystyle{ [2]^n }[/math] have lines

Proofread By: no one yet

This is simply Sperner's Theorem. Our version, with the Pólya Urn distribution, is:

Theorem 1: Let [math]\displaystyle{ A \subseteq [2]^n }[/math] have [math]\displaystyle{ \nu_2 }[/math]-density at least [math]\displaystyle{ \delta }[/math]. Assume that [math]\displaystyle{ n \geq n_1(\delta) }[/math], where [math]\displaystyle{ n_1(\delta) = O(1/\delta^2) }[/math]. Then [math]\displaystyle{ A }[/math] contains a combinatorial ([math]\displaystyle{ 2 }[/math]-)line.

Proof of Sperner's Theorem. For now, the proof more or less appears in the article on Sperner's Theorem; we might want to use the writeup ideas in the current article on Equal Slices. The easiest proof involves first passing from Pólya to Equal Slices. I think you only need [math]\displaystyle{ n_1(\delta) \gt 1/\delta^2 + 1 }[/math] or something.

2. Sets in [math]\displaystyle{ [2]^n }[/math] have subspaces

Proofread By: no one yet

The next step is to extend DHJ([math]\displaystyle{ 2 }[/math]) from lines to subspaces of arbitrary dimension.

Lemma 2: Let [math]\displaystyle{ A \subseteq [2]^n }[/math] have [math]\displaystyle{ \nu_2 }[/math]-density at least [math]\displaystyle{ \delta }[/math], and let [math]\displaystyle{ d \geq 1 }[/math]. Assume that [math]\displaystyle{ n \geq n_2(\delta,d) }[/math]. Then [math]\displaystyle{ A }[/math] contains a [math]\displaystyle{ d }[/math]-dimensional combinatorial subspace. Here [math]\displaystyle{ n_2(\delta,d) }[/math] probably only needs to be [math]\displaystyle{ O(1/\delta)^{2^{d+1}} }[/math]

This sort of result has been shown for the uniform distribution case by [[1]], from which one can easily conclude the Pólya distribution case by passing between measures. Alternatively, one can prove the result with a (much) worse bound on [math]\displaystyle{ n_2 }[/math] using an argument which generalizes to [math]\displaystyle{ [k]^n }[/math]. A few technical bits need to be filled into this argument; namely, showing that if one does Pólya on some small random subset [math]\displaystyle{ S \subseteq [n] }[/math], and then combines this with an independent Pólya draw on [math]\displaystyle{ [n] \setminus S }[/math], the overall draw is very close in total variation distance to a normal Pólya draw. This is proved rather explicitly in the passing between measures article. (Presumably there is also literature from the Pólya Urn studiers on this, too.)

3. [math]\displaystyle{ ij }[/math]-insensitive sets in [math]\displaystyle{ [3]^n }[/math] have subspaces

Proofread By: no one yet

Let [math]\displaystyle{ i,j \in [k] }[/math] be distinct characters. We define [math]\displaystyle{ A \subseteq [k]^n }[/math] to be an "[math]\displaystyle{ ij }[/math]-insensitive set" if for all strings [math]\displaystyle{ x }[/math], changing [math]\displaystyle{ i }[/math]'s to [math]\displaystyle{ j }[/math]'s in [math]\displaystyle{ x }[/math] or vice versa does not change whether or not [math]\displaystyle{ x \in A }[/math].

An [math]\displaystyle{ 23 }[/math]-insensitive in [math]\displaystyle{ [3]^n }[/math] is elsewhere on the blog called a "[math]\displaystyle{ 1 }[/math]-set", since it depends only on the set of coordinates where the value 1 is taken. It is a special case of a special set of complexity [math]\displaystyle{ 1 }[/math]. See also this article discussing the complexity of sets.

The statement we prove here is:

Lemma 3: Let [math]\displaystyle{ A \subseteq [3]^n }[/math] be an [math]\displaystyle{ ij }[/math]-insensitive set with [math]\displaystyle{ \nu_3 }[/math]-density at least [math]\displaystyle{ \delta }[/math], and let [math]\displaystyle{ d \geq 1 }[/math]. Assume that [math]\displaystyle{ n \geq n_3(\delta,d) = \sqrt{2/\delta} \cdot n_2(\delta/2, d) }[/math]. Then [math]\displaystyle{ A }[/math] contains a [math]\displaystyle{ d }[/math]-dimensional combinatorial subspace.

We sketch the proof here, for now.

Proof: (Sketch.) Assume without loss of generality that [math]\displaystyle{ i = 2 }[/math], [math]\displaystyle{ j = 3 }[/math]. We can think of a draw [math]\displaystyle{ x \sim \nu_3^n }[/math] by first conditioning on the set of coordinates [math]\displaystyle{ S }[/math] where [math]\displaystyle{ x }[/math] has its [math]\displaystyle{ 3 }[/math]'s, and then drawing the remainder of the string as [math]\displaystyle{ y \sim \nu_2^{|\overline{S}|} }[/math], where [math]\displaystyle{ \overline{S} = [n] \setminus S }[/math]. (This requires a quick justification.) Inventing some notation, we have [math]\displaystyle{ \mathbf{E}_S[\nu_2(A_S)] = \delta }[/math]. Further, it should be easy to check that [math]\displaystyle{ \mathbf{Pr}[|\overline{S}| \lt \gamma n] \leq \gamma^2 }[/math] (or perhaps only a tiny bit higher). Hence [math]\displaystyle{ \mathbf{E}_S[\nu_2(A_S) \mid |\overline{S}| \geq \gamma n] \geq \delta - \gamma^2. }[/math] We set [math]\displaystyle{ \gamma = \sqrt{\delta/2} }[/math] and conclude that there exists a particular set of [math]\displaystyle{ 3 }[/math]-coordinates [math]\displaystyle{ S_0 }[/math] such that [math]\displaystyle{ \nu_2(A_{S_0}) \geq \delta/2 }[/math] and [math]\displaystyle{ |\overline{S_0}| \geq \sqrt{\delta/2} n }[/math]. By choice of [math]\displaystyle{ n_2 }[/math], this lets us apply Lemma 2 to conclude that [math]\displaystyle{ A_{S_0} \subseteq [2]^{S_0} }[/math] contains a [math]\displaystyle{ d }[/math]-dimensional combinatorial subspace; call it [math]\displaystyle{ \sigma }[/math].

Pulling [math]\displaystyle{ \sigma }[/math] back into [math]\displaystyle{ [3]^n }[/math] by putting [math]\displaystyle{ 3 }[/math]'s into the [math]\displaystyle{ S }[/math] coordinates, we get a [math]\displaystyle{ d }[/math]-dimensional "[math]\displaystyle{ 2 }[/math]-subspace" in [math]\displaystyle{ A \subseteq [3]^n }[/math]. But in fact, all of the strings necessary to fill this out into a complete [math]\displaystyle{ d }[/math]-dimensional subspace in [math]\displaystyle{ [3]^n }[/math] must also be present in [math]\displaystyle{ A }[/math], because [math]\displaystyle{ A }[/math] is [math]\displaystyle{ 23 }[/math]-insensitive. [math]\displaystyle{ \Box }[/math] (somewhat poorly explained)

4. [math]\displaystyle{ ij }[/math]-insensitive sets are subspace rich

Proofread By: no one yet

Lemma 4: Let [math]\displaystyle{ A \subseteq [3]^n }[/math] be an [math]\displaystyle{ ij }[/math]-insensitive set with [math]\displaystyle{ \nu }[/math]-density at least [math]\displaystyle{ \delta }[/math], and let [math]\displaystyle{ d \geq 1 }[/math]. Assume that [math]\displaystyle{ n \geq n_4(\delta,d) = n_3(\delta/2,d) }[/math]. Then a random [math]\displaystyle{ d }[/math]-dimensional subspace drawn from [math]\displaystyle{ \nu^n_{3+d} }[/math] is in [math]\displaystyle{ A }[/math] with probability at least [math]\displaystyle{ \eta_4(\delta, d) = \delta/(O(d))^{n_4(\delta,d)} }[/math].

This is sketched originally here. Here is a more complete argument:

Proof: (Sketch.) For any [math]\displaystyle{ 3 \leq m \leq n }[/math] one can draw a string [math]\displaystyle{ h \sim \nu_3^n }[/math] as follows: First, draw [math]\displaystyle{ f \sim \nu_m^n }[/math]; then independently draw [math]\displaystyle{ g \sim \nu_3^m }[/math]; finally, set [math]\displaystyle{ h = g \circ f }[/math]. This notation means that [math]\displaystyle{ h_i = g_{f_i} }[/math]. The fact that this indeed gives the distribution [math]\displaystyle{ \nu_3^n }[/math] is justified in [document], but should be simplified and ported to the wiki.

By assumption, [math]\displaystyle{ \mathbf{Pr}[h \in A] \geq \delta }[/math]; hence with probability at least [math]\displaystyle{ \delta/2 }[/math] over the choice of [math]\displaystyle{ f }[/math] we get that [math]\displaystyle{ A_f \subseteq [3]^m }[/math] has [math]\displaystyle{ \nu_3 }[/math]-density at least [math]\displaystyle{ \delta/2 }[/math]. Here [math]\displaystyle{ A_f }[/math] of course denotes [math]\displaystyle{ \{g \in [3]^m : g \circ f \in A }[/math]. Crucially, [math]\displaystyle{ A_f }[/math] is an [math]\displaystyle{ ij }[/math]-insensitive set because [math]\displaystyle{ A }[/math]. (This takes a slight bit of reflection but is, I think, easily confirmed.) Call an [math]\displaystyle{ f }[/math] "good" if indeed [math]\displaystyle{ \nu_3(A_f) \geq \delta/2 }[/math].

We therefore select [math]\displaystyle{ m = n_3(\delta/2,d) }[/math] (which is allowable as [math]\displaystyle{ n \geq n_3(\delta/2,d) }[/math]) and use Lemma 3 to conclude that for each good [math]\displaystyle{ f }[/math], the set [math]\displaystyle{ A_f }[/math] contains some [math]\displaystyle{ d }[/math]-dimensional subspace. In these cases, a randomly chosen subspace [math]\displaystyle{ \sigma \sim [3+d]^m }[/math] is in [math]\displaystyle{ A_f }[/math] with some positive probability. At this point, we should calculate the least probability of any outcome under [math]\displaystyle{ \nu_k^n }[/math]; I believe it is [math]\displaystyle{ \frac{\Theta(1/k)^{k/2}}{n^{(k-1)/2} \cdot k^n} }[/math]. Lower-bounding this crudely, we have that [math]\displaystyle{ \sigma \sim [3+d]^m }[/math] is in [math]\displaystyle{ A_f }[/math] with probability at least [math]\displaystyle{ (O(d))^{-m} }[/math].

So overall we have that for [math]\displaystyle{ f \sim \nu_3^m }[/math] and [math]\displaystyle{ \sigma \sim [3+d]^m }[/math], the probability of [math]\displaystyle{ \sigma \circ f }[/math] being entirely in [math]\displaystyle{ A }[/math] is at least [math]\displaystyle{ \delta/(O(d))^m = \delta/(O(d))^{n_3(\delta/2,d)} }[/math]. But [math]\displaystyle{ \sigma \circ f }[/math] is distributed as [math]\displaystyle{ \nu_{3+d}^n }[/math], completing the proof. [math]\displaystyle{ \Box }[/math]

5. [math]\displaystyle{ ij }[/math]-insensitive sets are subspace partitionable

Proofread By: no one yet

Definition: A set [math]\displaystyle{ A \subseteq [3]^n }[/math] is "[math]\displaystyle{ (\gamma,d) }[/math]-subspace partitionable" if it can be written as a disjoint union of [math]\displaystyle{ d }[/math]-dimensional combinatorial subspaces, along with a single "error" set [math]\displaystyle{ E }[/math] satisfying [math]\displaystyle{ \nu(E)/\nu(A) \leq \gamma }[/math].

Lemma 5: Let [math]\displaystyle{ A \subseteq [3]^n }[/math] be an [math]\displaystyle{ ij }[/math]-insensitive set with [math]\displaystyle{ \nu }[/math]-density at least [math]\displaystyle{ \delta }[/math], let [math]\displaystyle{ d \geq 1 }[/math], and let [math]\displaystyle{ \gamma \in (0,1) }[/math] be a parameter. Assume that [math]\displaystyle{ n \geq n_5(\delta,\gamma,d) = XXX }[/math]. Then [math]\displaystyle{ A }[/math] is [math]\displaystyle{ (\gamma,d) }[/math]-subspace partitionable.

This is currently written fairly thoroughly here, although the parameters need to be worked out to fill in the "XXX" in the statement.

6. Intersections of [math]\displaystyle{ ij }[/math]-insensitive sets are subspace partitionable

Proofread By: no one yet

Currently written here.

7. Line-free sets increment on intersections of [math]\displaystyle{ ij }[/math]-insensitive sets

Proofread By: no one yet

Written mostly completely here, although some of the "passing between measures" tricks that were done for the uniform distribution should be done for the Pólya distribution instead.

8. Line-free sets increment on subspaces

Proofread By: no one yet

Sketch here.

9. Sets in [math]\displaystyle{ [3]^n }[/math] have lines

Proofread By: no one yet

The basic idea is described in the article on the density increment method.