# The polymath blog

## July 27, 2009

### Selecting another polymath project

Filed under: planning — Terence Tao @ 5:55 pm

In a few months (the tentative target date is October), we plan to launch another polymath project (though there may also be additional projects before this date); however, at this stage, we have not yet settled on what that project would be, or even how exactly we are to select it.  The purpose of this post, then, is to begin a sort of pre-pre-selection process, in which we discuss how to organise the search for a new project, what criteria we would use to identify particularly promising projects, and how to run the ensuing discussion or voting to decide exactly which project to begin.  (We think it best to only launch one project at a time, for reasons to be discussed below.)

There are already a small number of polymath projects being proposed, and I expect this number to grow in the near future.  Anyone with a problem which is potentially receptive to the polymath approach, and who is willing to invest significant amounts of time and effort to administrate and advance the effort, is welcome to make their own proposal, either in their own forum, or by contacting one of us.  (If you do make a proposal on your own wordpress blog, put it in the category “polymath proposals” so that it will be picked up by the above link.)    There is already some preliminary debate and discussion at the pages of each of these proposals, though one should avoid any major sustained efforts at solving the problem yet, until the participants for the project are fully assembled and prepared, and the formal polymath threads are ready to launch.

[One lesson we got from the minipolymath feedback was that one would like a long period of lead time before a polymath project is formally launched, to get people prepared by reading up and allocating time in advance.    So it makes sense to have the outlines of a project revealed well in advance, though perhaps the precise details of the project (e.g. a compilation of the proposer’s own thoughts on the problem) can wait until the launch date.]

On the other hand, we do not want to launch multiple projects at once.  So far, the response to each new launched project has been overwhelming, but this may not always be the case in the future, and in particular simultaneous projects may have to compete with each other for attention, and perhaps most crucially, for the time and efforts of the core participants of the project.  Such a conflict would be particularly acute for projects that are in the same field, or in related fields.  (In particular, we would like to diversify the polymath enterprise beyond combinatorics, which is where most of the existing projects lie.)

So we need some way to identify the most promising projects to work on.  What criteria would we look for in a polymath project that would indicate a high likelihood of full or partial success, or at least a valuable learning experience to aid the organisation of future projects of this type?  Some key factors come to mind:

1. The amount of expected participation. The more people who are interested in participating, both at a casual level and at a more active full time level, the better the chances that the project will be a success.  We may end up polling readers of this blog for their expected participation level (no participation, observation only, casual participation, active participation, organiser/moderator) for each proposed project, to get some idea as to the interest level.
2. The feasibility of the project. I would imagine that a polymath to solve the Riemann Hypothesis will be a spectacular and frustrating fiasco; we should focus on problems that look like some progress can be made.  Ideally, there should be several potentially promising avenues of inquiry identified in advance; simply dumping the problem onto the participants with no suggestions whatsoever (as was done with the minipolymath project) seems to be a suboptimal way to proceed.
3. The flexibility of the project. This is related to point #2; it may be that the problem as stated is beyond the ability of the polymath effort, but perhaps some interesting variant of the problem is more feasible.  A problem which allows for a number of variations would be more suitable for a polymath effort, especially since polymath projects seem particularly capable of pursuing multiple directions of attack at once.
4. The available time and energy of the administrator. Another thing we learned from the minipolymath project was that these projects need one or more active leaders who are willing to take the initiative and push the project in the directions it needs to go (e.g. by encouraging more efforts at exposition when the flood of ideas become too chaotic).  The proposer of a project would be one obvious choice for such a leader, but there seems to be no reason why a project could have multiple such leaders (and any given participant could choose to seize the initiative and make a major push to advance the project unilaterally).
5. The barriers to entry. Some projects may require a substantial amount of technical preparation before participation; this is perhaps one reason why existing projects have been focused on “elementary” fields of mathematics, such as combinatorics.  Nevertheless, it should be possible (perhaps with some tweaking of the format) to adapt these projects to more “sophisticated” mathematical fields.  For instance, one could imagine a polymath project which is not aimed at solving a particular problem per se, but is instead trying to understand a difficult mathematical topic (e.g. quantum field theory, to pick a subject a random) as thoroughly as possible.  Given the right leadership, and sufficient interest, this very different type of polymath project could well be a great success.
6. Lack of conflict with existing research. It has been pointed out that one should be careful not to let a polymath project steamroll over the existing research plans of some mathematician (e.g. a grad student’s thesis).  This is one reason why we are planning an extended process to select projects, so that such clashes can be identified as early as possible, presumably removing that particular project from contention.  (There is also the danger that even a proposal for a polymath project may deter other mathematicians from pursuing that problem by more traditional means; this is another point worth discussing here.)

