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 , , , , , , , , | 3 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 , , , , | 1 Comment

Or Ordentlich, Oded Regev and Barak Weiss: New bounds for Covering Density!

Update (June 3, 2020): The paper New bounds on the density of lattice coverings is now on the arXiv.

Barak Weiss lectured about his breakthrough results with Or Ordentlich, and Oded Regev, at a Simons Institute workshop: Lattices: Geometry, Algorithms and Hardness.

It is a famous problem what is the densest (or, most efficient) packing of unit balls in Euclidean n-dimensional spaces and, of course, you can ask the same questions for other convex bodies. A sort of a dual problem, also famous, is the question of the most efficient covering the n-dimensional Euclidean space by balls or by translates of other convex bodies.

A very basic insight is that covering is much more efficient than packing. Can you explain the reason for that? The only thing that came up to my mind was that convex sets are roundish from the outside but not from the inside which makes it easier to cover with them.

But how efficiently can we cover the n-dimensional Euclidean space with translates of a convex body $K$?

C.A. Rogers with coauthors had some very fundamental results regarding covering (and packing) in the 50s and 60s. Or Ordentlich, Oded Regev and Barak Weiss have made a terrific improvement for one of the main questions in this area. They showed that for every convex set K, you can find a lattice of determinant 1, and r>0  such that rK+L = \mathbb R^n and

{\rm vol} (rK) \le cn^2.

The best earlier upper bound was n^{\log \log n}.

One surprising aspect of the proof is the use of finite field Kakeya-type questions. Since the breakthrough by Zeev Dvir, many people had hopes for applications from the finite fields results to the Euclidean setting (in particular, to the Euclidean Kakeya problem itself) and it is rare to see such applications. The proof here relies on results by  Dvir, Kopparty, Saraf, Sudan, and Lev. The Ordentlich-Regev-Weiss paper is not yet on the arXiv but the lecture gives a good picture about the results and the proofs.

The definition of the covering density of L with respect to a convex body K

The definition of the covering density of K

Old results for the Euclidean ball

Old results for general convex bodies

The first main result

 

The required finite field Kakeya theorem.

Posted in Combinatorics, Computer Science and Optimization, Geometry | Tagged , , | 3 Comments

To cheer you up in complicated times – A book proof by Rom Pinchasi and Alexandr Polyanskii for a 1978 Conjecture by Erdős and Purdy!

Things do not look that good, and these are difficult times. But here on the blog we have plenty of things to cheer you up and assure you. And today we point to two book proofs — two book proofs to the same theorem– and, as a matter of fact, two book proofs to the same theorem by the same person, Rom Pinchasi.  One of the proofs, the one chosen for presentation, is by Rom Pinchasi and  Alexandr Polyanskii.

Rom Pinchasi has an immense proving power, both for difficult proofs at all costs, for book proofs, and for a large variety of proofs in between. (See, for example,  this post.)

Before moving on, let me mention that there is a timely blog post by Terry Tao on Online teaching, and here is a related MO question about online conferences that I asked last December.

Proofs from the book

Famously, the mathematician Paul Erdős, often referred to “The Book” in which God keeps the most elegant proof of each mathematical theorem. During a lecture in 1985, Erdős said, “You don’t have to believe in God, but you should believe in The Book.” (And you do not have even to believe in the book to enjoy proofs from the book.)

The Theorem: a 1978 conjecture by Erdős and Purdy

Theorem:  Let P be a set of n points in general position in the plane. Suppose that R is a set of red points disjoint from P such that every line determined by P passes through a point in R. Then |R|≥ n for n > 6.

This theorem settles a problem by Erdős and Purdy from 1978. Erdős and Purdy also asked about the case where the set of points is not required to be in general position. For that problem the best known lower bound, also proved by Rom Pinchasi, is n/3.

Book Proof I: An algebraic solution of a problem of Erdős and Purdy, by Rom Pinchasi

Book Proof II: A one-page solution of a problem of Erdős and Purdy, by Rom Pinchasi and Alexandr Polyanskii

