Congruent numbers

A press release from the American Institute of Mathematics two weeks ago announced that all the congruent numbers up to 1 trillion have been enumerated. Two questions leap to mind. What the heck is a congruent number? And who cares?

I’ll return to those questions. But first I’d like to pause just a moment to marvel at the idea of calculating anything up to 1012. A few decades ago, such a project would have been unthinkable. Today, counting to a trillion takes only an hour or so, even on plain vanilla hardware. This is truly one of the wonders of the age, and we shouldn’t grow too blasé about it. But the computation of all those congruent numbers involved a lot more than looping through “+1″ a trillion times, and it took considerably longer than an hour.

Okay, so what’s a congruent number? I would like to sidle up to that question rather than face it straightaway. The definition is not hard to understand—it’s all about right triangles with rational side lengths and integer areas—but when I started looking into this story, it took me a while to appreciate why those particular triangles might be worth thinking about.

Let’s begin with Pythagorean triples—sets of positive integers (a, b, c) that define a right triangle, with a and b giving the lengths of the legs and c the hypotenuse. The familiar (3, 4, 5) triangle is everybody’s favorite example. For which right triangles with integer side lengths is the area also an integer? That’s easy: All of them. The area of a right triangle is ab/2; in any Pythagorean triple either a or b (or both) must be an even number, which implies that ab/2 is a whole number. For the (3, 4, 5) triangle the area is (3 × 4)/2 = 6.

Knowing one such triangle, we can make more. Lots more. Just multiply a, b and c by any integer k, which has the effect of multiplying the area by k2. If k = 2, we get the (6, 8, 10) triangle with area 24; k = 3 yields the (9, 12, 15) triangle with area 54, and so on. The resulting sequence of triangles is infinite but not very interesting; all the larger triangles are just scaled-up versions of the original, like photographic enlargements. We can view the entire infinite series as a single class of triangles, and take the smallest member of the series as the prototype. That smallest triangle is given by a primitive Pythagorean triple—one where a, b and c have no factors in common. It turns out there are also infinitely many primitive triples. Euclid bequeathed us an algorithm that will generate all of them, if you let it run forever.

Given this infinite set of infinite series of triangles, it’s clear that infinitely many integers can be the area of a Pythagorean triangle. But that certainly doesn’t mean that every positive integer has this property. For example, there’s no Pythagorean triangle with an area of 5. To convince yourself of this fact, just measure the area of every integer-sided right triangle with legs no longer than 10. None of those triangles has an area of 5, and no triangle with longer integer legs can have an area that small. In principle, the same laborious but reliable procedure could be applied to any integer N to determine whether or not it is the area of some Pythagorean triangle. Here are the first few integers that appear in such an enumeration ( sequence A009112.):

6, 24, 30, 54, 60, 84, 96, 120, 150, 180, 210, 216, 240, 270, 294, 330

Rational triangles. Suppose we relax the constraints a little, allowing the sides of a right triangle to be rational numbers—either fractions or integers but not irrational values such as the square root of 2. The area is still required to be an integer.

A first question is whether right triangles with fractional sides and integer areas even exist. Maybe the cupboard is bare; maybe there are no such triangles. But no, they do exist. Here’s a proof by example:

35-12triangle.png

There’s no trickery here. If you’re in any doubt, do the arithmetic; you’ll find that the numbers define a genuine right triangle (the Pythagorean theorem holds) and the area really is exactly 7.

At last we have arrived in the realm of congruent numbers. A congruent number is an integer that’s the area of a right triangle with rational sides. All integer-sided right triangles are included in the category, along with those whose sides are rational fractions. Here’s a more formal definition:

A positive integer N is congruent if there exist rational numbers a, b and c such that a2 + b2 = c2 and ab/2 = N.

All the same questions we were asking about Pythagorean triples also come up in this new context. Where do we find rational triangles with integer area, or how can we manufacture them? Which integers N can be the area of such a triangle? Answers aren’t quite as easy to come by in this case. In particular, the strategy of enumerating triangles from the smallest up won’t work, because there is no smallest rational triangle. There are other ways of imposing an ordering on the rationals, but none of them lead to a good algorithm for enumerating congruent numbers.

So where did I get the example illustrated above? I didn’t just stumble upon it by trying random rational triangles. Note that multiplying each rational side length by the common denominator of the fractions will return us to the land of integer-sided triangles. For the example shown, multiplying through by 60 yields a (175, 288, 337) triangle; these numbers have no factor in common, so they form a primitive Pythagorean triple. The area of the new triangle is 7 × 60 × 60, or 25,200. Thus we’ve recovered an integer triangle from a rational one; what’s more important, the process can be reversed to derive rational triangles from integer-sided ones.

