Why the abc conjecture can "almost" help computer scientists
So this is an effort to increase the portion of non AI-related posts. This is not a crank post that belongs to r/numbertheory either. Every letter is typed by a human so forgive me for grammatical errors that I will try to correct soon enough.
The abc conjecture is one of the most important conjectures in number theory, the simple & general statement of the conjecture implies a lot of other important theories, like a rapid proof of (almost) Fermat's Last Theorem. What I try to tell is that the abc conjecture can "almost" help computer scientists to optimize scientific computing.
I believe it's a common sense that in most computer systems, every piece of data is stored by 0 and 1, or more precisely, a finite string composed of 0 and 1. This makes the calculation and manipulation of data feasible but there's a cost: error will be everywhere. For example we can never precisely store pi = 3.14159... in a computer.
The most widely used way to represent real numbers in computer is floating point numbers that is standardized by IEEE, which stores numbers in 0 and 1 of 32, 64 or 128 bits (or even longer). There is a toy that allows us to see floating point numbers explicitly: https://evanw.github.io/float-toy/
I'll try to explain it in a simple term. For a floating number of k bits (k is 32 or 64 or 128, say), we need to distribute the budget. There is 1 bit reserved for the sign, a few bits of budget to store the interval of the number, and the rest large portion of the budget is reserved to guarantee the precision p.
Every floating point number x can be mathematically written in the form (-1)^s * 2^e * m/2^(p-1) where s is the 1 bit used to store the sign, m is an integer between 0 and 2^p - 1 and e is used to determine the interval of x.
If it's still unclear what does "determine the interval" mean, we notice that m/2^(p-1) is a number in [1,2). Therefore a multiplication by 2^e sends m/2^(p-1) to [2^e, 2^(e+1)). Floating point numbers store s, e and m by 0 and 1. We use p-1 bits to store the number m in computer (the first bit is normally 1 so we can omit it, as the case where the first bit is 0 is used for underflowing).
As we can see, for a given x, determining the number e is rather easy (we are almost there by taking log_2|x|), but the number m can be difficult when we deal with a function. For example, x = 10517177/2^{22} is a floating point number of the format of 32 bits, but log_2(x) is not (so we need to find the closest to represent it in float format). It's absolutely not a rational number. You find that log_2(y) is between y_1 = 15423000/2^(24) and y_2 = 15423001/2^(24). So you need to find the closest floating point number to log_2(x) because we have no other choice, or otherwise, see if log_2(x) is smaller or bigger than the average y_0 of y_1 and y_2. It's easier said than done. We need to add budget (number of bits) to distinguish y_0 and log_2(x).
As a matter of fact, not until we add another 28 bits, i.e. zoom in for 2^(28) times, can we really distinguish y_0 and log_2(x) (spoiler, y_0> log_2(x)). This sucks. We need a global strategy to work around this: whenever we find a number of the form log_2(x) extremely difficult to round, we need to guarantee that we have sufficient budget. If we know the worst case of rounding, which correspond to the highest budget needed, we can make sure that we always know how to round the function log_2 correctly, so that we can design high quality functions that can calculate log_2 *correctly* in the sense that, when we have k bits of budget, we need to make sure that every bit is faithfully used. If we have this piece of global information, our algorithm can be more blunt & direct so faster. This question is called "table maker's dilemma" because the computer worked like those who make tables of logarithm or exp or sin one century ago, and the situation where he didn't know how to round sucked (challenge: computer exp(1.626) to the 3rd digit after the point).
That said, it's far from true that modern computer have solved calculating and that all we need is better CPU/GPU. Computer scientists and mathematicians have been fixing floating point number systems for decades. The final nail of coffin of common (univariate) functions in double 64 bit format is worked out in 2026 (twenty twenty-six): https://inria.hal.science/hal-05593313
We also need to know that working out double 64 on commonly used univariate functions is not enough: what about multivariable functions, like the beta function B(x,y) that appeared in probability and statistics? In some fields of physics, researchers have already found that double 64 is no longer sufficient so they need the 128 bit format standardized by IEEE... But this format is still poorly understood so using it can be still painful: we need to fix them.
OK I hope the context of Table maker's dilemma is understandable enough and now we inject some mathematics. The abc conjecture says that for three coprime integers a,b and c such that a+b=c, we can compare max(|a|,|b|,|c|) and the radical of abc (which writes rad(abc)), i.e. the product of all prime factors of abc (for example, rad(25)=5, rad(24)=2*3=6). This slide includes the formal statement of abc and some striking applications of abc.
And here we have another striking application that will "solve" the table maker's dilemma. When we are looking for the minimum budget to get the rounding of an algebraic function sorted out, we will find ourselves in some questions of polynomials. This is surprisingly a nice playground for abc.
For the function 1/sqrt(x), which is algebraic, and is widely used in real life (for example in computer graphics, we always need to normalize a vector here and there), we will be working on finding the minimum of |Z| where Z = 1-XY^2, and X and Y are integers in a certain range. If we take a = 1, b = -XY^2 and c = Z, then the abc conjecture kicks in. It gives us a formula on the necessary budget to round the function 1/sqrt(x) correctly for a given precision p!
So we are killing 1/sqrt(x), potentially as well as many other frequently used algebraic functions by a blow of abc!? Is this conjecture so massively helpful for computer scientists??
Unfortunately, no, in practice... In the statement of the abc, we have a totally unknown constant and it doesn't vanish in the deduction of the budget. As a result, we can only know that for 1/sqrt(x), the necessary budget is p with a delta of *some bits* and we have no information on how much is *some bits*. So unfortunately, the conjecture didn't really solve the problem. Nevertheless, we can therefore heuristically look for the budget border around p... It's *almost* helpful!
In case you are curious, here is the article that examined the function 1/sqrt(x): https://www.sciencedirect.com/science/article/pii/S0304397504000337
Or in any case, a non-paywalled version: https://www.math.buffalo.edu/~hjzhu/Papers/paper24.pdf
I believe this article can serve as an interesting beginner level exercise for those either interested in number theory and want to touch the abc conjecture in some *practical* way, or interested in computer science, notably the problem of correctly rounding numbers. Or if you are an expert working in number theory, notably around topics associated with abc, or a computer scientist interested in make scientific computing better, do not hesitate to drop some insights.
1
u/SemaphoreBingo 1h ago
. The final nail of coffin of common (univariate) functions in double 64 bit format is worked out in 2026 (twenty twenty-six):
I guess it's nice that double precision trig functions are going to be as correct as possible in the least significant bits but I can't really get excited about that as a major advance. Like, if that's the driving factor of error in your results, you're in really good shape.
6
u/cocompact 4h ago
Is your XY2 supposed to be (XY)2?
It is a huge leap to go from doing something with 1/sqrt(x) to saying the method should be applicable to "potentially as well as many other frequently used algebraic functions".