Over to the other readers of this blog: what else should we be looking for in a polymath project?  How quickly should we proceed with the selection process?  Should we decide by popular vote, or by some fixed criteria?

### Proposal: Boshernitzan’s problem

Filed under: polymath proposals — Terence Tao @ 2:32 am

Another proposal for a polymath project is the following question of Michael Boshneritzan:

Question. Let $x_1, x_2, x_3, \ldots \in {\Bbb Z}^d$ be a (simple) path in a lattice ${\Bbb Z}^d$ which has bounded step sizes, i.e. $0 < |x_{i+1}-x_i| < C$ for some C and all i.  Is it necessarily the case that this path contains arbitrarily long arithmetic progressions, i.e. for each k there exists $a, r \in {\Bbb Z}^d$ with r non-zero such that $a, a+r, \ldots, a+(k-1)r \in \{x_1,x_2,x_3,\ldots\}$.

The d=1 case follows from Szemerédi’s theorem, as the path has positive density.  Even for d=2 and k=3 the problem is open.  The question looks intriguingly like the multidimensional Szemerédi theorem, but it is not obvious how to deduce it from that theorem.  It is also tempting to try to invoke the Furstenberg correspondence principle to create an ergodic theory counterpart to this question, but to my knowledge this has not been done.  There are also some faint resemblances to the angel problem that has recently been solved.

In honour of mini-polymath1, one could phrase this problem as a grasshopper trying to jump forever (with bounded jumps) in a square lattice without creating an arithmetic progression (of length three, say).

It is also worth trying to find a counterexample if C, d, k are large enough.  Note that the continuous analogue of the problem is false: a convex curve in the plane, such as the parabola $\{ (x,x^2): x \in {\Bbb R}\}$, contains no arithmetic progressions, but is rectifiable.  However it is not obvious how to discretise this example.

In short, there seem to be a variety of tempting avenues to try to attack this problem; it may well be that many of them fail, but the reason for that failure should be instructive.

Andrew Mullhaupt informs me that this question would have applications to short pulse rejected Boolean delay equations.

### Proposal: deterministic way to find primes

Filed under: finding primes,polymath proposals,research — Terence Tao @ 2:24 am

Here is a proposal for a polymath project:

Problem. Find a deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k.  You may assume as many standard conjectures in number theory (e.g. the generalised Riemann hypothesis) as necessary, but avoid powerful conjectures in complexity theory (e.g. P=BPP) if possible.

The point here is that we have no explicit formulae which (even at a conjectural level) can quickly generate large prime numbers.  On the other hand, given any specific large number n, we can test it for primality in a deterministic manner in a time polynomial in the number of digits (by the AKS primality test).  This leads to a probabilistic algorithm to quickly find k-digit primes: simply select k-digit numbers at random, and test each one in turn for primality.  From the prime number theorem, one is highly likely to eventually hit on a prime after about O(k) guesses, leading to a polynomial time algorithm.  However, there appears to be no obvious way to derandomise this algorithm.

Now, given a sufficiently strong pseudo-random number generator – one which was computationally indistinguishable from a genuinely random number generator – one could derandomise this algorithm (or indeed, any algorithm) by substituting the random number generator with the pseudo-random one.  So, given sufficiently strong conjectures in complexity theory (I don’t think P=BPP is quite sufficient, but there are stronger hypotheses than this which would work), one could solve the problem.

Cramer conjectured that the largest gap between primes in [N,2N] is of size $O( \log^2 N )$.  Assuming this conjecture, then the claim is easy: start at, say, $10^k$, and increment by 1 until one finds a prime, which will happen after $O(k^2)$ steps.  But the only real justification for Cramer’s conjecture is that the primes behave “randomly”.  Could there be another route to solving this problem which uses a more central conjecture in number theory, such as GRH? (Note that GRH only seems to give an upper bound of $O(\sqrt{N})$ or so on the largest prime gap.)

My guess is that it will be very unlikely that a polymath will be able to solve this problem unconditionally, but it might be reasonable to hope that it could map out a plausible strategy which would need to rely on a number of not too unreasonable or artificial number-theoretic claims (and perhaps some mild complexity-theory claims as well).

Note: this is only a proposal for a polymath, and is not yet a fully fledged polymath project.  Thus, comments should be focused on such issues as the feasibility of the problem and its suitability for the next polymath experiment, rather than actually trying to solve the problem right now. [Update, Jul 28: It looks like this caution has become obsolete; the project is now moving forward, though it is not yet designated an official polymath project.  However, because we have not yet fully assembled all the components and participants of the project, it is premature to start flooding this thread with a huge number of ideas and comments yet.  If you have an immediate and solidly grounded thought which would be of clear interest to other participants, you are welcome to share it here; but please refrain from working too hard on the problem or filling this thread with overly speculative or diverting posts for now, until we have gotten the rest of the project in place.]

See also the discussion thread for this proposal, which will also contain some expository summaries of the comments below, as well as the wiki page for this proposal, which will summarise partial results, relevant terminology and literature, and other resources of interest.

## July 26, 2009

Filed under: discussion,mock-up — Terence Tao @ 8:06 pm

This is a mockup of what a discussion thread for a polymath project would look like; it would run alongside the research thread, but is focused on strategy, exposition, and discussion by casual participants, as opposed to the more cutting edge research conducted by more active participants in the research thread.

Please feel free to make suggestions in this thread as to how the format and organisation of these projects (or this blog) could be improved.

Filed under: mock-up,research — Terence Tao @ 7:27 pm

This is a mock-up of what a research thread for a polymath project would look like.  The thread would begin with a statement of the research problem, e.g.

Problem (Boundedness of the trilinear Hilbert transform). Show that the trilinear Hilbert transform $T(f,g,h) := p.v. \int_{-\infty}^\infty f(x+t) g(x+2t) h(x+3t) \frac{dt}{t}$ is bounded from $L^{p_1}({\Bbb R}) \times \ldots \times L^{p_3}({\Bbb R}) \to L^p({\Bbb R)}$ for some $p_1,p_2,p_3,p$ (e.g. $p_1=p_2=p_3=4$ and $p_4 = 4/3$).

Some discussion of the precise objective (are we aiming for an actual proof, or would we be happy with understanding why the problem is difficult?) would go here.  [Note: while the above problem is an important open problem in harmonic analysis, I am not actually proposing to solve it by polymath here; it is only being used as an example for the purposes of this mock-up.]

A brief discussion of prior results would also be appropriate here, though an extended bibliography might be better placed on the wiki.

A reminder of the polymath rules might also be placed here, together with a link to the discussion thread for issues relating to exposition, strategy, and other meta-comments.  The initiator of the project should also put some effort into laying down preliminary thoughts of the project as clearly as possible.

All threads in a polymath project would have a dedicated category; in this case, the category is mock-up.

Finally, one should put a list of moderators of the project, who would be able to respond to technical issues, such as fixing up a mangled comment.  For this mock-up project, the moderators are:

• Terence Tao (tao@math.ucla.edu)
« Previous Page

The Rubric Theme. Blog at WordPress.com.