To cheer you up in difficult times 5: A New Elementary Proof of the Prime Number Theorem by Florian K. Richter

Here is a piece of news that will certainly cheer you up: Florian Richter found A new elementary proof of the prime number theorem. (I thank Tami Ziegler for telling me about the new result.)

From left to right: Atle Selberg, Florian Richter, and Paul Erdos

From the Introduction

“One of the most fundamental results in mathematics is the Prime Number Theorem, which describes the asymptotic law of the distribution of prime numbers in the integers.

Prime Number Theorem. Let π(N) denote the number of primes smaller or equal to a positive integer N. Then

\lim_{N \to \infty}   \frac {\pi (N)}{N/\log N}~=~1

The Prime Number Theorem was conjectured independently by Gauß and Legendre towards the end of the 18th century and was proved independently by Hadamard and de la Vallée Poussin in the year 1896. Their proofs are similar and rely on sophisticated analytic machinery involving complex analysis, which was developed throughout the 19th century by the combined effort of many great mathematicians of this era, including Euler, Chebyshev, and Riemann (to name a few).

Even though it was believed for a long time not to be possible, more than 50 years after the analytic proof of the Prime Number Theorem was discovered, an elementary proof was found by Erdős and Selberg [Erd49; Sel49]. In this context, elementary refers to methods that avoid using complex analysis and instead rely only on rudimentary facts from calculus and basic arithmetic identities and inequalities. Their approach was based on Selberg’s famous “fundamental formula”:

\sum_{p \le x}\log ^2(p)~+~\sum_{pq \le x}\log (p)\log (q)~=~2x\log (x)+O(x).

In this paper we provide a new elementary proof of the Prime Number Theorem, using ideas inspired by recent developments surrounding Sarnak’s and Chowla’s conjecture. With the exception of Stirling’s approximation formula, which is used in Section 3 without giving a proof, our proof is self-contained.”

The introduction also cites papers on the history of the analytic method and an abridged version of it by Newman, on several earlier elementary proofs of the PNT, and on recent dynamically inspired way by McNamara of deriving the Prime Number Theorem from Selberg’s fundamental formula.

Some thoughts and remarks

What precisely is elementary, formally?

What is the formal distinction between elementary and non-elementary proofs of the PNT? (This was explained to me several times but I don’t remember the details.) The distinctions between “non-explicit” and “explicit” proofs (or constructions) and between “effective” and “non-effective” proofs are quite clear cut. But here I am less certain.

Are there other important distinctions about proofs that you are aware of?

PNT and Boolean functions (weighted majority functions)

An equivalent formulation of the prime number theorem is the following:

(*)~~~ \sum_{k \le n}\mu (k)~=~o(n),

where \mu is the Mobius function. Consider now a Boolean function f(x_1,x_2, \dots, x_n) with n variables. Here the variables x_i and the function f has values in \{0,1\}. Given n nonnegative weights w_1\le w_2 \le \cdots \le w_n and C>0 the function $f$ is a weighted majority function if f=1 iff w_1x_1+\cdots +w_nx_n \le C. Let p(f) be the probability that f=1, and let \hat f[n] be the top Fourier coefficient of f.

Problems:

(1) Find conditions for a weighted majority function f that guarantee that

(**)~~~ \hat f([n])~=~o( p(f))

Let p_k be the kth prime, w_k = \log p_k, and C=\log n. The PNT asserts that the Boolean function associated to these parameters satisfies (**). (It is very easy to see that (**) and (*) are essentially the same.)  From vague understanding of some fragments of older elementary proofs of the PNT it looks that the proofs could perhaps be described in this way, namely starting with some weaker properties on the weights (namely the primes)  perhaps the derivation of (**) apply to general weighted majority functions with these properties. (This is related to PNT for systems of Beurling primes.) Finding conditions for (**) is interesting also for other weighted majority functions where the weights are not related to the growth behavior of the primes.  In fact, the following is also interesting:

(2) Find conditions for (general) Boolean functions f that guarantee that (**) holds, namely that the top Fourier coefficients is little o of p(f). Signs of low degree polynomials form a very interesting class of  Boolean functions, and they are of special interest also here.

Remark: The first problem looks very related to PNT for systems of Beurling primes going back to 1937 paper by Arne Beurling. (Based on the inequality 1937 < 1949, I understand that Breuling’s proof was not elementary, and I don’t know if the elementary proofs for PNT gives Breuling’s theorem as well.)

PNT here on the blog and Mobius randomness

The new paper is related to conjectures by Chowla and Sarnak and to the notion of Mobius randomness that we considered in an earlier post. The basic question is for which functions f of k, {\bf (***)} \sum_{k \le n} \mu (k)f(k) = o(\sum_{k \le n}f(k)). This is correct if f is random (or random-like in a variety of meanings), and it turns out to be correct if (in some sense) if f is of low complexity. We also mentioned some analogs of the PNT in this post. Both polymath 4 and polymath5 had some connections to the PNT.

Is PNT to expanders like RH to Ramanujan graphs?