Murty’s magic configurations conjecture.

The first proof of the Erdős-Purdy 1978 Conjecture was achieved in 2008 by Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, and Günter Rote. They derived it from their solution to the 1971 conjecture on magic configurations by Murty. A planar set of points P is called magic if it possible to assign positive weights to the points so that the sum of weights in every line determined by the points is one. Murty conjectured that the only magic configurations are those in general position, and those which have a line missing at most one of the points, and a certain configuration of seven points.

The Pinchasi-Polyanskii Book-Proof:

Here, we very closely follow the Pinchasi-Polyanskii’s paper.

We say that a line is determined by a set of points in the plane if it contains at least two of the points. Since the points in P are in general position, each pair of points determines a different line.

Under the contrary assumption we must have |R| = n−1. Then it must be that every point in R is incident to precisely n/2 lines determined by P and every line determined by P is incident to precisely one point in R. We would like to reach a contradiction.

Preliminary step: apply a projective transformation to the plane such that the convex hull of P becomes a triangle.

Observation 1:  No point of R lies outside the convex hull of P.

Such a point r should be incident to two lines supporting the convex hull of P. Each of these supporting lines must contain precisely two points of P. Since the convex hull of P is a triangle this is impossible.

Regard the points in the plane as complex numbers.

(This is really cool. I am not aware of many examples in discrete geometry that thinking about planar points as complex numbers helps.)

Notation: for every point p in the plane we denote by p_x  the x-coordinate of p.

Crucial definition: For every point p ∈ P define

f(p) = \prod_{r \in R}(p-r) / \prod_{p' \in P\backslash \{p\}}(p-p').

Observation 2: f(p) is a real number!

The proof will surely make you smile: For every p’ ∈ P \{p} there is a unique r ∈ R such that p, p’, and r are collinear. So (p-r)/(p-p’) is real. And the big ratio between products split to many small fractions that are all real.  Walla!

Note that f(p) is thus also invariant under rotations of the plane.

Now, if the vertical line through p does not contain any other point in P ∪ R, then, for the unique r ∈ R such that p, p’, and r are collinear, we have that:

(1)~~~(p-r)/(p-p')~=~(p_x-r_x)/(p_x-p'_x).

This leads to:

Observation 3:  if the vertical line through p does not contain any other point in P ∪ R, then

(2)~~~ f(p) = \prod_{r \in R}(p_x-r_x) / \prod_{p' \in P\backslash \{p\}}(p_x-p'_x).

Crucial observation 4:  Let p and q be any two points in P and let r be the unique point in R collinear with p and q. Then

f(p)/f(q)=-(p-r)/(q-r).

To see this rotate the plane so that the x-coordinates of p,q, and r are equal (or nearly equal) and apply Equations (2) and (1). (You will get the same, or nearly the same, contributions for r’ ≠ r  and you are left with the contribution for r. ) This also leads to:

Observation 5: f(p)/f(q) >0  if and only if the unique point r ∈ R that is collinear with p and q lies in the straight line segment delimited by p and q.

A complete graph with green and red edges.

Consider the complete graph G whose vertices are the points in P. For every two points p, q ∈ P we color the edge connecting  p and q red if the unique point in R collinear with p and q lies outside the straight line segment connecting p and q. Otherwise we color the edge green. In other words, the edge is red if f(p)/f(q) < 0, and green if f(p)/f(q) > 0.

The vertices of G can naturally be partitioned into two sets: U = {p ∈ P | f(p) > 0} and W = {p ∈ P | f(p) < 0}.

Without loss of generality assume that the three vertices of the convex hull of P belong to U. (Since no point of R is outside this convex hull all edges of the triangle forming the convex hull are green.)

Observation 6: |U| = n/2 + 1.

To see this let a,bU be two vertices of the convex hull of P. Let cR be the point in R collinear with a and b. The point c must be between a and b on the boundary of the convex hull of P. Therefore, all the other n/2 −1 pairs of points of P that are collinear with c must form red edges. Consequently, precisely one point of every such pair belongs to U. Together with a and b, we obtain |U| = n/2+1.

