IP-Szemerédi theorem

IP-Szemerédi theorem: If n is sufficiently large depending on [math]\displaystyle{ \delta \gt 0 }[/math], then any subset of [math]\displaystyle{ [2]^n \times [2]^n }[/math] of density at least [math]\displaystyle{ \delta }[/math] contains a corner [math]\displaystyle{ (x,y), (x+r,y), (x,y+r) }[/math], where x, y, x+r, y+r all lie in [math]\displaystyle{ [2]^n }[/math] and r lies in [math]\displaystyle{ [2]^n \backslash 0^n }[/math].

Implies the corners theorem, and hence Roth's theorem. Is implied in turn by the density Hales-Jewett theorem, and may thus be a simpler test case.

No combinatorial proof of this theorem is currently known.

Randall McCutcheon proposes a slightly weaker version of this theorem in which [math]\displaystyle{ [2]^n }[/math] is replaced by [math]\displaystyle{ [n]^n }[/math], but r is still constrained to [math]\displaystyle{ [2]^n \backslash 0^n }[/math].

Relationship with DHJ(3)

First note that the density Hales-Jewett theorem for [math]\displaystyle{ k=3 }[/math] is equivalent to the following statement.

Theorem. Let [math]\displaystyle{ \mathcal{A} }[/math] be a dense subset of the set of all pairs [math]\displaystyle{ (A,B) }[/math] of disjoint subsets of [math]\displaystyle{ [n]. }[/math] Then [math]\displaystyle{ \mathcal{A} }[/math] contains a triple of the form [math]\displaystyle{ (A,B),(A\cup D,B),(A,B\cup D), }[/math] where A, B and D are all disjoint.

To see the equivalence, just associate with each pair [math]\displaystyle{ (A,B) }[/math] the sequence in [math]\displaystyle{ [3]^n }[/math] that is 1 on A, 2 on B and 3 everywhere else. Then a triple of pairs as described in the theorem corresponds to a combinatorial line. (One can of course modify the statement above to obtain a version that is equivalent to DHJ(3) with the equal-slices measure.)

Now let us see how to modify the set-pairs formulation of DHJ(3) to obtain a statement equivalent to the IP-Szemerédi theorem. All we have to do is drop the condition that A and B should be disjoint.

Theorem. Let [math]\displaystyle{ \mathcal{A} }[/math] be a dense subset of the set of all pairs [math]\displaystyle{ (A,B) }[/math] of subsets of [math]\displaystyle{ [n]. }[/math] Then [math]\displaystyle{ \mathcal{A} }[/math] contains a triple of the form [math]\displaystyle{ (A,B),(A\cup D,B),(A,B\cup D), }[/math] where D is disjoint from both A and B.

The equivalence of this with the IP-Szemerédi theorem is even easier to see: one just associates each set with its characteristic function.

Motivation for considering the IP-Szemerédi theorem

When trying to solve a problem, one good strategy is to look for the simplest related problem that involves the same difficulties (or some of the same difficulties) that one is facing. The IP-Szemerédi theorem is a good candidate for a result that has this relationship with DHJ(3). Since no combinatorial proof is known, it clearly involves some serious difficulties. However, if we drop the condition that A and B have to be disjoint, then the bipartite graph formed by joining A to B if and only if [math]\displaystyle{ (A,B)\in\mathcal{A} }[/math] is dense if [math]\displaystyle{ \mathcal{A} }[/math] is dense. This means that one third of the natural tripartite graph associated with the problem (see the article on the triangle removal lemma for details) is dense, which should make it easier, but not too much easier, to analyse than the tripartite graph naturally associated with DHJ(3).

Unorganised discussion

Solymosi.2: In this note I will try to argue that we should consider a variant of the original problem first. If the removal technique doesn’t work here, then it won’t work in the more difficult setting. If it works, then we have a nice result! Consider the Cartesian product of an IP_d set. (An IP_d set is generated by d numbers by taking all the [math]\displaystyle{ 2^d }[/math] possible sums. So, if the n numbers are independent then the size of the IP_d set is [math]\displaystyle{ 2^d }[/math]. In the following statements we will suppose that our IP_d sets have size [math]\displaystyle{ 2^n }[/math].)

