Line free sets correlate locally with dense sets of complexity k-2

From Polymath Wiki
Revision as of 18:37, 23 April 2009 by (Talk)

Jump to: navigation, search

DHJ(k) implies equal-slices Varnavides-DHJ(k)

This section is intended to fill the main gap in the section above. We would like to deduce from DHJ(k) that if [math]\mathcal{B}[/math] is an equal-slices dense subset of [math][k]^n,[/math] then with positive probability an equal-slices random combinatorial line is contained in [math]\mathcal{A}.[/math]

To prove this it is enough to do the following. Let the density of [math]\mathcal{B}[/math] be [math]\theta,[/math] let [math]\zeta[/math] be some positive constant that depends on [math]\theta[/math] only, and let M be large enough that every subset of [math][k]^M[/math] of density at least [math]\zeta[/math] contains a combinatorial line. We would now like to find a positive linear combination [math]\nu[/math] of characteristic functions of M-dimensional subspaces of [math][k]^n[/math] with the following properties.

  • [math]\nu[/math] is a probability measure: that is, it sums to 1.
  • If [math]\mathcal{B}[/math] is any subset of [math][k]^n[/math] with equal-slices density [math]\theta\gt0,[/math] then [math]\nu(\mathcal{B})\geq\eta=\eta(\theta)\gt0.[/math]
  • Let [math]\mathcal{L}[/math] be a set of combinatorial lines. Define the [math]\nu[/math]-density of [math]\mathcal{L}[/math] to be the probability that a random line L belongs to [math]\mathcal{L}[/math] if you choose it by first picking a [math]\nu[/math]-random subspace and then picking a random line (uniformly) from that subspace. (See below for the definition of [math]\nu[/math]-random subspace.) Then if the [math]\nu[/math]-density of [math]\mathcal{L}[/math] is at least [math]c,[/math] then the equal-slices density of [math]\mathcal{L}[/math] is at least [math]c'(c).[/math]

Let us see why these three properties are enough. Let the M-dimensional subspaces of [math][k]^n[/math] be enumerated as [math]S_1,\dots,S_N,[/math] and let [math]\sigma_i[/math] be the uniform probability measure on [math]S_i.[/math] Then we are looking for a convex combination [math]\nu=\sum_{i=1}^N\lambda_i\sigma_i[/math] of the measures [math]\sigma_i.[/math] Given such a [math]\nu,[/math] we define a [math]\nu[/math]-random subspace to be what you get when you choose [math]S_i[/math] with probability [math]\lambda_i.[/math]

Suppose we have found [math]\nu[/math] with the three properties above, and let [math]\mathcal{B}[/math] be a set of equal-slices density [math]\theta.[/math] Then by hypothesis we have that [math]\nu(\mathcal{B})\geq\eta.[/math] This implies that if [math]S_i[/math] is a [math]\nu[/math]-random subspace, then the probability that [math]\sigma_i(\mathcal{B})\geq\eta/2[/math] is at least [math]\eta/2.[/math] If we have taken [math]\zeta[/math] to be [math]\eta/2,[/math] then each subspaces [math]S_i[/math] for which [math]\sigma_i(\mathcal{B})\geq\eta/2[/math] contains a combinatorial line in [math]\mathcal{B}.[/math] Since an M-dimensional subspace contains [math](k+1)^M[/math] combinatorial lines, this implies that the [math]\nu[/math]-density of the set of all combinatorial lines in [math]\mathcal{B}[/math] is at least [math]\eta/2(k+1)^M.[/math] Hence, by the third property, the equal-slices density of this set of lines is at least [math]c(\theta,k,M)\gt0.[/math]

It remains to define an appropriate measure [math]\nu.[/math] I think probably a fairly obvious equal-slices measure on M-dimensional subspaces will do the trick, but will have to wait to check this.

Here is a preliminary attempt to do the check. This will be tidied up at some point if it works. Let us define a random M-dimensional subspace S by randomly choosing numbers [math]a_1+\dots+a_M=n[/math] and then randomly partitioning [math][n][/math] into wildcard sets [math]Z_1,\dots,Z_M[/math] with [math]|Z_i|=a_i.[/math] Then [math]\nu[/math] is the measure you get by choosing a random subspace in this way and then choosing a random point in that subspace.

Now [math]\nu[/math] is nothing like the equal-slices density, since a typical point will have roughly equal numbers of each coordinate value. However, the probability that we deviate from this average is small as a function of M rather than as a function of n, so the second property looks fine.

A similar argument appears to deal with the third property. It may be a bore to make it rigorous, but I definitely believe it.