# Difference between revisions of "Line-free sets correlate locally with complexity-1 sets"

Line 1: | Line 1: | ||

''Warning: I think I can prove something rigorously, but will not be sure until it is completely written up. The writing up will continue when I have the time to do it.'' | ''Warning: I think I can prove something rigorously, but will not be sure until it is completely written up. The writing up will continue when I have the time to do it.'' | ||

− | The aim of this page is to present a proof that if <math>\mathcal{A}</math> is a dense subset of <math>[3]^n</math> that contains no combinatorial line, then there is a combinatorial subspace X of <math>\mathcal{A}</math> with dimension tending to infinity and a dense subset <math>\mathcal{B}</math> of X [[complexity of a set|of complexity 1]]. For convenience we shall use [[equal-slices measure]] but this is not fundamental to the argument. | + | The aim of this page is to present a proof that if <math>\mathcal{A}</math> is a dense subset of <math>[3]^n</math> that contains no combinatorial line, then there is a combinatorial subspace X of <math>\mathcal{A}</math> with dimension tending to infinity and a dense subset <math>\mathcal{B}</math> of X [[complexity of a set|of complexity 1]]. It is written in a slightly unconventional way, with first a short sketch, then a longer one that fleshes out a few details, and then a longer one still. That way, even while it is incomplete it should be understandable to some extent, and if I get stuck then it will be clearer where the problem lies. |

+ | |||

+ | ==Short sketch of argument== | ||

+ | |||

+ | Throughout this sketch, <math>\mathcal{A}</math> refers to a subset of <math>[3]^n</math> of [[density]] <math>\delta</math> in the uniform distribution on <math>[3]^n.</math> We shall sometimes use letters such as x, y and z for elements of <math>[3]^n</math> and we shall sometimes write them as triples (U,V,W) of sets that partition [n]. A triple of sets corresponds to the 1-set, the 2-set and the 3-set of a sequence. We shall pass freely between the two ways of thinking about <math>[3]^n,</math> at each stage using whichever is more convenient. | ||

+ | |||

+ | If (U,V,W) is an element of <math>[3]^n</math> and (U',V',W') is an arbitrary triple of disjoint sets (not necessarily partitioning [n]), we shall write (U,V,W)++(U',V',W') for the sequence obtained from (U,V,W) by changing everything in U' to 1, everything in V' to 2, and everything in W' to 3. For example, writing § for an unspecified coordinate, we have 331322311++§§§1§22§3=331122213. (We think of (U',V',W') as "overwriting" (U,V,W).) If Z is a subset of [n], we shall also write <math>(U,V,W)++[3]^Z</math> for the combinatorial subspace consisting of all <math>(U,V,W)++(U',V',W')</math> with <math>(U',V',W')\in[3]^Z.</math> | ||

+ | |||

+ | Step 1. If a, b and c are all within <math>C\sqrt n</math> of n/3 and a+b+c=n, and if r, s and t are three integers that add up to 0 and are all at most <math>m=o(\sqrt{n})</math> in modulus, then the size of the [[slice]] <math>\Gamma_{a,b,c}</math> is 1+o(1) times the size of the slice <math>\Gamma_{a+r,b+s,c+t}.</math> | ||

+ | |||

+ | Step 2. If <math>\mu</math> is some probability distribution on combinatorial subspaces of <math>[3]^n</math> such that the distribution of a point x chosen uniformly at random from a subspace chosen randomly according to the distribution <math>\mu</math> is approximately uniform, then we may assume that <math>\mu</math>-almost all subpaces <math>V\subset[3]^n</math> contain at least <math>(\delta-\eta)|V|</math> elements of <math>\mathcal{A}.</math> | ||

+ | |||

+ | Step 3. By an averaging argument, we find (U,V,W) and <math>Z\subset U\cup V</math> with two properties. First, out of all pairs <math>(U',V')\in[2]^Z,</math> the proportion such that <math>(U,V,W)++(U',V',\emptyset)</math> belongs to <math>\mathcal{A}</math> is at least <math>\delta/2.</math> Secondly, out of all triples <math>(U',V',W')\in[3]^Z,</math> the proportion such that <math>(U,V,W)++(U',V',W')</math> belongs to <math>\mathcal{A}</math> is at least <math>\delta-\eta.</math> | ||

+ | |||

