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

(Started article) |
(→Notation and definitions) |
||

Line 13: | Line 13: | ||

Of particular interest to us will be the sequence | Of particular interest to us will be the sequence | ||

− | <math>(E_1,\dots,E_{k-1}),</math> where <math>E_j=[k-1]\setminus j.</math> | + | <math>(E_1,\dots,E_{k-1}),</math> where <math>E_j=[k-1]\setminus j.</math> What is an <math>(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>U_i(x)</math> with <math>i\leq k-1</math> and <math>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 subset <math>\mathcal{B}</math> of <math>[k-1]^n.</math> We can use <math>\mathcal{B}</math> to define a set <math>\mathcal{A}\subset[k]^n</math> as follows. A sequence x belongs to <math>\mathcal{A}</math> if and only if whenever you change all the ks of x into js, for some j<k, you end up with a sequence in <math>\mathcal{B}.</math> | |

− | <math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math> | + | To see that this is an <math>(E_1,\dots,E_{k-1})</math>-set, it is enough to show that the set of all x such that changing ks to js is an <math>E_j</math>-set. And indeed, whether or not x belongs to that set does depend only on the sets <math>U_i(x)</math> with <math>i\leq k-1</math> and <math>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></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math> | ||

+ | |||

+ | ==Some stuff copied from the DHJ(3) case that I hope to modify== | ||

+ | |||

+ | Let us assume for now that the equal-slices density of <math>\mathcal{A}</math> in <math>[3]^n</math> is at least <math>\delta</math>, and that the equal-slices density of <math>\mathcal{A} \cap [2]^n</math> in <math>[2]^n</math> is at least <math>\theta</math>. As discussed in the sections below, we can reduce to this case by passing to subspaces. | ||

+ | |||

+ | The key definitions are: | ||

+ | |||

+ | <center> <math>\mathcal{U} := \{z \in [3]^n : \mathrm{changing }\ z\mathrm{'s }\ 3\mathrm{'s}\ \mathrm{to }\ 2\mathrm{'s\ puts\ it\ in }\ \mathcal{A}\}</math>, </center> | ||

+ | <center> <math>\mathcal{V} := \{z \in [3]^n : \mathrm{changing }\ z\mathrm{'s }\ 3\mathrm{'s}\ \mathrm{to }\ 1\mathrm{'s\ puts\ it\ in }\ \mathcal{A}\}</math>. </center> | ||

+ | |||

+ | Note that <math>\mathcal{U}</math> is a 1-set and <math>\mathcal{V}</math> is a 2-set. Further, since <math>\mathcal{A}</math> contains no combinatorial line, it must be disjoint from <math>\mathcal{U} \cap \mathcal{V}</math>. We will now see that <math>\mathcal{U} \cap \mathcal{V}</math> is large in equal-slices measure on <math>[3]^n</math>. | ||

+ | |||

+ | To see this, let <math>z</math> be drawn from equal-slices measure on <math>[3]^n</math> in the manner described at the end of the [[Equal-slices measure|article on the topic]]. Note that this also generates <math>x, y \in [2]^n</math>. As we saw in the article, we get that both <math>x, y \in \mathcal{A}</math> with probability at least <math>\eta := \theta^2 - \frac{2}{n+2}</math>, using the fact that <math>\mathcal{A} \cap [2]^n</math> has equal-slices density at least <math>\theta</math> in <math>[2]^n</math>. But when this happens, <math>z \in \mathcal{U} \cap \mathcal{V}</math>, by definition. Hence <math>\mathcal{U} \cap \mathcal{V}</math> has equal-slices density at least <math>\eta</math> on <math>[3]^n</math>. | ||

+ | |||

+ | We now have that <math>\mathcal{A}</math> avoids the set <math>\mathcal{U} \cap \mathcal{V}</math>, which has equal-slices density at least <math>\eta</math>. It is thus easy to conclude that <math>\mathcal{A}</math> must have relative density at least | ||

+ | |||

+ | <center> <math>\frac{\delta}{1 - \eta} \geq \delta(1 + \eta)</math></center> | ||

+ | |||

+ | on one of the three sets <math>\mathcal{U}\cap \mathcal{V}^c</math>, <math>\mathcal{U}^c\cap \mathcal{V}</math>, <math>\mathcal{U}^c \cap \mathcal{V}^c</math>. And each of these is a 12-set with density at least <math>\eta</math>. | ||

+ | |||

+ | We can move from this relative density-increment under equal-slices to a nearly as good one under uniform using the results in the [[passing between measures]] section ("relative density version"). |

## Revision as of 21:59, 9 March 2009

## Introduction

The aim of this page is to generalize the proof that line-free subsets of [math][3]^n[/math] correlate locally with sets of complexity 1 to an analogous statement for line-free subsets of [math][k]^n.[/math]

Until this sentence is removed, there is no guarantee that this aim will be achieved, or even that a plausible sketch will result.

## 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]j\leq k[/math] and a sequence [math]x\in[k]^n,[/math] let [math]U_j(x)[/math] denote the set [math]\{i\in[n]:x_i=j\}.[/math] We call this the *j-set* of x. More generally, if [math]E\subset[k],[/math] let [math]U_E(x)[/math] denote the sequence [math](U_j(x):j\in E).[/math] We call this the *E-sequence* of x. For example, if n=10, k=4, [math]x=3442411123[/math] and [math]E=\{2,3\}[/math] then the E-sequence of x is [math](\{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](49,235).[/math]

An *E-set* is a set [math]\mathcal{A}\subset[k]^n[/math] such that whether or not x belongs to [math]\mathcal{A}[/math] depends only on the E-set of x. In other words, to define an E-set one chooses a collection [math]\mathcal{U}_E[/math] of sequences of the form [math](U_i:i\in E),[/math] where the [math]U_i[/math] are disjoint subsets of [n], and one takes the set of all x such that [math](U_i(x):i\in E)\in\mathcal{U}_E.[/math] More generally, an [math](E_1,\dots,E_r)[/math]-*set* is an intersection of [math]E_h[/math]-sets as h runs from 1 to r.

Of particular interest to us will be the sequence [math](E_1,\dots,E_{k-1}),[/math] where [math]E_j=[k-1]\setminus j.[/math] What is an [math](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]U_i(x)[/math] with [math]i\leq k-1[/math] and [math]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 subset [math]\mathcal{B}[/math] of [math][k-1]^n.[/math] We can use [math]\mathcal{B}[/math] to define a set [math]\mathcal{A}\subset[k]^n[/math] as follows. A sequence x belongs to [math]\mathcal{A}[/math] if and only if whenever you change all the ks of x into js, for some j<k, you end up with a sequence in [math]\mathcal{B}.[/math]

To see that this is an [math](E_1,\dots,E_{k-1})[/math]-set, it is enough to show that the set of all x such that changing ks to js is an [math]E_j[/math]-set. And indeed, whether or not x belongs to that set does depend only on the sets [math]U_i(x)[/math] with [math]i\leq k-1[/math] and [math]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][/math][math][/math][math][/math][math][/math][math][/math][math][/math][math][/math][math][/math][math][/math][math][/math]

## Some stuff copied from the DHJ(3) case that I hope to modify

Let us assume for now that the equal-slices density of [math]\mathcal{A}[/math] in [math][3]^n[/math] is at least [math]\delta[/math], and that the equal-slices density of [math]\mathcal{A} \cap [2]^n[/math] in [math][2]^n[/math] is at least [math]\theta[/math]. As discussed in the sections below, we can reduce to this case by passing to subspaces.

The key definitions are:

Note that [math]\mathcal{U}[/math] is a 1-set and [math]\mathcal{V}[/math] is a 2-set. Further, since [math]\mathcal{A}[/math] contains no combinatorial line, it must be disjoint from [math]\mathcal{U} \cap \mathcal{V}[/math]. We will now see that [math]\mathcal{U} \cap \mathcal{V}[/math] is large in equal-slices measure on [math][3]^n[/math].

To see this, let [math]z[/math] be drawn from equal-slices measure on [math][3]^n[/math] in the manner described at the end of the article on the topic. Note that this also generates [math]x, y \in [2]^n[/math]. As we saw in the article, we get that both [math]x, y \in \mathcal{A}[/math] with probability at least [math]\eta := \theta^2 - \frac{2}{n+2}[/math], using the fact that [math]\mathcal{A} \cap [2]^n[/math] has equal-slices density at least [math]\theta[/math] in [math][2]^n[/math]. But when this happens, [math]z \in \mathcal{U} \cap \mathcal{V}[/math], by definition. Hence [math]\mathcal{U} \cap \mathcal{V}[/math] has equal-slices density at least [math]\eta[/math] on [math][3]^n[/math].

We now have that [math]\mathcal{A}[/math] avoids the set [math]\mathcal{U} \cap \mathcal{V}[/math], which has equal-slices density at least [math]\eta[/math]. It is thus easy to conclude that [math]\mathcal{A}[/math] must have relative density at least

on one of the three sets [math]\mathcal{U}\cap \mathcal{V}^c[/math], [math]\mathcal{U}^c\cap \mathcal{V}[/math], [math]\mathcal{U}^c \cap \mathcal{V}^c[/math]. And each of these is a 12-set with density at least [math]\eta[/math].

We can move from this relative density-increment under equal-slices to a nearly as good one under uniform using the results in the passing between measures section ("relative density version").