Suppose that is a subset of of maximum cardinality not containing an arithmetic progression of length 3. Let .
How does behave? We do not really know. Will it help talking about it? Can we somehow look beyond the horizon and try to guess what the truth is?
Update 1: for the discussion: Here are a few more specific questions that we can wonder about and discuss.
1) Is the robustness of Behrend’s bound an indication that the truth is in this neighborhood.
2) Why arn’t there analogs for Salem-Spencer and Behrend’s constructions for the cup set problem?
3) What type of growth functions can we expect at all as the answer to such problems?
4) Where is the deadlock in improving the upper bounds for AP-free sets?
5) What new kind of examples one should try in order to improve the lower bounds? Are there some directions that were already extensively explored?
6) Can you offer some analogies? Other problems that might be related?
Roth proved that . Szemeredi and Heath-Brown improved it to for some (Szemeredi’s argument gave .) Jean Bourgain improved the bound in 1999 to and recently to (up to lower order terms).
Erdös and Turan who posed the problem in 1936 described a set not containing an arithmetic progression of size . Salem and Spencer improved this bound to . Behrend’s upper bound from 1946 is of the form . A small improvement was achieved recently by Elkin and is discussed here. (Look also at the remarks following that post.)
A closely related problem can be asked in . It is called the cap set problem. A subset of is called a cap set if it contains no arithmetic progression of size three or, alternatively, no three vectors that sum up to 0(modulo 3). If is a cap set of maximum size we can ask how the function behaves. Roy Meshulam proved, using Roth’s argument, that . Edell found an example of a cap set of size . So . Again the gap is exponential. What is the truth?
These are problems that attracted people’s interest for decades. The gaps between the lower and upper bounds are very large.
Will it help talking about it? Can we somehow look beyond the horizon and try to guess what the truth is? Is there a meaningful way to have a discussion of these problems? To give some heuristic non-rigorous arguments? To bring some useful analogies? To assign probabilities to the different possibilities? (We talked a little about assigning probabilities in cases of uncertainty in this post.)
Anyway, (as a little spin off to the polymath1 project, if you have any thoughts about where the truth is for these problems, or about how to discuss them meaningfully, or about the more general issue of trying to look “beyond the horizon” in mathematics in a meaningful way, you are most welcome to contribute.
And everybody is invited to participate in the following polls – one about 3-term arithmetic progressions and one about cap sets.
Update 2: another poll on the expected answer for density Hales Jewett added
The question is: what is the maximum size of a subset of without a combinatorial line. The recent proofs appears to lead to . A sort of hyper-optimistic conjecture that was proposed along the project asserts that the maximum is obtained by a union of slices, where a slice means all vectors with a prescribed numbers of 0′s 1′s and 2′s.
In polls the choice of answers is of important. For our choices of answers, look also at Scott Aaronson’s favorite growth rates.
Polls (even exit polls) can also be wrong…