Archive for the 'Math' Category

Truth, Provability and the Fabric of the Universe

Here is my talk to the University of Rochester’s Society of Undergraduate Math Students on “Truth, Provability and the Fabric of the Universe”. The audience was great, and except for a couple of slips of the tongue (like “Sir William of Ockham” for “William of Ockham”), I thought it went very well.

Get the Flash Player to see this content.

(Click the lower right hand corner to view fullscreen, or click here for higher quality video).

Faithful readers will recognize multiple themes from the book The Big Questions, and from numerous past blog posts, including:

Continue reading ‘Truth, Provability and the Fabric of the Universe’

Share/Save

Many Many Worlds

tegmarkMax Tegmark is a professor of physics at MIT, a major force in the development of modern cosmology, a lively expositor, and the force behind what he calls the Mathematical Universe Hypothesis — a vision of the Universe as a purely mathematical object. Readers of The Big Questions will be aware that this is a vision I wholeheartedly embrace.

Tegmark’s new book Our Mathematical Universe is really several books intertwined, including:

  1. A brisk tour of the Universe as it’s understood by mainstream cosmologists, touching on many of the major insights of the past 2000 years, beginning with how Aristarchos figured out the size of the moon, and emphasizing the extraordinary pace of recent progress. In just a few years, cosmologists have gone from arguing over whether the Universe is 10 billion or 20 billion years old to arguing over whether it’s 13.7 or 13.8.

    Continue reading ‘Many Many Worlds’

A Pi-Day Treat

In 1706, the British astronomer John Machin calculated π to 100 digits (by hand of course). His trick was to notice that π = 16A – 4B where A and B are given by

If you’re computing by hand, this is an excellent discovery, because the series for A involves a lot of divisions by 5, which are a lot easier to calculate than, say, divisions by 7, and the series for B converges very fast, so just a few terms buys you a whole lot of accuracy. (Try using, say, just the first four terms of A and just the first term of B to see what I mean.)

Machin’s 100 digits were a substantial improvement over the 72 digits obtained just a little earlier by Abraham Sharp, using the far less efficient series

In 1729, a Frenchman named de Lagny got all the way to 127 digits, but, in the words of the scientist/engineer/philosopher/historian Petr Beckmann (of whom more later), de Lagny “sweated these digits out by Sharp’s series, and so exhibited more computational stamina than mathematical wits.”

Machin’s methods were ingenious, but no more ingenious — and certainly no more striking — than John Wallis’s 1655 discovery that


which still looks awesome to me after decades of familiarity.

Continue reading ‘A Pi-Day Treat’

Hi, Mom!

MomMy mother, who reads this blog, reports that she’s lost a few nights’ sleep lately, tormented by thoughts of Knights, Knaves and Crazies. Serves her right. Once when she and I were very young, she tormented me with a geometry puzzler that I now know she must have gotten (either directly or indirectly) from Lewis Carroll; you can find it here. If she remembers the solution, she should be able to sleep tonight.

Herewith, a proof that a right angle can equal an obtuse angle. The puzzle, of course, is to figure out where I cheated.

But wait! Let’s do this as a video, since I’m starting to fool around with this technology and could use the practice. Consider this more or less a first effort. If you prefer the old ways, you can skip the video and read the (identical) step-by-step proof below the fold.

Get the Flash Player to see this content.

Or, if you prefer to skip the video, start here:

Continue reading ‘Hi, Mom!’

News From The Math World

Big news from the math world:

One of the oldest problems in number theory is the twin primes problem: Are there or are there not infinitely many ways to write the number 2 as a difference of two primes? You can, for example, write 2 = 5 -3, or 2 = 7 – 5, or 2 = 13 – 11. Does or does not this list go on forever? There are very strong reasons to believe the answer is yes, but many a great mathematician has tried and failed to find a proof.

Here’s a related problem: Are there or are there not infinitely many ways to write the number 4 as a difference of two primes? What about the number 6? Or 8? Or any even number you care to think about? It seems likely that the answer is yes in every case, though no proof is known in any case. But….

