Quick announcements of past (recorded) and future events

1) Shachar Lovett was the Erdos Speaker for 2022 and his great talks are recorded. (Lecture 1, Tensor ranks and their applicationslecture 2, The monomial structure of Boolean functions, lecture 3, Point location: an interface between geometry, machine learning and complexity.)

4) This year I also give the Turàn memorial lectures in Budapest. The first talk Discrete Geometry – When Combinatorics Meets Convexity was given by zoom and here is a link to the recording. The two remaining talks, one devoted to probabilistic combinatorics and one devoted to extremal combinatorics will take place live (but in a hybrid setting) on June in Budapest.

5) The Simons Center at Berkeley celebrates on May 25-27 its 10th Anniversary Symposium (I plan to devote to it a special post).

7) Remote lectures open up new opportunities. This summer I was invited to give a lecture in Indonesia and last fall I gave a lecture at Lahore, Pakistan.

One of my first posts on this blog was a 2008 post Five Open Problems Regarding Convex Polytopes, now 14 years later, I can tell you about the first problem on the list to get solved.

Imre Bárány posed in the late 1990s the following question:

For a -dimensional polytope and every , , is it true that ?

Now, Joshua Hinman settled the problem! In his paper A Positive Answer to Bárány’s Question on Face Numbers of Polytopes he actually proved even stronger linear relations. The abstract of Joshua’s paper starts with the very true assertion: “Despite a full characterization of the face vectors of simple and simplicial polytopes, the face numbers of general polytopes are poorly understood.” He moved on to describe his new inequalities:

The 2006 expectation threshold conjecture gives a justification for a naive way to estimate the threshold probability of a random graph property. Suppose that you are asked about the critical probability for a random graph in G(n,p) for having a perfect matching (or a Hamiltonian cycle). You compute the expected number of perfect matchings and realize that when p is C/n this expected number equals 1/2. (For Hamiltonian cycles it will be C’/n.) Of course, if the expectation is one half, the probability for a perfect matching can still be very low; indeed, in this case, an isolated vertex is quite likely but when there is no isolated vertices the expected number of perfect matchings is rather large. Our 2006 conjecture boldly asserts that the gap between the value given by such a naive computation and the true threshold value is at most logarithmic in the number of vertices. Jeff and I tried hard to find a counterexample but instead we managed to find more general and stronger forms of the conjecture that we could not disprove.

Two years ago Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Jinyoung Park proved a weak form of the conjecture which was proposed in a 2010 paper by Michel Talagrand. (See this post.) Indeed, the expectation threshold conjecture had some connections with a 1995 paper of Michel Talagrand entitled Are all sets of positive measure essentially convex? In a 2010 STOC paper Are Many Small Sets Explicitly Small? Michel formulated a whole array of interesting conjectures and commented that he feels that these conjectures are related to the expectation threshold conjecture to which he offered a weaker fractional version. This weak version suffices for various applications of the original conjecture. Keith, Jeff, Bhargav, and Jinyoung’s work built on the breakthrough work of Alweiss, Lovett, Wu and Zhang on the Erdős-Rado ‘sunflower’ conjecture.

Proving the full expectation threshold conjecture looked like a difficult task. The only path that people saw was to try to relate Talagrand’s fractional expectation threshold with our expectation threshold. (Indeed Talagrand also conjectured that they only differ by a multiplicative constant factor. This looked if true very difficult to prove.) However this is not the path taken by Jinyoung Park and Huy Tuan Pham and they found a direct simple argument! Jinyoung and Huy Tuan also used their method to settle one of the central conjectures (Conj 5.7) from Talagrand’s paper and this will be presented in a forthcoming paper.

The logn gap in our conjecture looked rather narrow but now that it was proved we can ask for conditions that will guarantee a smaller gap. For example, when is the gap only a constant?

Here is a nice IAS video on Jinyoung Park’s path to math.

A few days ago I received by mail Imre Bárány’s new book Combinatorial Convexity. The book presents Helly-type theorems and other results in convexity with combinatorial flavour. The choice of material and the choice of proofs is terrific and it is an ideal book for a course for graduate students and advanced undergraduates. Congratulations, Imre!

This book is about the combinatorial properties of convex sets, families of convex sets in finite dimensional Euclidean spaces, and finite points sets related to convexity. This area is classic, with theorems of Helly, Carathéodory, and Radon that go back more than a hundred years. At the same time, it is a modern and active field of research with recent results like Tverberg’s theorem, the colourful versions of Helly and Carathéodory, and the (p,q) theorem of Alon and Kleitman. As the title indicates, the topic is convexity and geometry, and is close to discrete mathematics. The questions considered are frequently of a combinatorial nature, and the proofs use ideas from geometry and are often combined with graph and hypergraph theory.