This is another connection to combinatorics, See this post in “In Theory”.

Posted in Number theory, Updates | Tagged , , | 5 Comments

To cheer you up in difficult times 4: Women In Theory present — I will survive

An amazing video

(Update, May18 2020). I failed to explain what WIT is and this may have caused some misunderstanding. Here is a description from the Simons Institute site.

“The Women in Theory (WIT) Workshop is intended for graduate and exceptional undergraduate students in the area of theory of computer science. The workshop will feature technical talks and tutorials by senior and junior women in the field, as well as social events and activities. The motivation for the workshop is twofold. The first goal is to deliver an invigorating educational program; the second is to bring together theory women students from different departments and foster a sense of kinship and camaraderie.”

Continue reading

Posted in Academics, Combinatorics, Computer Science and Optimization, Convexity, Games, Philosophy, Poetry, What is Mathematics, Women in science | 14 Comments

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

This is a guest post kindly contributed by Noam Lifshitz.

My short introduction: There is nothing like a new hypercontractivity inequality to cheer you up in difficult times and this post describes an amazing new hypercontractivity inequality.  The post describes a recent hypercontractive inequality by Peter Keevash, Noam Lifshitz, Eoin Long and Dor Minzer (KLLM) from their paper: Hypercontractivity for global functions and sharp thresholds. (We reported on this development in this post. By now, there are quite a few important applications.) And for Talagrand’s generic chaining inequality, see this beautiful blog post by Luca Trevisan.

Barry Simon coined the term “hypercontractivity” in the 70s.  (We asked about it here and Nick Read was the first to answer.) A few months ago Barry told us about the early history of hypercontractivity inequalities, and, in particular, the very entertaining story on William Beckner’s Ph. D. qualifying exam.

And now to Noam Lifshitz’s guest post.

Hypercontractivity on product spaces

Analysis of Boolean functions (ABS) is a very rich subject. There are many works whose concern is generalising some of the results on analysis of Boolean functions to other (product) settings, such as functions on the multicube {\left[m\right]^{n},} where {m} is very large. However, in some of these cases the fundemental tools of AOBF seem to be false for functions on the multicube {f\colon\left[m\right]^{n}\rightarrow\mathbb{R}.} However, in the recent work of Keevash, Long, Minzer, and I. We introduce the notion of global functions. These are functions that do not strongly depend on a small set of coordinates. We then show that most of the rich classical theory of AOBF can in fact be generalised to these global functions. Using our machinery we were able to strengthen an isoperimetric stability result of Bourgain, and to make progress on some Erdos-Ko-Rado type open problem.

We now discuss some background on the Fourier analysis on functions on the multicube {f\colon\left\{ 1,\ldots,m\right\} ^{n}\rightarrow\mathbb{R}.}

Derivatives and Laplacians

There are two fundemental types of operators on Boolean functions {f\colon\left\{ 0,1\right\} ^{n}\rightarrow\mathbb{R}.} The first ones are the discrete derivatives, defined by {D_{i}[f]=\frac{f_{i\rightarrow1}-f_{i\rightarrow0}}{2},} where {f_{i\rightarrow x}} denotes the we plug in the value {x} for the {i}th coordinate. The other closely related ones are the laplacians defined by {L_{i}f\left(x\right):=f\left(x\right)-\mathbb{E}f\left(\mathbf{y}\right),} where {\mathbf{y}} is obtained from {x} by resampling its {i}th coordinate.

The laplacians and the derivatives are closely related. In fact, when we plug in {1} in the {i}th coordinate, we obtain {L_{i}[f]_{i\rightarrow1}=D_{i}[f]}, and when we plug in {0} in it, we obtain {L_{i}[f]_{i\rightarrow0}=-D_{i}[f].}

The 2-norm of the {i}th derivative is called the {i}th influence of {f} as it measures the impact of the {i}th coordinate on the value of {f}. It’s usually denoted by {\mathrm{Inf}_{i}[f]}.

Generalisation to functions on the multicube

For functions on the multicube we don’t have a very good notion of a discrete derivative, but it turns out that it will be enough to talk about the laplacians and their restrictions. The Laplacians are again defined via {L_{i}f\left(x\right):=f\left(x\right)-\mathbb{E}f\left(\mathbf{y}\right),} where {\mathbf{y}} is obtained from {x} by resampling its {i}th coordinate. It turns out that in the continuous cube it’s not enough to talk about Laplacians of coordinate, and we will also have to concern ourselves with Laplacians of sets. We define the generalised Laplacians of a set {S} by composing the laplacians corresponding to each coordinate in {S} {L_{\left\{ i_{1},i_{2},\ldots,i_{r}\right\} }\left[f\right]:=L_{i_{1}}\circ\cdots\circ L_{i_{r}}\left[f\right].}

