Finding the First Trillion Congruent Numbers 94
eldavojohn writes "First stated by al-Karaji about a thousand years ago, the congruent number problem is simplified to finding positive whole numbers that are the area of a right triangle with rational number sides. Today, discovering these congruent numbers is limited only by the size of a computer's hard drive. An international team of mathematicians recently decided to push the limits on finding congruent numbers and came up with the first trillion. Their two approaches are outlined in detail, with pseudo-code, in their paper (PDF) as well as details on their hardware. For those of you familiar with this sort of work, the article provides links to solving this problem — from multiplying very large numbers to identifying square-free congruent numbers."
Re:Why? (Score:5, Informative)
Birch-Swinnerton-Dyer (Score:5, Informative)
Among other issues, which numbers are congruent numbers is deeply related to the Birch-Swinnerton-Dyer conjecture which is a major open problem http://en.wikipedia.org/wiki/Birch_and_Swinnerton-Dyer_conjecture [wikipedia.org]. This is due to a theorem which relates whether a number is a congruent number or not to the number of solutions of certain ternary quadratic forms.
The summary isn't quite accurate in that regard: The problem of finding congruent numbers is not completely solved. If BSD is proven then we can reasonably call the question solved. But it doesn't look like there's much hope for anyone resolving BSD in the foreseeable future. There's also hope that the data will give us further patterns and understanding of ternary quadratic forms and related issues which show up in quite a few natural contexts (such as Julia Robinson's proof that first order Q is undecidable).
Terrible summary (Score:5, Informative)
FtFP (From the F***ing Paper):
We report on a computation of congruent numbers, which subject to the Birch and Swinnerton-Dyer conjecture is an accurate list up to 10^12.
Slight correction (Score:5, Informative)
I don't believe they found the first trillion congruent numbers; rather, they tested the first trillion whole numbers for congruency.
Great work demonstrating important algorithms! (Score:2, Informative)
This is a fantastic piece of work by some of the leading computational number theorists today. Most of the authors are involved in the Sage [sagemath.org] project in some form or another and their algorithms and code are driving the cutting edge of the field. Great work guys!!
Re:Why? (Score:1, Informative)
Re:Terrible summary (Score:3, Informative)
For anybody who's curious... (Score:3, Informative)
I had to look up congruent numbers to make sense of the definition in TFS (I was thinking the "sides" of a right triangle meant only base and height, instead of all 3 sides of a triangle... needless to say this didn't make sense).
So, for the mathematically inclined, here's an explanation with as little English as possible.
Find all positive integers (1/2)bh where b, h, and sqrt(b^2 + h^2) are rational numbers.
They found all such integers = 10^16 (up to 1 trillion), not the first trillion such integers (as is incorrectly claimed). The reason for this error was that the article claims they used an algorithm to determine whether a number is congruent, then tested the first trillion numbers (some of them were congruent, some were not).
Re:Why? (Score:3, Informative)
Strictly speaking, there aren't any seriously new methods of multiplying numbers here; even the techniques they use for handling multiplicands larger than the computer's memory (sectional FFTs, using the Chinese Remainder Theorem to solve the problem by reducing modulo a lot of small primes) are pretty well-established from things like computations of pi, with this group offering a few improvements to the core ideas. What they did provide, and what sounds particularly promising, is a library (judging from the article, likely even open-source) for handling bignums like this that they've made available for general use. It'll be interesting to see if anyone else picks up this ball and runs with it.
Re:Terrible summary (Score:3, Informative)
Hmm, that's correct. Today, in fact. I didn't realize.
However, this PDF [cms.math.ca] (the top result for Al-Karaji congruent -trillion [google.com]) does support the edit:
Re:Why? (Score:2, Informative)
It is an *open problem* to show that there exists algorithm at all to decide whether a given integer N is a congruent number. Full stop. It's not a question of speed, or even skipping previous integers. We simply don't even know that it is possible to decide whether or not integers are congruent numbers. However, if the Birch and Swinnerton-Dyer conjecture is true (which we don't know), then there is an algorithm.