End of proof:

Continue reading

Posted in Combinatorics, Geometry, What is Mathematics | Tagged , | 8 Comments

A new PolyTCS blog!

A new PolyTCS blog

The PolyTCS Project is a new blog to run collaborative Theoretical Computer Science projects. The initiative is by two graduate students Rupei Xu and Chloe Yang. The logo was designed by Grigory Yaroslavtsev.

At this stage the blog raised possible projects to pursue.  A few days ago Rupei Xu discussed a second possible exciting project:   Project 2: Is Semi-Definite Programming (SDP) Polynomial-Time Solvable? The first project-proposal (Nov 1, 2019 by Jiapeng Zhang) was Project 1: The Entropy-Influence Conjecture.

(Here is a 2014  post on GLL on the problem of Project 2, and here is my 2007 post on WN on the problem of Project 1.)

Good luck!!!

 

Posted in Combinatorics, Computer Science and Optimization, Mathematics over the Internet | Tagged , , | Leave a comment

Remarkable New Stochastic Methods in ABF: Ronen Eldan and Renan Gross Found a New Proof for KKL and Settled a Conjecture by Talagrand

 

The main conjecture from Talagrand’s paper on boundaries and influences was settled by Ronen Eldan and Renan Gross. Their paper introduces a new powerful method to the field of analysis of Boolean functions (ABF).

This post is devoted to a new breakthrough paper by Ronen Eldan and Renan Gross, Concentration on the Boolean hypercube via pathwise stochastic analysis.

The paper introduces remarkable new techniques based on stochastic calculus, (that bypass the use of hypercontractivity), that allow to settles several open problems on analysis of Boolean functions. (And on the way, to give a very different proof for KKL.)

Renan Gross recently wrote an excellent high-level explanation of the paper in his  blog: New paper on arXiv: Concentration on the Boolean hypercube via pathwise stochastic analysis. It is accompanied by a brief introduction to Boolean analysis, featuring the required Boolean material:

 

Before we move on, a trivia question:

Trivia question: Who invented the term hypercontractivity?

(For a hint, see at the end of the post.)

Back to the paper by Ronen Eldan and Renan Gross. Perhaps the best way to explain what was achieved in this paper is to put one after the other the abstracts of the first version followed by the abstract of the second paper.

 

Ronen and Renan’s paper. Version 1, 26 Sept 2019.

The title for version 1 was: Stability of Talagrand’s influence inequality

And here is the abstract: 

We strengthen several classical inequalities concerning the influences of a Boolean function, showing that near-maximizers must have large vertex boundaries. An inequality due to Talagrand states that for a Boolean function

(1)~~~~~\mathrm{var}\left(f\right)\leq C\sum_{i=1}^{n}\frac{\mathrm{Inf}_{i}\left(f\right)}{1+\log\left(1/\mathrm{Inf}_{i}\left(f\right)\right)}

where  \mathrm{Inf}_{i}\left(f\right) denote the influence of the i-th coordinate. We give a lower bound for the size of the vertex boundary of functions saturating this inequality. As a corollary, we show that for sets that satisfy the edge-isoperimetric inequality or the Kahn-Kalai-Linial (KKL) inequality up to a constant, a constant proportion of the mass is in the inner vertex boundary. Our proofs rely on new techniques, based on stochastic calculus, and bypass the use of hypercontractivity common to previous proofs.

Let me say a few words about it. KKL theorem asserts that the maximal influence of a balanced Boolean function is at least \Omega (\log n/n) var (f). The famous tribe example of Ben-Or and Linial shows that this is tight.  The KKL paper gave some statements about other norms of the influence vector and Talagrand’s inequality stated above (from the paper “On Russo’s 0-1 law”) gives a sharp description of the influence vectors. Ronen and Renan found a new method that gave new proofs for KKL’s theorem and the stronger Talagrand’s inequality. This new methods led to new stability result.

Now, lets move to version 2.

Ronen and Renan’s paper: Version 2: 12 Nov 2019,

