Another artistic view by Alef on mathematical collaboration.
Other Alef’s corner posts
Another artistic view by Alef on mathematical collaboration.
Other Alef’s corner posts
To cheer you up in difficult times here are songs by Sabine Hossenfelder and by Tom Lehrer. I like the music and lyrics and the unusual combination of science, humor and satire.
Sabine Hossenfelder : Outer space*
Tom Lehrer: That’s mathematics
Sabine Hossenfelder: Theories of everything
Tom Lehrer: Lobachevsky
Sabine Hossenfelder: Schrödinger Cat (The song follows by a physics explanation).
Tom Lehrer: The Professor’s Song (2:55 there is delta for every epsilon)
Sabine Hossenfelder: Ave Maria
Tom Lehrer: The Vatican Rag
Sabine Hossenfelder: Ivory Tower
Tom Lehrer: Elements
Sabine Hossenfelder: Not a Toy
Tom Lehrer The Hunting Song
Sabine Hossenfelder: A Million Miles
Tom Lehrer: Pollution
Sabine Hossenfelder: This is how I pray
Tom Lehrer: Wernher von Braun
Sabine Hossenfelder: Galaxy Song, Monty Python (cover)
Tom Lehrer: Poisoning Pigeons In The Park
Sabine: Catching light
Tom: National brotherhood week
Sabine Hossenfelder (left) Tom Lehrer (right)
A comparison between the Google estimator U for the fidelity and two improved estimators that we studied MLE (maximum likelihood estimator) and V (a variant of U). (More figures at the end of the post.)
Here are some links on quantum matters. I hope to return to them in more detail in some future posts.
Yosef Rinott, Tomer Shoham and Gil Kalai: Statistical aspects of the quantum supremacy demonstration, (arXive)
The notable claim of quantum supremacy presented by Google’s team in 2019 consists of demonstrating the ability of a quantum circuit to generate, albeit with considerable noise, bitstrings from a distribution that is considered hard to simulate on classical computers. Verifying that the generated data is indeed from the claimed distribution and assessing the circuit’s noise level and its fidelity is a purely statistical undertaking.
The objective of this paper is to explain the relations between quantum computing and some of the statistical aspects involved in demonstrating quantum supremacy in terms that are accessible to statisticians, computer scientists, and mathematicians.
Starting with the statistical analysis in Google’s demonstration, which we explain, we study various estimators of the fidelity, and different approaches to testing the distributions generated by the quantum computer. We propose different noise models, and discuss their implications. A preliminary study of the Google data, focusing mostly on circuits of 12 and 14 qubits is discussed throughout the paper.
I am greatly enjoying working with Yosi and Tomer, and I hope to devote a special post to the very interesting statistics of the Google supremacy experiment.
Here is how the paper concludes
Over the past four decades, the very idea of quantum computation has led to many advances in several areas of physics, engineering, computer science, and mathematics. I expect that the most important application will eventually be the understanding of the impossibility of quantum error-correction and quantum computation. Overall, the debate over quantum computing is a fascinating one, and I can see a clear silver lining: major advances in human ability to simulate quantum physics and quantum chemistry are expected to emerge if quantum computational supremacy can be demonstrated and quantum computers can be built, but also if quantum computational supremacy cannot be demonstrated and quantum computers cannot be built.
Some of the insights and methods characteristic of the area of quantum computation might be useful for classical computation of realistic quantum systems – which is, apparently, what nature does.
My Dec 19 2019 (B.C.) surprise lecture at the mathematics of quantum computing school and the afternoon panel on the same day. It turned out that the lecture was videotaped. The slides can be seen in this post. Remarkably, social distancing was pioneered by the session chair toward the end of the lecture (while not justified in that case).
Here once again again is the link for the panel discussion on quantum supremacy of the same day (reviewed here) . Here is a quote of mine from the panel.
Of course, it is important to think what are the implications of quantum supremacy, is it useful? what does it say on the extended Church-Turing thesis? on prospects for quantum error-correction and universal quantum computers? etc. but I think that in the next few years one thing that we need to also concentrate on is the following question: Is the Google experiment correct? Is this a correct scientific verification of quantum supremacy?
Four slides from my USTLC zoom lecture. (Click to enlarge.)
Poems by Peter Shor and Renan Gross (click to enlarge)
Peter Shor pioneered quantum poetry for the skeptics over Twitter. There were many very nice contributions all over social media by Renan Gross, John Dowling, Vidit Nanda, ⟨dl|yonge|mallo⟩, Alfred Marcel Bruckstein, Kenneth Regan, and others. Keep the quantum poems coming! Of course, the poems should be taken with humor. Here is a small taste.
Understanding nature and ourselves is a worthy dream
Requiring no interaction with the supreme
Rota’s Basis Conjecture holds asymptotically, by Alexey Pokrovskiy
Abstract: Rota’s Basis Conjecture is a well known problem from matroid theory, that states that for any collection of n bases in a rank n matroid, it is possible to decompose all the elements into n disjoint rainbow bases. Here an asymptotic version of this is proved. We show that it is possible to find n − o(n) disjoint rainbow independent sets of size n − o(n).
A rainbow basis is a basis with one element from each collection.
(I thank Nati Linial for telling me about it.)
Another way to formulate Rota’s basis conjecture (for representable matroids) is that if B1, B2, …, Bn are n bases of an n-dimensional vector space V (not necessarily distinct or disjoint), then there exists an n × n grid of vectors (vij) such that
1. the n vectors in row i are the members of the ith basis Bi (in some order), and
2. in each column of the matrix, the n vectors in that column form a basis of V.
If all the bases are the standard basis then this reduces to the existence of Latin squares.
Unrelated trivia question: AGC-GTC-TGC-GTC-TGC-GAC-GATC-? what comes next in the sequence?
We mentioned Rota’s basis conjecture in various earlier posts. A classic paper on the subject is the 1989 paper by Rosa Huang and Gian Carlo-Rota. Three and a half years ago Timothy Chow lunched a polymath project (Polymath 12) to solve it. (Here is my post on the project with various variants of the conjecture, the first post on the polymath blog, and the wiki). See this post for several famous conjectures by Rota, and this post about the related Alon-Tarsi conjecture.
Today we talk about the paper, Proof of Tomaszewski’s Conjecture on Randomly Signed Sums, by Nathan Keller and Ohad Klein.
Consider a unit vector That is . Consider all () signed sums where each is either 1 or -1.
Theorem (Keller and Klein (2020) asked by Boguslav Tomaszewski (1986)): For at least signed sums
Another way to state the theorem is that the probability of a signed sum to be in the interval [-1, 1] is at least 1/2.
To see that this is best possible consider the case that and let be non zero. For the sum in question to exceed one we need both summands to have the same sign which happens half of the times. There is another example of importance, the vector . Here 3/8 of the absolute values of signed sums (6 out of 16) are below 1 (in fact, equal to zero), 1/2 equal to 1 and 1/8 exceed 1. Holzman and Kleitman proved in 1992 that the fraction of absolute values of signed sums below 1 is always at least 3/8.
Congratulations to Nathan and Ohad. I will say a little more about the problem below but before that, a few more things.
Luca Trevisan posted on his blog In Theory a post “Silver linings” about two cheerful pieces of news. The first one is “Karlin, Klein, and Oveis Gharan have just posted a paper in which, at long last, they improve over the 1.5 approximation ratio for metric TSP which was achieved, in 1974, by Christofides.”
The second one is about breaking the logarithmic barrier for Roth’s theorem that we wrote about here. This was also discussed by Bill Gasarch on Computational Complexity. In the comment section of my post there is an interesting discussion regarding timetable for future achievements and how surprising they would be.
The third is about Ron Graham, a friend and a mathematical giant who passed away a few days ago. Here is a moving post by Fan Chung, a web page for Ron set by Fan, and a blog post by Dick and Ken on GLL.
The fourth is that there is a nice collection of open problems on Boolean functions that is cited in the paper of Nathan and Ohad: Y. Filmus, H. Hatami, S. Heilman, E. Mossel, R. O’Donnell, S. Sachdeva, A. Wan, and K. Wimmer, Real analysis in computer science: A collection of open problems.
The fifth is that both our (HUJI) combinatorics seminar and basic notions seminar are running and are recorded. Here are the links. (Hmm, the links are not yet available, I will update.)
Daniel Kleitman and Ron Holzman
If the s are all the same, or small, or random, then to compute the probability that the weighted sum is between -1 and 1, we can use some Gaussian approximation and then we will find ourselves in a clash of constants that goes our way. The probability will be close to a constant well above 1/2. So what we need to understand is the case where some s are large.
The problem first appeared in the American Math Monthly. Richard Guy collected several problems and challenged the readers Any Answers Anent These Analytical Enigmas? (I don’t know what the fate of the other questions is.) Holzman and Kleitman proved in 1992 that the fraction of absolute values of signed sums below 1 is always at least 3/8, and this is tight. For many years, 3/8 was the record for the original problem, until the 2017 paper by Ravi Boppana and Ron Holzman: Tomaszewski’s problem on randomly signed sums: Breaking the 3/8 barrier, where a lower bound of 0.406, was proved. The current record 0f 0.46 was proved in the paper Improved Bound for Tomaszewski’s Problem by Vojtěch Dvořák, Peter van Hintum, and Marius Tiba. The new definite result by Nathan and Ohad used some ideas of these early papers.
Let me quote what the authors kindly wrote me:
“The crux of the matter is how to deal with the case of very large coefficients (). We gave a short semi-inductive argument covering this case (this is Section 5 of the paper). The argument is only semi-inductive, as it requires the full assertion of Tomaszewski for any n'<n, and gives only the case () for . But this means that if we can handle all other cases by other methods then we will be done.
The semi-inductive argument takes only 3 pages. Handling the other cases takes 72 more pages and requires several new tools, but is closer to things that were done in previous works. (Actually, after we found the 3-page argument, we were quite sure we will be able to finalize the proof; this indeed happened, but took a year).”
Most of the paper deals with the case of small coefficients. This requires several ideas and new tools.
If all coefficients are “sufficiently small”, then we can
approximate X by a Gaussian and the inequality should follow. However, using the standard Berry-Esseen bound, this holds only if all coefficients are less than 0.16.
Nathan and Ohad showed that for Rademacher sums, namely random variables of the form , as discussed in the conjecture, a stronger Berry-Esseen
bound can be obtained, and this bound shows immediately that Tomaszewski’s assertion holds whenever all coefficients are less than 0.31. The stronger bound stems
from a method of Prawitz, presented in the 1972 paper. H. Prawitz, Limits for a distribution, if the characteristic function is given in a finite domain, which appeared in the Scandinavian Actuarial journal.
The second tool is local tail inequalities for Rademacher sums, of the form where a,b,c,d satisfy certain conditions. Inequalities of this kind were obtained before by Devroye and Lugosi in the 2008 paper: Local tail bounds for functions of independent random variables.
These local tail inequalities already have some other applications, e.g., to analysis of Boolean functions. They were developed and applied in an earlier paper paper of Keller and Klein: Biased halfspaces, noise sensitivity, and relative Chernoff inequalities. Let me mention my related MO question A variance tail description for continuous probability distributions.
A stopping time argument. Variants of Tomaszewski’s problem appeared in various fields. The problem was stated independently in a 2002 paper by Ben-Tal, Nemirovski, Roos, Robust solutions of uncertain quadratic and conic-quadratic problems. A stopping time argument introduced there (for proving a lower bound of 1/3) played a crucial role in subsequent works and the critical semi-inductive argument by Nathan and Ohad.
Refinements of the famous Chebyshev’s inequality. (Did you know Chebyshev’s full name? Ans: Pafnuty Lvovich Chebyshev.)
Q1: What can be said about families of signs that can serve as those signs for which for some vector .
Q2: What can be said about the complex version or even more generally about high dimensions?
Q3: Are there any relations to Littlewood-Offord type problems?
Q4: Is there any relation to the Komlos Conjecture?
We can ask about simpler or just different proofs for almost every result we discuss here. But here the statement is so simple…
This is a guest post kindly contributed by Noam Lifshitz. Here is a pdf version. This post is a continuation of the post To cheer you up in difficult times 3: A guest post by Noam Lifshitz on the new hypercontractivity inequality of Peter Keevash, Noam Lifshitz, Eoin Long and Dor Minzer, and it gives the proof of the new hypercontractive inequality. We plan a third post where various applications will be mentioned.
Before we get to the post I want to mention that there are a lot of activities on the web. I may devote a special post to links and discussion (and contributing links in the comment section is very welcome.) but meanwhile a few links: 1) Advances in Boolean Function Analysis Lecture Series (thanks to Avishay Tal and Prasad Raghavendra for letting me know); 2) Online course in Foundations of Algebraic Geometry Given by Ravi Vakil from Stanford. You can take the course at varying levels of involvement. (Thanks to Tami Ziegler for telling me) A very very interesting way of online teaching. 3) A site with online mathematical lectures.
Aline Bonami with Szilard Revesz and me (2006). Aline Bonami first proved the 2-point hypercontractive inequality which is very useful in the analysis of Boolean functions. (Leonard Gross proved it independently a few years later and William Beckner found important applications to harmonic analysis.)
Our aim is to prove the hypercontractivity theorem for global functions. The proof here is taken from a joint paper with David Ellis and Guy Kindler that’ll soon be out on the Arxiv.
Here we use the notations given in the last blog post. Let us first get a feel for our hypercontractivity theorem by proving the case. Here the RHS is
We will prove the following slightly stronger version of Theorem 1 for the case.
Let Let Then
Proof: Let us write for Rearranging, we have
The noise operator in the case is by definition equal to where is the expectation over operator, and is the identity operator. Hence,
Now when expanding the 4-norm of the function , we obtain
where we used the fact that the expectation of is 0. When looking at the right hand side of the global hypercontractivity theorem, we see most of the above terms except for the one involving the third norm of the Laplacian. Indeed we have
Hence we see that the only term in the left hand side that doesn’t appear with a greater coefficient in the left hand side is the term and by AM-GM we have
which allows us to upper bound the only term appearing in the left hand side but not in the right hand side by corresponding terms that do appear in the right hand side.
Next we are going to prove a theorem that doesn’t seem to fit to our setting, but we’re going to fit it in by force. Let be finite sets. Let us write for the linear space of complex valued functions on . The space can be identified with the space where a pair of function is identified with the function
Given two operators , the operator is the unique operator sending to . We write for The operator can also be defined more explictly in terms of its values on functions. The operator can be understood more explicitly by noting that it is the composition of the operators and Now the operator is given by where
Lemma 3: Let be measure spaces with finite underlying sets. Let be operators satisfying
for all functions
Here the spaces and are equipped with the product measure, where the measure of an atom is the product of the measures of its coordiates.
Proof: For each let be given by As mentioned Hence by hypothesis, we have
We may now repeat the same process on each of the other coordinates to replace the s by s one by one.
The strategy of our proof is to take the theorem
which we established in the case for , and to turn it into an essentially equivalent statement about 4-norms. We will then get a tensorised statement for general , which we will be able to convert back into our hypercontractivity theorem for global functions. Our idea is to encode our function as a function satisfying
The benefit of working with rather than is that in one may move between 4-norms and 2-norms by appealing to the hypercontractivity theorem there, which gives
at the cost of some noise.
To define we use Fourier analysis of Abelian groups. Let us briefly recall it. For simplicity let us assume that where is a prime. Let be a th root of unity. For any we have a character given by The are an orthonormal basis of and we write , where Note that is the constant function, and so we have
Our mission will first be to convert the -norm of a function to the norm of a different function.
We define an encoding operator by setting
as the are orthonormal and so are the Moreover, by the Fourier formula for Since -norms are always smaller than 4-norms on probability spaces, we’ve got the following corollary of Proposition 2.
Lemma 4. For all and all we have
We now reach the final little trick. We define a measure space whose underlying set is and where the measure is given by for and for We let be given by on and letting it be on This way Lemma 4 takes the form
The operator on satisfies where the latter refers to the noise operator on The characters satisfy and so we have the Fourier formula
We also have
This will allow us to conclude that
We will also encounter the operator which by abusing notation we also call encodes
as the function on
Now finally we can get to the understanding of the operator The space is the disjoint union of spaces of the form
By definition of the tensor product, for is the function
Proof: Lemmas 3 and 4 yield:
for any We now have
The first equality follows from the formula and the fact that commutes with the encoding. The inequality used hypercontractivity on the discrete cube. The last equality follows from the fact that the operator preserves 2-norms.
Once again Extraordinary news regarding Roth Theorem! (I thank Ryan Alweiss for telling me about it and Rahul Santhanam for telling me about Thomas and Olof’s earlier attempts.)
Suppose that is a subset of of maximum cardinality not containing an arithmetic progression of length 3. Let . Roth proved that .
A few days ago Thomas Bloom and Olof Sisask proved that for some
This is an extraordinary result!!! I will tell you a little more about it below.
I just heard yesterday the sad news that Ron Graham passed away. Ron was an extraordinary mathematician and an extraordinary person. I first met Ron in Montreal in 1978 and we met many times since then. Ron will be dearly missed.
From an abstract of a lecture by Thomas and Olof: “This is the integer analogue of a result of Bateman and Katz for the model setting of vector spaces over a finite field, and the proof follows a similar structure.”
A catchy (weaker) formulation which goes back to Erdos and Turan is:
Let be a sequence of integers so that , then the sequence contains an arithmetic progression of length three!!
Bloom and Sisask’s result implies, of course, Van der Korput’s result that the primes contain infinitely many 3-terms arithmetic progression as well as Green’s 2005 result asserting it for every dense subset of primes.
Szemeredi’s celabrated result extended Roth’s theorem to arithmetic progression of any fixed size, and Green-Tao celebrated 2008 result asserts that the primes (or a dense subsets of primes) contain arithmetic progression of any length. (The case of 3-term AP is so far much simpler for all the results mentioned below.)
A little more about the history of the problem below the fold
Sorry for the long blog silence. In this post I wish to give a few links each of which probably deserves a full post. I will start with
Here is a web-page by a student in my “Game Theory” course where you can play several two-players variants of John Conway’s game-of-life. (A couple of variants were considered before. See, e.g. this paper.)
I really enjoyed playing Rani’s games and it can certainly cheer you up in difficult times. Questions about the game, remarks, and suggestions for improvements and for new features, are most welcome.
Maya Bar-Hillel (left) and Ester Samuel-Cahn
Here is an interesting 2006 power point presentation entitled How to detect lies with statistics by Maya Bar-Hillel. This was a talk given by Maya at the conference honoring Prof. Ester Samuel- Cahn , Jerusalem, December 18-20, 2006, and it described a planned research project of Maya Bar-Hillel with Yossi Rinott, David Budescu and myself. At the end we did not pursue it, mainly because each of us was involved in various other projects (but also because we were skeptical about some aspects of it.) Ester Samuel-Cahn (1933-2015) was a famous Israeli statistician. (Here is a post by Yosi Levy in Hebrew about the conference and about Ester.)
The lecture starts with “Last year, Statistical Science celebrated 50 years for `How to Lie with Statistics’ the book [by Durell Huff] whose title inspired this talk.”
And here are a few other quotes from Maya’s presentation
“We are not sure a general toolkit for detecting lies with statistics can be developed. Perhaps that explains why none yet exists. We have shown just a collection of anecdotes. But they can be classified and categorized. Some do seem generalizeable, at least to some extent.”
and the conclusion
A famous quip by Fred Mosteller: “It is easy to lie with statistics, but easier to lie without them.”
Likewise, we should say: “It is possible to detect (some) lies with statistics, but easier to detect them with other means”.
Peter Keevash, Alexey Pokrovskiy, Benny Sudakov, and Liana Yepremyan’s paper New bounds for Ryser’s conjecture and related problems, describes remarkable progress very old questions regarding transversals in Latin square.
I came across a very interesting paper The topological Tverberg problem beyond prime powers by Florian Frick and Pablo Soberón with new bounds and a new method for topological Tverberg theorem in the non prime-power case.
A year ago I came across this cool facebook post by Rupei Xu
OMG! Just learned that Jaeger’s conjecture is false for every t>=3. An interesting consequence of it is that a specific version of Goddyn’s conjecture on thin spanning trees is false, which shows some negative evidence that the thin spanning tree approaches may fail to lead to a constant factor approximation algorithm for ATSP!
Let me mention two problems I posted 6-7 years ago about Conway’s game of life. Conway’s game of life for random initial position and Does a noisy version of Conway’s game of life support universal computation?