We now need to convince ourselves that these laplacians have something to do with the impact of {S} on the outcome of {f.} In fact, the following notions are equivalent

  1. For each {x,y\in\left[m\right]^{S}}we have {\|f_{S\rightarrow x}-f_{S\rightarrow y}\|_{2}<\delta_{1}}
  2. For each {x\in\left[m\right]^{S}} we have {\|L_{S}[f]_{S\rightarrow x}\|_{2}<\delta_{2},}

in the sense that if (1) holds then (2) holds with {\delta_{2}=C^{\left|S\right|}\delta_{1}} and conversely if (2) holds, then (1) holds with {\delta_{1}=C^{\left|S\right|}\delta_{2}.}

The main theme of our work is that one can understand global function on the continuous cube, and these are functions that satisfy the above equivalent notions for all small sets {S}.

Noise operator, hypercontractivity, and small set expansion

For {\rho\in\left(0,1\right),} the noise operator is given by {\mathrm{T}_{\rho}\left[f\right]\left(x\right)=\mathbb{E}f\left(\mathbf{y}\right)} when {\mathbf{y}} is obtained from {x} by independently setting each coordinate {\mathbf{y}_{i}} to be {\mathbf{x}_{i}} with probability {\rho} and resampling it with uniformly out of {\left\{ -1,1\right\} } otherwise. The process which given {x} outputs {\mathbf{y}} is called the {\rho}-noisy process, and we write {\mathbf{y}\sim N_{\rho}\left(x\right).}

The Bonami hypercontractivity theorem, which was then generalised by Gross and Beckner states that the noise operator {T_{\frac{1}{\sqrt{3}}}} is a contraction from {L^{2}\left(\left\{ 0,1\right\} ^{n}\right)} to {L^{4}\left(\left\{ 0,1\right\} ^{n}\right),} i.e.

\displaystyle \|\mathrm{T}_{\frac{1}{\sqrt{3}}}f\|_{4}\le\|f\|_{2}
for any function {f.}

One consequence of the hypercontractivity theorem is the small set expansion theorem of KKL. It concerns fixed {\rho\in\left(0,1\right)} and a sequence of sets {A_{n}\subseteq\{0,1\}^{n}} with {\left|A_{n}\right|=o\left(2^{n}\right).} The small set expansion theorem states that if we choose {\mathbf{x}\sim A_{n}} uniformly and a noisy {\mathbf{y}\sim N_{\rho}\left(\mathbf{x}\right),} then {\mathbf{y}} will reside outside of {A_{n}} almost surely.

The Generalisation to the multicube:

The small set expansion theorem and the hypercontractivity theorem both fail for function on the multicube that are of a very local nature. For instance, let {A} be the set of all {x\in\left\{ 1,\ldots,m\right\} ^{n},} such that {x_{1}} is {m.} Then {A} is of size {m^{n-1},} which is {o\left(m^{n}\right)} if we allow {m} to be a growing function of {n}. However, the {\rho}-noisy process from the set stays within the set with probability {\rho.} For a similar reason the hypercontractivity theorem fails as is for functions on {\left\{ 1,\ldots,m\right\} ^{n}.} However we were able to generalise the hypercontractivity theorem by taking the globalness of {f} into consideration.

Our main hypercontractive inequality is the following

Theorem 1.

\displaystyle \|\mathrm{T}_{\frac{1}{100}}f\|_{4}^{4}\le\sum_{S\subseteq\left[n\right]}\mathbb{E}_{\mathbf{x}\sim\left\{ 1,\ldots,m\right\} ^{m}}\left(\|L_{S}\left[f\right]_{S\rightarrow\mathbf{x}}\|_{2}^{4}\right).

The terms {\|L_{S}\left[f\right]_{S\rightarrow x}\|_{2}} appearing on the right hand side are small whenever {f} has a small dependency on {S} and it turns out that you have the following corrolary of it, which looks a bit more similar to the hypercontractive intequality.

 

Corollary 2.

Let {f\colon\left\{ 1,\ldots,m\right\} ^{n}\rightarrow\mathbb{R}}, and uppose that {\|L_{S}[f]_{S\rightarrow x}\|_{2}\le4^{\left|S\right|}\|f\|_{2}} for all sets {S.}

Then {\mathrm{\|\mathrm{T}_{\frac{1}{1000}}f\|_{4}\le\|f\|_{2}.}}

Finally, one might ask wonder why this globalness notion appears only when we look at large values of {m} and not when {m=2.} I think the corollary is a good explanation for that as {\|f\|_{2}^{2}\ge\left(\frac{1}{2}\right)^{\left|S\right|}\|f_{S\rightarrow x}\|_{2}^{2}} holds trivially for any Boolean function {f\colon\left\{ 0,1\right\} ^{n}\rightarrow\mathbb{R}.}

Posted in Analysis, Combinatorics, Computer Science and Optimization, Guest post, Poetry, Probability | Tagged , , , , | 3 Comments

Harsanyi’s Sweater

Today is the Holocaust Remembrance Day in Israel.  Here is a moving story from the  paper  about  John Harsanyi,  Harsanyi’s Sweater, by Robert J. Aumann.

