Slashdot Mirror
Finding the First Trillion Congruent Numbers
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."
An african or european congruent number?
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
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).
Why don't they post their actual code? What good is it to tell me if you found the first trillion congruent numbers when you're hiding part of your methodology?
[b.belong('us') for b in bases if b.owner() == 'you']
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.
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.
I don't believe they found the first trillion congruent numbers; rather, they tested the first trillion whole numbers for congruency.
According to the article they found 3,148,379,694 numbers between 1 and a trillion that are congruent and not the first trillion numbers that are congruent like the summary suggests.
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?
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!!
Ok, so they do have this at the end of their paper:
A special thanks to David Farmer, Estelle Basor, Kent Morrison, Sally Koutsoliotas and Brian Conrey of AIMath for their careful preparation of a web page providing details of our computation for the general public.
which is refreshing. I'm guilty of assuming that most researchers are still adherents of the, "well I can't be bothered to make my code easily available for open scrutiny, even though all my paper's conclusions are based on numerics" mindset.
[b.belong('us') for b in bases if b.owner() == 'you']
TFA says they have found all congruent numbers up to 1,000,000,000,000. It does NOT say that they found 1,000,000,000,000 congruent numbers.
"I do not agree with what you say, but I will defend to the death your right to say it"
I read a headline saying "Finding the First Trillion Congruent Numbers" and I'm ashamed to admit I had no idea they were missing...
You have the right to remain sentient. If you give up the right to remain sentient, you will be elected to public office
That's because the programming itself is menial work. The algorithms are more important which the pseudo code describes well enough.
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.
680?
Alexander Peter Kristopeit bought his basement from his mommy for one dollar.
An irrational team of mathematicians recently decided to push the limits on finding congruent numbers...
and thought, "I quite agree!"
For conscience is the wound, and there's naught to staunch it
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.
The 80's called. They want their hacked paged memory architecture invented because of crappy small address buses back.
I believe your name actually speaks a lot about you now.
Pseudo-code is a trillion times more helpful to programmers than code in a language they potentially don't know.
...1,000,000,000,001 Ha ha!!
The ancient greek philosophers went into a tizzy when they discovered the hypotenuse of a unit square was not rational. The pythagorians incorrectly hoped the universe was rational. A trillion congruent numbers should be useful for any engineering purpose. You just normalize one side to unity.
I asked them before this came out, and they said they didn't want to post their code on the press release in order to avoid being slashdotted. Seriously. I think the code is certainly available upon request, and will be made available later when the hoopla dies down. Much of it is in FLINT, which is part of Sage.
Most of the code you'd want is in FLINT and MPIR. Every single author of the paper (with the possible exception of Mark Watkins) is a developer of open source software. You can find the disk-multiplication code here: http://sage.math.washington.edu/home/robertwb/disk_mul/, published under what looks like a BSD-like license. Their email addresses are public, and I'm sure they'd happily send you the source.
Nobody should ever need more than 680.
You misquoted that:
Nobody should ever need more than 640.
Hence my confusion. 680 is more than 640!
Alexander Peter Kristopeit bought his basement from his mommy for one dollar.