Polymath Wiki - User contributions [en]

Main Page

2009-03-10T09:46:44Z

128.232.245.25: Undo revision 766 by 213.163.65.65 (Talk)

== The Problem ==

The basic problem to be considered by the Polymath1 project is to explore a particular [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-density-hales-jewett/ combinatorial approach] to the [[density Hales-Jewett theorem]] for k=3 (DHJ(3)), suggested by Tim Gowers. The [[Furstenberg-Katznelson argument|original proof of DHJ(3) used arguments from ergodic theory]].

==Basic definitions==

*[[line|Algebraic line]]

*[[line|Combinatorial line]]

*[[Combinatorial subspace]]

*[[corners|Corner]]

*[[Density]]

*[[line|Geometric line]]

*[[Slice]]

== Useful background materials ==

Here is [http://gowers.wordpress.com/2009/01/30/background-to-a-polymath-project/ some background to the project.] There is also a [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ general discussion on massively collaborative "polymath" projects.] This is [http://meta.wikimedia.org/wiki/File:MediaWikiRefCard.png a cheatsheet for editing the wiki.] Finally, here is the general [http://meta.wikimedia.org/wiki/Help:Contents Wiki user's guide].

== Threads and further problems==

* (1-199) [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-density-hales-jewett/ A combinatorial approach to density Hales-Jewett] (inactive)
* (200-299) [http://terrytao.wordpress.com/2009/02/05/upper-and-lower-bounds-for-the-density-hales-jewett-problem/ Upper and lower bounds for the density Hales-Jewett problem] (inactive)
* (300-399) [http://gowers.wordpress.com/2009/02/06/dhj-the-triangle-removal-approach/ The triangle-removal approach] (inactive)
* (400-499) [http://gowers.wordpress.com/2009/02/08/dhj-quasirandomness-and-obstructions-to-uniformity Quasirandomness and obstructions to uniformity] (inactive)
* (500-599) [http://gowers.wordpress.com/2009/02/13/dhj-possible-proof-strategies/#more-441/ Possible proof strategies] (inactive)
* (600-699) [http://terrytao.wordpress.com/2009/02/11/a-reading-seminar-on-density-hales-jewett/ A reading seminar on density Hales-Jewett] (inactive)
* (700-799) [http://terrytao.wordpress.com/2009/02/13/bounds-for-the-first-few-density-hales-jewett-numbers-and-related-quantities/ Bounds for the first few density Hales-Jewett numbers, and related quantities] (inactive)
* (800-849) [http://gowers.wordpress.com/2009/02/23/brief-review-of-polymath1/ Brief review of polymath1] (inactive)
* (850-899) [http://gowers.wordpress.com/2009/03/02/dhj3-851-899/ DHJ(3): 851-899] (inactive)
* (900-999) [http://terrytao.wordpress.com/2009/03/04/dhj3-900-999-density-hales-jewett-type-numbers/ DHJ(3): 900-999 (Density Hales-Jewett type numbers)] (active)
* (1000-1049) [http://gowers.wordpress.com/2009/03/10/problem-solved-probably/ Problem solved (probably)] (active)

[http://blogsearch.google.com/blogsearch?hl=en&ie=UTF-8&q=polymath1&btnG=Search+Blogs Here is a further list of blog posts related to the Polymath1 project]. [http://en.wordpress.com/tag/polymath1/ Here is wordpress's list]. Here is a [[timeline]] of progress so far.

A spreadsheet containing the latest upper and lower bounds for <math>c_n</math> can be found [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg here]. Here are the proofs of our [[upper and lower bounds]] for these constants.

We are also collecting bounds for [[Fujimura's problem]], motivated by a [[hyper-optimistic conjecture]].

There is also a chance that we will be able to improve the known bounds on [[Moser's cube problem]].

Here are some [[unsolved problems]] arising from the above threads.

Here is a [[tidy problem page]].

== Proof strategies ==

It is natural to look for strategies based on one of the following:

* [[Szemerédi's original proof of Szemerédi's theorem]].
* [[Szemerédi's combinatorial proof of Roth's theorem]].
* [[Ajtai-Szemerédi's proof of the corners theorem]].
* The [[density increment method]].
* The [[triangle removal lemma]].
* [[Ergodic-inspired methods]].
* The [[Furstenberg-Katznelson argument]].
* Use of [[equal-slices measure]].

== Related theorems ==

* [[Carlson's theorem]].
* The [[Carlson-Simpson theorem]].
* [[Folkman's theorem]].
* The [[Graham-Rothschild theorem]].
* The colouring [[Hales-Jewett theorem]].
* The [[Kruskal-Katona theorem]].
* [[Roth's theorem]].
* The [[IP-Szemerédi theorem]].
* [[Sperner's theorem]].
* [[Szemerédi's regularity lemma]].
* [[Szemerédi's theorem]].
* The [[triangle removal lemma]].

All these theorems are worth knowing. The most immediately relevant are Roth's theorem, Sperner's theorem, Szemerédi's regularity lemma and the triangle removal lemma, but some of the others could well come into play as well.

==Important concepts related to possible proofs==

* [[Complexity of a set]]
* [[Concentration of measure]]
* [[Influence of variables]]
* [[Obstructions to uniformity]]
* [[Quasirandomness]]

==Complete proofs or detailed sketches of potentially useful results==

*[[Sperner's theorem|The multidimensional Sperner theorem]]
*[[Line-free sets correlate locally with complexity-1 sets]]
*[[Correlation with a 1-set implies correlation with a subspace]] (Superseded)
*[[Fourier-analytic_proof_of_Sperner|A Fourier-analytic proof of Sperner's theorem]]
*[[A second Fourier decomposition related to Sperner's theorem]]
*[[A Hilbert space lemma]]
*A [[Modification of the Ajtai-Szemerédi argument]]

==Attempts at proofs of DHJ(3)==

*[[An outline of a density-increment argument]] (ultimately didn't work)
*[[A second outline of a density-increment argument]] (seems to be OK but more checking needed)

==Generalizing to DHJ(k)==

*[[DHJ(k) implies multidimensional DHJ(k)]]
*[[Line free sets correlate locally with dense sets of complexity k-2]]

== Bibliography ==

[[Density Hales-Jewett]]

# H. Furstenberg, Y. Katznelson, “[http://math.stanford.edu/~katznel/hj43.pdf A density version of the Hales-Jewett theorem for k=3]“, Graph Theory and Combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 227–241.
# H. Furstenberg, Y. Katznelson, “[http://math.stanford.edu/~katznel/dhj12.pdf A density version of the Hales-Jewett theorem]“, J. Anal. Math. 57 (1991), 64–119.
# R. McCutcheon, “[http://www.msci.memphis.edu/~randall/preprints/HJk3.pdf The conclusion of the proof of the density Hales-Jewett theorem for k=3]“, unpublished.

[[Coloring Hales-Jewett theorem]]

# A. Hales, R. Jewett, [http://www.jstor.org/stable/1993764 Regularity and positional games], Trans. Amer. Math. Soc. 106 1963 222--229. [http://www.ams.org/mathscinet-getitem?mr=143712 MR143712]
# N. Hindman, E. Tressler, "[http://www.math.ucsd.edu/~etressle/hj32.pdf The first non-trivial Hales-Jewett number is four]", preprint.
# P. Matet, "[http://dx.doi.org/10.1016/j.ejc.2006.06.021 Shelah's proof of the Hales-Jewett theorem revisited]", European J. Combin. 28 (2007), no. 6, 1742--1745. [http://www.ams.org/mathscinet-getitem?mr=2339499 MR2339499]
# S. Shelah, "[http://www.jstor.org/stable/1990952 Primitive recursive bounds for van der Waerden numbers]", J. Amer. Math. Soc. 1 (1988), no. 3, 683--697. [http://www.ams.org/mathscinet-getitem?mr=929498 MR 929498]

[[Roth's theorem]]

# E. Croot, "[http://www.math.gatech.edu/~ecroot/szemeredi.pdf Szemeredi's theorem on three-term progressions, at a glance], preprint.

Behrend-type constructions

# M. Elkin, "[http://arxiv.org/abs/0801.4310 An Improved Construction of Progression-Free Sets ]", preprint.
# B. Green, J. Wolf, "[http://arxiv.org/abs/0810.0732 A note on Elkin's improvement of Behrend's construction]", preprint.
# K. O'Bryant, "[http://arxiv.org/abs/0811.3057 Sets of integers that do not contain long arithmetic progressions]", preprint.

Triangles and corners

# M. Ajtai, E. Szemerédi, Sets of lattice points that form no squares, Stud. Sci. Math. Hungar. 9 (1974), 9--11 (1975). [http://www.ams.org/mathscinet-getitem?mr=369299 MR369299]
# I. Ruzsa, E. Szemerédi, Triple systems with no six points carrying three triangles. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, pp. 939--945, Colloq. Math. Soc. János Bolyai, 18, North-Holland, Amsterdam-New York, 1978. [http://www.ams.org/mathscinet-getitem?mr=519318 MR519318]
# J. Solymosi, [http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=206943 A note on a question of Erdős and Graham], Combin. Probab. Comput. 13 (2004), no. 2, 263--267. [http://www.ams.org/mathscinet-getitem?mr=2047239 MR 2047239]

[[Kruskal-Katona theorem]]

# P. Keevash, "[http://arxiv.org/abs/0806.2023 Shadows and intersections: stability and new proofs]", preprint.

An outline of a density-increment argument

2009-03-05T12:36:43Z

128.232.245.25: /* Notation and definitions */

==Introduction==

One of the proof strategies we have considered seriously is [[Density_increment_method|the density-increment method]]. The idea here is to prove that if <math>\mathcal{A}</math> is a subset of <math>[3]^n</math> of [[density]] <math>\delta</math> with no [[combinatorial line]] then there is a [[combinatorial subspace]] S of dimension tending to infinity with n such that the density of <math>\mathcal{A}</math> inside S is larger than <math>\delta</math> by an amount that depends on <math>\delta</math> only. If we can prove such a result, then we can drop down to S and repeat the argument. If the initial dimension n is large enough, then we push the density up to 1 before we run out of dimensions, and thereby obtain a contradiction.

==Notation and definitions==

Let x be an element of <math>[3]^n.</math> Write <math>U(x),V(x)</math> and <math>W(x)</math> for the sets of i such that <math>x_i=1,2</math> and 3, respectively. These are called the ''1-set'', the ''2-set'' and the ''3-set'' of x. The map <math>x\mapsto(U(x),V(x),W(x))</math> is a one-to-one correspondence between <math>[3]^n</math> and the set of all triples <math>(U,V,W)</math> of sets that partition <math>[n].</math> We shall use the notation x and also the notation <math>(U,V,W)</math> and will pass rapidly between them.

Let <math>\mathcal{U}</math> and <math>\mathcal{V}</math> be collections of subsets of <math>[n].</math> We shall write <math>\mathcal{U}\otimes\mathcal{V}</math> for the collection of all sequences <math>x</math> such that <math>U(x)\in\mathcal{U}</math> and <math>V(x)\in\mathcal{V}.</math> A set of the form <math>\mathcal{U}\otimes\mathcal{V}</math> will be called a ''12-set''.

In general, if X is a finite set and A and B are subsets of X, we define ''the density of'' A ''in'' B to be <math>|A\cap B|/|B|.</math>

==A very broad overview of the argument==

One of the main features of the argument is that it is ''local'' in character. In other words, it does not try to understand fully the [[obstructions to uniformity]] that cause a set to fail to have the expected number of combinatorial lines. Instead, we are content to find non-quasirandom behaviour inside small subspaces of <math>[3]^n.</math> This happens right from the start. A conjecture that one might hope to be true is that if a set <math>\mathcal{A}</math> is line-free, then there is a dense 12-set <math>\mathcal{U}\otimes\mathcal{V}</math> such that the density of <math>\mathcal{A}</math> inside <math>\mathcal{U}\otimes\mathcal{V}</math> is a bit larger than the density of <math>\mathcal{A}</math> in <math>[3]^n.</math> However, this is not in fact our first step. Instead, we argue that this kind of correlation happens when one restricts to an appropriate subspace. This part of the argument is [[Line-free_sets_correlate_locally_with_complexity-1_sets|given in some detail on a different page]], (where what we are calling 12-sets are called special sets of complexity 1).

Once we have correlation with a 12-set (even if we have had to pass to a subspace to get it) it is natural to try to prove that a 12-set can be partitioned into combinatorial subspaces, since then by averaging we could show that <math>\mathcal{A}</math> correlated with one of those subspaces, and we would be done. An argument similar to [[Sperner's_theorem|the proof of the multidimensional Sperner theorem]] can be used to prove that a dense 12-set contains many combinatorial subspaces. However, it is not at all obvious that one can partition the 12-set into such subspaces (even if small errors are allowed).

However, a different principle comes to the rescue. It is the observation that there are ''two'' kinds of density increment that will be good enough for us. One is a density increment on a subspace, as we already know. The other is a density increment on a 12-set (obtained after passing to a subspace if necessary). Let us spell this out in more detail. Suppose that <math>\mathcal{A}</math> is a line-free set of density <math>\delta</math> and we want to obtain a contradiction. We know two things. First, we can find a 12-subset of a subspace in which <math>\mathcal{A}</math> has increased density <math>\delta+\eta</math>, and secondly, if we can ever prove that there is increased density <math>\delta+\eta/2</math> (say) on a subspace then we are done. However, we can add a third principle, which is that if we can find a 12-subset of a subspace on which the density goes up from <math>\delta+\eta</math> then we are again done. Why? Because we are in the same position as we were in before, but with a slightly higher density, so we can iterate.

To be continued.

<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>

An outline of a density-increment argument

2009-03-05T12:33:38Z

128.232.245.25: /* Introduction */

==Introduction==

One of the proof strategies we have considered seriously is [[Density_increment_method|the density-increment method]]. The idea here is to prove that if <math>\mathcal{A}</math> is a subset of <math>[3]^n</math> of [[density]] <math>\delta</math> with no [[combinatorial line]] then there is a [[combinatorial subspace]] S of dimension tending to infinity with n such that the density of <math>\mathcal{A}</math> inside S is larger than <math>\delta</math> by an amount that depends on <math>\delta</math> only. If we can prove such a result, then we can drop down to S and repeat the argument. If the initial dimension n is large enough, then we push the density up to 1 before we run out of dimensions, and thereby obtain a contradiction.

==Notation and definitions==

Let x be an element of <math>[3]^n.</math> Write <math>U(x),V(x)</math> and <math>W(x)</math> for the sets of i such that <math>x_i=1,2</math> and 3, respectively. These are called the ''1-set'', the ''2-set'' and the ''3-set'' of x. The map <math>x\mapsto(U(x),V(x),W(x))</math> is a one-to-one correspondence between <math>[3]^n</math> and the set of all triples <math>(U,V,W)</math> of sets that partition <math>[n].</math> We shall use the notation x and also the notation <math>(U,V,W)</math> and will pass rapidly between them.

Let <math>\mathcal{U}</math> and <math>\mathcal{V}</math> be collections of subsets of <math>[n].</math> We shall write <math>mathcal{U}\otimes\mathcal{V}</math> for the collection of all sequences <math>x</math> such that <math>U(x)\in\mathcal{U}</math> and <math>V(x)\in\mathcal{V}.</math> A set of the form <math>\mathcal{U}\otimes\mathcal{V}</math> will be called a ''12-set''.

In general, if X is a finite set and A and B are subsets of X, we define ''the density of'' A ''in'' B to be <math>|A\cap B|/|B|.</math>

==A very broad overview of the argument==

One of the main features of the argument is that it is ''local'' in character. In other words, it does not try to understand fully the [[obstructions to uniformity]] that cause a set to fail to have the expected number of combinatorial lines. Instead, we are content to find non-quasirandom behaviour inside small subspaces of <math>[3]^n.</math> This happens right from the start. A conjecture that one might hope to be true is that if a set <math>\mathcal{A}</math> is line-free, then there is a dense 12-set <math>\mathcal{U}\otimes\mathcal{V}</math> such that the density of <math>\mathcal{A}</math> inside <math>\mathcal{U}\otimes\mathcal{V}</math> is a bit larger than the density of <math>\mathcal{A}</math> in <math>[3]^n.</math> However, this is not in fact our first step. Instead, we argue that this kind of correlation happens when one restricts to an appropriate subspace. This part of the argument is [[Line-free_sets_correlate_locally_with_complexity-1_sets|given in some detail on a different page]], (where what we are calling 12-sets are called special sets of complexity 1).

Once we have correlation with a 12-set (even if we have had to pass to a subspace to get it) it is natural to try to prove that a 12-set can be partitioned into combinatorial subspaces, since then by averaging we could show that <math>\mathcal{A}</math> correlated with one of those subspaces, and we would be done. An argument similar to [[Sperner's_theorem|the proof of the multidimensional Sperner theorem]] can be used to prove that a dense 12-set contains many combinatorial subspaces. However, it is not at all obvious that one can partition the 12-set into such subspaces (even if small errors are allowed).

However, a different principle comes to the rescue. It is the observation that there are ''two'' kinds of density increment that will be good enough for us. One is a density increment on a subspace, as we already know. The other is a density increment on a 12-set (obtained after passing to a subspace if necessary). Let us spell this out in more detail. Suppose that <math>\mathcal{A}</math> is a line-free set of density <math>\delta</math> and we want to obtain a contradiction. We know two things. First, we can find a 12-subset of a subspace in which <math>\mathcal{A}</math> has increased density <math>\delta+\eta</math>, and secondly, if we can ever prove that there is increased density <math>\delta+\eta/2</math> (say) on a subspace then we are done. However, we can add a third principle, which is that if we can find a 12-subset of a subspace on which the density goes up from <math>\delta+\eta</math> then we are again done. Why? Because we are in the same position as we were in before, but with a slightly higher density, so we can iterate.

To be continued.

<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>

Ajtai-Szemerédi's proof of the corners theorem

2009-03-02T16:05:36Z

128.232.245.25: /* Introduction */

==Introduction==

Ajtai and Szemerédi proved the [[corners theorem]] with a clever use of three basic principles: the [[density-increment_methods|density-increment strategy]], which allowed them to assume that the set A was of density almost <math>\delta</math> in almost all subgrids; averaging arguments, which implied that any dense structured set in which A was sparse must be compensated for by a structured set in which it was of increased density; and [[Szemerédi's theorem]], which allowed them to pass from dense subsets of [n] to long arithmetic progressions. Their original paper does not seem to be available online, but here you can find [http://www.math.rutgers.edu/~vanvu/papers/numbertheory/gower.pdf a quantitative version of their argument] due to Van Vu. On this page, we give a detailed sketch of the argument: the aim is to present the key ideas in enough detail that the reader who wishes to can go away and make it fully precise.

==Statement of the theorem and some basic definitions==

For every <math>\delta>0</math> there exists n such that every subset <math>A\subset [n]^2</math> of density at least <math>\delta</math> (i.e., of cardinality at least <math>\delta n^2</math>) contains three points of the form (x,y), (x+d,y) and (x,y+d) with <math>d>0.</math>

'''Definitions.''' A ''grid of side'' m is a Cartesian product <math>P\times Q,</math> where P and Q are arithmetic progressions of length m with the same common difference. A ''vertical line'' is a subset of <math>[n]^2</math> of the form <math>VL_x=\{(x,y):y\in[n]\},</math> and a ''horizontal line'' is a subset of the form <math>HL_y=\{(x,y):x\in[n]\}.</math>

==First step: A is dense on almost all grids==

This is a very standard move in density-increment arguments. We are trying to do an iteration in which we pass to a subgrid where A has increased density. Suppose we aim for a density increase from <math>\delta</math> to <math>\delta+\eta.</math> Then if we find a subgrid (of width tending to infinity with n) where the density is at least <math>\delta+\eta</math> then we have our density increase, obviously enough. But if we do ''not'' have such a subgrid, then we can argue as follows. Pick a random point in <math>[n]^2</math> by first picking a random grid of width m, and then picking a random point in that grid. If m is small enough, then it is easy to argue that the distribution of the resulting point is approximately uniform, from which it follows that the average density in a random subgrid is approximately <math>\delta.</math> But if the average density in a subgrid is approximately <math>\delta</math> and the maximum density is at most <math>\delta+\eta,</math> then there can be only a small proportion of subgrids inside which A has density substantially smaller than <math>\delta.</math> (Roughly, the proportion where the density is less than <math>\delta-\mu</math> is at most <math>\eta/\mu,</math> by a simple averaging argument).

==Second step: find a large set of "full" vertical lines==

We shall now prove that almost all vertical lines have density close to <math>\delta.</math> (What does this mean? It means that the number of points of A inside the line is at least <math>\delta n.</math> Of course, this is really saying that A is dense in the line, and not that the line is dense, but it is such a convenient way of talking that we shall adopt it from now on.) First, we observe that if some positive proportion <math>\mu</math> of vertical lines have density at most <math>\delta-\eta,</math> then the average density in the remaining vertical lines is at least <math>\delta+\mu\eta,</math> so there must be at least <math>\mu\eta n/2</math> vertical lines with density at least <math>\delta+\mu\eta/2.</math> So if a positive proportion of lines have density substantially ''different'' from <math>\delta,</math> then we know that a positive proportion of vertical lines have density that is substantially ''larger'' than <math>\delta.</math> (Here, the word "substantially" means that the difference is a constant that depends on <math>\delta</math> and not on n.)

If that is the case, then we can apply [[Szemerédi's theorem]] to obtain an arithmetic progression P of length m (which tends to infinity as n does) such that for every <math>x\in P</math> the vertical line <math>VL_x</math> has density substantially larger than <math>\delta.</math> Furthermore, we can choose P so that the common difference is small compared with n.

This last condition is useful because it enables us to partition almost all of [n] into translates <math>Q_i</math> of P. And then the average density of the grids <math>P\times Q_i</math> is substantially larger than <math>\delta.</math> Therefore, there must be a density increase on some subgrid and we are done, unless all but at most <math>\eta n</math> vertical lines have density at least <math>\delta-\eta,</math> for some positive <math>\eta</math> that we can make as small as we like.

==Third step: find a dense diagonal==

Since there are at most 2n possible values of x+y when <math>(x,y)\in[n]^2,</math> there must exist z such that for at least <math>\delta n/2</math> pairs <math>(x,y)\in A</math> we have <math>x+y=z.</math> Assuming we have ensured that
<math>\eta<\delta/4,</math> this gives us at least <math>\delta n/4</math> points <math>(x,y)\in A</math> such that <math>x+y=z</math> ''and'' the vertical line <math>VL_x</math> has density at least <math>\delta-\eta.</math>

==Fourth step: find a long arithmetic progression of good points in that diagonal==

Pick a diagonal as given by Step 3. Amongst the first <math>\delta n/8</math> points on that diagonal (counting from the top left) there must be an arithmetic progression of points of length m tending to infinity and small common difference (much smaller than <math>\sqrt{n},</math> say). That is, we can find an arithmetic progression P of length m and common difference d such that for every <math>x\in P</math> the point (x,z-x) belongs to A, and the vertical line <math>VL_x</math> has density at least <math>\delta-\eta.</math>

==Fifth step: find a subgrid with several empty horizontal lines==

Now let us partition almost all of [n] into translates <math>Q_1,\dots,Q_s</math> of P (which is easy to do since the common difference is small). On almost all the grids <math>P\times Q_i</math> the density of A is almost <math>\delta,</math> since otherwise there would have to be some grids with increased density. Also, the average density in <math>Q_i</math> of numbers y such that (z-y,y) belongs to A and is not one of the first <math>\delta n/8</math> such points is at least <math>\delta/8.</math> If <math>x\in P</math> and y is such a number, then (x,y) cannot belong to A, since otherwise the three points (x,y), (x,z-x) and (z-y,y) would form a corner in A, and we are assuming that A is corner free. (Remark: z-y is greater than x because the point (z-y,y) is further down the diagonal than the point (x,z-x).) Therefore, we can find some <math>Q_i</math> such that the density of A in <math>P\times Q_i</math> is almost as large as <math>\delta</math> ''and'' several horizontal lines inside <math>P\times Q_i</math> are empty.

==Conclusion==

And now we are done by the second step: we have a dense grid with some sparse (in fact, empty) lines, so it has several lines of increased density, and the argument of Step 2 leads to a density increase on a further subgrid (after another application of Szemerédi's theorem).

==An old blog comment that used to be the main article==

Ajtai and Szemerédi found a clever proof of the corners theorem that used Szemerédi’s theorem as a lemma. This gives us a direction to explore that we have hardly touched on. Very roughly, to prove the corners theorem you first use an averaging argument to find a dense diagonal (that is, subset of the form x+y=r that contains many points of your set A). For any two such points (x,r-x) and (y,r-y) you know that the point (x,r-y) does not lie in A (if A is corner free), which gives you some kind of non-quasirandomness. (The Cartesian semi-product arguments discussed in the 400s thread are very similar to this observation.) Indeed, it allows you to find a large Cartesian product <math>X\times Y</math> in which A is a bit too dense. In order to exploit this, Ajtai and Szemerédi used Szemerédi’s theorem to find long arithmetic progressions <math>P\subset X</math> and <math>Q\subset Y</math> of the same common difference such that A has a density increment in <math>P\times Q</math>. (I may have misremembered, but I think this must have been roughly what they did.) So we could think about what the analogue would be in the DHJ setting. Presumably it would be some kind of multidimensional Sperner statement of sufficient depth to imply Szemerédi’s theorem. A naive suggestion would be that in a dense subset of <math>[2]^n</math> you can find a large-dimensional combinatorial subspace in which all the variable sets have the same size. If you apply this to a union of layers, then you find an arithmetic progression of layer-cardinalities. But this feels rather artificial, so here’s a question we could think about.

Question 1. Can anyone think what the right common generalization of Szemerédi’s theorem and Sperner’s theorem ought to be? (Sperner’s theorem itself would correspond to the case of progressions of length 2.)

A second Fourier decomposition related to Sperner's theorem

2009-02-27T15:24:00Z

128.232.245.25: /* A Fourier translation of the problem */

==Introduction==

It seems as though it should be possible to give a clean "purely Fourier" proof of Sperner's theorem that exploits positivity, if one uses [[equal-slices measure]]. Here we present a Fourier decomposition that should achieve this, but we have not yet managed to prove the positivity (which could turn out to be a hard problem---at this stage it is not clear).

We use Ryan's formulation of equal-slices measure on <math>[2]^n</math>: the density of a set <math>\mathcal{A}</math> is <math>\mathbb{E}_p\mu_p(\mathcal{A}),</math> where <math>\mu_p</math> is the standard p-weighted measure on the cube: if A is a subset of [n] then <math>\mu_p(A)=p^{|A|}(1-p)^{n-|A|}.</math> A useful way of thinking about <math>\mu_p</math> is that <math>\mu_p(\mathcal{A}</math> is the probability that <math>(X_1,\dots,X_n)\in\mathcal{A}</math> if the <math>X_i</math> are independent Bernoulli random variables with probability p of equalling 1.

We also need to define a measure on the space of all [[combinatorial_line|combinatorial lines]]. The natural measure seems to be this. Define two sequences <math>(X_1,\dots,X_n)</math> and <math>(Y_1,\dots,Y_n)</math> of Bernoulli random variables as follows. The joint distribution of <math>(X_i,Y_i)</math> is that it equals (0,0),(0,1) and (1,1) with probabilities 1-q,q-p and p, respectively, and let different pairs
<math>(X_i,Y_i)</math> be independent. Then the <math>X_i</math> are independent Bernoulli, as are the <math>Y_i,</math> but they depend on each other in a way that guarantees that they form a combinatorial line.

We shall now be interested in the quantity <math>\mathbb{E}f(X)f(Y),</math> where <math>f</math> is some function and <math>X=(X_1,\dots,X_n), Y=(Y_1,\dots,Y_n).</math> But ultimately what will interest us is the average of this quantity over all pairs <math>0\leq p\leq q\leq 1,</math> which we can write as <math>\mathbb{E}_{p\leq q}\mathbb{E}f(X_{p,q})f(Y_{p,q}).</math>

==A proof in physical space==

Let us first prove positivity in physical space. To do this, we shall define the following equivalent model for the joint distribution of <math>X_{p,q}</math> and <math>Y_{p,q}.</math> We first pick a random variable <math>T=(t_1,\dots,t_n)</math> uniformly from <math>[0,1]^n,</math> and then we let <math>(X_{p,q})_i</math> be <math>0</math> if <math>p\leq t_i</math> and <math>1</math> if <math>p>t_i.</math> Similarly, we let <math>Y_{p,q}</math> be 0 if <math>q\leq t_i</math> and 1 if <math>q>t_i.</math> This gives us the nice property that it makes perfectly good sense even if <math>p>q,</math> and we therefore have the equation <math>\mathbb{E}_{p\leq q}\mathbb{E}f(X_{p,q})f(Y_{p,q})=(1/2)\mathbb{E}_{t\in T}\mathbb{E}_{p,q}f(X_{p,q})f(Y_{p,q}).</math>

Now <math>X_{p,q}</math> is just a function of p and t, and <math>Y_{p,q}</math> is the same function applied to q and t. Therefore, the right-hand side is equal to <math>\mathbb{E}_{t\in T}(\mathbb{E}_pf(X_{p,q}))^2,</math> which is positive.

We can say more. By Cauchy-Schwarz, the expectation is at least <math>(\mathbb{E}_{t\in T}\mathbb{E}_pf(X_{p,q}))^2,</math> which is the square of the equal-slices integral of f. In particular, if f is the characteristic function of a set <math>\mathcal{A},</math> then the combinatorial-line density is at least the square of the density of <math>\mathcal{A}.</math>

==A Fourier translation of the problem==

Recall that the [http://en.wikipedia.org/wiki/Walsh_function Walsh functions] on the set <math>[2]^n</math> are defined as follows. For each subset <math>A\subset[n]</math> we define <math>w_A(B)</math> to be <math>(-1)^{|A\cap B|}.</math> They can also be conveniently defined in sequence terms: for each A and each <math>x\in\{0,1\}^n</math> we define <math>w_A(x)=\prod_{i\in A}(-1)^{x_i}.</math>

It can easily be checked that the Walsh functions form an orthonormal basis of the <math>2^n</math>-dimensional Euclidean space of all functions from <math>\{0,1\}^n</math> to <math>\mathbb{R},</math> if we take as our inner product the expression <math>\langle f,g\rangle =\mathbb{E}_xf(x)g(x).</math> However, we shall not always be taking the uniform measure on <math>\{0,1\}^n.</math> If we take the measure <math>\mu_p,</math> then the natural inner product is <math>\langle f,g\rangle_p=\sum_x\mu_p(x)f(x)g(x),</math> which we shall write as <math>\mathbb{E}_pf(x)g(x).</math> (This can be read as the expectation of <math>f(x)g(x)</math> if the coordinates of x are independent Bernoulli variables with mean p.)

With respect to this inner product, the Walsh functions are no longer orthonormal, but we can define very similar functions that are orthonormal, as follows. First, choose numbers <math>a_p</math> and <math>b_p</math> such that <math>(1-p)a_p+pb_p=0,</math> <math>(1-p)a_p^2+pb_p^2=1,</math> and <math>a_p\geq 0.</math> This turns out to imply that <math>a_p=(p/(1-p))^{1/2}</math> and <math>b_p=-((1-p)/p)^{1/2},</math> though for now it is the equations they satisfy that we really care about. Next, define <math>w_{i,p}(x)</math> to be <math>a_p</math> if <math>x_i=0</math> and <math>b_p</math> if <math>x_i=1.</math> Finally, define <math>w_{A,p}(x)</math> to be <math>\prod_{i\in A}w_{i,p}(x).</math>

To be continued.

A second Fourier decomposition related to Sperner's theorem

2009-02-27T15:23:35Z

128.232.245.25: Wrote some more

==Introduction==

It seems as though it should be possible to give a clean "purely Fourier" proof of Sperner's theorem that exploits positivity, if one uses [[equal-slices measure]]. Here we present a Fourier decomposition that should achieve this, but we have not yet managed to prove the positivity (which could turn out to be a hard problem---at this stage it is not clear).

We use Ryan's formulation of equal-slices measure on <math>[2]^n</math>: the density of a set <math>\mathcal{A}</math> is <math>\mathbb{E}_p\mu_p(\mathcal{A}),</math> where <math>\mu_p</math> is the standard p-weighted measure on the cube: if A is a subset of [n] then <math>\mu_p(A)=p^{|A|}(1-p)^{n-|A|}.</math> A useful way of thinking about <math>\mu_p</math> is that <math>\mu_p(\mathcal{A}</math> is the probability that <math>(X_1,\dots,X_n)\in\mathcal{A}</math> if the <math>X_i</math> are independent Bernoulli random variables with probability p of equalling 1.

We also need to define a measure on the space of all [[combinatorial_line|combinatorial lines]]. The natural measure seems to be this. Define two sequences <math>(X_1,\dots,X_n)</math> and <math>(Y_1,\dots,Y_n)</math> of Bernoulli random variables as follows. The joint distribution of <math>(X_i,Y_i)</math> is that it equals (0,0),(0,1) and (1,1) with probabilities 1-q,q-p and p, respectively, and let different pairs
<math>(X_i,Y_i)</math> be independent. Then the <math>X_i</math> are independent Bernoulli, as are the <math>Y_i,</math> but they depend on each other in a way that guarantees that they form a combinatorial line.

We shall now be interested in the quantity <math>\mathbb{E}f(X)f(Y),</math> where <math>f</math> is some function and <math>X=(X_1,\dots,X_n), Y=(Y_1,\dots,Y_n).</math> But ultimately what will interest us is the average of this quantity over all pairs <math>0\leq p\leq q\leq 1,</math> which we can write as <math>\mathbb{E}_{p\leq q}\mathbb{E}f(X_{p,q})f(Y_{p,q}).</math>

==A proof in physical space==

Let us first prove positivity in physical space. To do this, we shall define the following equivalent model for the joint distribution of <math>X_{p,q}</math> and <math>Y_{p,q}.</math> We first pick a random variable <math>T=(t_1,\dots,t_n)</math> uniformly from <math>[0,1]^n,</math> and then we let <math>(X_{p,q})_i</math> be <math>0</math> if <math>p\leq t_i</math> and <math>1</math> if <math>p>t_i.</math> Similarly, we let <math>Y_{p,q}</math> be 0 if <math>q\leq t_i</math> and 1 if <math>q>t_i.</math> This gives us the nice property that it makes perfectly good sense even if <math>p>q,</math> and we therefore have the equation <math>\mathbb{E}_{p\leq q}\mathbb{E}f(X_{p,q})f(Y_{p,q})=(1/2)\mathbb{E}_{t\in T}\mathbb{E}_{p,q}f(X_{p,q})f(Y_{p,q}).</math>

Now <math>X_{p,q}</math> is just a function of p and t, and <math>Y_{p,q}</math> is the same function applied to q and t. Therefore, the right-hand side is equal to <math>\mathbb{E}_{t\in T}(\mathbb{E}_pf(X_{p,q}))^2,</math> which is positive.

We can say more. By Cauchy-Schwarz, the expectation is at least <math>(\mathbb{E}_{t\in T}\mathbb{E}_pf(X_{p,q}))^2,</math> which is the square of the equal-slices integral of f. In particular, if f is the characteristic function of a set <math>\mathcal{A},</math> then the combinatorial-line density is at least the square of the density of <math>\mathcal{A}.</math>

==A Fourier translation of the problem==

Recall that the [http://en.wikipedia.org/wiki/Walsh_function Walsh functions] on the set <math>[2]^n</math> are defined as follows. For each subset <math>A\subset[n]</math> we define <math>w_A(B)</math> to be <math>(-1)^{|A\cap B|}.</math> They can also be conveniently defined in sequence terms: for each A and each <math>x\in\{0,1\}^n</math> we define <math>w_A(x)=\prod_{i\in A}(-1)^{x_i}.</math>

It can easily be checked that the Walsh functions form an orthonormal basis of the <math>2^n</math>-dimensional Euclidean space of all functions from <math>\{0,1\}^n</math> to <math>\mathbb{R},</math> if we take as our inner product the expression <math>\langle f,g\rangle =\mathbb{E}_xf(x)g(x).</math> However, we shall not always be taking the uniform measure on <math>\{0,1\}^n.</math> If we take the measure <math>\mu_p,</math> then the natural inner product is <math>\langle f,g\rangle_p=\sum_x\mu_p(x)f(x)g(x),</math> which we shall write as <math>\mathbb{E}_pf(x)g(x).</math> (This can be read as the expectation of <math>f(x)g(x)</math> if the coordinates of x are independent Bernoulli variables with mean p.)

With respect to this inner product, the Walsh functions are no longer orthonormal, but we can define very similar functions that are orthonormal, as follows. First, choose numbers <math>a_p</math> and <math>b_p</math> such that <math>(1-p)a_p+pb_p=0,</math> <math>(1-p)a_p^2+pb_p^2=1,</math> and <math>a_p\geq 0.</math> This turns out to imply that <math>a_p=(p/(1-p))^{1/2}</math> and <math>b_p=-((1-p)/p)^{1/2},</math> though for now it is the equations they satisfy that we really care about. Next, define <math>w_{i,p}(x)</math> to be <math>a_p</math> if <math>x_i=0</math> and <math>b_p</math> if <math>x_i=1.</math> Finally, define <math>w_{A,p}(x)</math> to be </math>\prod_{i\in A}w_{i,p}(x).</math>

To be continued.

A second Fourier decomposition related to Sperner's theorem

2009-02-26T12:51:05Z

128.232.245.25: /* Introduction */

A second Fourier decomposition related to Sperner's theorem

2009-02-26T12:50:20Z

128.232.245.25: Started article

Main Page

2009-02-26T12:13:36Z

128.232.245.25: /* Possibly useful lemmas that are definitely in the bag */

==Introduction==

This wiki is intended to be a useful resource for anybody who wants to think about the [[density Hales-Jewett theorem]]. There are no rules about what can be added to it, but amongst other things it will contain articles that digest parts of the discussion that is taking place as part of the so-called Polymath1 project and present them in a concise way. This should save people from having to wade through hundreds of comments. If you add an article, it would be good to have it linked from this main page, so that it is easy to find. (However, there is also a [[Special:AllPages|list of all pages on this wiki]].)

During the course of the discussion so far, several [[density Hales-Jewett theorem|variants of the problem]] have been proposed.

== The Problem ==

The basic problem to be considered by the Polymath1 project is to explore a particular [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-density-hales-jewett/ combinatorial approach] to the [[density Hales-Jewett theorem]] for k=3 (DHJ(3)), suggested by Tim Gowers. The [[Furstenberg-Katznelson argument|original proof of DHJ(3) used arguments from ergodic theory]].

==Basic definitions==

*[[line|Algebraic line]]

*[[line|Combinatorial line]]

*[[Combinatorial subspace]]

*[[corners|Corner]]

*[[Density]]

*[[line|Geometric line]]

*[[Slice]]

== Useful background materials ==

Here is [http://gowers.wordpress.com/2009/01/30/background-to-a-polymath-project/ some background to the project.] There is also a [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ general discussion on massively collaborative "polymath" projects.] This is [http://meta.wikimedia.org/wiki/File:MediaWikiRefCard.png a cheatsheet for editing the wiki.] Finally, here is the general [http://meta.wikimedia.org/wiki/Help:Contents Wiki user's guide].

== Threads and further problems==

* (1-199) [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-density-hales-jewett/ A combinatorial approach to density Hales-Jewett] (inactive)
* (200-299) [http://terrytao.wordpress.com/2009/02/05/upper-and-lower-bounds-for-the-density-hales-jewett-problem/ Upper and lower bounds for the density Hales-Jewett problem] (inactive)
* (300-399) [http://gowers.wordpress.com/2009/02/06/dhj-the-triangle-removal-approach/ The triangle-removal approach] (inactive)
* (400-499) [http://gowers.wordpress.com/2009/02/08/dhj-quasirandomness-and-obstructions-to-uniformity Quasirandomness and obstructions to uniformity] (inactive)
* (500-599) [http://gowers.wordpress.com/2009/02/13/dhj-possible-proof-strategies/#more-441/ Possible proof strategies] (inactive)
* (600-699) [http://terrytao.wordpress.com/2009/02/11/a-reading-seminar-on-density-hales-jewett/ A reading seminar on density Hales-Jewett] (closing)
* (700-799) [http://terrytao.wordpress.com/2009/02/13/bounds-for-the-first-few-density-hales-jewett-numbers-and-related-quantities/ Bounds for the first few density Hales-Jewett numbers, and related quantities] (active)
* (800-899) [http://gowers.wordpress.com/2009/02/23/brief-review-of-polymath1/ Brief review of polymath1] (active)

[http://blogsearch.google.com/blogsearch?hl=en&ie=UTF-8&q=polymath1&btnG=Search+Blogs Here is a further list of blog posts related to the Polymath1 project]. [http://en.wordpress.com/tag/polymath1/ Here is wordpress's list].

A spreadsheet containing the latest upper and lower bounds for <math>c_n</math> can be found [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg here]. Here are the proofs of our [[upper and lower bounds]] for these constants.

We are also collecting bounds for [[Fujimura's problem]], motivated by a [[hyper-optimistic conjecture]].

There is also a chance that we will be able to improve the known bounds on [[Moser's cube problem]].

Here are some [[unsolved problems]] arising from the above threads.

Here is a [[tidy problem page]].

== Proof strategies ==

It is natural to look for strategies based on one of the following:

* [[Szemerédi's original proof of Szemerédi's theorem]].
* [[Szemerédi's combinatorial proof of Roth's theorem]].
* [[Ajtai-Szemerédi's proof of the corners theorem]].
* The [[density increment method]].
* The [[triangle removal lemma]].
* [[Ergodic-inspired methods]].
* The [[Furstenberg-Katznelson argument]].
* Use of [[equal-slices measure]].

== Related theorems ==

* [[Carlson's theorem]].
* The [[Carlson-Simpson theorem]].
* [[Folkman's theorem]].
* The [[Graham-Rothschild theorem]].
* The colouring [[Hales-Jewett theorem]].
* The [[Kruskal-Katona theorem]].
* [[Roth's theorem]].
* The [[IP-Szemerédi theorem]].
* [[Sperner's theorem]].
* [[Szemerédi's regularity lemma]].
* [[Szemerédi's theorem]].
* The [[triangle removal lemma]].

All these theorems are worth knowing. The most immediately relevant are Roth's theorem, Sperner's theorem, Szemerédi's regularity lemma and the triangle removal lemma, but some of the others could well come into play as well.

==Important concepts related to possible proofs==

* [[Complexity of a set]]
* [[Concentration of measure]]
* [[Influence of variables]]
* [[Obstructions to uniformity]]
* [[Quasirandomness]]

==Complete proofs or detailed sketches of potentially useful results==

*[[Sperner's theorem|The multidimensional Sperner theorem]]
*[[Line-free sets correlate locally with complexity-1 sets]]
*[[Fourier-analytic_proof_of_Sperner|A Fourier-analytic proof of Sperner's theorem]]
*[[A second Fourier decomposition related to Sperner's theorem]]

== Bibliography ==

[[Density Hales-Jewett]]

# H. Furstenberg, Y. Katznelson, “[http://math.stanford.edu/~katznel/hj43.pdf A density version of the Hales-Jewett theorem for k=3]“, Graph Theory and Combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 227–241.
# H. Furstenberg, Y. Katznelson, “[http://math.stanford.edu/~katznel/dhj12.pdf A density version of the Hales-Jewett theorem]“, J. Anal. Math. 57 (1991), 64–119.
# R. McCutcheon, “[http://www.msci.memphis.edu/~randall/preprints/HJk3.pdf The conclusion of the proof of the density Hales-Jewett theorem for k=3]“, unpublished.

[[Coloring Hales-Jewett theorem]]

# A. Hales, R. Jewett, [http://www.jstor.org/stable/1993764 Regularity and positional games], Trans. Amer. Math. Soc. 106 1963 222--229. [http://www.ams.org/mathscinet-getitem?mr=143712 MR143712]
# N. Hindman, E. Tressler, "[http://www.math.ucsd.edu/~etressle/hj32.pdf The first non-trivial Hales-Jewett number is four]", preprint.
# P. Matet, "[http://dx.doi.org/10.1016/j.ejc.2006.06.021 Shelah's proof of the Hales-Jewett theorem revisited]", European J. Combin. 28 (2007), no. 6, 1742--1745. [http://www.ams.org/mathscinet-getitem?mr=2339499 MR2339499]
# S. Shelah, "[http://www.jstor.org/stable/1990952 Primitive recursive bounds for van der Waerden numbers]", J. Amer. Math. Soc. 1 (1988), no. 3, 683--697. [http://www.ams.org/mathscinet-getitem?mr=929498 MR 929498]

[[Roth's theorem]]

# E. Croot, "[http://www.math.gatech.edu/~ecroot/szemeredi.pdf Szemeredi's theorem on three-term progressions, at a glance], preprint.

Behrend-type constructions

# M. Elkin, "[http://arxiv.org/abs/0801.4310 An Improved Construction of Progression-Free Sets ]", preprint.
# B. Green, J. Wolf, "[http://arxiv.org/abs/0810.0732 A note on Elkin's improvement of Behrend's construction]", preprint.
# K. O'Bryant, "[http://arxiv.org/abs/0811.3057 Sets of integers that do not contain long arithmetic progressions]", preprint.

Triangles and corners

# M. Ajtai, E. Szemerédi, Sets of lattice points that form no squares, Stud. Sci. Math. Hungar. 9 (1974), 9--11 (1975). [http://www.ams.org/mathscinet-getitem?mr=369299 MR369299]
# I. Ruzsa, E. Szemerédi, Triple systems with no six points carrying three triangles. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, pp. 939--945, Colloq. Math. Soc. János Bolyai, 18, North-Holland, Amsterdam-New York, 1978. [http://www.ams.org/mathscinet-getitem?mr=519318 MR519318]
# J. Solymosi, [http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=206943 A note on a question of Erdős and Graham], Combin. Probab. Comput. 13 (2004), no. 2, 263--267. [http://www.ams.org/mathscinet-getitem?mr=2047239 MR 2047239]

[[Kruskal-Katona theorem]]

# P. Keevash, "[http://arxiv.org/abs/0806.2023 Shadows and intersections: stability and new proofs]", preprint.

Quasirandomness

2009-02-23T17:04:33Z

128.232.245.25:

==Introduction==

Quasirandomness is a central concept in extremal combinatorics, and is likely to play an important role in any combinatorial proof of the density Hales-Jewett theorem. This will be particularly true if that proof is based on the [[density increment method]] or on some kind of generalization of [[Szemerédi's regularity lemma]].

In general, one has some kind of parameter associated with a set, which in our case will be the number of combinatorial lines it contains, and one would like a ''deterministic'' definition of the word "quasirandom" with the following key property.

*Every quasirandom set <math>\mathcal{A}</math> has roughly the same value of the given parameter as a random set of the same density.

Needless to say, this is not the ''only'' desirable property of the definition, since otherwise we could just define <math>\mathcal{A}</math> to be quasirandom if it has roughly the same value of the given parameter as a random set of the same density. The second key property is this.

*Every set <math>\mathcal{A}</math> that ''fails'' to be quasirandom has some other property that we can exploit.

These two properties are already discussed in some detail in the [[density increment method|article on the density increment method]]: this article concentrates more on examples of quasirandomness in other contexts, and possible definitions of quasirandomness connected with the density Hales-Jewett theorem.

==Examples of quasirandomness definitions==

====Bipartite graphs====

Let X and Y be two finite sets and let <math>f:X\times Y\rightarrow [-1,1].</math> Then f is defined to be c-quasirandom if <math>\mathbb{E}_{x,x'\in X}\mathbb{E}_{y,y'\in Y}f(x,y)f(x,y')f(x',y)f(x',y')\leq c.</math>

Since the left-hand side is equal to <math>\mathbb{E}_{x,x'\in X}(\mathbb{E}_{y\in Y}f(x,y)f(x',y))^2,</math> it is always non-negative, and the condition that it should be small implies that <math>\mathbb{E}_{y\in Y}f(x,y)f(x',y)</math> is small for almost every pair <math>x,x'.</math>

If G is a bipartite graph with vertex sets X and Y and <math>\delta</math> is the density of G, then we can define <math>f(x,y)</math> to be <math>1-\delta</math> if xy is an edge of G and <math>-\delta</math> otherwise. We call f the ''balanced function'' of G, and we say that G is c-quasirandom if its balanced function is c-quasirandom.

It can be shown that if H is any fixed graph and G is a large quasirandom graph, then the number of copies of H in G is approximately what it would be in a random graph of the same density as G.

====Subsets of finite Abelian groups====

If A is a subset of a finite Abelian group G and A has density <math>\delta,</math> then we define the balanced function f of A by setting <math>f(x)=1-\delta</math> when x\in A and <math>f(x)=-\delta</math> otherwise. Then A is c-quasirandom if and only if f is c-quasirandom, and f is defined to be c-quasirandom if <math>\mathbb{E}_{x,a,b\in G}f(x)f(x+a)f(x+b)f(x+a+b)\leq c.</math> Again, we can prove positivity by observing that the left-hand side is a sum of squares. In this case, it is <math>\mathbb{E}_{a\in G}(\mathbb{E}_{x\in G}f(x)f(x+a))^2.</math>

If G has odd order, then it can be shown that a quasirandom set A contains approximately the same number of triples <math>(x,x+d,x+2d)</math> as a random subset A of the same density. However, it is decidedly ''not'' the case that A must contain approximately the same number of arithmetic progressions of higher length (regardless of torsion assumptions on G). For that one must use "higher uniformity".

====Hypergraphs====

====Subsets of grids====

A function f from <math>[n]^2</math> to [-1,1] is c-quasirandom if the "sum over rectangles" is at most c. The sum over rectangles is <math>\mathbb{E}_{x,y,a,b}f(x,y)f(x+a,y)f(x,y+b)f(x+a,y+b)</math>. Again, it is easy to show that this sum is non-negative by expressing it as a sum of squares. And again, one defines a subset <math>A\subset[n]^2</math> to be c-quasirandom if it has a balanced function that is c-quasirandom.

If A is a c-quasirandom set of density <math>\delta</math> and c is sufficiently small, then A contains roughly the same number of [[corners]] as a random subset of <math>[n]</math> of density <math>\delta.</math>

==A possible definition of quasirandom subsets of <math>[3]^n</math>==

As with all the examples above, it is more convenient to give a definition for quasirandom functions. However, in this case it is not quite so obvious what should be meant by a balanced function.

Here, first, is a possible definition of a quasirandom function from <math>[2]^n\times [2]^n</math> to <math>[-1,1].</math> We say that f is c-quasirandom if <math>\mathbb{E}_{A,A',B,B'}f(A,B)f(A,B')f(A',B)f(A',B')\leq c.</math> However, the expectation is not with respect to the uniform distribution over all quadruples (A,A',B,B') of subsets of <math>[n].</math> Rather, we choose them as follows. (Several variants of what we write here are possible: it is not clear in advance what precise definition will be the most convenient to use.) First we randomly permute <math>[n]</math> using a permutation <math>\pi</math>. Then we let A, A', B and B' be four random intervals in <math>\pi([n]),</math> where we allow our intervals to wrap around mod n. (So, for example, a possible set A is <math>\{\pi(n-2),\pi(n-1),\pi(n),\pi(1),\pi(2)\}.</math>)

As ever, it is easy to prove positivity. To apply this definition to subsets <math>\mathcal{A}</math> of <math>[3]^n,</math> define f(A,B) to be 0 if A and B intersect, <math>1-\delta</math> if they are disjoint and the sequence x that is 1 on A, 2 on B and 3 elsewhere belongs to <math>\mathcal{A},</math> and <math>-\delta</math> otherwise. Here, <math>\delta</math> is the probability that (A,B) belongs to <math>\mathcal{A}</math> if we choose (A,B) randomly by taking two random intervals in a random permutation of <math>[n]</math> (in other words, we take the marginal distribution of (A,B) from the distribution of the quadruple (A,A',B,B') above) and condition on their being disjoint. It follows from this definition that <math>\mathbb{E}f=0</math> (since the expectation conditional on A and B being disjoint is 0 and f is zero whenever A and B intersect).

Nothing that one would really like to know about this definition has yet been fully established, though an argument that looks as though it might work has been proposed to show that if f is quasirandom in this sense then the expectation <math>\mathbb{E}f(A,B)f(A\cup D,B)f(A,B\cup D)</math> is small (if the distribution on these "set-theoretic corners" is appropriately defined).

Quasirandomness

2009-02-23T17:03:20Z

128.232.245.25: /* Subsets of grids */

Quasirandomness is a central concept in extremal combinatorics, and is likely to play an important role in any combinatorial proof of the density Hales-Jewett theorem. This will be particularly true if that proof is based on the [[density increment method]] or on some kind of generalization of [[Szemerédi's regularity lemma]].

In general, one has some kind of parameter associated with a set, which in our case will be the number of combinatorial lines it contains, and one would like a ''deterministic'' definition of the word "quasirandom" with the following key property.

*Every quasirandom set <math>\mathcal{A}</math> has roughly the same value of the given parameter as a random set of the same density.

Needless to say, this is not the ''only'' desirable property of the definition, since otherwise we could just define <math>\mathcal{A}</math> to be quasirandom if it has roughly the same value of the given parameter as a random set of the same density. The second key property is this.

*Every set <math>\mathcal{A}</math> that ''fails'' to be quasirandom has some other property that we can exploit.

These two properties are already discussed in some detail in the [[density increment method|article on the density increment method]]: this article concentrates more on examples of quasirandomness in other contexts, and possible definitions of quasirandomness connected with the density Hales-Jewett theorem.

==Examples of quasirandomness definitions==

====Bipartite graphs====

Let X and Y be two finite sets and let <math>f:X\times Y\rightarrow [-1,1].</math> Then f is defined to be c-quasirandom if <math>\mathbb{E}_{x,x'\in X}\mathbb{E}_{y,y'\in Y}f(x,y)f(x,y')f(x',y)f(x',y')\leq c.</math>

Since the left-hand side is equal to <math>\mathbb{E}_{x,x'\in X}(\mathbb{E}_{y\in Y}f(x,y)f(x',y))^2,</math> it is always non-negative, and the condition that it should be small implies that <math>\mathbb{E}_{y\in Y}f(x,y)f(x',y)</math> is small for almost every pair <math>x,x'.</math>

If G is a bipartite graph with vertex sets X and Y and <math>\delta</math> is the density of G, then we can define <math>f(x,y)</math> to be <math>1-\delta</math> if xy is an edge of G and <math>-\delta</math> otherwise. We call f the ''balanced function'' of G, and we say that G is c-quasirandom if its balanced function is c-quasirandom.

It can be shown that if H is any fixed graph and G is a large quasirandom graph, then the number of copies of H in G is approximately what it would be in a random graph of the same density as G.

====Subsets of finite Abelian groups====

If A is a subset of a finite Abelian group G and A has density <math>\delta,</math> then we define the balanced function f of A by setting <math>f(x)=1-\delta</math> when x\in A and <math>f(x)=-\delta</math> otherwise. Then A is c-quasirandom if and only if f is c-quasirandom, and f is defined to be c-quasirandom if <math>\mathbb{E}_{x,a,b\in G}f(x)f(x+a)f(x+b)f(x+a+b)\leq c.</math> Again, we can prove positivity by observing that the left-hand side is a sum of squares. In this case, it is <math>\mathbb{E}_{a\in G}(\mathbb{E}_{x\in G}f(x)f(x+a))^2.</math>

If G has odd order, then it can be shown that a quasirandom set A contains approximately the same number of triples <math>(x,x+d,x+2d)</math> as a random subset A of the same density. However, it is decidedly ''not'' the case that A must contain approximately the same number of arithmetic progressions of higher length (regardless of torsion assumptions on G). For that one must use "higher uniformity".

====Hypergraphs====

====Subsets of grids====

A function f from <math>[n]^2</math> to [-1,1] is c-quasirandom if the "sum over rectangles" is at most c. The sum over rectangles is <math>\mathbb{E}_{x,y,a,b}f(x,y)f(x+a,y)f(x,y+b)f(x+a,y+b)</math>. Again, it is easy to show that this sum is non-negative by expressing it as a sum of squares. And again, one defines a subset <math>A\subset[n]^2</math> to be c-quasirandom if it has a balanced function that is c-quasirandom.

If A is a c-quasirandom set of density <math>\delta</math> and c is sufficiently small, then A contains roughly the same number of [[corners]] as a random subset of <math>[n]</math> of density <math>\delta.</math>

==A possible definition of quasirandom subsets of <math>[3]^n</math>==

As with all the examples above, it is more convenient to give a definition for quasirandom functions. However, in this case it is not quite so obvious what should be meant by a balanced function.

Here, first, is a possible definition of a quasirandom function from <math>[2]^n\times [2]^n</math> to <math>[-1,1].</math> We say that f is c-quasirandom if <math>\mathbb{E}_{A,A',B,B'}f(A,B)f(A,B')f(A',B)f(A',B')\leq c.</math> However, the expectation is not with respect to the uniform distribution over all quadruples (A,A',B,B') of subsets of <math>[n].</math> Rather, we choose them as follows. (Several variants of what we write here are possible: it is not clear in advance what precise definition will be the most convenient to use.) First we randomly permute <math>[n]</math> using a permutation <math>\pi</math>. Then we let A, A', B and B' be four random intervals in <math>\pi([n]),</math> where we allow our intervals to wrap around mod n. (So, for example, a possible set A is <math>\{\pi(n-2),\pi(n-1),\pi(n),\pi(1),\pi(2)\}.</math>)

As ever, it is easy to prove positivity. To apply this definition to subsets <math>\mathcal{A}</math> of <math>[3]^n,</math> define f(A,B) to be 0 if A and B intersect, <math>1-\delta</math> if they are disjoint and the sequence x that is 1 on A, 2 on B and 3 elsewhere belongs to <math>\mathcal{A},</math> and <math>-\delta</math> otherwise. Here, <math>\delta</math> is the probability that (A,B) belongs to <math>\mathcal{A}</math> if we choose (A,B) randomly by taking two random intervals in a random permutation of <math>[n]</math> (in other words, we take the marginal distribution of (A,B) from the distribution of the quadruple (A,A',B,B') above) and condition on their being disjoint. It follows from this definition that <math>\mathbb{E}f=0</math> (since the expectation conditional on A and B being disjoint is 0 and f is zero whenever A and B intersect).

Nothing that one would really like to know about this definition has yet been fully established, though an argument that looks as though it might work has been proposed to show that if f is quasirandom in this sense then the expectation <math>\mathbb{E}f(A,B)f(A\cup D,B)f(A,B\cup D)</math> is small (if the distribution on these "set-theoretic corners" is appropriately defined).

Furstenberg correspondence principle

2009-02-19T09:54:00Z

128.232.245.25: /* Version 6a implies Version 1 */ typo corrected

The Furstenberg correspondence principle equates density Ramsey theorems in combinatorics with recurrence theorems in ergodic theory. In our context, the principle equates the following two statements:

'''DHJ(3), Version 1'''. For every <math>\delta > 0</math> there exists n such that every subset <math>A \subset [3]^n</math> of density at least <math>\delta</math> contains a [[combinatorial line]].

'''DHJ(3), Version 6'''. If the free group <math>F_3</math> on three generators 1, 2, 3, acts in a measure-preserving fashion <math>(T_w: X \to X)_{w \in F_3}</math> on a probability space X, and E is a set of positive measure in X, then there exists a combinatorial line <math>w^1,w^2,w^3</math> such that <math>T_{w^1}^{-1}(E) \cap T_{w^2}^{-1}(E) \cap T_{w^3}^{-1}(E)</math> has positive measure.

To prove this equivalence, it is convenient to introduce an intermediate stage:

'''DHJ(3), Version 6a'''. Let <math>(X_n)_{n \in {\Bbb Z}}</math> be a family of probability spaces, and for each <math>w \in F_3</math> of length <math>|w| \in {\Bbb Z}</math> (where the inverse generators <math>1^{-1}, 2^{-1}, 3^{-1}</math> are considered to have length -1) and <math>n \in {\Bbb Z}</math>, let <math>T_{w, n+|w|}: X_{n+|w|} \to X_n</math> be an invertible measure-preserving map obeying the groupoid law

:<math> T_{vw, n+|vw|} = T_{v,n+|v|} T_{w,n+|vw|}</math> (1)

for all integers n and group elements <math>v,w \in F_3</math>. Let <math>E_0</math> be a set of positive measure in <math>X_0</math>, then there exists a combinatorial line <math>w^1,w^2,w^3 \in [3]^n</math> such that <math>T_{w^1,n}^{-1}(E_0) \cap T_{w^2,n}^{-1}(E_0) \cap T_{w^3,n}^{-1}(E_0)</math> has positive measure in <math>X_n</math>.

== Version 1 implies Version 6 ==

This is easy. Let <math>\delta</math> be the measure of E, and let n be as in Version 1. From the first moment method and the measure-preserving nature of T, we see that the expected density of <math> \{ w \in [3]^n: x \in T_w^{-1}(E) \}</math> is <math>\delta</math>. Thus for a set of positive measure, this set has density at least <math>\delta</math> and thus contains a combinatorial line. The claim now follows from the pigeonhole principle.

== Version 6 implies Version 6a ==

This is also easy. Let the setup be as in Version 6a. We define the product space <math>X := \prod_{n \in {\Bbb Z}} X_n</math>, and give it the action <math>T_w: X \to X</math> of the free group <math>F_3</math> by the formula

:<math> T_w ( x_n )_{n \in {\Bbb Z}} := ( T_{w,n+|w|} x_{n+|w|} )_{n \in {\Bbb Z}};</math>

the groupoid law (1) ensures that this is an action, and the measure-preserving nature of the <math>T_{w,n+|w|}</math> ensures that this is measure-preserving. The claim now follows by applying Version 6 to the cylinder set <math>E_0 \times \prod_{n \neq 0} X_n</math>.

== Version 6a implies Version 1 ==

This is the hard direction. We argue by contradiction. If Version 1 failed, then there exists <math>\delta > 0</math>, a sequence of n going off to infinity, and a sequence of line-free sets <math>A^{(n)} \subset [3]^n</math>, each of density at least <math>\delta</math>.

We let <math>m = m^{(n)}</math> be an integer growing slowly with n, and <math>r = r^{(n)}</math> be an integer growing more slowly with n. For each <math>i \geq 0</math>, let <math>B_i</math> be the ball of radius i in <math>F_3</math> (i.e. the set of all strings of length at most i formed from the generators <math>1,2,3,1^{-1},2^{-1},3^{-1}</math>). For any d, define a ''simple'' d-dimensional [[combinatorial subspace]] to be a d-dimensional combinatorial subspace whose d wildcards <math>*_1,\ldots,*_d</math> each appear in just a single position <math>a_1,\ldots,a_d \in [n]</math>; we refer to these positions as the <math>directions</math> of the simple subspace. We say that a simple (d+1)-dimensional subspace is a ''j-extension'' of a simple d-dimensional subspace for some j=1,2,3, if the latter subspace can be obtained from the former by replacing the final wildcard <math>*_{d+1}</math> with j, and then we refer to the latter subspace as the ''j-slice'' of the former.

We will assign a random simple <math>m+|w|</math>-dimensional subspace <math>V_w = \phi_w( [3]^{m+|w|} ) \subset [3]^n</math> to each word <math>w \in B_r</math>, by the following recursive procedure:

* To the identity element id, we choose <math>V_{id}</math> uniformly at random among all m-dimensional simple combinatorial subspaces in <math>[3]^n</math>, such that the digits 1, 2, 3 each appear at least r times amongst the frozen coordinates.
* Now suppose recursively that <math>V_w</math> has been chosen for all <math>v \in B_i</math>.
* If <math>v \in B_i \backslash B_{i-1}</math> and <math>j \in \{1,2,3\}</math>, we define <math>V_{vj^{-1}}</math> to be the j=slice of <math>V_v</math>.
* If <math>v \in B_i \backslash B_{i-1}</math> and <math>j \in \{1,2,3\}</math>, we draw <math>V_{vj}</math> uniformly and independently at random from all j-extensions of <math>V_v</math>.

For each integer s, let <math>\Gamma_s := \{w \in F_3: |w| = s \}</math>, and let <math>X_s := 2^{\Gamma_{-s}}</math> be the power set of the countable set <math>\Gamma_{-n}</math>. We have the maps <math>T_{w,s+|w|}: X_{s+|w|} \to X_s</math> defined by

:<math>T_{w,s+|w|}(B) := w B</math>;

these are invertible and obeys the groupoid relation (1).

We can define a random element <math>x_0^{(n)} \in X_0</math> by the formula

:<math>x_0^{(n)} := \{ w \in B_r \cap \Gamma_{-0}: \phi_w( 1^m ) \in A^{(n)} \}.</math>

The distribution of this random element gives a probability measure <math>\mu_0^{(n)}</math>.

Let <math>E_0 \subset X_0</math> be the cylinder set <math>E_0 := \{ B \subset \Gamma_0: id \in B \}.</math>

'''Lemma 1''' (Density): <math>\mu_0^{(n)}(E_0) = \delta + o(1)</math> as <math>n \to \infty</math>.

'''Proof'''. ...

'''Lemma 2''' (Asymptotic stationarity): If <math>w \in \Gamma_0</math> and E is a cylinder set in <math>X_0</math>, then <math>\mu_0^{(n)}( T_{w,0}(E) ) = \mu_0( E ) + o(1)</math> as <math>n \to \infty</math>.

'''Proof'''. ...

'''Lemma 3''' (Line-free-ness) For any combinatorial line <math>w^1,w^2,w^3</math>, the set <math>E_0 \cap T_{w^2 (w^1)^{-1},0}(E_0) \cap T_{w^3 (w^1)^{-1},0}(E_0)</math> has zero measure in <math>\mu_0^{(n)}</math>.

'''Proof'''. ...

Now let <math>\mu_0</math> be a vague subsequential limit of the <math>\mu_0^{(n)}</math>, then by Lemma 1, <math>E_0</math> has positive measure, and by Lemma 2 the probability measure <math>\mu_0</math> is invariant with respect to <math>T_{w,0}</math> whenever <math>w \in \Gamma_0</math>, We can then uniquely define a probability measure <math>\mu_s</math> on <math>X_s</math> by requiring that <math>T_{w,s}: X_s \to X_0</math> map <math>\mu_s</math> to <math>\mu_0</math> for all <math>w \in \Gamma_s</math>. The hypotheses of Theorem 6a are now satisfied and so there exists a combinatorial line <math>w^1,w^2,w^3 \in [3]^s</math>, the set <math>E_0 \cap T_{w^2 (w^1)^{-1},0}(E_0) \cap T_{w^3 (w^1)^{-1},0}(E_0)</math> has positive measure with respect to <math>\mu_s</math>, but this contradicts Lemma 3 and we are done.

Tidy problem page

2009-02-17T12:33:37Z

128.232.245.25: /* What is the correct one-dimensional generalization of Sperner's theorem? */ expanded article and added more problems

There is already a page devoted to [[unsolved problems]] related to the polymath1 project. This page is intended as a more polished page for unsolved problems. Contributions are welcome: they should be problems that are formulated precisely enough for others to think about without having to worry about what they mean. Additional commentary about the problems is also very useful. Also, it would be good if this page were reasonably organized: if you want to add a problem then try to put it near other related problems, and if there are two or three problems that could fit under a general heading, then add such a heading, and so on.

==What is the correct one-dimensional generalization of Sperner's theorem?==

As has been observed several times, if you apply the density Hales-Jewett theorem to sets <math>A</math> of sequences such that whether or not <math>x</math> belongs to <math>A</math> depends only on the number of 1s, 2s and 3s in <math>x</math>, then you can easily deduce the corners theorem: that a dense subset of <math>[n]^2</math> contains a triple of the form <math>(x,y),(x+d,y),(x,y+d)</math>. If you try the same thing with Sperner's theorem, you deduce the trivial one-dimensional result that a dense subset of <math>[n]</math> contains a pair of the form <math>(x),(x+d)</math>. (I have written these as "ordered singletons" to make the analogy clearer.) This is Szemerédi's theorem for arithmetic progressions of length 2.

Now the corners result is a natural generalization of Szemerédi's theorem for progressions of length 2, but so is Szemerédi's theorem itself. So a natural question (with potential applications to the project) arises:

*What generalization of Sperner's theorem relates to Sperner's theorem itself in the way that the general case of Szemerédi's theorem relates to the trivial case of progressions of length 2?

One theorem that does the job is the following: let <math>\mathcal{A}</math> be a subset of <math>[2]^n</math> such that the average density of <math>\mathcal{A}</math> in each slice of <math>[2]^n</math> is at least <math>\delta</math>. Then there are disjoint sets <math>A,D_1,\dots,D_k</math> all of the same size such that <math>A\cup D_1\cup\dots\cup D_j</math> belongs to <math>\mathcal{A}</math> for every <math>0\leq j\leq k</math>.

'''Proof:''' Pick a random permutation of <math>[n]</math>. Then on average there will be <math>\delta n</math> initial segments of the permuted set that belong to <math>\mathcal{A}</math>. By Szemerédi's theorem we can find an arithmetic progression of these of length <math>k</math>.

There is one aspect of this statement that seems a bit artificial, which is the assumption that the <math>D_j</math> all have the same cardinality.

*Is it possible to justify this as a natural assumption (e.g. by showing that the theorem is useful)?

*Is there a more set-theoretic generalization of the statement?

*Can one find not just the sets of the form <math>A\cup D_1\cup\dots\cup D_j</math> but all sets of the form <math>A\cup\bigcup_{j\in S}D_j</math>?

Closely related to this last question is the same question but without the requirement that the <math>D_i</math> have the same cardinality:

*If <math>\mathcal{A}</math> is dense (either in the uniform probability measure on <math>[2]^n</math> or in the [[equal-slices measure]]) then must there exist disjoint sets <math>A,D_1\dots,D_k</math> such that <math>A\cup\bigcup_{j\in S}D_j\in\mathcal{A}</math> for every <math>S\subset\{1,2,\dots,k\}</math>?

It is possible to deduce a positive answer to this last question by using DHJ(<math>2^k</math>) and considering binary expansions of numbers in <math>[2^k]</math>. Is there a more elementary argument?

==How difficult is DHJ(j,k)?==

One might expect that proving [[Density_Hales-Jewett_theorem|DHJ(j,k)]] is about as difficult as proving DHJ(j+1). But is this the case? In particular, is there a reasonably simple Sperner-style proof of DHJ(1,3)? (There is at least a proof of a fairly general case of this theorem, but it would be good to prove the whole thing in an elementary way.) If you are allowed to use DHJ(j+1) as a black box, can you give a combinatorial proof of DHJ(j,k) for all k?

==Hyper-optimistic conjectures==

The proof of Sperner's theorem yields the following stronger result.

'''Theorem.''' If <math>\mathcal{A}\\subset[2]^n</math> has [[equal-slices_measure|equal slices density]] greater than <math>1/(n+1)</math> then <math>\mathcal{A}</math> contains two distinct sets A and B with <math>A\subset B.</math>

The proof makes use of the following trivial fact: if <math>A\subset\{0,1,\dots,n\}</math> has density greater than <math>1/(n+1)<\math> then A contains two distinct numbers x and y with <math>x<y.</math>

The trivial fact can be generalized to the [[corners theorem]]. For each n, let <math>\delta_n</math> be the minimal density needed to guarantee a corner. By analogy with the above two results, one might be "hyper-optimistic" and hope for the following to be true. (However, there is no good evidence for the conjecture that is to follow.)

'''Conjecture.''' If <math>\mathcal{A}\\subset[3]^n</math> has [[equal-slices_measure|equal slices density]] greater than <math>\delta_n</math> then <math>\mathcal{A}</math> contains a combinatorial line.