Skip to content

Not As Easy As ABC

April 5, 2020

Is the claimed proof of the ABC conjecture correct?

[ Photo courtesy of Kyodo University ]

Shinichi Mochizuki is about to have his proof of the ABC conjecture published in a journal. The proof needs more than a ream of paper—that is, it is over 500 pages long.

Today I thought we would discuss his claimed proof of this famous conjecture.

The decision to published is also discussed in an article in Nature. Some of the discussion we have seen elsewhere has been about personal factors. We will just comment briefly on the problem, the proof, and how to tell if a proof has problems.

The Problem

Number theory is hard because addition and multiplication do not play well together. Adding numbers is not too complex by its self; multiplication by its self is also not too hard. For those into formal logic the theory of addition for example is decidable. So in principle there is no hard problem that only uses addition. None. A similar point follows for multiplication.

But together addition and multiplication is hard. Of course Kurt Gödel proved that the formal theory of arithmetic is hard. It is not complete, for example. There must be statements about addition and multiplication that are unprovable in Peano Arithmetic.

The ABC conjecture states a property that is between addition and multiplication. Suppose that

\displaystyle  A + B = C,

for some integers {1 \le A \le B \le C}. Then

\displaystyle  C \le ABC

is trivial. The ABC conjecture says that one can do better and get

\displaystyle  C \le F(ABC),

for a function {F(X)} that is sometimes much smaller than {X}. The function {F(X)} depends not on the size of {X} but on the multiplicative structure of {X}. That is the function depends on the multiplicative structure of the integers. Note, the bound

\displaystyle  C \le ABC

only needed that {A,B,C} were numbers larger than {1}. The stronger bound

\displaystyle  C \le F(ABC),

relies essentially on the finer structure of the integers.

Roughly {F(X)} operates as follows: Compute all the primes {p} that divide {X}. Let {Q} be the product of all these primes. Then {F(X) \le Q^{2}} works:

\displaystyle  C \le Q^{2}.

The key point is: Even if {p^{100}}, for example, divides {X}, we only include {p} in the product {Q}. This is where the savings all comes from. This is why the ABC conjecture is hard: repeated factors are thrown away.

Well not exactly, there is a constant missing here, the bound is

\displaystyle  C \le \alpha Q^{2}

where {\alpha>0} is a universal constant. We can replace {Q^{2}} by a smaller number—the precise statement can be found here. This is the ABC conjecture.

The point here is that in many cases {F(ABC)} is vastly smaller than {ABC} and so that inequality

\displaystyle  C \le F(ABC),

is much better than the obvious one of

\displaystyle  C \le ABC.

For example, suppose that one wishes to know if

\displaystyle  5^{z} = 2^{x} + 3^{y},

is possible. The ABC conjecture shows that this cannot happen for {z} large enough. Note

\displaystyle  F(2^{x} 3^{y} 5^{z}) = 30

for positive integers {x,y,z}.

Is He Correct?

Eight years ago Mochizuki announced his proof. Now it is about to be published in a journal. He is famous for work in part of number theory. He solved a major open problem there years ago. This gave him instant credibility and so his claim of solving the ABC conjecture was taken seriously.

For example, one of his papers is The Absolute Anabelian Geometry of Canonical Curves. The paper says:

How much information about the isomorphism class of the variety {X} is contained in the knowledge of the étale fundamental group?

A glance at this paper shows that it is for specialists only. But it does seem to be math of the type that we see all the time. And indeed the proof in his paper is long believed to be correct. This is in sharp contrast to his proof of the ABC conjecture.

Indicators of Correctness

The question is: Are there ways to detect if a proof is (in)correct? Especially long proofs? Are there ways that rise above just checking the proof line by line? By the way:

The length of unusually long proofs has increased with time. As a rough rule of thumb, 100 pages in 1900, or 200 pages in 1950, or 500 pages in 2000 is unusually long for a proof.

There are some ways to gain confidence. Here are some in my opinion that are useful.

  1. Is the proof understood by the experts?

  2. Has the proof been generalized?

  3. Have new the proofs been found?

  4. Does the proof have a clear roadmap?

The answer to the first question (1) seems to be no for the ABC proof. At least two world experts have raised concerns—see this article in Quanta—that appear serious. The proof has not yet been generalized. This is an important milestone for any proof. Andrew Wiles famous proof that the Fermat equation

\displaystyle  x^{p} + y^{p} = z^{p},

has no solutions in integers for {xyz \neq 0} and {p \ge 3} a prime has been extended. This certainly adds confidence to our belief that it is correct.

Important problems eventually get other proofs. This can take some time. But there is almost always success in finding new and different proofs. Probably it is way too early for the ABC proof, but we can hope. Finally the roadmap issue: This means does the argument used have a nice logical flow. Proofs, even long proofs, often have a logic flow that is not too complex. A proof that says: Suppose there is a object {X} with this property. Then it follows that there must be an object {Y} so that {\dots} Is more believable than one with a much more convoluted logical flow.

Open Problems

