The Quantum Computer Puzzle @ Notices of the AMS

The Quantum Computer Puzzle

My paper “the quantum computer puzzle” has just appeared in the May 2016 issue of Notices of the AMS. Here are the beautiful drawings for the paper (representing the “optimistic view” and the “pessimistic view”) by my daughter Neta.

PN5  Ob


And the summary of my view

Understanding quantum computers in the presence of noise requires consideration of behavior at different scales. In the small scale, standard models of noise from the mid-90s are suitable, and quantum evolutions and states described by them manifest a very low-level computational power. This small-scale behavior has far-reaching consequences for the behavior of noisy quantum systems at larger scales. On the one hand, it does not allow reaching the starting points for quantum fault tolerance and quantum supremacy, making them both impossible at all scales. On the other hand, it leads to novel implicit ways for modeling noise at larger scales and to various predictions on the behavior of noisy quantum systems.


The nice thing is that my point of view is expected to be tested in various experimental efforts to demonstrate quantum computational supremacy in the next few years.

Updates (April, 24 2016): Here is an expanded version of the paper, with references, additional predictions and discussion. Here is a related post on GLL.

Polymath10 Plans, polymath11 news, and other plans.

The plan for polymath10: I hope to come back to it soon, report on some computer experimentation  and, of course, further comments on post 4 are most welcome. I hope to be able to report on some computer experimentation regarding the various conjectures and ideas.  I am planning to launch a fifth post in May.  Overall, I consider one year as a good time span for the project. Post 4 of Polymath11 is still active on Gowers’s blog, and I think that a fifth post is also in planning.

Here on the blog,  I plan a  mathematical post about my visit to Yale on February. The visit have led to Stefan Steinerberger’s beautiful post on Ulam sequences.  There are also newer interesting things, from our combinatorics seminar at HUJI, and from the third Simons’ conference on the analysis of Boolean functions (I hoped Ryan will blog about the conference). In celebration of the recent breakthrough on sphere packing in dimensions 8 and 24  I also plan to write more on sphere packing.

Happy Passover!

gilavi  gilalex

Pictures with Avi Wigderson at Nogafest and with Alex Lubotzky at Yale.

Posted in Combinatorics, Quantum, Updates | Tagged , | 2 Comments

Three Conferences: Joel Spencer, April 29-30, Courant; Joel Hass May 20-22, Berkeley, Jean Bourgain May 21-24, IAS, Princeton

Dear all, I would like to advertise three  promising-to-be wonderful mathematical conferences in the very near future.

Quick TYI. See if you can guess the title and speaker for  a lecture described by  “where the mathematics of Cauchy, Fourier, Sobolev, Gelfand and Bourgain meet. (Answer at the end of the post.)”


Random Roads – Joel Spencer’s 70 conference,  April 29-30 2016, at Courant NYC.

Joel Spencer’s 70th birthday conference is coming up on April. Here is the website



Geometry, Topology and Complexity of Manifolds, and applications to Biology – Joel Hass’ 60th birthday, May 20-22, 2016 at UC Berkeley.


Joel Hass’ 60th birthday conference is coming up in May at UC Berkeley. Here is the website.

Analysis and Beyond: Celebrating Jean Bourgain’s Work and Impact, May 21-24, I.A.S., Princeton.


A conference celebrating Jean Bourgain’s work is coming up in May at Princeton. Here is the conference page. 

Answer:  Speaker: Haim Brezis; TitleOld-new perspectives on the winding number; 


Posted in Analysis, Combinatorics, Conferences, Geometry, Updates | Tagged , , | Leave a comment

Math and Physics Activities at HUJI

Between 11-15 of September 2016 there will be a special mathematical workshop for excellent undergraduate students at the Hebrew University of Jerusalem. In parallel there will also be a workshop in physics. These workshops are aimed for second and third year undergraduate students. Here is the list of speakers! You need to register before June 15, 2016. More details below.


Open day, April 20, 2016

Two days from now on Wednesday April 20 there will be a splendid open day at the math department.  Do not miss it!!


Workshop for excellent undergraduate students, September 11-15 2016.

For online registration form and more information click here or on the picture!


Posted in Teaching, Updates | Tagged | Leave a comment

Stefan Steinerberger: The Ulam Sequence

This post is authored by Stefan Steinerberger.

The Ulam sequence

1,2,3,4,6,8,11,13, 16, 18, \dots

