# Influence, Threshold, and Noise

My dear friend Itai Benjamini told me that he won’t be able to make it to my Tuesday talk on influence, threshold, and noise, and asked if I already have  the slides. So it occurred to me that perhaps I can practice the lecture on you, my readers, not just with the slides (here they are) but also roughly what I plan to say, some additional info, and some pedagogical hesitations. Of course, remarks can be very helpful.

I can also briefly report that there are plenty of exciting things happening around that I would love to report about – hopefully later in my travel-free summer. One more thing: while chatting with Yuval Rabani and Daniel Spielman I realized that there are various exciting things happening in algorithms (and not reported so much in blogs). Much progress has been made on basic questions: TSP, Bin Packing, flows & bipartite matching, market equilibria, and k-servers, to mention a few, and also new directions and methods. I am happy to announce that Yuval kindly agreed to write here an algorithmic column from time to time, and Daniel is considering contributing a guest post as well.

## The second AMS-IMU meeting

Since the early 70s, I have been a devoted participants in our annual meetings of the Israeli Mathematical Union (IMU), and this year we will have the second joint meeting with the American Mathematical Society (AMS). Here is the program. There are many exciting lectures. Let me mention that Eran Nevo, this year Erdős’ prize winner, will give a lecture about the g-conjecture. Congratulations, Eran! Among the 22 exciting special sessions there are a few related to combinatorics, and even one organized by me on Wednsday and Thursday.

 Combinatorics Contact person: Gil Kalai, gil.kalai@gmail.com TAU, Dan David building, Room 103 Wed, 10:50-11:30 Van H. Vu (Yale University) Real roots of random polynomials (abstract) Wed, 11:40-12:20 Oriol Serra (Universitat Politecnica de Catalunya, Barcelona) Arithmetic Removal Lemmas (abstract) Wed, 12:30-13:10 Tali Kaufman (Bar-Ilan University) Bounded degree high dimensional expanders (abstract) Wed, 16:00-16:40 Rom Pinchasi (Technion) On the union of arithmetic progressions (abstract) Wed, 16:50-17:30 Isabella Novik (University of Washington, Seattle) Face numbers of balanced spheres, manifolds, and pseudomanifolds (abstract) Wed, 17:40-18:20 Edward Scheinerman (Johns Hopkins University, Baltimore) On Vertex, Edge, and Vertex-Edge Random Graphs (abstract) Thu, 9:20-10:00 Yael Tauman Kalai (MSR, New England) The Evolution of Proofs in Computer Science (abstract) Thu, 10:10-10:50 Irit Dinur (Weitzman Institute) Lifting locally consistent solutions to global solutions (abstract) Thu, 11:00-11:40 Benny Sudakov (ETH, Zurich) The minimum number of nonnegative edges in hypergraphs (abstract)

And now for my own lecture.

# The Kadison-Singer Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava

…while we keep discussing why mathematics is possible…

## The news

Adam Marcus, Dan Spielman, and Nikhil Srivastava posted a paper entitled “Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem,” where they prove the 1959 Kadison-Singer conjecture.

(We discussed part I of “interlacing families” in this post about new Ramanujan graphs.  Looks like a nice series.)

The Kadison-Singer conjecture refers to a positive answer to a question posed by Kadison and Singer: “They asked ‘whether or not each pure state of $\cal B$ is the extension of some pure state of some maximal abelian algebra’ (where $\cal B$ is the collection of bounded linear transformations on a Hilbert space.”) I heard about this question in a different formulation known as the “Bourgain-Tzafriri conjecture” (I will state it below) and the paper addresses a related well known discrepancy formulation by Weaver. (See also Weaver’s comment on the appropriate “quantum” formulation of the conjecture.)

Updates: A very nice post on the relation of the Kadison-Singer Conjecture  to foundation of quantum mechanics is in this post in  Bryan Roberts‘ blog Soul Physics. Here is a very nice post on the mathematics of the conjecture with ten interesting comments on the proof by Orr Shalit, and another nice post on Yemon Choi’s blog and how could I miss the very nice post on James Lee’s blog.. Nov 4, 2013: A new post with essentially the whole proof appeared on Terry tao’s blog, Real stable polynomials and the Kadison Singer Problem.

Update: A very nice blog post on the new result was written by  Nikhil Srivastava on “Windows on theory.” It emphasizes the discrapancy-theoretic nature of the new result, and explains the application for partitioning graphs into expanders.

## The Bourgain-Tzafriri theorem and conjecture

Let me tell again (see this post about Lior, Michael, and Aryeh where I told it first) about a theorem of Bourgain and Tzafriri related to the Kadison-Singer conjecture.

Jean Bourgain and Lior Tzafriri considered the following scenario: Let $a > 0$ be a real number. Let $A$ be a $n \times n$ matrix with norm 1 and with zeroes on the diagonal. An $s$ by $s$ principal minor $M$ is “good” if the norm of $M$ is less than $a$.

Consider the following hypergraph $F$:

The vertices correspond to indices ${}[n]=\{1,2,\dots,n\}$. A set $S \subset [n]$ belongs to $F$ if the $S \times S$ sub-matrix of $M$ is good.

Bourgain and Tzafriri showed that for every $a > 0$ there is $C(a) > 0$ so that for every matrix $A$ we can find $S \in F$ so that $|S| \ge C(a)n$.

Moreover, they showed that for every nonnegative weights $w_1,w_2,\dots w_n$ there is $S \in F$ so that the sum of the weights in $S$ is at least $C(a)$ times the total weight. In other words, (by LP duality,) the vertices of the hypergraph can be fractionally covered by $C(a)$ edges.

