Whither Polymath?

Over at the Polymath blog, Gil Kalai recently proposed a discussion about possible future Polymath projects. This post is partly to direct you to that discussion in case you haven’t noticed it and might have ideas to contribute, and partly to start a specific Polymathematical conversation. I don’t call it a Polymath project, but rather an idea I’d like to discuss that might or might not become the basis for a nice project. One thing that Gil and others have said is that it would be a good idea to experiment with various different levels of difficulty and importance of problem. Perhaps one way of getting a Polymath project to take off is to tackle a problem that isn’t necessarily all that hard or important, but is nevertheless sufficiently interesting to appeal to a critical mass of people. That is very much the spirit of this post.

Before I go any further, I should say that the topic in question is one about which I am not an expert, so it may well be that the answer to the question I’m about to ask is already known. I could I suppose try to find out on Mathoverflow, but I’m not sure I can formulate the question precisely enough to make a suitable Mathoverflow question, so instead I’m doing it here. This has the added advantage that if the question does seem suitable, then any discussion of it that there might be will take place where I would want any continuation of the discussion to take place.

Polymath6: A is to B as C is to ???

The Polymath experiment is still very much in its infancy, with the result that we still have only a rather hazy idea of what the advantages and disadvantages are of open online multiple collaboration. It is easy to think of potential advantages and disadvantages, but the more actual experience we can draw on, the more we will get a feel for which of these plausible speculations are correct.

In my last post but one I outlined a few thoughts about the cap-set problem. Although this wasn’t meant as the beginning of a Polymath project (as I said in the post, it was modelled more on Gil Kalai’s notion of an “open discussion”), it had something in common with such projects, to the point where one of the worries people have about the Polymath approach actually occurred: I suggested a line of attack that was, unbeknownst to me, actively being pursued by somebody.

I do not know exactly what calculations went on in the minds of Michael Bateman and Nets Katz when they decided to go public with their ideas before they had fully worked them out, but my guess is that they wanted to establish that they had got there first. This they did by the very effective method of explaining that the simple observations that I had made were much weaker than what they already knew how to prove. As it happens, the story has had a happy ending for them, since they managed, soon after posting their comments, to push their ideas to the point where they have obtained the first improvement to the Roth/Meshulam bound, something that many people have wanted to do for a long time.

Polymath3 now active

After a long initial discussion period, Polymath3, a project on Gil Kalai’s blog that aims to solve the polynomial Hirsch conjecture, has now started as an active research project. There is already quite a lot of material on his blog, and soon some of it should have migrated to a wiki, which will be a good place to get up to speed on the basics. I will update this post from time to time with news of how the project is going.

Something that is maybe worth pointing out is that although the problem looks at first as though you need to know all sorts of facts about convexity, there is a very nice purely combinatorial statement (about set systems) that would imply the conjecture. So there is no excuse not to think about it …

Polymath news

If you haven’t already spotted this, you might like to know that Scott Aaronson has just posed a very interesting unsolved combinatorial problem and invited Polymath-style thoughts on it. I’ll give a quick and I hope appetite-whetting account of the problem here, but you could skip it if you want and jump straight to his posts on his blog and at Mathoverflow.

The problem is completely elementary, but it has consequences of great interest to theoretical computer scientists. As Scott says, it also seems to be at a realistic level of difficulty and highly suitable for a Polymath approach. (The first assertion is a coded way of saying that it isn’t a notorious “impossible” complexity assertion in disguise.) It asks this. Suppose you colour the points of with two colours in such a way that the origin is red and each of the coordinate axes contains at least one blue point. Do there exist constants , independent of , such that there must be a point that has at least neighbours that are coloured differently from ? At the moment, it seems that there isn’t even a proof that for sufficiently large there must be a point with 100 neighbours of the other colour. There is a non-trivial but not hard example that shows that cannot be more than . (Scott presents this in his Mathoverflow post.) A very brief remark is that if you just assume that not all points are coloured the same way, then the assertion is false: a counterexample is obtained if you colour a point red if its first coordinate is positive and blue otherwise.

Erdős’s discrepancy problem as a forthcoming Polymath project

This is an emergency post, since the number of comments on the previous post about Erdős’s discrepancy problem has become unwieldy while I’ve been away enjoying a bit of sunshine in Luxor. My head is full of amazing details from the walls and columns of ancient Egyptian tombs and temples. The main thing I didn’t see, or at least not until I finally saw them sticking up through the mist from my plane window yesterday morning, was the pyramids, since those are near Cairo. However, I didn’t feel too bad about that as my guide book, the Lonely Planet guide to Egypt, assured me that the pyramids never fail to disappoint (which was just one of many little gems of bad writing in that book).

For the first time for ages, I was completely away from all email and internet for a week, but just before I left, the results of the polls, as they then stood, about the next Polymath project were already suggesting that the Erdős discrepancy problem was the clear favourite, so I couldn’t help thinking about it a certain amount while I was in Egypt. I said that the process of choosing the next problem was not going to be fully democratic, but the fact is that I love the Erdős discrepancy problem and am currently somewhat grabbed by it, so I see no reason to go against such a clear majority, especially as it also has a clear majority of people who say that they are ready to work on it.

The next Polymath project on this blog: some polls

For reasons that I have already gone into, I do not think that the origin-of-life project is suitable as the next Polymath project on this blog, though there seems to be enough enthusiasm for it that I am quite serious about giving it a try at some point in the not too distant future. The complexity-related project also no longer seems such a great idea for now. That leaves three candidates from amongst the problems that I have posted about recently: the project related to the polynomial-DHJ problem, the project related to the Littlewood problem, and the project to solve Erdős’s discrepancy problem. My impression is that for each of these three projects there is already a small group of highly interested people, and certainly my level of enthusiasm for each of these three problems is enough for me to be ready to devote plenty of time to it. (A theory I want to test is that if I post regularly and am not completely stuck, then that will be enough to keep the project feeling active and attracting contributions from other people as well, even if a proof does not appear to be round the corner.)

