Suppose that 
How does 
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 
Erdös and Turan who posed the problem in 1936 described a set not containing an arithmetic progression of size 
A closely related problem can be asked in 
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.
For polymath1 background look especially here and here. Look also at this post on our blog. The updated version contains a discussion in what sense was polymath1 a massive collaboration.
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 
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…
Combinatorics and more 
Gil, the one thing I would say (which we have sort of said already) is that in my view it would be a very good idea to have a big collaboration devoted to these problems. However, I know that Ernie Croot would not like it, and he may well not be alone. So I think it’s a good idea to have a discussion.
The reason I’m in favour of an open collaboration for these problems is that, as you yourself said, many people have thought about them very hard and had ideas. This means that there is, out there, a great deal of private expertise, and there seems to be at least a chance that a combination of this and the Polymath phenomenon of people very rapidly stimulating each other to develop their ideas would result in a solution. And if it didn’t, it could still greatly clarify where the difficulties lie.
One issue we would need to discuss if such a project went ahead is how broad its scope should be. For example, it would seem artificial to exclude attempting to solve it by improving the bounds in the triangle-removal lemma, but including that problem as well would mean that the project encompassed a large part of additive combinatorics. That would be fine by me, but some might object.
I’m seriously considering your suggestion that I go public with my little thoughts on Roth’s theorem. The three main things that inhibit me are (i) I haven’t checked whether this would be interfering with somebody else’s work; (ii) I don’t feel ready just at the moment for another Polymath project (because I have some conventional ones that badly need attention), and (iii) I think the thoughts I had may be well-known ideas in disguise. Of these, (iii) is the least important — making the ideas public would be a quick way of checking whether they were essentially equivalent to known ideas.
Anyhow, I hope others who are interested in these problems will also contribute to this discussion, so we can see whether there is an appetite for a poly-attack on them.
Dear Prof. Gowers,
Inspired by your idea about Polymath project and in combination with the idea behind founding MathOverflow.net, recently I suggested an “Idea Exchange site” for professional mathematicians on Meta.MathOverflow which received a nice feedback by the community.
Fortunately some MO users who are expert in community building found the idea interesting and practically reasonable and so they really want to help establishing such a community beside MathOverflow. It can enrich MathOverflow and add a new dimension to the contribution style of professional mathematicians online.
However due to the difficulty of finding a nice group of network builders, nobody started the project yet and based on some reasons the corresponding post in Meta.MathOverflow is deleted now, but I think the idea has a great potential for being experimented. Thus let me explain it here briefly, hopefully those who may see this post can start such a project.
In a few words it is about the idea of establishing a site which serves as a kind of “never ending online math conference” for public discussing on possible approaches to the long standing open problems and also finding research collaborators, A kind of online simulation for all what happens in a real conference, a place for gathering of prominent mathematicians and young researchers and sharing their half-baked thoughts for finding real solutions for hard open problems.
However travelling around the world to get a physical access to a researcher for discussing the ideas and founding a joint work based on common interests is still a dominating way of doing maths, but it seems a bit old fashioned particularly when we notice that almost all other important aspects of the life have now an online alternative. You can meet people online, talk to them, find partners, buy things, exchange money, watch movies, etc., Why can’t mathematicians solve math problems online together? And why can’t they find their collaborators with a simple discussion online?
Unfortunately the potential of MathOverflow as a Q&A forum is limited for solving important open problems. Its style is not suitable for approaching hard open problems or finding collaborators because the good questions appear randomly and the discussions are not allowed there while most of long standing open problems need long discussions of the experts on their personal thoughts and possible difficulties of the problem. The Idea Exchange site can accumulate all those uncompleted but valuable personal thoughts on a particular open problem and hopefully can generate a complete solution, as you described in your comment.
As the first step people on MathOverflow suggested starting a blog for everybody (including MathOverflow users) to go there and discuss the possible purposes and features of this “Idea Exchange” site. It would be perfect if the first move for building such a site starts from those mathematicians who experienced similar ideas so far. Their great experience can highly improve the discussions on the primary blog and will attract much more attention of the mathematics community.
Best Regards
Despite being somewhat directly affected by Tim’s point (ii) above, I think it would be very exciting to have an open collaboration on Roth and related questions! Personally I’d be much more inclined to invest time in keeping up with such a project than the initial one on DHJ.
However, my worry is that discussing upper bounds for Roth would result in a similarly small set of experts dominating the discussion from the start. The entry barrier would again be quite high, because some very good people have thought about this problem very hard and discarded a lot of the ideas one might have thinking about it for the first time.
Of course a small collaboration of this type is not necessarily a bad thing! If one wanted to aim for wider participation, however, one could initiate an in-depth discussion on the lower bound first, which is likely (because of its much more elementary nature) to attract a much wider audience. Even if one believed firmly that Behrend cannot be improved, a better understanding of why that is may tell us quite a bit about possible upper-bound approaches, which could then be discussed in a second stage.
The cap set problem strikes me as a particularly useful formulation in the sense that it would attract mathematicians who wouldn’t necessarily classify themselves as combinatorialist, at least not of the analytic variety. And since we are very clearly missing something pretty important in the big picture, an outsider’s perspective may be exactly what is needed here.
As a footnote, as Tim mentioned, I know of a number people who would not welcome such a project at this point. It may be worth the effort trying to convince them on an individual basis though.
Dear Tim and Julia,
many thanks for your comments. Tim, I hope you will find a way publically or otherwise to explore your ideas about Roth’s theorem. It need not be a large cooperational project.
The purpose of my current post is not to have an open attack on these problems or an invitation to a new polymath, but to have an open discussion on them. I am curious to know if there are ways we can “just” discuss these problems.
There are various famous problems in mathematics were we have rather strong confidence about what the truth is. It is often the case in mathematics and certainly in other sciences that we can meaningfully try to look beyond the horizon using appealing conjectures (even vaguely-formulated,) analogies, “baby problems, various heuristic methods, etc.
This is not the case for Roth theorem or for the cap set problem. At least not to my kowledge. Maybe there is no way around it but I thought it worth the try. And we can also discuss what type of math problems.issues are more suitable for a “conceptual” non technical discussion.
Some cases where there is an emerging confidence that a certain conjecture is true is when many appealing applications and consequences are found. This is a little paradoxical because one can argue that every appealing (unknown) consequence of a conjecture makes the conjecture itself a little less plausible. Still if a conjecture is becomming part of a whole coherent array of conjectures then it looks that we are more willing to accept it and it also looks that in many cases being part of such a coherent array of conjectures indeed makes it more plausible.
Pingback: Polymath1: Success! « Combinatorics and more
Hello all,
I’ve only got a (very vague) item to answer to question 6) you ask. It looks like
a fairly standard “extremal” problem in combinatorics, but I did not find any reference to it
in the literature. Let p be a fixed integer,
and F be any set of “forbidden” subsets of {1, … ,p}. For any integer n, call a susbet E of {1, … ,n} admissible if for every intger k, the intersection of E with {k+1, … ,k+p} is not a translate
of a forbidden subset. Let h(n) denote the largest size of an admissible subset of {1, … ,n}.
Question 1. Is it true that h(n) is always eventually affine (i.e. h(n+1)-h(n) is eventually
periodic?)
Question 2. Is it true that for large enough n, the “optimal” subsets of {1, … ,n} (those
whose size is exactly h(n)) must contain APs ?
All questions are already nontrivial when F is a singleton. When p tends to infinity and
F is the subset of all AP’s in {1,…,p}, we may look at this as a “sequence of finite approximants”
converging to the original problem on AP-free sets, so that this problem looks easier.
Ewan
Dear Ewan, This looks interesting and quite natural.
Answer to Ewan’s question 1 is yes. See paper “Sequences of integers with missing differences” by Cantor and Gordon, JCTA, 1973. They deal with a more special question, and with infinite sets, but their argument can be adapted to this situation. Answer to question 2 is again no for trivial reason: it might happen that everything but the empty set is forbidden. The underlying issue is that “containing AP” is a non-induced notion, whereas the structures Ewan forbids are induced. It seems hard to formulate a non-trivial question along those lines as Szemeredi’s theorem tells us that a set without a given AP has density zero. One might ask about progressions of linear size, but I remember constructing examples where optimal sets were made of blocks, and each block could be chosen among several possibility. That rules out necessarily periodic answers, but I do not remember whether it ruled out linearly-sized APs. I would be surprised if it did not. I cannot give you the examples (which were for more restrictive problem of Cantor and Gordon), as the program that found them was not backed up, when my hard drive crashed,
Thanks for your reference Boris.
Ewan
As a footnote, as Tim mentioned, I know of a number people who would not welcome such a project at this point. It may be worth the effort trying to convince them on an individual basis though.
Could someone in the know explain in more detail why so many people are working on the problem?
I do not know if many people are working on it (the cap set problem), but there are several people who do. It is a neat problem and it looks that ideas needed for pushing the
bound would be closely related to improving the bounds for Roth’s theorem beyond 
. However, the cap set problem looks technically much easier and “cleaner”.
I would be greatly interested in a “capset Polymath project.”
I don’t think many people work on the capset problem, as long as “to work” means “to make progress.” Rather, there may be people who dream of working on it, but I believe a mathematical problem should not be reserved for one particular person just because (s)he has already spent some time on it.
For any positive development there may be someone not quite happy with this development for whatever personal reason; should we thus reject the very idea of progress?
I just wanted to add it was original proposed to work on the capset problem alongside with other low-n problems:
and Terry even gave it a notation of c”_n, but other than pointing out papers were people had made progress nobody at polymath has took up the gauntlet. Someone still could, I suppose; I don’t think the low-n case is glamorous enough for people to have spent their careers on.
One of the questions I asked is about analogies.
Perhaps the simplest question is the analogy between the problem of the right bound in Roth’s theorem, and the cap set problem. I am not sure this analogy was obvious when the cap set problem was first raised, but Meshulam’s proof of the upper bound using Roth’s method (Meshulam’s paper attributes a similar observation also to Ruzsa,) and asking about 3-terms arithmetic progressions in different groups made this analogy very clear.
Now, looking at the outcome of the polls so far, it is not clear if this analogy is strong on people mind. It looks that believeing that the known constructions are close to the truth will go along in the two conjectures.
My expectations were as follows: People who believe that the best cap sets are of size
will also believe that the truth for Roth’s theorem is near the Behrend bound – 
.
I expected that some people who believe that the truth in Roth is the Behrend bound, may think that for the cap set problem the truth is
, but others may think that there is still a Behrend-type construction that we missed for the cap set problem, so the truth is 
(
).
The polls do not support my expectations on what people think. A large majority of people (8 out of 11) think the answer for the cap set problem is
. Nobody expected the answer to be 
. Only 7 out of 17 expressed the opinion that the answer for Roth is in near the Behrend bound. 8 people think that the answer for Roth is 
for some 
and 3 even voted (against the Erdos-Turan conjecture) for 
.
(Personally, i do not have strong beliefs on these conjectures. (And whatever belief I apriori had is shaddowed by Tim’s recent assertions on the matter.) But I do believe that the answers to Roth and cap sets will go together.)
Maybe I will suggest wilder analogies to these problems later. Meanwhile, here is a nice post on n-category cafe with some discussions on the role of analogies im mathematics starting with a sentence (brought by Jonathan vos post) attributed by Ulam to Banach: “Good mathematicians see analogies. Great mathematicians see analogies between analogies.” (And here is another post from n category cafe about explaining Geometric Langlands theory using analogies.)
I do not know if in the ptoblem-solving Erdos-like part of mathematics analogies are so useful.
One characterization of the discussion I wanted to have is that it will not be direct open attack on the problems like in the main threads, and also not a metadiscussion like a few meta threads but something in between. Beside analogies some remarks about possible connections and problems inspired by the technical discussion could fit here. And in fact there were several such remarks in the regular threads.
Let me repeat some analogy that I wanted to discuss. I may devote to it a new post but for the time being I will just have it as a remark.
1042. Density increasing and an analog problem (repeated) http://gowers.wordpress.com/2009/03/10/problem-solved-probably/#comment-2908
Let me mention a problem which I thought of as analogous to Roth/cap set where the gaps between lower and upper bounds are similarly shocking and the current density increasing arguments cannot help; (It is related to old work of mine with Kahn and Linial, and also to some more recent work with Shelah that we did not publish.)
You have a subset A of
of density c and you would like to find a combinatorial subcube F of dimension 0.9n so that the projection of A to F is of large density say 0.99.
In other words, we want to find a set of 0.9n coordinates so that for a fraction 0.99 of the vectors supported on this set we can find a continuation on the other coordinates that is in A.
(The DHJ was about restriction to a subcube/subspace and not about projections. But projections which are closely related to influences played a role, and traditionally sections and projections are related.)
By a density increasing argument doing it one coordinate at a time it was known from the late 80s that this can be achieved if c is
for 
or so. A conjecture by Benny Chor asserts that 
is good enough!
This conjecture is mentioned in the post on Nati’s influence.
(At the end, the section about two old conjectures on influences.)
I think it is a little analogous to Roth (or cap set)
a few points:
1) The proof is also by a slow density increasing argument (you reduce the dimension by one every time) and there are examples the such an argument cannot be improved. The density increase argument is based on KKL’s theorem.
2) There are some conjectures (by Friedgut and others) which may explain why we can get the density down to
for every 
and maybe even to $ \beta=\gamma \log n$ but not even plans on how to prove Chor’s conjecture beyond it.
3) There are important examples by Ajtai and Linial of Boolean functions descibed by certain random depth 3 circuits (that Ryan already mentioned in the main threads) that may (or a varian of) give a counter example. It is complicated to check it. Here is the link to Ajtai-Linial paper.
(NEW: Here is an online version of the paper
http://www.cs.huji.ac.il/~nati/PAPERS/ajtai_coalitions.pdf )
I admit that the analogy with density increasing argument for Roth-type problems is not very strong: this problem is about projection to subcubes and there it is about restrictions to subspaces or similar creatures; But there may be some connecion.
In particular I would try subsets described by low depth small size circuits (with operations over {0,1,2}) as candidates for counter examples for the most ambitious conjectures regarding Roth and cap sets.
Another worthwhile direction in the Roth/Szemeredi saga would be to find different and or simpler approach to Gowers’s theorems regarding AP of length four and more.
The very basic strategy in these proofs is (But I tell it from memory so please correct me if it is incorrect):
A) show that if the number of k-dimensional discrete subcubes is as expected (from a random set with the same density) then so is the number of A.P. of length k. A discrete k-dimensional cube is a set of all points of the form
where the x and y’s are fixed and the epsilons go over all 0-1 vectors of length k.
B-Z) Show that if the number of discrete cube is not as expected there is a subspace of dimension
on which the density is higher.
on the way to Z there are some other steps. One step is to show high correlation with a set which is “piece-wise polynomial” in some sense.
Also Freiman’s theorem plays a prominent (but to me quite a mysterious role). I think a very nice place to read about the proof for 4 terms AP is in the paper dealing with k-terms AP where the original argument is somewhat simplified. (I am not sure what is the best place to read about the proof for k=4 is now.)
There are two obvious question: The first is to find simpler proof for the general k case which is a very complicated proof. The second is the question even for k=4: is there a different way to go from A to Z, namely from the assumption that the number of discrete k-dimensional cubes is irregular to the conclusion that there is a subspace of polynomial dimension on which the set has higher density.
Julia wrote: “Even if one believed firmly that Behrend cannot be improved, a better understanding of why that is may tell us quite a bit about possible upper-bound approaches, which could then be discussed in a second stage.”
I think this is a very good idea. Finding interesting examples appears to be an area where large open discussion can be quite fruitfull.
Tres intiresno, gracias
Pingback: Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier | Combinatorics and more
Pingback: What is difficult about the cap-set problem? « Gowers's Weblog
Pingback: The Cap-Set Problem and Frankl-Rodl Theorem (C) | Combinatorics and more
Pingback: A Couple Updates on the Advances-in-Combinatorics Updates | Combinatorics and more
Pingback: Cup Sets, Sunflowers, and Matrix Multiplication | Combinatorics and more
Dear Prof. Kalai,
Are you sure that you didn’t approve the above comment by ALindsayE accidentally?!
Please review the comment and see the introduced link. It seems an advertisement for kind of services which are not appropriate to be mentioned on this site.
Shanah Tovah! 🙂
GK: comment deleted. Dear Ali, Thanks, Comments here are not moderated, but I try to delete inappropriate comments if I see them or told about them.
Pingback: The new bound on cap sets | Anurag's Math Blog
Pingback: Avi Wigderson’s: “Integrating computational modeling, algorithms, and complexity into theories of nature, marks a new scientific revolution!” (An invitation for a discussion.) | Combinatorics and more
Pingback: To cheer you up in difficult times 7: Bloom and Sisask just broke the logarithm barrier for Roth’s theorem! | Combinatorics and more
Pingback: Péter Pál Pach and Richárd Palincza: a Glimpse Beyond the Horizon | Combinatorics and more
Pingback: Barnabás Janzer: Rotation inside convex Kakeya sets | Combinatorics and more