Sixty needs two digits and sixty-one needs ten

In February 1657 Pierre de Fermat sent a challenge to the mathematicians of Europe: find a whole-number solution of $x^2 - 61y^2 = 1$, other than the trivial one. He chose 61 with care. The smallest answer is

$$x = 1{,}766{,}319{,}049, \qquad y = 226{,}153{,}980,$$

and the equations on either side of it are no challenge at all. $x^2 - 60y^2 = 1$ is solved by $x = 31$, $y = 4$, and $x^2 - 62y^2 = 1$ by $x = 63$, $y = 8$. Bhāskara II had solved the 61 case five hundred years earlier by the cyclic method that a method that is allowed to miss describes, and he too chose it as a showpiece.

Why should two neighbouring equations differ by eight digits? The existence of a solution is guaranteed for every non-square $D$, and one solution that makes all the others shows that all the others follow from the smallest. Its size is the remaining mystery, and it is a mystery with a precise answer: the smallest solution is the product of the continued fraction’s complete quotients over one period. A long period with large quotients means an enormous solution, and nothing about the size of $D$ controls either.

Neighbours that disagree by eight digits #

The scatter above shows the first surprise in bulk. Most values of $D$ have small solutions: 777 of the 969 non-square $D$ up to 1,000 need fewer than ten digits. But the top edge climbs steadily, and the records are spaced irregularly — 61 jumps from five digits to ten, 421 from 23 to 34, and between records the cloud is dense and noisy. There is no smooth function of $D$ hiding under it.

Look closely at a run of consecutive values. From 52 to 72, the solutions have 1 to 5 digits except at 61, which has 10. The row of periods printed under the bars tells the same story at a smaller scale: 61’s period is 11, the longest in the run; 67’s is 10 and its solution has five digits; 63, 65 and 68 have periods of 1 or 2 and solutions of one to three digits.

The small ones have a reason that can be seen directly. When $D$ is one less than a square, $D = n^2 - 1$, the solution is $x = n$, $y = 1$, since $n^2 - (n^2 - 1) = 1$. So 63 has $x = 8$ and 99 has $x = 10$. When $D$ is one more than a square, $n^2 + 1$, the number $n + \sqrt D$ has norm $-1$ and its square, $2n^2 + 1 + 2n\sqrt D$, solves the equation: 65 has $x = 129$. Values next to a square are cheap, and the floor of the scatter is made of them — the small scalloped arches visible along the bottom of the second scatter below.

61 is as far from structure as a number between 49 and 64 can be, and it pays for it. The same is true of every record-setter: none sits beside a square.

The solution is a product of the steps #

The link between the period and the size is an identity, and it is exact. The continued fraction of $\sqrt D$ is computed as a fraction that never closes computes any continued fraction, by repeatedly taking a whole part and inverting what is left, and the numbers produced along the way are the complete quotients $\alpha_1, \alpha_2, \ldots$ — for $\sqrt{61}$, the first is $1/(\sqrt{61} - 7) = (7 + \sqrt{61})/12 \approx 1.234$. Why the expansion has to repeat writes each one as a state $(P + \sqrt D)/Q$ and shows that the states cycle.

Multiply the complete quotients of one period together. The result is not merely close to the fundamental unit — it is the fundamental unit, or its square root when the period is odd. The reason is a general fact about continued fractions: for any number $x$ with convergents $p_k/q_k$,

$$\alpha_1 \alpha_2 \cdots \alpha_n = \frac{1}{\lvert q_{n-1}x - p_{n-1}\rvert}.$$

Each inversion magnifies the leftover error, and the product of the magnifications is the reciprocal of the error remaining after $n$ steps. For $x = \sqrt D$ at the end of a period, the convergent $p/q$ satisfies $p^2 - Dq^2 = \pm 1$, so $p - q\sqrt D = \pm 1/(p + q\sqrt D)$ and the product is exactly $p + q\sqrt D$.