+ | Step 4. Fixing such (U,V,W) and Z, let us write (U',V',W') instead of (U,V,W)++(U',V',W'). Then if <math>U_1\subset U_2</math> and <math>(U_1,Z\setminus U_1,\emptyset)</math> and <math>(U_2,Z\setminus U_2,\emptyset)</math> both belong to <math>\mathcal{A},</math> then, writing <math>V_i</math> for <math>Z\setminus U_i,</math> we have that <math>(U_1,V_2,Z\setminus(U_1\cup V_2)</math> does not belong to <math>\mathcal{A}.</math> | ||

+ | |||

+ | Step 5. Let <math>\mathcal{U}</math> be the set of all U such that <math>(U,Z\setminus U,\emptyset)</math> belongs to <math>\mathcal{A},</math> and let <math>\mathcal{V}=\{Z\setminus U:U\in\mathcal{U}\}.</math> Then, in an appropriate sense, the set of all pairs <math>(U_1,V_2)</math> such that <math>U_1\in\mathcal{U}</math> and <math>V_2\in\mathcal{V}</math> is dense. It follows that <math>\mathcal{A}</math> is disjoint from a dense set of complexity 1. | ||

+ | |||

+ | Step 6. We can partition the set of all disjoint pairs <math>(U_1,V_2)</math> according to which of the sets <math>\mathcal{U}\times\mathcal{V},</math> <math>\mathcal{U}\times\mathcal{V}^c,</math> <math>\mathcal{U}^c\times\mathcal{V}</math> or <math>\mathcal{U}^c\times\mathcal{V}^c</math> they belong to. There must be at least one of the three sets other than <math>\mathcal{U}\times\mathcal{V}</math> in which <math>\mathcal{A}</math> has a density increment. Thus, we have a local density increment on a set of complexity 1. | ||

+ | |||

+ | ==Further details== | ||

+ | |||

+ | ===Step 1=== | ||

+ | |||

+ | <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></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math><math></math> | ||

+ | |||

+ | |||

+ | |||

+ | |||

+ | |||

+ | |||

+ | For convenience we shall use [[equal-slices measure]] but this is not fundamental to the argument. | ||

The model of equal-slices measure we use is this. If p, q and r are non-negative real numbers with p+q+r=1, and <math>(X_1,\dots,X_n)</math> are independent random variables with probabilities p, q and r of equalling 1, 2 and 3, respectively, then we define <math>\mu_{p,q,r}(\mathcal{A})</math> to be the probability that <math>(X_1,\dots,X_n)</math> lies in <math>\mathcal{A}.</math> We then define the ''density'' of <math>\mathcal{A}</math> to be the average of <math>\mu_{p,q,r}(\mathcal{A})</math> over all possible triples p,q,r. | The model of equal-slices measure we use is this. If p, q and r are non-negative real numbers with p+q+r=1, and <math>(X_1,\dots,X_n)</math> are independent random variables with probabilities p, q and r of equalling 1, 2 and 3, respectively, then we define <math>\mu_{p,q,r}(\mathcal{A})</math> to be the probability that <math>(X_1,\dots,X_n)</math> lies in <math>\mathcal{A}.</math> We then define the ''density'' of <math>\mathcal{A}</math> to be the average of <math>\mu_{p,q,r}(\mathcal{A})</math> over all possible triples p,q,r. |

## Revision as of 23:02, 24 February 2009

*Warning: I think I can prove something rigorously, but will not be sure until it is completely written up. The writing up will continue when I have the time to do it.*

The aim of this page is to present a proof that if [math]\mathcal{A}[/math] is a dense subset of [math][3]^n[/math] that contains no combinatorial line, then there is a combinatorial subspace X of [math]\mathcal{A}[/math] with dimension tending to infinity and a dense subset [math]\mathcal{B}[/math] of X of complexity 1. It is written in a slightly unconventional way, with first a short sketch, then a longer one that fleshes out a few details, and then a longer one still. That way, even while it is incomplete it should be understandable to some extent, and if I get stuck then it will be clearer where the problem lies.

## Short sketch of argument

Throughout this sketch, [math]\mathcal{A}[/math] refers to a subset of [math][3]^n[/math] of density [math]\delta[/math] in the uniform distribution on [math][3]^n.[/math] We shall sometimes use letters such as x, y and z for elements of [math][3]^n[/math] and we shall sometimes write them as triples (U,V,W) of sets that partition [n]. A triple of sets corresponds to the 1-set, the 2-set and the 3-set of a sequence. We shall pass freely between the two ways of thinking about [math][3]^n,[/math] at each stage using whichever is more convenient.

If (U,V,W) is an element of [math][3]^n[/math] and (U',V',W') is an arbitrary triple of disjoint sets (not necessarily partitioning [n]), we shall write (U,V,W)++(U',V',W') for the sequence obtained from (U,V,W) by changing everything in U' to 1, everything in V' to 2, and everything in W' to 3. For example, writing § for an unspecified coordinate, we have 331322311++§§§1§22§3=331122213. (We think of (U',V',W') as "overwriting" (U,V,W).) If Z is a subset of [n], we shall also write [math](U,V,W)++[3]^Z[/math] for the combinatorial subspace consisting of all [math](U,V,W)++(U',V',W')[/math] with [math](U',V',W')\in[3]^Z.[/math]

Step 1. If a, b and c are all within [math]C\sqrt n[/math] of n/3 and a+b+c=n, and if r, s and t are three integers that add up to 0 and are all at most [math]m=o(\sqrt{n})[/math] in modulus, then the size of the slice [math]\Gamma_{a,b,c}[/math] is 1+o(1) times the size of the slice [math]\Gamma_{a+r,b+s,c+t}.[/math]