Ivan Fesenko of Nottingham has written an essay about the proof and the decision to publish. Among factors he notes is “the potential lack of mathematical infrastructure and language to communicate novel concepts and methods”—noting the steep learning curve of trying to grasp the language and framework in which Mochizuki has set his proof. Will the decision to publish change the dynamics of this effort?

Research at Home

April 1, 2020


An idea for human-interest interviews

Pixabay free src

Dr. Lofa Polir is, like many of us, working from home. When we last wrote about her two years ago, she had started work for the Livingston, Louisiana branch of LIGO. They sent her and the rest of the staff home on March 19 and suspended observations on the 26th. Since Polir’s duties already included public outreach, she is looking to continue that online.

Today we helped Dr. Polir interview another pandemic-affected researcher.

We liked her idea of interviewing young people just starting their careers, who are facing unexpected uncertainties. Her first choice was a new graduate of Cambridge University doing fundamental work related to LIGO. Unfortunately, he had been unable to install a current version of Zoom on his handheld device, or maybe afraid owing to security issues. So she requested the special equipment we have used to interview people in the past.

He replied at the speed of light that he was willing to do the interview so long as we respected some privacy measures. As for what name to use, he said we could just call him Izzy—Izzy Jr., in fact. So Dick, I, and Dr. Polir all used our own Zoom to port into our machine’s console room. The connection worked right away as Izzy’s head glimmered into view.

Starting The Interview

At first glimpse, all we could see was his long, light-brown hippie hair. This really surprised us—not the image we had of Cambridge—and we gasped about it before even saying hello. He replied that it was fashion from the Sixties. We asked how his family was doing and he said his fathers had passed on but mother and young siblings were at home and fine. We think he said “fathers” plural—the machine rendered him in a drawl like Mick Jagger and he was hard to follow.

Izzy picked up on our discomfort and immediately assured us he hadn’t been doing any drugs: “You can’t get them anyway because they’re all being diverted to treat the sick.” But he did open up to us that he was in some kind of withdrawal. He confessed that he had resorted to looking at the sun with one eye. “It was ecstasy but bad—I still can see only reds and blues with that eye, and I need to use an extra-large rectangular cursor to read text.” We were curious what brand of handheld device he was using because of his problems with Zoom, and he told us it was a Napier 1660 by Oughtred, Ltd. We hadn’t heard of that model but he said he’d connected three of them into a good home lab setup.

We asked how he was coping with distance teaching, but he said he hadn’t yet started his faculty position at Trinity College. We were surprised to learn that lecture attendance at Cambridge University is optional. “I shall be required to give the lectures but nobody will come to them so that’s all the same now—at least here I’ll have a cat for audience. No dogs and not my mother or siblings—I’d sooner burn the house down.” He quickly added, “Oh, my mother and I get along fine now and I love playing teatime with my little sisters.”

We really didn’t want to go into Izzy’s personal life, and I tried to shift the small-talk by noting a little chess set on a shelf behind him. He snapped that he shouldn’t have spent money on it and he was a poor player anyway. We thought, wow, either this guy’s really down on himself or the cabin fever of the pandemic is getting to him. So Dick, always quick to pick up on things and find ways of encouragement, said:

“Dr. Polir here works on gravity and we’re told you have some great new ideas about it. We’d love to hear them.”

“Yes, I do—or did. But something happened yesterday that is making me realize that it’s all wrong, rubbish really…”

In the Garden

Izzy started by explaining that it’s a basic principle of alchemy that all objects have humors that can manifest as kinds of magnetism. (“Alchemy”? did we hear him right?) If you realize that the Earth and Sun are objects just like any other then you can model gravity that way. You just need to assign each object a number called its “mass” and then you get the equation

\displaystyle  F = G \frac{m_1 m_2}{r^2}

for the force of attraction, where {r} is the distance between the objects with masses {m_1,m_2} and {G} is a constant that depends on your units.

“We understand all that,” said Dr. Polir.

Izzy said the point is that {G} depends only on your units and is the same regardless of where you are on Earth or on the Moon or wherever. It is very small, though. Then he went into his story of yesterday.

“I was in our garden by the path to the neighbor’s farm. I was supposed to be watching my little brother Benjamin who wanted to help harvest squash but I hate farming so I let him go without me. I was lying under an apple tree for shade when an apple fell and I realized all my mistakes.”

“What?,” we thought silently. We didn’t need to speak up—Izzy launched right into his litany of error:

“First, I’d thought the force was in what made the apple fall, but that’s nonsense. The apple would fall naturally because down is the shortest path it would be on if the tree branch were not holding it back. The only force is the tensile strength of the branch which was restraining it. I think that the tensile force really is magnetism, by the way.”

“Second, it’s ridiculous to think the force is coming from the Earth. On first principles, it could come from the ground, but that’s not what the equations say. They could have it all coming from one point in the center of the Earth. Just one point—four thousand miles deep!”

“Third and worst, though, is when you apply it to the Sun and the Earth. My equation means they are exerting force on each other instantaneously. But they are millions of miles apart. Whereas, the tree was touching the apple. Force can work only by touch, not by some kind of spooky action at a distance.”