The figure makes the identity visible. The eleven quotients of $\sqrt{61}$ have logarithms 0.21, 1.45, 1.31, 0.35, 0.86, 1.02, 0.27, 1.16, 1.60, 0.07 and 2.70, and stacked end to end they reach 10.99 — the logarithm of $29{,}718 + 3{,}805\sqrt{61}$. Multiplied out exactly, with no rounding anywhere, the product of the eleven numbers $(P + \sqrt{61})/Q$ is that number itself. Its norm is $-1$, because 11 is odd, and squaring it gives the answer to Fermat’s challenge.

Size is length times average step #

The identity turns a question about size into a question about length. The logarithm of the fundamental unit is a sum of one term per step of the period, so it is the period’s length times the average logarithm of a complete quotient. Either factor can make a solution large.

For $\sqrt{94}$ the period has 16 terms, the product lands on $+1$ directly, and the logarithm is 15.27 — about 0.95 per step, a little below $\sqrt{61}$'s 1.0 per step. The last quotient is always the largest: it is $a_0 + \sqrt D$, roughly $2\sqrt D$, because the last term of every period is twice the first. So a period of length $\ell$ produces a unit of size roughly $2\sqrt D$ times the product of $\ell - 1$ more modest factors, and a long period is what makes a solution enormous.

For a typical real number the average is known exactly, and it is the rate at which the denominators of the best approximations in how close a fraction can get grow. Paul Lévy proved in 1936 that for almost every $x$ the denominators of the convergents grow like $e^{\beta n}$ with $\beta = \pi^2/(12 \ln 2) \approx 1.1866$, so the average logarithm of a complete quotient is that constant. Quadratic irrationals are not typical — they form a set of measure nothing — but their periods behave like short samples of typical expansions, and the per-step averages for $\sqrt D$ up to 1,000 have a median of about 1.28 — above Lévy’s constant, because in a short period the large final quotient carries a heavy share.

So the problem of size reduces to the problem of period length, which the essay on repetition found scattered below a ceiling of about $2\sqrt D$ up to 1,000, with no formula predicting which $D$ come close. The solution’s size inherits exactly that irregularity, multiplied by about one per step.

Why the records sit five past a multiple of eight #

The records in the first scatter share a remainder. After the small early ones, they are 61, 109, 181, 277, 421, 541 and 661 — every one of them a prime, and every one except 409 leaves remainder 5 on division by 8. That is not a quirk of the range, and the reason is one of the prettiest facts in the subject.

When $D$ leaves remainder 1 on division by 4, the ring $\mathbb{Z}[\sqrt D]$ is not the whole of the integers in its field. The numbers $(a + b\sqrt D)/2$ with $a$ and $b$ both odd are integers too — they satisfy a monic equation with whole coefficients, the point the integers a field contains makes about the golden ratio — and the field’s smallest unit may be one of them. For 61 it is

$$\varepsilon_0 = \frac{39 + 5\sqrt{61}}{2}, \qquad \frac{39^2 - 61 \cdot 5^2}{4} = \frac{1521 - 1525}{4} = -1.$$

Pell’s equation cannot see $\varepsilon_0$, because its coordinates are not whole numbers. It sees the first power of $\varepsilon_0$ whose coordinates are, and that power is the cube: $\varepsilon_0^3 = 29{,}718 + 3{,}805\sqrt{61}$, exactly the product of the eleven complete quotients above. The answer to Fermat’s challenge is a cube, and a third of its digits are the price of refusing halves.

Why the cube, always? Reduce the half-integers modulo 2. When $D$ is 5 more than a multiple of 8, the result is the field with four elements, whose non-zero elements form a group of order 3; the whole-number ones are exactly those that reduce to 1, and every element cubed reduces to 1. When $D$ is 1 more than a multiple of 8, the reduction is two copies of the field with two elements, a unit with odd $a$ and $b$ would need $a^2 - Db^2 = \pm 4$ with the left side a multiple of 8, and no half-integer unit exists. Of the 102 square-free $D$ up to 1,000 that are 5 more than a multiple of 8, 77 have a half-integer unit, and for each of them the Pell solution’s logarithm is tripled. The records collect where the tripling happens and where, as the class number formula below requires of a large unit, the class number is small.

