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

## 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 $\mathcal{B}$ is an equal-slices dense subset of $[k]^n,$ then with positive probability an equal-slices random combinatorial line is contained in $\mathcal{A}.$

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

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

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

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

It remains to define an appropriate measure $\nu.$ 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 $a_1+\dots+a_M=n$ and then randomly partitioning $[n]$ into wildcard sets $Z_1,\dots,Z_M$ with $|Z_i|=a_i.$ Then $\nu$ is the measure you get by choosing a random subspace in this way and then choosing a random point in that subspace.

Now $\nu$ 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.