Polymath 10 post 6: The Erdos-Rado sunflower conjecture, and the Turan (4,3) problem: homological approaches.

In earlier posts I proposed a homological approach to the Erdos-Rado sunflower conjecture.  I will describe again this approach in the second part of this post. Of course, discussion of other avenues for the study of the conjecture are welcome. The purpose of this post is to discuss another well known problem for which a related  homological approach,  might be relevant.  The problem is the Turan (4,3) problem from 1940.

We will not regard attacks on the sunflower conjecture based on the recent solution of the cap set problem and the Erdos Szemeredi sunflower conjecture (which is a weaker version of the Erdos-Rado conjecture) as part of the present polymath10 project, but, of course, I will be happy to hear also reports on progress or comments on these directions. Some updates on this story: Eric Naslund and Will Sawin gave a direct proof based on the polynomial method for the Erdos-Szemeredi sunflower conjecture, and an even  stronger result is given by Naslund here. (Eric also has stronger quantitative bounds for Erdos-Szemeredi based on bounds for cap sets.)   More cap set updates are added to this post, and can be found in the comment threads here and here.

Turan’s (4,3) problem

Turan’s 1940 problem is very easy to state.

What is the maximum number of edges in a 3-uniform hypergraph on n vertices with the property that every four vertices span at least one triangle? 

We talked about the problem (and a little about the homological approach to it) in this post and this post.

Four things that the Erdos-Rado sunflower problem and the Turan (4,3) problem have in common.

4. 1000 dollars or so Erdos prize

If I remember correctly, the Turan’s problem is the only question not asked by Erdos himself for which he offered a monitory award.

3.  The homological approach  might be relevant.

This is what this post is going to be about. But while this connection is still tentative and speculative, the next connections between the two problems are solid.

2. Sasha Razborov

Sasha used the Erdos-Rado sunflower theorem in his famous theorem on superpolynomial lower bounds for monotone circuits, and his flag-algebra theory have led to remarkable progress and the best known upper bound for the Turan (4,3) problem. (See here and here .)

1. Sasha Kostochka

Sasha holds the best known upper bound  for the sunflower conjecture and he found a large class of examples for the equality cases for the Turan (4,3) conjecture.

Quasi-isomorphism of hypergraphs

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.

A class of matroids defined on hypergraphs

Let G(k,r,n) be the k-uniform hypergraph which consists of all k-subsets of [n] that intersect [r]. For a k-uniform hypergraph F on the vertex set [n] let rank_r(F) = rank C_{F,G(k,r,n)}. For the complete k-uniform hypergraph K on n vertices (n \ge r) rank_r(K)={{n}\choose {k}} - {{n-r} \choose {k}}.

 Homological approach to Turan’s (4,3) problem.

We refer to a 3-uniform hypergraph  with the property that every four vertices span at least one triangle as a Turan (4,3)-hypergraph.

Conjecture: If F is a Turan (4,3)-hypergraph with n vertices then

rank_r(F) \ge r {{n-r-1}\choose {2}}.

This conjecture is a refinement of Turan’s conjecture. (The conjectured 1940 lower bound by Turan can be written as  \max (r{{n-r-1} \choose {2}}: r\ge 1).) It is known for r=1 (see this post) and an analogous statement is known for Turan (3,2)-graphs.

We would like to find even stronger algebraic statements which amounts not only to upper bounds on certain homology-like groups but to stronger statements about vanishing of certain homology-like  groups.

I am also curious about

Question: Are all extremal examples with n vertices for the Turan (4,3) problem quasi-isomorphic? If this is the case we can also conjecture that every Turan (4,3) hypergraph dominates  Turan’s example on the same number of vertices.

I hope to be able to present some experimental data on these problems.

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

The (current) homological approach to the Sunflower problem: a reminder.

Our ultimate conjecture is:

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

An equivalent formulation in terms of reverse lexicographic shifting is:

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

Our current proposal  is to use the following theorem and (a greatly modify) Conjecture B. (For general families.)

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 (from post 4, greatly modified from the one discussed in posts 2,3): For a family F of k-sets satisfying (*) we have

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

Also here, I hope to be able to present some experimental data soon.

