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

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