The “big question” is if there a real number $C'(a) > 0$ so that for every matrix $M,$ ${}[n]$ can be covered by $C'(a)$ good sets. Or, in other words, if the vertices of $F$ can be covered by $C'(a)$ edges. This question is known to be equivalent to an old conjecture by Kadison and Singer (it is also known as the “paving conjecture”). In view of what was already proved by Bourgain and Tzafriri what is needed is to show that the covering number is bounded from above by a function of the fractional covering number. So if you wish, the Kadison-Singer conjecture had become a statement about bounded integrality gap. Before proving the full result, Marcus, Spielman and Srivastava gave a new proof of the Bourgain-Tzafriti theorem.

KADISON-SINGER MEETS BOURGAIN-TZAFRIRI by PETER G. CASAZZA, ROMAN VERSHYNIN,  The Kadison-Singer Problem in Mathematics and Engineering: A Detailed Account pdf, and many other recent publications by Pete Casazza.

# Celebrations in Sweden and Norway

### Celebrations for Endre, Jean and Terry

Anders Bjorner presents the 2012 Crafoord Prize in Mathematics

I am in Sweden for two weeks to work with colleagues and to take part in two celebrations. Jean Bourgain and Terence Tao are the 2012 laureates of the Crafoord Prize in mathematics which was awarded  last Tuesday at Lund. Along with them the 2012 Crafoord Prize in Astronomy was awarded to Reinhand Genzel and Andrea Ghez.  I took part in the symposium entitled “From chaos to harmony” to celebrate the event.

Next Friday the Swedish Royal academy will celebrate with a mini-symposium in honor of the 2012 Abel prize winner Endre Szeméredi. (Here are the slides of my future talk looking at and around the Szeméredi-Trotter theorem. Please alert me of mistakes if you see them.) The Abel prize symposium and ceremony in Oslo are  Tuesday (Today! see the picture above) and Wednesday of this week.

Congratulations again to Jean, Terry and Endre for richly deserved awards.

### Crafoord days at Lund

Owing to the passing of Count Carl Johan Bernadotte af Wisborg, H.M. King Carl XVI Gustaf was unable to attend the Crafoord Days 2012. The prizes were presented by Margareta Nilsson, daughter of the Donors, Holge and Anna-Greta Crafoord. Ms Nilsson’s kind hospitality, deep devotion to science, culture and other noble social causes, and moving childhood memories shared at the dinner,  have led Reinhard Genzel in his moving speech on behalf of the winners in Astronomy to refer to Margareta Nilsson by the words: “You were our King these past two days!”.

The one day symposium itself was very interesting, and so were the four prize lectures on Tuesday morning. In a few days The videos of the two days’ lectures will be are posted here. Here are the slides of my talk on analysis of Boolean functions, featuring, among other things a far-reaching conjectural extension of a recent theorem by Hamed Hatami.

### Gothenburg and Stockholm

From Lund I continued to a short visit of Gothenburg hosted by Jeff Steif with whom I share much interest in noise sensitivity and many other things. I then continued to Stockholm where I visit Anders Björner who is a long-time collaborator and friend since the mid eighties. For me this is perhaps the twelfth visit to Stockholm and it is always great to be here.

We will celebrate on this blog these exciting events with a rerun of the classic, much-acclaimed piece by Christine Björner on the Golden room and the golden mountain.

Speakers at Crafoord symposium, (from right to left) Carlos Kenig, Ben Green, Jean Bourgain, Terry Tao, me and Michael Christ. Copyright: Crafoord foundation.

Update(Oct 2014): Here is a picture of me and  Jean at IHES 1988

# Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier

I missed Tom by a few minutes at Mittag-Leffler Institute a year and a half ago

Suppose that $R_n$ is a subset of $\{1,2,\dots, n \}$ of maximum cardinality not containing an arithmetic progression of length 3. Let $g(n)=n/|R_n|$.

Roth proved that $g(n) \ge log logn$. Szemeredi and Heath-Brown improved it to $g(n) \ge log^cn$ for some 0″ src=”http://l.wordpress.com/latex.php?latex=c%3E0&bg=ffffff&fg=000000&s=0&#8243; alt=”c>0″ /> (Szemeredi’s argument gave $c=1/4$.) Jean Bourgain improved the bound in 1999 to $c=1/2$ and in 2008 to $c=2/3$ (up to lower order terms).

Erdös and Turan who posed the problem in 1936 described a set not containing an arithmetic progression of size $n^c$.  Salem and Spencer improved this bound to $g(n) \le e^{logn/ loglogn}$. Behrend’s upper bound from 1946 is of the form $g(n) \le e^{C\sqrt {\log n}}$. A small improvement was achieved recently by Elkin and is discussed here.  (Look also at the remarks following that post.)

In an earlier post we asked: How does $g(n)$ behave? Since we do not really know, will it help talking about it? Can we somehow look beyond the horizon and try to guess what the truth is? (I still don’t know if softly discussing this or other mathematical problems is a fruitful idea, but it can be enjoyable.)

We even had a poll collecting people’s predictions about $g(n)$.  Somewhat surprisingly 18.18% of answerers predicted that $g(n)$ behaves like $(\log n)^c$ for some $c<1$. Be the answer as it may be, reaching  the logarithmic barrier was considered extremely difficult.

A couple of months ago Tom Sanders was able to refine Bourgain’s argument and proved that $g(n) \ge (\log n)^{3/4}$. Very recently Tom have managed to reach the logarithmic barrier and to prove that

$g(n) \ge (\log n)/(\log \log n)^{5}.$

Quoting from his paper: “There are two main new ingredients in the present work: the first is a way of transforming sumsets introduced by Nets Katz and Paul Koester in 2008, and the second is a result on the $L_p$-invariance of convolutions due to Ernie Croot and Olof Sisask (2010).”

This is a truly remarkable result.