Prove that for any [math]\displaystyle{ c\gt 0 }[/math] there is a [math]\displaystyle{ d }[/math], such that any [math]\displaystyle{ c }[/math]-dense subset of the Cartesian product of an IP_d set (it is a two dimensional pointset) has a corner.

The statement is true. One can even prove that the dense subset of a Cartesian product contains a square, by using the density HJ for [math]\displaystyle{ k=4 }[/math]. (I will sketch the simple proof later) What is promising here is that one can build a not-very-large tripartite graph where we can try to prove a removal lemma. The vertex sets are the vertical, horizontal, and slope -1 lines, having intersection with the Cartesian product. Two vertices are connected by an edge if the corresponding lines meet in a point of our [math]\displaystyle{ c }[/math]-dense subset. Every point defines a triangle, and if you can find another, non-degenerate, triangle then we are done. This graph is still sparse, but maybe it is well-structured for a removal lemma.

Finally, let me prove that there is square if [math]\displaystyle{ d }[/math] is large enough compare to [math]\displaystyle{ c }[/math]. Every point of the Cartesian product has two coordinates, a 0,1 sequence of length [math]\displaystyle{ d }[/math]. It has a one to one mapping to [math]\displaystyle{ [4]^d }[/math]; Given a point [math]\displaystyle{ ( (x_1,…,x_d),(y_1,…,y_d) ) }[/math] where [math]\displaystyle{ x_i,y_j }[/math] are 0 or 1, it maps to [math]\displaystyle{ (z_1,…,z_d) }[/math], where [math]\displaystyle{ z_i=0 }[/math] if [math]\displaystyle{ x_i=y_i=0 }[/math], [math]\displaystyle{ z_i=1 }[/math] if [math]\displaystyle{ x_i=1 }[/math] and [math]\displaystyle{ y_i=0, z_i=2 }[/math] if [math]\displaystyle{ x_i=0 }[/math] and [math]\displaystyle{ y_i=1 }[/math], and finally [math]\displaystyle{ z_i=3 }[/math] if [math]\displaystyle{ x_i=y_i=1 }[/math]. Any combinatorial line in [math]\displaystyle{ [4]^d }[/math] defines a square in the Cartesian product, so the density HJ implies the statement.

Gowers.7: With reference to Jozsef’s comment, if we suppose that the [math]\displaystyle{ d }[/math] numbers used to generate the set are indeed independent, then it’s natural to label a typical point of the Cartesian product as [math]\displaystyle{ (\epsilon,\eta) }[/math], where each of [math]\displaystyle{ \epsilon }[/math] and [math]\displaystyle{ \eta }[/math] is a 01-sequence of length [math]\displaystyle{ d }[/math]. Then a corner is a triple of the form [math]\displaystyle{ (\epsilon,\eta) }[/math], [math]\displaystyle{ (\epsilon,\eta+\delta) }[/math], [math]\displaystyle{ (\epsilon+\delta,\eta) }[/math], where [math]\displaystyle{ \delta }[/math] is a [math]\displaystyle{ \{-1,0,1\} }[/math]-valued sequence of length [math]\displaystyle{ d }[/math] with the property that both [math]\displaystyle{ \epsilon+\delta }[/math] and [math]\displaystyle{ \eta+\delta }[/math] are 01-sequences. So the question is whether corners exist in every dense subset of the original Cartesian product.

This is simpler than the density Hales-Jewett problem in at least one respect: it involves 01-sequences rather than 012-sequences. But that simplicity may be slightly misleading because we are looking for corners in the Cartesian product. A possible disadvantage is that in this formulation we lose the symmetry of the corners: the horizontal and vertical lines will intersect this set in a different way from how the lines of slope -1 do.

I feel that this is a promising avenue to explore, but I would also like a little more justification of the suggestion that this variant is likely to be simpler.

