Slashdot Mirror

← Back to Stories (view on slashdot.org)

Finding the First Trillion Congruent Numbers

Posted by timothy on from the after-that-it's-easy dept.

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."

12 of 94 comments (clear)

  1. Why? by Stuart+Gibson · · Score: 4, Insightful

    I'm so not a maths geek, but why is this useful other than being able to say "hey, we found the first trillion congruent numbers"?

    I know that certain branches are useful for cryptography purposes, but what awesomeness does this let us do?

    --
    It's all fun and games until a 200' robot dinosaur shows up and trashes Neo-Tokyo... Again
    1. Re:Why? by immakiku · · Score: 4, Informative

      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.

    2. Re:Why? by BKX · · Score: 3, Interesting

      According to TFA (I know, I know, we aren't supposed to do that, but I only skimmed it! I swear!!), this isn't particularly useful in itself, but the new techniques they had to develop to solve it are important. Specifically, they had to figure out news ways of multiplying numbers, since the numbers they wanted to multiply were larger than their hardware's main memory (OK, OK, a number that's trillions of bits long seems a bit far fetched to me too, but that's what TFA said.)

    3. Re:Why? by Shaterri · · 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.

  2. Birch-Swinnerton-Dyer by JoshuaZ · · 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. 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).

    1. Re:Birch-Swinnerton-Dyer by sconeu · · Score: 4, Funny

      But it doesn't look like there's much hope for anyone resolving BSD in the foreseeable future.

      Of course not. Netcraft has already confirmed that BSD is dead.

      --
      General Relativity: Space-time tells matter where to go; Matter tells space-time what shape to be.
  3. Terrible summary by theskov · · Score: 5, Informative
    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.

  4. Re:"outlined in detail" != "here's some pseudo cod by JoshuaZ · · Score: 4, Insightful

    They aren't hiding any part of their methodology. They've given more than enough details. Posting the actual code in the paper would be a distraction. When publishing new algorithms mathematicians generally outline it in pseudocode since this is a) easier to follow and b) much more useful for issues of proving formal correctness. I would not be at all surprised if you can find the code on the website of one of the authors and almost certainly the authors will provide the code details if you send them an email.

  5. Slight correction by mcg1969 · · Score: 4, Informative

    I don't believe they found the first trillion congruent numbers; rather, they tested the first trillion whole numbers for congruency.

  6. Hard Drive? by Diabolus+Advocatus · · Score: 3, Interesting

    Today the limitations of discovering these congruent numbers is limited only by the size of a computer's hard drive.

    Can someone explain why they didn't use more than 2.7TB of HDD space if HDD space is the limiting factor?

    1. Re:Hard Drive? by localman57 · · Score: 4, Funny

      The rest was already full of pr0n. These guys don't get out much.

  7. Re:For anybody who's curious... by William+Stein · · Score: 3, Insightful

    That's a good explanation. I have to emphasize though, that they actually found all the congruent numbers up to a trillion only under the completely unproven hypothesis that the Birch and Swinnerton-Dyer conjecture is true. It's entirely possible that this conjecture is false, and some of the numbers they found are actually not congruent numbers. However, part of the conjecture is known (by work of Coates and Wiles -- the same Wiles who proved Fermat's Last Theorem), so we do know that all numbers they didn't list are definitely not congruent numbers.