Month: July 2017

A Long-Sought Proof, Found and Almost Lost

I enjoyed this article from Quanta Magazine, both for its mathematical content as well as the human interest story.

A Long-Sought Proof, Found and Almost Lost

From the opening paragraphs:

Known as the Gaussian correlation inequality (GCI), the conjecture originated in the 1950s, was posed in its most elegant form in 1972 and has held mathematicians in its thrall ever since. “I know of people who worked on it for 40 years,” said Donald Richards, a statistician at Pennsylvania State University. “I myself worked on it for 30 years.”

[Thomas] Royen hadn’t given the Gaussian correlation inequality much thought before the “raw idea” for how to prove it came to him over the bathroom sink… In July 2014, still at work on his formulas as a 67-year-old retiree, Royen found that the GCI could be extended into a statement about statistical distributions he had long specialized in. On the morning of the 17th, he saw how to calculate a key derivative for this extended GCI that unlocked the proof. “The evening of this day, my first draft of the proof was written,” he said.

Not knowing LaTeX, the word processer of choice in mathematics, he typed up his calculations in Microsoft Word, and the following month he posted his paper to the academic preprint site arxiv.org. He also sent it to Richards, who had briefly circulated his own failed attempt at a proof of the GCI a year and a half earlier. “I got this article by email from him,” Richards said. “And when I looked at it I knew instantly that it was solved” …

Proofs of obscure provenance are sometimes overlooked at first, but usually not for long: A major paper like Royen’s would normally get submitted and published somewhere like the Annals of Statistics, experts said, and then everybody would hear about it. But Royen, not having a career to advance, chose to skip the slow and often demanding peer-review process typical of top journals. He opted instead for quick publication in the Far East Journal of Theoretical Statistics, a periodical based in Allahabad, India, that was largely unknown to experts and which, on its website, rather suspiciously listed Royen as an editor. (He had agreed to join the editorial board the year before.)

With this red flag emblazoned on it, the proof continued to be ignored… No one is quite sure how, in the 21st century, news of Royen’s proof managed to travel so slowly. “It was clearly a lack of communication in an age where it’s very easy to communicate,” Klartag said.

Netflix was born out of this grad-school math problem

From Quartz magazine: Netflix was born out of this grad-school math problem

While studying computer science at Stanford University in the 1980s, Hastings said there was an exercise by computer scientist Andrew Tanenbaum in which he had to work out the bandwidth of a station wagon carrying tapes across the US. “It turns out that’s a very high-speed network,” Hastings said, speaking at a Mobile World Congress session in Barcelona. “From that original exercise, it made me think we can build Netflix first on DVD and then eventually the internet would catch up with the postal system and pass it.”

This is how Tanenbaum and co-writer David Wetherall described the problem in their book Computer Networks (fifth edition, pdf):

One of the most common ways to transport data from one computer to another is to write them onto magnetic tape or removable media (e.g., recordable DVDs), physically transport the tape or disks to the destination machine, and read them back in again. Although this method is not as sophisticated as using a geosynchronous communication satellite, it is often more cost effective, especially for applications in which high bandwidth or cost per bit transported is the key factor.

A simple calculation will make this point clear. An industry-standard Ultrium tape can hold 800 gigabytes. A box 60 × 60 × 60 cm can hold about 1000 of these tapes, for a total capacity of 800 terabytes, or 6400 terabits (6.4 petabits). A box of tapes can be delivered anywhere in the United States in 24 hours by Federal Express and other companies. The effective bandwidth of this transmission is 6400 terabits/86,400 sec, or a bit over 70 Gbps. If the destination is only an hour away by road, the bandwidth is increased to over 1700 Gbps. No computer network can even approach this. Of course, networks are getting faster, but tape densities are increasing, too.

If we now look at cost, we get a similar picture. The cost of an Ultrium tape is around $40 when bought in bulk. A tape can be reused at least 10 times, so the tape cost is maybe $4000 per box per usage. Add to this another $1000 for shipping (probably much less), and we have a cost of roughly $5000 to ship 800 TB. This amounts to shipping a gigabyte for a little over half a cent. No network can beat that. The moral of the story is:

Never underestimate the bandwidth of a station wagon full of tapes hurtling down the highway.

Meet the Math Professor Who’s Fighting Gerrymandering With Geometry

From the Chronicle of Higher Education: Meet the Math Professor Who’s Fighting Gerrymandering With Geometry, an interview with Dr. Moon Duchin, an associate professor of math and director of the Science, Technology and Society program at Tufts.

Q. What is the Metric Geometry and Gerrymandering Group’s aim?

A. In redistricting, one of the principles that’s taken seriously by courts is that districts should be compact. The U.S. Constitution does not say that, but many state constitutions do, and it’s taken as a kind of general principle of how districts ought to look.

But nobody knows exactly what compactness means. People just have the idea that it means the shape shouldn’t be too weird, shouldn’t be too eccentric; it should be a kind of reasonable shape. Lots of people have taken a swing at that over the years. Which definition you choose actually has stakes. It changes what maps are acceptable and what maps aren’t. If you look at the Supreme Court history, what you’ll see is that a lot of times, especially in the ’90s, the court would say, Look, some shapes are obviously too bizarre but we don’t know how to describe the cutoff. How bizarre is too bizarre? We don’t know; that sounds hard.

Q. It’s like how they define obscenity.

A. Exactly. When I started thinking about this, I was surprised to see that even though there were different mathematical attempts at a definition, you don’t ever see mathematicians testifying in court about it. So our first aim was to think like mathematicians about compactness and look at all the definitions that already exist, and compare them and try to prove theorems about the relationships between the definitions.

What courts have been looking for is one definition of compactness that they can understand, that we can compute, and that they can use as a kind of go-to standard. I don’t have any illusions that we’re going to settle that debate forever, but I think we can make a contribution to the debate.

See also her lecture for the Mathematical Association of America’s Distinguished Lecture Series: