New Elliptic Curve Breaks 18-Year-Old Record:
In August, a pair of mathematicians discovered an exotic, record-breaking curve. In doing so, they tapped into a major open question about one of the oldest and most fundamental kinds of equations in mathematics.
Elliptic curves, which date back to at least ancient Greece, are central to many areas of study. They have a rich underlying structure that mathematicians have used to develop powerful techniques and theories. They were instrumental in Andrew Wiles' famous proof of Fermat's Last Theorem in 1994, at the time one of the most important unsolved problems in number theory. And they play a key role in modern cryptography.
Yet mathematicians still can't answer some of the most basic questions about them. For example, they often try to characterize elliptic curves by studying the special "rational points" that live on them. On a given curve, these points form clear and meaningful patterns. But it's not yet known whether there's a limit to how varied and complicated these patterns can get.
Answering this question would allow mathematicians to make sense of the vast and diverse world of elliptic curves, much of which remains uncharted. So they've set out to explore the outer fringes of that world, hunting down outlier curves with stranger and stranger patterns. It's a painstaking process, requiring both creativity and sophisticated computer programs.
Now, two mathematicians — Noam Elkies of Harvard University and Zev Klagsbrun of the Center for Communications Research in La Jolla, California — have found an elliptic curve with the most complicated pattern of rational points to date, breaking an 18-year-old record. "It was a big question whether this barrier could be broken," said Andrej Dujella of the University of Zagreb in Croatia. "It's a very exciting result for all of us working and interested in elliptic curves."
The discovery lays bare an ongoing debate over what mathematicians think they know about elliptic curves.
Elliptic curves don't appear particularly exotic. They're just equations of the form y2 = x3 + Ax + B, where A and B are rational numbers (any number that can be written as a fraction). When you graph the solutions to these equations, they look like this:
Mathematicians are particularly interested in a given elliptic curve's rational solutions — points on the curve whose x– and y-values are both rational numbers. "It's literally one of the oldest math problems in the history of humanity," said Jennifer Park of Ohio State University.
While it's relatively straightforward to find rational solutions to simpler types of equations, elliptic curves are "the first class of equations where there are really a lot of open questions," said Joseph Silverman of Brown University. "It's just two variables in a cubic equation, and that's already complicated enough."
To get a handle on the rational solutions of an elliptic curve, mathematicians often turn to the curve's rank, a number that measures how closely packed the rational points are along the curve. A rank 0 elliptic curve has only a finite number of rational points. A rank 1 elliptic curve has infinitely many rational points, but all of them line up in a simple pattern, so that if you know one, you can follow a well-known procedure to find the rest.
Higher-rank elliptic curves also have infinitely many rational points, but these points have more complicated relationships to each other. For example, if you know one rational solution of a rank 2 elliptic curve, you can use the same procedure you used in the rank 1 case to find a whole family of rational points. But the curve also has a second family of rational points.
The rank of an elliptic curve tells mathematicians how many "independent" points — points from different families — they need in order to define its set of rational solutions. The higher the rank, the richer in rational points the curve will be. A rank 2 and a rank 3 curve both have infinitely many rational solutions, but the rank 3 curve packs in rational points from an additional family, meaning that on average, a given stretch of it will contain more of them.
Almost all elliptic curves are known to be either rank 0 or rank 1. But there are still infinitely many oddballs with higher rank — and they're exceedingly difficult to find.
As a result, mathematicians aren't sure if there's a limit to how high the rank can get. For a while, most experts thought it was theoretically possible to construct a curve of any rank. Recent evidence suggests otherwise. Without a proof either way, mathematicians are left to debate the true nature of elliptic curves, illustrating just how much they have yet to understand about these equations.
Elkies, a prominent number theorist, didn't intend to break rank records. In the mid-2000s, he was studying seemingly unrelated objects called K3 surfaces. To understand them, he sliced them up and looked at the pieces.
Imagine starting with a simple surface, a flat plane. You can slice it into infinitely many straight lines, laid side by side. Depending on how you make your slices, the lines you end up with will be defined by different equations.
Similarly, there are more complicated, curvy surfaces that, when sliced up, yield infinitely many elliptic curves. Mathematicians have been using these surfaces to find higher-rank elliptic curves since the 1950s.
Elkies realized that his K3 surfaces were strange enough to give him access to even more exotic curves. In 2006, he sliced a particular K3 surface in just the right way and found among the slices an elliptic curve that he could show had a rank of at least 28 — beating the previous record of 24. It was an exciting moment for elliptic curve experts, who believed an explosion of record breakers might follow.
Instead, nothing happened. Elkies' record stood for nearly two decades — a noticeable departure from the relatively steady record-setting rate that mathematicians had enjoyed since the 1970s.
Was it perhaps a sign that rank could be limited after all — that the hunters were beginning to close in on their last few prey? Or was it just a reflection of the difficulty of the task?
When Elkies announced his discovery in 2006, Zev Klagsbrun was an undergraduate student at Queens College in New York. One of his professors, who had competed against Elkies in a high school math competition in the 1980s — Elkies won — told him about the new record-breaking curve during office hours.
Klagsbrun was intrigued. Years later, he returned to the result, proving that so long as a widely believed conjecture is true, Elkies' curve has a rank of precisely 28. So when he ran into Elkies at a conference in 2019, he saw an opportunity to push the result even further. Though a bit intimidated — "It's difficult to keep up with him," Klagsbrun said — he convinced Elkies to return to the search for new curves.
"I was like, 'Hey, I've got access to some computing power. I'm willing to write fast code. Search with me! Show me your secrets!'" Klagsbrun said.
They went back to Elkies' K3 surface. Eighteen years earlier, he had sliced it up in a way that gave him a pile of infinitely many curves. These curves were already quite exotic, but he could only guarantee that they had a rank of at least 17. He still needed an outlier to break the record of 24. Since he couldn't just calculate the rank of every curve in his pile, he used a well-known computational method to determine which among millions of them seemed most likely to have an anomalously high rank. He then calculated those ranks by hand, one by one, until he found his rank 28 winner.
Klagsbrun could now offer a faster computational method for sifting through the contenders. While Elkies had only been able to look through millions of curves, Klagsbrun could handle tens of trillions.
This wider search unearthed many curves in Elkies' old pile that exhibited some unusual properties, but none of them broke his 2006 record. The pair decided to move on.
Four years passed. Then, a few months ago, Elkies and Klagsbrun crossed paths once more at a conference and got to talking.
They set out to slice the K3 surface in a different way, getting a new pile of curves to work with. But there were hundreds of ways they could slice it, and most of those slicing methods seemed unlikely to produce the curve they sought.
Then, entirely by accident, they found a slicing method that, like Elkies' previous one, gave them a pile of curves, all guaranteed to have a rank of at least 17. It seemed more likely than the other approaches to contain a hidden gem. Sure enough, using Klagsbrun's more powerful computational technique, they found within that pile an elliptic curve with a rank of at least 29. This elliptic curve has the most complicated set of rational solutions ever seen: Mathematicians need at least 29 independent points to characterize them.
The curve's equation, when written as y2 = x3 + Ax + B, has values of A and B that are each over 60 digits long. The 29 independent rational solutions that Elkies and Klagsbrun pinpointed involve numbers that are similarly huge.
(Score: 5, Informative) by aliks on Sunday November 17, @09:06AM (4 children)
In case you are wondering why society encourages top class brains to play around with such abstruse corners of the mathematical world - these elliptic curves can be used to create especially efficient crypto codes, error correcting codes etc etc
And of course the power techniques they develop to solve these tough problems usually have lots more applications.
So a message to all purseholders - keep those university grants coming!
To err is human, to comment divine
(Score: 3, Insightful) by JoeMerchant on Sunday November 17, @02:13PM (1 child)
Agreed, the general area of study is valuable.
However, from a novice perspective, these fellows are finding higher order elliptic curves in which the solution sets are more segregated, into larger numbers of "bins".
I am guessing that would make for (marginally) weaker cryptography than the more common curves wherein all solutions are in a single set?
🌻🌻 [google.com]
(Score: 2) by aliks on Sunday November 17, @05:02PM
I'm not sure its weaker, but probably less efficient in the sense that the key sizes are larger than necessary.
My understanding is that the role of the elliptic curve is to provide a cyclic group whose multiplication/exponentiation can create a "trapdoor" function - a function that is easy to calculate, but whose inverse is very very difficult to calculate.
The trouble with the higher rank elliptic curves is that they give you a product of cyclic groups, so you are only using a small part of a very large group, which is inefficient.
I'm happy to be corrected if there are any experts in here, and of course its always possible that there is a clever way to make use of the higher rank curves to achieve new miracles.
To err is human, to comment divine
(Score: 2) by Deep Blue on Sunday November 17, @02:14PM
Oh come on. That Y^2 = X^3-x+1 is clearly for puzzle pieces.
(Score: 2) by ledow on Monday November 18, @10:21AM
We fund education because it's good to have smart people - even abstract smartness - and produces results for the nation you're in.
It's not a difficult thing to fathom, and those that can't are the ones who benefit from it the most and understand it the least.
Even if this had no practical application, it builds into a body of science that helps reinforce everything else we do, including the things with practical application, in the future.
(Score: 2) by mcgrew on Sunday November 17, @06:54PM (2 children)
The difficulty of writing science fiction:
In STNG's The Royale, 1989, Picard is trying to solve the as yet unsolved mathematical riddle that would be solved in the real world five years after the episode was filmed, hundreds of years before the fictional Picard is born.
Safer to set your fiction in a different galaxy long, long ago, where "parsec" isn't a measure of distance and there's sound in outer space.
A man legally forbidden from possessing a firearm is in charge of America's nuclear arsenal. Have a nice day.
(Score: 3, Insightful) by ledow on Monday November 18, @10:24AM (1 child)
It's a suspension of disbelief thing - and all you need to do to combat it is to make it a different name.
"Ah, Piquant's Last Theorem! Unsolved for a century!".
Instant fix.
It bugs me that scriptwriters think that dropping in a real name adds "authenticity" - it doesn't. It makes those who know cringe, and those who don't know couldn't care less what the name was anyway.
So why not just fix it immediately and play on the 400+ (or whatever) years of maths that's supposed to have occurred between now and then by just making up a name / theorem?
"Le'Dow's first conjecture of Space-graph, how interesting".
(Score: 1) by khallow on Monday November 18, @06:37PM
(Score: 2) by jasassin on Monday November 18, @10:35PM
CRICKETS CHIRPING
It's ok... I wouldn't have understood it anyway.
jasassin@gmail.com GPG Key ID: 0xE6462C68A9A3DB5A