Ronen Eldan and Renan Gross, Concentration on the Boolean hypercube via pathwise stochastic analysis.

Abstract: We develop a new technique for proving concentration inequalities which relate between the variance and influences of Boolean functions. Using this technique, we

1. Settle a conjecture of Talagrand [Tal97] proving that

(2)~~~~~\int_{\left\{ -1,1\right\} ^{n}}\sqrt{h_{f}\left(x\right)}d\mu\geq C\cdot\mathrm{var}\left(f\right)\cdot\left(\log\left(\frac{1}{\sum\mathrm{Inf}_{i}^{2}\left(f\right)}\right)\right)^{1/2},

where h_f(x) is the number of edges at x  along which f changes its value, and Inf_i(f) is the influence of the i-th coordinate.

2. Strengthen several classical inequalities concerning the influences of a Boolean function, showing that near-maximizers must have large vertex boundaries. An inequality due to Talagrand states that for a Boolean function f

\mathrm{var}\left(f\right)\leq C\sum_{i=1}^{n}\frac{\mathrm{Inf}_{i}\left(f\right)}{1+\log\left(1/\mathrm{Inf}_{i}\left(f\right)\right)}

We give a lower bound for the size of the vertex boundary of functions saturating this inequality. As a corollary, we show that for sets that satisfy the edge-isoperimetric inequality or the Kahn-Kalai-Linial inequality up to a constant, a constant proportion of the mass is in the inner vertex boundary.

3. Improve a quantitative relation between influences and noise stability given by Keller and Kindler.

Our proofs rely on techniques based on stochastic calculus, and bypass the use of hypercontractivity common to previous proofs.

Let me explain in a few words the main inequality that verified a conjecture by Talagrand. For other advances look at the paper itself.

The famous Margulis-Talagrand inequality asserts that

(3)~~~~~\int_{\left\{ -1,1\right\} ^{n}}\sqrt{h_{f}\left(x\right)}d\mu\geq C\cdot\mathrm{var}(f).

Let me say a little more. Talagrand’s proved in  his paper on Influence and boundary asserts that the right hand is a constant only if II(f) – the sum of squares of the influences is a constant. He conjectured that we can actually add the square root of \log II(f) to the RHS.

A few remarks:

  1.  For more background see my old post “Nati’s influence“.
  2. Let me mention that Talagrand’s influence inequality (Equation (1) above) is sharp up to a multiplicative constant. This is shown in a 2015 paper: On the Converse of Talagrand’s Influence Inequality by Saleet Klein, Amit Levi, Muli Safra, Clara Shikhelman, and Yinon Spinka.
  3.  Finding the best constant in KKL’s theorem is a well known challenge. So is the question of understanding balanced Boolean functions on n variables where the maximum influence is C \log n/n. Ehud Friedgit in his paper: Influences in Product Spaces, KKL and BKKKL Revisited, have made important conjectures for such Boolean functions.
  4.  I expect that the new method will have many applications. Ronen Eldan in a paper Second-order bounds on correlations between increasing families, found applicaions to correlation inequalities which I will discuss at some other time.
  5.  See the last part of this post for a description of Talagrand’s various relevant papers.
  6. Renan Gross is building the BooleanZoo in a similar spirit to the famous complexityZoo.
  7. I was in the process of writing a post about progress on ABS, mentioning twelve or so papers, apologizing for not mentioning others, promising to write in details about some of the papers, and making further apologetic remarks. But as this large post does not advance let me start with some of the promises.

talabb

Hint to the trivia question:

Continue reading

Posted in Analysis, Combinatorics, Probability | Tagged , , | 5 Comments

Hoi Nguyen and Melanie Wood: Remarkable Formulas for the Probability that Projections of Lattices are Surjective

Following a lecture by Hoi Nguyen at Oberwolfach, I would like to tell you a little about the paper: Random integral matrices: universality of surjectivity and the cokernel by Hoi Nguyen and Melanie Wood.

Two background questions:

Hoi started with two background questions –

Background Question 1: Consider an n \times n 0-1 matrix where the entries are taken at random. What is the probability that the matrix is singular (over the rationals)?