I mentioned a Euclidean method for generating primitive Pythagorean triples. It goes like this: Take any two positive integers m and n that satisfy the following conditions:

  • m > n;
  • one of the numbers is odd and the other even;
  • the numbers are coprime (no common factors other than 1).

Then (2mn, m2n2, m2 + n2) is a primitive Pythagorean triple. By counting through all suitable values of (m, n) starting with (2, 1), all primitive triples are generated.

A postprocessing step built atop Euclid’s procedure will generate congruent numbers. The plan is to produce a primitive Pythagorean triple and calculate the area N = ab/2 of the corresponding triangle. If the area is “square-free”—that is, it has no pairs of repeated prime factors and thus cannot be divided evenly by a perfect square—then we’re done; that value of N is a congruent number and cannot be reduced to a smaller congruent number. But if N is not square-free, we can divide out each square factor, leaving a smaller triangle with rational sides and integer area, and thereby generating another congruent number.

A worked example: The (m, n) pair (5, 4) produce the primitive triple (9, 40, 41), with area N = (9 × 40)/2 = 180. Thus 180 is identified as a congruent number, but it is not square-free; it factors as 22 × 32 × 5. We can therefore divide the area by 4 and the sides by 2, producing a shrunken (9/2, 20, 41/2) triangle of area N = 45. In this way we learn that 45 is also a congruent number, but again it is not square-free. Dividing the area by 9 and the sides by 3 yields the (3/2, 20/3 and 41/6) triangle with area N = 5. And so 5, too, is congruent; it’s also square-free and therefore cannot be reduced further. There is no smaller triangle similar to the (9, 40, 41) triangle that has integer area.

This scheme can produce an unlimited supply of congruent numbers. Unfortunately, it’s not so well suited to answering the question of whether a particular integer is congruent. The problem is that the congruent values are not generated in order from smallest to largest. If we turn the crank for a while and discover that a certain integer N appears in the algorithm’s output, then we know for sure that N is congruent. But if N has not shown up, we can’t conclude that it is not among the congruent numbers; we might simply have to wait longer for N‘s turn to come.

When I turn the crank on my own little program for generating congruent numbers, these are the first 101 values to pop out, in order of appearance:

6, 30, 60, 15, 84, 21, 210, 180, 45, 5, 330, 630, 70, 924, 231, 546, 504, 126, 14, 1320, 1560, 390, 840, 1386, 154, 2340, 585, 65, 1224, 306, 34, 990, 110, 2730, 3570, 1710, 190, 2574, 286, 4620, 1155, 5610, 5016, 1254, 2310, 1716, 429, 7140, 1785, 7980, 1995, 3036, 759, 4290, 7956, 1989, 221, 10374, 10920, 8970, 3900, 975, 39, 7854, 11970, 1330, 14490, 1610, 11550, 462, 4914, 6630, 12540, 3135, 19320, 4830, 6090, 4080, 1020, 255, 11856, 2964, 741, 18480, 23184, 5796, 1449, 161, 25200, 6300, 1575, 175, 7

Here’s the same list sorted into ascending order of magnitude:

5, 6, 7, 14, 15, 21, 30, 34, 39, 45, 60, 65, 70, 84, 110, 126, 154, 161, 175, 180, 190, 210, 221, 231, 255, 286, 306, 330, 390, 429, 462, 504, 546, 585, 630, 741, 759, 840, 924, 975, 990, 1020, 1155, 1224, 1254, 1320, 1330, 1386, 1449, 1560, 1575, 1610, 1710, 1716, 1785, 1989, 1995, 2310, 2340, 2574, 2730, 2964, 3036, 3135, 3570, 3900, 4080, 4290, 4620, 4830, 4914, 5016, 5610, 5796, 6090, 6300, 6630, 7140, 7854, 7956, 7980, 8970, 10374, 10920, 11550, 11856, 11970, 12540, 14490, 18480, 19320, 23184, 25200

The problem, again, is that we can’t conclude anything about the numbers that don’t appear in this collection. For example, 13 is absent, even though it is in fact a congruent number; it just doesn’t turn up until we get well down the list—it comes from the 49,485th triangle examined, which has sides (780/323, 323/30, 106921/9690). On the other hand, 8 is unlisted because it is not congruent; it will never show up in the output hopper no matter how long we keep cranking away.

Here are the first 101 true congruent numbers (sequence A003273):