Continue reading ‘News From The Math World’

Seven Trees in One

When you met the late Armen Alchian on the street, he used to greet you not with “Hello” or “How ya doin’?”, but with “What did you learn today?” Today I learned that there are contexts in which the most ludicrous reasoning is guaranteed to lead you to a correct conclusion. This is too cool not to share.

But first a little context. The first part is a little less cool, but it’s still fun and it will only take a minute.

First, I have to tell you what a tree is. A tree is something that has a root, and then either zero or two branches growing out of that root, and then either zero or two branches (a “left branch” and a “right branch”) growing out of each branch end, and then either zero or two branches growing out of each of those branch ends, and so on. Here are some trees. (The little red dots are the branch ends and the big black dot is the root; these trees grow upside down.)

A pair of trees is, as you might guess, two trees — a first and a second.

There are infinitely many trees, and infinitely many pairs of trees, and purely abstract considerations tell us that there’s got to be a one-one correspondence between these two infinities. But what if we ask for a simple, easily describable one-one correspondence? Well, here’s an attempt: Starting with a pair of trees, you can create a single tree by creating a root with two branches, and then sticking the two trees from the pair onto the ends of the two branches. Like so:

Continue reading ‘Seven Trees in One’

A Sip of Monstrous Moonshine


You and a stranger have been instructed to meet up sometime tomorrow, somewhere in New York City. You (and the stranger) can decide for yourselves when and where to look for each other. But there can be no advance communication. Where do you go?

Me, I’d be at the front entrance to the Empire State Building at noon, possibly missing my counterpart, who might be under the clock at Grand Central Station. But, because there are only a small number of points in New York City that stand out as “extra-special”, we’ve at least got a chance to find each other.

A Schelling point is something that stands out from the background so sharply that we can expect people to coordinate around it. Schelling points are on my mind this week, because I’ve just heard David Friedman give a fascinating talk about the evolution of property rights, and Schelling points play a big role in his story. But that story is not the topic of this post.

Instead, I’m curious about the Schelling points that say, two mathematicians, or two economists, or two philosophers, or two poets, or two street hustlers might converge on. Suppose, for example, that you asked two mathematicians each to separately pick a number between 200 and 300, with a prize if their answers coincide. I’m guessing they both go for 256, the only power of two within range.

Continue reading ‘A Sip of Monstrous Moonshine’

Accounting for Numbers

Over at Less Wrong, the estimable Eliezer Yudkowsky attempts to account for the meaning of statements in arithmetic and the ontological status of numbers. I started to post a comment, but it got long enough that I’ve turned my comment into a blog post. I’ve tried to summarize my understanding of Yudkowsky’s position along the way, but of course it’s possible I’ve gotten something wrong.

It’s worth noting that every single point below is something I’ve blogged about before. At the moment I’m too lazy to insert links to all those earlier blog posts, but I might come back and put the links in later. In any event, I think this post stands alone. Because it got long, I’ve inserted section numbers for the convenience of commenters who might want to refer to particular passages.

1. Yudkowsky poses, in essence, the following question:

Main Question, My Version: In what sense is the sentence “two plus two equals four” meaningful and/or true?

Yudkowsky phrases the question a little differently. What he actually asks is:

Main Question, Original Version: In what sense is the sentence “2 + 2 = 4″ meaningful and/or true?”

This, I think, threatens to confuse the issue. It’s important to distinguish between the numeral “2″, which is a formal symbol designed to be manipulated according to formal rules, and the noun “two”, which appears to name something, namely a particular number. Because Yudkowsky is asking about meaning and truth, I presume it is the noun, and not the symbol, that he intends to mention. So I’ll stick with my version, and translate his remarks accordingly.

2. Yudkowsky provisionally offers the following answer:

Continue reading ‘Accounting for Numbers’

Simple as ABC

