The polymath blog

August 13, 2016

MO Polymath question: Summary of Proposals

Filed under: polymath proposals — Gil Kalai @ 7:23 pm

mo

Here are the Math Overflow Polymath proposals given in response to the polymath question,

Summary of proposals (updated: August 10, 2016)

1) The LogRank conjecture. Proposed by Arul.

2) The circulant Hadamard matrix conjecture. Proposed by Richard Stanley.

3) Finding combinatorial models for the Kronecker coefficients. Proposed by Per Alexandersson.

4) Eight lonely runners. Proposed by Mark Lewko.

5) A problem by Ruzsa:
Finding the slowest possible exponential growth rate of a mapping from N to Z that is not a polynomial and yet shares with (integer) polynomials the congruence-preserving property n−m∣f(n)−f(m). Proposed by Vesselin Dimitrov.

6) Finding the Matrix Multiplication Exponent ω. (Running time of best algorithm for matrix multiplication.) Proposed by Ryan O’Donnell.

7) The Moser Worm problem and Bellman’s Lost in a forest problem. Proposed by Philip Gibbs.

8) Rational Simplex Conjecture ( by Cheeger and Simons). Proposed by Sasha Kolpakov.

9) determinants for 0-1 matrices Proving that for every integer m with |m|\le c(\sqrt{n}/2)^n there is an n \times n
0-1 matrix matrix whose determinant equals m.  Proposed by Gerhard Paseman.

10) Proving or disproving that the Euler’s constant is irrational. Proposed by Sylvain JULIEN.

11) The Greedy Superstring Conjecture. Proposed by Laszlo Kozma.

12) Understanding the behavior and structure of covering arrays. Proposed by Ryan.

13) The group isomorphism problem, proposed by Arul based on an early proposal by Lipton.

14) Frankl’s union closed set conjecture (Proposed by Dominic van der Zypen; Also one of the proposals by Gowers in this post). (Launched)

15) Komlos’s conjecture in Discrepancy Theory. Proposed by Arul.

16) Rota’s Basis Conjecture. Proposed by Timothy Chow.

17)+18) I contributed two proposals. One in ANT is to A problem in ANT show that
$latex 2^n+5$ is  composite for almost all positive integers n. (Might be too hard.) Another is to prove a remarkable combinatorial identity on certain Permanents.

19) Real world applications of large cardinals Proposed by Joseph van Name. There were a few more proposals in comments.

20) A project around a cluster of tiling problems. In particular: Is the Heech number bounded for polygonal monotiles? Is it decidable to determine if a single given polygonal tile can tile the plane monohedrally? Even for a single polyomino? Proposed by Joseph O’Rourke

February 7, 2016

Polymath Proposals on Math Overflow

Filed under: news,polymath proposals — Gil Kalai @ 3:21 am

mo

 

Here is the link to a mathoverflow question asking for polymath proposals. There are some very  interesting proposals. I am quite curious to see some proposals in applied mathematics, and various areas of geometry, algebra, analysis and logic.

January 2, 2016

“Crowdmath” project for high school students opens on March 1

Filed under: polymath proposals — Terence Tao @ 4:25 pm
Tags: ,

The MIT PRIMES program and the Art of Problem Solving are planning to run a “Crowdmath” project for high school students with advanced mathematical backgrounds, based on the polymath approach to mathematical research.  The project, which officially starts on March 1, will be devoted to original research on a mathematics problem to be specified at the time of the project (but judging from the reference material provided, it will probably involve the combinatorics of 0-1 matrices).  Participation is open to all high school students (though they will need an Art of Problem Solving account).

December 28, 2015

Polymath proposal: explaining identities for irreducible polynomials

Filed under: planning,polymath proposals — Terence Tao @ 7:05 pm

I am posting this proposal on behalf of Dinesh Thakur.

Let F_2[t] be the ring of polynomials over the finite field F_2 of two elements, and let

\displaystyle {\mathcal P} = \{t, t+1, t^2+t+1, \dots \}

be the set of irreducible polynomials in this ring.  Then infinite series such as

\displaystyle \sum_{P \in {\mathcal P}} \frac{1}{1+P} = \frac{1}{t+1} + \frac{1}{t} + \frac{1}{t^2+t} + \dots

and

\displaystyle \sum_{P \in {\mathcal P}} \frac{1}{1+P^3} = \frac{1}{t^3+1} + \frac{1}{(t+1)^3+1} + \frac{1}{(t^2+t+1)^3+1} + \dots

can be expanded as formal infinite power series in the variable t = 1/u.

It was numerically observed in http://arxiv.org/abs/1512.02685 that one appears to have the remarkable cancellation

\displaystyle{}\sum_{P \in {\mathcal P}} \frac{1}{1+P} = 0

and

\displaystyle{}\sum_{P\in{\mathcal P}} \frac{1}{1+P^3}=\frac{1}{t^4+t^2}

\displaystyle = u^4 + u^6 + u^8 + \dots.

For instance, one has

\displaystyle \frac{1}{t+1} = u + u^2 + u^3 + \dots

\displaystyle \frac{1}{t} = u

\displaystyle \frac{1}{t^2+t} = u^2 + u^3 + \dots

and all other terms in \sum_{P \in {\mathcal P}} \frac{1}{1+P} are of order u^3 or higher, so this shows that {}\sum_{P \in {\mathcal P}} \frac{1}{1+P} has u-valuation at least 3.  Similarly, if one expands the first sum for all primes of degree (in t) up to 37, one obtains {}u^{38}+u^{39}+u^{44}+u^{45}+\dots (the calculation took about a month on one computer), implying that the u-valuation of the infinite sum is at least 38; in fact a bit of theory can improve this to 42. (But we do not know whether this 42  is the answer to everything!).