5, 6, 7, 13, 14, 15, 20, 21, 22, 23, 24, 28, 29, 30, 31, 34, 37, 38, 39, 41, 45, 46, 47, 52, 53, 54, 55, 56, 60, 61, 62, 63, 65, 69, 70, 71, 77, 78, 79, 80, 84, 85, 86, 87, 88, 92, 93, 94, 95, 96, 101, 102, 103, 109, 110, 111, 112, 116, 117, 118, 119, 120, 124, 125, 126, 127, 133, 134, 135, 136, 137, 138, 141, 142, 143, 145, 148, 149, 150, 151, 152, 154, 156, 157, 158, 159, 161, 164, 165, 166, 167, 173, 174, 175, 180, 181, 182, 183, 184, 188, 189

Ancient history. The search for congruent numbers does not stretch back all the way to Pythagorus or Euclid, although Diophantus apparently considered a couple of special cases. L. E. Dickson’s big history of number theory attributes the first full statement of the problem to “an anonymous Arab manuscript, written before 972.” Other sources cite the works of Abu Bakr al-Karaji, a mathematician who worked in Baghdad at the end of the 10th century. A couple of centuries later Fibonacci, who straddled the Arabic and European worlds, had more to say about the problem in his Liber Quadratorum. Later still, Pierre de Fermat proved (in a marginal note, for which he had sufficient room!) that 1 is not a congruent number. (The proof extends to 4 and 9 and 16 and all other square numbers, none of which are congruent.)

These early writers formulated the problem in a somewhat different way than the rational-triangle scheme explained above. Given an integer N, they asked whether it’s possible to find three perfect squares in arithmetic progression with the interval between the squares equal to N. In other words, they sought a number s2 such that s2 – N, s2, and s2 + N are all perfect squares. For example, if N = 24, then the solution is s = 5; the three perfect squares are 25 – 24 = 1, 25, and 25 + 24 = 49.

The two versions of the problem—the integer-area right triangles and the squares in arithmetic progression—are equivalent, although that’s not exactly obvious. Here’s the connection: If a2 + b2 = c2 and ab/2 = N, then setting s = c/2 guarantees that s2N, s2, and s2 + N are all perfect squares. (For the algebraic exercise proving this, see the book by Neal Koblitz cited below.)

By the way, the squares-in-arithmetic-progression version is where we get the term “congruent numbers.” The three numbers s2N, s2, and s2 + N are all congruent modulo N. For example, 1, 25 and 49 are all congruent to 1 modulo 24. If you ask me, “congruent numbers” is a poor excuse for a name, and is particularly confusing in the context of triangles, where “congruent” has another meaning altogether. But after a thousand years I suppose it’s too late to fix it. “Karaji numbers,” anyone?

By 1915, all the integers up to 100 had been classified as either congruent or noncongruent. But as recently as 1980, when Ronald Alter wrote a brief review of the status of the problem, there were still 189 square-free numbers less than 1,000 for which the question of congruence remained unsettled. Then everything changed in 1983. In that year the nature of the congruent-number problem was transformed by Jerrold B. Tunnell of Rutgers, who not only found a better way to calculate congruent numbers but also showed why it’s worth the effort to do so.

From right triangles to elliptic curves. Before I go on, a warning: I am about to walk up to the blackboard with a piece of chalk in my hand and impersonate one of those masterful, self-confident lecturers who rattle off long trains of equations, invent lemmas on the fly, and always come to QED just as the blackboard fills up and the class ends. In my case any such air of mastery is a complete illusion; I’m just learning this stuff as I go along. But I’ll do my best to make it an entertaining illusion.

So here goes. It’s not hard to see that any product of perfect squares is also a perfect square: a2b2c2 = (abc)2. Therefore, if N is a congruent number, and s2 – N, s2, and s2 + N are all squares, we can set the product of these three factors equal to another square; call it y2. Thus we get the equation:

y2  =  (s2N) s2(s2 + N).

Multiplying the three terms on the right, this becomes:

y2  =  (s2)3N2s2.

Now perform a simple substitution of variables, setting s2 = x:

y2 = x3N2x.

This is the equation of an elliptic curve—another mathematical object with a really unfortunate name. An elliptic curve looks nothing like an ellipse. Here’s the graph of a particular elliptic curve, the one for N = 6:

elliptic-curve-6.jpg

The two pieces of the blue line mark the locus of all points (x, y) that satisfy the equation

y2 = x3 – 36x.

