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

From Polymath Wiki
Revision as of 22:10, 9 March 2009 by Gowers (Talk | contribs)

Jump to: navigation, search

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-sequence 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 set [math]\mathcal{B}\subset[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 i-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

To write this section, I am lifting a section from the equivalent proof for DHJ(3) and making such changes as were necessary.

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:

[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],
[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].

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

[math]\frac{\delta}{1 - \eta} \geq \delta(1 + \eta)[/math]

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").