Another proposal for a polymath project is the following question of Michael Boshneritzan:
Question. Let
be a (simple) path in a lattice
which has bounded step sizes, i.e.
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
with r non-zero such that
.
The d=1 case follows from Szemerédi’s theorem, as the path has positive density. Even for d=2 and k=3 the problem is open. 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 to my knowledge this has not been done. There are also some faint resemblances to the angel problem that has recently been solved.
In honour of mini-polymath1, one could phrase this problem as a grasshopper trying to jump forever (with bounded jumps) in a square lattice without creating an arithmetic progression (of length three, say).
It is also worth trying to find a counterexample if C, d, k are large enough. Note that the continuous analogue of the problem is false: a convex curve in the plane, such as the parabola 
In short, there seem to be a variety of tempting avenues to try to attack this problem; it may well be that many of them fail, but the reason for that failure should be instructive.
Andrew Mullhaupt informs me that this question would have applications to short pulse rejected Boolean delay equations.
The polymath blog 
A very small remark, though one that does have some bearing on how one might approach the problem, is that the d=1 case follows even from van der Waerden’s theorem, since each interval of size C (on at least one side of the origin) must contain a point in the set. One can therefore partition into equal intervals and colour them according to which member belongs to the set.
If it really is the case that no counterexample is known for any C, d and k, then that certainly sounds a tempting thing to think about.
Comment by gowers — July 27, 2009 @ 1:34 pm |
I can see, by the way, that it is going to be difficult to restrain participants from making useful comments on a proposed project before the project really starts :-). But perhaps having a limited number of such comments serve as a good “warm-up” before the project begins, somewhat analogous to the preliminary laps an indoor cyclist takes before an Olympic race. Perhaps what we can do here in this pre-polymath stage is adhere much more strictly to the rule that no offline thinking about the problem is allowed.
Comment by Terence Tao — July 27, 2009 @ 2:51 pm |
I think there’s a big difference between making remarks that occur to one immediately (in the above case, I was familiar with the general principle that sets with bounded gaps “only need van der Waerden” so didn’t have to think) and making remarks that are a genuine attempt to get things going.
As for offline thinking, there is an argument for allowing it to a limited extent. Consider, for example, the case of DHJ. If I had said that anybody who wanted to was welcome to spend a month trying to solve the problem, then it is fairly unlikely that anybody would have, but at the end of the month there might have been more people who were familiar enough with the relevant ideas to be able to follow the discussion and participate. However, there could be a problem that everybody saved up their preliminary ideas and the result was an even huger burst of initial activity than we actually experienced. So in the end, perhaps the best solution is to have no offline thinking but to take very seriously the need for a lot of expository work to accompany the research.
Comment by gowers — July 27, 2009 @ 4:02 pm |
I think there is only 5 levels of reply possible and when you reply to the 6 level it bump the highest level reply to the next numbering sort of the RSK algorithm.
Comment by Gil Kalai — July 27, 2009 @ 5:46 pm |
Not only does the d=1 case follow from vdW, it *implies* vdW. Consider a coloring of the naturals with r colors (r minimial) and without long APs. Clearly, all r colors are used infinitely often. The set of naturals colored red either have bounded gaps (and so has long APs), or it has arbitrarily long gaps. By looking at the r-1 coloring of ever longer segments between reds, and applying the usual compactness-type argument, we get an r-1 coloring of the naturals, and by induction we’re done.
Comment by Kevin O'Bryant — July 29, 2009 @ 2:47 am |
Gil, I have set the comment depth at 10. I would imagine that this would be adequate for just about any conceivable discussion…
Comment by Terence Tao — July 27, 2009 @ 6:04 pm |
Two concerns about this problem are: (1) Is the problem sufficiently well known; (2) As this problem is fairly closely related to polymath1 there is a “strategic” question if it is a good idea to have the next project in the same area, and if the same general area is chosen how this problem is compared with others.
An advantage of the problem is that the answer is not known, it can go both ways, so it has a different nature from polymath1, polymath2 and the minipolymath.
If there are a veriety of promising avenues it may be useful to write them down (even if some are fairly obvious to experts) and this can be useful to a researcher working on this problem or even on other problems in this area regardless if the problem is chosen.
Comment by Gil Kalai — July 27, 2009 @ 9:33 pm |
The following very nice related problem was posted and solved at the MathLinks forum a while back (see http://www.mathlinks.ro/viewtopic.php?t=5294).
“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.”
The general Boshernitzan question for d=2, if true, would solve the above problem directly. It might be a good idea to study the ‘frog’ problem first.
Comment by Raghu — July 28, 2009 @ 6:15 pm |
I asked a variation of this question at the Western Number Theory Conference in 2001, see http://www.math.colostate.edu/~achter/wntc/problems/problems2001.pdf , problem 000:12. Tom Brown had worked on this and related questions, and pointed out that the answer is known to be “no”. In particular (quoting the pdf file referenced above; I haven’t read the article itself):
F. M. Dekking, Strongly nonrepetitive sequences and progression-free sets, JCT-A 27 (1979) 181–185, MR 81b:05027.
Dekking shows that there is an infinite sequence of plane lattice points where each gap is (0, 1) or (1, 0) such that no 5 points are in AP.
Comment by Kevin O'Bryant — July 29, 2009 @ 2:33 am |
It looks to me like Dekking solves the problem (in the negative), doesn’t he? The way he phrases it is that he builds infinite words, in an alphabet of r letters, so that no n consecutive blocks are permutations of each other. If we turn these letters into steps in the unit directions in Z^r, then this gives paths that avoid n+1 term arithmetic progressions. Dekking gives counter-examples for (r,n) = (4,2) and (3,3). He states that (25,2) was done by Evdokimov http://www.ams.org/mathscinet-getitem?mr=234842 and (2,5) by Justin http://www.ams.org/mathscinet-getitem?mr=301119 .
Am I missing something?
Comment by David Speyer — July 29, 2009 @ 12:53 pm |
Ah, I see, the problem wasn’t open for all (k,d).
In that case, let me make a suggestion: Terry says that the case (k,d) = (3,2) is open. Dekking has solved (3,4). Could we modify Dekking’s solution so that its projection to the plane remains a solution?
Comment by David Speyer — July 29, 2009 @ 1:05 pm |
If the following is true:
Dekking shows that there is an infinite sequence of plane lattice points where each gap is (0, 1) or (1, 0) such that no 5 points are in AP.
Don’t we have a complete solution to the problem as posted?
If dimension is one we are done.
If we have two linearly independent possible steps we can use them in place of the gaps (0,1) and (1,0) in Dekkings proof and limit arithmetic progressions to length 5 which solves the problem as stated since we are trying to block arbitrarily long arithmetic progressions and we can in fact block all those of length six.
Comment by kristalcantwell — July 29, 2009 @ 4:02 pm |
In addition to Kevin, I had also asked a related sort of question in the past (to Olof Sisask), though I didn’t publish it anywhere. You can find the note I sent to Olof at
http://www.math.gatech.edu/~ecroot/dendrites.tex
Comment by Ernie Croot — July 29, 2009 @ 1:37 pm |
If it doesn’t turn out to have an unexpectedly easy solution, then that’s a very nice question!
Comment by gowers — July 29, 2009 @ 2:15 pm |
Thanks! The third question in the note I feel is probably quite hard, but the second one can surely be worked out easily. I suppose one can think of the third problem as a type of “Turan-type analogue” to Michael B.’s problem.
On an unrelated matter, I am glad to hear about the paper of Dekking on paths without 5APs. I had come to that problem myself, and had asked two grad students here at Georgia Tech (my student Evan Borenstein and Michael Lacey’s student Bill McClain) about whether they could construct such paths (without 5APs), but we didn’t ever produce one, though we sort of knew how to do it.
Comment by Ernie Croot — July 29, 2009 @ 2:38 pm |
Can anyone post the Dekking paper or give a short summary of the construction? I couldn’t find the paper on the web and my (like most) library doesn’t have access to JCT volumes as far back as 1979.
Comment by Anonymous — July 29, 2009 @ 3:26 pm |
It was the third one that I was referring to. I like the way it seems to invite a curious mixture of topological arguments with more conventional density ones — indeed, so curious that it isn’t obvious at all how a proof could go if the answer was positive.
Comment by gowers — July 29, 2009 @ 4:16 pm |
I’ve set up a rudimentary wiki page for this problem at
http://michaelnielsen.org/polymath1/index.php?title=Boshernitzan’s_problem
It also incorporates some information sent to me by email by Michael Boshneritzan. As always, further contributions are welcome (currently, for instance, Croot’s problems are not on the wiki).
Comment by Terence Tao — August 3, 2009 @ 1:12 pm |
“It is also worth trying to find a counterexample if C, d, k are large enough. Note that the continuous analogue of the problem is false: a convex curve in the plane, such as the parabola \{ (x,x^2): x \in {\Bbb R}\}, contains no arithmetic progressions, but is rectifiable. However it is not obvious how to discretise this example.”
If the problem is changed so integers are replaced by real numbers then it is still false as there is only a finite number of points forming lines and an uncountable number of points that are real numbers distance C from the original point.
Comment by kristalcantwell — August 3, 2009 @ 7:15 pm |
In all of the negative results given by Dekking, the counterexamples have step sizes that are not only bounded, but are actually all equal to one. However, in the case (d,k)=(2,3), one can verify by hand that if a counterexample exists, it must have step sizes greater than one.
For the two remaining cases, I wrote a little algorithm to find long paths which avoid AP’s, assuming we only allow a step size of one. It found paths of length > 80 for both (d,k)=(2,4) and (d,k)=(3,3) in a matter of minutes. This seems to suggest that it is possible to construct a counterexample in these cases. Unfortunately, the constructed paths don’t appear to follow any obvious pattern.
Comment by Kevin V. — August 4, 2009 @ 7:27 am |
Another question of this type: Let
be lattice points in 
dimensions, and suppose that 
is a finite set. Must the set 
contain arbitrarily large symmetric subsets?
The set
is symmetric if there is a 
(not necessarily in 
) such that 
. For example, arithmetic progressions are symmetric.
Comment by Kevin O'Bryant — August 9, 2009 @ 8:28 am |
Oops, this has been solved, too:
MR1881964 (2003b:05153)
Banakh, T. O.(UKR-LVV-MM); Kmit, I. Ya.(UKR-LST-NMP); Verbitsky, O. V.(UKR-LVV-MM)
On asymmetric colorings of integer grids. (English summary)
Ars Combin. 62 (2002), 257–271.
Comment by Kevin O'Bryant — August 17, 2009 @ 6:06 am |