typodupeerror

## Finding the First Trillion Congruent Numbers94

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."
This discussion has been archived. No new comments can be posted.

## Finding the First Trillion Congruent Numbers

• #### Re:Why? (Score:5, Informative)

on Tuesday September 22, 2009 @11:35AM (#29504749)
Well math is usually all for fun anyway. And it seems like they're having fun. But here's where someone found an application: [url]http://en.wikipedia.org/wiki/Congruent_number[/url]. Please don't ask us to explain why elliptic curves are useful.
• #### Birch-Swinnerton-Dyer (Score:5, Informative)

on Tuesday September 22, 2009 @11:41AM (#29504831) Homepage

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)

<philipskov AT gmail DOT com> on Tuesday September 22, 2009 @11:49AM (#29504957) Homepage
They didn't find a trillion numbers - they found all numbers up to a trillion.

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)

on Tuesday September 22, 2009 @11:52AM (#29504993)

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)

on Tuesday September 22, 2009 @12:05PM (#29505191)

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)

on Tuesday September 22, 2009 @12:40PM (#29505647)
> this isn't particularly useful in itself, but the new techniques they had to develop to solve it are important. Wiles' Fermat proof is a paramount example.
• #### Re:Terrible summary (Score:3, Informative)

on Tuesday September 22, 2009 @01:09PM (#29506037)
Although in the body it says they found 3,148,379,694 congruent numbers, the title is "A Trillion Triangles" and the web page is titled "The first 1 trillion coefficients of the congruent number curve" so I think you should let the lazy editors put their sandaled feet up and sip their lattes on this one. It's the article that's got it wrong.
• #### For anybody who's curious... (Score:3, Informative)

on Tuesday September 22, 2009 @01:21PM (#29506217) Journal

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)

on Tuesday September 22, 2009 @01:27PM (#29506279)

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)

on Tuesday September 22, 2009 @02:16PM (#29506921) Journal

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:

A congruent number k is an integer for which there exists a square such that the sum and difference of that square with k are themselves squares.

• #### Re:Why? (Score:2, Informative)

<wstein@gmail.com> on Tuesday September 22, 2009 @04:49PM (#29508725) Homepage

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.

#### Related LinksTop of the: day, week, month.

The power to destroy a planet is insignificant when compared to the power of the Force. - Darth Vader

Working...