An Open Discussion and Polls: Around Roth’s Theorem

Suppose that R_n is a subset of \{1,2,\dots, n \} of maximum cardinality not containing an arithmetic progression of length 3. Let g(n)=n/|R_n|.

How does g(n) 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 g(n) \ge log logn. Szemeredi and Heath-Brown improved it to g(n) \ge log^cn  for some c>0 (Szemeredi’s argument gave c=1/4.) Jean Bourgain improved the bound in 1999 to c=1/2 and recently to c=2/3 (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 n^c.  Salem and Spencer improved this bound to g(n) \le e^{logn/ loglogn}. Behrend’s upper bound from 1946 is of the form g(n) \le e^{C\sqrt {\log n}}. 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 \Gamma=\{0,1,2\}^n. It is called the cap set problem. A subset of \Gamma 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 A is a cap set of maximum size we can ask how the function h(n)=3^n/|A| behaves. Roy Meshulam proved, using Roth’s argument, that h(n) \ge n. Edell found an example of a cap set of size 2.2^n. So h(n) \le (3/2.2)^n. 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.

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 3^n/d(n) of a subset of \{0,1,2\}^n without a combinatorial line. The recent proofs appears to lead to d(n) \ge \log*n. 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… 

25 thoughts on “An Open Discussion and Polls: Around Roth’s Theorem

  1. gowers

    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.

  2. juliawolf

    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.

  3. Gil Kalai Post author

    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.

  4. Gil Kalai Post author

    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.

  5. Pingback: Polymath1: Success! « Combinatorics and more

  6. Ewan

    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
    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.


  7. Boris

    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,

  8. Jason Dyer

    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?

  9. Gil Kalai Post author

    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 3^n/n bound would be closely related to improving the bounds for Roth’s theorem beyond n/\log n. However, the cap set problem looks technically much easier and “cleaner”.

  10. Anonymous

    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?

  11. Jason Dyer

    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.

  12. Gil Kalai Post author

    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 (3-a)^n will also believe that the truth for Roth’s theorem is near the Behrend bound – n/exp (\log ^cn).

    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 (3-a)^n, but others may think that there is still a Behrend-type construction that we missed for the cap set problem, so the truth is 3^n/exp (n^c) (c<1).

    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 (3-a)^n. Nobody expected the answer to be 3^n/exp (n^c). 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 n/(log n)^c for some c and 3 even voted (against the Erdos-Turan conjecture) for c<1.

    (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.

  13. Gil Kalai Post author

    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)

    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 \{0,1\}^n 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 n^{-\alpha} for \alpha=1/5 or so. A conjecture by Benny Chor asserts that c=0.999^n 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 n^{-\beta} for every \beta 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 )

    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.

  14. Gil Kalai Post author

    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 \{x+epsilon_1 y_1+ \epsilon_2y_2+\dots\epsilon_ky_k\} 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 n^\alpha 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.

  15. Gil Kalai Post author

    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.

  16. Pingback: Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier | Combinatorics and more

  17. Pingback: What is difficult about the cap-set problem? « Gowers's Weblog

  18. Pingback: The Cap-Set Problem and Frankl-Rodl Theorem (C) | Combinatorics and more

  19. Pingback: A Couple Updates on the Advances-in-Combinatorics Updates | Combinatorics and more

  20. Cowadodcals

    (Reuters) : The European Central Bank waved their big fireplace hose on blazing bond markets, then fired up a weak sprinkler.

    Unsurprisingly, the flame refused to go out. Indeed, the fires grew higher, licking the feet of Madeira and The world, the foreign currency area’s third and fourth largest economic climates.

    Three days and nights later, the bank’s regulating council decided in a emergency Sunday night meeting call to improve course easily and resort on the big hearth hose in the end.

    The ECB may now end up being the reluctant manager of tens of billions of euros in Italian and also Spanish debt in a high-risk strategy to avert a new European monetary meltdown.

    It wasn’t the first time since this euro zone’s sovereign debt woes began in late 2009 how the guardians associated with Europe’s projetos de moveis solitary currency were being forced by events into a U-turn.

    The hesitant reaction to the latest and quite a few dangerous turn in the dilemma illustrates the way political restrictions are rendering it ever more challenging for Europe to find effective solutions.

    The 17-nation dollar area is lacking in a lender of very last resort, and it is politicians in addition to central bankers carry on and argue around who, in case anyone, ought to play of which role.

    European frontrunners thought that they had erected the firewall with a July twenty one emergency peak by agreeing on a second bailout with regard to Greece, the weakest link in the euro sequence, and granting new steps to counteract contagion to other countries.

    Yet following a 24-hour comfort rally, traders gave the complex deal the thumbs-down, judging this insufficient to avoid the rot, and spying some sort of window connected with vulnerability prior to measures got effect.

    Facing a massive selloff regarding Italian in addition to Spanish debt that was forcing individuals countries’ asking for costs upwards towards unsustainable levels, the ECB chose last Thursday to acquire small levels of Irish and also Portuguese provides only.

    “What would we label of a fireplace brigade in which responds with a major emergency but drives on the wrong position and refuses to turn all-around and douse the actual fire? inches asked economist Holger Schmieding regarding Germany’s Berenberg Bank.

    There were three possible causes of the peculiar decision, which often ECB president Jean-Claude Trichet proclaimed without their usual guarantee:

    – any dissenting minority for the bank’s governing council opposed to any bond-buying is growing from one this past year to four in the 23 members yesterday, ECB options say;

    – most ECB policymakers considered Italy had to do much more to fit its community finances in order and liberalise its sclerotic economic climate before it deserved virtually any support;

    : and at any rate, the ECB desired euro sector governments to look at over the burden of purchasing risky bonds making use of their own saving fund, which ECB options say central bankers believe needs to be at minimum doubled in space to fit the idea.

    By selecting a half-measure, your ECB on purpose or by accident heightened connect market strain on Ancient rome and Madrid. The downgrading the United States’ credit ratings last Exclusive did the others.

    Without decisive action because of the central financial institution, the european zone situation was collection to spiral spinning out of control on Friday morning, WESTERN EUROPEAN officials contracted in frantic weekend phone consultations.

    Beneath fierce stress from his European mates, Italian Primary Minister Silvio Berlusconi predetermined hastily upon Friday to bring forward spending budget balancing measures by the year in order to 2013.

    He likewise pledged to anchor any balanced budget rule inside the constitution and to push through long-deferred reforms on the welfare system and time markets soon after talks with trade unions in addition to employers.

    Seasoned Italy-watchers are sceptical connected with such obscure promises by way of a shaky federal to “fast-track” reforms by using a fractious parliament, where Berlusconi’s specialist is waning because he holds trial intended for alleged sham and sex which has a minor.

    Some key bankers thought that making Italy in order to twist within the wind a lttle bit longer at the mercy of bond current market vigilantes could concentrate minds in The italian capital on finally breaking this habits of an lifetime.

    That’s before Regular & Poor’s lobbed a new hand grenade to the markets by simply downgrading the particular United States’ AAA credit history to AA+ using a negative prospect on Fri, sending perhaps the strongest tremors throughout the global financial system since this 2008 collapse of Lehman Siblings.

    The ECB has now been forced in to a major dedication, which the idea insists is actually temporary, to purchase Italian as well as Spanish bonds to stabilise areas.

    Euro zone leaders decided last month to permit their 440-billion-euro Eu Financial Steadiness Facility to acquire bonds around the secondary marketplace under strict conditions in order to give precautionary loans to countries with difficulty.

    But those brand new powers will not apply until national parliaments agree the alterations, probably with late Sept. Moreover, the two leading euro zone countries, Germany and France, don’t would like to increase this EFSF’s size away from concern with regards to own budget.

    To convenience the ECB’s insurance plan shift, German Chancellor Angela Merkel in addition to French Chief executive Nicolas Sarkozy promised how the EFSF would undertake responsibility pertaining to bond-buying from the secondary market when its fresh powers were in force.

    But markets might not be convinced that either institution has got the political stamina along with the financial fire-power for you to shield France durably by danger unless it achieves an dubious twin

    alteration to monetary discipline as well as economic expansion.

    Critics point out past ECB bond-buying has experienced only short-lived calming side effects and did not prevent A holiday in greece, Ireland or even Portugal via requiring bailouts.

    “Over period, we think that ongoing marketing pressure will probably force the particular ECB/EFSF to be able to eventually hold close to half of the traded Italian and Spanish debt as well as around 850 thousand euros, ” economists at RBS financial institution said in a research note.

    Such a tremendous holding connected with southern countries’ credit card debt could total a de facto mutualisation regarding euro region debt risk, potentially increasing a political backlash throughout northern The european countries.

    Even if your fire subsides for now, prepare regarding more blazes.

  21. Pingback: Cup Sets, Sunflowers, and Matrix Multiplication | Combinatorics and more

  22. ALindsayE

    Hello every one i want propose you some of service.
    If you go to London on tourism, and you want to escort with nice girl.
    Our escort agency Caprice help you
    All model you can see in our site
    We have a wide range of models
    See our offers on the site below

    Elite London escort –


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s