The book is intended for students (graduate and undergraduate alike), but postdocs and research mathematicians will also find it useful. It can be used as a textbook with short chapters, each suitable for a one- or two-hour lecture. Not much background is needed: basic linear algebra and elements of (hyper)graph theory as well as some mathematical maturity should suffice.

Abstract:The amplituhedron is a geometric object, introduced by Arkani-Hamed and Trnka (2013) in the study of scattering amplitudes in quantum field theories. They conjecture that admits a decomposition into images of BCFW positroid cells, arising from the Britto–Cachazo–Feng–Witten recurrence (2005). We prove that this conjecture is true.

Congratulations to Chaim, Tsviqa, and Ran!

Quick remarks:

The introduction to the paper give a very friendly introduction of the topic as well as a variety of results between 2013 and today.

Ran Tessler gave recently a lovely colloquium talk about the result in Tel Aviv University, here are the slides.

This blog post is kindly written by Ehud Friedgut.

My daughter, Shiri, who’s in seventh grade, had the following question in a math exam:

How many cubes of 2×2×2 fit into a box of size 8×4×3?

Shiri divided the volumes, getting the answer 12, but it was, of course, a trick question, and the intended answer was 8.

But I thought to myself – is eight really the best? (I’m pretty sure the answer is yes, but I’m only 99% sure.)

Test your intuition: Is the answer 8 ?

This gave birth to the following question (for which I know the answer):

Is there an integer n such that you can fit n+1 squares of size 1 (with disjoint interiors) into a rectangle of size (n+0.999) × 1.9999 ?

How about a rectangle of size (n+0.999) × 2.9999 ?

Knowing me, (and/or my type) you can probably guess, using pure logic, what the answers are to these two last questions (otherwise, why ask both?). Hint: for the first question use , for the second one, try n=2.

I’m happy that I could use my iPad to drag and rotate little squares and try to squish them into the rectangle, it’s helpful to be hands-on.

Here is a short email interview from April 2021 with Michael Brooks from “New Scientist”.

Dear Professor Kalai,I’m writing a short feature for New Scientist magazine on the theme “Will we ever have a useful quantum computer?”. I’m aware of your work on the problems with noise, and your position that error correction won’t be possible.

This is correct. My analysis asserts that quality error correction won’t be possible and that even the easier target of HQCA (huge quantum computational advantage) won’t be possible. Here is a link to my new paper that you may find useful. It refers to recent developments: the Google Sycamore experiment and HQCA claims are discussed in Sections 6 and 7, and there is a new Section 9 regarding the very recent developments.

I was wondering whether anything you’ve seen – demonstrations or arguments – in the last few months have done anything to change your mind, or whether you are now more convinced than ever that we won’t ever see truly useful (beyond doing science) quantum computing?

Well, I think that my theory is rather strong but not ironclad. As for the level of my conviction, it does not change often, but roughly speaking there were three stages to my research (and level of conviction):

1) 2005-2013. What I did was (in hindsight) exploring consequences of the failure of quantum fault tolerance and, on the way, some mistakes in the logic of firmly believing that quantum computers could be built. But, as I often said at that time, I did not think my work then gave a reason for people to change their a priori beliefs.

2) 2013-2019. Following my work with Guy Kindler I saw a clear scientific argument for why quantum computers will fail. (We first considered the special case of boson sampling and later I extended it in greater generality.) Since that time, I regard my argument to be strong enough to change people a priori beliefs, and my level of conviction went up as well. But, as I said, it is not an ironclad argument.

3) 2019 – onward. The experimental claims by Google and later by a group from Hefei, China would, if correct, refute my argument. So, naturally, this casts some doubts also in my mind. However, there are good technical reasons to doubt the fantastic claims by the Hefei group, and on that matter actually my 2014 paper with Kindler comes to play. The situation with the Google experiment is more delicate, but there are reasons to doubt their experimental claims as well.

As for a priori beliefs: In my view the situation is that it is hard to believe that quantum computers are not possible, but it is even harder to believe that quantum computers are possible 🙂 . So much experimental and theoretical research is needed before humankind will crack this puzzle.

