# What Is Research?

## October 26, 2009

### Polymath again

Filed under: Culture and society of research — vipulnaik @ 10:42 pm
Tags:

Timothy Gowers and Michael Nielsen have written an article for Nature magazine about the polymath project (I blogged about this here and here).

In the meantime, Terence Tao started a polymath blog here, where he initiated four discussion threads (1, 2, 3 and 4) on deterministic ways to find primes (I’m not quite sure how that’s proceeding — the last post was on August 28, 2009). (UPDATE: A new post (thread 5) was put up shortly after I published my blog post).

Around the same time, Gil Kalai started a polymath on the polynomial Hirsch conjecture (1, 2, 3, 4 and 5).

Also, some general discussion posts on polymath projects: by Tim Gowers and by Terence Tao.

It remains to be seen whether any of these projects are able to reach successful conclusions or make substantial inroads into the problem. If there is another success for a polymath project, then that would be a major booster to the idea of polymath projects. Otherwise, it might raise the question of whether the unexpected degree of success of the first polymath project led by Gowers (which aimed for, and got, an elementary proof of the density Hales-Jewett theorem) was an anomaly.

1. The last post in thread four of the discussion of finding primes is on October 26th, the august 28th date is from the header of thread 4 it is the date in which the thread started there are over 60 comments after that.

Comment by Kristal Cantwell — October 27, 2009 @ 4:33 pm

2. I would like to point out some differences between this problem (Polymath 4 — finding primes) and the other polymath projects, especially the one on the Density Hales-Jewett problem:

1. With DHJ (Polymath 1), there was already one proof known, and then the problem was whether one could produce a combinatorial proof as well. Knowing that a problem already has a solution helps to guide the development of other approaches (e.g. combinatorial); and it also has the psychological effect of making one think it is doable, and therefore one is not as willing to give up so easily.

2. With Polymath 4 we have had *much* fewer contributors. Perhaps this is a matter of taste — people who regularly contribute to polymath projects tend to be more focused on combinatorics and computational complexity; yet Polymath 4 is more a problem in computational number theory, which tends to use ideas of a different flavor.

3. There doesn’t seem to be as many avenues from which to attack Polymath 4 as there are other problems. Many analytic approaches to the problem, for example, can be boiled down to certain problems about bounds on something called “Dirichlet polynomials”, and it is known to be a hard general problem to beat something called the “square-root barrier” for such approaches. Though, I do think that we have a viable approach for doing this by computing certain generating functions in $F_2[x]$ (which is not what one would call an `analytic method’ — it is more algebraic… it has been the subject of the last tens of posts to Polymath 4).

Also note that Polymath 4 is not over yet! I think there is a very good chance of producing an algorithm to find primes of size $n$ (i.e. $log(n)/log(2)$ bits) in time better than $n^{0.499}$ (bit operations), perhaps assuming some “reasonable” conjectures in linear algebra. While this may not seem like much, if it could be achieved, it would beat “Odlyzko’s algorithm”, the current record-holder. I would consider that a “success” for Polymath 4, and a good place for the project to stop.

Comment by Ernie Croot — October 27, 2009 @ 10:15 pm

3. @Kristal: Thanks for your comment. I am aware that people can continue commenting and the comment thread can remain active forever — however, the absence of a blog post summarizing latest achievements appears to indicate that concrete progress hasn’t yet been made. It appears, though, that after I put up my blog post, a new post was put up starting Thread 5, and I’ve updated my blog post to reflect that.

@Ernie: You’re right — I know that in these kind of problems, even a slight improvement over the best bound is usually considered worthwhile, so I agree with you that if such a breakthrough is achieved, that would constitute success. Even if it takes several more months to achieve the breakthrough, that would still be pretty impressive and provide strong indications that the polymath strategy may be a replicable strategy for producing original research. Unfortunately, this isn’t my area of mathematical expertise, so looking at the comments, I cannot judge for myself how likely it is that the goals you state will be achieved.

Comment by vipulnaik — October 27, 2009 @ 11:43 pm

The Rubric Theme. Blog at WordPress.com.