New Number Systems Seek Their Lost Primes
Mathematicians are digging up the root structures of “class numbers,” which are closely related to primes.
Olena Shmahalo/Quanta Magazine
Introduction
In 1847, Gabriel Lamé proved Fermat’s Last Theorem. Or so he thought. Lamé was a French mathematician who had made many important discoveries. In March of that year he sensed he’d made perhaps his biggest: an elegant proof of a problem that had rebuffed the most brilliant minds for more than 200 years.
His method had been hiding in plain sight. Fermat’s Last Theorem, which states that there are no positive integer solutions to equations of the form an + bn = cn if n is greater than 2, had proved to be intractable. Lamé realized that he could prove the theorem if he just expanded his number system to include a few exotic values.
Adding (or “adjoining”) new values to the old numbers is not hard to do — there’s a straightforward mathematical recipe for how to incorporate the square root of 5 as a normal number between 2 and 3, for example, after which you can carry on with the business of arithmetic as usual. All you do is write each value in the new number system as a + b√5, where a and b are integers. This might seem like an ungainly way to write a number, but it serves as a coherent basis for creating a new number system that functions just like the old one. Mathematicians call this new system a number “ring”; they can create an infinite variety of them, depending on the new values they choose to incorporate.
Of course, it’s hard to tinker with something as intricate as a number system without producing unintended consequences. When Lamé started adjoining these funny numbers, everything looked great at first. But then other mathematicians pointed out that this newly gained flexibility came at a high cost: The new number system lacked unique prime factorization, by which a number — for example, 12 — can be expressed uniquely as a product of primes: 2 x 2 x 3. This violated a bedrock principle of conventional arithmetic.
Unique prime factorization ensures that each number in a number system can be built up from prime numbers in exactly one way. In a number ring that includes a √-5 (in practice, mathematicians often employ number systems that use the square roots of negative numbers), duplicity creeps in: 6 is both 2 x 3 and also (1 + √-5) x (1 – √-5). All four of those factors are prime in the new number ring, giving 6 a dual existence that just won’t do when you’re trying to nail things down mathematically.
Manjul Bhargava, a mathematician at Princeton University, is responsible for one of only two results ever proven in an important area of number theory.
Photo by Denise Applewhite
“In algebra classes when we first teach that unique prime factorization sometimes doesn’t hold, students gasp, they say, ‘Oh my, what happened?’ We always take for granted that everything can be uniquely decomposed into primes,” said Manjul Bhargava, a professor at Princeton University and winner of the Fields Medal, math’s highest honor.
Unique prime factorization is a way of constructing a number system from fundamental building blocks. Without it, proofs can turn leaky. Mixing roots with the regular numbers failed as an attack on Fermat’s Last Theorem, but as often happens in math, the way in which it failed was provocative. It launched an area of inquiry unto itself called algebraic number theory.
Today mathematicians are actively engaged in the study of “class numbers” of number systems. In their crudest form, they’re a rating of how badly a number system fails the test of unique prime factorization, depending on which roots get mixed in: A number system that gets a “1” has unique prime factorization; a system that gets a “2” misses unique prime factorization by a little; a system that gets a “7” misses it by a lot more.
On their face, you’d expect class numbers to be randomly distributed — that class number 5 occurs with the same frequency as class number 6, or that half of all class numbers are even. That’s not the case, though, and current research in the subject aims to understand why. Today mathematicians are circling in on the structure that underlies class numbers and inching closer to establishing the truth about long-conjectured values. It’s an effort that has generated insights about how numbers behave that go far beyond a proof of any one problem.
Ideal Symmetries
Around the same time Lamé gave his failed proof, the German mathematician Ernst Kummer developed a way to fix the loss of prime factorization with what he called “ideal numbers.” They’re not numbers in any conventional sense. Rather, they’re sprawling constructions in set theory that perform a number-like function.
For example, the simplest ideal is the infinite set of all multiples of a given integer — 5, 10, 15, 20 and so on. Ideals can be added into an already expanded number ring to restore unique factorization. They allow mathematicians to reconcile competing prime factorizations into a single set of prime factors.
Ideals can be categorized into various classes. The number of different classes of ideals you need to add to a number ring in order to restore unique factorization is the ring’s “class number.”
The study of class numbers goes at least as far back as Carl Friedrich Gauss in the early 19th century. In a sign of how hard it’s been to make progress in this area, many of his results are still state of the art. Among his contributions, Gauss conjectured that there are infinitely many positive square roots that can be adjoined to the whole numbers without losing unique factorization — a proof of which remains the most sought-after result in class numbers (and is rumored to have frustrated Kurt Gödel enough to make him give up number theory for logic). Gauss also conjectured that there are only nine negative square roots that preserve prime factorization. √-163 is the very last one.
Today, research on class numbers remains inspired by Gauss, but much of it takes place in a context established in the late 1970s by the mathematicians Henri Cohen, emeritus professor of mathematics at the University of Bordeaux, and Hendrik Lenstra, who recently retired from Leiden University in the Netherlands. Together they formulated the Cohen-Lenstra heuristics, which are a series of predictions about how frequently particular kinds of class numbers should appear. For example, the heuristics predict that 43 percent of class numbers are divisible by 3 in situations where you’re adjoining square roots of negative numbers.
“That’s interesting because it tells you this way in which class numbers are behaving unexpectedly. If you go and look at a list of telephone numbers or something, then generally speaking one in three of them should be divisible by 3,” said Akshay Venkatesh, a mathematician at Stanford University.
Gauss had to compute class numbers by hand. By the time Cohen and Lenstra made their predictions, computers made it possible to rapidly calculate class numbers for billions of different number rings. As a result, there is good experimental evidence to support the Cohen-Lenstra heuristics. However, knowing something with confidence is entirely different from proving it.
“Probably in other sciences this is where you’d be done. However, in math that’s just the beginning. Now we want to know for sure,” said Melanie Wood, a mathematician at the University of Wisconsin-Madison.
The fact that class numbers are not distributed randomly suggests something interesting is going on beneath the surface. A class number, remember, tells us something about a given number ring: the number of classes of ideals required to restore unique factorization. Those ideal classes form the “class group” of that number ring. Groups have all sorts of interesting structural properties that are not evident just from knowing the number of elements they contain, in the same way that knowing the number of people in a family doesn’t tell you much about how those people are related.
In order to understand why class numbers are distributed as they are, mathematicians need to study the structure of the class groups that give rise to the class numbers. In particular, they’re interested in the amount of symmetry in one group versus another, with the understanding that groups that have more symmetry will occur proportionally less often than groups with less symmetry.
To see the relationship between the amount of symmetry something has and the frequency with which it occurs, consider a geometric example. Start with three points arranged to make a triangle. (These points are analogous to elements of a group, but they’re not a group in any real mathematical sense.) Now think of all possible ways of connecting those points with lines, which are a stand-in for mathematical relationships. There are eight possible configurations:
- One with three lines that make a triangle.
- Three with two lines that make an ‘‘open jaw’’ shape.
- Three with one line that connects two points.
- One with no lines.
Lucy Reading-Ikkanda/Quanta Magazine
The triangle has six symmetries and appears once. The open jaw shape has two symmetries and appears three times. Or, put another way, the triangle has three times as much symmetry as the open jaw and appears one-third as often. This relationship — the more symmetry something has, the less often it occurs — holds throughout mathematics. It’s true because the less symmetry something has, the more ways it can appear. Consider that there are an infinite number of two-dimensional shapes with no symmetry, but only one shape that has infinite lines of symmetry — the circle.
“It’s not just a rough [correlation], it’s exact and precise: If one thing has three times as many symmetries, it appears one-third as often,” said Wood.
The same relationship between how symmetric something is and how frequently it occurs holds for the way groups are constructed. In the example above, relationships are defined by lines drawn between points. In a group, relationships are established by the way the elements of the group can be added together.
To be a group, those additive relationships have to satisfy certain axioms. The elements of class groups must obey the associative and commutative properties of addition, and must include a zero element, such that zero plus any other element leaves the element unchanged. The integers are in a sense the original group because they satisfy all these axioms. But certain finite sets (like class groups) also satisfy these axioms, creating, in essence, miniature number systems.
Knowing that a group has, say, four elements doesn’t tell you everything about how those four elements are related to one another. Consider two groups — call them Group 1 and Group 2 — each with four elements. What’s different about the two groups is the additive relationships between those elements. The tables below show what happens when you add an element to another element in each group.
Lucy Reading-Ikkanda/Quanta Magazine
In this setting, a “symmetry” of the group occurs wherever it’s possible to rearrange elements of the group in a way that preserves the addition structure of the group. For Group 2, there are two such symmetries: the “identity” symmetry (in which you don’t change the places of any elements), and the symmetry that swaps x with z. (Because x + x = y and z + z = y, x and z are interchangeable.)
Group 1 has more symmetries. The elements a, b, and c are all interchangeable, since a + a = 0, b + b = 0, and c + c = 0. Given that, every way of rearranging these three elements is a symmetry (or “automorphism”) of the group. If you work through all the combinations you see there are six symmetries in all. Putting this together, Group 1 has three times as many symmetries as Group 2. You’d therefore expect to find Group 2 three times as often as you would Group 1, in keeping with the rule that arrangements occur in inverse proportion to their number of symmetries. This law is as true for groups with four simple elements like Group 1 and Group 2 as it is for other, more complicated, groups of ideals.
When mathematicians are confronted with a class number, they want to know the structure of the underlying group it represents. If they can establish the structure of the underlying group, and establish how frequently groups of a given structure arise, they can bring that information back to the surface and use it to understand how often a given class number should occur.
If you start to examine the group structure and its symmetries, then “suddenly it gives you what the distribution of class numbers should be on the nose,” said Bhargava.
A New Way to Test Structure
The two groups above are (relatively) easy to parse. Groups of ideals are much harder to pin down; it’s not easy to sketch out their addition tables. Instead, mathematicians have ways of probing the groups, testing their structure, even when they can’t see the whole thing completely. In particular, they test how far each element in the group is from zero.
Recall that every group has a zero element that, when added to any other number, leaves that number unchanged. To investigate the structure of class groups, mathematicians try to get a feel for the number of elements in a given class group that have what they call “n-torsion,” which means that when you add n copies of the element, you wind up at the zero of the group. An element is 2-torsion, for example, if x + x = 0, 3-torsion if x + x + x = 0, 4-torsion if x + x + x + x = 0 and so on.
One way to make clear the difference between the two groups above is to consider how many of their elements are 2-torsion. In Group 1, all four elements are 2-torsion, which is evident by the line of zeroes on the diagonal: 0 + 0 = 0, a + a = 0, b + b = 0, c + c = 0. In Group 2, only 0 and y are 2-torsion. The amount of different types of torsion in the group is an exact reflection of the group’s overall structure.
“If the number of n-torsion elements in two groups is the same for all n then they’re the same group. Investigating how many n-torsion elements there are is a simple strategy that probes the group and is enough to recover the group if you understand everything about torsion,” said Bhargava.
A lot of the work on the Cohen-Lenstra heuristics today has to do with establishing how many elements in a class group have different types of torsion. The Cohen-Lenstra predictions with respect to torsion are quite easy to state. For example, if you’re adjoining the square roots of negative numbers, how many ideals in their class group should have 3-torsion? Cohen-Lenstra predict that there should be on average two 3-torsion elements per number ring. How many should have 5-torsion? 7-torsion? 11-torsion? The answer again, for each prime, is two.
This constancy is striking because from a naïve perspective, you’d expect the number of elements with a given torsion to grow as the size of the class group grows. Yet even as the sizes of the class groups vary, the Cohen-Lenstra heuristics predict that the number of elements with, say, 3-torsion, will on average remain constant.
“It’s interesting that this prediction is independent of the prime number,” said Bhargava. “It’s an amazing prediction.”
It’s an amazing prediction that’s been borne out statistically in countless computer runs, yet remains hard to prove.
Lowering the Bound
The Cohen-Lenstra heuristics, further extended by Cohen and Jacques Martinet in 1987, have been around for more than 40 years. Yet you could summarize progress on them on a Post-it. Only two cases have ever been proved: one in 1971, by Harold Davenport and Hans Heilbronn, and another in 2005 by Bhargava. Otherwise, “almost nothing has been proven,” said Bhargava.
With proofs of the heuristics being hard to come by, mathematicians have adopted more modest goals. They’d like to prove that the average number of n-torsion elements for a given prime is as expected, but short of that, they’ll settle for at least putting a ceiling on the number. This is called establishing an upper bound, and mathematicians have been making gradual progress in this regard.
When you’re adjoining the square root of a negative number to your number system, the class number grows in proportion to the size of the square root. If you’re adjoining the square root of –13, you can expect the class group to be, at most, about square root of 13 elements in size. Another way of writing the square root for any number n is n0.5, and that number — the 0.5 in the exponent — is the place mathematicians start when trying to fix an upper bound. If the whole class group contains n0.5 elements, then you know from the start that there can’t be more than n0.5 elements with say, 3-torsion, because that would be every element. For that reason, n0.5 is considered the trivial bound on n-torsion in the class group.
Mathematicians typically use one of several general approaches to lowering these bounds. One is an approach called a “sieve,” which you can analogize as “panning” for n-torsion elements the way a prospector pans for gold. The two other methods involve complicated transformations through which elements with n-torsion can be counted as lattice points in a region or on a curve.
One of the first to break the trivial bound was Lillian Pierce, a mathematician at Duke University, when, in 2006, she proved that the number of 3-torsion elements in a particular number ring is at most n0.49. It was a small improvement over the trivial bound, but it started a trail that other mathematicians followed. Independently and around the same time, Venkatesh and Harald Helfgott of the University of Göttingen lowered the bound to n0.44, and the next year Venkatesh and Jordan Ellenberg of the University of Wisconsin-Madison brought the bound down even further, to n0.33. These are not expected to be the optimal bounds, but they do move the field forward. “From my point of view it’s much more important to prove anything at all in the first place,” said Venkatesh.
The most recent result in this area comes from Bhargava and five coauthors, Arul Shankar, Takashi Taniguchi, Frank Thorne, Jacob Tsimerman, and Yongqiang Zhao. In January, they posted a paper to the scientific preprint site arxiv.org that lowered the bound for 2-torsion in cubic and quartic number rings to n0.28. In that same paper they also proved that they can break the trivial bound for 2-torsion for number rings in any degree.
“It is just a small savings, but it’s chipped away at the trivial bound for the first time in infinitely many cases,” said Pierce.
Even that small savings has already paid mathematical dividends. The methods Bhargava and his collaborators used have proved useful for bounding the number of solutions to a specific class of polynomial equation called elliptic curves, which is consistent with the way that class numbers seem to be situated at the intersection of many different mathematical fields. And, while there’s a long way to go before this happens, progress on class numbers could end up redeeming the original purpose of the number rings they describe.
“A proof of Fermat’s Last Theorem has never been obtained just by studying these class numbers,” said Bhargava. “If we fully understood how class groups behave in general, it seems conceivable a proof of that kind could work for FLT and for many other equations. It’s hard to say because we still have a long way to go.”
Correction: On March 6 this article was updated to clarify that the integers, not the whole numbers, are in a sense the original group.
This article was reprinted on ScientificAmerican.com.
