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

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.

Additional references:

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.

Posted in Analysis, Computer Science and Optimization, Physics, Updates | Tagged , , , , , | 30 Comments

Why is Mathematics Possible: Tim Gowers’s Take on the Matter

lnc math

In a previous post I mentioned the question of why is mathematics possible. Among the interesting comments to the post, here is a comment by Tim Gowers:

“Maybe the following would be a way of rephrasing your question. We know that undecidability results don’t show that mathematics is impossible, since we are interested in a tiny fraction of mathematical statements, and in practice only in a tiny fraction of possible proofs (roughly speaking, the comprehensible ones). But why is it that these two classes match up so well? Why is it that nice mathematical statements so often have proofs that are of the kind that we are able to discover?

Continue reading

Posted in Open discussion, Philosophy, What is Mathematics | Tagged , , , | 23 Comments

Polymath8: Bounded Gaps Between Primes

Yitang Zhang’s very recent shocking paper demonstrated that bounded gaps between primes occur infinitely often, with the explicit upper bound of 70,000,000 given for this gap. Polymath8 was launched for the dual purpose of learning Zhang’s proof and improving the upper bound for the gaps. Here are links for three posts (I, II, III) on Terry Tao’s blog, a post on the secret blogging seminar,  and for a post on the polymath blog. And here is the table for the world records so far.

Updates: Record for June 16 – 60,744

Posted in Mathematics over the Internet, Number theory, Updates | Tagged , | Leave a comment

Joram’s Memorial Conference

Joram2

Joram Lindenstrauss 1936-2012

This week our local Institute of Advanced Study holds a memorial conference for Joram Lindenstrauss. Joram was an immensely powerful mathematician, in terms of originality and conceptual vision, in terms of technical power, in terms of courage to confront difficult problems, in terms of clarity and elegance, and in terms of influence and leadership. Joram was a dear teacher and a dear colleague and I greatly miss him.

IMG_3032-002

One nice anecdote that I heard in the conference was about the ceremony where Joram received the Israel Prize. When he shook the hand of the Israeli president, Itzhak Navon, Navon told him: “If you have a little time please drop by to tell me sometime what Banach spaces are.” Next Joram shook the hand of prime minister Menchem Begin who overheard the comment and told Joram: “If you have a little time please do not drop by to tell me sometime what Banach spaces are.”

Continue reading

Posted in Conferences, Obituary | Tagged | 1 Comment

Andriy Bondarenko Showed that Borsuk’s Conjecture is False for Dimensions Greater Than 65!

The news in brief

Andriy V. Bondarenko proved in his remarkable paper The Borsuk Conjecture for two-distance sets  that the Borsuk’s conjecture is false for all dimensions greater than 65. This is a substantial improvement of the earlier record (all dimensions above 298) by Aicke Hinrichs and Christian Richter.

Borsuk’s conjecture

Borsuk’s conjecture asserted that every set of diameter 1 in d-dimensional Euclidean space can be covered by d+1 sets of smaller diameter. (Here are links to a post describing the disproof by Kahn and me  and a post devoted to problems around Borsuk’s conjecture.)

Two questions posed by David Larman

David Larman posed in the ’70s two basic questions about Borsuk’s conjecture:

1) Does the conjecture hold for collections of 0-1 vectors (of constant weight)?

2) Does the conjecture hold for 2-distance sets? 2-distance sets are sets of points such that the pairwise distances between any two of them have only two values.

Reducing the dimensions for which Borsuk’s conjecture fails

In 1993 Jeff Kahn and I disproved Borsuk’s conjecture in dimension 1325 and all dimensions greater than 2014. Larman’s first conjecture played a special role in our work.   While being a special case of Borsuk’s conjecture, it looked much less correct.

The lowest dimension for a counterexample were gradually reduced to  946 by A. Nilli, 561 by A. Raigorodskii, 560 by  Weißbach, 323 by A. Hinrichs and 320 by I. Pikhurko. Currently the best known result is that Borsuk’s conjecture is false for n ≥ 298; The two last papers relies strongly on the Leech lattice.

Bondarenko proved that the Borsuk’s conjecture is false for all dimensions greater than 65.  For this he disproved Larman’s second conjecture.

Bondarenko’s abstract

In this paper we answer Larman’s question on Borsuk’s conjecture for two-distance sets. We found a two-distance set consisting of 416 points on the unit sphere in the dimension 65 which cannot be partitioned into 83 parts of smaller diameter. This also reduces the smallest dimension in which Borsuk’s conjecture is known to be false. Other examples of two-distance sets with large Borsuk’s numbers will be given.

Two-distance sets

There was much interest in understanding sets of points in R^n  which have only two pairwise distances (or K pairwise distances). Larman, Rogers and Seidel proved that the maximum number can be at most (n+1)(n+4)/2 and Aart Blokhuis improved the bound to (n+1)(n+2)/2. The set of all 0-1 vectors of length n+1 with two ones gives an example with n(n+1)/2 vectors.