is defined by starting with 1,2 and then repeatedly adding the smallest integer that is (1) larger than the last element and (2) can be written as the sum of two distinct earlier terms in a unique way. It was introduced by Stanislaw Ulam in a 1962 paper (`On some mathematical problems connected with patterns of growth of figures’) where he vaguely describes this as a one-dimensional object related to the growth of patterns. He also remarks (in a later 1964 paper) that `simple questions that come to mind about the properties of a sequence of integers thus obtained are notoriously hard to answer.’ The main question seems to have been whether the sequence has asymptotic density 0 (numerical experiments suggests it to be roughly 0.07) but no rigorous results of any kind have been proven so far.

A much stranger phenomenon seems to be hiding underneath (and one is tempted to speculate whether Ulam knew about it). A standard approach in additive cominatorics is to associate to the first N elements of a sequence a_1, a_2, \dots, a_N a

 f_N(\theta) = \exp{(a_1 i \theta)} + \exp{(a_2 i \theta)} + \dots + \exp{(a_N i \theta)}

and work with properties of f_N. If we do this with the elements of the Ulam sequence and plot the real part of the function, we get a most curious picture with a peak around
 \theta \sim 2.571447\dots


Such spikes are generally not too mysterious: if we take the squares 1,4,9,16, ... we can observe a comparable peak at \theta = 2\pi/4 for the simple reason that squares are \equiv 0, 1 (mod 4). However, here things seem to be very different: numerically, the Ulam sequence does seem to be equidistributed in every residue class. Due to 2\pi-periodicity, the function f_N only sees the set of numbers

\left\{ \theta a_n~\mbox{mod}~ 2\pi: 1 \leq n \leq N\right\}

and it makes sense to look at the distribution of that sequence on the torus for that special value \theta \sim 2.571447\dots. A plot of the first 10 million terms reveals a very strange distribution function.


The distribution function seems to be compactly supported (among the first 10 million terms only the four elements 2, 3, 47, 69 give rise to elements on the torus that lie outside [\pi/2, 3\pi/2].) The same phenomenon seems to happen for some other initial conditions (for example, 2,3 instead of 1,2) as well and the arising distribution functions seem to vary greatly.


Question 1: What is causing this?

Question 2: Are there other `natural’ sequences of integers with that property?


See also Stefan’s paper  A Hidden Signal in the Ulam sequence .

Update: See also Daniel Ross’  subsequent study of Ulam’s sequence, presented in Daniel’s sort of public ongoing “research log”.  (“It includes a summary at the top of the most interesting observations to date, which usually lags a couple weeks behind the most current stuff.”) pic3

Posted in Guest blogger, Open problems | Tagged , | 8 Comments

TYI 26: Attaining the Maximum

(Thanks, Dani!) Given a random sequence a_1,a_2,\dots , a_n, ***a_i \in \{-1,1\}***, n>2, let S_k=a_1+a_2+\cdots +a_k. and assume that S_n=0.  What is the probability that the maximum value of S_k is attained only for a single value of k?

Test your intuition: is this probability bounded away from 0? tends to 0 like 1/\sqrt n? Quicker? Slower? Is there a nice formula?

Posted in Combinatorics, Probability, Test your intuition | Tagged | 21 Comments

A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24


Maryna Viazovska

The news

Maryna Viazovska has solved the densest packing problem in dimension eight! Subsequently, Maryna Viazovska with Henry Cohn, Steve Miller, Abhinav Kumar, and Danilo Radchenko solved the densest packing problem in 24 dimensions!

Here are the links to the papers:

Maryna Viazovska, The sphere packing problem in dimension 8

Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, Maryna Viazovska,
The sphere packing problem in dimension 24

(I thank Steve Miller and Peter Sarnak for telling me about it.)

Additional sources:  An article by Frank Morgan in The Huffington Post; A blog post by John Baez on the n-Category Cafe; An article by Erica Klarreich on Quanta Magazine; A blog post in Mathbya girl;

Some Background

Kepler, Gauss, Hales, Cohn and Kumar. A central mathematical problem is to find the densest sphere packing in R^d. The case d=3 is known as the Kepler conjecture. Gauss solved it for lattice packings, and Thomas Hales proved it for general packing using a massive use of computations. Cohn and Kumar settled the lattice case for dimensions 8 and 24.

Conway and Sloane. The “bible” regarding sphere packing is the classic book by two major player of the theory John Conway and Neil Sloane.

Hales and Fejes Toth.  Announced in 1998 and published a few years later, Hales’ proof  relies on some early work of Laszlo Fejes Toth. Since a full verification would require developing much of  the whole project from scratch, Hales himself led a team of researchers to find a formal proof which was published in 2015.

Lie and  Leech.   Lower bounds for higher dimensions. For some dimensions, special lattices of Lie type give surprisingly dense lattice packings. The Leech lattice gives a remarkably dense packing in dimension 24.

Minkowski,…, Ball, Vance and Venkatesh,  For asymptotically large dimensions a probabilistic method by Minkowski gives the best known lower bound up to small (but exciting) improvements. It gives a packing of density $2 \cdot 2^{-n}$.  Here is a slide from a lecture by Henry Cohn on the state of the art for the asymptotic question. (And here is the link to the slides of the full lecture.)


Delsartes, Kabatiansky and Levenshtein. Upper bounds via linear programming. Delsartes’ linear programming method (that can be seen as a Fourier/spectral attack with special features,) had led to important results towards general upper bounds by Kabatiansky and Levenshtein.

Cohn and Elkies developed related spectral methods applying directly to sphere packing, which allow to improve the upper bounds in dimensions 4–31 and give strikingly good results in dimensions 8 and 24.  Cohn and Kumar used these linear programming methods to settle the densest lattice problem in dimensions 8 and 24 and to give extremely good numerical upper bounds for the non-lattice case.

This is the starting point for Viazovska’s breakthrough.

Related problems/issues  to keep in mind: The densest packing problem in other dimensions and when the dimension tends to infinity; Kissing numbers and spherical codes; Upper bounds for error correcting codes; packing in other symmetric spaces; packing covering and tiling in combinatorics and geometry.

Viazovska’s breakthrough

The little I can tell you is that for a solution one needs to identify certain functions to plug in to the spectral machine. And Maryna’s starting point was some familiar extraordinary elliptic functions and modular forms.  More details on the comment section are most welcome.  (Update:) John Baez wrote on the n-Category Cafe some elementary comments on the proofs: E8 is the best.

The 24-dimensional case

A key ingredient for the result in dimension 24 is the earlier numerical rationality conjectures by Cohn and Miller.  Those now appear in the preprint: Henry Cohn, Stephen D. Miller, Some properties of optimal functions for sphere packing in dimensions 8 and 24 .

Congratulations to Maryna, Abhinav,  Danilo,  Henry, and Steve!

I remember a decade ago that Steve Miller explained to me some developments, ideas, and dreams  regarding two problems. One was the sphere packing problem in dimensions 8 and 24 that he now took part in solving, and the other was the irrationality questions regarding zeta functions at odd integers (and maybe also the Euler constant.)  Time to move to the second problem, Steve:)

(And a trivia question: name a player in both these stories. As usual if you answer in the comment section please give a zero-knowledge answer demonstrating that you know the solution without revealing it.)

Posted in Combinatorics, Geometry, Updates | Tagged , , , , , , | 15 Comments

Polymath10-post 4: Back to the drawing board?

It is time for a new polymath10 post on the Erdos-Rado Sunflower Conjecture. (Here are the links for post1, post2, post3.) Let me summarize the discussion from Post 3 and we can discuss together what directions to peruse. It is a pleasure to mention that in parallel Tim Gowers is running polymath11 aimed for resolving Frankl’s union closed conjecture. Both questions were offered along with the Erdos discrepancy problem and the Erdos-Hajnal conjecture in this 2009 post by Tim. In fact, some people participate both in polymath10 and polymath11. The acronym for polymath 11 is FUNC and I suppose we can choose between SUN or ERSC or some other options for polymath10.

Because of polymath10, I did not discuss over here other things. Let me mention two super major developments that I am sure you all know about. One is Laci Babai’s  quasi-polynomial algorithm for Graph isomorphism. (This is a good time to mention that my wife’s mother’s maiden name is Babai.) You can read about it here (and the next three posts) and here. Another is the solution by Jean Bourgain, Ciprian Demeter, Larry Guth of Vinogradov’s main conjecture. You can read about it here and here.



We denoted by f(k,r) the largest cardinality of a family of k-sets without a sunflower of size r, and  f(k,r,m,n) the largest cardinality in a family of k-subsets of [n] with the property P(r,m), namely without a sunflower of size r with head of size at most m. Adding the subscript b for f_b(k,r),f_b(k,r,m,n) refer to balanced families rather than to arbitrary family. The “Erdos-Ko-Rado regime” is when r=2 and m is arbitrary or when m=1 and r is arbitrary. (In this regime the property P(r,m) is preserved under shifting.)

Results by Ferdinand Ihringer

Ferdinand gave interesting upper bounds and lower bounds for f(k,r,m,n) in terms of f(k,r).

f(m, r) \leq f(k, r, m, n) / \binom{n-m}{k-m} \leq 10 f(k, r)^3.

For the upper bound see this writeup by Ferdinand. For more details see this comment and the following ones. It will be interesting to find sharp lower and upper bounds.

Proposal by Domotor Palvolgyi

Domotor raised   in this comment and the following ones some ideas for using algebraic methods for the sunflower conjecture. This have led to an interesting discussion (following these comments) between Domotor and Ferdinand on connection between Sunflowers and Ramsey numbers (mainly R_3(k)).

So that this post will not interrupt this interesting discussion let me quote the beginning of Domotor’s comment posted minutes ago:

“So let us denote the size of the largest k-uniform family without r (different) sets whose pairwise intersection has the same size by g(k,r). As we have seen in the earlier discussion, trivially g(k,r)\le f(k,r) and g(k,r)\le R_r(k) (where in the last Ramsey notation we forbid K_r in a k-coloring of the complete graph). Mysteriously, for all three functions we have similar lower and upper bounds. In this comment I propose to try proving f(k,r) \le g(ck,r) for some c.”

Proposal by Shachar Lovett.

Shachar Lovett proposed in this comment how to use the topological Tverberg theorem for attacking a certain important special case of the conjecture.

Reminder: Reduction to the balanced case, Phillip Gibbs’ construction, and more drastic reductions.

We started with the observation that every family F of k-sets contains a balanced subfamily of size \frac {k!}{k^k}|F|. (BTW for graphs there is a sharper result by Noga Alon and it would be interesting to extend it to hypergraphs!) This gives that

f(k,r) \le e^kf_b(k,r).

Phillip Gibbs showed in this comment that if the sunflower conjecture is true then

f_ (k,r) \le (1+o(1))^kf_b(k,r).

It will be interesting to describe precisely what (1+o(1)) stands for, and improve it as much as possible. All left to be done for a counterexample to the sunflower conjecture is to complement Phillip construction by another one showing an exponential gap between the balanced and general case. This is certainly a tempting direction.

More drastic reductions then the very basic one are also possible, for example: for families of k-subsets without a sunflower of size 3 it is enough to consider families with elements colored by 100k colors such that every set is colored by consecutive colors and two sets sharing k-1 elements are not using the same color-intervals. (This implies “high girth” of some sort.) We can ask if this type of reductions is useful for proving the conjecture, if one can show (like Phillip) that assuming the conjecture, the gap between the bounds for this version is not too large compared to the general version, and hope that this can be part of a construction going in the negative direction.

The Homological/Algebraic Approach

In quite a few comments to post 3, I tried to further develop the homological ideas   (and to mention some low hanging fruits and related questions). We did reach a major obstacle sending us back to the drawing board. I see some possible way around the difficulty and I will now describe it. For this purpose I will review the homological ideas in somewhat more general and very elementary context. (We only briefly mention the connection with cycles/homology but it is not needed).

Compound matrices, weak isomorphism and dominance.

Let X=(x_ij)_{1 \le i \le n, 1 \le j \le n} be a generic matrix. The k-th compound matrix C_k(X) is the matrix of k by k minors. Namely, C_k(X)=x_{ST}, S,T \in {{[n]} \choose {k}} where x_{ST}=det(x_{ij})_{i \in S,j\in T}.

Given two k-unform hypergraphs F,G we say that F and G are weakly isomorphic if the m\times m minor C_{F,G}(X) of C_k(X) whose rows and columns correspond to sets in F and G respectively is non-singular. (It is fairly easy to see that if F and G are isomorphic then they are weakly isomorphic. This relies on the condition that X is generic.) We will say that F dominates G if  |F|\ge |G| and C_{F,G}(X) is full rank. Thus, F and G are weakly isomorphic if each dominates the other.

Let D[b,c] be the set of k-subsets S of [n] such that |S \cap [b]|\ge c.  The connection with our notions of acyclicity is as follows: F is acyclic (i.e. Z_{k-1}(K)=0) iff F is dominated by D[1,1]. In greater generality,   K_{k-1}[b,c]=0 iff F is dominated by D[b,c]. (In particular,  Z_{k-1} [r,1](K)=0 iff F is dominated by D[r,1], and Z_{k-1}[m,m](K)=0 iff F is dominated by $D[m,m]$.) Remark: Here and later in the post Z_*[b,c] with H_*[b,c] since we deal only with cycles for the top dimension, so there are no “boundaries” to mod out.

Algebraic shifting

A family F of k-subsets of [n] is shifted if whenever S \in F and R is obtained by replacing an element by a smaller element then R \in F.  It can be shown that two shifted families of the same size are weakly isomorphic only if they are equal! We can use our compound matrix to describe an operation (in fact, several operations) called shifting which associated to a family F a shifted family \Delta_T(F).  Suppose that |F|=m. \Delta (F) is the lexicographically smallest family of sets which is weakly isomorphic to F. In more details: we first consider a total ordering T on k-subsets of [n]. Then we greedily  build a hypergraph which is dominated by F.  When we reach m sets we obtain a  hypergraph \Delta_T(F) weakly isomorphic to F.

Now, if the total ordering is the lexicographic order on {{[n]} \choose {k}} then we denote \Delta(F)=\Delta_T(F)) and call \Delta(F) the “algebraic shifting” of F. In this case, it can be shown that the resulting family is shifted. Also of special importance is the case that T=RL is the reverse lexicographic order.

For sets of integers of size k, the lexicographic order refers to the lexicographic order when we ordered the elements of every set from increasingly, and the reverse lexicographic order is the lexicographic order when we order the elements decreasingly.

From 12<13<14<15<…<21<22<…<31<32<… we get

\{1,2\} <_L \{1,3\} <_L \{1,4\} \dots <_L \{ 2,3\} <_L \{2,4\} <_L \dots

and from  21<31<32<41<42<43<51<52<…  we get

\{1,2\} <_{RL} \{1,3\}<_{RL}\{2,3\}<_{RL}\{1,4\}\dots

We mention again some connection with acyclicity and homology: F  is acyclic if all sets in \Delta (F) contains ‘1’. F is [r,1]-acyclic iff all sets in in \Delta (F) intersect [r]. F is [m,m]-acyclic iff all sets in \Delta(F) contains [r]. For general b,c, [b,c]-acyclicity is not expressed by those two versions of algebraic shifting, however, F is [s,k]-cyclic if \Delta_{RL}(F) \subset {{[s]}\choose{k}}.

Algebraic shifting in  the Erdos-Ko-Rado regime.

The following properties are preserved under algebraic shifting:

(1) Every two members of F has at least m elements in common.

(2) There are no r pairwise disjoint sets in F.

For balanced families we know even more:

(3) If F is balanced and every two members of F has at least m elements in common then all sets in \Delta(F) contains [m].


(4) If F is balanced and there are no r pairwise disjoint sets in F, then every set in \Delta(F) intersects [r-1].

Reverse shifting in the Erdos-Ko-Rado regime.

As it turns out we have much stronger statements:

The following properties are preserved under reverse-lexicographic algebraic shifting:

(5) Every two members of F has at least m elements in common.

(6) There are no r pairwise disjoint sets in F.

(I dont know if (3) and (4) extends as well. It  certainly worth the effort to check it.)


Modified plan for attack:

Our ultimate conjecture remains the same:

Main Conjecture:  If F has no sunflower of size r then it is [xk,k]-acyclic. (I.e., Z_{k-1}[(xk,k](K)=0.)

For balanced family we conjectured that x=(r-1) and for the non-balance we had a larger value x=r.

Our homological approach mainly for the balanced case was to use the local homological condition from  (2) (or(4)) (with some additional homological condition yet to be proved – this was Conjecture A) to conclude (This was Conjecture B) that F is [xk,k]-acyclic. However,  Conjecture B turned out to be false.  Our new idea is to replace the local conditions on homology obtained from (2), (4) by those given by (6) which are apparently quite stronger.

We also tried to explore how to prove the main conjecture via  an even stronger statement for “combinatorial cycles”. This works for the balanced case in the Erdos-Ko-Rado-regime (leading to some interesting consequences). But we did not manage to extend it beyond this regime. Domotor  shoot down some half-baked attempts towards such a goal.

What we propose now is to use the following theorem instead of Conjecture A and to greatly modify Conjecture B accordingly. (For general families; being balanced is not used.)

Theorem: Let F is a family of k-sets without a sunflower of size r. Then

(*) For every family of i-sets F' which is the link of a set of size k-i (including the case F'=F) , Every set in \Delta _{RL}(F') intersect [(r-1)i].

Conjecture B (greatly modified): For a family F of k-sets satisfying (*) we have

(**) \Delta_{RL}(F) \subset {{[rk]}\choose{k}}.

This is the new plan! Below are a couple of comments.

A new homological translation:

We can, I think,  translate the condition on reverse lexicographic shifting also to some conditions on homology, given in this comment,  but the connection is still a little dubious and need some further checking and explanation. (Specifically, it relies on a comment I make in my paper on algebraic shifting that if F is a family of k-subsets of [n] and  G is its complement, then the shifting of F is related to the reverse lexicographic shifting of G as follows: takes the complement of \Delta (F) and apply the involution sending element i to n-i.)

If K is the simplicial complex spanned by our family F and L is the simplicial complex spanned by the complement of F  we want to replace conditions of the form

(*) Z_{k-1}[s,1] (K)=0

by the stronger condition

(**) Z_{k-1}[n-s-k,1] (L)\ne 0

For example, for a graph G with n vertices and n-1 edges \Delta (G) gives all edges containing ‘1’ (which is equivalent to (*) for s=1) if and only if G is a tree. But requiring it for \Delta_{RL}(G)  implies (I think) that G  be a star and is equivalent (I think) to Z_1[n-3,1](\bar G)\ne 0, where \bar G is the complement of G.

Planned experimentation.

We plan to run computer experimentation to test some of these ideas on small cases.

A few words on symmetric shifting and related notions of homology.

Let me mention that there is a variant of compound matrix, weak equivalence and of algebraic shifting (and hence also of the various homology groups we considered,) when we use symmetric products instead of exterior products.  The theories based on those variants are very similar, and the advantage of the notions based on symmetric powers is that they are closer to studied notions of commutative algebra. (But I think they will be harder to compute as determinants are replaced by permanents.)


Posted in Combinatorics, Mathematics over the Internet, Polymath10 | 10 Comments

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

2016_JAZZ 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).



Posted in Combinatorics, Conferences, Mathematics over the Internet, Polymath10, Polymath3, Updates | Tagged , , , , , , , | 11 Comments

Polymath 10 Post 3: How are we doing?

The main purpose of this post is to start a new research thread for Polymath 10  dealing with the Erdos-Rado Sunflower problem.  (Here are links to post 2 and post 1.) Here is a  very quick review of where we are.

Let f(k,r) [f_b(k,r)] be the maximum size of a family of k-sets [balanced family] with no sunflower of size r. Let C(r) = \lim sup f(k,r)^{1/k} and  C_b(r) = \lim sup f_b(k,r)^{1/k}.

Philip Gibbs:  The balanced case vs. the general case.

Phillip gave a beautiful construction showing that if C(r) is finite than C_b(r)=C(r). This is very interesting and I found it surprising. (Earlier we only knew that C(r) \le e \cdot C_b(r).) Of course, if you can find another construction which starts with balanced families (even only those constructed by Philip) and end with exponentially larger general families (you can even enlarge k a little,) this will provide a counterexample to the Erdos-Rado conjecture.

The homological approach:

In the previous post and some comments (like this comment and the following ones; and this comment)  I continued to meditate about my homological approach. For r=3 we want to show that for balanced families, a (2m,m)-cycle will contain a sunflower with head of size smaller than m. (This will now give C(3) \le 4.)  Juggeling between the homological notion of (b,c)-cycles and a combinatorial one can be useful.

Proposals by Tim:

Tim observed that if all pairwise intersections between sets in a sunflower free family have the same size then this leads to exponential upper bounds. This can be a starting point for an argument where “same size” is replaced by a weaker condition, or to ideas about how to construct a counterexample.

Random sunflower-free families

We also want to understand the expected number of sets in the sunflower-free process when we consider k-subsets fron [n]. (We would also like to understand the expected size of the union of sets in the resulting family.) This is interesting both for the general case and the balanced case. Simulations by Philip (e.g. here) and by Gonzalo (e.g. here) were presented. (I am still confused about the outcomes of the simulations, maybe we shoud run more simulations.)

New examples

In the later comments to the previous thread (starting here) that I did not digest yet, Philip offered some ideas on new constructions of various types.

Some more comments and questions

Avi Wigderson asked: Is it enough to prove the Erdos-Rado conjecture for n=k^2? n=k \log k? etc? Dömötör asked the following Kneser-type coloring question:
How many colors to we need to color all k-tuples of an n element set avoiding monochromatic 3-sunflowers?

The special case mentioned by Shachar:

Shachar mentioned in comments to post I (starting here) an exciting special case (related to matrix multiplication.)

Looking at the classic papers:

It can be a good time to look at the classic papers by Abott, Hanson, and Sauer and , Spencer and Kostochka (for the general case; for sunflower of size three). Here is again the link for Kostochka’s survey.  There are many other papers (even recent) about sunflowers and many aspect of the problem and related problems that we did not talk about.

Here are the six pages of Joel’s paper.


temp1temp2temp3temp4 temp5temp6

Posted in Combinatorics, Mathematics over the Internet, Open problems, Polymath10 | Tagged , | 103 Comments

Polymath10, Post 2: Homological Approach

We launched polymath10 a week ago and it is time for the second post. In this post I will remind the readers what  the Erdos-Rado Conjecture and the Erdos-Rado theorem are,  briefly mention some points made in the previous post and in the comments, make some remarks of administrative nature, and describe in detail a homological plan for attack, some of whose ingredients were mentioned in the first post.

Of course, there are various other avenues that can be explored:  In a series of comments (e.g. this thread and that thread and this) Tim Gowers proposed a line of attack related to understanding quasirandom behavior of families of sets in terms of their pairwise intersections. (Update: Tim developed his ideas in further comments. A theme which is common to his approach as well as to the homological approach is to see if we can “improve” certain properties of the family after moving to an exponentially smaller subfamily. Second update: this post was written after 70 or so comments for post 1. There are many further interesting comments. ) Karim Adiprasito described a different topological combinatorics approach. Another clear direction is  to try to extend the ideas of Spencer and Kostochka which led to the best known bounds today.  Raising more ideas for attacking the conjecture is most welcome. For example, in Erdos Ko Rado theory, besides direct combinatorial arguments (mainly those based on “shifting,”) spectral methods are also quite important. Of course, the sunflower conjecture may be false as well and ideas on how to construct large families without sunflowers are also most welcome.

Terry Tao kindly set a Wiki page for the project and proposed to conduct computer experimentation for small values of r and k. Of course, computer experimentation will be most welcome! Some of the suggestions described below can also be tested experimentally for small values.

Let me also mention some surprising connections between the sunflower conjecture and various issues arising in matrix multiplication. As pointed by Shachar Lovett (in this comment and the following one), a counterexample to a certain structural special case of the sunflower conjecture will imply an almost quadratic algorithm for matrix multiplication!

Dömötör and I hyperoptimistically conjectured that the Erdos-Rado example is optimal for Balanced families. But Hao gave a very simple counterexample.

The status of our project at this stage is described very nicely by Tim Gowers who wrote:

At the time of writing, Gil’s post has attracted 60 comments, but it is still at what one might call a warming-up stage, so if you are interested in the problem and understand what I have written above, it should still be easy to catch up with the discussion. I strongly recommend contributing — even small remarks can be very helpful for other people, sparking off ideas that they might not have had otherwise. And there’s nothing quite like thinking about a problem, writing regular bulletins of the little ideas you’ve had, and getting feedback on them from other Polymath participants. This problem has the same kind of notoriously hard feel about it that the Erdős discrepancy problem had — it would be wonderful if a Polymath collaboration could contribute to its finally getting solved.

Update to an earlier post. Karim Adiprasito, June Huh, and Eric Katz have now posted their paper “Hodge theory for combinatorial geometries” which contains, among other things, a proof of the Heron-Rota-Welsh conjecture on matroids.

Here is a reminder of the sunflower theorem and conjecture:

The Erdos-Rado sunflower Theorem

A sunflower (a.k.a. Delta-system) of size r is a family of sets A_1, A_2, \dots, A_r such that every element that belongs to more than one of the sets belongs to all of them.  We call the common element to all the sets the head of the sunflower (or the kernel of the sunflower), and the elements that belong to just one among the sets, the petals.

A basic and simple result of Erdos and Rado asserts that

Erdos-Rado sunflower theorem: There is a function f(k,r) so that every family \cal F of k-sets with more than f(k,r) members contains a sunflower of size r.

We denote by f(k,r) the smallest integer that suffices for the assertion of the theorem to be true.

The Erdos-Rado Sunflower Conjecture

The Erdos-Rado sunflower conjecture:  f(k,r) \le C_r^k.

Here, C_r is a constant depending on r. It may be also the case that we can take C_r=Cr for some absolute constant C. The conjecture is already most interesting for r=3.  I recommend to reading Kostochka’s survey paper and also, as we go, it will be useful to learn Spencer’s argument and Kostochka’s argument which made remarkable improvements over earlier upper bounds.

The main purpose of this post is to provide

A Homological attack on the sunflower Conjecture

Part 1:  Combinatorial Extensions and Variations

A) The question as an Erdos-Ko-Rado type question

Let f(k,r,m;n) be the maximum size of a family \cal F of k-subsets of [n]=\{1,2,\dots ,n\}  containing no sunflower of size r with head of size at most m-1.  (Note: it should me m-1.)

Basic Question: Understand the function f(k,r,m;n). Is it true that f(k,r,m;n)\le C_r^{k}n^{k-m}, where C_r is a constant depending on r, perhaps even linear in r.

A family of k-sets satisfies property P(k,r,m) if it contains no sunflower of size r with head of size at most m-1.

B) Stars and links:  Given a family F of sets and a set S,  the star of S is the subfamily of those sets in F containing S, and the link of S is obtained from the star of S by deleting the elements of S from every set in the star. Another way to say that \cal F has property P(k,r,m) is that the link of every set of size at most  less than m contains no r pairwise disjoint sets.

C) The balanced case

A family of k-sets is balanced (or k-colored, or multipartite) if it is possible to divide the ground set into k parts so that every set in the family contains one element from every part.

Let g(k,r,m;n) be the maximum size of a balanced family \cal F of k-subsets of [n]=\{1,2,\dots ,n\}  containing no sunflower of size r with head of size at most m. By randomly dividing the ground set into colors we obtain that f(k,r,m;n) \le \frac{k^k}{k!}g(k,r,m;n).

D) What we aim for. Below we describe two variations of a homological attack on the sunflower conjecture. If successful (as they are) they will lead to the following bounds.

The first variation based on conjectured homological properties of balanced families would yield

(*) f(k,r,m;n)\le e^k {{(r-1)m}\choose{m}}\cdot{{n-m} \choose {k-m}}

The alternative version would give

(**) f(k,r,m;n)\le {{m+(r-1)k}\choose{m}}\cdot {{n-m}\choose {k-m}}

Part 2: Collections of sets as geometric objects, homology and iterated homology.

E) Simplicial complexes and homology

Staring with a family {\cal F} we will consider the collection of sets obtained by adding all subsets of sets in {\cal F}. This is a simplicial complex, K, and we can regard it as a geometric object if we replace every set of size i by a simplex of dimension i-1. (We call sets in K of cardinality (i+1) by the name i-faces.

The definition of homology groups only depends on the combinatorial data. For simplicity we assume that all sets in {\cal F} (and hence in the associated simplicial complex) are subsets of {1,2,…,n}. We choose a field A (we can agree that the field will be the field of real numbers). Next we define for i>0 the vector space of i-dimensional chains C_i(K) as a vector space generated by i-faces of K. We also define a boundary map \partial_i:C_i(K)\to C_{i-1}(K) for every i. The kernel of \partial_i is the space of i-cycles denoted by Z_i(K); the image of \partial_{i+1} is the space of i-boundaries, denoted by B_i(K). The crucial property is that applying boundary twice gives you zero, and this allows to define homology groups H_i(K)=Z_i(K)/B_i(K). The betti numbers are defined as b_i(K)=dim H_i(K).  We will give the definition of the boundary operator further below.

F) Acyclic families and intersecting families

A family {\cal F} of k-sets is acyclic  if it contains no k-cycle, or equivalently if H_k({\cal F})=0.  (For coefficients in Z/2Z, a k-cycle G is a family of k-sets such that  every set of size (k-1) is included in an even number of k-sets in G.)

Proposition: An acyclic family of k-subsets of [n], contains at most {{n-1} \choose {k-1}} sets.

In the first post we asked:  Are there some connections between the property “intersecting” and the property “acyclic?”

Unfortunately, but not surprisingly intersecting families are not always acyclic, and acyclic families are not always intersecting. (The condition 2k \le n from EKR theorem also disappeared.) As we mentioned in the previous post intersecting balanced families are acyclic! And as we will see for balanced families Erdos-Ko-Rado properties translate nicely into homological property.

G) Pushing the analogy further

We made an analogy between “intersecting” and “acyclic”. Building on this analogy

1) What could be the “homological” property analogous to “every two sets have at least elements in common”?

2) What could be the “homological” property analogous to “not having r pairwise disjoints sets”?

I will propose answers below the fold. What is your answer?

Continue reading

Posted in Combinatorics, Polymath10 | Tagged , , , | 125 Comments