Also, I was wondering if the retraction of the main paper about creating Majorana fermions (https://www.nature.com/articles/d41586-021-00612-z) kills topological computing’s hopes of getting us there?

No, the retraction of a single paper does not kill at all topological computing’s hopes. In fact, the researchers who found the mistake are hopeful that a successful experiment of that kind is possible and are also hopeful regarding further experimental steps towards topological quantum computing.

My general argument does extend to topological quantum computing and asserts that stable topological qubits are not possible.

Thanks for your interest and best wishes, Gil Kalai

Additional comments: The (very nice) article appeared in August 2021 and (accurately) refers to my position: “Gil Kalai, a mathematician at the Hebrew University of Jerusalem in Israel, argued that the basic noise level in a quantum computer will always be too high, no matter how many qubits are available. ‘My analysis says that correcting quality errors will not be possible.’ ” The article quotes also Sabrina Maniscalco from the University of Helsinki in Finland who said: “Finding a cure for the effect of environmental noise is not only, in my opinion, a technological problem, but more conceptual and fundamental. I would say that I am optimistic, rather than confident”.

My debate with Aram Harrow over GLL started ten years ago. A lot has happened in these ten years! (Here is a comment from the debate on my assessment of the situation at that time.)

The researchers who took on themselves the thankless task of putting the Microsoft Majorana claims under scrutiny and found the mistakes are Sergey Frolov and Vincent Mourik. (See also Frolov’s commentary in “Nature” and this article in “Quanta Magazine”.) They drew important conclusions for the need of sharing raw data and other experimental details for such experiments.

This is my fifth and last report from ICM 2018 at Rio. I will talk a little about the three Wednesday plenary talks by Assaf Naor, Geordie Williamson, and Christian Lubich. See here for other posts about ICM2018. (For the three talks, I relied on a recent viewing (Dec. 2021) of the videotaped lectures rather than on my incomprehensible earlier notes.)

While at the Rio conference, I met, for the first time, quite a few people including the (then) current and previous IMU president Shigefumi Mori and Ingrid Daubechies, and the current IMU secretary Holge Holdem. I went mainly to the combinatorics and TCS sessions. The highlight of the opening ceremony that I watched with Itai Benjamini and Tammy Ziegler in Tel Aviv was the announcements of Field-medal recipients, and I enjoyed also when Mori recounted his first ICM where he had been awarded the Fields medal and how nervous he was.

The plan for this post

So the plan for this post is as follows: I will share with you some memories of Assaf, whom I know since he was an undergraduate student at HUJI, and will then proceed to tell you about the three ICM plenary talks of Christian, Geordie, and Assaf.

Two memories with Assaf

I have known Assaf since he was an undergraduate student at HUJI. He took my first year course on discrete mathematics, and he told me an amusing story about it.

The lecture took place in “Canada lecture hall” where there were four rolling blackboards, each divided into 12 or so rectangular parts that I will call “blackboardettes”. Once I finished writing on some of the small blackboardettes, I had the habit of moving on to a completely random new one. The students found it frustrating since they could not trace back to the previous blackboardette. So one day I came to class and saw that the students numbered the blackboardettes from 1 to 48 in a random way. The students respected my disposition of writing on the blackboard in a completely unorganized way but they still wanted to be able to trace back. When I saw the numbering, I immediately realized the intention (or so Assaf says), I complied with the numbering, and the students were pleased about it.

The next memory about Assaf and me was from a really great conference at Edinburgh in the early 2000s. It was one of two conferences, where I came with a large delegation of seven members: my wife and children and also my mother and sister. We were all living in some dormitories and the lectures were a 15-minute walk away. One morning Assaf and I somehow went there after the main group of mathematicians, Assaf followed me to the location of the lectures, we pleasantly chatted about various things, and after 45 minutes he asked me if I knew where I was going and my response was “no”. (But somehow we got there, eventually.) You can read some India mathematical memories about Assaf in this post.

Let me make a small diversion and mention the other conference which I attended with a delegation of the same seven members, my wife and children, mother and sister. The conference took place in 1997 in a town Sant Feliu de Guíxols a little north of Barcelona in Catalonia, Spain. The main organizer was Anders Björner and it was essentially a highly successful union of several sub-conferences on several areas of combinatorics. One day we went to tour a picturesque town nearby and I found myself at the head of the group talking with a colleague, and behind me was a long line of 100 or so participants and a few family members. At some point I discovered that the path of mathematicians crossed itself! like this

and still people obediently followed with no shortcuts! I think that my path with Assaf in Edinburgh was at least a self-avoiding walk, but I cannot swear that this was indeed the case.

The lectures by Lubich, Williamson, and Naor (incomplete)

Christian Lubich

Before reaching out to my lecture notes I would like to share with you one thing that I have learned and still remember: You have to adopt the numerical methods to the deep structures of the problem. The law for the numeric is the same as the law for the system. (Another way to say it is: a good algorithm should respect the structure of the problem). This reminds me of something important about noise: that often, the noise respects the same laws as the system. Numerical approximation for mathematical systems seems similar in spirit to real-life approximation of (or by) mathematical systems. Another way to think about it is as follows: you have an ideal mathematical system say a PDE. Now, on the one hand you want to think about real life systems that are ideally described by this PDE. On the other hand, you want to think about numerical schemes that approximate the PDE. Maybe these two are two sides of the same coin.

Now, said Christian, the structure of the problem often refers to geometry. So this brought geometry into the problem and led to the theory of geometric numerical integration. And the systems considered in the lecture were Hamiltonian systems.

The lecture moved on from Hamiltonian ordinary differential equations to multi scale Hamiltonian systems to Hamiltonian PDEs, then considered low rank approximation and concluded with quantum systems. And when you hear the lecture you feel that you understand these concepts; everything is gentle and friendly. I will mention one more thing: the Euler numerical method was introduced 250 years before the lecture. And Christian mentioned one system – the solar system. (He showed a picture that still included Plato.) He explained why the symplectic version of Euler’s method is appropriate, and then moved on to discuss numerical evidence that the solar system is chaotic. OK I will stop here and leave out many exciting punchlines and details. For much more, watch the video!

A disclaimer regarding Christian Lubich’s lecture

Sometimes when talk number k in a conference is incomprehensible or when I don’t enjoy it for any other reason I skip talk number k+1 . (I know this is neither so fair nor rational.) Usually, when I hear a good talk I have a greater passion for hearing the next talk. But on Wednesday morning I was so overwhelmed by the great performances of Geordie, and Assaf that I could not stay for another talk. Instead, I only saw the videotaped lecture a few weeks later. The best way for that, I found out, was while babysitting my grandchildren in the evenings when my daughter Neta and her husband Eran went out to a restaurant or a movie and Ilan and Yoav were sleeping. (I could see there the lecture on their TV which was directly connected to a computer.) For a few months after the ICM, I saw the video in four overlapping parts and I greatly enjoyed it. (and also Eran and Neta enjoyed my volunteering.) Lubich’s lecture was also a great lecture, and I am sure that the live version was even greater. I got very excited by the topic and some of the major insights.

Christian talked about numerical methods and approximations and I thought about noise which I like, and this reminded me of the saying that if you if you have a hammer you treat everything as if it were a nail.

Little diversion: If you have a hammer, it is actually a good idea to treat everything as if it were a nail.

Indeed, it occurred to me recently that the famous description of treating everything as nails if you have a hammer, is more obliging than demeaning. In my view, it is a good thing to think about matters in the lens of your tools, even for the purpose of reaching to other areas and eventually adopting other tools.

Geordie Williamson

One great conjecture that I had been hearing about since the 1980s is the conjecture that the Kazhdan-Lusztig polynomials have non-negative coefficients for all Coxeter groups. The case of Weil groups was proved by Kazhdan and Lusztig in the late 1970s. In 2012 David Kazhdan gave a class about the startling solution of Elias and Williamson to the Kazhdan-Lusztig conjecture for general Coxeter groups. (The class mainly described Soergel’s program for solving the conjecture.) Later, I first met Geordie in person at the Berlin 2016 European Congress of Mathematics. Here is a great talk by Geordie on representation theory and geometry.

A) Groups and representations: a quick explanation of representation theory.

