There has been a lot of recent interest in the abc conjecture, since the release a few weeks ago of the last of a series of papers by Shinichi Mochizuki which, as one of its major applications, claims to establish this conjecture. It’s still far too early to judge whether this proof is likely to be correct or not (the entire argument encompasses several hundred pages of argument, mostly in the area of anabelian geometry, which very few mathematicians are expert in, to the extent that we still do not even have a full outline of the proof strategy yet), and I don’t have anything substantial to add to the existing discussion around that conjecture. (But, for those that are interested, the Polymath wiki page on the ABC conjecture has collected most of the links to that discussion, and to various background materials.)
In the meantime, though, I thought I might give the standard probabilistic heuristic argument that explains why we expect the ABC conjecture to be true. The underlying heuristic is a common one, used throughout number theory, and it can be summarised as follows:
Heuristic 1 (Probabilistic heuristic) Even though number theory is a deterministic subject (one does not need to roll any dice to factorise a number, or figure out if a number is prime), one expects to get a good asymptotic prediction for the answers to many number-theoretic questions by pretending that various number-theoretic assertions (e.g. that a given number is prime) are probabilistic events (with a probability that can vary between and ) rather than deterministic events (that are either always true or always false). Furthermore:
- (Basic heuristic) If two or more of these heuristically probabilistic events have no obvious reason to be strongly correlated to each other, then we should expect them to behave as if they were (jointly) independent.
- (Advanced heuristic) If two or more of these heuristically probabilistic events have some obvious correlation between them, but no further correlations are suspected, then we should expect them to behave as if they were conditionally independent, relative to whatever data is causing the correlation.
This is, of course, an extremely vague and completely non-rigorous heuristic, requiring (among other things) a subjective and ad hoc determination of what an “obvious reason” is, but in practice it tends to give remarkably plausible predictions, some fraction of which can in fact be backed up by rigorous argument (although in many cases, the actual argument has almost nothing in common with the probabilistic heuristic). A famous special case of this heuristic is the Cramér random model for the primes, but this is not the only such instance for that heuristic.
To give the most precise predictions, one should use the advanced heuristic in Heuristic 1, but this can be somewhat complicated to execute, and so we shall focus instead on the predictions given by the basic heuristic (thus ignoring the presence of some number-theoretic correlations), which tends to give predictions that are quantitatively inaccurate but still reasonably good at the qualitative level.
Here is a basic “corollary” of Heuristic 1:
Heuristic 2 (Heuristic Borel-Cantelli) Suppose one has a sequence of number-theoretic statements, which we heuristically interpet as probabilistic events with probabilities . Suppose also that we know of no obvious reason for these events to have much of a correlation with each other. Then:
- If , we expect only finitely many of the statements to be true. (And if is much smaller than , we in fact expect none of the to be true.)
- If , we expect infinitely many of the statements to be true.
This heuristic is motivated both by the Borel-Cantelli lemma, and by the standard probabilistic computation that if one is given jointly independent, and genuinely probabilistic, events with , then one almost surely has an infinite number of the occuring.
Before we get to the ABC conjecture, let us give two simpler (and well known) demonstrations of these heuristics in action:
Example 1 (Twin prime conjecture) One can heuristically justify the twin prime conjecture as follows. Using the prime number theorem, one can heuristically assign a probability of to the event that any given large integer is prime. In particular, the probability that is prime will then be . Making the assumption that there are no strong correlations between these events, we are led to the prediction that the probability that and are simultaneously prime is . Since , the Borel-Cantelli heuristic then predicts that there should be infinitely many twin primes.
Note that the above argument is a bit too naive, because there are some non-trivial correlations between the primality of and the primality of . Most obviously, if is prime, this greatly increases the probability that is odd, which implies that is odd, which then elevates the probability that is prime. A bit more subtly, if is prime, then is likely to avoid the residue class , which means that avoids the residue class , which ends up decreasing the probability that is prime. However, there is a standard way to correct for these local correlations; see for instance in this previous blog post. As it turns out, these local correlations ultimately alter the prediction for the asymptotic density of twin primes by a constant factor (the twin prime constant), but do not affect the qualitative prediction of there being infinitely many twin primes.
Example 2 (Fermat’s last theorem) Let us now heuristically count the number of solutions to for various and natural numbers (which we can reduce to be coprime if desired). We recast this (in the spirit of the ABC conjecture) as , where are powers. The number of powers up to any given number is about , so heuristically any given natural number has a probability about of being an power. If we make the naive assumption that (in the coprime case at least) there is no strong correlation between the events that is an power, is an power, and being an power, then for typical , the probability that are all simultaneously powers would then be . For fixed , the total number of solutions to the Fermat equation would then be predicted to be
(Strictly speaking, we need to restrict to the coprime case, but given that a positive density of pairs of integers are coprime, it should not affect the qualitative conclusion significantly if we now omit this restriction.) It might not be immediately obvious as to whether this sum converges or diverges, but (as is often the case with these sorts of unsigned sums) one can clarify the situation by dyadic decomposition. Suppose for instance that we consider the portion of the sum where lies between and . Then this portion of the sum can be controlled by
which simplifies to
Summing in , one thus expects infinitely many solutions for , only finitely many solutions for (indeed, a refinement of this argument shows that one expects only finitely many solutions even if one considers all at once), and a borderline prediction of there being a barely infinite number of solutions when . Here is of course a place where a naive application of the probabilistic heuristic breaks down; there is enough arithmetic structure in the equation that the naive probabilistic prediction ends up being an inaccurate model. Indeed, while this heuristic suggests that a typical homogeneous cubic should have a logarithmic number of integer solutions of a given height , it turns out that some homogeneous cubics (namely, those associated to elliptic curves of positive rank) end up with the bulk of these solutions, while other homogeneous cubics (including those associated to elliptic curves of zero rank, including the Fermat curve ) only get finitely many solutions. The reasons for this are subtle, but certainly the high degree of arithmetic structure present in an elliptic curve (starting with the elliptic curve group law which allows one to generate new solutions from old ones, and which also can be used to exclude solutions to via the method of descent) is a major contributing factor.
Below the fold, we apply similar heuristics to suggest the truth of the ABC conjecture.
— 1. The ABC conjecture —
The ABC conjecture asserts that for every , one has
whenever are coprime natural numbers, and is the product of all the primes dividing . Since are coprime, , and an equivalent formulation of the conjecture is as follows: if are real numbers with , then for sufficiently large , there does not exist any solution to the equation with (say), coprime, and
Indeed, one can deduce the former version of the ABC conjecture from the latter by using a finite mesh of triples with spacing equal to small multiple of ; we leave the details to the interested reader.
We can now try to randomly find counterexamples to the abc conjecture as follows:
- Pick a large (say, a power of two).
- Pick coprime squarefree numbers , , .
- Pick numbers with with comparable to .
- Check if .
Steps 1, 2, and 4 are easy to apply probabilistic heuristics to. For Step 3, we need the following lemma, reminiscent of the classical divisor bound:
Lemma 3 Let be a square-free integer. Then there are at most integers less than with radical .
Proof: Factorise . We are trying to establish the bound , where is the number of numbers less than which are divisible by but by no other primes, that is to say they lie in the set . To do this, it is convenient to work with Dirichlet series, and specifically with the sum
for some parameter to be optimised in later. On the one hand, this expression is at least . On the other hand, we have the factorisation
We crudely bound
for some depending only on , using the trivial bound and the geometric series formula, leading to
On the other hand, since
we see from the prime theorem (which gives a lower bound on the sum of the logarithms of the first primes, which in turn lower bounds ) that
and so
for any fixed ; as can be arbitrarily small, the claim follows.
Now we can run the probabilistic heuristics. After selecting as a large power of two in Step 1, we have choices for in Step 2. By the above lemma, for each , there are choices for that are of magnitude , and assuming (in the case when are coprime) that there is no prior correlation between and , which we think of as being randomly distributed amongst the numbers of size , the probability that should be of order . This leads to a total probability of ; since , this sum is convergent (for ranging over powers of ), so we expect only finitely many counterexamples, thus supporting the ABC conjecture.
Remark 1 In the case of , the naive heuristic prediction was incorrect, basically because of the algebraic structure in the Fermat curve (which, among other things, is an elliptic curve and thus enjoys a group law). In the case of the general equation, though, no analogous algebraic structure appears to be present. So there is no obvious correlation here. (Of course, this does not rule out the possibility of a much less obvious correlation; this is one of the reasons why the above arguments are only heuristic, and fall well short of a rigorous proof of anything.)
42 comments
Comments feed for this article
18 September, 2012 at 5:01 pm
The probabilistic heuristic justification of the ABC conjecture « Guzman's Mathematics Weblog
[…] The probabilistic heuristic justification of the ABC conjecture. Share this:FacebookTwitterRedditStumbleUponTumblrDiggLinkedInPinterestEmailPrintLike this:LikeBe the first to like this. […]
18 September, 2012 at 5:51 pm
Will Sawin
The equation x^3=y^3+z^3 is an elliptic curve, as are slight perturbations of it. Some of these curves have finitely many rational points and some have infinitely many. Can we build a probabilistic heuristic that suggests this ambiguity?
18 September, 2012 at 6:11 pm
Terence Tao
This is a very delicate question (essentially that of understanding the rank of a typical elliptic curve), as the objects involved have a very rich algebraic structure, and the crude analytic heuristics given here only give a zeroth order approximation at best; also, deep conjectures such as BSD become relevant. There are a number of surveys on this topic, see e.g. this one by Rubin and Silverberg, or this one by Bektemirov, Mazur, Stein and Watkins.
ADDED LATER: The crude heuristics mentioned in the post, though, do support the fact that a “typical” cubic curves should a logarithmic number of integer points at a given height, or equivalently that a “typical” elliptic curves have a logarithmic number of rational points at a given height. This is consistent with the algebraic heuristics that suggest that the rank of a typical elliptic curve is typically zero or one.
18 September, 2012 at 6:33 pm
Will Sawin
Well I guess one can say that the group law induces an obvious correlation between the existence of rational points in different regions. Similarly, in the other case where the “actual” algebraic results give (much easier to resolve) ambiguity, which is affine conics, there is also a group law to provide correlation. This “explains” the failure of crude heuristics.
19 September, 2012 at 5:01 am
Wednesday Highlights | Pseudo-Polymath
[…] Probability and number theory. […]
19 September, 2012 at 5:01 am
Stones Cry Out - If they keep silent… » Things Heard: e238v3
[…] Probability and number theory. […]
19 September, 2012 at 10:31 am
Tao on the ABC Conjecture « Pink Iguana
[…] What’s New, The probabilistic heuristic justification of the ABC conjecture, here. There has been a lot of recent interest in the abc conjecture, since the release a few weeks ago […]
19 September, 2012 at 5:36 pm
The abc conjecture and its consequences « Fight with Infinity
[…] T.Tao The probabilistic heuristic justification of the ABC conjecture […]
20 September, 2012 at 11:42 pm
William Schlieper
I think that there’s a slight error in the Fermat’s Last Theorem derivation for n=3, as the elements of the ring have only two degrees of freedom, not three, as
21 September, 2012 at 8:14 am
Terence Tao
Ugh, you’re right, that argument is in fact incorrect (even when one takes the factorisation in into account, the probabilistic heuristic still suggests a logarithmic number of solutions). It appears that it is instead the group law for elliptic curves (
and for singular cubic curvessuch as ) which is the additional structure that is defeating the probabilistic heuristic (cf. Euler’s proof by descent of FLT for n=3, which can be interpreted in terms of this group law).21 September, 2012 at 6:05 pm
Joe Silverman
Are you using projective coordinates here? If so, then isn’t singular, it’s an elliptic curve. On a singular cubic, the non-singular points form a multiplicative group, so the number of rational points of bounded height grows even more rapidly than on elliptic curves. So it’s not just having a group law, but the kind of group, that determines how badly the heuristic fails. (Sorry for the quibble, this was a very nice post on why ABC should be true.)
[Gah, that was careless of me. Corrected now, thanks – T.]
21 September, 2012 at 8:09 am
Noname
If I apply the argument of Example 1 to the case when n, n+2, n+4 are all primes, do I also get the conclusion that there are infinitely many of them? But for any n, at least one of these three numbers must be 0 mod 3, do we get a contradiction?
21 September, 2012 at 8:16 am
Terence Tao
Yes, this is a failure of the naive Cramer heuristic in which there is no correlation between the primality of numbers such as n, n+2, and n+4, whereas in fact as you point out there are some correlations, in this case coming from the residue classes modulo 3. There is a refined heuristic to take care of this, which is discussed further in a previous blog post ( https://terrytao.wordpress.com/2008/01/07/ams-lecture-structure-and-randomness-in-the-prime-numbers/ ), which was also mentioned at the end of Example 1.
22 September, 2012 at 4:40 am
Américo Tavares
Could you please inform how does one read the symbol that appears in the conjecture? I think I understand its meaning but I don’t know
how to read it, even in my native language.
22 September, 2012 at 1:24 pm
Ruben
Much Smaller <<
22 September, 2012 at 1:33 pm
Américo Tavares
Thanks, but how do you read the dependence on ?
23 September, 2012 at 12:51 pm
Américo Tavares
I had posted essentially this question on Mathematics Stack Exchange How does one read aloud Vinogradov’s notation and ?
22 September, 2012 at 10:28 am
Envy number theorists! « Noncommutative Analysis
[…] learned from some blogs (here, here and here) that the ABC-conjecture might be solved, and also (by extrapolation) that this is a very […]
22 September, 2012 at 10:25 pm
Anonymous
Tao,
a bit misplaced, I’m sorry, but this may be of interest to you:
http://arxiv.org/pdf/1208.2473.pdf
Best,
Markus
23 September, 2012 at 2:15 am
Duvall
Markus,
the professor who posed this paper on arxiv also claims to have solved 3 Millenium problems on his web-page. I think the situation is clear now and does not require Terry’s attention.
23 September, 2012 at 10:52 am
Anonymous
any given natural number {a} has a probability about {a^{1/n – 1}} of being an {n^{th}} power
—- any natural number no larger than {a} has a probability about {a^{1/n – 1}} of being an {n^{th}} power
23 September, 2012 at 10:54 am
Anonymous
any given natural number {a} has a probability about {a^{1/n – 1}} of being an {n^{th}} power
— any given natural number no larger than {a} has a probability about {a^{1/n – 1}} of being an {n^{th}} power
23 September, 2012 at 11:20 am
Terence Tao
Well, yes, if you want to stay rigorous and treat the property of being an n^th power as a deterministic event, one has to perform an additional averaging such as the one you suggest. But for the purposes of applying the probabilistic heuristic, it is often simpler to pretend to work with a probabilistic model, where the property of being an n^th power has been replaced by a probabilistic event with a probability consistent with these averaged statistics; see Heuristic 1. While this model is of course inaccurate at the foundational level, the point of the heuristic is that it can still be remarkably accurate at the predictive level, particularly with regards to asymptotic statistics.
23 September, 2012 at 5:03 pm
Anonymous
P(for a given n-th power N, a number no larger than N is n-th power)
P(for a given n-th power N, there is a number a smaller than N is n-th power and N-a is also a N-th power)
sum (P(a is n-th power)P(N-a is n-th power)=sum(N^(1/n-1)*N^(1/n-1)=sum(1/(k^(2n-2)) (with N=k^n) so the sum is always smaller than 1 when sum from k=2 and on for any n. When n=2, it is meaningless as we know there are lots of solutions.
This is originated from that P(for a given n-th power N, there is a number a smaller than N is n-th power and N-a is also a N-th power) is not the same as P(a is n-th power)P(N-a is n-th power)
23 September, 2012 at 4:16 pm
Weekly links for September 23 « God plays dice
[…] Terry Tao has written a probablistic heuristic justification of the abc conjecture. […]
23 September, 2012 at 10:28 pm
lkafle
Reblogged this on lava kafle kathmandu nepal.
5 October, 2012 at 3:43 am
Jeff Ezearn
One particular intriguing situation that sets FLT for n=3 (as in the pythagorean case n=2) from the higher cases is an old result of Perrin from the late 19th century, that a single solution to that (cubic) fermat curve implies an infinity of other (coprime) solutions.
This reinforces the reason why the heuristic must “turn in” an infinite number of solutions for the cubic case, since (implicitly) it assumes that there’s at least one solution (i.e. some a, b and a+b being simultaneously cubic integers). In that respect (juxtaposed with Perrin’s result), the heuristic is accurate!
5 October, 2012 at 7:08 am
Jeff Ezearn
Aargh, on coming back to read I just realised that I should have said
“… (implicitly) assumes that there’s at least one PROBABLE solution…”
I had written in haste and perhaps I may give further thoughts. One may want to contrast and compare the heuristic for FLT n=3 and n>3 with Perrin’s and Falting’s theorem. i.e.
Theorem (Perrin): If Fermat curve for n=3 has one solution, then there are infinitely many (coprime) solutions
Theorem (after Falting’s): If Fermat curve for n>3 has at least one solution, then there can only be finitely many solutions.
Under these two DEFINITE results, an “accurate” heuristic should run as:
Heuristic (FLT n=3): If FLT n=3, has at least one PROBABLE counterexample (say some a, b and a+b being simultaneously cubic integers with an assumed non-zero probability), then there must be PROBABLY infinitely many other counterexamples.
Heuristic (FLT n>3): If FLT n>3 has at least one PROBABLE counterexample, then there can be PROBABLY only finitely many other counter
7 October, 2012 at 1:30 am
News on the ABC conjecture | MathBlog
[…] that I have found two blog posts discussing it, one from Terrence Tao the other from the blog Quomodocumque, and just mentioning Terrence Tao, always seems to put some […]
12 October, 2012 at 7:57 am
Martin
New amazing prime numbers spiral: http://www.youtube.com/watch?v=Dfar_AZub4Y
12 October, 2012 at 3:16 pm
James Tomson
Beal Fermat and Pythagora’s Triplets http://www.coolissues.com/mathematics/BealFermatPythagorasTriplets.htm
14 October, 2012 at 5:43 pm
The Chowla conjecture and the Sarnak conjecture « What’s new
[…] the amount that an analogous random sum would provide; cf. the probabilistic heuristic discussed in this recent blog post. There are a number of ways to make this heuristic precise. One of these is the following old […]
24 February, 2013 at 2:07 pm
John Salazar
What’s the current status of Mochizuki’s proof? Does it look like it will fly or have gaps been found that cannot be patched?
12 June, 2013 at 6:08 am
Anonymous
For a list of all known abc triples with quality > 1.4 see:
http://www.math.leidenuniv.nl/~desmit/abc/index.php?set=2
23 April, 2015 at 8:56 am
observer
Progress: https://www.maths.nottingham.ac.uk/personal/ibf/symcor.conf.html. What would be the consequences of a person of his pedigree to be wrong?
7 September, 2015 at 1:34 pm
Optimus Prime
Would be interested to see a Terry Tao update post on this theory given this post is from 2012 and the theory is still rumbling on.
29 November, 2015 at 11:21 am
ABC conjecture | fragments
[…] A probabilistic heuristic justification for the ABC conjecture can be found at this blog post. […]
8 March, 2016 at 3:25 am
Anonymous
Is there any classification of Diophantine equations which (at least in principle) can be solved by an effective version of the ABC conjecture?
16 February, 2017 at 10:50 am
Anonymous
On the Search for a Valid Proof of the famous and important abc Conjecture, please refer to the following link for details:
https://www.researchgate.net/post/What_is_the_proof_of_the_ABC_Conjecture
9 May, 2017 at 7:20 pm
Anonymous
It is possible to formulate the abc conjecture in terms of c alone by defining the following function of c
Where the minimum is over all coprime pairs (a,b) satisfying
Clearly, is well-defined for each .
The abc conjecture is equivalent to the claim that grows faster than any fractional power of . This claim may be refined by making more refined lower bound estimates on the growth rate of .
19 June, 2017 at 3:35 am
Anonymous
For a new approach (based on the theory of Shimura curves) to the abc conjecture and related problems, see Pasten’s paper
https://arxiv.org/pdf/1705.09251.pdf
9 October, 2018 at 3:01 pm
David Cole
FYI: “Searching for a proof of the ABC-conjecture”,
https://www.math10.com/forum/viewtopic.php?f=63&t=1793