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

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

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


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]

To be continued.