Boshernitzan’s problem

A polymath project is proposed to study the following question of Michael Boshneritzan:

'Question. Let [math]\displaystyle{ x_1, x_2, x_3, \ldots \in {\Bbb Z}^d }[/math] be a (simple) path in a lattice [math]\displaystyle{ {\Bbb Z}^d }[/math] which has bounded step sizes, i.e. [math]\displaystyle{ 0 \lt |x_{i+1}-x_i| \lt C }[/math] for some C and all i. Is it necessarily the case that this path contains arbitrarily long arithmetic progressions, i.e. for each k there exists [math]\displaystyle{ a, r \in {\Bbb Z}^d }[/math] with [math]\displaystyle{ r }[/math] non-zero such that [math]\displaystyle{ a, a+r, \ldots, a+(k-1)r \in \{x_1,x_2,x_3,\ldots\} }[/math].

The discussion page for the proposal is here.

The answer to this question is true for some values of (d,k), false for others, and open for yet others. The only open cases yet remaining are (d,k) = (2,3), (3,3), and (2,4).

The question looks intriguingly like the multidimensional Szemerédi theorem, but it is not obvious how to deduce it from that theorem. It is also tempting to try to invoke the Furstenberg correspondence principle to create an ergodic theory counterpart to this question, but this apparently has not been done. There are also some faint resemblances to the angel problem that has recently been solved.

According to Andrew Mullhaupt, this question has applications to short pulse rejected Boolean delay equations.

Positive results

• True for d=1 from van der Waerden's theorem (and is in fact equivalent to it), as one can colour (at least one half of the) integers by the local structure of the path near that integer.
• Trivial for k=1,2.

Negative results

• False for (d,k) = (2,4) : indeed, in Cassaigne et al (see the Bibliography), they construct an infinite word over the alphabet {0, 1, 3, 4} containing no three consecutive blocks of the same size and the same sum. Hence, if we replace the letter i by the vector (1,i), we get a path in Z^2 that does not contain arithmetic progressions of length 4.
• False for (d,k) = (2,5) (Dekking; previously shown for (3,5) by Justin
• False for (d,k) = (4,3) (Dekking; previously shown for (26,3) by Evdokimov)

Note that a negative result for some (d,k) implies negative results for higher d and k.

Related problems and observations

• The following very nice related problem was posted and solved at the MathLinks forum a while back: “On the plane with lattice points,there is a frog. First it is on the point(0,0).At each second if it is on point (x,y) it goes to point (x+1,y) or (x,y+1). Prove that for each n there are n collinear points on the frog’s path.”

• It is interesting to point out that some ”approximate” versions of the conjecture hold for all constants:

in fact, one can always choose “approximate” arithmetical progressions of any length.

The following observations are due to Michael Boshneritzan:

• Every connected set [math]\displaystyle{ S \subset {\Bbb R}^2 }[/math] (not one point) contains an approximate progression of length 3.
  • If S is not a convex curve (locally) or just one point then it contains a precise AP of length 3.
• Every set in [math]\displaystyle{ {\Bbb R} }[/math] of Hausd. dim 1 contains arbitrary long approx. APs. A compact subset of Hausd.dim .99 does not need to contain approx. APs of length 3.
• The property of a metric space to contain arbitrary long approximate APs is a biLipshitz invariant.
• Special case: If a sequence [math]\displaystyle{ x = (x_k)_{k=1}^\infty }[/math], in a metric space is Bi-Lipshitz (i.e. [math]\displaystyle{ d(x_j,x_k) }[/math] is comparable to |j-k|) then there are arbitrary long (finite) APs [math]\displaystyle{ F \subset {\Bbb Z} }[/math] such that x(F) is an approx. AP.

I would also like to state an ergodic conjecture which would imply my problem with d=2.

Conjecture. Let T, S be ergodic measure preserving transformations of a prob. measure space X. Let f,g be integrable real valued (important!) functions X → R with [math]\displaystyle{ \int f + g = 0 }[/math]. Then for a.a. [math]\displaystyle{ x \in X }[/math]

[math]\displaystyle{ \liminf_{N \to \infty} |\sum_{k=1}^N f(T^n x) + g(S^n x)| = 0. }[/math]

(T, S may be assumed commuting.)

One can also think of a topological formulation which may turn out easier.

Bibliography

• S. V. Avgustinovich, A. E. Frid. Words avoiding abelian inclusions. Journal of Automata, Languages and Combinatorics 7 (2002) 39.
• M. Boshneritzan, Lecture Notes In Computer Science; Vol. 623, Proceedings of the 19th International Colloquium on Automata,, Languages and Programming, Pages: 41 - 52. Year of Publication: 1992
• M. Boshneritzan, WORDS 2007 Sixth International Conference on Words September 1721, 2007, CIRM, Marseille, France
• T. C. Brown, Is there a sequence on four symbols in which no two adjacent segments are permutations of one another?, Amer. Math. Monthly 78 (1971), no. 8, 886--888. MR 1536459
• J. Cassaigne, J. D. Currie, L. Schaeffer, J. Shallit, Avoiding Three Consecutive Blocks of the Same Size and Same Sum, arXiv preprint.
• F. M. Dekking, Strongly nonrepetitive sequences and progression-free sets, JCT-A 27 (1979) 181–185, MR 81b:05027.
• R.C. Entringer, D.E. Jackson, J.A. Schatz ”On non-repetitive sequences”, J. Combin. Theory Ser. A 16 (1974), 159-164.