For the second sum, calculation for degrees up to 28 shows that the difference between the two sides has u-valuation at least 88.

The polymath proposal is to investigate this phenomenon further (perhaps by more extensive numerical calculations) and supply a theoretical explanation for it.

Background links:

Below the fold is some more technical information regarding the above calculations.

(more…)

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.

November 4, 2013

Polymath9: P=NP? (The Discretized Borel Determinacy Approach)

Filed under: polymath proposals — Gil Kalai @ 2:07 pm
Tags: ,

p-np5

Tim Gowers Proposed and launched a new polymath proposal aimed at a certain approach he has for proving that NP \ne P.

June 4, 2013

Polymath proposal: bounded gaps between primes

Filed under: planning,polymath proposals — Terence Tao @ 4:31 am

Two weeks ago, Yitang Zhang announced his result establishing that bounded gaps between primes occur infinitely often, with the explicit upper bound of 70,000,000 given for this gap.  Since then there has been a flurry of activity in reducing this bound, with the current record being 4,802,222 (but likely to improve at least by a little bit in the near future).

It seems that this naturally suggests a Polymath project with two interrelated goals:

  1. Further improving the numerical upper bound on gaps between primes; and
  2. Understanding and clarifying Zhang’s argument (and other related literature, e.g. the work of Bombieri, Fouvry, Friedlander, and Iwaniec on variants of the Elliott-Halberstam conjecture).

Part 1 of this project splits off into somewhat independent sub-projects:

  1. Finding narrow prime admissible tuples of a given cardinality (or, dually, finding large prime admissible tuples in a given interval).  This part of the project would be relatively elementary in nature, relying on combinatorics, elementary number theory, computer search, and perhaps some clever algorithm design.  (Scott Morrison has already been hosting a de facto project of this form at this page, and is happy to continue doing so).
  2. Solving a calculus of variations problem associated with the Goldston-Yildirim-Pintz argument (discussed at this blog post, or in this older survey of Soundararajan) [in particular, this could lead to an improvement of a certain key parameter k_0, currently at 341,640, even without any improvement in the parameter \varpi mentioned in part 3. below.]
  3. Delving through the “hard” part of Zhang’s paper in order to improve the value of a certain key parameter \varpi (which Zhang sets at 1/1168, but is likely to be enlargeable).

Part 2 of this project could be run as an online reading seminar, similar to the online reading seminar of the Furstenberg-Katznelson paper that was part of the Polymath1 project.  It would likely focus on the second half of Zhang’s paper and would fit well with part 1.3.  I could run this on my blog, and this existing blog post of mine could be used for part 1.2.

As with other polymath projects, it is conceivable that enough results are obtained to justify publishing one or more articles (which, traditionally, we would publish under the D.H.J. Polymath pseudonym).  But it is perhaps premature to discuss this possibility at this early stage of the process.

Anyway, I would be interested to gauge the level of interest and likely participation in these projects, together with any suggestions for improving the proposal or other feedback.

March 2, 2013

Polymath proposal (Tim Gowers): Randomized Parallel Sorting Algorithm

Filed under: polymath proposals — Gil Kalai @ 4:41 pm

traj2

From Holroyd’s sorting networks picture gallery

A celebrated theorem of Ajtai, Komlos and Szemeredi describes a sorting network for  $n$ numbers of depth $O(log N)$. rounds where in each runs $n/2$. Tim Gowers proposes to find collectively a randomized sorting with the same properties.

February 14, 2013

Next Polymath Project(s): What, When, Where?

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

wspolymath

Let us have a little discussion about it.

We may also discuss both general and specific open research mathematical projects which are of different flavor/rules.

Proposals for polymath projects appeared on this blog,  in this post on Gowers’s blog, and in several other places.

July 13, 2012

Minipolymath4 project, second research thread

Filed under: polymath proposals — Terence Tao @ 7:49 pm

It’s been almost 24 hours since the mini-polymath4 project was opened in order to collaboratively solve Q3 from the 2012 IMO.  In that time, the first part of the question was solved, but the second part remains open.  In other words, it remains to show that for any sufficiently large k and any N, there is some n \geq (1.99)^k such that the second player B in the liar’s guessing game cannot force a victory no matter how many questions he asks.

As the previous research thread is getting quite lengthy (and is mostly full of attacks on the first part of the problem, which is now solved), I am rolling over to a fresh thread (as is the standard practice with the polymath projects).  Now would be a good time to summarise some of the observations from the previous thread which are still relevant here.  For instance, here are some relevant statements made in previous comments:

  1. Without loss of generality we may take N=n+1; if B can’t win this case, then he certainly can’t win for any larger value of N (since A could simply restrict his number x to a number up to n+1), and if B can win in this case (i.e. he can eliminate one of the n+1 possibilities) he can also perform elimination for any larger value of N by partitioning the possible answers into n+1 disjoint sets and running the N=n+1 strategy, and then one can iterate one’s way down to N=n+1.
  2. In order to show that B cannot force a win, one needs to show that for any possible sequence of questions B asks in the N=n+1 case, it is possible to construct a set of responses by A in which none of the n+1 possibilities of x are eliminated, thus each x belongs to at least one of each block of k+1 consecutive sets that A’s answers would indicate.
  3. It may be useful to look at small examples, e.g. can one show that B cannot win when k=1, n=1? Or when k=2, n=3?

It seems that some of the readers of this blog have already obtained a solution to this problem from other sources, or from working separately on the problem, so I would ask that they refrain from giving spoilers for this question until at least one solution has been arrived at collaboratively.

Also, participants are encouraged to edit the wiki as appropriate with new developments and ideas, and participate in the discussion thread for any meta-discussion about the polymath project.

« Previous Page — Next Page »

Blog at WordPress.com.