Equiangular lines

This is a good opportunity to mention another question related to two-distance sets. Suppose that you have a set of lines through the origin in R^n so that the angles between any two of them is the same. Such  a set is  called an equiangular set of lines. Given such a set of cardinality m, if we take on each line one unit vector, this gives us a 2-distance set. It is known that m ≤ n(n+1)/2 but for a long time it was unknown if a quadratic set of equiangular lines exists in high dimensions. An exciting breakthrough came in 2000 when Dom deCaen constructed a set of equiangular lines in R^n with 2/9(n+1)^2 lines for infinitely many values of n.

Strongly regular graphs

Strongly regular graphs are central in the new examples. A graph is strongly regular if every vertex has k neighbors, every adjacent pair of vertices have λ common neighbors and every non-adjacent pair of vertices have μ common neighbors. The study of strongly regular graphs (and other notions of strong regularity/symmetry) is a very important area in graph theory which involves deep algebra and geometry. Andriy’s construction is based on a known strongly regular graph G_2(4).

Posted in Combinatorics, Geometry, Open problems | Tagged , , , , | 2 Comments

Why is mathematics possible?

Spectacular advances in number theory

Last weeks we heard about two spectacular results in number theory.  As announced in Nature, Yitang Zhang proved that there are infinitely many pairs of consecutive primes (p_n, p_{n+1}) which are at most 70 million apart! This is a sensational achievement. Pushing 70 million to 2 will settle the ancient conjecture on twin primes, but this is already an extremely amazing breakthrough.  An earlier breakthrough came in 2005 when Daniel Goldston, János Pintz, and Cem Yıldırım proved that the gaps between consecutive primes p_{n+1}-p_n is infinitely often smaller than \sqrt {\log p_n} \log \log ^2 p_n.

Update: A description of Zhang’s work and a link to the paper can be found on Emmanuel Kowalski’s bloog Further update: A description of Zhang’s work and related questions and results can be found now in Terry Tao’s blog. Terry Tao also proposed a new polymath project aimed to reading Zhang’s paper and attempting to improve the bounds.

Harald Helfgott proved that every integer is the sum of three primes.  Here the story starts with Vinogradov who proved it for sufficiently large integers, but pushing down what “sufficiently large” is, and pushing up the computerized methods needed to take care of “small” integers required much work and ingenuity.

Why is Mathematics possible?

The recent news, and a little exchange of views I had with Boaz Barak, bring us back to the question: “Why is mathematics possible?” This is an old question that David Kazhdan outlined in a lovely 1999 essay “Reflection on the development of mathematics in the twentieth century.” The point (from modern view) is this: We know that mathematical statements can, in general, be undecidable.  We also know that a proof for a short mathematical statement can be extremely long. And we also know that even if a mathematical statement admits a short proof, finding such a proof can be computationally intractable. Given all that, what are the reasons that mathematics is at all possible?

It is popular to associate “human creativity” with an answer. The problem with incorrect (or, at least, incomplete) answers is that they often represent missed opportunities for better answers. I think that for the question “why is mathematics possible” there are opportunities (even using computational complexity thinking) to offer better answers.

Please offer your answers.

Posted in Computer Science and Optimization, Number theory, Open discussion, Philosophy, Updates, What is Mathematics | 15 Comments

Dan Mostow on Haaretz and Other Updates

Enlightenment at a red traffic light

Wolf Prize laureate Prof. George Daniel Mostow made his greatest scientific breakthrough while driving.

Haaretz tells the story of how Dan Mostow reached his breakthrough known as Mostow’s rigidity theorem.

Mostow

Congratulations, Dan!

French-Isreali Meeting and Günterfest

French-Isreali

More updates: If you are in Paris On Wednesday and Thursday this week there will be a lovely French-Isreali interacademic meeting on mathematics.  The problem is very interesting, and I will give a talk quite similar to my recent MIT talk on quantum computers.

In the  weekend  we will celebrate Günter Ziegler’s 50th birthday in Berlin. Günter started very very young so we had to wait long for this.

ziegler

 Happy birthday, Gunter

Posted in Updates | Tagged , | 1 Comment

Test Your Intuition (21): Auctions

850320-austria-photography-camera-auction

You run a single-item sealed bid auction where you sell an old camera. There are three bidders and the value of the camera for each of them is described by a certain (known) random variable: With probability 0.9 the value is 100+x where x is taken uniformly at random from the interval [-1,1]. With probability 0.1 the value is 300+x where x is as before. The 300 value represents the case that the item has a special nostalgic value for the buyer.

The values of the camera to the three bidders are thus i.i.d random variables. (The reason for adding this small random x is to avoid ties, and you can replace the interval [-1,1] with [-ε, ε] for a small ε, if you wish.) If you don’t want to worry about ties you can simply think about the value being 100 with probability 0.9 and 300 wit probability 0.1.