Posted in Combinatorics, Mathematics over the Internet, Open problems, Polymath10 | Tagged , | Leave a comment

Polymath 10 Emergency Post 5: The Erdos-Szemeredi Sunflower Conjecture is Now Proven.

While slowly writing Post 5 (now planned to be Post 6) of our polymath10 project on the Erdos-Rado sunflower conjecture, the very recent proof (see this post) that cap sets have  exponentially small density has changed matters greatly! It implies a weaker version of the Erdos-Rado sunflower conjecture made by Erdos and Szemeredi. Let me remind the readers what these conjectures are:

The Erdos-Szemeredi Sunflower Conjecture: There is \epsilon >0 such that a family of subsets of [n] without a sunflower of size three have at most (2-\epsilon)^n sets. (Erdos and Szemeredi have made a similar conjecture for larger sunflowers.)

The strong Cap Set Conjecture: There is \delta >0 such that a subset of \mathbb Z_3^n without three distinct elements a, b, and c with a+b+c=0 contains at most (3-\delta)^n elements.

In order that the post with the cap set startling news will remain prominent, I will put the rest of this post under the fold.

Continue reading

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

Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem!

A quote from a recent post from Jordan Ellenberg‘s blog Quomodocumque:

Briefly:  it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday (GK: see also my last post) can indeed be used to give a new bound on the size of subsets of F_3^n with no three-term arithmetic progression! Such a set has size at most (2.756)^n. (There’s actually a closed form for the constant, I think, but I haven’t written it down yet.)

Here’s the preprint. It’s very short. I’ll post this to the arXiv in a day or two, assuming I (or you) don’t find anything wrong with it, so comment if you have comments!

This is amazing! The cap set problem was quite popular here on the blog, see also Tao’s 2007 post, and Jordan made also quite an effort over the years in proving the other direction before proving this direction. (Fortunately for our profession, success for two conflicting statements was avoided.) Congratulations to Jordan, Ernie, Seva, and Peter!

Update: Congratulations also to Dion Gijswijt who also derived a similar solution to the cap set problem based on CLP! See this comment on Quomodocumque.

gijswijt

Updates: See also this post by Tao (presenting a symmetric version of the proof), this post by Gowers, this post in by Luca Trevisan, and this post by Peter Cameron, and this post by Anurag Bishnoi.

Of course, there is also plenty of more to desire: Full affine lines for q>3, higher dimensional affine subspaces for q\ge3, some application to better bounds for Roth’s theorem, Szemeredi’s theorem, (for more, see this comment by Terry Tao,)… It is all very exciting.

Noga Alon also pointed out that the solution of the cap set problem also settles affirmatively the Erdos-Szemeredi weaker version of the Erdos-Rado Delta-system conjecture (via the connections discussed in this post) and also shows that a certain direction for showing that ω=2 for matrix multiplication cannot possibly work. The Erdos-Rado sunflower conjecture is still (at least for a few days) open.

Can the affine results be applied for integers or for combinatorial setting? The geometries are quite different but still… This is of great interest here (and also for other problems like the Kakeya problem). Starting from a positive density set in Z_3^n considered as a subset of Z_{3^{100}}^m we can find there a 10^{100}-dimensional affine subspace contained in the set. Can’t we use it (or such a subspace with a few additional pleasant properties) to get just a single combinatorial line over Z_3, or, easier, just a 3-term arithmetic progression when A represent a subset of {1,2,… , 3^n }?  A bit later: These thoughts about the relevance of finite field results to questions for the integers (or reals) are not really relevant to the new discovery.  But what seems to be relevant is the possibility to transfer the new method for the cap set problem back to the question on better lower bounds for Roth’s theorem.

More updates: Eric Naslund and Will Sawin gave a direct proof based on the polynomial method for the Erdos-Szemeredi sunflower conjecture, and an even  stronger result is given by Naslund here. (Eric also has stronger quantitative bounds for Erdos-Szemeredi based on bounds for cap sets.)   Ben Green has studied the analogue of Sarkozy’s theorem in function fields (other results on function fields are mentioned by Bloom in this comment);  Variants on the CLPEG-arguments are described by Petrov and by Bishnoi over the comment threads here and here.  Here is a paper by Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Chris Umans, on consequences of the cap set result for fast matrix multiplication.

