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 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.

July 27, 2009

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.

« Previous Page

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

Follow

Get every new post delivered to your Inbox.

Join 245 other followers