## News (mainly polymath related)

Update (Jan 21)

j) Polymath11 (?) Tim Gowers’s proposed a polymath project on Frankl’s conjecture. If it will get off the ground we will have (with polymath10) two projects running in parallel which is very nice. (In the comments Jon Awbrey gave a links for a first in a series posts also on Frankl’s conjecture, with the catchy title, Frankl my dear.)

a) NogaFest started a few days ago. It is a wondeful meeting! My lecture entitled “polymath” refers to the older meaning of the word, so appropriate to describe Noga. (I was not aware that the word has a meaning until recently). I talked, among other things, about polymath10. I prepared the talk a week ahead and  presented our Conjectures A and B (from polymath10 last post) hoping that perhaps I could add some positive information toward them. Well, just after my presentation was ready, I realized that Conjecture B is false. Here are the slides.

Two quotes from the lecture. First about the birthday boy: the idea of the polymath was expressed by Leon Battista Alberti (1404–1472), in the statement, most suitable to Noga a man (who) can do all things if he will”.  Second, about polymath projects (by Gowers): “a large collaboration in which no single person has to work all that hard.”

b) 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 (perhaps mainly to see what researchers regard as central major projects,) in applied mathematics, and various areas of geometry, algebra, analysis and logic.

c) A very nice polymath proposal by Dinesh Thakur was posted  by Terry Tao on the polymath blog. The task was to explain some numerically observed identities involving the irreducible polynomials $P$ in the polynomial ring ${\bf F}_2[t]$ over the finite field of characteristic two. David Speyer managed to prove Thakur’s observed identities! Here is the draft of the paper.

d) This reminds me that some years ago David Speyer solved a question that interested me for decades and was presented here on the blog and later on MathOverflow about systems of skew lines in three dimensional vector spaces over division rings (and especially the Quaternions).

e) Related to polymath3, let me mention that Michael Todd proved a small but very elegant improvement of the upper bounds by Kleitman and me from 1992. (The new bound is $(n-d)^{\log d}$. The first improvement, I think, in two decades!

f) I have a very nice thing to tell you about polymath4! Shafi Goldwasser abstract for Nogafest talked about a new notion of randomized algorithms: A randomized algorithm to achieve a certain task (for example to find a perfect matching in a graph,) which is guaranteed to reach the same answer with high probability! Such an algorithm is called pseudo-deterministic. It is both an amazing concept, and it is quite amazing that it was not introduced before. The polymath4 question was to find deterministically a prime with n digits and A new challenge (that Shafi asks about) is to find a pseudo-deterministic efficient algorithm. Namely, a randomized algorithm which will find an n-digit prime, but with high probability the same one! (I would guess that it is still hopeless.)

g) And Terry Tao gave a beautiful lecture on Erdos discrepancy problem (the topic of polymath5). I understood a little better the argument (which is  similar to Roth density increase argument for 3 term AP,) that allows Tao to use the logarithmically-averaged Chowla inequalities.

h) The old conjecture that centrally symmetric convex sets  have nonnegative correlation w.r.t. the Gaussian distribution  was proved! Let me refer you to the paper Royen’s proof of the Gaussian correlation inequality for a simple exposition of a proof by Thomas Royen, and more information on the solutions and solvers.

i) The Nogafest participants are invited to a Jazz night at Gilly’s

The third Polymath10 post is active. I hope to post a new polymath10 post in about 1-2 weeks. I hope also to return to various amazing things I am hearing on Nogafest and other places (and also on my ownfest some months ago).

This entry was posted in Combinatorics, Conferences, Mathematics over the Internet, Polymath10, Polymath3, Updates and tagged , , , , , , , , . Bookmark the permalink.

### 11 Responses to News (mainly polymath related)

1. Bogdan says:

My comment in about pseudo-deterministic algorithms, in particular for finding primes. In the initial paper about pseudo-deterministic algorithms (Eran Gat and Shafi Goldwasser. Probabilistic search algorithms with unique answers and their cryptographic applications) the authors prove (Theorem 4) that search problem has pseudo-deterministic algorithms if and only if it is deterministically reducible in polynomial time (via a Cook reduction) to a decision problem in BPP.
On the other hand, Oded Goldreich, In a World of P=BPP. Studies in Complexity and Cryptography 2011: 191-232, writes (beginning of section 3.2): “One may expect that any BPP-search problem be deterministically reducible to some BPP decision problem. Indeed, this holds for the restricted definition of BPP-search problems as in Definition 3.1”. Definition 3.1 essentially states that BPP-search problem is a binary relation R such that (1) Membership in R is decidable in probabilistic polynomial-time, and (2) there exists a probabilistic polynomial-time algorithm A for R.

The problem for finding primes clearly satisfies definition 3.1. Hence, it is deterministically reducible to some BPP decision problem by Oded Goldreich theorem, and hence it has a pseudo-deterministic algorithm by Gat – Goldwasser result.

Did I misunderstand something?

• Gil Kalai says:

Dear Bogdan. You certainly understand and told more about it than me. I only read Shafi’s abstract…

2. Concerning g) Did Terrence Tao provide any (publicly available) notes for his talk?

3. Jon Awbrey says:

Lipton and Regan’s post on the Frankl Conjecture a couple years ago prompted me to pursue their approach for a while. Here I just started preparing the ground:

4. obryant says:

I’m a bit confused about people publishing Polymath results under their own individual name. The first time it happened, that I noticed, was when Tim Austin published a variant of the ergodic proof of density Hales-Jewett. I was okay with that because (A) he was an unknown grad student building a name and (B) his work had little direct overlap with the course of polymath discussions. Next was Terry publishing his solution of the Erdos Discrepancy problem, which was fine because the polymath project had quit functioning a long time before his big leap forward. With Speyer’s paper, I have no opinion still: I didn’t participate in that Polymath project. But it’s an issue that could use some clarification.

• Gil Kalai says:

Dear Kevin, Actually Tim Austin worked on and had progress on finding a simpler proof (compared to the original one) for density Hales Jewett before polymath1 started. (You can read  more details on Tim’s blog post announcing the (then probable) success of the project, this Terry’s blog post, my report in real time, and I suppose also in the relevant papers.) As you said, at the end there was some overlap as his ideas may have contributed to polymath1, and polymath1 ideas and breakthrough/success contributed to his project.

I agree about EDP. Thakur’s question was solved by Speyer before any polymath project started and before anybody else contributed anything. It is very welcome that David will publish the paper on his name or if David and Dinesh prefer they may unite their papers. I suppose, that Dinesh’s question was even more suitable as a MO question but it worked well as is.

I suppose we have to apply common sense on the question of how to publish papers emerging from large projects in the future and remember that the threads themselves give information on how the project developed and that part of the idea is of altruistic/fun/open-source-like effort.