The (really really) big news in the math world today is that Shin Mochizuki has (plausibly) claimed to have solved the ABC problem, which in turn suffices to settle many of the most vexing outstanding problems in arithmetic. Mochizuki’s work rests on so many radically new ideas that it will take the experts a long time to digest. I, who am not an expert, will surely die with only a vague sense of the argument. But based on my extremely limited (and possibly mistaken) understanding, it appears that Mochizuki’s breakthrough depends at least partly on his willingness to abandon the usual axioms for the foundations of mathematics and replace them with new axioms. (See, for example, the first page of these notes from one of Mochizuki’s lectures. You can find other related notes here.)

That’s interesting for a lot of reasons, but the one that’s most topical for The Big Questions is this: No mathematician would consider rejecting Mochizuki’s proof just because it relies on new axiomatic foundations. That’s because mathematicians (or at least the sort of mathematicians who study arithmetic) don’t particularly care about axioms; they care about truth.

There’s a widespread misconception that arithmetic is about “what can be derived from the axioms”, which is a lot like saying that astronomy is about “what can be discovered through telescopes”. Axiomatic systems, like telescopes, are investigative tools, which we are free to jettison when better tools come along. The blather of thoughtless imbeciles notwithstanding, what really matters is the fundamental object of study, whether it’s the system of natural numbers or the planet Jupiter.

Mathematicians care about what’s true, not about what’s provable; if a truth isn’t provable, we’re fine with changing the rules of the game to make it provable.

Continue reading ‘Simple as ABC’

The Visionary

I mentioned earlier this week that I’d been crafting a long post on the fabric of the Universe when I was sidetracked by relatively mundane political events. Now I’ve been sidetracked again by the entirely unexpected (to me) news of the death from melanoma, at age 65, of the Fields Medalist Bill Thurston, who devoted his life to understanding the shape of space.

One-dimensional topology is the study of curves and two-dimensional topology is the study of surfaces. Both subjects are quite well understood. Thurston was the king of three-dimensional topology, which gains additional interest from the fact that we perceive ourselves as living in a three-dimensional Universe. Three-dimensional topology attempts to classify all the possible shapes for that Universe.

One of course is also interested in four, five, six and many-dimensional topology, four dimensions being of particular interest because they can be used to model space together with time. But although three dimensions are more complicated than two and two are more complicated than one, it turns out that when you go much higher, a lot of things get simpler. Consider knots, for example. There are no knots inside a one or two dimensional space; a knot needs three dimensions in which to pass over and under itself. But in more than three dimensions, you can untie any knot just by pulling on its ends — roughly because the additional dimensions give it so much space in which to untangle itself. For those and related reasons, topology is often hardest in three and four dimensions — coincidentally (or maybe not) the very dimensions most relevant to the way we experience the world.

Thurston revolutionized three-dimensional topology in the 1980s with his geometrization conjecture, which says that any three-manifold (the three-dimensional analogue of a smooth curve or surface) can be cut up into pieces, each of which exhibits one of eight permissible geometries. The simplest of those geometries is the flat three-dimensional space you think you see around you, where you can draw three straight lines in mutually perpendicular directions and extend them forever. Another is the geometry of the three-dimensional sphere, which is an analogue of the two-dimensional surface of the earth, where any “straight” line eventually circles back to meet itself.

The geometrization conjecture was important, but what really mattered was the vast array of new techniques Thurston introduced for visualizing and understanding the structure of three-manifolds. When those techniques came on line in the early 1980s, he was widely acclaimed as the mathematician of the decade.

One thing that set Thurston apart was his insistence that mathematics is a human study, and that it’s the mathematician’s job to communicate not just theorems and proofs, but a unique way of thinking. Stories are often told of mid-twentieth century mathematicians (usually French) who, when asked a question about their work, would scribble a picture on the blackboard, deliberately stand in front of that picture to shield it from everyone else’s view, and then, having studied it a few minutes, erased the picture, turned around, and gave a purely formal explanation designed to obscure all of the motivation and insight. Nobody ever told a story like that about Bill Thurston. Here he is, talking about the mystery of three-manifolds; dip in at a random moment and chances are excellent you’ll hear him talking not about how he proved a theorem but about how he sees the world:

Continue reading ‘The Visionary’

Chain Reaction


If you study economics, or statistics, or chemistry, or mathematical biology, or thermodynamics, you’re sure to encounter the notion of a Markov chain — a random process whose future depends probabilistically on the present, but not on the past. If you travel through New York City, randomly turning left or right at each corner, then you’re following a Markov process, because the probability that you’ll end up at Carnegie Hall depends on where you are now, not on how you got there.

But even if you work with Markov processes every day, you’re probably unaware of their origins in a dispute about free will, Christianity, and the Law of Large Numbers.

Continue reading ‘Chain Reaction’

Tuesday Puzzle

There’s an old puzzle popular among a certain type of schoolchildren that challenges the solver to write as many positive integers as possible using exactly four 4′s, together with some set of mathematical operations. (As is often the case with school children, the exact rules tend to get negotiated in real time as the puzzle is being solved.) Some examples are:

But when I became a man, I put away childish things. So here’s the grown-up version of the problem, which I got from Mel Hochster over 20 years ago, and still don’t know how to solve:

This being a grown-up problem, the rules are carefully specified:

Continue reading ‘Tuesday Puzzle’

The Number Devil

devilIn the comments section of Bob Murphy’s blog, I was asked (in effect) why I insist on the objective reality of the natural numbers (that is, the counting numbers 0,1,2,3…) but not of, say, the real numbers (that is, the numbers we use to represent lengths — and that are themselves represented by possibly infinite decimal expansions).

There seem to be two kinds of people in the world: Those with enough techncal backgroud that they already know the answer, and those with less technical background, who have no hope — at least without a lot of work — of grasping the answer. I’m going to attempt to bridge that gap here. That means I’m going to throw a certain amount of precision to the winds, in hopes of being comprehensible to a wider audience.

Continue reading ‘The Number Devil’

That Does Not Compute

stanleyStanley Tennenbaum was an itinerant mathematician with, for much of his adult life, no fixed address and no permanent source of income. Sometimes he slept on park benches. He didn’t have a lot of teeth.

But if you were involved with mathematics in the second half of the twentieth century, sooner or later you were going to cross paths with Stanley, probably near the coffee machine in a math department. He’d proudly show you the little book he carried in his breast pocket, with the list of people to whom he owed money. Then he’d teach you something, or he’d tell you a good story.

Stanley had little tolerance for convention. His one permanent job, at the University of Rochester, came to an abrupt end during a faculty meeting where he spit on the shoes of the University president and walked out. Surely the same personality trait had something to do with his departure from the University of Chicago without a Ph.D., though the paper he wrote there (at age 22) has acquired fame and influence far beyond many of the doctoral theses of his more conventionally successful classmates. I’d like to tell you a little about that paper and what I think it means for the foundations of mathematics.

Continue reading ‘That Does Not Compute’

Humpty Dumpty’s Math Puzzle

humptyGreg Mankiw, with a hat tip to his son Nicholas, asks for a plot of the function xx, where x is a real variable. The answer he points to (provided by Pedagoguery Software) gives this picture/expanation:

Continue reading ‘Humpty Dumpty’s Math Puzzle’

Loose Ends

I’m eager to summarize the (largely excellent) discussion of last week’s nightmares and to talk about what it all means. I’ll surely get to that in the next few days. But meanwhile, we have another loose end to tie up.

I recently asked what comes next in the following series:

The answer, of course, is

Please raise your hand if you found this intuitively obvious.

In case your hand didn’t go up, consider the following sequence:

Continue reading ‘Loose Ends’

Touched by Greatness

Roger Godement, 1970I continue to be bowled over daily by the high quality of the discussion at MathOverflow, and the prominence of many of the frequent participants. But this one was special:

A newbie poster asked for a pointer to a proof of the “de Rham-Weil” theorem. There’s a bit of ambiguity about what theorem this might refer to, but I had a pretty good of what the poster meant, so I responded that the earliest reference I know of is in Grothendieck‘s 1957 Tohoku paper — which led another poster to ask if this meant de Rham and Weil had had nothing to do with it.