Step 2. If [math]\mu[/math] is some probability distribution on combinatorial subspaces of [math][3]^n[/math] such that the distribution of a point x chosen uniformly at random from a subspace chosen randomly according to the distribution [math]\mu[/math] is approximately uniform, then we may assume that [math]\mu[/math]-almost all subpaces [math]V\subset[3]^n[/math] contain at least [math](\delta-\eta)|V|[/math] elements of [math]\mathcal{A}.[/math]

Step 3. By an averaging argument, we find (U,V,W) and [math]Z\subset U\cup V[/math] with two properties. First, out of all pairs [math](U',V')\in[2]^Z,[/math] the proportion such that [math](U,V,W)++(U',V',\emptyset)[/math] belongs to [math]\mathcal{A}[/math] is at least [math]\delta/2.[/math] Secondly, out of all triples [math](U',V',W')\in[3]^Z,[/math] the proportion such that [math](U,V,W)++(U',V',W')[/math] belongs to [math]\mathcal{A}[/math] is at least [math]\delta-\eta.[/math]

Step 4. Fixing such (U,V,W) and Z, let us write (U',V',W') instead of (U,V,W)++(U',V',W'). Then if [math]U_1\subset U_2[/math] and [math](U_1,Z\setminus U_1,\emptyset)[/math] and [math](U_2,Z\setminus U_2,\emptyset)[/math] both belong to [math]\mathcal{A},[/math] then, writing [math]V_i[/math] for [math]Z\setminus U_i,[/math] we have that [math](U_1,V_2,Z\setminus(U_1\cup V_2)[/math] does not belong to [math]\mathcal{A}.[/math]

Step 5. Let [math]\mathcal{U}[/math] be the set of all U such that [math](U,Z\setminus U,\emptyset)[/math] belongs to [math]\mathcal{A},[/math] and let [math]\mathcal{V}=\{Z\setminus U:U\in\mathcal{U}\}.[/math] Then, in an appropriate sense, the set of all pairs [math](U_1,V_2)[/math] such that [math]U_1\in\mathcal{U}[/math] and [math]V_2\in\mathcal{V}[/math] is dense. It follows that [math]\mathcal{A}[/math] is disjoint from a dense set of complexity 1.

Step 6. We can partition the set of all disjoint pairs [math](U_1,V_2)[/math] according to which of the sets [math]\mathcal{U}\times\mathcal{V},[/math] [math]\mathcal{U}\times\mathcal{V}^c,[/math] [math]\mathcal{U}^c\times\mathcal{V}[/math] or [math]\mathcal{U}^c\times\mathcal{V}^c[/math] they belong to. There must be at least one of the three sets other than [math]\mathcal{U}\times\mathcal{V}[/math] in which [math]\mathcal{A}[/math] has a density increment. Thus, we have a local density increment on a set of complexity 1.

## Further details

### Step 1

[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][/math][math][/math][math][/math][math][/math][math][/math][math][/math][math][/math][math][/math][math][/math][math][/math]

For convenience we shall use equal-slices measure but this is not fundamental to the argument.

The model of equal-slices measure we use is this. If p, q and r are non-negative real numbers with p+q+r=1, and [math](X_1,\dots,X_n)[/math] are independent random variables with probabilities p, q and r of equalling 1, 2 and 3, respectively, then we define [math]\mu_{p,q,r}(\mathcal{A})[/math] to be the probability that [math](X_1,\dots,X_n)[/math] lies in [math]\mathcal{A}.[/math] We then define the *density* of [math]\mathcal{A}[/math] to be the average of [math]\mu_{p,q,r}(\mathcal{A})[/math] over all possible triples p,q,r.

Now let us do some averaging. Let us write [math]\delta_{p,q,r}[/math] for [math]\mu_{p,q,r}(\mathcal{A}).[/math] Let us also use the notation (U,V,W) for the [math]x\in[3]^n[/math] that has 1-set U, 2-set V and 3-set W.

First, we prove two similar lemmas that are very simple, but also rather useful.

**Lemma 1.** *The probability distribution of (U,V,W) conditioned on W is the equal-slices measure of (U,V) with ground set [math][n]\setminus W.[/math]*

**Proof.** We are asking for the distribution of the random variable [math](X_1,\dots,X_n)[/math] when we condition on the event that [math]W_i=3[/math] for every [math]i\in W.[/math] Let us condition further on the value of r. Then for each fixed p, q such that p+q=1-r, and each [math]i\notin W,[/math] we have that [math]X_i=1[/math] with probability p/(1-r) and [math]X_i=2[/math] with probability q/(1-r). When we average over p and q, the numbers p/(1-r) and q/(1-r) are uniformly distributed over pairs of positive reals that add up to 1. For each r, we therefore obtain precisely the equal-slices probability distribution on the random variables [math]X_i[/math]with [math]i\notin W,[/math] so the same is true when we average over r.[math]\Box[/math]

It is obviously not the case that the set W in a random triple (U,V,W) is distributed according to equal-slices measure: rather, we choose r with density 2(1-r) and then choose elements of W independently with probability r. When we refer to a random set W or discuss probabilities of events associated with W, it will be this measure that we refer to. (In other words, we take the marginal distribution on W, just as we should.)

To be continued, but possibly not for a while as I have a lot to do in the near future.

[math][/math][math][/math][math][/math]