The polymath blog

July 8, 2010

Minipolymath2 project: IMO 2010 Q5

Filed under: polymath proposals — Terence Tao @ 3:56 pm

This post marks the official opening of the mini-polymath2 project to solve a problem from the 2010 IMO.  I have selected the fifth question (which appears to be slightly more challenging than the sixth, for a change) as the problem to focus on:

Problem. In each of six boxes B_1, B_2, B_3, B_4, B_5, B_6 there is initially one coin. There are two types of operation allowed:
  1. Type 1: Choose a nonempty box B_j with 1 \leq j \leq 5. Remove one coin from B_j and add two coins to B_{j+1}.
  2. Type 2: Choose a nonempty box B_k with 1 \leq k \leq 4. Remove one coin from B_k and exchange the contents of (possibly empty) boxes B_{k+1} and B_{k+2}.
Determine whether there is a finite sequence of such operations that results in boxes B_1, B_2, B_3, B_4, B_5  being empty and box B_6 containing exactly 2010^{2010^{2010}} coins. (Note that a^{b^c} := a^{(b^c)}.)
The comments to this post shall serve as the research thread for the project, in which participants are encouraged to post their thoughts and comments on the problem, even if (or especially if) they are only partially conclusive.  Participants are also encouraged to visit the discussion thread for this project, and also to visit and work on the wiki page to organise the progress made so far.
This project will follow the general polymath rules.  In particular:
  1. All are welcome. Everyone (regardless of mathematical level) is welcome to participate.  Even very simple or “obvious” comments, or comments that help clarify a previous observation, can be valuable.
  2. No spoilers! It is inevitable that solutions to this problem will become available on the internet very shortly.  If you are intending to participate in this project, I ask that you refrain from looking up these solutions, and that those of you have already seen a solution to the problem refrain from giving out spoilers, until at least one solution has already been obtained organically from the project.
  3. Not a race. This is not intended to be a race between individuals; the purpose of the polymath experiment is to solve problems collaboratively rather than individually, by proceeding via a multitude of small observations and steps shared between all participants.   If you find yourself tempted to work out the entire problem by yourself in isolation, I would request that you refrain from revealing any solutions you obtain in this manner until after the main project has reached at least one solution on its own.
  4. Update the wiki. Once the number of comments here becomes too large to easily digest at once, participants are encouraged to work on the wiki page to summarise the progress made so far, to help others get up to speed on the status of the project.
  5. Metacomments go in the discussion thread. Any non-research discussions regarding the project (e.g. organisational suggestions, or commentary on the current progress) should be made at the discussion thread.
  6. Be polite and constructive, and make your comments as easy to understand as possible. Bear in mind that the mathematical level and background of participants may vary widely.

Have fun!

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.

June 12, 2010

Mini-polymath proposal: IMO 2010 Q6

Filed under: news,planning,polymath proposals — Terence Tao @ 11:16 pm

I am proposing the sixth question for the 2010 International Mathematical Olympiad (traditionally, the trickiest of the six problems) as a mini-polymath project for next month.  Details and discussions are in this post on my other blog.

[Update, June 27: the project is scheduled to start on Thursday, July 8 16:00 UTC.]


January 9, 2010

Polymath5: Erdős’s discrepancy problem

Filed under: polymath proposals — Gil Kalai @ 10:56 pm

Is taking place on Gowers’s blog!

December 31, 2009

Proposal (Tim Gowers): Erdos’ Discrepancy Problem

Filed under: polymath proposals — Gil Kalai @ 3:11 pm

For a description of Erdos’ discrepancy problem and a large discussion see this blog on Gowers’s blog.

The decision for the next polymath project over Gowers’s blog will be between three projects: The polynomial DHJ problem, Littlewood problem, and the Erdos discrepency problem. To help making the decision four polls are in place!

November 20, 2009

Proposals (Tim Gowers): Polynomial DHJ, and Littlewood’s problem

Filed under: polymath proposals — Gil Kalai @ 10:06 am

Tim Gowers described two additional proposed polymath projects. One about the first unknown cases of the polynomial Density Hales Jewett problem. Another about the Littelwood’s conjecture.

I will state one problem from each of these posts:

1) (Related to polynomial DHJ) Suppose you have a family \cal F of graphs on n labelled vertices, so that we do not two graphs in the family G,H such that H is a subgraph of G and the edges of G which are not in H form a clique. (A complete graph on 2 or more vertices.) can we conclude that |{\cal F}| =2^{o({{n} \choose {2}}}? (In other words, can we conclude that \cal F contains only a diminishing fraction of all graphs?)

Define the “distance” between two points in the unit cube as the product of the absolute value of the differences in the three coordinates. (See Tim’s remark below.)

2) (Related to Littlewood) Is it possible to find n points in the unit cube [0,1]^3 so that the “distance” between any two of them is at least 1/100000000000000000000n?

A negative answer to Littlewood’s problem will imply a positive answer to problem 2 (with some constant). So the pessimistic saddle thought would be that the answer to Problem 2 is yes without any bearing on Littlewood’s problem.

November 8, 2009

Proposal (Tim Gowers) The Origin of Life

Filed under: polymath proposals — Gil Kalai @ 12:54 pm

Early Earth

 

 

 

 

 

 

 

 

 

A presentation of one possible near future polymath: the mathematics of the origin of life can be found on Gowers’s blog.

October 27, 2009

(Research thread V) Determinstic way to find primes

Filed under: finding primes,research — Terence Tao @ 10:25 pm

It’s probably time to refresh the previous thread for the “finding primes” project, and to summarise the current state of affairs.

The current goal is to find a deterministic way to locate a prime in an interval [z,2z] in time that breaks the “square root barrier” of \sqrt(z) (or more precisely, z^{1/2+o(1)}).  Currently, we have two ways to reach that barrier:

  1. Assuming the Riemann hypothesis, the largest prime gap in [z,2z] is of size z^{1/2+o(1)}.  So one can simply test consecutive numbers for primality until one gets a hit (using, say, the AKS algorithm, any number of size z can be tested for primality in time z^{o(1)}.
  2. The second method is due to Odlyzko, and does not require the Riemann hypothesis.  There is a contour integration formula that allows one to write the prime counting function \pi(z) up to error z^{1+o(1)}/T in terms of an integral involving the Riemann zeta function over an interval of length O(T), for any 1 \leq T \leq z.  The latter integral can be computed to the required accuracy in time about z^{o(1)} T.  With this and a binary search it is not difficult to locate an interval of width z^{1+o(1)}/T that is guaranteed to contain a prime in time z^{o(1)} T.  Optimising by choosing T = z^{1/2} and using a sieve (or by testing the elements for primality one by one), one can then locate that prime in time z^{1/2+o(1)}.

Currently we have one promising approach to break the square root barrier, based on the polynomial method, but while individual components of this approach fall underneath the square root barrier, we have not yet been able to get the whole thing below (or even matching) the square root.  I will sketch the approach (as far as I understand it) below; right now we are needing some shortcuts (e.g. FFT, fast matrix multiplication, that sort of thing) that can cut the run time further.

(more…)

October 16, 2009

Nature article on Polymath

Filed under: news — Terence Tao @ 4:25 pm

Timothy Gowers and Michael Nielsen have written an article “Massively collaborative mathematics“, focusing primarily on the first Polymath project, for the October issue of Nature.

August 28, 2009

(Research Thread IV) Determinstic way to find primes

Filed under: finding primes,research — Terence Tao @ 1:43 am
Tags:

This post will be somewhat abridged due to my traveling schedule.

The previous research thread for the “finding primes” project is now getting quite full, so I am opening up a fresh thread to continue the project.

Currently we are up against the “square root barrier”: the fastest time we know of to find a k-digit prime is about \sqrt{10^k} (up to \exp(o(k)) factors), even in the presence of a factoring oracle (though, thanks to a method of Odlyzko, we no longer need the Riemann hypothesis).  We also have a “generic prime” razor that has eliminated (or severely limited) a number of potential approaches.

One promising approach, though, proceeds by transforming the “finding primes” problem into a “counting primes” problem.  If we can compute prime counting function \pi(x) in substantially less than \sqrt{x} time, then we have beaten the square root barrier.

Currently we have a way to compute the parity (least significant bit) of \pi(x) in time x^{1/2+o(1)}, and there is hope to improve this (especially given the progress on the toy problem of counting square-frees less than x).  There are some variants that also look promising, for instance to work in polynomial extensions of finite fields (in the spirit of the AKS algorithm) and to look at residues of \pi(x) in other moduli, e.g. \pi(x) mod 3, though currently we can’t break the x^{2/3+o(1)} barrier for that particular problem.

Next Page »

Blog at WordPress.com.