The basic question

The basic questions for you the seller is:

What is the highest expected revenue you, the seller, can guarantee and what is your optimal allocation policy.

I’d like to see the answer for this question. But let me challenge your intuition with two simpler questions.

1) Can the seller guarantee an expected revenue of 120  or more?

2) What (roughly) is the optimal allocation policy

a) Highest bidder wins.

b) Highest bidder wins if his bid passes some reserve price.

c) The item is allocated at random to the bidders with probabilities depending on their bids.

Background: Myerson’s paper and his revenue equivalence theorem

The most relevant paper to this post is a well-known paper Optimal auction design by Roger Myerson. Myerson considered the case of a single-item sealed-bid auction where the bidders’ values for the item are independent identical random variable.

Note that I did not specify the price that the winning bidder is going to pay for the camera. The reason is that according to a famous theorem by Myerson (referred to as the revenue equivalence theorem), when the bidders are strategic, the expected revenues for the seller are determined by the allocation rule and are independent from the pricing policy! (Well, you need to assume a reasonable pricing policy…)

For example, if the item is allocated to the highest bidder then the expected price will be the second highest price. If the price is determined by the second highest bid (Vickery’s auction) then each bidder has no incentive to give a bid which is different from its value. But even if the item will be allocated to the first bidder for the highest price, the expected revenues will still be the same! When you analyze an auction mechanism like ours you can assume that the payments are set in a way that the bidders have no incentive not to bid the true value the camera has. This is sometimes referred to as the revelation principle.

Myerson considered a mechanism which sometimes lead to higher revenues compared to allocating the item to the highest bidder: The seller set a reserve price and the item is allocated to the highest bidder if the bid passes this reserve price, and is not allocated at all otherwise. In the paper Myerson also considered more complicated allocation rules which are important in the analysis where the item is allocated to bidders according to some probabilities based on their bids.

Polls

This time we have two questions and two polls:

Once again this is a game-theory question. I hope it will lead to interesting discussion like the earlier one on tic-tac-toe.

A little more Background: Auctions and Vickery’s second price auction.

(From Wikipedia) An auction is a process of buying and selling goods or services by offering them up for bid, taking bids, and then selling the item to the highest bidder. In economic theory, an auction may refer to any mechanism or set of trading rules for exchange.

In our case, we consider an auction of a single item (the camera) and each bidder is giving a sealed bid.

(Again from Wikipedea) A Vickrey auction is a type of sealed-bid auction, where bidders submit written bids without knowing the bid of the other people in the auction, and in which the highest bidder wins, but the price paid is the second-highest bid. The auction was first described academically by Columbia University professor William Vickrey in 1961 though it had been used by stamp collectors since 1893.[2] This type of auction is strategically similar to an English auction, and gives bidders an incentive to bid their true value.

Posted in Economics, Games, Test your intuition | Tagged , , | 4 Comments

Oz’ Balls Problem: The Solution

idledisc500

A commentator named Oz proposed the following question: You have a box with n red balls and n blue balls. You take out each time a ball at random but, if the ball was red, you put it back in the box and take out a blue ball. If the ball was blue, you put it back in the box and take out a red ball.

You keep doing it until left only with balls of the same color. How many balls will be left (as a function of n)?

ozpoll

Peter Shor wrote in a comment “I’m fairly sure that there is not enough bias to get cn, but it intuitively seems far too much bias to still be c \sqrt{n}. I want to say n^c. At a wild guess, it’s either c = \frac{2}{3}or c = \frac{3}{4}, since those are the simplest exponents between \frac{1}{2} and 1.”  The comment followed by a heuristic argument of Kevin Kostelo and computer experiments by Lior Silberman that supported the answer n^{3/4}.
Continue reading

Posted in Probability, Test your intuition | Tagged , , , | 1 Comment

Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun

YK2           396px-Kelvin-1200-scale1000

Yeshu Kolodni and Lord Kelvin

The question

In 1862, the physicist William Thomson (who later became Lord Kelvin) of Glasgow published calculations that fixed the age of Earth at between 20 million and 400 million years. Later in the 1890s Kelvin calculated the age of Earth by using thermal gradients, and arrived at an estimate of 100 million years old which he later reduced to 20 million years. (For much more interesting details see this Wikipedia article.)

The question was: what was the main reason for Lord Kelvin’s wrong estimation

a) Radioactivity – Heat produced by radioactive decay; this was a process unknown to science for decades to come.

b) Convection – The transfer of heat not through radiation or heat-conduction but through the movement of hot parts to the surface; this is a process familiar in home cooking.

Here is the answer and some discussion mainly based on what Yeshu Kolodny have told me.

The short answer: Continue reading

Posted in Geology, Physics, Test your intuition | 4 Comments