Line free sets correlate locally with dense sets of complexity k-2
bBzk7b <a href="http://hcldigzjsdll.com/">hcldigzjsdll</a>, [url=http://yhhozjkgrxnj.com/]yhhozjkgrxnj[/url], [link=http://rlvcfsbsgddq.com/]rlvcfsbsgddq[/link], http://lxkwhxtjoxgx.com/
Notation and definitions
The actual result to be proved is more precise than the result given in the title of the page. To explain it we need a certain amount of terminology. Given [math]\displaystyle{ j\leq k }[/math] and a sequence [math]\displaystyle{ x\in[k]^n, }[/math] let [math]\displaystyle{ U_j(x) }[/math] denote the set [math]\displaystyle{ \{i\in[n]:x_i=j\}. }[/math] We call this the j-set of x. More generally, if [math]\displaystyle{ E\subset[k], }[/math] let [math]\displaystyle{ U_E(x) }[/math] denote the sequence [math]\displaystyle{ (U_j(x):j\in E). }[/math] We call this the E-sequence of x. For example, if n=10, k=4, [math]\displaystyle{ x=3442411123 }[/math] and [math]\displaystyle{ E=\{2,3\} }[/math] then the E-sequence of x is [math]\displaystyle{ (\{4,9\},\{1,10\}). }[/math] It can sometimes be nicer to avoid set-theoretic brackets and instead to say things like that the 24-sequence of x is [math]\displaystyle{ (49,235). }[/math]
An E-set is a set [math]\displaystyle{ \mathcal{A}\subset[k]^n }[/math] such that whether or not x belongs to [math]\displaystyle{ \mathcal{A} }[/math] depends only on the E-sequence of x. In other words, to define an E-set one chooses a collection [math]\displaystyle{ \mathcal{U}_E }[/math] of sequences of the form [math]\displaystyle{ (U_i:i\in E), }[/math] where the [math]\displaystyle{ U_i }[/math] are disjoint subsets of [n], and one takes the set of all x such that [math]\displaystyle{ (U_i(x):i\in E)\in\mathcal{U}_E. }[/math] More generally, an [math]\displaystyle{ (E_1,\dots,E_r) }[/math]-set is an intersection of [math]\displaystyle{ E_h }[/math]-sets as h runs from 1 to r.
Of particular interest to us will be the sequence [math]\displaystyle{ (E_1,\dots,E_{k-1}), }[/math] where [math]\displaystyle{ E_j=[k-1]\setminus j. }[/math] What is an [math]\displaystyle{ (E_1,\dots,E_{k-1}) }[/math]set? It is a set where membership depends on k-1 conditions, and the jth condition on a sequence x depends just on the sets [math]\displaystyle{ U_i(x) }[/math] with [math]\displaystyle{ i\leq k-1 }[/math] and [math]\displaystyle{ i\ne j. }[/math]
Since it provides a useful illustrative example, let us describe the class of sets that will arise in the proof. Suppose we have a set [math]\displaystyle{ \mathcal{B}\subset[k-1]^n. }[/math] We can use [math]\displaystyle{ \mathcal{B} }[/math] to define a set [math]\displaystyle{ \mathcal{C}\subset[k]^n }[/math] as follows. A sequence x belongs to [math]\displaystyle{ \mathcal{C} }[/math] if and only if for each j < k the following holds: if change all the k's of x into j's, the resulting sequence is in [math]\displaystyle{ \mathcal{B}. }[/math]
To see that this is an [math]\displaystyle{ (E_1,\dots,E_{k-1}) }[/math]-set, it is enough to show that the set [math]\displaystyle{ \mathcal{C}_j }[/math] of all x such that changing ks to js puts you in [math]\displaystyle{ \mathcal{B} }[/math] is an [math]\displaystyle{ E_j }[/math]-set. And indeed, whether or not x belongs to that set does depend only on the i-sets [math]\displaystyle{ U_i(x) }[/math] with [math]\displaystyle{ i\leq k-1 }[/math] and [math]\displaystyle{ i\ne j, }[/math] since once you know those you have determined the sequence obtained from x when you rewrite the ks as js.
[math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math]
Proof of the main result, with a gap still left to fill
To write this section, I lifted a section from the equivalent proof for DHJ(3) and made such changes as were necessary. One result did not go through straightforwardly and now needs to be thought about. (It is pretty clear that it can be done -- it will just need a bit of work.)
Let us assume for now that the equal-slices density of [math]\displaystyle{ \mathcal{A} }[/math] in [math]\displaystyle{ [k]^n }[/math] is at least [math]\displaystyle{ \delta }[/math], and that the equal-slices density of [math]\displaystyle{ \mathcal{A} \cap [k-1]^n }[/math] in [math]\displaystyle{ [k-1]^n }[/math] is at least [math]\displaystyle{ \theta }[/math]. As discussed in the sections below, we can reduce to this case by passing to subspaces. Let us write [math]\displaystyle{ \mathcal{B} }[/math] for [math]\displaystyle{ \mathcal{A}\cap[k-1]^n, }[/math] and let [math]\displaystyle{ \mathcal{C} }[/math] be the set defined in terms of [math]\displaystyle{ \mathcal{B} }[/math] in the previous section.
We shall now deduce from the fact that [math]\displaystyle{ \mathcal{A} }[/math] contains no combinatorial line that it is disjoint from [math]\displaystyle{ \mathcal{C}. }[/math] Indeed, this is pretty well trivial. Given any sequence x, let [math]\displaystyle{ \rho_j(x) }[/math] be the sequence obtained by changing all the ks in x to js. Then the set [math]\displaystyle{ \{\rho_1(x),\dots,\rho_{k-1}(x),x\} }[/math] is a combinatorial line (with wildcard set [math]\displaystyle{ U_k(x) }[/math]). Therefore, not all its points belong to [math]\displaystyle{ \mathcal{A} }[/math] which implies that either [math]\displaystyle{ x\notin\mathcal{A} }[/math] or [math]\displaystyle{ x\notin\mathcal{C}. }[/math]
We will now show that [math]\displaystyle{ \mathcal{C} }[/math] is dense in equal-slices measure on [math]\displaystyle{ [k]^n }[/math].
Hmm ... this is less obvious. Hopefully one can use the understanding of the equal-slices distribution for DHJ(k).
For now let me just say what happens if this is true. If [math]\displaystyle{ \mathcal{C}=\mathcal{C}_1\cap\dots\cap\mathcal{C}_{k-1} }[/math] has density at least [math]\displaystyle{ \eta, }[/math] then consider all the [math]\displaystyle{ 2^{k-1}-1 }[/math] sets of the form [math]\displaystyle{ \mathcal{D}_1\cap\dots\cap\mathcal{D}_{k-1}, }[/math] where each [math]\displaystyle{ \mathcal{D}_i }[/math] is either [math]\displaystyle{ \mathcal{C}_i }[/math] or its complement, and not every [math]\displaystyle{ \mathcal{D}_i }[/math] equals [math]\displaystyle{ \mathcal{C}_i. }[/math] Then there must be some i such that the measure [math]\displaystyle{ \mu(\mathcal{A}\cap\mathcal{D}_i) }[/math] is at least [math]\displaystyle{ \delta\mu(\mathcal{D}_i)+\eta/(2^{k-1}-1). }[/math] This gives us a density increase of at least [math]\displaystyle{ \eta/2^{k-1} }[/math] on a set of density at least [math]\displaystyle{ \eta/2^{k-1}. }[/math]
We should be able to move from this relative density-increment under equal-slices to a nearly as good one under uniform by appropriately generalizing the results in the passing between measures section ("relative density version").
This section is intended to fill the main gap in the section above. We would like to deduce from DHJ(k) that if [math]\displaystyle{ \mathcal{B} }[/math] is an equal-slices dense subset of [math]\displaystyle{ [k]^n, }[/math] then with positive probability an equal-slices random combinatorial line is contained in [math]\displaystyle{ \mathcal{A}. }[/math]
To prove this it is enough to do the following. Let the density of [math]\displaystyle{ \mathcal{B} }[/math] be [math]\displaystyle{ \theta, }[/math] let [math]\displaystyle{ \zeta }[/math] be some positive constant that depends on [math]\displaystyle{ \theta }[/math] only, and let M be large enough that every subset of [math]\displaystyle{ [k]^M }[/math] of density at least [math]\displaystyle{ \zeta }[/math] contains a combinatorial line. We would now like to find a positive linear combination [math]\displaystyle{ \nu }[/math] of characteristic functions of M-dimensional subspaces of [math]\displaystyle{ [k]^n }[/math] with the following properties.
- [math]\displaystyle{ \nu }[/math] is a probability measure: that is, it sums to 1.
- If [math]\displaystyle{ \mathcal{B} }[/math] is any subset of [math]\displaystyle{ [k]^n }[/math] with equal-slices density [math]\displaystyle{ \theta\gt 0, }[/math] then [math]\displaystyle{ \nu(\mathcal{B})\geq\eta=\eta(\theta)\gt 0. }[/math]
- Let [math]\displaystyle{ \mathcal{L} }[/math] be a set of combinatorial lines. Define the [math]\displaystyle{ \nu }[/math]-density of [math]\displaystyle{ \mathcal{L} }[/math] to be the probability that a random line L belongs to [math]\displaystyle{ \mathcal{L} }[/math] if you choose it by first picking a [math]\displaystyle{ \nu }[/math]-random subspace and then picking a random line (uniformly) from that subspace. (See below for the definition of [math]\displaystyle{ \nu }[/math]-random subspace.) Then if the [math]\displaystyle{ \nu }[/math]-density of [math]\displaystyle{ \mathcal{L} }[/math] is at least [math]\displaystyle{ c, }[/math] then the equal-slices density of [math]\displaystyle{ \mathcal{L} }[/math] is at least [math]\displaystyle{ c'(c). }[/math]
Let us see why these three properties are enough. Let the M-dimensional subspaces of [math]\displaystyle{ [k]^n }[/math] be enumerated as [math]\displaystyle{ S_1,\dots,S_N, }[/math] and let [math]\displaystyle{ \sigma_i }[/math] be the uniform probability measure on [math]\displaystyle{ S_i. }[/math] Then we are looking for a convex combination [math]\displaystyle{ \nu=\sum_{i=1}^N\lambda_i\sigma_i }[/math] of the measures [math]\displaystyle{ \sigma_i. }[/math] Given such a [math]\displaystyle{ \nu, }[/math] we define a [math]\displaystyle{ \nu }[/math]-random subspace to be what you get when you choose [math]\displaystyle{ S_i }[/math] with probability [math]\displaystyle{ \lambda_i. }[/math]
Suppose we have found [math]\displaystyle{ \nu }[/math] with the three properties above, and let [math]\displaystyle{ \mathcal{B} }[/math] be a set of equal-slices density [math]\displaystyle{ \theta. }[/math] Then by hypothesis we have that [math]\displaystyle{ \nu(\mathcal{B})\geq\eta. }[/math] This implies that if [math]\displaystyle{ S_i }[/math] is a [math]\displaystyle{ \nu }[/math]-random subspace, then the probability that [math]\displaystyle{ \sigma_i(\mathcal{B})\geq\eta/2 }[/math] is at least [math]\displaystyle{ \eta/2. }[/math] If we have taken [math]\displaystyle{ \zeta }[/math] to be [math]\displaystyle{ \eta/2, }[/math] then each subspaces [math]\displaystyle{ S_i }[/math] for which [math]\displaystyle{ \sigma_i(\mathcal{B})\geq\eta/2 }[/math] contains a combinatorial line in [math]\displaystyle{ \mathcal{B}. }[/math] Since an M-dimensional subspace contains [math]\displaystyle{ (k+1)^M }[/math] combinatorial lines, this implies that the [math]\displaystyle{ \nu }[/math]-density of the set of all combinatorial lines in [math]\displaystyle{ \mathcal{B} }[/math] is at least [math]\displaystyle{ \eta/2(k+1)^M. }[/math] Hence, by the third property, the equal-slices density of this set of lines is at least [math]\displaystyle{ c(\theta,k,M)\gt 0. }[/math]
It remains to define an appropriate measure [math]\displaystyle{ \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]\displaystyle{ a_1+\dots+a_M=n }[/math] and then randomly partitioning [math]\displaystyle{ [n] }[/math] into wildcard sets [math]\displaystyle{ Z_1,\dots,Z_M }[/math] with [math]\displaystyle{ |Z_i|=a_i. }[/math] Then [math]\displaystyle{ \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]\displaystyle{ \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.
[math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math]