And the hot pink dot? That marks a rational point on the curve—a point where x and y both take on rational values. (Insiders, I’m told, call it a ratpoint.) Specifically, the dot identifies the point x = 25/4, y = 35/8. If you care to plug those numbers into the equation, you’ll find that indeed 1225/64 = 15625/64 – 225, and so the point does lie on the curve.

Tunnell, elaborating on earlier work of Kurt Heegner, showed that N is congruent if the elliptic curve y2 = x3N2x passes through a certain kind of point on the (x, y) plane. Specifically, we have to search for points whose x and y coordinates are both rational numbers, but we ignore the three points with y = 0. Then the x coordinate of the point has to satisfy three more conditions. Letting x = u/v, we require that:

  • u and v are perfect squares,
  • v is even,
  • u has no factors in common with N.

If we can find just one point on the curve that matches all these properties, then we can generate an infinity of other rational points. Moreover, the existence of such a point implies, according to Tunnell’s theorem, that N is congruent. (The hot pink point above clearly qualifies.) Thus the congruent-number problem appears to be solved: We have an unambiguous criterion for deciding if a given N is congruent or not. Just construct the corresponding elliptic curve and check the ratpoints.

Regrettably, we’ve been set up for yet another disappointment. Searching for rational points on elliptic curves is a task for which we have no efficient general method. We’re really no better off than trying to generate all Pythagorean triples.

But wait! We’re not done yet. From the properties of elliptic curves, Tunnell derived yet another criterion—and this one turns out to be the key to a simple and practical test. It all hinges on the number of integer solutions to some quadratic equations that on first glance appear to be arbitrary strings of symbols plucked out of thin air. The criterion is this: If N is a square-free congruent number, and if N is odd, then the number of integer solutions to the equation N = 2x2 + y2 + 8z2 must be exactly double the number of integer solutions to N = 2x2 + y2 + 32z2. (If both equations have no integer solutions, the condition is satisfied, since 2 × 0 = 0.) For even N, the two equations are slightly different, but the test works in exactly the same way.

tunnell-criterion-1000.png

The graphic above shows the 361 square-free numbers up to 1,000 that pass the Tunnell test. The height of each dot indicates the number of integer solutions to the equation N = 2x2 + y2 + 8z2 (or the corresponding equation for even N). The two values of N with 160 solutions are 689 and 761. (It’s curious that in most cases—308 out of 361—the number of solutions is actually zero. I don’t know what this means or whether that pattern continues with larger N.) [See Update 2009-10-10, below.]

What sets the Tunnell criterion apart from all the others is that we can actually carry out the test in a reasonable and predictable amount of time. For any given N, counting the solutions should be doable in time proportional to N3/2, simply by trying all integer values of x, y and z less than the square root of N.

So that’s it, right? Problem solved at last? Well, no, there’s still a small hitch—a bit of awkward fine print. Tunnell proved that if N is square-free and congruent, then the criterion on the number of integer solutions must be satisfied. This much is unconditionally true. But what about the converse? If the criterion is satisfied, can we be certain that N is a congruent number? In this direction, the proof is not unconditional. It’s contingent on a proposition known as the Birch–Swinnerton-Dyer conjecture, which is widely believed, and supported by an abundance of empirical evidence, but still unproved. Which leaves just enough doubt to make the game still interesting.

Why should anyone care about this stuff? On first acquaintance, the search for congruent numbers sounds like one of those mathematical pastimes that appeal to amateurs (like me!) but don’t really command the attention of the research community. There are so many kinds of cutely named numbers out there—perfect, amicable, lucky, happy—and not all of them carry deep significance. The congruent numbers might well be just another amusing sideshow. But it turns out they’re not. There’s serious mathematics here, enough to engage the interest of serious mathematicians.

Elliptic curves have been a focus of intense scrutiny for decades. Henri Poincaré studied them in the early years of the 20th century. In the 1920s Louis Mordell proved a theorem about the rational points on elliptic curves: Even when there are infinitely many points, they all come from a finite set of “generators”; the number of generators and hence the number of infinite families is called the rank of the curve. In the 1950s Yutaka Taniyama and Goro Shimura, with later refinements by André Weil, worked out a conjecture about elliptic curves and another class of mathematical objects, called modular forms. Andrew Wiles and Richard Taylor proved part of that conjecture in the course of settling Fermat’s Last Theorem in the 1990s; the rest of the Taniyama-Shimura conjecture has since been proved as well.