It is 1944 in Budapest, and John is in his early twenties. He has been taken for deportation, with all that that implies. Arriving at the railroad station, he puts his knapsack down and wanders off a few yards, under the watchful eye of a guard. Then the guard is distracted for a moment, and John sees his chance to escape. But in the knapsack there is a beautiful, warm sweater, lovingly hand-knitted for John by his mother. John hesitates; should he — can he — abandon the sweater? After a moment, the urge to live takes over, and he slips away, taking refuge in a convent by previous arrangement. He survives the Holocaust to become the great thinker that he becomes. Hesitant, careful, open-minded, undogmatic — and in spite of that, or perhaps because of that — great.

Aumann himself  was born in Frankfurt, Germany, and fled at the age of eight to the United States with his family in, two weeks before the 1938 Kristallnacht.

I plan to mention this story in my game theory class this evening and also to mention five great game theorists named John.

Continue reading

Posted in Games, Teaching | Tagged , | Leave a comment

To cheer you up in difficult times II: Mysterious matching news by Gal Beniamini, Naom Nisan, Vijay Vazirani and Thorben Tröbst!

Matching is one of the richest gold mines for ideas and results in mathematics, computer science and other areas.  Today I want to briefly tell you about a curious, surprising, mysterious, and cheerful recent result by Gal Beniamini and Noam Nisan and a subsequent work of Vijay Vazirani. It is a result that will cheer up combinatorialists on both sides of the aisle: graph theorists and researchers in extremal and probabilistic combinatorics as well as algebraic and enumerative combinatorialists.  (And it is related to query complexity, Eulerian lattices, Birkhoff’s polytope, a theorem of Lou Billera and Aravamuthan Sarangarajan, evasiveness, analysis of Boolean functions, and various other things.) At the end of the post I will remind you of a central problem in matching theory: that of extending Lovasz’ randomized algorithm for matching to general graphs. (Perhaps methods from algebraic combinatorics can help.)

I will start with sad news. John Horton Conway, an amazing mathematical hero,  passed away a few days ago. There are very nice posts on Conway’s work by Scott Aaronson (with many nice memories in the comments section), by Terry Tao, and by Dick Lipton and Ken Regan. And a moving obituary on xkcd with a touch of ingenuity of Conway’s style. (There is also a question on MO  “Conway’s less known results,” and two questions on the game of life (I, II).)

Another reading material to cheer you up is my paper: The argument against quantum computers, the quantum laws of nature, and Google’s supremacy claims. It is for Laws, Rigidity and Dynamics, Proceedings of the ICA workshops 2018 & 2019 in Singapore and Birmingham. Remarks are most welcome. (Update (May, 25 2020): An interesting discussion on Hacker news.)

Update: starting today, the algebraic combinatorics online workshop.  Here is the schedule for the first week, and for the second week.

 

Matching theory by Lovasz and Plummer is probably one of the best mathematics books ever written. 

Bipartite Perfect Matching as a Real Polynomial

Bipartite Perfect Matching as a Real Polynomial, by Gal Beniamini and Noam Nisan

Abstract: We obtain a description of the Bipartite Perfect Matching decision problem as a multilinear polynomial over the Reals. We show that it has full degree and (1-o_n(1))\cdot 2^{n^2}  monomials with non-zero coefficients. In contrast, we show that in the dual representation (switching the roles of 0 and 1) the number of monomials is only exponential in \Theta(n \log n)  Our proof relies heavily on the fact that the lattice of graphs which are “matching-covered” is Eulerian.

And here is how the paper starts

Every Boolean function f:\{0,1\}^n\to\{0,1\} can be represented in a unique way as a Real multilinear polynomial. This representation and related ones (e.g. using the {1,−1} basis rather than {0,1}– the “Fourier transform” over the hypercube, or approximation variants) have many applications for various complexity and algorithmic purposes. See, e.g., [O’D14] for a recent textbook. In this paper we derive the representation of the bipartite-perfect-matching decision problem as a Real polynomial.

Definition. The Boolean function BPM_n(x_{1,1},\dots,x_{n,n}) is defined to be 1 if and only if the bipartite graph whose edges are\{(i,j):x_{i,j}=1\} has a perfect matching, and 0 otherwise.

And here are the two main theorems regarding this polynomial and the polynomial for the dual representation:

(For the second theorem you need the notion of totally ordered bipartite graphs.)

And here is a nice picture!

A very interesting open problem is:

Problem: Can the Beniamini-Nisan results be extended to general (non-bipartite) graphs

This reminds me of an old great problem:

Problem: Does Lovasz’ randomized algorithm for matching extend to the non-bipartite case?

For both problems methods of algebraic combinatorics may be helpful.

An Extension by Vijay Vazirani and Thorben Tröbst

A Real Polynomial for Bipartite Graph Minimum Weight Perfect Matchings, Thorben Tröbst, Vijay V. Vazirani

Abstract:

In a recent paper, Beniamini and Nisan gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph G \subset K_{n,n} has a perfect matching, together with an efficient algorithm for computing the coefficients of the monomials of this polynomial. We give the following generalization: Given an arbitrary non-negative weight function w on the edges of K_{n,n}, consider its set of minimum weight perfect matchings. We give the real multilinear polynomial for the Boolean function which determines if a graph G \subset K_{n,n} contains one of these minimum weight perfect matchings.

Three more remarks about VVV

Three more VVV remarks: in the Tel Aviv theory fast fest three months ago (it seems like ages ago) Vijay Vazirani gave a lecture about matching. Here is the link to Vijay’s lecture, and to all plenary lectures.  At the end, I asked him how he explains that matching theory is such inexhaustable gold mine and Vijay mentioned the fact that a polynomial-time algorithm for the assignment problem (which is closely related to matching) was already found by Jacobi in 1890. (Unfortunately VJ’s inspiring answer was not recorded). A few years ago Vijay published a simplified proof of a fantastic famous result he first proved with Silvio Micaly 34 years earlier. And here is a most amazing story: a few years ago I went to the beach in Tel Aviv and I discovered Vijay swimming just next to me.  We were quite happy to see each other and Vijay told me a few things about matching, economics and biology. This sounds now like a truly surrealistic story, and perhaps we even shook hands.

 

 

 

Posted in Combinatorics, Computer Science and Optimization | Tagged , , , | 10 Comments

Trees not Cubes! Memories of Boris Tsirelson

This post is devoted to a few memories of Boris Tsirelson who passed away at the end of January. I would like to mention that a few days ago graph theorist Robin Thomas passed away after long battle with ALS. I hope  to tell about Robin’s stunning mathematics in a future post.

Boris Tsirelson (1950 – 2020); Boris’ home-page, and Wikipedia. (More links, below.)

The title of the post is taken from the title of a very interesting 1999 paper by Boris Tsirelson and Oded Schramm: Trees, not cubes: hypercontractivity, cosiness, and noise stability

I was very sad and shocked to hear that Boris Tsirelson had passed away. Boris was one of the greatest Israeli mathematicians, and since 1997 or so we established mathematical connections surrounding several matters of common interest.  Here are a few memories.

Love for coding

1) One thing that Boris told me was that he loves to code. Being a “refusnik”, he could not get into Academia and (luckily) he could work as a programmer. And he told me that afterwards deciding what he liked more – programming or doing mathematical research – was no longer a trivial question for him.  Boris chose to go back to mathematical research, but he continued to enjoy programming, and when he needed it in his mathematical research, he could easily program.

Love for quantum

2) Another thing that Boris loved is “quantum”, the mathematics and physics of quantum mechanics and various connections to mathematics. Early on he proved his famous Tsirelson’s bound related to Bell’s inequalities, and later he was enthusiastic about the area of quantum computing. (And he learned it quickly, taught a course about it in 1997, and his 1997 lecture notes are still considered very useful.)

Black Noise and noise sensitivity

3) Perhaps the most significant mathematical connection between us was in the late 90s, and was centered around the theory of noise stability and noise sensitivity by Benjamini, Schramm and myself, which was closely related to a theory initiated by Boris Tsirelson and Anatoly Vershik. The translation between the different languages that we used and that Boris used was awkward, since the analog of Boolean functions that we studied was the “noise” that Boris studied, and the analog of noise sensitive Boolean functions in our language was “black noise” in Boris’s language. In any case, we had email discussions and we also met a few times with Itai and Oded regarding this connection.

Black Noise and noise sensitivity II

4)  Boris developed a very rich theory of black noise with relations to various areas of probability theory and operator algebras. He also found hypercontractivity that we used in our work quite useful to his applications, and also in this theory, he considered both classical and quantum aspects. I know only a little about Boris Tsirelson’s theory and its applications, but as far as tangent points with our Boolean interests are concerned, I can mention that Boris was enthusiastic by the result of Schramm and Stas Smirnov that percolation is a “black noise” and also that, in 1999, Boris and Oded Schramm wrote a paper whose title started with “Trees not cubes!”, presenting a different angle on this theory.

Tsirelson saw white noise (what we call noise stability) as manifesting “linearity” while “black noise” (what we call noise sensitivity) as manifesting “non-linearity”. Over the years, I often asked him to explain this to me.

Tsireslon’s Banach spaces

5) Geometry of Banach spaces is a very strong area in Israel so naturally I heard as a graduate student about “Tsirelson’s space” from 1974 and some subsequent developments in the 80s. Boris Tsirelson constructed a  Banach space that does not contain an imbedding of \ell_p or c_0.

Bible codes

6) My first personal connection with Boris was related to claims regarding a hidden Bible Code, and a 1994 paper claiming a statistical proof of the existence of these Bible codes. For many years my attitude was that these claims should be ignored, but around 1997, I changed my mind and did some work to see what was going on. Now, Boris kept a site linked in his homepage devoted to developments regarding the Bible Code claims. In this site Boris kindly reported about my first 1997 paper on the topic, my observation that the proximity of two reported p-values for the two Bible code experiments was “too good to be true”, and my interpretation that this suggests that the claimed results manifest naïve statistical expectations rather than scientific reality.  A few weeks later, Boris reported about a much stronger evidence (by McKay and Bar Nathan) against the Bible Code claims (they demonstrated codes of similar quality in Tolstoy’s “War and Peace”) and subsequently after some time he lost interest in this topic.