How large it can get #

Plotted against $\sqrt D$ rather than $D$, the logarithm of the unit fills a wedge. The steepest line from the origin through any point has slope 3.80, reached at $D = 421$, where $\ln\varepsilon \approx 78$ and $\sqrt D \approx 20.5$. That wedge shape is not a coincidence of the range.

The class number formula is where the shape comes from. For each real quadratic field it relates two quantities that look unrelated — the class number $h$, which counts how badly unique factorisation fails, and the logarithm of the fundamental unit — through a special value of an $L$-function:

$$h \cdot \ln\varepsilon \approx \sqrt D \cdot L(1, \chi_D),$$

up to a constant depending on how $D$ sits modulo 4. The $L$-value is never large; it is at most a constant times $\log D$. So $\ln\varepsilon$ is at most about $\sqrt D \log D$, and it is near that size exactly when the class number is small. When $h = 1$ — which heuristics predict for most prime $D$ — the unit is forced to be as large as $\sqrt D \cdot L(1, \chi_D)$, and the dashed line of slope 1 is that prediction with the $L$-value set to its typical size.

Seen this way, the huge solution for 61 is not bad luck but good arithmetic. $\mathbb{Q}(\sqrt{61})$ has class number 1, so every scrap of $\sqrt{61} \cdot L(1, \chi)$ must be carried by the unit. For $D = 60$ the field is $\mathbb{Q}(\sqrt{15})$, since $\sqrt{60} = 2\sqrt{15}$, and its class number is 2, so the budget is shared and the unit is small: it is $4 + \sqrt{15}$, and the solution for 60 is its square, $31 + 8\sqrt{15} = 31 + 4\sqrt{60}$. A large unit and a small class number are the same fact. That is the tie two families of solutions ended on, seen from the other side.

The cattle of the Sun #

The most famous large solution belongs to a problem written in verse and attributed to Archimedes, rediscovered by Lessing in a Wolfenbüttel manuscript in 1773. It asks for the numbers of bulls and cows, white, black, yellow and dappled, in the herd of the Sun god, subject to seven linear conditions and two more: that the white and black bulls together make a square, and the yellow and dappled bulls a triangular number. In 1880 August Amthor reduced it to

$$x^2 - 4{,}729{,}494\,y^2 = 1 \quad \text{with } 9{,}314 \text{ dividing } y.$$

The fundamental solution of $x^2 - 4729494y^2 = 1$ is not the difficulty. The continued fraction of $\sqrt{4729494}$ has period 92, and the product of its complete quotients is a unit whose $x$ has 45 digits. The difficulty is the extra condition: $y$ must be divisible by $9314 = 2 \times 4657$. The first solution’s $y$ is even already, so everything depends on 4657.

The powers $\varepsilon^k = x_k + y_k\sqrt D$ all solve the equation, and the question is the first $k$ with $4657 \mid y_k$. Reduce everything modulo 4657. Since $4729494$ is not a square modulo 4657 — Euler’s criterion gives $-1$ — the numbers $a + b\sqrt D$ modulo 4657 form a finite field with $4657^2$ elements, in which raising to the power 4657 is the same as conjugating. So $\varepsilon^{4657} = \bar\varepsilon = \varepsilon^{-1}$, and $\varepsilon^{4658} = 1$ modulo 4657. The $k$ wanted is the order of $\varepsilon$ in that field, and it must divide $4658 = 2 \times 17 \times 137$.