Gowers.22: A slight variant of the problem you propose is this. Let’s take as our ground set the set of all pairs [math]\displaystyle{ (U,V) }[/math] of subsets of [math]\displaystyle{ [n] }[/math], and let’s take as our definition of a corner a triple of the form [math]\displaystyle{ (U,V), (U\cup D,V), (U,V\cup D) }[/math], where both the unions must be disjoint unions. This is asking for more than you asked for because I insist that the difference [math]\displaystyle{ D }[/math] is positive, so to speak. It seems to be a nice combination of Sperner’s theorem and the usual corners result. But perhaps it would be more sensible not to insist on that positivity and instead ask for a triple of the form [math]\displaystyle{ (U,V), ((U\cup D)\setminus C,V), (U, (V\cup D)\setminus C }[/math], where [math]\displaystyle{ D }[/math] is disjoint from both [math]\displaystyle{ U }[/math] and [math]\displaystyle{ V }[/math] and [math]\displaystyle{ C }[/math] is contained in both [math]\displaystyle{ U }[/math] and [math]\displaystyle{ V }[/math]. That is your original problem I think.

I think I now understand better why your problem could be a good toy problem to look at first. Let’s quickly work out what triangle-removal statement would be needed to solve it. (You’ve already done that, so I just want to reformulate it in set-theoretic language, which I find easier to understand.) We let all of [math]\displaystyle{ X }[/math], [math]\displaystyle{ Y }[/math] and [math]\displaystyle{ Z }[/math] equal the power set of [math]\displaystyle{ [n] }[/math]. We join [math]\displaystyle{ U\in X }[/math] to [math]\displaystyle{ V\in Y }[/math] if [math]\displaystyle{ (U,V)\in A }[/math].

Ah, I see now that there’s a problem with what I’m suggesting, which is that in the normal corners problem we say that [math]\displaystyle{ (x,y+d) }[/math] and [math]\displaystyle{ (x+d,y) }[/math] lie in a line because both points have the same coordinate sum. When should we say that [math]\displaystyle{ (U,V\cup D) }[/math] and [math]\displaystyle{ (U\cup D,V) }[/math] lie in a line? It looks to me as though we have to treat the sets as 01-sequences and take the sum again. So it’s not really a set-theoretic reformulation after all.

O'Donnell.35: Just to confirm I have the question right…

There is a dense subset [math]\displaystyle{ A }[/math] of [math]\displaystyle{ \{0,1\}^n x \{0,1\}^n }[/math]. Is it true that it must contain three nonidentical strings [math]\displaystyle{ (x,x’), (y,y’), (z,z’) }[/math] such that for each [math]\displaystyle{ i = 1…n, }[/math] the 6 bits

[math]\displaystyle{ [ x_i x'_i ] }[/math]

[math]\displaystyle{ [ y_i y'_i ] }[/math]

[math]\displaystyle{ [ z_i z'_i ] }[/math]

are equal to one of the following:

[math]\displaystyle{ [ 0 0 ] [ 0 0 ] [ 0, 1 ] [ 1 0 ] [ 1 1 ] [ 1 1 ] }[/math]

[math]\displaystyle{ [ 0 0 ], [ 0 1 ], [ 0, 1 ], [ 1 0 ], [ 1 0 ], [ 1 1 ], }[/math]

[math]\displaystyle{ [ 0 0 ] [ 1 0 ] [ 0, 1 ] [ 1 0 ] [ 0 1 ] [ 1 1 ] }[/math]

?

McCutcheon.469: IP Roth:

Just to be clear on the formulation I had in mind (with apologies for the unprocessed code): for every [math]\displaystyle{ \delta\gt 0 }[/math] there is an [math]\displaystyle{ n }[/math] such that any [math]\displaystyle{ E\subset [n]^{[n]}\times [n]^{[n]} }[/math] having relative density at least [math]\displaystyle{ \delta }[/math] contains a corner of the form [math]\displaystyle{ \{a, a+(\sum_{i\in \alpha} e_i ,0),a+(0, \sum_{i\in \alpha} e_i)\} }[/math]. Here [math]\displaystyle{ (e_i) }[/math] is the coordinate basis for [math]\displaystyle{ [n]^{[n]} }[/math], i.e. [math]\displaystyle{ e_i(j)=\delta_{ij} }[/math].

Presumably, this should be (perhaps much) simpler than DHJ, [math]\displaystyle{ k=3 }[/math].