We realized what he was driving at. Dick again always likes to encourage, so he said:

“But the math you developed for this force theory—surely it is good for calculations…?”

“No it’s not—it’s the Devil’s own box. I can calculate two bodies—the Earth and the Sun, or the Moon and the Earth if you suppose there is no Sun, but as soon as you have all three bodies it’s a bog. Worst of all, I can arrange five bodies so that one of them gets accelerated to infinite velocity—in finite time. This is a clear impossibility, a contradiction, so by modus tollens… it can all go in the bin.”

We didn’t think it would help to tell him that his math was good enough to calculate a Moon landing but not to locate a friend’s house while driving. He supplied his own coup-de-grâce anyway:

“And even the two-body calculations are tainted. I can calculate the orbits of the planets but the equations I get aren’t stable. I would wind up having to postulate something like God keeps the planets on their tracks. Yes, you need an intelligent Agent to start the planets going—all in one plane, basically—but to need such intervention all the time defeats the point of having equations.”

Inklings

We asked Izzy what he was going to do. He said that the one blessing of enforced solitude is that one gets time to reflect on things and deepen the foundations. And he said he’d had an idea later that afternoon.

“Toward supper I realized I needed to get Benjamin home. The path to the farm is straight except it goes over a mound. I was sauntering along and when I got to the hill I realized that if I didn’t watch it I’d have fallen right into it. So that got me thinking. First, what I thought was straight on the path was really a curve—the Earth is after all a ball. We think space is straight, but maybe it too is curved. So when I’m standing here, perhaps I would really be moving in a diagonally down direction, but the Earth is stopping me. The Irish blessing says, ‘may the road rise up to meet you.’ Perhaps it does.”

“So are you doing math to work that out?,” I ventured.

“I started after supper. One good thing is that it allows light to be affected by gravity—which I was already convinced of—even if light has no mass. But a problem is that it appears Time would have to be included as curved. That does not make sense either.”

We asked when he might write up all this. He said he didn’t want to be quick to publish something so flawed on the one hand, or incomplete on the other, “unless someone else be about to publish the same.” We noted that there weren’t going to be any in-person conferences to present papers at for awhile anyway.

“Besides, that’s not what I’m most eager to do. What the respite is really giving me time for is to start writing up my work on Theology. That’s most important—it could have stopped thirty years of war. For one thing, homoiousios, not homoousios, is the right rendering. There will be a time and times and the dividing of times in under 400 years anyway.”

That last statement somehow did not reassure us. We thanked Izzy Jr. for the interview and he gave consent to publish it posthumously.

Open Problems

We hope that your April Fool’s Day is such as to allow a time to laugh. But also seriously, would you be interested in the idea of our interviewing people during these times? Is there anyone you would like to suggest?

Logic and Star-Free, Part Deux

March 29, 2020


A visual proof with no abstract-algebra overhead

Composite crop of src1, src2

Dominique Perrin and Jean-Éric Pin are French mathematicians who have done significant work in automata theory. Their 1986 paper “First-Order Logic and Star-Free Sets” gave a new proof that first-order logic plus the {<} relation characterizes star-free regular sets.

Today we present their proof in a new visual way, using “stacked words” rather than their “marked words.” We also sidestep algebra by appealing to the familiar theorem that every regular language has a unique minimal deterministic finite automaton (DFA).
Read more…

Star-Free Regular Languages and Logic

March 21, 2020


Part 1 of a two-part series

Daniel Winton is a graduate student in mathematics at Buffalo. He did an independent study with me last semester on descriptive complexity.

Today we begin a two-part series written by Daniel on a foundational result in this area involving first-order logic and star-free languages.

Read more…

Leprechauns Stay Home

March 17, 2020


Stay safe, everyone

Cropped from Floss Dance source

Neil L. is a Leprechaun. He has visited me once every year since I started GLL. I had never seen a leprechaun before I began the blog—there must be some connection.

Today, Ken and I want to share the experiences we had with him on this morning of St. Patrick’s Day.
Read more…

Group Testing For The Coronavirus

March 12, 2020


Plus other mathematical ideas that may be helping

History of Econ. Thought src

Robert Dorfman was a professor of political economy at Harvard University, who helped create the notion of group testing.

Today Ken and I discuss this notion and its possible application to the current epidemic crisis. We also discuss other mathematical aspects that have clear and immediate value. Update 03/19/20: Israel Cidon in a comment links to an actual implementation of group testing for the virus up to 64 samples from the Technion.
Read more…

The Virtue of Closed Problems

March 8, 2020


A new condition in property testing

Composite crop of src1, src2

Maryam Aliakbarpour and Sandeep Silwal are PhD students at MIT. They have a joint paper titled, “Testing Properties of Multiple Distributions with Few Samples.” Aliakbarpour is advised by Ronitt Rubinfeld. Silwal has a different advisor, Piotr Indyk. Could we test which advisor is better by sampling? Haha, not a chance…

Today we will discuss this paper as an example of the power of computer science theory.
Read more…