Checking the eight divisors in turn, the first power whose $y$ vanishes modulo 4657 is the 2329th, $2329 = 17 \times 137$. The solution the herd needs is therefore $\varepsilon^{2329}$, and its $x$ has $\lfloor 2329 \log_{10}\varepsilon - \log_{10} 2 \rfloor + 1 = 103{,}273$ digits. Amthor found this in 1880 and worked out that the total herd begins 7766 and runs to 206,545 digits. The whole number was computed in 1965 by Williams, German and Zarnke, and printed out in 1981 — forty-seven pages of it.

The argument is a short tour of a good deal of number theory in one place: Fermat’s little theorem in a field of $p^2$ elements, where the Frobenius power is conjugation; the order of an element dividing the size of the group; and a unit of Pell’s equation whose size comes, as above, from a period of 92 complete quotients.

What the scatter cannot show #

The digit counts are exact and the explanation is not. Every point in the scatters is a solution computed and verified in exact arithmetic, and the identity with the complete quotients is checked by multiplying them out. The class number formula is quoted rather than drawn, and no figure computes a class number or an $L$-value, so the claim that the wedge’s top edge belongs to class number 1 is the theory’s, not the picture’s.

The range is small. Up to 1,000 the steepest slope is 3.80, and nothing in the figures says how that number behaves further out. The theory’s bound of order $\sqrt D \log D$ allows it to grow slowly without limit, and whether it does, for infinitely many $D$, is tied to the same unanswered questions about class numbers.

And a digit count is not a computation. Writing down $\varepsilon^{2329}$ takes 103,273 digits, but finding the exponent took eight trials modulo 4657. The size of the answer and the difficulty of finding it are different things, and the scatter shows only the first. A scatter of the time each solution took to find would look different again: the cyclic method and the continued fraction both take a number of steps proportional to the period, not to the digits, so the 61 case is eleven steps of small arithmetic that happen to end on a large number.

Still open: computing the size without writing it down #

The logarithm of the fundamental unit, the regulator, is a small number even when the unit is enormous — for the cattle problem’s unit it is about 237,795, while the unit itself has over a hundred thousand digits. Algorithms since Shanks and Lenstra compute the regulator to any precision without ever writing the unit out, representing it instead as a short product of manageable numbers, and they run in subexponential time in the number of digits of $D$.

In 2002 Sean Hallgren gave a quantum algorithm that computes the regulator in polynomial time, one of the few problems besides factoring and discrete logarithms on which a quantum algorithm is exponentially faster than every known classical one. Whether a classical computer can do it in polynomial time is open. It is believed not — the problem is at least as hard as factoring — but no proof of that exists either, and the question sits alongside factoring as one of the few natural problems on which quantum and classical computation are thought to differ.

The gap is sharpest for exactly the equations this essay has been about. A solution with a hundred thousand digits cannot be printed in polynomial time by anybody, quantum or not, because printing it takes a hundred thousand steps. What can be asked of an algorithm is the regulator, the logarithm, to a stated number of places — a few dozen digits in place of a few hundred thousand — and that is the quantity whose classical complexity is unknown.

A size set by a journey #

Neighbouring equations have wildly different first solutions because the first solution is not a function of $D$ in any simple sense. It is the product of the steps the continued fraction takes to return to its start, so it is as long as the journey and as large as the steps along it. A number just beside a square returns in one or two steps; 61 takes eleven; 4729494 takes ninety-two, and then the cattle problem asks for the journey to be repeated 2329 times.

When a quantity is a product along a cycle, its size is the cycle’s length times the typical step — and the right question stops being “how large is it?” and becomes “how long is the cycle?”, which here has an honest answer only in the class number formula, and a complete one nowhere.

Two further facts sharpen the answer without completing it. The cycle can be shorter than the unit it produces suggests, when the field has a smaller unit with halves in it that Pell’s equation is not allowed to use; then the solution is a cube, and the records cluster where that happens. And the cycle is long exactly when the class number is small, because the class number formula shares a fixed budget between the two. Fermat chose 61 because it was hard. He could not have known that it is hard because $\mathbb{Q}(\sqrt{61})$ factors uniquely, and because 61 is five more than a multiple of eight.