And now we have the Birch–Swinnerton-Dyer conjecture, one of the famous million-dollar math problems. I’m not going to try to explain the conjecture in any detail—I’ve used up all my chalk, and probably my readers’ patience, too—but I think the basic idea goes something like this. On the one hand we have an elliptic curve, drawn in the (x, y) plane. On the other hand we have something called an L-function, which is defined on the plane of complex numbers. Think of the L-function as an undulating landscape with mountains rising above the plane and submarine canyons deep under it. The topography of this surface is determined in part by points selected from the elliptic curve, so there’s a connection between the two objects. The conjecture formulated in the 1960s by Bryan Birch and Peter Swinnerton-Dyer says that the shape of the L-function in the neighborhood where it passes through zero gives us information about the rank of the elliptic curve and thus about the number of rational points.

There’s an analogy between the BSD conjecture and an even more celebrated problem on the million-dollar list, the Riemann hypothesis. The zeros of the Riemann zeta function (which is much like an L-function), carry information about the distribution of prime numbers. The Birch–Swinnerton-Dyer conjecture invites us to suppose that the zeros of L-functions of certain elliptic curves tell us something about the distribution of congruent numbers.

Incidentally, the BSD conjecture must be one of the earliest products of computer-driven experimental mathematics. The numerical explorations that led to the conjecture were done with the EDSAC, the pioneering electronic computer built at the University of Cambridge.

The trillion triangles. Hand-waving about elliptic curves and L-functions might provide vague a rationale for interest in congruent numbers, but one part of the story I still didn’t get was why anyone would bother to compute mass quantities of congruent numbers. So I asked Michael Rubinstein of the University of Waterloo. Rubinstein had earlier computed the congruent numbers up to 109, and it was his challenge that provoked the recent thousandfold expansion of the inventory. Rubinstein explained:

I’m interested in the statistical distribution of congruent numbers. A few years ago, Brian Conrey, Jon Keating, myself, and Nina Snaith came up with a prediction for the asymptotic number of congruent numbers up to x, akin to the prime number theorem. This prediction grew out of remarkable models created by the same researchers and David Farmer for related elliptic curve L-functions that were inspired by random matrix theory and based on a number of unproved assumptions.

The prediction is that the number of congruent numbers less than x, arising from even-rank elliptic curves, is asymptotically

$$c x^{3/4} \log(x)^{11/8}$$

where c is a constant. Our model doesn’t let us completely nail down the constant c, and the data will help us understand what the correct constant is. The asymptotic behaviour stabilizes at a logarithmic rate, so going to 1012 is only 50 percent better than going to 108.

It will also provide a good amount of data for studying the statistics of ‘higher rank elliptic curves’ in the family of elliptic curves related to congruent numbers. The correct model to use for higher rank elliptic curves is not really understood, and the billions of congruent numbers found will end up yielding several million higher rank curves with which we hope to gain insight into the statistics of higher rank curves (compared to just thousands of higher rank curves from earlier computations).

The enumeration of the trillion triangles was done by two teams. William Hart of the University of Warwick and Gonzalo Tornaria of the Universidad de la Republica in Uruguay ran their program on a computer called Selmer at Warwick. Mark Watkins of the University of Sydney, David Harvey of the Courant Institute and Robert Bradshaw of the University of Washington used the SAGE computer at Washington.

The strategy of the computation is based on the Tunnell criterion, but it turns out there’s a better way to go about it than explicitly counting the number of integer solutions to those various quadratic equations in (x, y, z). Tunnell showed that all the information about the number of solutions could be encoded in a formal power series, which looks like this:

\[A(q) = a_{1}q^{1} + a_{2}q^{2} + a_{3}q^{3} + a_{4}q^{4} + ... \]

It’s a “formal” series in the sense that we don’t actually care about evaluating the sum for any particular value of q; instead, we just want to know the various coefficients ai. This is how the Tunnell criterion gets encoded in the series: If ai is zero in this series, and if i is a square-free number, then i is congruent. (Actually, there are two separate series, one for odd i and one for even i.)

The odd and even power series are generated by a couple of formidable-looking products. Here’s the one for the odd series:

\[A(q)=q\prod_{n=1}^\infty(1-q^{8n})(1-q^{16n})\left(1+\sum_{n=1}^\infty 2q^{2n^2}\right)\]

Since both the overall product and the sum in the third factor call for infinitely many values of n, we can’t multiply out this whole expression. Fortunately, though, it turns out that larger n contribute only to higher coefficients, and so we can compute early terms in the series without worrying about what might happen later. Kent Morrison notes that taking just the factors

\[q(1-q^8)(1-q^{16})(1-q^{16})(1+2q^2+2q^8+2q^{18})\]

is enough to generate all the odd congruent numbers up to 25. Those five factors expand to:

\[A(q)=q^1+2q^3+q^9-2q^{11}-4q^{17}-2q^{19}-3q^{25}+...\text{ higher terms}\]

The terms missing from this series—those with a zero coefficient—are just the odd square-free congruent numbers in this range: 5, 7, 13, 15, 21, 23.

The big computation by Bradshaw et al. used essentially this same scheme, with a few refinements and optimizations. The challenge is that when you’re trying to compute all the terms of the series out to a1,000,000,000,000q1,000,000,000,000, you wind up multiplying some enormous numbers. I don’t mean just that the numbers are too big to fit into the registers of a 32-bit or a 64-bit computer. They’re too big to fit into the main memory of a computer with 128 gigabytes of RAM. Moreover, the arithmetic has to be done exactly; approximations are useless. Thus a major part of the effort in setting up the computation was devising efficient “out of core” multiplication routines for ridiculously large numbers. The basic algorithm was a fast-fourier-transform method.

And the result? Up to 1012, the computation identified 3,148,379,694 square-free congruent numbers number candidates with N in the residue classes 1, 2, and 3 modulo 8. I look forward to reading more about the analysis of their distribution. [See Update 2009-10-10, below.]

References and resources. Two weeks of reading and tinkering have not made me the master of this subject. For those who would like to explore further I can offer some resources I’ve found helpful, listed in no particular order.

  • Ed Eikenberg has posted some lecture notes from a talk on elliptic curves and congruent numbers given in 2000.
  • William Stein offers slides from a Harvard lecture in 2001.
  • The web page for another William Stein course (this one at the University of Washington in 2006) provides notes and handouts and a collection of function definitions that will let you play with congruent numbers and elliptic curves in the Sage computer mathematics system.
  • Koblitz, Neal. 1993. Introduction to Elliptic Curves and Modular Forms. Second edition. New York: Springer-Verlag. Some kind soul has posted page images for the first chapter online.
  • Guy, Richard K. 2004. Unsolved Problems in Number Theory. Third edition. New York: Springer. (Section D27, p. 306, discusses congruent numbers.)
  • Tunnell, J. B. 1983. A classical diophantine problem and modular forms of weight 3/2. Inventiones Mathematicae 72:323–334. (Available online via the DigiZeitschriften.)
  • Barry Cipra writes on the recent trillion-trangle computation: Tallying the class of congruent numbers, ScienceNOW, September 23, 2009. (Get it now, while it’s free.)
  • Dickson, Leonard Eugene. 1952. History of the Theory of Numbers. New York: Chelsea Pub. Co. (For congruent numbers see Vol. 2, Chapter 16, p. 459.)
  • Brown, Ezra. 2000. Three Fermat trails to elliptic curves. The College Mathematics Journal 31:162–172. Free PDF available online (unlike most CMJ articles), apparently because it won a Polya prize.
  • Rubin, Karl, and Alice Silverberg. 2002. Ranks of elliptic curves. Bulletin of the American Mathematical Society 39:455–474. Online.
  • Silverberg, Alice. 2001. Open questions in arithmetic algebraic geometry. In Arithmetic Algebraic Geometry, Institute for Advanced Study/Park City Mathematics Series 9, pp. 83–142. Providence: American Mathematical Society. Postscript preprint.
  • The American Institute of Mathematics web page on congruent numbers, which includes several helpful appendices, such as a discussion of FFT multiplication, an essay on congruent numbers by Kent Morrison and a link to the paper by Bradshaw, Hart, Harvey, Tornaria and Watkins reporting the trillion-triangle computation. (At this writing, the posted version of the paper is still an incomplete draft.)
  • Conrey, J. B., J. P. Keating, M. O. Rubinstein and N. C. Snaith. 2000. On the frequency of vanishing of quadratic twists of modular L-functions. arXiv preprint. (This paper and the one listed below discuss conjectures about the distribution of congruent numbers, among other topics.)
  • Conrey, J. Brian, Jon P. Keating, Michael O. Rubinstein and Nina C. Snaith. 2004. Random matrix theory and the Fourier coefficients of half-integral weight forms. arXiv preprint.
  • Brown, Jim. 2007. Congruent numbers and elliptic curves. PDF (Brown refers to this text as lecture notes for an undergraduate course, but in fact it is a very polished and well-organized expository article. Includes some Sage code for working with rational points of elliptic curves.)
  • Alter, Ronald. 1980. The congruent number problem. American Mathematical Monthly 87:43–45. (Tables of what was known and unknown shortly before Tunnell’s breakthrough.)