This triggered an appearance from the legendary Roger Godement (had he been lurking all this time?), now aged 91 and one of the last survivors of the extraordinary circle of French mathematicians who rewrote the foundations of topology and geometry in the mid-20th century and changed the look, feel and content of mathematics forever. I tend to think of them as gods and demigods. Godement’s indispensable Theorie des Faisceaux was my constant companion in late graduate school. And now he has emerged from retirement for the express purpose of chastising me:

Continue reading ‘Touched by Greatness’

IQ Test

What comes next in the following series?

(Hint: This is a calculus problem.)

Click here for the answer. Explanation forthcoming in a few days.

Click here to comment or read others’ comments.

Uh Oh

How secure is Internet security? A team of researchers recently set out to crack the security of about 6.6 million sites around the Internet that use a supposedly “unbreakable” cryptosystem. The good news is that they succeeded only .2% of the time. The bad — and rather shocking — news — is that .2% of 6.6 million is almost 13,000. That’s 13,000 sites with effectively no security. The interesting part is what went wrong. It’s a gaping security hole that I’d never stopped to consider, but is obvious once it’s pointed out.

Continue reading ‘Uh Oh’

Who Expected THAT?

Suppose you go around taking extremely close-up black-and-white pictures of randomly chosen natural and unnatural objects (rocks, trees, streams, buildings, etc.). What do they look like?

Well, each one looks like a patch of varying shades of gray, of course. But do some patches arise more than others? If each of your close-ups is, say, three pixels by three pixels, Which would you expect to see more of:

This? Or this?

Continue reading ‘Who Expected THAT?’

Rock On

rockI don’t trust rocks. Rocks keep fooling me. They sit there looking all solid until you examine them more carefully and find out they’re mostly empty space, with a smattering of charged particles here and there. Then you look a little deeper and find out those charged particles are nothing like they first appeared. They don’t even have locations. Rocks, and their constituents, are nothing at all like they first present themselves. But at least they’re real. I think.

Now here’s what genuinely baffles me: Apparently there are people in this world (and even, occasionally, in the comments section of this blog) who haven’t the slightest doubt about the existence of rocks, galaxies, squirrels, and the rest of the physical universe, but who suddenly turn into hardcore skeptics re the existence of mathematical objects like the natural numbers. (Many of these people, I suspect, are in fact affecting skepticism because of a badly mistaken belief that it makes them look sophisticated. But that’s speculation on my part, so let’s put it aside and take their positions at face value.) I just don’t get this. Why on earth would, say, a scientist, commit to the belief that there’s a physical universe out there but not a mathematical one, when we know that our perceptions of the physical universe demand constant revision, whereas our perceptions of the mathematical universe are largely eternal. My conception of the natural numbers is very close to Euclid’s; my conception of an atom bears almost no resemblance to Demosthenes’s.

Continue reading ‘Rock On’

The Big Surprise

Back in the 1930′s, Kurt Godel proved two amazing facts about arithmetic: First, there are true statements in arithmetic that can’t be proven. Second, the consistency of arithmetic can’t be proven (at least not without recourse to logical methods that are on shakier ground than arithmetic itself).

Yesterday, I showed you Gregory Chaitin’s remarkably simple proof, of Godel’s first theorem. Today, I’ll show you Shira Kritchman and Ron Raz’s remarkably simple (and very recent) proof of Godel’s second theorem. If you work through this argument, you will, I think, have no trouble seeing how it was inspired by the paradox of the surprise examination.

Continue reading ‘The Big Surprise’

Berry Interesting

confiture and ingredientsToday, I’m going to give you a short, simple proof of Godel’s First Incompleteness Theorem — the one that says there are true statements in arithmetic that can’t be proven. The proof is due to Gregory Chaitin, and it is far far simpler than Godel’s original proof. A bright high-schooler can grasp it instantly. And it’s wonderfully concrete. At the end, we’ll have an infinite list of statements, all easy to understand, and none of them provable — but almost all of them true (though we won’t know which ones).

