Difference between revisions of "DHJ(k) implies multidimensional DHJ(k)"

From Polymath1Wiki
Jump to: navigation, search
(To appear soon: Removed section, for now at least)
Line 6: Line 6:
  
 
Let <math>\mathcal{A}</math> be a [[density]]-<math>\delta</math> subset of <math>[k]^n</math> and let M be large enough so that every subset of <math>[k]^M</math> of density at least <math>\theta</math> contains a [[combinatorial line]]. Now split <math>[k]^n</math> up into <math>[k]^M\times[k]^{n-M}.</math> For a proportion at least <math>\delta/2</math> of the points y in <math>[k]^{n-M}</math> the set of <math>x\in[k]^M</math> such that <math>(x,y)\in\mathcal{A}</math> has density at least <math>\delta/2.</math> Therefore, by DHJ(k) (with <math>\theta=\delta/2</math>) we have a combinatorial line. Since there are fewer than <math>(k+1)^M</math> combinatorial lines to choose from, by the pigeonhole principle we can find a combinatorial line <math>L\subset[k]^M</math> and a set <math>\mathcal{A}_1</math> of density <math>\delta/2(k+1)^M</math> in <math>[k]^{n-M}</math> such that <math>(x,y)\in\mathcal{A}</math> whenever <math>x\in L</math> and <math>y\in\mathcal{A}_1.</math> And now by induction we can find an (m-1)-dimensional subspace in <math>\mathcal{A}_1</math> and we're done.
 
Let <math>\mathcal{A}</math> be a [[density]]-<math>\delta</math> subset of <math>[k]^n</math> and let M be large enough so that every subset of <math>[k]^M</math> of density at least <math>\theta</math> contains a [[combinatorial line]]. Now split <math>[k]^n</math> up into <math>[k]^M\times[k]^{n-M}.</math> For a proportion at least <math>\delta/2</math> of the points y in <math>[k]^{n-M}</math> the set of <math>x\in[k]^M</math> such that <math>(x,y)\in\mathcal{A}</math> has density at least <math>\delta/2.</math> Therefore, by DHJ(k) (with <math>\theta=\delta/2</math>) we have a combinatorial line. Since there are fewer than <math>(k+1)^M</math> combinatorial lines to choose from, by the pigeonhole principle we can find a combinatorial line <math>L\subset[k]^M</math> and a set <math>\mathcal{A}_1</math> of density <math>\delta/2(k+1)^M</math> in <math>[k]^{n-M}</math> such that <math>(x,y)\in\mathcal{A}</math> whenever <math>x\in L</math> and <math>y\in\mathcal{A}_1.</math> And now by induction we can find an (m-1)-dimensional subspace in <math>\mathcal{A}_1</math> and we're done.
 +
 +
==A weak multidimensional DHJ(k) implies DHJ(k)==
 +
 +
It is also true that a weak multidimensional DHJ(k) implies DHJ(k). We will show that the following statement is equivalent to DHJ(k):
 +
 +
“There is a constant, c < 1 that for every d there is an n that any c-dense subset of <math> [k]^n</math>  contains a d-dimensional subspace.”
 +
 +
We should show that the statement above implies DHJ(k). As before, write <math> [k]^n</math>  as <math> [k]^r\times[k]^s </math> , where s is much bigger than r. For each <math> y\in [k]^s</math> , define <math> \mathcal{A}_y</math>  to be <math> \{x\in[k]^r:(x,y)\in\mathcal{A}\}</math> . Let Y denote the set of <math> y\in [k]^s</math> , that \mathcal{A}_y</math>  is empty. Suppose that <math> \mathcal{A} </math>  is large, line-free, and its density is <math> \delta =\Delta-\epsilon</math>  where <math> \Delta</math>  is the limit of density of line-free sets and <math> \epsilon < (1-c)\Delta</math> . We can also suppose that no <math> \mathcal{A}_y</math>  has density much larger than <math> \Delta</math>  as that would guarantee a combinatorial line. But then the density of Y is at most 1-c, so there is a c-dense set, <math> Z=[k]^s-Y</math>,  such that any element is a tail of some elements of <math> \mathcal{A}</math> . For every <math> y \in Z</math>  choose an <math> x\in [k]^r:(x,y)\in\mathcal{A}</math> . This x will be the colour of y. It gives a <math> [k]^r</math>  colouring on Z. By the initial condition Z contains arbitrary large subspaces, so by HJ(k) we get a line in <math> \mathcal{A}</math> .

Revision as of 08:36, 15 March 2009

Introduction

This is a result that will be needed if the proof of DHJ(3) is correct and we want to push it through for DHJ(k).

The proof

Let [math]\mathcal{A}[/math] be a density-[math]\delta[/math] subset of [math][k]^n[/math] and let M be large enough so that every subset of [math][k]^M[/math] of density at least [math]\theta[/math] contains a combinatorial line. Now split [math][k]^n[/math] up into [math][k]^M\times[k]^{n-M}.[/math] For a proportion at least [math]\delta/2[/math] of the points y in [math][k]^{n-M}[/math] the set of [math]x\in[k]^M[/math] such that [math](x,y)\in\mathcal{A}[/math] has density at least [math]\delta/2.[/math] Therefore, by DHJ(k) (with [math]\theta=\delta/2[/math]) we have a combinatorial line. Since there are fewer than [math](k+1)^M[/math] combinatorial lines to choose from, by the pigeonhole principle we can find a combinatorial line [math]L\subset[k]^M[/math] and a set [math]\mathcal{A}_1[/math] of density [math]\delta/2(k+1)^M[/math] in [math][k]^{n-M}[/math] such that [math](x,y)\in\mathcal{A}[/math] whenever [math]x\in L[/math] and [math]y\in\mathcal{A}_1.[/math] And now by induction we can find an (m-1)-dimensional subspace in [math]\mathcal{A}_1[/math] and we're done.

A weak multidimensional DHJ(k) implies DHJ(k)

It is also true that a weak multidimensional DHJ(k) implies DHJ(k). We will show that the following statement is equivalent to DHJ(k):

“There is a constant, c < 1 that for every d there is an n that any c-dense subset of [math] [k]^n[/math] contains a d-dimensional subspace.”

We should show that the statement above implies DHJ(k). As before, write [math] [k]^n[/math] as [math] [k]^r\times[k]^s [/math] , where s is much bigger than r. For each [math] y\in [k]^s[/math] , define [math] \mathcal{A}_y[/math] to be [math] \{x\in[k]^r:(x,y)\in\mathcal{A}\}[/math] . Let Y denote the set of [math] y\in [k]^s[/math] , that \mathcal{A}_y</math> is empty. Suppose that [math] \mathcal{A} [/math] is large, line-free, and its density is [math] \delta =\Delta-\epsilon[/math] where [math] \Delta[/math] is the limit of density of line-free sets and [math] \epsilon \lt (1-c)\Delta[/math] . We can also suppose that no [math] \mathcal{A}_y[/math] has density much larger than [math] \Delta[/math] as that would guarantee a combinatorial line. But then the density of Y is at most 1-c, so there is a c-dense set, [math] Z=[k]^s-Y[/math], such that any element is a tail of some elements of [math] \mathcal{A}[/math] . For every [math] y \in Z[/math] choose an [math] x\in [k]^r:(x,y)\in\mathcal{A}[/math] . This x will be the colour of y. It gives a [math] [k]^r[/math] colouring on Z. By the initial condition Z contains arbitrary large subspaces, so by HJ(k) we get a line in [math] \mathcal{A}[/math] .