charles_seife's picture
Professor of Journalism, New York University; Former Journalist, Science Magazine; Author, Hawking Hawking

The Power Of One, Two, Three

Sometimes even the simple act of counting can tell you something profound.

One day, back in the late 1990s, when I was a correspondent for New Scientist magazine, I got an e-mail from a flack waxing rhapsodic about an extraordinary piece of software. It was a revolutionary data-compression program so efficient that it would squash every digital file by 95% or more without losing a single bit of data. Wouldn't my magazine jump at the chance to tell the world about the computer program that will make their hard drives hold 20 times more information than every before.

No, my magazine wouldn't.

No such compression algorithm could possibly exist; it was the algorithmic equivalent of a perpetual motion machine. The software was a fraud.

The reason: the pigeonhole principle.

The pigeonhole principle is a simple counting argument. It says that if you've got N pigeons and manage to stuff them into fewer than N boxes, then at least one box must have more than one pigeon in it. As blindingly obvious as this is, it's a powerful tool.

For example, imagine that the compression software really worked as advertised, and every file is shrunk by a factor of 20 without any loss of fidelity. Every single file 2000 bits long will be squashed down into a mere 100 bits, and then, when the algorithm is reversed, it expands back into its original form, unscathed.

When compressing files, you bump up against the pigeonhole principle. There are many more 2000-bit pigeons (22000, to be exact) than 100-bit boxes (2100). If an algorithm stuffs the former into the latter, at least one box must contain multiple pigeons. Take that box
—that 100-bit file—and reverse the algorithm, expanding the file into its original 2000-bit form. You can't! Since there are multiple 2000-bit files which all wind up being squashed into to the same 100-bit file, the algorithm has no way of knowing which one was the true original—it can't reverse the compression.

The pigeonhole principle puts an absolute limit on what a compression algorithm can do. It can compress some files—often dramatically—but it can't compress them all, at least if you insist on perfect fidelity.

Counting arguments similar to this one have opened up entire new realms for us to explore. Georg Cantor used a kind of reverse-pigeonhole-principle technique to show that it was impossible to fit the real numbers into boxes labeled by the integers—even though there are an infinite number of integers. The almost unthinkable consequence was that there were different levels of infinity; the infinity of the integers was dwarfed by the infinity of the reals, which, in turn is dwarfed by yet another infinity and another infinity on top of that... an infinity of infinities, all unexplored until we learned to count them.

Taking the pigeonhole principle into deep space has an even stranger consequence. A principle in physics, the holographic bound, implies that in any finite volume of space, there are only a finite number of possible configurations of matter and energy in that space. If, as cosmologists tend to believe, the universe is infinite, there are an infinite number of visible-universe-sized volumes out there—enormous cosmos-sized bubbles containing matter and energy. And if space is more or less homogeneous, there's nothing particularly special about the cosmos-sized-bubble we live in. These assumptions, taken together, lead to a stunning conclusion. Infinite universe-sized bubbles, with only a finite number of configurations of the matter and energy in those bubbles mean that there's not just an exact copy of our universe—and our earth—out there, the transfinite version of the pigeonhole principle states that there's an infinite number of copies of every (technically, "almost every," which has a precise mathematical definition) possible universe. Not only are there infinite copies of you on infinite alternate Earths, there are infinite copies of countless variations upon the theme: versions of you with a prehensile tail, versions of you with multiple heads, versions of you that have made a career juggling carnivorous rabbit-like animals in exchange for costume jewelry.

Even something as simple as counting one, two, three can lead to a completely unexpected realm.