Not so easy ABCs

Number theory is notorious for producing conjectures that are easy to state but difficult to resolve. The Fermat theorem, stated in 1637—by Fermat, of course, in the margin of his copy of Diophantus’ Arithmetica—, requires nothing but a knowledge of basic arithmetic to comprehend fully. It was proved (by Andrew Wiles, building on the work of dozens of predecessors) only in 1995. The Goldbach conjecture (that every even number is the sum of two primes) and the twin primes conjecture (that there are infinitely many pairs of prime numbers p, q such that p + 2 = q), stated long ago, remain open.

A newer conjecture of this sort is the “ABC” conjecture. It has been a topic of excitement among mathematicians lately because a mathematician has made a credible claim to have proved it—but by idiosyncratic methods that other mathematicians will have to master before they can evaluate the proof. Proving it, moreover, would resolve a number of other outstanding problems in number theory.

▶ See the Wikipedia entry for more; see also Michael Nielsen’s very helpful page and list of references. I should note that of the news stories he refers to, the best is that from Nature; the New Scientist story should be ignored.)

In what follows I will describe in elementary terms the conjecture and its mathematical significance. The methods used by Shinichi Mochizuki in his claimed proof are very far from elementary. I won’t discuss them; follow the links if you want to know more. In a future post I will consider some philosophical questions suggested by the theorem and its proof.

Divisors and primes

An integer is a “whole number”, with a + or - in front: e.g. +3, –17. Mostly we omit the +. Many mathematical objects other than integers are called “numbers” of one sort or another; nevertheless I will use the term “number” for “integer” if no confusion will arise from doing so. If a, b, c are numbers such that a · b = c, then a and b are factors or divisors of c. Notice that since a · 1 = a for every number a, every number has at least two divisors.

A divisor of a other than a itself and 1 is a proper divisor. Some numbers have many proper divisors—48, 36, 120, 144, 168—and some have none at all. Every proper divisor of a number a must be no larger than a divided by 2 (because 2 is the smallest proper divisor, and because if a · b = c, then the larger a is, the smaller b must be). If a number has many proper divisors, those divisors will mostly have to be much smaller than the number itself (check the numbers I just listed).

A prime number is a “multiplicative atom”: it has no proper factors (the number 1, which divides every number, and the number itself, are divisors but not proper divisors). 14 = 2 · 7 is not prime, but 2 and 7 are.

Every number, prime or not, can be generated from powers of primes: for example, 144 = 2·2·2·2·3·3 = 24 · 32. The multiplicative structure of the integers—that is, which numbers divide which—is completely determined by the primes.

A set of numbers is said to be coprime (or “relatively prime”) if the numbers have no common divisors other than 1. The set 2,3,35 is coprime; the set 2,3,6 is not.

The set of primes is of course entirely determinate.

Plus and times

Integers can also be added as well as multiplied. The additive structure of the integers is much easier to specify. For example, 9 = 8 + 1 = 7 + 2 = 6 + 3 = 5 + 4; notice that I constructed the list simply by counting down from 9; I can stop at 5 because the remaining sums, e.g. 3 + 6, have already been accounted for, given that + is commutative (i.e. p + q = q + p for all numbers p, q).

The list of all the summands of a number, unlike the list of divisors, is not very exciting, because it can be completely described even in advance of knowing which number you want the summands of: in every instance it is the list of all the numbers greater than or equal to 1 and less than that number. Finding the divisors of (also called factoring), a large number, on the other hand, is a difficult problem, so difficult that systems of cryptography which can be broken only by factoring very large numbers (with several hundred digits) are regarded as extremely secure.

One might well wonder—as mathematicians have for centuries—what relations there might be between the two basic algebraic structures of the integers, the additive and the multiplicative. In particular, could knowing algebraic facts about the summands of a number—facts relatively easy to discover—yield information about its list of divisors?

The ABC conjecture says that it can. A little technical machinery is needed in order to state the conjecture.

Exponents and the radical of a number

Every integer, as I’ve said, can be factored (and factored uniquely) into a product of primes. 24 = 23 · 31, 60 = 22 · 31 · 51. (If you’ve studied Gödel’s proof, you may remember that Gödel took advantage of unique factorization to encode the propositions of a simple version of arithmetic into the integers in such a way that from the code one can recover the proposition encoded.)

Notice that the integer, written as a product of primes, consists of a list of primes, each of which has a exponent indicating how many times it occurs in the product. For some integers that list is lengthy, for other it has only one entry: 2310 = 21 · 31 · 51 · 71 · 111, 2048 = 211. In what follows, if the exponent is 1, I will omit it.

Now for the technical machinery. Suppose we have factored a number into prime powers. We have a more or less lengthy list of primes with exponents attached to them. Change all the exponents to 1 (or, equivalently, erase them). Call the resulting product the radical of your original number. The radical of 2310 is 2310 itself; the radical of 2048 is 2. (A little thought will show that these are the extreme cases: the radical of a number is never larger than that number itself, and never less than 2.)