To help me decide which of the above three problems to go for, here are four polls.

Erdős’s discrepancy problem

I’ve been pretty busy over the last month or so — hence my blog silence — and continue to be busy. But here is one more discussion of a problem that was on my earlier list of possible future Polymath projects. The problem in question is sometimes known as Erdős’s discrepancy problem. This will be a shortish post, because I don’t have much of a programme for solving the problem: if it were adopted, then we would be starting almost from scratch, but that could be an interesting experiment.

Here is the question.

Problem. Is it possible to find a -valued sequence and a constant such that for every and every ?

With the help of a little terminology we can ask this question in a slightly different way. If is a collection of subsets of a set and , define the discrepancy of to be the maximum value of over all . In our case, is the collection of all arithmetic progressions of the special form , and the question is whether there is any function that has bounded discrepancy for this . I say “bounded” rather than “finite” because one can define the function to be the discrepancy of with respect to all those sets in that are subsets of . Then the question is equivalent to asking whether there is any function for which is a bounded function of .

Problems related to Littlewood’s conjecture

This is the third in a series of posts in which I discuss problems that could perhaps form Polymath projects. Again, I am elaborating on a brief discussion that appeared in an earlier post on possible future projects. [Not for the first time in my experience, WordPress’s dates have gone funny and this was posted not on the 17th as it says above but on the 20th.]

An obvious objection to the Littlewood conjecture as a Polymath project is that it is notoriously hard. On its own that might not necessarily be a convincing argument, since part of the point of Polymath is to attempt to succeed where individual mathematicians have failed. However, a second objection is that the best results in the direction of the Littlewood conjecture, due to Einsiedler, Katok and Lindenstrauss, use methods that are far from elementary (and far from understood by me). I envisage this project as an elementary one, at least to begin with, so does that make it completely unrealistic? I shall try to argue in this post that there is plenty that could potentially be done by elementary methods, even if attempting to prove the conjecture itself is probably too ambitious.

Another advantage of tackling the conjecture by elementary means is that if we find ourselves forced to reintroduce the non-elementary methods that have led to the very interesting results of Einsiedler, Katok and Lindenstrauss, we will have a deeper understanding of those methods than if we had just passively learnt about them. I myself prefer to rediscover things than to learn them: it isn’t always practical, but it’s easier if you half bear in mind that they are there and have a vague idea about them.

The first unknown case of polynomial DHJ

In this post I want to discuss a combinatorial problem that is very appealing in its own right, but also important as a potential first step towards solving a central open problem in Ramsey theory. It is the second in a series of three posts (I may add to this number later, but three is what I have written or semi-written so far) that give further details about possible Polymath projects. This one was number 2 in the post in which I first discussed these projects. In that post, I said nothing beyond the fact that the project had close connections with the density Hales-Jewett theorem. Unlike the origin-of-life suggestion, this project is a straightforward mathematical one.

Let me very briefly indicate what the central open problem in Ramsey theory is. The density Hales-Jewett theorem, which has been discussed at great length on this blog, is the assertion that every dense subset of contains a combinatorial line (provided that is large enough in terms of and the density). This implies Szemerédi’s theorem.

Now there is an amazing generalization of Szemerédi’s theorem, due to Bergelson and Leibman, known as the polynomial Szemerédi’s theorem. This is the following assertion. For any and any choice of polynomials with integer coefficients and constant terms equal to zero, there exists such that every subset of size at least contains a subset of the form with . To see that this generalizes Szemerédi’s theorem, just let (unless you feel that is more natural).

Another special case of this theorem is when and . Then one is trying to find a subset of the form , or in other words a pair of elements of that differ by a perfect square. This was proved independently by Sarkozy and Furstenberg, though my favourite proof is a more recent argument due to Ben Green that follows more closely the general structure of Roth’s proof of Roth’s theorem.

An obvious question now arises: is there a generalization of DHJ that implies both DHJ and the polynomial Szemerédi’s theorem? So far, the answer is no, and that is the central problem I was referring to earlier. However, we do at least know the colouring version: that is, there is a colouring statement that simultaneously generalizes the Hales-Jewett theorem and van der Waerden’s theorem. This is a result of Bergelson and McCutcheon — alternative proofs have been given by Mark Walters (who has the shortest and simplest argument) and Saharon Shelah (who has produced a primitive recursive bound).

Polymath and the origin of life

This is the first of a few posts I plan (one other of which is written and another of which is in draft form but in need of a few changes) in which I discuss various Polymath proposals in more detail than I did in my earlier post on possible projects.

One of my suggestions, albeit a rather tentative one, was to try to come up with a model that would show convincingly how life could emerge from non-life by purely naturalistic processes. But before this could become a sensible project it would be essential to have a more clearly defined mathematical question. By that I don’t mean a conjecture that Polymath would be trying to prove rigorously, but rather a list of properties that a model would have to have for it to count as successful. Such a list need not be fully precise, but in my view it should be reasonably precise, so that the task is reasonably well defined. It would of course be possible to change the desiderata as one went along.

In this post I’d like to make a preliminary list. It will undoubtedly be unsatisfactory in many ways, but I hope that there will be a subsequent discussion and that from it a better list will emerge. The purpose of this is not to start a Polymath project, but simply to attempt to define a Polymath proposal that might at some future date be an actual project. For two reasons I wouldn’t want this to be a serious project just yet: it seems a good idea to think quite hard about how it would actually work in practice, and someone who I hope will be a key participant is very busy for the next few months and less busy thereafter.