which was used for the official T-shirt for Jean-François Le Gall’s birthday conference.
See also this quanta magazine article by Kevin Hartness.
which was used for the official T-shirt for Jean-François Le Gall’s birthday conference.
See also this quanta magazine article by Kevin Hartness.
Credit George Csicsery (from the 1993 film “N is a Number”) (source)
(I thank Gady Kozma for telling me about the result.)
An old problem from analysis with a rich history and close ties with combinatorics is now solved!
The paper is: Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, and Marius Tiba, Flat Littelwood Polynomials exist
Abstract: We show that there exist absolute constants Δ > δ > 0 such that, for all n⩾2, there exists a polynomial P of degree n, with ±1 coefficients, such that
for all z ∈ C with |z|=1. This confirms a conjecture of Littlewood from 1966.
It is still a major open problem to replace by and by (ultra-flat polynomials).
The problem can be traced back to a 1916 paper by Hardy and Littlewood.
Shapiro (1959) and Rudin (1959) showed the existence of such polynomials when you only require for all z ∈ C with |z|=1.
The new result confirms a conjecture of Littlewood from 1966 and answers a question by Erdős from 1957.
If one allows complex coefficients of absolute value one, ultra flat polynomials exist by a result of Kahane (1980). Bombieri and Bourgain (2009) gave an explicit construction with sharper bounds.
The proof relies strongly on Spencer’s famous result :”Six standard deviation suffices”. (In fact, on a version of Spencer’s result by Lovett and Meka.) Continue reading
A couple weeks ago I told you about Avi Wigderson’s vision on the connections between the theory of computing and other areas of mathematics on the one hand and between computer science and other areas of science, technology and society on the other hand. In this spirit I am happy to inform about the conference “Computer Science and its Impact on the Future” to be held in Jerusalem, September 16-18, 2019. This is a joint conference of the Israel Academy of Science and Humanities and the (US) National academy of Science. Incidentally, September 17 2019 is the general elections day in Israel which will also have some impact on our future.
The program has sessions on quantum science and technology, computer science and society, computation and the life sciences, and AI and autonomous systems. The keynote speaker is Amnon Shashua who will speak on the promise of machime learning and AI in transforming industries. Other speakers are: Charles Bennett, Adi Stern, Dorit Aharonov, and Thomas Vidick (quantum); Noam Nisan, Omer Reingold, Shafi Goldwasser, and Moshe Vardi (society); Aviv Regev, Ron Shamir, Uri Alon and Leroy Hood (biology), Sarit Kraus, Eva Tardos, Naftali Tishby, and Gal Kaminka (AI), and David Harel (closing remarks).
As for startling connections between the theory of computation and other areas of mathematics let me refer to the very recent post with the big news on the sunflower conjecture.
In the spirit of the coming Israeli elections let me promise to report more on our recent great Oberwolfach conference, on my visit to CERN, and to tell more about the sunflower progress, and about various combinatorics (and more) news I heard about.
Update: in partial fulfillment of my promises here are a couple of pictures from CERN and Oberwolfach.
Richard Ehrenborg with a polyhedron
In the Problem session last Thursday in Oberwolfach, Steve Klee presented a beautiful problem of Richard Ehrenborg regarding the number of spanning trees in bipartite graphs.
Let be a bipartite graph with vertices on one side and vertices on the other side, and with vertex-degrees and .
Ehrenborg’s problem: Is it the case that the number of spanning trees of is at most
In words, the number of spanning trees is at most the product of the vertex degrees divided by the sizes of the two sides.
For example for the complete bipartite graph the number of the spanning trees is so equality hold. More genarally, equality holds for Ferrer’s graphs. Those are graphs where the vertices on the two sides are ordered and if is an edge so are and for and . See this paper of Richard Ehrenborg and Stephanie van Willigenburg.
Greetings from Oberwolfach from a great conference on algebraic, geometric, and topological combinatorics. Stay tuned for more pictures and updates from Oberwolfach and CERN, and also in case you did not see it already here is the link to the previous post with the sunflower news. And towards the end of this post a connection to Saint-Exupéry’s “Le Petit Prince”.
Or Hershkovich reported on FB group “diggings in mathematics” about the solution of the Cartan-Hadamard conjecture by Mohammad Ghomi and Joel Spruck. The conjecture, one of the most famous conjectures in Riemannian geometry, is a far reaching extension of the classic isoperimetric inequality for general Riemannian manifolds.
Here is the abstract: We prove that the total positive Gauss-Kronecker curvature of any closed hypersurface embedded in a complete simply connected manifold of nonpositive curvature $latex M^n, n\ge 2$, is bounded below by the volume of the unit sphere in Euclidean space $latex R^n$. This yields the optimal isoperimetric inequality for bounded regions of finite perimeter in M, via Kleiner’s variational approach, and thus settles the Cartan-Hadamard conjecture. The proof employs a comparison formula for total curvature of level sets in Riemannian manifolds, and estimates for smooth approximation of the signed distance function. Immediate applications include sharp extensions of the Faber-Krahn and Sobolev inequalities to manifolds of nonpositive curvature.
The proof is quite involved (the paper is 80 pages long) and is based on extending Kleiner’s approch for the 3- and 4- dimensional case. Or Hershkovich raised on FB an even more general question related to isospectral relations based on higher homology.
We also note a 2013 paper by Benoît Kloeckner and Greg Kuperberg The Cartan-Hadamard conjecture and the little prince
A page from Kloeckner-Kuperberg’s paper, and related FB posts by Greg (below).
WOW! The new paper https://arxiv.org/abs/1908.08483 improved bounds for the sunflower lemma gives the most dramatic progress on the sunflower conjecture since it was asked. Congratulations to Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang.
(Written on my smartphone will expand it when reconnected to my laptop.) (Reconnected) Rather, I will write about it again in a few weeks. Let me mention now that while the old difficult and ingenious improvements stayed in the neighborhood of Erdos and Rado initial upper bound the new result is in the neighborhood of the conjecture! (And is tight for a certain robust version of the problem!)
Update: Let me mention an important progress on the sunflower conjecture from 2018 by Junichiro Fukuyama in his paper Improved Bound on Sets Including No Sunflower with Three Petals. I missed Fukuyama’s paper at the time and I thank Sasha Kostochka and Andrew Thomason for telling me about it now.
Let me announce my CERN colloquium this Thursday, August 22, 2019, 16:30-17:30 entitled “The argument against quantum computers.” If you are at CERN or the neighborhood, please please come to the lecture. (Tea and coffee will be served at 16:00. ) If you are further away, there is a live broadcast.
A few weeks ago I uploaded to the arXive a new paper with the same title “The argument against quantum computers“. The paper will appear in the volume: Quantum, Probability, Logic: Itamar Pitowsky’s Work and Influence, Springer, Nature (2019), edited by Meir Hemmo and Orly Shenker. A short abstract for the lecture and the paper is:
We give a computational complexity argument against the feasibility of quantum computers. We identify a very low complexity class of probability distributions described by noisy intermediate-scale quantum computers, and explain why it will allow neither good-quality quantum error-correction nor a demonstration of “quantum supremacy.” Some general principles governing the behavior of noisy quantum systems are derived.
The new paper and lecture have the same title as my 2018 interview with Katia Moskvitch at Quanta Magazine (see also this post). Note that Christopher Monroe has recently contributed a very interesting comment to the Quanta article. My paper is dedicated to the memory of Itamar Pitowsky, and for more on Itamar see the post Itamar Pitowsky: Probability in Physics, Where does it Come From? See also this previous post for two other quantum events in Jerusalem: a seminar in the first semester and a winter school on The Mathematics of Quantum Computation on December 15 – December 19, 2019.
A slide from a lecture by Scott Aaronson where he explains why soap bubble computers cannot solve the NP-complete Steiner-tree problem. Noisy intermediate scale quantum (NISQ) circuits are computationally much more primitive than Scott’s soap bubble computers and this will prevent them from achieving neither “quantum supremacy” nor good quality quantum error correcting codes. (source for the picture)
Low-entropy quantum states give probability distributions described by low degree polynomials, and very low-entropy quantum states give chaotic behavior. Higher entropy enables classical information.
Today I would like to report about some breakthroughs in the area of combinatorics, and about blog posts in Yufei Zhao’s blog that describe these remarkable results (better than I can). Many of the coauthors in these breakthroughs are undergraduate students.
A collection of equiangular lines is a collection of lines so that the angles between every pair of lines in the same?
Here are two classical questions:
In 2000 Dom de Caen found for the first time an equiangular set of lines in space of size . (The crucial observation that one of the graphs in the Cameron–Seidel association scheme has a certain eigenvalue of large multiplicity. Prior to this construction, the largest sets had sizes of order . In de Caen’s example the lines have angles approaching 90 degrees, and question 2 for a fixed value of led to very different bounds. (For another result by Dom, see this post.)
There were some important progress on this problem by Igor Balla, Felix Dräxler, Peter Keevash, and Benny Sudakov, as featured in this Quanta Magazine article written by Kevin Hartnett. Zilin, Jonathan, Yuan, Shengtong, and Yufei finished off the problem in a clean and crisp manner, in a 10-page paper with a self-contained proof. On the way they proved the following very interesting theorem.
Theorem: A bounded degree graph must have sublinear second eigenvalue multiplicity.
Abstract: We prove a conjecture of Fox, Huang, and Lee that characterizes directed graphs that have constant density in all tournaments: they are disjoint unions of trees that are each constructed in a certain recursive way.
“Constant density in all tournaments” means that for some (and hence for all , every tournament with vertices has the same number of copies of . (On the nose!)
This result is related to the famous Sidorenko’s conjecture. Let me copy its description from the paper:
For undirected graphs, conjectures of Sidorenko and Erdős–Simonovits (commonly referred to as Sidorenko’s conjecture) say that for every bipartite graph , the -density in a graph of fixed density is minimized asymptotically by a random graph. Lately the conjecture has been proved for many families of though the conjecture remains open in general. In particular, the case is open.
Let me describe briefly three additional posts on Yufei’s blog with two results from 2018 and one result from 2014.
These are two remarkable papers by the same team of researchers. The paper on the number of independent sets in a regular graph settled a famous 2001 conjecture by Jeff Kahn. An earlier breakthrough on the problem was made by Zhao in 2009 when he was an undergraduate student.
Recently I wrote a post Matan Harel, Frank Mousset, and Wojciech Samotij and the “the infamous upper tail” problem describing a major breakthrough on the infamous upper tail problem. Over the years I heard a lot of lectures and private explanation on upper tails and the remarkable related mathematics. I remember lectures by Kim and Vu from the early 2000’s and by Varadhan from ICM 2010 describing (among other things) the fundamental paper by Chatterjee and Varadhan, and later works by DeMarco and Kahn, and by Chatterjee and Dembo and Lubetzky and Zhao and others. But when I wrote the post I realized my knowledge is too sparse for giving a thorough description, and I decided not to wait and write a short post. This post by Yufei describes some of the history very nicely as well as the major papers by Eyal and Yufei from 2012 and 2014.
I am very happy to announce two quantum events. First, I would like to announce a course “Computation, quantization, symplectic geometry, and information” in the first 2019/2020 semester at the Hebrew University of Jerusalem (HUJI). The course will by on Sundays 14:00-16:00. Second, I would also like to announce The 4th Advanced School in Computer Science and Engineering on The Mathematics of Quantum Computation on December 15 – December 19, 2019, at IIAS HUJI.
Emmy Noether (left) Grete Hermann (right)
“In the fall of 2019 Dorit Aharonov, Gil Kalai, Guy Kindler and Leonid Polterovich intend to run a new one semester course (as a Kazhdan seminar) attempting to connect questions about noise and complexity in quantum computation, with ideas and methods about “classical-quantum correspondence”.that are well studied in symplectic geometry. The course will be highly research-oriented, and will attempt to teach the basics in both areas, and define and clarify the interesting research questions related to the connections between these areas, with the hope that this will lead to interesting insights. The course is oriented to grad students (and faculty), with reasonable background in mathematics, and with interest in the connections between mathematical and computational aspects of quantum mechanics. (See below for a full description.)”
The course will by on Sundays 14:00-16:00 in Ross building.
See also the post Symplectic Geometry, Quantization, and Quantum Noise from January 2013. (The seminar was initially planned to 2014 but some bumps in the road delayed it to 2019.)
The Mathematics of Quantum Computation
The 4th Advanced School in Computer Science and Engineering
Event date: December 15 – December 19, 2019
“We will be organizing a math-oriented quantum computation school in the IIAS at the Hebrew university. No prior knowledge on quantum will be assumed. The school will introduce TCS and math students and faculty, who are interested in the more mathematical side of the area, to the beautiful and fascinating mathematical open questions in quantum computation, starting from scratch. We hope to reach a point where participants gain initial tools and basic perspective to start working in this area. (See below for a full description.)
Organizers: Dorit Aharonov, Zvika Brakerski, Or Sattath, Amnon Ta-Shma,
Main (confirmed) Speakers: Sergey Bravyi, Matthias Christandl, Sandy Irani, Avishay Tal, Thomas Vidick, (1-2 additional speakers may be added later).
Additional (confirmed) lectures will be given by: Dorit Aharonov, Zvika Brakerski, and/ Or Sattath. (1-2 additional speakers may be added later).”
The cover of Avi Wigderson’s book “Mathematics and computation” as was first exposed to the public in Avi’s Knuth Prize videotaped lecture. (I had trouble with 3 of the words: What is EGDE L WONK 0? what is GCAAG?GTAACTC ? TACGTTC ? I only figured out the first.)
Avi Wigderson’s book “Mathematics and computation, a theory revolutionizing technology and science” is about to be published by Princeton University Press. The link is to a free copy of the book which will always be available on Avi’s homepage. (See also this re-blogged post here of Boaz Barak.)
One main theme of the book is the rich connection between the theory of computing and other areas (in fact, most areas) of mathematics. See also this self contained survey (based on Chapter 13 of the book) by Avi Interactions of Computational Complexity Theory and Mathematics, which in 27 pages overviews relations to number theory, Geometry, Operator Theory, Metric Geometry, Group Theory, Statistical Physics, Analysis and Probability, Lattice Theory and Invariant Theory. Of course, Avi himself is among the main heroes in finding many paths between mathematics and the theory of computing over the last four decades.
Another theme of the book and of several talks by Avi is that the theory of computing has revolutionary connections with many fields of science and technology. Again, this theme is present in the entire book and is emphasized in Chapter 20, which also appeared as a self contained paper “On the nature of the Theory of Computation (ToC).” Let me quote one sentence from Avi’s book that I propose for discussion. (For the complete quote see the end of the post.)
The intrinsic study of computation transcends human-made artifacts, and its expanding connections and interactions with all sciences, integrating computational modeling, algorithms, and complexity into theories of nature and society, marks a new scientific revolution!
Of course, similar ideas were also expressed by several other prominent scientists, and let me mention Bernard Chazelle’s essay: The Algorithm: Idiom of Modern Science. (Feel free to give further examples and links in the comment section.)
I propose to discuss in the comment section the idea that the theory of computing offers a scientific revolution. Very nice cases to examine are the computational study of randomness and connections to statistics, connections with economy and connections with biology. Comments on the relations between the theory of computation and other areas of mathematics are also very welcome.
Avi’s concluding slide compared these three great theories of human understanding.
(Previous attempts of open discussions were made in the following posts on this blog: 10 Milestones in the History of Mathematics according to Nati and Me; Why is mathematics possible? (and a follow up post); When it rains it pours; Is it Legitimate/Ethical for Google to close Google+?; An Open Discussion and Polls: Around Roth’s Theorem; Is Mathematics a Science?)
Avi promotes the idea of the central place of the theory of computing in his talks and writings Continue reading