The polymath blog

January 20, 2014

Two polymath (of a sort) proposed projects

Filed under: discussion,polymath proposals — Gil Kalai @ 5:20 pm
Tags: , ,

This post is meant to propose and discuss a polymath project and a sort of polymath project.

I. A polymath proposal: Convex hulls of real algebraic varieties.

One of the interesting questions regarding the polymath endeavor was:

Can polymath be used to develop a theory/new area?

My idea is to have a project devoted to develop a theory of “convex hulls of real algebraic varieties”. The case where the varieties are simply a finite set of points is a well-developed area of mathematics – the theory of convex polytopes, but the general case was not studied much. I suppose that for such a project the first discussions will be devoted to raise questions/research directions. (And mention some works already done.)

In general (but perhaps more so for an open-ended project), I would like to see also polymath projects which are on longer time scale than existing ones but perhaps less intensive, and that people can “get in” or “spin-off” at will in various times.

II. A polymath-of-a-sort proposal: Statements about the Riemann Hypothesis

The Riemann hypothesis is arguably the most famous open question in mathematics. My view is that it is premature to try to attack the RH by a polymath project (but I am not an expert and, in any case, a project of this kind is better conducted with some specific program in mind). I propose something different. In a sort of polymath spirit the project I propose invite participants, especially professional mathematicians who thought about the RH over the years,  to share their thoughts about RH.

Ideally each comment will be

1) One or a few paragraphs long

2) Well-thought, focused and rather polished

A few comments by the same contributors are also welcome.

To make it clear, the thread I propose is not going to be a research thread and also not a place for further discussions beyond some clarifying questions. Rather it is going to be a platform for interested mathematician to make statements and expressed polished thoughts about RH. (Also, if adopted, maybe we will need a special name for such a thing.)

____________________

This thread is not launching any of the two suggested projects, but rather a place to discuss further these proposals. For the second project,  it will be better still if the person who runs it will be an expert in the area, and certainly not an ignorant. For the first project, maybe there are better ideas for areas/theories appropriate for polymathing.

June 9, 2012

Polymath7 discussion thread

Filed under: discussion,hot spots — Terence Tao @ 5:50 am

The “Hot spots conjecture” proposal has taken off, with 42 comments as of this time of writing.  As such, it is time to take the proposal to the next level, by starting a discussion thread (this one) to hold all the meta-mathematical discussion about the proposal (e.g. organisational issues, feedback, etc.), and also starting a wiki page to hold the various facts, strategies, and bibliography around the polymath project (which now is “officially” the Polymath7 project).

I’ve seeded the wiki with the links and references culled from the original discussion, but it was a bit of a rush job and any editing would be greatly appreciated.  From past polymath experience, these projects can get difficult to follow from the research threads alone once the discussion takes off, so the wiki becomes a crucial component of the project as it can be used to collate all the progress made so far and make it easier for people to catch up.  (If the wiki page gets more complicated, we can start shunting off some stuff into sub-pages, but I think it is at a reasonable size for now.)

One thing I see is that not everybody who has participated knows how to make latex formatting such as \Delta u = \lambda u appear in their comments.  The instructions for that (as well as a “sandbox” to try out the code) are at this link.

Once the research thread gets long enough, we usually start off a new thread (with some summaries of the preceding discussion) to make it easier to keep the discussion at a manageable level of complexity; traditionally we do this at about the 100-comment mark, but of course we can alter this depending on how people are able to keep up with the thread.

March 9, 2011

Polymath discussion at IAS

Filed under: discussion — Gil Kalai @ 2:26 pm
Tags: , ,

In October 2010 there was a discussion about polymath projects at an event organized by the I.A.S in NYC. Tim Gowers described the endeavor and some prospects, and hopes, and Peter Sarnak responded with some concerns. An interesting discussion followed. Some of the discussion is described in the IAS Institute Letter for fall 2010 .

June 29, 2010

Draft version of polymath4 paper

Filed under: discussion,finding primes — Terence Tao @ 8:36 pm

I’ve written up a draft version of a short paper giving the results we already have in the finding primes project.  The source files for the paper can be found here.