Special thanks to David Farmer for alerting me to this story in the first place and to Michael Rubinstein for help understanding what it all means.

Update 2009-10-10: In the comments, Barry Cipra points out that the quadratic equations in the Tunnell criterion necessarily have no solution whenever N is congruent to 5, 6, or 7 modulo 8. In fact all of the zero-solution points in the graph I presented above come from such N. Numbers in the residue classes 0 and 4 modulo 8 cannot be square-free. If we plot only those N that are square-free and congruent to 1, 2 or 3 modulo 8, we are left with just 53 square-free congruent-number candidates up to 1,000:

tunnell-criterion-123.png

Only the numbers in these three residue classes were included in the trillion-triangle computation.

This entry was posted in computing, mathematics.

13 Responses to Congruent numbers

  1. Jeremy says:

    Thanks, well researched and interesting article. I learned something new

  2. Dave P says:

    I recall that in computing power series like this it can be more efficient to use the Chinese Remainder Theorem, provided that some sort of bound is known on the size of the coefficients, but I have not got any clue whether that’s true here.

  3. brian says:

    @Dave P: Yes, they did indeed use Chinese remaindering. The basic idea, if I understand correctly, is that you do all the computations modulo several primes and then use the Chinese remainder theorem to recover the full result. In this case “several primes” meant about 500 of them. And then they needed some further trickery to make sure the CRT reconstruction didn’t in fact take longer than simply doing the full multiplication without the modular reduction.

    See http://www.warwick.ac.uk/~masfaw/congruent.pdf for the details.

  4. Barry Cipra says:

    It is somewhat misleading to say that “Up to 1012, the computation identified 3,148,379,694 square-free congruent numbers.” For one, as you noted, the numbers that are identified are only conjecturally congruent, assuming the BSD conjecture — that is, they satisfy the “Tunnell criterion,” which is to say they satisfy certain conditions on the numbers of solutions to those funky quadratic equations. This is why in my ScienceNOW article I wound up calling them “candidate” congruent numbers.

    But also, it implies that the given number represents the count of *all* square-free congruent numbers up to a trillion. As I understand it (and I hope someone will jump in and correct me if I’m wrong), it only counts the square-free (candidate) congruent numbers up to a trillion that are congruent, modulo 8, to 1, 2, or 3.

    This is because these are the only cases for which an actual computation is required to check if N satisfies the Tunnell criterion. The square-free numbers congruent to 5, 6, and 7 mod 8 automatically satisfy the criterion for the simple reason that the ternary quadratic equations N = 2x^2 + y^2 + 32z^2 and N = 2x^2 + y^2 + 8z^2 (for N odd) and N = 8x^2 + 2y^2 + 64z^2 and N = 8x^2 + 2y^2 + 16z^2 (for N even) have no integer solutions whatsoever when N=5, 6, or 7 mod 8, for bordline trivial reasons based on the observation that, mod 8, the only odd square is 1 and the only even squares are 0 and 4. When you mod out by 8, the quadratic equations reduce to N = 2x^2 + y^2 for odd N and N = 2y^2 for even N, and it’s easy to see that neither of these has any solutions mod 8 when N=5, 6, or 7 mod 8. (For example, 2y^2 can equal 0 or 2 mod 8, but never 6.) This, by the way, helps account for the curiosity you observed in your graphic.

    There are 125 billion numbers in each residue class mod 8 (up to a trillion), and about 90% of them are square-free in the classes congruent to 1, 2, 3, 5, 6, and 7. (It’s reasonably straightforward to count the exact number of square-free numbers in each residue class, but I don’t trust myself to do the calculations correctly. There are, of course, *no* square-free numbers in the classes congruent to 0 or 4 mod 8.) Thus there are well over 300 billion square-free (candidate) congruent numbers altogether in the residue classes 5, 6, and 7 mod 8, whereas the recent computation showed that the residue classes 1, 2, and 3 contain only a little over 3 billion such numbers.

    On the one hand, it would be nice to know the complete count of (candidate) congruent numbers, square-free or not, up to various numbers x — a kind of analog to the prime number function pi(x). On the other hand, what the recent computation was really aimed at, as I understand it, is exploring implications of the BSD conjecture for elliptic curves (e.g., the asymptotic formula mentioned by Rubinstein), and for those purposes only the square-free numbers in the residue classes 1, 2, and 3 are of interest.

  5. brian says:

    @Barry: Thanks much for the clarification.

  6. Krish says:

    > in any Pythagorean triple either a or b (or both) must be an even number

    Actually, the “both” is incorrect.

    The triple generated by Euclid’s formula is primitive if and only if m and n are coprime and exactly one of them is even. (http://en.wikipedia.org/wiki/Pythagorean_triple)

    You can derive this by substituting (2n) & (2p) for a & b in a^2 + b^2 = c^2. You would get c^2 is even always which is not accurate.

  7. brian says:

    @Krish: Yes, but the sentence you quote is not discussing primitive triples, but rather all Pythagorean triples. The idea of primitive triples isn’t introduced until a couple of paragraphs later.

  8. Krish says:

    OK. I see. And I also see I was confusing my logic there in my previous “proof”. :-(

    Good article.

  9. Barry Cipra says:

    On further reflection, it occurs to me that a good way to clarify the nature of the recent computations might be to introduce a bit of terminology. Let’s call a positive integer N, with square-free part denoted n (i.e., n is square-free and N=nk^2 for some integer k), a “Tunnell number” if either

    n is even and the equation n = 8x^2 + 2y^2 + 16z^2 has twice as many integer solutions as the equation n = 8x^2 + 2y^2 + 64z^2; or

    n is odd and the equation n = 2x^2 + y^2 + 8z^2 has twice as many integer solutions as the equation n = 2x^2 + y^2 + 32z^2.

    This is, on the face of it, a seemingly arbitrary, unmotivated definition. One might equally arbitrarily define, say a “Hayes number” to be an N for which the equation n = x^2 + y^2 has twice as many integer solutions as the equation n = xy. But the motivation for Tunnell numbers is provided by Tunnell’s great theorem, which can be stated in two parts, as follows:

    1. Every congruent number is a Tunnell number; and
    2. If the BSD conjecture is true, then every Tunnell number is a congruent number.

    The current state of affairs can be summarized thusly:

    1. Every number (square-free or not) in the residue classes 5, 6, and 7 mod 8 is a Tunnell number; and
    2. Up to a trillion, the residue classes 1, 2, and 3 mod 8 contain a total of 3,148,379,694 square-free Tunnell numbers.

    If and when the BSD conjecture becomes a theorem, the distinction between Tunnell numbers and congruent numbers will evaporate. Until then, there will be additional results of the form “all Tunnell numbers up to x are congruent numbers” and “all Tunnell numbers that [blah blah blah] are congruent numbers.” A result of the first form can be obtained in a seemingly straightforward way by finding a right rational triangle of area N for each Tunnell number N up to whatever x you have the resources to compute — except that absent the BSD conjecture, there’s no algorithm that’s guaranteed to terminate (and even if you assume a guarantee of termination, some of the rational numbers can have huge numerators and denominators). I’m not sure what the current largest known x is, but I think it’s only in the thousands.

    It’s worth noting that even if the BSD conjecture turns out to be false, the first part of Tunnell’s theorem is still an amazingly powerful result. It provides a very easy way to show that certains numbers cannot be the area of any right rational triangle. Prior to Tunnell’s breakthrough, this was, if anything, the harder thing to prove, since it’s often easier to prove things do exist (e.g., by finding a right rational triangle of given area) than to prove they don’t (e.g., there’s no n-th power of any positive integer that’s the sum of two other n-th powers of positive integers).

    I hope this helps.

  10. Steve Winburn says:

    Barry,

    I am working on writing a paper on the congruent number problem for a modular forms class. The goal is not that extravagant, I need to exhibit 5 is congruent using the Shimura lift, Tunnel’s Theaorem, Eichler Shimura, and Waldspurger. However, I am having a bit of trouble with the construction. Is there a nuts and bolts reference to the lift with examples available anywhere. Thank you if you can help me. Please email me if you can because I happened upon this forum only and may not find it again. Thank you so much.

    Steve Winburn
    secuervo@aol.com
    winburn@math.uga.edu

  11. Pingback: Carnival of Mathematics #59 « The Number Warrior

  12. Teresa James says:

    Having been a literature major “in the day,” can you help me understand how one can use the information that 8 is NOT a congruent number? I’m really serious–and totally ignorant when it comes to mathmatics. I read about the research in NYU’s pub on recent research in congruent numbers and that’s how I got interested.

    Thanks for any insight!

  13. brian says:

    @Teresa James: Golly, I’d like to help, but I’m not sure I have an answer. As I said at some point in the piece, a lot of mathematics of this sort isn’t really of much use even to mathematicians, much less to us English-major types. In this particular case, I think the mathematics has genuine applications to serious research, but that still leaves most of the world out in the cold.

    What does it really mean to “use” an idea–any idea?

    I worry that I’ve totally missed the point of your question. If so, please do let me know.