AviFest, AviStories and Amazing Cash Prizes.

avi wigderson1

 

Ladies and gentlemen,  a workshop in Princeton in honor of Avi Wigderson’s 60th birthday  is coming on October. It will take place at Princeton on October 5-8 2016 right before FOCS 2016.  Don’t miss the event !

Attendance is free but registration is required. Also there are funds for travel support for students for which you should apply before August 1st. Saturday lectures are joint with FOCS 2016 and will be held at the FOCS hotel (location TBA).

Here is what Boaz Barak, one of the organizers,  wrote about Avi and the event:

Avi is one of the most productive, generous and collaborative researchers in our community (see mosiac below of his collaborators). So, it’s not surprising that we were able to get a great lineup of speakers to what promises to be a fantastic workshop on Computer Science, Mathematics, and their interactions.

 

Cash Prizes!

Do you want to tell a story about Avi? or about Avi’s mathematics? or about collaborating with Avi? or to send some words of congratulations to Avi? Or something like that? Or something different? Or some reflections on the CS 1980 Technion picture below? or some guesses regarding the picture next to Avi in the very first post of this blog?

Continue reading

Posted in Combinatorics, Computer Science and Optimization, Conferences, Updates | Tagged | 1 Comment

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 that we considered in post 5) 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 minimum 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 monetary 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).) Continue reading

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

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.

Results  by Erdos and Szemeredi  give  that the Erdos Rado sunflower conjecture implies the Erdos-Szemeredi sunflower conjecture.  This implication is Theorem 2.3 in the paper  On sunflowers  and matrix multiplication by Noga Alon, Amir Shpilka, and Christopher Umans where many implications between various related conjectures are discussed (we discussed it in this post). One implication by Noga, Amir and Chris is that the  strong cap set Conjecture implies the  Erdos-Szemeredi sunflower conjecture!

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 , , , | 35 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. See also this lovely quanta article  Set proof stuns mathematicians by Erica Klarreich. See also the post Polynomial prestidigitation on GLL. There, among other things the relation to Smolensky’s early use of the “halving degree trick” for the polynomial method is noted. (See also this comment.)

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.

More updates (May 31): New applications are mentioned in a new post on quomodocumque: sumsets and sumsets of subsets including a lovely new application by Jordan, a link to a paper  by Robert Kleinberg: A nearly tight upper bound on tri-colored sum-free sets in characteristic 2. And here is a link to a new manuscript by Fedor Petrov Many Zero Divisors in a Group Ring Imply Bounds on Progression–Free Subsets.

One more: (Quoting Arnab Bhattacharyya, June 15 2016 on GLL) Another amazing result that follows from these techniques for one of my favorite problems: http://arxiv.org/pdf/1606.01230v2.pdf. Fox and LM Lovasz improve the bounds for the arithmetic triangle removal lemma dramatically, from a tower of two’s to polynomial!

More (Early July 2016) : An interesting new post on Ellenberg’s blog.

cap

 

Posted in Combinatorics, Open problems, Updates | Tagged , , , , , | 19 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