Boshernitzan’s problem - Revision history

Tmonteil: the conjecture is false for (d,k) = (2,4)

2012-01-03T10:55:08Z

the conjecture is false for (d,k) = (2,4)

← Older revision		Revision as of 03:55, 3 January 2012
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.

OBryant: /* Bibliography */ added reference to Brown, which itself has 16 references to other work on this problem, and generalizations

2009-08-17T05:58:54Z

Bibliography: added reference to Brown, which itself has 16 references to other work on this problem, and generalizations

← Older revision		Revision as of 22:58, 16 August 2009
Line 53:		Line 53:
	* 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, 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		* 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
	* 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.

Teorth: /* Related problems and observations */

2009-08-03T13:10:55Z

Teorth: New page: A polymath project is proposed to study the following question of Michael Boshneritzan: : '''Question''. Let $x_1, x_2, x_3, \ldots \in {\Bbb Z}^d$ be a (simple) path in a latt...

2009-08-03T13:10:40Z

New page: 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 latt...

New page

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 < |x_{i+1}-x_i| < 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 [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 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.

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,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])

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 [http://www.mathlinks.ro/viewtopic.php?t=5294 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
* 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.

← Older revision		Revision as of 06:10, 3 August 2009
Line 34:		Line 34:
	* Every connected set <math>S \subset {\Bbb R}^2</math> (not one point) contains an approximate progression of length 3.		* 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.		** 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		* 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.
	.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.		* 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.		* 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.
Line 47:		Line 46:

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


	== Bibliography ==		== Bibliography ==

Boshernitzan’s problem - Revision history

Tmonteil: the conjecture is false for (d,k) = (2,4)

OBryant: /* Bibliography */ added reference to Brown, which itself has 16 references to other work on this problem, and generalizations

Teorth: /* Related problems and observations */

Teorth: New page: A polymath project is proposed to study the following question of Michael Boshneritzan: : '''Question''. Let x_1, x_2, x_3, \ldots \in {\Bbb Z}^d be a (simple) path in a latt...

Teorth: New page: A polymath project is proposed to study the following question of Michael Boshneritzan: : '''Question''. Let $x_1, x_2, x_3, \ldots \in {\Bbb Z}^d$ be a (simple) path in a latt...