Difference between revisions of "Line free sets correlate locally with dense sets of complexity k-2"

From Polymath Wiki
Jump to: navigation, search
(Proof of the main result, with a gap still left to fill)
(DHJ(k) implies equal-slices Varnavides-DHJ(k))
Line 1: Line 1:
==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>0,</math> then <math>\nu(\mathcal{B})\geq\eta=\eta(\theta)>0.</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)>0.</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.

Revision as of 03:22, 24 April 2009