DHJ(1,3)

Statement of the problem

Recall that DHJ(1,3) is the following problem.

• Let [math]\displaystyle{ \mathcal{U}, \mathcal{V} }[/math] and [math]\displaystyle{ \mathcal{W} }[/math] be three collections of subsets of [math]\displaystyle{ [n] }[/math] and let [math]\displaystyle{ \mathcal{A} }[/math] be the set of all sequences [math]\displaystyle{ x\in[3]^n }[/math] such that the 1-set, 2-set and 3-set of [math]\displaystyle{ x }[/math] belongs to [math]\displaystyle{ \mathcal{U}, \mathcal{V} }[/math] and [math]\displaystyle{ \mathcal{W}, }[/math] respectively. If [math]\displaystyle{ \mathcal{A} }[/math] is dense, does it follow that it contains a combinatorial line?

The answer is of course yes, since it is just DHJ(3) with an extra restriction on the dense set that one would like to contain a combinatorial line. The reasons for considering the question are (i) that it ought to be amenable to the kinds of techniques used to prove Sperner's theorem, and (ii) that sets of this special kind need to be understood, as they appear to be an important class of obstructions to uniformity in DHJ(3). Since Sperner's theorem is most naturally proved using equal-slices measure on [math]\displaystyle{ [2]^n, }[/math] we shall use it here.

An easy version of the problem

Since any element [math]\displaystyle{ x\in[3]^n }[/math] is determined by just its 1-set and its 2-set, it is natural to consider the yet simpler variant of DHJ(1,3) where [math]\displaystyle{ \mathcal{W} }[/math] consists of all subsets of [math]\displaystyle{ [n]. }[/math] This problem can be solved by an easy adaptation of one of the proofs of Sperner's theorem.

