View source for Proof of DHJ(3) via density-increment

==Introduction==

This article is intended to contain a proof outline of DHJ(<math>3</math>) via the [[Density_increment_method|density-increment method]].  The proofs of each step in the outline will appear in separate articles.  The goal is to rigorously codify the [[A_second_outline_of_a_density-increment_argument|"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>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>[k]^n</math>, we'll write it as <math>\nu_k^n</math>, or as <math>\nu_k</math> or <math>\nu</math> if it's clear from context.  (Note: even if one only wants to prove DHJ(<math>3</math>), one needs to define <math>\nu_k^n</math> for general <math>k</math>.)  One way to define it is as follows:  Order the coordinates <math>[n]</math> in a list according to a random permutation.  Now choose <math>k-1</math> distinct "partition points" uniformly at random from the <math>\binom{n+1}{k-1}</math> possibilities.  This partitions the list of coordinates into <math>k</math> sublists; take the <math>1</math>st sublist of coordinates to be <math>1</math>'s, the <math>2</math>nd sublist to be <math>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>[3]</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.