The Most-Used Mathematical Algorithm Idea in History
An octillion. A billion billion billion. That’s a fairly conservative estimate of the number of times a cellphone or other device somewhere in the world has generated a bit using a maximum-length linear-feedback shift register sequence. It’s probably the single most-used mathematical algorithm idea in history. And the main originator of this idea was Solomon Golomb, who died on May 1—and whom I knew for 35 years.
Solomon Golomb’s classic book Shift Register Sequences, published in 1967—based on his work in the 1950s—went out of print long ago. But its content lives on in pretty much every modern communications system. Read the specifications for 3G, LTE, Wi-Fi, Bluetooth, or for that matter GPS, and you’ll find mentions of polynomials that determine the shift register sequences these systems use to encode the data they send. Solomon Golomb is the person who figured out how to construct all these polynomials.
He also was in charge when radar was first used to find the distance to Venus, and of working out how to encode images to be sent from Mars. He introduced the world to what he called polyominoes, which later inspired Tetris (“tetromino tennis”). He created and solved countless math and wordplay puzzles. And—as I learned about 20 years ago—he came very close to discovering my all-time-favorite rule 30 cellular automaton all the way back in 1959, the year I was born. Continue reading
Today is the 200th anniversary of the birth of George Boole. In our modern digital world, we’re always hearing about “Boolean variables”—1 or 0, true or false. And one might think, “What a trivial idea! Why did someone even explicitly need to invent it?” But as is so often the case, there’s a deeper story—for Boolean variables were really just a side effect of an important intellectual advance that George Boole made.
When George Boole came onto the scene, the disciplines of logic and mathematics had developed quite separately for more than 2000 years. And George Boole’s great achievement was to show how to bring them together, through the concept of what’s now called Boolean algebra. And in doing so he effectively created the field of mathematical logic, and set the stage for the long series of developments that led for example to universal computation.
When George Boole invented Boolean algebra, his basic goal was to find a set of mathematical axioms that could reproduce the classical results of logic. His starting point was ordinary algebra, with variables like x and y, and operations like addition and multiplication.
At first, ordinary algebra seems a lot like logic. After all, p and q is the same as q and p, just as p×q = q×p. But if one looks in more detail, there are differences. Like p×p = p2, but p and p is just p. Somewhat confusingly, Boole used the notation of standard algebra, but added special rules to create an axiom system that he then showed could reproduce all the usual results of logic.
Boole was rather informal in the way he described his axiom system. But within a few decades, it had been more precisely formalized, and over the course of the century that followed, a few progressively simpler forms of it were found. And then, as it happens, 16 years ago I ended up finishing this 150-year process, by finding—largely as a side effect of other science I was doing—the provably very simplest possible axiom system for logic, that actually happens to consist of just a single axiom.
Every four years for more than a century there’s been an International Congress of Mathematicians (ICM) held somewhere in the world. In 1900 it was where David Hilbert announced his famous collection of math problems—and it’s remained the top single periodic gathering for the world’s research mathematicians.
This year the ICM is in Seoul, and I’m going to it today. I went to the ICM once before—in Kyoto in 1990. Mathematica was only two years old then, and mathematicians were just getting used to it. Plenty already used it extensively—but at the ICM there were also quite a few who said, “I do pure mathematics. How can Mathematica possibly help me?”
I’ve been curious about Gottfried Leibniz for years, not least because he seems to have wanted to build something like Mathematica and Wolfram|Alpha, and perhaps A New Kind of Science as well—though three centuries too early. So when I took a trip recently to Germany, I was excited to be able to visit his archive in Hanover.
Leafing through his yellowed (but still robust enough for me to touch) pages of notes, I felt a certain connection—as I tried to imagine what he was thinking when he wrote them, and tried to relate what I saw in them to what we now know after three more centuries:
I was just in New York City for the grand opening of the National Museum of Mathematics. Yes, there is now a National Museum of Mathematics, right in downtown Manhattan. And it’s really good—a unique and wonderful place. Which I’m pleased to say I’ve been able to help in various ways in bringing into existence over the past 3 years.
A little more than 3 years ago, though, my older daughter picked out of my mail a curious folding geometrical object—which turned out to be an invitation to an event about the creation of a museum of mathematics. At first, it wasn’t clear what kind of museum this was supposed to be. But as soon as we arrived at the event, it started to be much clearer: this was “math as physical experience”. With the centerpiece of the event, for example, being a square-wheeled tricycle that one could ride on a cycloidal “road”—a mathematical possibility that, as it happens, was the subject of some early Mathematica demonstrations. Continue reading
A hundred years ago this month the first volume of Whitehead and Russell’s nearly-2000-page monumental work Principia Mathematica was published. A decade in the making, it contained page after page like the one below, devoted to showing how the truths of mathematics could be derived from logic.
Principia Mathematica is inspiring for the obvious effort put into it—and as someone who has spent much of their life engaged in very large intellectual projects, I feel a certain sympathy towards it. Continue reading
A few times a year they would arrive. Email dispatches from an adventurous explorer in the world of geometry. Sometimes with subject lines like “Phenomenal discoveries!!!” Usually with images attached. And stories of how Russell Towle had just used Mathematica to discover yet another strange and wonderful geometrical object.
Then, this August, another email arrived, this time from Russell Towle’s son: “…last night, my father died in a car accident”.
I first heard from Russell Towle thirteen years ago, when he wrote to me suggesting that Mathematica’s graphics language be extended to have primitives not just for polygons and cubes, but also for “polar zonohedra”.
I do not now recall, but I strongly suspect that at that time I had never heard of zonohedra. But Russell Towle’s letter included some intriguing pictures, and we wrote back encouragingly.
There soon emerged more information. That Russell Towle lived in a hexagonal house of his own design, in a remote part of the Sierra Nevada mountains of California. That he was a fan of Archimedes, and had learned Greek to be able to understand his work better. And that he was not only an independent mathematician, but also a musician and an accomplished local historian. Continue reading
Not a lot gets written in the general press about foundational issues in mathematics, but this afternoon I found myself talking to a journalist about the subject of certainty in mathematics.
It turned out to be a pretty interesting conversation, so I thought I’d write here about a few things that came up.
Mathematics likes to think of itself as a very certainty-based business. If you’ve “proved something mathematically”, then it’s supposed to just be true. No ifs or buts. Complete certainty.
But in practice that’s not quite how it works—at least the way mathematics has traditionally been done. Because in reality a mathematical proof of the kind people publish in papers is something much more social. It’s a vehicle for convincing other humans—one’s fellow mathematicians—that something is true.
There’ve been a few million mathematical proofs published over the past century or so. Essentially all of them are written in a kind of human-compatible mixture of mathematical formalism and ordinary natural language.
They’re intended for human consumption. For people to read, and process. The best of them aren’t just arguments for some particular theorem. Instead they’re expositions that illuminate some whole mathematical structure.
But inevitably they require effort to read. It’s not just a mechanical matter. Instead, every reader of every proof has to somehow map what the proof is saying into their particular patterns of thought. So that they can personally be convinced that the proof is true.
And of course, in practice, proofs written by humans have bugs. Somewhere between the imprecision of ordinary language, and the difficulty of really thinking through every possible eventuality, it’s almost inevitable that any long proof that’s been published isn’t perfect. And even with an army of people to check it, not every bug will be found.
So how do computers—and Mathematica change this picture?