The paper is focused on what I think is our best partial result, namely that the prime counting polynomial \sum_{a < p < b} t^p \hbox{ mod } 2 has a circuit complexity of O(x^{1/2-c+o(1)}) for some absolute constant c>0 whenever 1 < a < b < x and b-a < x^{1/2+c}.  As a corollary, we can compute the parity of the number of primes in the interval [a,b] in time O(x^{1/2-c+o(1)}).

I’d be interested in hearing the other participants opinions about where to go next.  Ernie has suggested that experimenting with variants of the algorithm could make a good REU project, in which case we might try to wrap up the project with the partial result and pass the torch on.

July 28, 2009

Deterministic way to find primes: discussion thread

Filed under: discussion,finding primes — Terence Tao @ 3:09 pm

The proposal “deterministic way to find primes” is not officially a polymath yet, but is beginning to acquire the features of one, as we have already had quite a bit of interesting ideas.  So perhaps it is time to open up the discussion thread a little earlier than anticipated.  There are a number of purposes to such a discussion thread, including but not restricted to:

  1. To summarise the progress made so far, in a manner accessible to “casual” participants of the project.
  2. To have “meta-discussions” about the direction of the project, and what can be done to make it run more smoothly. (Thus one can view this thread as a sort of “oversight panel” for the research thread.)
  3. To ask questions about the tools and ideas used in the project (e.g. to clarify some point in analytic number theory or computational complexity of relevance to the project).  Don’t be shy; “dumb” questions can in fact be very valuable in regaining some perspective.
  4. (Given that this is still a proposal) To evaluate the suitability of this proposal for an actual polymath, and decide what preparations might be useful before actually launching it.

To start the ball rolling, let me collect some of the observations accumulated as of July 28:

  1. A number of potentially relevant conjectures in complexity theory and number theory have been identified: P=NP, P=BPP, P=promise-BPP, existence of PRG, existence of one-way functions, whether DTIME(2^n) has subexponential circuits, GRH, the Hardy-Littlewood prime tuples conjecture, the ABC conjecture, Cramer’s conjecture, discrete log in P, factoring in P.
    1. The problem is solved if one has P=NP, existence of PRG, or Cramer’s conjecture, so we may assume that these statements all fail.  The problem is probably also solved on P=promise-BPP, which is a bit stronger than P=BPP, but weaker than existence of PRG; we currently do not have a solution just assuming P=BPP, due to a difficulty getting enough of a gap in the success probabilities.
      1. Existence of PRG is assured if DTIME(2^n) does not have subexponential circuits (Impagliazzo-Wigderson), or if one has one-way functions (is there a precise statement to this effect?)
    2. Discrete log being in hard (or easy) may end up being a useless hypothesis, since one needs to find large primes before discrete logarithms even make sense.
  2. If the problem is false, it implies (roughly speaking) that all large constructible numbers are composite.  Assuming factoring is in P, it implies the stronger fact that all large constructible numbers are smooth.  This seems unlikely (especially if one assumes ABC).
  3. Besides adding various conjectures in complexity theory or number theory, we have found some other ways to make the problem easier:
    1. The trivial deterministic algorithm for finding k-bit primes takes exponentially long in k in the worst case.  Our goal is polynomial in k.  What about a partial result, such as exp(o(k))?
      1. An essentially equivalent variant: in time polynomial in k, we can find a prime with at least log k digits.  Our goal is k.  Can we find a prime with slightly more  than log k digits?
    2. The trivial probabilistic algorithm takes O(k^2) random bits; looks like we can cut this down to O(k).  Our goal is O(log k) (as one can iterate through these bits in polynomial time).  Can we do o(k)?
    3. Rather than find primes, what about finding almost primes?  Note that if factoring is in P, the two problems are basically equivalent.  There may also be other number theoretically interesting sets of numbers one could try here instead of primes.
  4. At the scale log n, primes are assumed to resemble a Poisson process of intensity 1/log n (this can be formalised using a suitably uniform version of the prime tuples conjecture).  Cramer’s conjecture can be viewed as one extreme case of this principle.  Is there some way to use this conjectured Poisson structure in a way without requiring the full strength of Cramer’s conjecture?  (I believe there is also some work of Granville and Soundarajan tweaking Cramer’s prediction slightly, though only by a multiplicative constant if I recall correctly.)

See also the wiki page for this project.

July 26, 2009

Mock-up discussion thread

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.

Customized Rubric Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 226 other followers