Quantum computing skepticism

6) In 2005 we had some correspondence and meetings regarding my quantum computing skepticism. In his first email he told me that my reference to “decoherence” seemed strange and I realized that I consistently referred to “entanglement” as “decoherence” and to “decoherence” as “entanglement”.

7) In his 1997 lecture notes on quantum computing (that I cannot find on the web, so I count on my memory), Boris addressed the concerns of early quantum computers skeptics like Rolf Landauer. He did not accept the analogy between quantum computing and analog computation, but he also regarded the analogy with digital computation as problematic. Rather, he regarded quantum information based on qubits as something (at least a priori) different from both these examples. (Update: I found one non-broken link to the lecture notes; indeed the subtitle of Chapter 9 is “neither analog nor digital”.)

A joke that I heard from Boris at that time

8) I remember that once when I asked him about some aspects of quantum fault tolerance he told me the following joke: A student is entitled to a special exam, he arrives at the professor’s office, is given three questions to answer and he fails to do so. He request and is granted a make-up exam two weeks later. When the student shows up at the office two weeks later the professor, who forgot all about it, gave him the same three questions. “This is extremely unfair”, said the student “you ask me questions that you already know that I cannot answer.”

Noise sensitivity and high energy physics

9) In 2006 I came up with the idea that noise sensitivity might be a great idea for physics. Knowing very little physics, I wrote a little manifesto with this idea and tried it, among other people, on Boris. As it turned out, Boris had the idea that noise sensitivity could add a useful modeling power to physics (especially high energy physics) well before that time. (And by 2006 he was already a bit skeptical regarding his own idea.) He also told me that one of the motivations of his 1998 paper with Tolya Vershik came from some mathematical ideas related to physics of the big bang. When I asked him if this was written somewhere in the paper itself, he answered: “Of course, not!”

Boris Tsirelson’s lecture at Oded’s memorial school

10) in 2009 we organized a meeting in memory of Oded Schramm and Boris gave a lecture related to the Schramm-Smirnov “percolation is black noise” result with a single theorem. And what was remarkable about it that it was that he presented a classical theorem with a quantum proof. You can find the videotaped lecture here  (And here are the slides. Boris never wrote up this result.) Following this lecture we had a short correspondence with Scott A. and Greg K. about quantum proofs to classical theorems. (Namely theorems that do not mention quantum in the statement).

Tsirelson’s problem

11) Our last correspondence in 2019 was about Thomas Vidick’s  Notices AMS article about Tsirelson’s problem. (This was a couple of months before the announcement of the solution.) Boris was pleased to hear about these developments, as he was regarding earlier developments in this area. He humorously refers to the history of his problem on his homepage and this interview.

12) People who knew Boris regarded him as a genius from a very early age, and former students have fond memories of his classes.

 

More resources:

Boris’s home page contains  “Museum to my courses” with many useful lecture notes; link to a small page on quantum computation with a link to Boris’ 1997 lecture notes on quantum computing.  Links to comments on some of Tsirelson’s famous papers. Tsirelson’s 1980 bound. Boris published papers, and his “self-published” papers.

Boris was a devoted Wikipedian and his Wikipidea user page is now devoted to his memory; Here is a great interview with Boris; A very nice memorial post on Freeman Dyson and Boris Tsirelson on the Shtetl Optimized; Tim Gowers explains some ideas behind Tsirelson’s space over Twitter; and here in Polymath2.

Below the fold some emails of interest from Boris, mainly where he explained to me various mathematics. (More can be found in this page.)

Continue reading

Posted in Combinatorics, Obituary, Probability, Quantum | Tagged | 3 Comments

A small update from Israel and memories from Singapore: Partha Dasgupta, Robin Mason, Frank Ramsey, and 007

A small update about the situation here in Israel

Eight weeks ago I wrote that my heart goes out to the people of Wuhan and China, and these days my heart goes out to people in Italy, Spain, the US, Iran, France, the United Kingdom, Germany, Netherland and many other countries all over the world. Of course, I am especially worried about the situation here in my beloved country Israel, and let me tell you a little about it.

The pandemic started here late but it hit us pretty hard with 5,358 identified cases yesterday. Severe measures of social distancing were gradually introduced, and right now it is too early to tell if the pandemic is under control.

My part in this struggle is to stay at home. (Many Israeli scientists are making various endeavors and proposing ideas of various kind for fighting the disease and I salute them all for their efforts.) Like all of us I am very thankful to medical and other essential workers who are in the front-lines. As a scientist, I am especially impressed by the people from the Ministry of Health who manage the crisis and communicate with the public. They represent the very best we can offer in terms of science and medicine, decision making, gathering information, communicating with the public, and managing the crisis. In the picture below you can see three of the leaders – Moshe Bar Siman Tov (middle) Prof. Itamar Grotto (right) and Professor Sigal Sadetzki (left).