cap

 

Posted in Combinatorics, Open problems, Updates | Tagged , , , , , | 18 Comments

More Math from Facebook

mffDavid Conlon pointed out to two remarkable papers that appeared on the arxive:

Joel Moreira solves an old problem in Ramsey’s theory.

Monochromatic sums and products in \mathbb N.

Abstract: An old question in Ramsey theory asks whether any finite coloring of the natural numbers admits a monochromatic pair {x+y,xy}. We answer this question affirmatively in a strong sense by exhibiting a large new class of non-linear patterns which can be found in a single cell of any finite partition of N. Our proof involves a correspondence principle which transfers the problem into the language of topological dynamics. As a corollary of our main theorem we obtain partition regularity for new types of equations, such as x^2-y^2=z and x^2+2y^2-3z^2=w.

Ernie Croot, Vsevolod Lev, Peter Pach gives an exponential improvement to Roth over \mathbb Z_4^n.!

Abstract: We show that for integer n>0, any subset A of Z^n_4 free of three-term arithmetic progressions has size |A|<2(\sqrt n +1)4^{cn}, with an absolute constant c approximately equal to 0.926.

David Ellis made a few comments: Three ‘breakthrough’ papers in one week – one in combinatorial geometry (referring to the Erdos-Szekeres breakthrough) , one in additive number theory and one in Ramsey theory – not bad!; . I’ve now read all of the proofs and am sure (beyond reasonable doubt) that they’re all correct – an unusually short time-frame, for me at any rate! The Croot-Lev-Pal Pach paper is a really beautiful application of the polynomial method – a ‘genuinely’ self-contained paper, too, and very nicely written.

I find the Z_4^n result quite mind boggling! What does it say about Z_3^n???  

Post by Green

In another facebook post Ben Green writes:  I Wish I could just casually hand Paul Erdos a copy of Annals of Math 181-1. 4 of the 7 papers are: solution to the Erdos distance conjecture by Guth and Nets Katz, solution to the Erdos covering congruence conjecture by Hough, Maynard’s paper on bounded gaps between primes, and the Bhargava-Shankar paper proving that the average rank of elliptic curves is bounded.

Posted in Combinatorics, Mathematics over the Internet, Updates | Tagged , , , | 3 Comments

The Erdős Szekeres polygon problem – Solved asymptotically by Andrew Suk.

Andrew_Suk

Here is the abstract of a recent paper by Andrew Suk. (I heard about it from a Facebook post by Yufei Zhao. I added a link to the original Erdős Szekeres’s paper.)

Let ES(n) be the smallest integer such that any set of ES(n) points in the plane in general position contains n points in convex position. In their seminal 1935 paper, Erdős and Szekeres showed that

ES(n)\le {{2n-4}\choose{n-2}}+1=4^{n-o(n)}

In 1960, they showed that

ES(n) \ge 2^{n-2}+1,

and conjectured this to be optimal. Despite the efforts of many researchers, no improvement in the order of magnitude has ever been made on the upper bound over the last 81 years. In this paper, we nearly settle the Erdős-Szekeres conjecture by showing that

ES(n)=2^{n+o(n)}.

This is amazing! The proof uses a 2002 “positive-fraction” version of the Erdős-Szekeres theorem by Pór and Valtr.

Among the many beautiful results extending, applying, or inspired by the Erdős Szekeres theorem let me mention an impressive recent body of works on the number of points in \mathbb R ^d which guarantee n points in cyclic position. A good place to read about it is the paper by Bárány, Matoušek and Pór Curves in \mathbb R^d  intersecting every hyperplane at most d+1 times, where references to earlier papers by Conlon, Eliàš,  Fox, Matoušek, Pach, Roldán-Pensado, Safernová, Sudakov, Suk, and others.

 

ES

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

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 , | 4 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.)”

3CONF

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

 

spencer3.

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

Joel1

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.

Bourgain

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.

speakers

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

poster3

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

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

poster-sadna.png

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
function

 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

pic1

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.

pic2

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