Finding the First Trillion Congruent Numbers 94
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."
Re: (Score:2, Insightful)
It's neither, turns out it's a Muslim [wikipedia.org] congruent number!
Re: (Score:2)
"African" and "European" are in reference to locations. "Muslim" is a religion, not a region.
Africa and Europe are not countries. Iran is. "Iranian" isn't fitting either.
"Middle-eastern" is the closest fit.
Re: (Score:1)
Re: (Score:2)
I concur.
Re: (Score:2)
680?
Re: (Score:2)
You misquoted that:
Nobody should ever need more than 640.
Hence my confusion. 680 is more than 640!
Why? (Score:5, 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?
Re:Why? (Score:5, Informative)
Re: (Score:2)
Re: (Score:3, 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
Re: (Score:3, Funny)
\section{Re:Why?}
Well \emph{of course} not...
Re: (Score:2, Funny)
After all, If we had a way to post readable formulas and uncommon chararacters, this wouldn't be the Slashdot comments section
Re: (Score:2)
Touché, Slashdot handles uncommon characters just fine!
Re: (Score:2)
Re: (Score:3, Funny)
Can I then ask, what must have happened in one's life, that he considers that to be "fun"? ;)
Re: (Score:1)
Well math is usually all for fun anyway.
I think maths is fun, sure, but I do hope you're not suggesting that's all it's usually good for?
Re:Why? (Score:4, 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.)
Re: (Score:1, Informative)
Re: (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
Re: (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...!
Birch-Swinnerton-Dyer (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 [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).
Re:Birch-Swinnerton-Dyer (Score:5, 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.
Re: (Score:2)
Ok then, but why is the Birch-Swinnerton-Dyer conjecture (whatever that is) in any way useful? (Honest question.)
Re: (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/ [claymath.org]. 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 da
Re: (Score:2)
Re: (Score:1, Funny)
It's how Derren Brown really predicted the lottery numbers.
Re: (Score:1)
In order to work out a trillion congruent numbers, they must be using some Very Deep Maths!
Re: (Score:1)
Re: (Score:1, Interesting)
Statistical analysis of the prime numbers gave us the insight needed to find a formula describing an upper bound for their frequency.
Sometimes in order to make an important realization, you have to work through near-pointless crap for a long time, hoping it will pay off.
Re: (Score:3, 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
Re: (Score:2)
Re: (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."
Re: (Score:2)
Math gives you a highly addictive mind/mood altering experience?
Yes, for certain values of "you". Apparently, you specifically are not a member of this set.
Re: (Score:2)
Is it possible to create an algorithm that calculates the Nth "congruent number" in a tractable amount of time -- without having to calculate the intervening N-1 such numbers? (or having to do an exhaustive search up to the *value* of that number)
Is there another algorithm that given N and X (and a radix), can ascertain (yes/no) whether "X is the Nth congruent number"? Does the most efficient possible algorithm for this problem also necessitate calculating N congruent numbers, assuming the first one d
Re: (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.
Re: (Score:3, 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 usefu
"outlined in detail" != "here's some pseudo code" (Score:1)
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?
Re:"outlined in detail" != "here's some pseudo cod (Score:5, Insightful)
Re: (Score:2)
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.
Re: (Score:3, Insightful)
That's because the programming itself is menial work. The algorithms are more important which the pseudo code describes well enough.
Re: (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
Re: (Score:1)
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 [flintlib.org], which is part of Sage [sagemath.org].
Re: (Score:1)
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/ [washington.edu], 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.
Terrible summary (Score:5, Informative)
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.
Re: (Score:3, Informative)
Re: (Score:2)
What they may have found is all of the congruent integers up to 1 trillion.
Re: (Score:2)
According to wikipedia...
Maybe you should read it again...
Re: (Score:2)
Re: (Score:3, Informative)
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:
Slight correction (Score:5, Informative)
I don't believe they found the first trillion congruent numbers; rather, they tested the first trillion whole numbers for congruency.
Re: (Score:2)
Re: (Score:2)
They might be stored as a bitmap. That would take only 10^12/8 = less than a terabyte of space. Or they might store them as successive differences, which would require only 3x10^9*8 = around 30 gigabytes. Of course, the latter would be a lot harder to work with. Depends on how you wanted to use the results, I gue
Hard Drive? (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?
Re:Hard Drive? (Score:5, Funny)
Re: (Score:2)
Can someone explain why they didn't use more than 2.7TB of HDD space if HDD space is the limiting factor?
Yeah. Cause I've already finished looking at the first 3 billion numbers...
Re: (Score:3)
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 thin
Re: (Score:3, 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?
Re: (Score:2, Insightful)
Re: (Score:1)
Re: (Score:1, Funny)
The 80's called. They want their hacked paged memory architecture invented because of crappy small address buses back.
Re: (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.
Re: (Score:2)
Time was the limiting factor. They just didn't say that.
Given enough time, their algorithm would have been limited only by the size of the hard drive... but they didn't give it enough time to reach that limit. So, the hard drive was big enough.
Re: (Score:2)
Maybe they only had a 2.7TB drive?
Great work demonstrating important algorithms! (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 [sagemath.org] project in some form or another and their algorithms and code are driving the cutting edge of the field. Great work guys!!
Misleading summary (Score:2)
I feel so bad... (Score:2)
For anybody who's curious... (Score:3, 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).
Re: (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 d
Re: (Score:2)
It's entirely possible that this conjecture is false, and some of the numbers they found are actually not congruent numbers
Surely a number less or equal to a trillion is testable for congruentness. The algorithm to test n would be find rational numbers x and y such that sqrt(x^2 + y^2) is rational and n = xy/2. It could be hard work for some of the numbers, but that's the whole point - to have done the work once and for all.
The claim is 3,148,379,694 congruent numbers were found - a finite number of numbers
Misread one word (Score:1)
An irrational team of mathematicians recently decided to push the limits on finding congruent numbers...
and thought, "I quite agree!"
1,000,000,000,000?? (Score:2)
can we finally outlaw irrational numbers now? (Score:2)