Proof of DHJ(3) via density-increment: Difference between revisions
Created stub |
Further stub |
||
| Line 10: | Line 10: | ||
A closely related distribution is called the [[Equal-slices_distribution_for_DHJ(k)|Equal Slices distribution]]. We will denote this distribution by <math>\overline{\nu}_k^n</math>. It has the same definition as the Pólya Urn definition just given, except that the <math>k-1</math> partition points are "allowed to be equal"; more precisely, we choose the <math>1</math>st partition point uniformly from the <math>n+1</math> possibilities, then we choose the <math>2</math>nd partition point uniformly from the <math>n+2</math> possibilities, etc. It should be clear from these definitions that the [[total variation distance]] between <math>\nu_k^n</math> and <math>\overline{\nu}_k^n</math> is small. Here is a [[to_be_filled|proof that it is <math>O(k^2/n)</math>]]. | A closely related distribution is called the [[Equal-slices_distribution_for_DHJ(k)|Equal Slices distribution]]. We will denote this distribution by <math>\overline{\nu}_k^n</math>. It has the same definition as the Pólya Urn definition just given, except that the <math>k-1</math> partition points are "allowed to be equal"; more precisely, we choose the <math>1</math>st partition point uniformly from the <math>n+1</math> possibilities, then we choose the <math>2</math>nd partition point uniformly from the <math>n+2</math> possibilities, etc. It should be clear from these definitions that the [[total variation distance]] between <math>\nu_k^n</math> and <math>\overline{\nu}_k^n</math> is small. Here is a [[to_be_filled|proof that it is <math>O(k^2/n)</math>]]. | ||
We identify [[Combinatorial_line|combinatorial lines]] in <math>[3]^n</math> with strings in <math>[4]^n</math>, where the <math>4</math> character is treated as identifying the "wildcard" set. Similarly, we identify <math>2</math>-dimensional [[Combinatorial_subspace|combinatorial subspaces]] in <math>[3]^n</math> with strings in <math>[5]^n</math>, where the characters <math>4</math> and <math>5</math> identify the <math>2</math> wildcard sets. Etc. | We identify [[Combinatorial_line|combinatorial lines]] in <math>[3]^n</math> with strings in <math>[4]^n</math>, where the <math>4</math> character is treated as identifying the "wildcard" set. Similarly, we identify <math>2</math>-dimensional [[Combinatorial_subspace|combinatorial subspaces]] in <math>[3]^n</math> with strings in <math>[5]^n</math>, where the characters <math>4</math> and <math>5</math> identify the <math>2</math> wildcard sets. Etc. Note that a combinatorial line in <math>[3]^n</math> drawn from <math>\nu_4^n</math> is automatically nondegenerate. | ||
Although we will prove DHJ(<math>3</math>) for sets that are dense under <math>\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>[2]^n</math> contain lines (i.e., DHJ(<math>2</math>)). | |||
2. Dense [[ij-insensitive]] sets in <math>[3]^n</math> contain lines. | |||
3. Dense <math>ij</math>-insensitive sets in <math>[3]^n</math> contain large subspaces. | |||
4. Dense <math>ij</math>-insensitive sets in <math>[3]^n</math> are [[large-subspace rich]]. | |||
5. Dense <math>ij</math>-insensitive sets in <math>[3]^n</math> are [[large-subspace partitionable]]. | |||
6. Dense intersections of <math>ij</math>-insensitive sets in <math>[3]^n</math> are large-subspace partitionable. | |||
7. Line-free sets in <math>[3]^n</math> have density increments on dense intersections of <math>ij</math>-insensitive sets. | |||
8. Line-free sets in <math>[3]^n</math> have density increments on large subspaces. | |||
9. Dense sets in <math>[3]^n</math> contain lines (i.e., DHJ(<math>3</math>)). | |||
===Sets in <math>[2]^n</math> have lines=== | |||
===<math>ij</math>-sets in <math>[3]^n</math> have lines=== | |||
===<math>ij</math>-sets have subspaces=== | |||
===<math>ij</math>-sets are subspace rich=== | |||
===<math>ij</math>-sets are subspace partitionable=== | |||
===Intersections of <math>ij</math>-sets are subspace partitionable=== | |||
===Line-free sets increment on intersections of <math>ij</math>-sets=== | |||
===Line-free sets increment on subspaces=== | |||
===Sets in <math>[3]^n</math> have lines=== | |||
Revision as of 14:25, 19 March 2009
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]).
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.
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 ij-insensitive sets in [math]\displaystyle{ [3]^n }[/math] contain lines.
3. Dense [math]\displaystyle{ ij }[/math]-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])).