To see this, note first that if the equal-slices measure of [math]\displaystyle{ \mathcal{A} }[/math] is greater than n+1, then there must exist c such that the sum over [math]\displaystyle{ a+b=n-c }[/math] of the densities of [math]\displaystyle{ \mathcal{A} }[/math] in the slices [math]\displaystyle{ \Gamma_{a,b,c} }[/math] is greater than 1. Now choose a random permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n]. }[/math] Then the expected number of [math]\displaystyle{ a }[/math] such that the first [math]\displaystyle{ a }[/math] elements of [math]\displaystyle{ \pi([n]) }[/math] form an element of [math]\displaystyle{ \mathcal{U} }[/math] and the next [math]\displaystyle{ n-c-a }[/math] elements form an element of [math]\displaystyle{ \mathcal{V} }[/math] is greater than 1. So there must exist a permutation such that this number is greater than 1, and hence at least 2. That gives us two pairs of disjoint sets [math]\displaystyle{ (U_1,V_1) }[/math] and [math]\displaystyle{ (U_2,V_2) }[/math] belonging to [math]\displaystyle{ \mathcal{U}\times\mathcal{V} }[/math] such that [math]\displaystyle{ U_1\cup V_1=U_2\cup V_2 }[/math] and [math]\displaystyle{ U_1\subset U_2. }[/math] But then, writing [math]\displaystyle{ W }[/math] for [math]\displaystyle{ [n]\setminus(U\cup V), }[/math] the three triples [math]\displaystyle{ (U_1,V_1,W), (U_2,V_2,W) }[/math] and [math]\displaystyle{ (U_1,V_2,W\cup(U_2\cap V_1) }[/math] determine sequences that form a combinatorial line in [math]\displaystyle{ \mathcal{A}. }[/math]

Corners(1,3)

Many of the alternative problems we have considered have been inspired by analogies between DHJ(3) and the corners theorem. Because of this, it is natural to ask whether there is a "corners analogue" of DHJ(1,3). And there is. We define a subset A of [math]\displaystyle{ [n]^2 }[/math] to be of complexity 1 if there are three subsets U, V and W of [math]\displaystyle{ [n] }[/math] such that A is the set of all [math]\displaystyle{ (x,y) }[/math] such that [math]\displaystyle{ x\in U, y\in V }[/math] and [math]\displaystyle{ x+y\in W. }[/math] Then we can ask the following question, for which the obvious name is corners(1,3).

• Let A be a dense subset of [math]\displaystyle{ [n]^2. }[/math] Must A contain a corner?

Again, we know that the answer is yes, since we know the corners theorem. So the next question is whether there is an easy proof of this fact. The reason for being interested in this question is that it may give us some guidance about how to approach DHJ(1,3).

The easy variant

Following what we did above, let us begin by looking at the obvious analogue of the even easier variant: in this case we find ourselves asking whether if U and V are dense sets then their Cartesian product [math]\displaystyle{ U\times V }[/math] must contain a corner? This amounts to asking whether we can find [math]\displaystyle{ u,u'\in U }[/math] and [math]\displaystyle{ v,v'\in V }[/math] with [math]\displaystyle{ u'-u=v'-v. }[/math] If such elements exist, then we get the corner [math]\displaystyle{ (u,v),(u,v'),(u',v). }[/math] (In fact, of course, we get a square by adding in the point [math]\displaystyle{ (u',v'). }[/math])

It is easy to prove that the difference sets intersect, since [math]\displaystyle{ u'-u=v'-v }[/math] if and only if [math]\displaystyle{ u'+v=u+v' }[/math] so we just need some element of [math]\displaystyle{ U+V }[/math] to have at least two representations as [math]\displaystyle{ u+v, }[/math] which we get from a trivial averaging argument. (Note how similar this argument is to the argument for the easy case of DHJ(1,3).)

The full statement

How about the general statement of corners(1,3)? For the corner [math]\displaystyle{ (x,y),(x+d,y),(x,y+d) }[/math] to lie in A, we need [math]\displaystyle{ x,x+d\in U, y,y+d\in V, }[/math] and [math]\displaystyle{ x+y,x+y+d\in W. }[/math] The information we are given is that there is a dense set of pairs [math]\displaystyle{ (x,y) }[/math] such that [math]\displaystyle{ x\in U,y\in V }[/math] and [math]\displaystyle{ x+y\in W. }[/math] In other words, we would like to find a triple [math]\displaystyle{ (u,v,w)\in U\times V\times W }[/math] such that u+v=w and there is a non-zero d with [math]\displaystyle{ (u+d,v+d,w+d)\in U\times V\times W. }[/math]

We are told that there are many triples [math]\displaystyle{ (u,v,w)\in U\times V\times W }[/math] such that u+v=w and an easy averaging argument shows that there are many triples [math]\displaystyle{ (u,v,w)\in U\times V\times W }[/math] such that [math]\displaystyle{ (u+d,v+d,w+d)\in U\times V\times W }[/math] for many non-zero d. Can we combine the two somehow?

Here is a very rapid sketch of a non-elementary argument for corners(1,3). We use the following lemmas.

• The intersection of a dense set with a random translate of another dense set is, on average, dense.

• Every dense subset of [n] contains an arithmetic progression of length proportional to [math]\displaystyle{ \log\log\log\log\log n. }[/math]

By repeatedly applying these two lemmas one can partition almost all of [math]\displaystyle{ U\times V }[/math] into products [math]\displaystyle{ P\times Q, }[/math] where P and Q are arithmetic progressions of the same common difference. If W has density c, then an average one of these products [math]\displaystyle{ P\times Q }[/math] contains [math]\displaystyle{ c|P\times Q| }[/math] elements [math]\displaystyle{ (x,y) }[/math] such that [math]\displaystyle{ x+y\in W, }[/math] and therefore contains two that do not lie in the same diagonal line. But if two diagonal lines intersect [math]\displaystyle{ P\times Q }[/math] then the intersection contains a corner.

This proof is non-elementary, but modulo Szemerédi's theorem it is elementary. Is there a completely elementary argument? If there does not seem to be one, then it will give us important information about what a proof of DHJ(1,3), and hence an eventual analytic proof of DHJ(3), could be like.