Continue reading ‘Berry Interesting’

A Tale of Three Paradoxes

This is a tale of three paradoxes and why they matter.

  • First, the ancient Liar Paradox: “This sentence is false”. If this sentence is true, it must be false. If it’s false, it must be true.
  • Next, the century-old Berry Paradox: Call a phrase “short” if it contains fewer than 13 words. The English language contains a finite number of words, and hence a finite number of short phrases. Hence there must be some natural numbers that can’t be described by any short phrase. Among these natural numbers, there must be a smallest. What is that natural number? Why, it’s the smallest natural number that can’t be described by any short phrase, of course. Except that this number is in fact described by the short phrase in boldface.
  • Finally, the more modern Paradox of the Surprise Examination (or the Unexpected Hanging), which we discussed yesterday.

The paradoxes are slippery, because they are stated in the imprecise language of English. But each of them has inspired a precise mathematical counterpart that is central to a brilliant argument in mathematical logic.

Continue reading ‘A Tale of Three Paradoxes’

The Surprise Exam, and More Surprises

surpriseexamIf you’re the sort of person who reads this blog, you’re likely to be familiar with the paradox of the unexpected hanging, which has been floating around since 1943 but achieved popular notoriety around 1969 through the writing of Martin Gardner. But you’re less likely to be aware that the unexpected hanging plays a central role in a wonderful new piece of serious mathematics related to algorithmic complexity, Godel’s theorems, and the gap between truth and provability.

The unexpected hanging might as well be a surprise examination, and that’s the form in which I present this paradox to my students every year: In a class that meets every weekday morning, the professor announces that there will be an exam one day next week, but that students won’t know exactly which day until the exams are handed out.

The students, of course, immediately start trying to guess the day of the exam. One student (call him Bob) observes that the quiz can’t be on Friday — because if it is, the students will know that by Thursday afternoon. After all, if Monday, Tuesday, Wednesday and Thursday mornings have all passed by, only Friday remains. A Friday exam can’t be a surprise exam.

A more thoughtful student (call her Carol) observes that this means the quiz must be on one of Monday, Tuesday, Wednesday or Thursday — and that if it’s on Thursday, they’ll know that by Wednesday night. After all, Friday’s ruled out, so if Monday, Tuesday and Wednesday have passed by, then only Thursday remains. That rules out a surprise exam on Thursday.

Another student (call him Ted) observes that thanks to Bob and Carol, we know the exam must be on one of the first three days of the week — which means that if it’s not on Monday or Tuesday, it must be on Wednesday. Therefore if it’s on Wednesday, they’ll know this by Tuesday night. Scratch Wednesday from the list of possibilities.

Now Ted’s girlfriend Alice points out that the exam can’t be on Tuesday either. Whereupon Bob concludes that the exam must be on Monday. But wait a minute! Carol points out that if they know the exam will be on Monday, it can’t be a surprise. Therefore no surprise exam is possible.

The students, relieved, decide not to study. But they’re awfully surprised when they show up in class the following Tuesday and the professor hands out an exam.

Continue reading ‘The Surprise Exam, and More Surprises’

Beauty, Truth and Symmetry

galoisToday is the 200th birthday of Evariste Galois, who did not live to celebrate his 21st, but found time in his short 20 years to develop a circle of ideas that permeate modern mathematics. We know of these ideas because Galois spent the night of May 30, 1832 scribbling them furiously in a letter to a friend, in advance of the fatal duel he would fight the following morning. According to the great mathematician Hermann Weyl, “This letter, if judged by the novelty and profundity of ideas it contains, is perhaps the most substantial piece of writing in the whole literature of mankind.”

(If this were a less serious post, I might suggest that this famous letter was the first example of a Galois Correspondence.)

Now, two centuries later, every first year graduate student in mathematics spends a semester studying Galois Theory, and many devote their subsequent careers to its extensions and applications. Many of the greatest achievements of modern mathematics (for example, the solution to Fermat’s Last Theorem) are, at their core, elucidations of Galois’s 200-year-old insight.