And now for today’s post

We had a tradition of sharing entertaining taxi-and-more stories and this post belongs to this category. We note that our highest quality story teller Michal Linial, a prominent Israeli biologist, is now involved in various aspects of the struggle against the disease. Our post today is part of a report by Michal Feldman and me on our experience from the ICA3 conferences in Singapore and Birmingham.

Partha Dasgupta, Robin Mason, Frank Ramsey, and James Bond

After hearing about him for many years, it was a great pleasure for both Michal Feldman and myself to finally meet Partha Dasgupta in person and to listen to his lecture. Partha who is the Frank Ramsey Professor of Economics at Cambridge was introduced by a person, who entered the room directly from an intercontinental flight, whom we did not know but who made a strong impression on us. He devoted part of his introduction to Frank Ramsey who was a mathematician, philosopher and economist, and who had made fundamental contributions to algebra and had developed the canonical model of saving in economic growth, before he died at the young age of 26. (And yes! also Ramsey’s theorem!)

Seeing the introducer, Robin Mason, three words came into our minds (more precisely two words, one repeated twice): “Bond, James Bond.”

Indeed, this has led to the following sequence of profound ideas:

1) Robin Mason is a perfect choice for a new generation James Bond.

2) The name “James Bond” is overused. “Robin Mason” is a perfect name to replace the name “James Bond”.

3) Espionage is a little obsolete and it lost much of its prestige and charm. Science and academia is the new thing! An international interdisciplinary academics is the perfect profession which, at present, deserves the prestige formely associated with espionage.

In summary, we came a full circle. Robin Mason is the perfect new choice for James Bond, “Robin Mason” is the perfect new name to replace the name “James Bond,” and Mason’s academic activities and title of Pro-Vice-Chancellor (International) are the perfect replacement for Bond’s activities and the title ‘007’.

(The option of Mason playing his role on the movies rather than in real life should be considered. ‘Q’ could be handy for science as well. )

Clique here for Robin’s introduction and Partha’s lectur

Posted in Algebra, Combinatorics, Conferences, Economics, Taxi-and-other-stories, Updates | Tagged , , , , , , , , | 2 Comments

Game Theory – on-line Course at IDC, Herzliya

Game theory, a graduate course at IDC, Herzliya; Lecturer: Gil Kalai; TA: Einat Wigderson,  ZOOM mentor: Ethan.

Starting Tuesday March 31, I am giving an on-line course (in Hebrew) on Game theory at IDC, Herzliya (IDC English site; IDC Chinese site).

In addition to the IDC moodle (course site) that allows IDC students to listen to recorded lectures, submit solutions to problem sets , etc., there will be a page here on the blog devoted to the course. Zoom link for the first meeting. https://idc-il.zoom.us/j/726950787

A small memory: In 1970 there was a strike in Israelis’ high schools and I took a few classes at the university. One of these classes was Game theory and it was taught by Michael Maschler. (I also took that trimester a course on art taught by Ziva Meisels.) Our department at HUJI is very strong in game theory, but once all the “professional” game theorists retired, I gave twice a game theory course which I enjoyed a lot and it was well accepted by students. In term of the number of registered students, it seems that this year’s course at IDC is quite popular and I hope it will be successful.

The first six slides of the first presentation

(Click to enlarge)

Game Theory 2020, games, decisions, competition, strategies, mechanisms, cooperation

The course deals with basic notions, central mathematical results, and important examples in non-cooperative game theory and in cooperative game theory, and with connections of game theory with computer science, economics and other areas.

What we will learn

1. Full information zero-sum games. The value of a game. Combinatorial games.

2. Zero-sum games with incomplete information. Mixed strategies, the Minmax Theorem and the value of the game.

3. Non cooperative games, the prisoner dilemma, Nash equilibrium, Nash’s theorem on the existence of equilibrium.

4. Cooperative games, the core and the Shapley value. Nash bargaining problem, voting rules and social choice.

Background material:

Game theory alive by Anna Karlin and Yuval Peres (available on-line).

In addition I may use material from several books in Hebrew by Maschler, Solan, Zamir, by Hefetz, and by Megiddo (based on lectures by Peleg). (If only I will manage to unite with my books that are not here.) We will also use a site by Ariel Rubinstein for playing games and some material from the book by Osborne and Rubinstein.

Requirement and challenges:

  • Play, play, play games, in Ariel Rubinshtein site and various other games.
  • Solve 10 short theoretical problem set.
  • Final assignment, including some programming project that can be carried out during the semester.
  • Of course, we will experience on-line study which is a huge challenge for us all.

Games and computers

  • Computer games
  • Algorithms for playing games
  • algorithmic game theory:
    • Mechanism design
    • Analyzing games in tools of computer science
    • Electronic commerce
  • Games, logic and automata: there will be a parallel course by Prof. Udi Boker

