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

32 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 dcollins · · Score: 2, Interesting

      "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 came here expecting to see this question, and was not disappointed.

      The answer is: "For the same reason that people do crack."

      Seriously. www.angrymath.com

      --
      We know where leadership by an anti-intellectual "strongman" who scapegoats minorities and likes boisterous rallies goes
    4. 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.

    5. Re:Why? by KingPin27 · · Score: 2, Funny

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

      Perhaps these are the guys that should have been working for Enron? I'm just sayin -- new ways of multiplying numbers...!

      --
      "i lost my dignity on a slippery wiener"
    6. Re:Why? by wastedlife · · Score: 2, Insightful

      I was going to remark that this is a forum, and not all forums need to use BBCode syntax.

      Then I realized I was being pedantic.

      Then I remembered this is /.

      So:

      Forum != BBCode

      --
      Said, "It's just like dice but it's got more sides And it tells me who lives and who dies"
    7. Re:Why? by jayspec462 · · Score: 2, Funny

      Math gives you a highly addictive mind/mood altering experience? Hmm... We must have tried different Math.

      You are. The addictive one is called "Crystal Math."

      --
      $comment =~ s/($verb)\s+($noun)/IN SOVIET RUSSIA, $2 $1s YOU!/g;
    8. Re:Why? by Hurricane78 · · Score: 2, Funny

      Can I then ask, what must have happened in one's life, that he considers that to be "fun"? ;)

      --
      Any sufficiently advanced intelligence is indistinguishable from stupidity.
    9. Re:Why? by William+Stein · · 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.

    10. Re:Why? by Eudial · · Score: 2, Funny

      \section{Re:Why?}

      Well \emph{of course} not...

      --
      GAAH! MY PRINTER IS ON FIRE!!! PUT IT OUT! PUT IT OUT!
    11. Re:Why? by Xest · · Score: 2, Insightful

      The same reason you do any high level math like this, to figure out more, new math, because you might have to think up different ways of doing math to solve the problem at hand, or because when you do you might notice new patterns that are of relevance to solving other problems.

      Ultimately any new techniques or patterns may be useful in themselves, or may go on to spawn other new techniques or patterns that are useful.

      Math is a massive topic, and the more you explore it the more it grows, some of it is useful, some merely interesting to those with a mathematical mind, but it is experimentation with this practically useless math that often opens further doors to the practically useful. Sometimes the point is merely furthering math until the the point itself is found- that's how a fair bit of math has become useful overtime, the math came first, and then the application was realised after. Sometimes you need to stumble upon the solution first to know what problems it can fix!

    12. Re:Why? by MacAnkka · · Score: 2, Funny

      This isn't a TeX document either. That would be just wrong.

      After all, If we had a way to post readable formulas and uncommon chararacters, this wouldn't be the Slashdot comments section ;)

  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.
    2. Re:Birch-Swinnerton-Dyer by Garridan · · Score: 2, Insightful

      Caveat: I am not an expert on BSD, but my advisor is.

      First place to look is here: http://www.claymath.org/millennium/Birch_and_Swinnerton-Dyer_Conjecture/. For one thing, the BSD conjecture implies that the title of this story is accurate. But, we don't even know that. Consider Fermat's last "theorem" -- the linchpin was a theorem "All Elliptic Curves are Modular" -- before that, we knew that modular elliptic curves behaved quite nicely, but we didn't know if there were other elliptic curves. To this day, we can prove remarkably little about very obvious-looking trends that we see in data about elliptic curves. Assuming BSD, many computations about elliptic curves are suddenly tractable.

      Ok, but what does this have to do with the country's bottom line? Directly, I'd say "nothing". Indirectly, though, this is providing a lot of interest to American mathematicians. The current thinking is (hah) a bit of a trickle-down effect. As undergrads study, they gravitate towards the more interesting fields -- if math looks sexy, we get more mathematicians. The more mathematicians graduate, the more funding mathematics departments will get in a very direct way -- this gives us better teaching budgets, which should effect an increase in the number of good math teachers. The more good math teachers we have, the better our students will learn. That's the hope, anyway.

  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.

    1. Re:Terrible summary by Intron · · Score: 2, Informative

      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.

      --
      Intron: the portion of DNA which expresses nothing useful.
    2. Re:Terrible summary by clone53421 · · Score: 2, Informative

      Hmm, that's correct. Today, in fact. I didn't realize.

      However, this PDF (the top result for Al-Karaji congruent -trillion) 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.

      --
      Alexander Peter Kristopeit bought his basement from his mommy for one dollar.
  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.

    2. Re:Hard Drive? by RobertB-DC · · Score: 2

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

      Yes, the explanation is simple. The non-technical writers who wrote "limited by the size of a computer's hard drive" have no freakin' clue how a computer actually works. Someone gave them a detailed explanation about the limits on multiplying large integers without resorting to "lossy" floating-point arithmetic, and the writer's head threw a fatal exception.

      So by default, they said, "Some computer thing isn't big enough." And computers only have four parts: Screen (aka "computer"), keyboard, mouse, and Hard Drive. So it must have been the Hard Drive.

      --
      Stressed? Me? Of course not. Stress is what a rubber band feels before it breaks, silly.
    3. Re:Hard Drive? by wastedlife · · Score: 2, Funny

      At least their Hard Drive works, mine wont turn on anymore after I spilled a little coffee in the cup-holder. Stupid foreign electronics.

      Anyway, can't they just have the Geek Squad put in more Gigabytes?

      --
      Said, "It's just like dice but it's got more sides And it tells me who lives and who dies"
    4. Re:Hard Drive? by William+Stein · · Score: 2, Interesting

      I own the 128GB RAM, etc., computer that the second group did the computation on. I have a Sun X4550 24TB disk array (ZFS) connected to it, but I only allocated a few terabytes of space for a scratch disk. They were well into the calculation when I found out what they were up to (I was initially annoyed, since they were saturating the network). I think they were just being polite to me and the other users by not using a lot more disk.

    5. Re:Hard Drive? by pipoca · · Score: 2, Insightful
      Well, they are right in that it's bounded by memory. A number of languages let you do arithmetic on arbitrarily large integers. Rational numbers are basically 2 integers of random size, and if arithmetic functions for rationals aren't provided (as in e.g. common lisp or Haskell), they can be implemented. Sure, it might be slower (addition and subtraction is O(n)), but if you're a researcher and if you know the program is correct, you should be able to just leave the computer on for a week or two (or however long) to let it run.

      More than that, this problem is embarrassingly parallel - each number doesn't change the result of any other, so you can very easily split up the work load on many computers, or write something that will run on GPU's or something. At a certain point, arithmetic will become too time expensive (because the number uses so many words of memory). So either you run out of memory first (unlikely) or things start to take to long. Possibly things will start to take to long when the numbers become larger then some cache, and the cache miss rate will drive your running time into the ground.

  7. Re:What do you mean? by MrNaz · · Score: 2, Insightful

    It's neither, turns out it's a Muslim congruent number!

    --
    I hate printers.
  8. Great work demonstrating important algorithms! by onionman · · 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 project in some form or another and their algorithms and code are driving the cutting edge of the field. Great work guys!!

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

    That's because the programming itself is menial work. The algorithms are more important which the pseudo code describes well enough.

  10. For anybody who's curious... by clone53421 · · Score: 2, 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).

    --
    Alexander Peter Kristopeit bought his basement from his mommy for one dollar.
    1. 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.