MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
RSS
Logo IMG

COMPUTING SCIENCE

Calculemus!

Celebrating 25 years of celebrating computation

Brian Hayes


ABCs

My third example is another pursuit of shy, elusive mathematical objects. It concerns the simple equation a + b = c , where a , b and c are positive integers that have no divisors in common (other than 1); for example, the equation 4+5=9 qualifies under this condition.

Now for some number theory. Multiply the three numbers a, b and c , then find all the prime factors of the product. From the list of factors, cast out any duplicates, so that each prime appears just once. The product of the unique primes is called the radical of abc , or rad ( abc ). For the triple {4, 5, 9}, the product is 4×5×9=180, and the factor list is 2, 2, 3, 3, 5. Removing the duplicated 2s and 3s leaves the unique factor list 2, 3, 5, so that rad (180)=30.

In this example, c is less than rad ( abc ). Can it ever happen than c is greater than rad ( abc )? Yes: The triple {5, 27, 32} has the product 5×27×32=4,320, for which the unique primes are again 2, 3 and 5. Thus c =32 is greater than rad (4,320)=30. Triples where c exceeds rad ( abc ) are called abc -hits. As with MSTD sets, there are infinitely many of them, and yet they are rare. Among all abc triples with c ≤10,000, there are just 120 abc -hits.

If c can be greater than rad ( abc ), how much greater? It's been shown that c can exceed rad ( abc ) plus any constant or rad ( abc ) multiplied by any constant. How about rad ( abc ) raised to some power greater than 1? A conjecture formulated by Joseph Oesterlé of the University of Paris and David W. Masser of the University of Basel claims there are only finitely many exceptional cases where c > rad ( abc ) 1+ε , for any ε no matter how small. The conjecture has made the search for abc -hits more than an idle recreation. If the conjecture could be proved, there would consequences in number theory, such as a much simpler proof of Fermat's Last Theorem.

In a program to search for abc -hits the one sticky point is factoring the product abc . Factoring integers is a notorious unclassified problem in computer science, with no efficient algorithm known but also no proof that the task is hard. If you want to get serious about the search, you need to give some thought to factoring algorithms—or else latch on to code written by someone else who has done that thinking. On the other hand, for merely getting a sense of what abc -hits look like and where they're found, the simplest factoring method—trial division—works quite well.

Searchers for abc -hits can also join ABC@home ( www.abcathome.com ), a distributed computing project.



» Post Comment

 

EMAIL TO A FRIEND :

Subscribe to American Scientist