For the time being this is an almost empty post, the main purpose of which is to provide a space for mathematical comments connected with the project of assessing whether it is possible to use the recent ideas of Sanders and of Bateman and Katz to break the barrier in Roth’s theorem. (In a few hours’ time I plan to write a brief explanation of what one of the main difficulties seems to be.)
Added later. Tom Sanders made the following remarks as a comment. It seems to me to make more sense to have them as a post, since they are a good starting point for a discussion. So I have taken the liberty of upgrading the comment. Thus, the remainder of this post is written by Tom.
This will hopefully be an informal post on one aspect of what we might need to do to translate the Bateman-Katz work into the setting.
One of the first steps in the Bateman-Katz argument is to note that if is a cap-set (meaning it is free of three-term progressions) of density then we can assume that there are no large Fourier coefficients, meaning
They use this to develop structural information about the large spectrum, , which consequently has size between and . This structural information is then carefully analysed in the `beef’ of the paper. (more…)
After some discussion and a lengthy hiatus, the Polymath3 project (on attacking the polynomial Hirsch conjecture via combinatorial means) has officially started with a new research thread on Gil Kalai’s blog (which, for now, can also double as the discussion thread, given that the activity level is still quite low), and a Polymath wiki page.
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:
In each of six boxes
there is initially one coin. There are two types of operation allowed:
- Type 1: Choose a nonempty box with . Remove one coin from and add two coins to .
- Type 2: Choose a nonempty box with . Remove one coin from and exchange the contents of (possibly empty) boxes and .
Determine whether there is a finite sequence of such operations that results in boxes
being empty and box
coins. (Note that
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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
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.]
Is taking place on Gowers’s blog!
Comments Off on Polymath5: Erdős’s discrepancy problem
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!
Comments Off on Proposal (Tim Gowers): Erdos’ Discrepancy Problem
A presentation of one possible near future polymath: the mathematics of the origin of life can be found on Gowers’s blog.
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 in time that breaks the “square root barrier” of (or more precisely, ). Currently, we have two ways to reach that barrier:
- Assuming the Riemann hypothesis, the largest prime gap in is of size . 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 .
- 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 up to error in terms of an integral involving the Riemann zeta function over an interval of length , for any . The latter integral can be computed to the required accuracy in time about . With this and a binary search it is not difficult to locate an interval of width that is guaranteed to contain a prime in time . Optimising by choosing and using a sieve (or by testing the elements for primality one by one), one can then locate that prime in time .
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.