The idea is that groups in mathematics are everywhere, groups are complicated nonlinear objects, and representation theory is an attempt to “linearize” groups, thus studying simpler objects and then drawing conclusions for groups.

Geordie’s first example was the group of symmetries of the icosahedron which is also a group of isometries (represented by matrices) of ,

Why study representations? Geordie first mentioned the symmetric group (which is related to later parts of the talk, and to a lot of combinatorics) and Galois representations (which are related to various other talks in the conference).

Next came the notions of simple and semi simple representations followed by an example of a representation that is not semi-simple but still has some structure that resembles semi-simplicity.

B) The semi-simple world; how geometry enters the picture, and how algebraic arguments can replace geometric arguments.

Two fundamental theorems are:

Maschke 1897: every representation of a finite group is semi-simple.

The proof (which was given in the lecture!) explains how geometry enters the story.

Weyl 1925: every representation of compact Lie group is semi-simple.

C) Beyond semi-simple representations: Kazhdan-Lusztig theory.

Geordie talked about the group as a guide for going beyond compact lie groups and semisimplicity. A bit later toward the Kazhdan-Lusztig theory he talked about (It should be caligraphic sl, I suppose), namely complex matrices with trace 0. He then proceeded to describe the Verma modules which play a central role in the story and the Kazhdan-Lusztig conjecture regarding the description of the representation on the Verma modules. He explained that orthogonality and direct-sum structures for the compact Lie group theory was replaced by certain “canonical basis” and filtrations for algebraic structures beyond semi-simplicity. The Kazhdan-Lusztig conjecture was settled shortly after it was posed using geometric tools along with a related conjecture by Jantzen. It took almost four decades for algebraic proofs (which gives plenty more) to be found.

