Difference between revisions of "Boshernitzan’s problem"
(→Bibliography: added reference to Brown, which itself has 16 references to other work on this problem, and generalizations) |
(the conjecture is false for (d,k) = (2,4)) |
||
Line 5: | Line 5: | ||
The discussion page for the proposal is [http://polymathprojects.org/2009/07/27/proposal-boshernitzans-problem here]. | The discussion page for the proposal is [http://polymathprojects.org/2009/07/27/proposal-boshernitzans-problem 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 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), <del>and (2,4)</del>. |
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 [http://en.wikipedia.org/wiki/Angel_problem angel problem] that has recently been solved. | 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 [http://en.wikipedia.org/wiki/Angel_problem angel problem] that has recently been solved. | ||
Line 18: | Line 18: | ||
== Negative results == | == 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 [http://www.ams.org/mathscinet-getitem?mr=301119 Justin] | * False for (d,k) = (2,5) (Dekking; previously shown for (3,5) by [http://www.ams.org/mathscinet-getitem?mr=301119 Justin] | ||
* False for (d,k) = (4,3) (Dekking; previously shown for (26,3) by [http://www.ams.org/mathscinet-getitem?mr=234842 Evdokimov]) | * False for (d,k) = (4,3) (Dekking; previously shown for (26,3) by [http://www.ams.org/mathscinet-getitem?mr=234842 Evdokimov]) | ||
Line 54: | Line 55: | ||
* M. Boshneritzan, WORDS 2007 Sixth International Conference on Words September 1721, 2007, CIRM, Marseille, France | * 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 | * 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, [http://arxiv.org/abs/1106.5204 arXiv preprint]. | ||
* F. M. Dekking, Strongly nonrepetitive sequences and progression-free sets, JCT-A 27 (1979) 181–185, MR 81b:05027. | * 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. | * R.C. Entringer, D.E. Jackson, J.A. Schatz ”On non-repetitive sequences”, J. Combin. Theory Ser. A 16 (1974), 159-164. |
Latest revision as of 02:55, 3 January 2012
A polymath project is proposed to study the following question of Michael Boshneritzan:
- 'Question. Let [math]x_1, x_2, x_3, \ldots \in {\Bbb Z}^d[/math] be a (simple) path in a lattice [math]{\Bbb Z}^d[/math] which has bounded step sizes, i.e. [math]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]a, r \in {\Bbb Z}^d[/math] with [math]r[/math] non-zero such that [math]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]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]{\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]x = (x_k)_{k=1}^\infty[/math], in a metric space is Bi-Lipshitz (i.e. [math]d(x_j,x_k)[/math] is comparable to |j-k|) then there are arbitrary long (ﬁnite) APs [math]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]\int f + g = 0[/math]. Then for a.a. [math]x \in X[/math]
- [math]\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.