Zauner’s conjecture is true in dimensions 18, 20, 21, 30, 31, 37, 39 and 43

Two years ago, I blogged about Tuan-Yow Chien’s PhD thesis, which proved Zauner’s conjecture in dimension 17. The idea was to exploit certain conjectures on the field structure of SIC-POVM fiducial vectors so as to round numerical solutions to exact solutions. This week, the arXiv announced Chien’s latest paper (coauthored with Appleby, Flammia and Waldron), which extends this work to find exact solutions in 8 new dimensions.

The following line from the introduction caught my eye:

For instance the print-out for exact fiducial 48a occupies almost a thousand A4 pages (font size 9 and narrow margins).

As my previous blog entry illustrated, the description length of SIC-POVM fiducial vectors appears to grow rapidly with d. However, it seems that the rate of growth is much better than I originally thought. Here’s a plot of the description lengths of the known fiducial vectors (the new ones due to ACFW17available here — appear in red):

Continue reading Zauner’s conjecture is true in dimensions 18, 20, 21, 30, 31, 37, 39 and 43

Genius at Play: The Curious Mind of John Horton Conway

I got exactly what I wanted for Christmas this year! This book is great, and I highly recommend it:


True story: One evening in 1996, I remember watching the news with my parents, and the program concluded with a “Persons of the Week” segment, in which the winner of the Westinghouse Science Talent Search was interviewed. Jacob Lurie‘s winning research investigated a certain collection of numbers that, at the time, didn’t seem terribly exciting to me. I asked my parents, “What’s so interesting about serial numbers?” After laughing at my honest confusion, my parents offered some explanation: “He’s talking about surreal numbers, not serial numbers.” But in the absence of wikipedia, no further explanation could be provided.

Continue reading Genius at Play: The Curious Mind of John Horton Conway

Zero to One: Notes on Startups, or How to Build the Future

I’ve been thinking a lot about my place in the world lately. I’m interested in doing math that makes a difference, and considering much of the breakthroughs in our society have come from various startups, I decided to investigate the startup culture. How might academia benefit from startup culture? One could easily imagine a hip research environment adorned with beanbag chairs and foosball tables, but these perks aren’t the stuff that makes a startup successful. To catch a glimpse, I turned to a book recently written by Peter Thiel (of PayPal fame):


Continue reading Zero to One: Notes on Startups, or How to Build the Future

The Signal and the Noise

I recently finished Nate Silver‘s famous book. Some parts were more fun to read than others, but overall, it was worth the read. I was impressed by Nate’s apparently vast perspective, and he did a good job of pointing out how bad we are at predicting certain things (and explaining some of the bottlenecks).


Based on the reading, here’s a brief list of stars that need to align in order to succeed at prediction:

Continue reading The Signal and the Noise

How Not to Be Wrong: The Power of Mathematical Thinking

I recently read this book by Jordan Ellenberg, and I wanted to briefly discuss it. My first impressions:

  • Is that really where “not” belongs in the title? (Answer: yes.)
  • This is nothing like The Grasshopper King.
  • The footnotes are fun.

Jordan introduces the book with a college student asking why math is so important. This book is an answer of sorts: It provides a bunch of simple, yet profound morsels of mathematical thinking. Actually, most of Jordan’s examples reveal how to properly think about the sort of math you might encounter in a newspaper (e.g., statistical significance that balding signifies future prostate cancer). I wonder if this book could form the basis of a “Math for the Humanities” type of class. Such a class might have more to offer the non-technical college student than calculus would. Overall, I highly recommend this book to everyone (including my mathematically disoriented wife).

Continue reading How Not to Be Wrong: The Power of Mathematical Thinking

Living on the edge: A geometric theory of phase transitions in convex optimization

Phase transitions are very common in modern data analysis (see this paper, for example). The idea is that, for a given task whose inputs are random linear measurements, there is often a magic number of measurements M^* such that if you input M\ll M^* measurements, the task will typically fail, but if you input M\gg M^* measurements, the task will typically succeed. As a toy example, suppose the task is to reconstruct an arbitrary vector in \mathbb{R}^N from its inner products with M random vectors; of course, M^*=N in this case. There are many tasks possible with data analysis, signal processing, etc., and it’s interesting to see what phase transitions emerge in these cases. The following paper introduces some useful techniques for exactly characterizing phase transitions of tasks involving convex optimization:

Living on the edge: A geometric theory of phase transitions in convex optimization

Dennis Amelunxen, Martin Lotz, Michael B. McCoy, Joel A. Tropp

Along with this paper, I highly recommend watching this lecture by Joel Tropp on the same topic. This blog entry is based on both the paper and the lecture.

Continue reading Living on the edge: A geometric theory of phase transitions in convex optimization

A fully automatic problem solver with human-style output

I think most would agree that the way we do math research has completely changed with technology in the last few decades. Today, I type research notes in LaTeX, I run simulations in MATLAB and Mathematica, I email with collaborators on a daily basis, I read the arXiv and various math blogs to keep in the know, and when I get stuck on something that’s a little outside my expertise, I ask a question on MathOverflow. With this in mind, can you think of another step we can take with technology that will revolutionize the way we conduct math research? It might sound ambitious, but the following paper is looking to make one such step:

A fully automatic problem solver with human-style output

M. Ganesalingam, W. T. Gowers

The vision of this paper is to make automated provers extremely mathematician-friendly so that they can be used on a day-to-day basis to help prove various lemmas and theorems. Today, we might use computers as a last resort to verify a slew of cases (e.g., to prove the four color theorem or the Kepler conjecture). The hope is that in the future, we will be able to seamlessly interface with computers to efficiently implement human-type logic (imagine HAL 9000 as a collaborator).

The paper balances its ambitious vision with a modest scope: The goal is to produce an algorithm which emulates the way human mathematicians (1) prove some of the simplest results that might appear in undergraduate-level math homework, and (2) write the proofs in LaTeX. To be fair, the only thing modest about this scope is the hardness of the results that are attempted, and as a first step toward the overall vision, this simplification is certainly acceptable. (Examples of attempted results include “a closed subset of a complete metric space is complete” and “the intersection of open sets is open.”)

Continue reading A fully automatic problem solver with human-style output