D) Shadows of Hodge theory: Soergel’s program, Elias-Williamson’s algebraic proof for Kazhdan-Lusztig conjecture (and the positivity conjecture); and various other conjectures.

Geordie mentioned that his proof with Elias gives a sort of shadow of Hodge theory in cases where algebraic varieties do not exist and mentioned other cases where shadows of Hodge theory are known and expected. This is also related to June Huh’s lecture that we discussed in this post.

E) Modular representations, Lusztig’s new character formula, and the billiard conjecture

While the representation theory of the symmetric group over the complex numbers is a well developed theory, once you move to finite fields our knowledge is considerably lower. Geordie described some results and conjectures in this direction.

This reminds me that in the early nineties, Micky Ajtai was interested in applications of modular representation of for computational complexity theory.

What did Cartan write to Weyl? In what year was the first algebraic proof of the Weyl theorem discovered? What was the role of Kasimir? How does Verma fit the picture? and Harish-Chandra? And why was the Kazhdan-Lusztig theory revolutionary? For all this and more, watch the video!

Assaf Naor

For this talk, like the other preceding talks, the interplay between linear and non-linear objects is an important theme.

The “Ribe program” is an attempt to organize the vast world of metric spaces. Metric spaces have many connections within mathematics, pure and applied, and connections to theoretical computer science, as well as other sciences. Special cases of metric spaces which originally motivated Martin Ribe are metrics described by normed spaces, and for them there is an important well-developed theory. Ribe discovered that many properties of normed spaces are “metric properties in disguise”, and this gives an opportunity to extend notions and results from the theory of Banach spaces to general metric spaces; Spanning several decades, this program have now become a large theory. (Normed metric spaces are described by their unit balls which are centrally symmetric convex sets that we like here on the blog.) General metric spaces are much more general objects than normed spaces, and it looks like a rather wild idea that insights about normed metric spaces extend to metric spaces described by Riemannian manifolds, complicated molecules, or by the connection-graph of the internet. Assaf mentioned Jean Bourgain and Joram Lindenstrauss as having pioneering roles.

“Dimension reduction” is also a very important paradigm common to many mathematical and scientific disciplines. The question is of finding useful ways of representing high dimensional data in low dimensions. Much of Assaf’s talk was devoted to dimension reduction within the Ribe program.

A very general framework is the question: When can you find a metric space inside a class of metric spaces, where “find” can refer to various notions of embeddability. Among the opening examples of a theorem in this direction, Assaf mentioned the existence of metric spaces proved by him with Eskenazis and Mendel, that you cannot “find” even in a very weak sense in any spaces of nonpositive curvature.

Dimension reduction 1: the Johnson-Lindenstrauss lemma

Johnson-Lindenstraus: Any billion vectors in a billion-dimensional vector space can be realized in 329 dimensions with distortion at most 2!

(In general, to get a constant distortion you can go (and need to go) to dimension.)

Dimension reduction 2: From Bourgain to Matoušek

What happens when you start with an arbitrary metric space of n elements? Can you embed it in some log n-dimensional normed space? Assaf gave a proof based on volumes for why you cannot go below log n. Next came a result by Bourgain that showed that dimensions are necessary. Some years later Linial, London and Rabinovich showed that are required, and a breakthrough 1996 result by Matoušek who showed that you need dimensions for some ! Twenty years later, in 2016, Naor proved that -dimensions are required even for a much weaker form of embedding where the distortion is taken on average.

Generalized notions of expanders

Toward the end of the proof Assaf defined a generalized notion of expanders: Ordinary expanders correspond to the -norm and there are analogous definitions for every norm.

Again, for much more, watch the video.

ICM 2022 St Petersburg

Our gifted columnist Alef has updated his ICM2022 drawing; he added a bit of the St. Petersburg skyline and diversified the participants. Here it is.