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

10 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 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"
    2. 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!

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

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

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

    --
    I hate printers.
  4. 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.

  5. Re:"outlined in detail" != "here's some pseudo cod by Anonymous Coward · · Score: 1, Insightful

    I think programmers are prone to overestimating the value of actual code in scientific research, mostly because they know how much fun coding can be. Misunderstand me correctly here - I'm not saying how you implement something is irrelevant or not a matter of skill, but that when you are trying to write a scientific paper, the actual code you use to implement a specific algorithm is not all that interesting. It's sort of like the color of your shoes when you go to a job interview - it's really irrelevant to the goal you are trying to achieve unless you fsck it up completely and end up with iridescent footwear.

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

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

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