Distinct numbers can have the same radical: by erasing the exponents, we are “losing information” about our original number, and therefore “confusing” it with all the other numbers that have the same prime divisors. The radical of 24 is 2 · 3, the radical of 144 is also 2 · 3. Indeed to every given radical, there will correspond infinitely many numbers.

Very large numbers, as one can see from the example of 2048, can have small radicals. (The smallest possible radical, as I said, is 2.) The radical of a number will be greatest in relation to that number if in its prime factorization no prime occurs with exponent other than 1. The radical of 30 = 2 · 3 · 5 is 30 itself, but the radical of 180 = 22 · 32 · 5 is also 30.

The ABC conjecture

Now the conjecture. It concerns triples a, b, c of numbers such that a + b = c, with a, b, c coprime. That entails that the list of prime divisors of a includes nothing from the list of prime divisors of b, and similarly for a and c and for b and c. Example: 11 + 16 = 27 (16 = 24, 27 = 33). We consider the radical, call it R, of the product a · b · c (in the example it is 11 · 2 · 3 = 66). The conjecture says that R is “almost always” greater than c (as it is in the example: 66 > 27).

Consider some cases.

4 + 127 = 131.
Here R = 2 · 127 · 131, which is of course greater than 131.

3 + 125 = 128.
Here R = 3 · 5 · 2 (because 125 = 53, and 128 = 27, so abc here is 3 · 53 · 27—now erase the exponents to get R). But 3 · 5 · 2 is just 30, and so c = 128 is greater than R.

Notice that in the second example b and c have small divisors raised to “large” powers, which forces their radicals to be much smaller than b and c themselves. One would expect such numbers to be rather sparse (in a sense that needs to be made precise). The powers of 2 increase exponentially, leaving more and more space between them, and it would seem that the products of large powers of primes—numbers like 144 or 480—will likewise have more and more space between them as the exponents increase.

Multiples of 2, 3, and 5 up to 640. These are numbers with relatively small radicals (≤ 2 · 3 · 5 = 30, in fact). Notice that they thin out. The apparent density of the rightmost column is an artifact of the construction of the grid (which is 20 = 4 · 5 squares wides), and so I have de-emphasized it.

The conjecture says, in effect, that products of large powers of primes are sparse indeed. More precisely:

Let α be a small decimal number like .01 or .00003. Given an integer a, the number a1 + α = (by definition) a1 · aα will be a number (usually not an integer) not much larger than a itself. For example, if α = .01 then 21 + α is 2.0139 (approximately).

Then according to the conjecture, for every α greater than zero, there are only finitely many triples of coprime integers a, b, c, such that

a + b = c

and (letting R again denote the radical of the product abc)

c > R 1 + α

That c is greater than the radical R of the product a · b · c (or greater than a number R 1 + α slightly larger than R) means that c (and perhaps b and a also) has just a few prime factors, most of which are raised to large powers—as in the case where a, b, c are 3, 125, and 128. If the conjecture holds, then even though there are in fact infinitely many cases of coprime triples a, b, c such that

a + b = c

c > R = the radical of a · b · c

(see the Wikipedia article), nevertheless if for each triple we replace R by an even slightly larger number, say R′ = R 1 + α with α as close to zero as you please (R′ will vary with the triple a, b, c, just as R itself does),

then in only finitely many cases will we have coprime triples a, b, c satisfying

a + b = c

and

c > R′.

The ABC conjecture (or perhaps now the ABC theorem) tells us something about the relation of the additive and multiplicative structures of the integers, and more precisely about the sparseness of integers whose prime factors are raised to large exponents (since those are the integers whose radicals are relatively small compared to the integers themselves) and which are the sums of integers of the same sort (remember the case a, b, c = 11, 16, 27 for which c = 27 is less than R = 66 owing to the large prime factor 11 of a = 11, and compare this with the case a, b, c = 3, 125, 128).

Among the consequences of the ABC conjecture is a generalization of Catalan’s conjecture (now a theorem, since it was proved in 2002 by Preda Mihăilescu)—and so, of course, Catalan’s conjecture itself. Catalan, a nineteenth-century mathematician now best known for the series of numbers named after him, conjectured in 1844 that although

2 3 + 1 = 3 2,

no other powers of numbers differ by 1. (A close call was noted above: 5 3 + 3 = 27, but as always in number theory, “close” doesn’t count, and quite often provides no help in solving the problem. You could of course define “close” precisely, and then state a generalization of Catalan’s conjecture to the effect that prime powers tend not to be close to other prime powers…)

The ABC conjecture doesn’t immediately entail that the equation

p m + 1 = q n

has only one solution. But it does entail that the equation has only finitely many solutions (in fact it entails a stronger claim, the Fermat-Catalan conjecture).