What’s The Longest Proof I’ve Done?


You know what’s a question I’m surprised I don’t get asked? I mean in the context of being a person with an advanced mathematics degree. I don’t get asked what’s the longest proof I’ve ever done. Either just reading to understand, or proving for myself. Maybe people are too intimidated by the idea of advanced mathematics to try asking such things. Maybe they’re afraid I’d bury them under a mountain of technical details. But I’d imagine musicians get asked what the hardest or the longest piece they’ve memorized is. I’m sure artists get asked what’s the painting (or sculpture, or whatnot) they’ve worked on the longest was.

It’s just as well nobody’s asked. I’m not sure what the longest proof I’ve done, or gone through, would even be. Some of it is because there’s an inherent arbitrariness to the concept of “a proof”. Proofs are arguments, and they’re almost always made up of many smaller pieces. The advantage of making these small pieces is that small proofs are usually easier to understand. We can then assemble the conclusions of many small proofs to make one large proof. But then how long was the large proof? Does it contain all the little proofs that go into it?

And, truth be told, I didn’t think to pay attention to how long any given proof was. If I had to guess I would think the longest proof I’d done, just learned, would be from a grad school course in ordinary differential equations. This is the way we study systems in which how things are changing depends on what things are now. These often match physical, dynamic, systems very well. I remember in the class spending several two-hour sessions trying to get through a major statement in a field called Kolmogorov-Arnold-Moser Theory. This is a major statement about dynamical systems being perturbed, given a little shove. And it describes what conditions make the little shove really change the way the whole system behaves.

What I’m getting to is that there appears to be a new world’s record-holder for the Longest Actually Completed Proof. It’s about a problem I never heard of before but that’s apparently been open since the 1980s. It’s known as the Boolean Pythagorean Triples problem. The MathsByAGirl blog has an essay about it, and gives some idea of its awesome size. It’s about 200 terabytes of text. As you might imagine, it’s a proof by exhaustion. That is, it divides up a problem into many separate cases, and tries out all the cases. That’s a legitimate approach. It tends to produce proofs that are long and easy to verify, at least at each particular case. They might not be insightful, that is, they might not suggest new stuff to do, but they work. (And I don’t know that this proof doesn’t suggest new stuff to do. I haven’t read it, for good reason. It’s well outside my specialty.)

But proofs can be even bigger. John Carlos Baez published a while back an essay, “Insanely Long Proofs”. And that’s awe-inspiring. Baez is able to provide theorems which we know to be true. You’ll be able to understand what they conclude, too. And in the logic system applicable to them, their proofs would be so long that the entire universe isn’t big enough just to write down the number of symbols needed to complete the proof. Let me say that again. It’s not that writing out the proof would take more than all the space in the universe. It’s that writing out how long the proof would be, written out would take more than all the space in the universe.

So you should ask, then how do we know it’s true? Baez explains.

Advertisements

Exam Grades And Ramsey Theory


While I don’t have any topics overwhelming my search-engine profile, I do see the rise in people looking up what they need to pass their class, or to get a desired minimum grade. The sorry answer is, they needed to start work sooner. But here’s the formula for working it out, for whatever your course average to date is, whatever score you want, whatever extra credit is available, all that. And here’s tables for some of the common cases, if you’re afraid of the formulas.

And for pleasantly recreational mathematics … I forget which mathematics twitter account that I follow posted the above. But it links to “Ramsey Theory in the Dining Room”. I’d mentioned the field last month because its question about organizing dinner-party guests somehow got a Dear Abby correspondent all angry in the late 70s.

Brian Hayes there ran across an application of the theory that gets away from dinner-party invites and into table place settings. It’s worth a read, particularly for the challenge posed. Hayes thought, briefly, he had solved a question in Ramsey Theory, one that’s easy to understand — you’ll understand the question — but that everyone else in the field has found too hard to answer. He doubted his result, but didn’t think until the next day of why he was wrong. Can you spot where he went wrong? (It’s a subtle flaw in the reasoning, but one an eight-year-old would understand, so I recommend trying to think like one.)

Why Was Someone Upset With Ramsey Theory In 1979?


I mentioned a couple weeks back reading John Stillwell’s Roads To Infinity: The Mathematics of Truth and Proof and how it stirred my desire to do mathematical logic. Besides that it reminded me of a baffling thing I’d read sometime around 1980. My memory is too vague to pin down the year nearer than that, but it was surely sometime between 1979 and 1983.

It draws on some newspaper column, I think a letter to Dear Abby or Dear Ann Landers. The letter-writer was complaining about ivory-tower academicians such as (to paraphrase) “mathematicians who work on how many people can be at a dinner party without three knowing each other instead of on solving world hunger”. The complaint struck me as unfair as a kid. The skills that make good mathematicians don’t have to have anything to do with feeding people. And it struck me even back then there was probably enough food produced. It was just not getting to hungry people for reasons that were likely, at heart, evil. (Today, I hold basically the same view.) Still the letter struck me as weird because … … Well, even granting the argument that mathematicians could be working on world hunger instead, what is Dear Abby supposed to do about it? (That I don’t remember Dear Abby’s response suggests maybe it was some other feature, or perhaps the letters to the editor. Or that she had no good answer.)

Roads To Infinity brings this old complaint back to mind because among its pages it discusses Ramsey Theory. This is a section of mathematics interested in combinatorics and graph theory. Its questions are like: how many ways can you arrange things that connect to one another with certain restrictions? And the dinner-party thing is the one piece of Ramsey Theory that any normal, non-mathematician might have heard of. This is because it’s a theorem that can be put into an immediately accessible, immediately understandable form. Even a seven-year-old can understand the question. The seven-year-old could even follow a demonstration of why the proof is true. The seven-year-old might even follow the proof, because it’s easier than you might guess.

The problem alluded to by the Dear Abby(?) complainer, and discussed in Roads To Infinity, is: what is the smallest number of people you must invite to a party to be sure that either at least three of them all know one another, or that at least three of them do not know one another? This is the simplest interesting example of the “party problem”. It asks how many things you need to gather so as to be sure that either some number m share a property, or some number n of them do not. I’ll not spoil the fun for people who want to work out this particular case.

What’s interesting about the result is that it suggests you can’t avoid structure. Get together enough things that can either have or not-have a relationship between pairs. Furthermore you will get relationships among bigger groups. We could interpret this as a reason there must be coincidences; logic compels them. The field speaks to us about how things must relate to one another.

But here’s what has me baffled: why was the Dear Abby(?) letter-writer aware of Ramsey Theory? What was going on in United States pop culture of the late-70s or early-80s that this might have been on the complainer’s mind? Why not something at least as abstract and more accessible, like the Goldbach conjecture? (That’s the notion any even number greater than two can be written as the sum of two primes?) Did something tell people this dinner-party problem was something mathematicians had worked on? Did Johnny Carson make a monologue joke about it?

The original problem, as best I can figure, was solved in 1930. Perhaps there was a surprising improvement in the proof that made it newsworthy at the time. I don’t know the history of mathematics in the 1970s in the right detail for that. Was it a recreational-mathematics challenge going around, the way a couple months ago everybody was worked up about that Singapore Birthday problem? Was there a good bio-pic of Frank Plumpton Ramsey that came out around that time?

I don’t know what motivated the letter-writer to start. Nor do I know why the memory of that letter should have lasted in my mind. I am curious if someone can suggest why the subject ever entered the realm of people complaining in newspapers, though.