Continue reading ‘Beauty, Truth and Symmetry’

Big News

Last week, the highly distinguished Princeton Professor Ed Nelson announced a proof that the Peano axioms for arithmetic are inconsistent — and hence so is arithmetic itself. If true, this would be much bigger news than faster-than-light neutrinos. It would be bigger news than a discovery that the South had won the American Civil War. It would be far, far bigger news than a discovery that all life on Earth was intelligently designed.

There are, after all, multiple proofs that Peano Arithmetic (that is, the fragment of arithmetic described by the Peano axioms) is consistent. Among those, the simplest and most convincing (to the overwhelming majority of mathematicians) is this: The axioms of Peano Arithmetic, and therefore the theorems of Peano Arithmetic, are all true statements about the natural numbers — and a set of true statements cannot contradict itself.

Ed Nelson rejects that argument because (exempting himself from that overwhelming majority) he doesn’t believe in the set of natural numbers — or perhaps even in individual numbers when those numbers are very large. (How do you know that 810000 exists? Have you ever counted to it?)

Continue reading ‘Big News’

Happy Birthday

twoMathOverflow turns two years old this week — a milestone in the transformation of mathematical research into a massively collaborative endeavor. It’s happening on blogs, it’s happening on mailing lists, and it’s happening in a big way on MathOverlow, where mathematicians ask and answer the sorts of questions that might come up in the faculty lounge — if the faculty lounge were populated by hundreds of experts pooling their expertise.

If you’re interested in mathematics at the research level, MathOverflow is a place to learn something new and fascinating every single day. (If you are not doing mathematics at a research level, feel free to read but please don’t feel free to join the fray; questions at anything below about a second-year graduate level should be directed to MathStackExchange, another massively collaborative site aimed, roughly, at the college level — which reminds me that it’s not just mathematical research, but also mathematical education, that is being revolutionized before our eyes.)

Continue reading ‘Happy Birthday’

Cats, Dogs and Quantum Mechanics

The game of Cats and Dogs works like this: You and your teammate are placed in separate rooms and forbidden to communicate. You are each asked a randomly chosen question: Either “Do you like cats?” or “Do you like dogs?” (Each of your questions is determined by a separate fair coin flip.)

You win if your answers agree — unless you were both asked the “cats” question, in which case you win if your answers disagree.

A little reflection should convince you that if you are allowed to meet with your partner and plot strategy before the game, then the best you can do is agree to always agree — say by both always answering “yes”. That way, you win 75% of the time, and there’s no way to do better. In particular, there’s nothing to be gained by randomizing your answers.

That, at least, is true, in a world governed by the laws of classical physics and probability theory. But in a world governed by the laws of quantum mechanics — which is to say, in the world we live in — you can in principle do better. Namely: You each carry with you one of a pair of entangled “quantum coins” (actually elementary particles, but I prefer to think of them as coins, since you’re going to use them as randomizing devices).

Continue reading ‘Cats, Dogs and Quantum Mechanics’

Friday Solution

Re yesterday’s puzzle, you’ll find answers in the comments. (We are blessed with some very smart commenters here at The Big Questions!!)

Commenter Roger Schlafly pointed this Wikipedia article where I was surprised and delighted to see a reference to a paper co-written by my old friend Dave Rusin. I did not remember that Dave had anything to do with this problem, but in retrospect I bet I knew this at one time.

I managed to dig out some notes I jotted down on this subject many many years ago. I have not doublechecked these results, and I can’t completely vouch for the careful accuracy of my younger self, so take these for what they’re worth. But here’s what I once claimed to have proved:

The reason there is exactly one pair of nonstandard six-sided dice is that six is the product of two distinct primes. For the same reason, there is exactly one pair of nonstandard n-sided dice when n is 10, or 15, or 21, or …. For any product of three distinct primes, there are at most 40 nonstandard pairs.

I also found (in what appears to be my handwriting) this chart, which I reproduce with the same caveats:

Continue reading ‘Friday Solution’