Hoi mentioned the recent result of Konstantin Tikhomirov, and moved to talk about matrices over the integers.

Background Question 2: Now, think about the lattice spanned by the rows of the matrix. How likely it is that this is the full \mathbb Z^n? (In other words that the determinant is +1 or -1.)

Probably, I thought, the answer is less than exponentially small.

The main question

Hoi moved quickly to the main question

Main question: Now think about the rows of a random 0-1 (n+1) \times n matrix. How likely it is that this is the full \mathbb Z^n?

Hmm, I was not sure how quickly the answer should tend to zero. But I learnt quickly that the answer does not tend to zero at all!

A remarkable heuristic formula: the probability for a random integral matrix from (n+1)-dimensions to n-dimenssions to be surjective is

one over  (ζ(2)ζ(3)ζ(4)ζ(5)…) 

What would justify this formula? Hoi described the following heuristic argument.

  1. To be surjective you need to be surjective modulo p for every prime number p.
  2.  Take some p. The probability to be surjective modulo p when the entries are uniformly random (independently) numbers modulo p is \prod_{j=2}^{n+1}(1-p^{-j}).
  3. This probability continues to work if you consider 0-1 entries.
  4. You can assume that all these probabilities for different primes are statistically independent.
  5. When you multiply all these probabilities you get

\zeta(2)^{-1}\zeta(3)^{-1}\zeta(5)^{-1}\zeta(7)^{-1}\cdots

When Hoi reached this formula in his Oberfolfach lecture my immediate thought was this: This is a remarkable formula; maybe it is even true although it looks very hard to justify the two crucial steps  in the heuristics. Why you can assume that 0-1 matrices behave like random matrices with uniform entries and why we have statistical independence that allows us to multiply probabilities just like in high school probability class? And maybe it is not true.

(This heuristics is known as the Cohen Lenstra heuristics and it was made for understanding the structure of class groups of quadratic fields.)

And then came the next slide of the presentation.

 

Hoi Nguyen and Melanie Wood actually proved this formula!

This is  a special case of a considerably more general formula. Look at the paper for more details and for the proofs.

It looks to me that the proof is tour de force and it uses various difficult and delicious techniques and earlier results. Various new and old Littlewood-Offord type results which are independently interesting are used.

And here is a related paper by Hoi and Melanie: Cokernels of adjacency matrices of random r-regular graphs.

 

Little more

As mentioned in the Nguyen-Wood paper, Shaked Koplewitz   roposed and proved some cases the Cohen-Lenstra heuristic for integral n by n+k matrices. (See Skaed’s comment below.)

As for background problem 2, the paper mentioned that the fact that the probability tends to 0 follows from Corollary 3.4 from a paper by Melanie Wood: Random integral matrices and the Cohen Lenstra Heuristics.  (Maybe there are different avenues for showing that there is a vanishing probability for every specific value of the determinant as well.) I don’t know if it is known that the probability that the determinant is 1 is exponentially small. (You can guess it is like square root of n! or something like that.) Also I don’t know if the ratio between the probabilities that the determinant is 3 and that it is 7 respects the Cohen Lenstra heuristics. Do we expect it at all? You can regard the determinant as a strange random walk so what is the reason that stopping at 3 will be different than stopping at 7?  It is also not known and this is raised as a question in the paper if the probability that the determinant is a perfect square respects the Cohen-Lenstra heuristics (and this seems reasonable).

There are similar nice questions for simplicial complexes. See the paper Cohen–Lenstra heuristics for torsion in homology of random complexes, by Matthew Kahle, Frank Lutz, Andrew Newman, and Kyle Parsons.

So if you consider the torsion of the 7 dimensional homology of a random 14 dimensional manifolds. Then (unless there are theorems to the contrary) it is natural to guess that the torsion will obey a Cohen-Lenstra heuristic of some kind.  This also applies to rationally acyclic complexes (hypertrees) and various other gadgets.

 

Posted in Algebra, Combinatorics, Number theory, Probability | Tagged , | 6 Comments