I still have some difficulty with the virtual background in ZOOM.

Posted in Combinatorics, Computer Science and Optimization, Economics, Games, Rationality, Teaching | Tagged , | 2 Comments

TYI44: “What Then, To Raise an Old Question, is Mathematics?”

“The argument is carried out not in mathematical symbols but in ordinary English, there is no obscure or technical terms. Knowledge of calculus is not presupposed. In fact, one hardly need to know how to count. Yet any mathematician will immediately recognize the argument as mathematical.” 

Test your intuition 44: what is the argument? who and where wrote this view about “what is mathematics”.

Zero-knowledge answers please.

Comments regarding this view itself and on “what is mathematics” are also welcome.

(Here are other posts on “What is mathematics.”)

 

 

PS. The last facetious sentence was omitted in the Journal version of the paper. (Indeed it was a good decision to take it out.) PPS Yannai Gonczarowski pointed out the the journal formulation is also rather condescending (perhaps even more so) towards non-mathematicians.

Posted in Test your intuition, What is Mathematics | Tagged , | 14 Comments

Kelman, Kindler, Lifshitz, Minzer, and Safra: Towards the Entropy-Influence Conjecture

Let me briefly report on a remarkable new paper by Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, and Muli Safra, Revisiting Bourgain-Kalai and Fourier Entropies. The paper describes substantial progress towards the Entropy-Influence conjecture, posed by Ehud Friedgut and me in 1996. (See this blog post from 2007.)

Abstract: The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta theorem give a strong characterization of such functions whenever the bound on the total influence is o(logn), however, both results become useless when the total influence of the function is ω(logn). The only case in which this logarithmic barrier has been broken for an interesting class of function was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of S_n.

In this paper, we revisit the key ideas of the Bourgain-Kalai paper. We prove a new general inequality that upper bounds the correlation between a Boolean function f and a real-valued, low degree function g in terms of their norms, Fourier coefficients and total influences.

Some corollaries of this inequality are:

  1. The Bourgain-Kalai result.
  2. A slightly weaker version of the Fourier-Entropy Conjecture. More precisely, we prove that the Fourier entropy of the low-degree part of f is at most O(I[f]log^2 I[f]), where I[f] is the total influence of f. In particular, we conclude that the Fourier spectrum of a Boolean function is concentrated on at most 2O(I[f]log^2 I[f]) Fourier coefficients.
  3. Using well-known learning algorithms of sparse functions, the previous point implies that the class of functions with sub-logarithmic total influence (i.e. at most O(\log n/(\log \log n)2)) is learnable in polynomial time, using membership queries.

Our theorem on influence under symmetry. From my videotaped lecture on Jean Bourgain. See this post about Jean Bourgain.

A few remarks:

A) Given a Boolean function f:\{-1,1\}^n\to \{-1,1\} let f=\sum_{S \subset \{1,2,\dots ,n\}}\hat f(S)W_S be its Fourier-Walsh expansion. (Here W_S(x_1,x_2,\dots ,x_n)=\prod_{i\in S}x_i.) The total influence I(f) of f is described by

I(f)=\sum {S \subset \{1,2,\dots ,n\}}\hat f^2(S)|S|.

The spectral entropy E(f) of f is defined by

E(f)=\sum_{S \subset \{1,2,\dots ,n\}}\hat f^2(S) \log (\hat f^2(S)).

The entropy-influence conjecture (here called the Fourier-entropy conjecture) asserts that for some universal constant C

I(f) \ge C E(f).

B) One interesting feature of the conjecture is that the RHS is invariant under arbitrary linear transformations of \{-1,1\}^n (regarded as an n-dimensional vector space) while the LHS is invariant only to permutations of the variables.

C) My paper with Jean Bourgain, Influences of variables and threshold intervals under group symmetries, describes lower bounds on total influences for Boolean function invariant under certain groups of permutations (of the variables). Those results are stronger (but more restrictive) than what the Entropy/influence conjecture directly implies. (This was overlooked for a while.) The new paper gives (much hoped for, see below) simpler proofs and stronger results compared to those in my paper with Jean Bourgain.

D) Ryan O’Donnel wrote about Bourgain and some of his contributions to the analysis of Boolean functions:

“I spent close to 5 years understanding one 6-page paper of his (“On the distribution of the Fourier spectrum of Boolean functions”), and also close to 10 years understanding a 10-page paper of his (the k-SAT sharp threshold ‘appendix’). If anyone’s up for a challenge, I’m pretty sure no one on earth fully understands the second half of his paper “Influences of variables and threshold intervals under group symmetries” with Kalai (including Gil 🙂 )”

It looks that by now we have pretty good understanding and even some far-reaching progress regarding all three papers that Ryan mentioned. (It is unclear if we can hope now for an exponential spread of understanding for Bourgain’s proofs.)

 

Posted in Combinatorics, Computer Science and Optimization, Open problems | Tagged , , , , | Leave a comment