Two families of solutions, and a box that holds both

One solution that makes all the others showed that every solution of $x^2 - 2y^2 = 1$ is a power of the smallest, $3 + 2\sqrt 2$, so that an equation with infinitely many answers is really one answer and a rule for multiplying. The obvious next question changes the right-hand side. What happens to $x^2 - 2y^2 = 7$, or to $x^2 - 2y^2 = N$ for any whole number $N$?

The answer has the same shape with one new ingredient. The solutions of $x^2 - 2y^2 = 7$ are again infinite, and again generated by multiplying by $3 + 2\sqrt 2$ — but one starting point is not enough. It takes two, and the solutions fall into two families that never meet. For other right-hand sides it takes one, three, four or none, and the number turns out to be decided by the prime factors of $N$ alone.

Multiplying by the unit keeps the right-hand side #

The reason the families exist is the identity that makes Pell’s equation work in the first place. Write a solution of $x^2 - 2y^2 = N$ as the number $x + y\sqrt 2$, and call $x^2 - 2y^2$ its norm. The norm is the product of the number and its conjugate, $(x + y\sqrt 2)(x - y\sqrt 2)$, and because conjugation respects multiplication, the norm of a product is the product of the norms. That is Brahmagupta’s composition, which the chakravala essay uses at every step.

So multiply a solution of norm 7 by $3 + 2\sqrt 2$, whose norm is 1, and the product has norm $7 \times 1 = 7$. Starting from $3 + \sqrt 2$, which has norm $9 - 2 = 7$, the product is

$$(3 + \sqrt 2)(3 + 2\sqrt 2) = 9 + 6\sqrt 2 + 3\sqrt 2 + 4 = 13 + 9\sqrt 2,$$

and indeed $169 - 162 = 7$. Multiplying again gives $75 + 53\sqrt 2$, then $437 + 309\sqrt 2$, and dividing by the unit instead runs the chain the other way. Every solution sits in a two-way infinite chain, and every link of the chain is a solution.

What is new is that one chain need not contain everything. Start instead from $3 - \sqrt 2$, which also has norm 7, and the chain runs $5 + 3\sqrt 2$, $27 + 19\sqrt 2$, $157 + 111\sqrt 2$, and so on. None of these is in the first chain. The two chains interleave along the hyperbola and never share a point, and together they hold every solution of $x^2 - 2y^2 = 7$ with $x$ positive — a claim that needs an argument, since a third chain could be hiding further out.

Straightening the hyperbola with a logarithm #

The figure at the top is the device that makes all of this visible, and it is worth seeing why it works. Along the branch of the hyperbola where $x$ is positive, the number $u = x + y\sqrt 2$ determines the point completely: its conjugate is $v = x - y\sqrt 2 = N/u$, and $x$ and $y$ are recovered as $(u + v)/2$ and $(u - v)/(2\sqrt 2)$. So the branch is a copy of the positive numbers, and multiplying by the unit $\varepsilon = 3 + 2\sqrt 2$ is simply $u \mapsto \varepsilon u$.

Take logarithms and multiplication becomes addition. On the line of $\ln u$, the unit acts as a translation by $\ln\varepsilon \approx 1.7627$, the same distance wherever it is applied. A chain of solutions therefore becomes an arithmetic progression with that common difference, and the curved, exponentially spreading hyperbola becomes a straight line with evenly spaced dots on it.

That is why the figure can be read at a glance. In the row for $N = 1$ the dots sit at 0, 1.76, 3.53, 5.29 and 7.05: the powers of the unit, one per step. In the row for $N = 7$ there are two progressions, orange and blue, offset from one another by $\ln\bigl((3+\sqrt 2)/(3 - \sqrt 2)\bigr) \approx 1.02$ and each with the same step. In the row for $N = 119$ there are four, and in the row for $N = 3$ there is nothing at all.

The shaded windows are each one step wide. Any window of that width contains exactly one member of each chain — a chain advances by one full step at a time, so it cannot skip a window or land in one twice. Counting the dots in any single window therefore counts the chains, and that is how the right-hand column was read.

The same trick turned the continued fraction’s periodicity into something finite, and it is the idea behind Dirichlet’s unit theorem in general: the units of a number ring become a lattice once logarithms are taken, and a lattice has a fundamental domain. Here the lattice is one-dimensional, the fundamental domain is a window of width $\ln\varepsilon$, and everything interesting about $N$ happens inside one window.

A box every family must visit #

A window of the log line corresponds to an arc of the hyperbola, and an arc of a hyperbola is bounded. That turns “count the chains” into a finite search.

Centre the window on the vertex of the hyperbola, where $u = v = \sqrt N$. Every chain has a member with $u$ between $\sqrt N/\sqrt\varepsilon$ and $\sqrt N\sqrt\varepsilon$, because the window has width exactly $\ln\varepsilon$. For such a member, $v = N/u$ lies in the same range, so

$$|y| = \frac{|u - v|}{2\sqrt D} \le \frac{\sqrt N\,(\sqrt\varepsilon - 1/\sqrt\varepsilon)}{2\sqrt D}.$$

Now $(\sqrt\varepsilon - 1/\sqrt\varepsilon)^2 = \varepsilon + \varepsilon^{-1} - 2 = 2x_1 - 2$, where $x_1 + y_1\sqrt D$ is the fundamental solution, since $\varepsilon + \varepsilon^{-1} = 2x_1$. Substituting and tidying with $x_1^2 - Dy_1^2 = 1$ gives the bound Trygve Nagell published:

$$|y| \le \frac{y_1\sqrt N}{\sqrt{2(x_1 + 1)}}.$$

For $x^2 - 2y^2 = 7$ that is $2\sqrt 7/\sqrt 8 = \sqrt{7/2} \approx 1.871$, so every family has a member with $y$ equal to $-1$, 0 or 1. Trying those three values of $y$ finds $x = 3$ twice and nothing for $y = 0$, since 7 is not a square. So there are at most two families, and there are exactly two if $(3, 1)$ and $(3, -1)$ are genuinely different.

They are, and the test is a divisibility. Two solutions $x + y\sqrt D$ and $x' + y'\sqrt D$ of the same norm $N$ lie in one chain exactly when their quotient is a unit, which after clearing the denominator comes to $N$ dividing both $xx' - Dyy'$ and $xy' - x'y$. For $(3, 1)$ and $(3, -1)$ those are $9 + 2 = 11$ and $-6$, and 7 divides neither. Two families, then, and the search is finished: the argument has turned “infinitely many solutions” into three trial values of $y$ and one divisibility check.

The figure’s arrows show the two chains leaving the box. The orange member $(3, -1)$ is carried by the unit to $(5, 3)$, the blue $(3, 1)$ to $(13, 9)$, and both land on the same branch further up — where the hyperbola has already grown too steep for the lattice points to be any help to the eye.

When a solution and its conjugate are the same family #

The two members of the box for $N = 7$ were conjugates, $3 + \sqrt 2$ and $3 - \sqrt 2$, and they turned out to be in different chains. That is not automatic.

For $x^2 - 7y^2 = 2$ the unit is $8 + 3\sqrt 7$, and Nagell’s bound works out to $3\sqrt 2/\sqrt{18} = 1$. The box contains $3 + \sqrt 7$ and $3 - \sqrt 7$, both of norm $9 - 7 = 2$. But the divisibility test says they are one family: $9 + 7 = 16$ and $-6$ are both even. And multiplying directly confirms it, since

$$(3 - \sqrt 7)(8 + 3\sqrt 7) = 24 + 9\sqrt 7 - 8\sqrt 7 - 21 = 3 + \sqrt 7.$$

The unit carries one conjugate onto the other. A solution and its conjugate lie in the same family exactly when their quotient $(3 + \sqrt 7)/(3 - \sqrt 7) = (3 + \sqrt 7)^2/2$ is a unit, and here it is, $8 + 3\sqrt 7$ on the nose.

What separates the two cases is the prime on the right. For $D = 2$, the prime 7 splits into two different factors, $(3 + \sqrt 2)(3 - \sqrt 2)$, that are not unit multiples of each other. For $D = 7$ the prime 2 is essentially a square: $2 = (3 + \sqrt 7)(3 - \sqrt 7)$ with the two factors equal up to a unit, because 2 divides the discriminant of $\mathbb{Z}[\sqrt 7]$. Number theorists say 7 splits in $\mathbb{Z}[\sqrt 2]$ and 2 ramifies in $\mathbb{Z}[\sqrt 7]$, and the vocabulary is the same one that decides which primes are sums of two squares, where 2 ramifies as $-i(1 + i)^2$ and a prime that is 1 more than a multiple of 4 splits.

The count is written in the factors of N #

Running the box search for every $N$ from 1 to 60 gives the grid above, and the pattern in it is sharper than it looks. The primes that have solutions are 2, 7, 17, 23, 31, 41 and 47, and each of the odd ones is 1 or 7 more than a multiple of 8. The primes 3, 5, 11, 13, 19, 29, 37, 43, 53 and 59 — 3 or 5 more than a multiple of 8 — have none. The squares of two of those, 9 and 25, reappear with one family each, and the square of the split prime 7, 49, has three.

The rule behind it has three clauses, one for each way a prime can behave:

• 2 contributes a factor of 1. It ramifies, $2 = (\sqrt 2)^2$, so its powers add no choice.
• A prime $p$ that is 1 or 7 more than a multiple of 8 contributes $e + 1$, where $p^e$ is its exact power in $N$. It splits into two conjugate factors, and $p^e$ can be made from them in $e + 1$ ways: all from one, all from the other, or any mixture.
• A prime that is 3 or 5 more than a multiple of 8 contributes 1 if $e$ is even and 0 if $e$ is odd. It does not split at all, so it can only appear as a whole power of itself, and an odd power is impossible.

Multiply the contributions and the result is the number of families. For $N = 49 = 7^2$ it is 3, from $7^2 = (3+\sqrt2)^2$, $(3 - \sqrt 2)^2$ and $(3 + \sqrt 2)(3 - \sqrt 2)$ — the last being $7$ itself, the solution $(7, 0)$. For $N = 18 = 2 \cdot 3^2$ it is $1 \times 1 = 1$, from $(6, 3)$. For $N = 3$ it is 0, and the reason can be checked by hand: if $x^2 \equiv 2y^2$ modulo 3 with $y$ not a multiple of 3, then 2 would be a square modulo 3, which it is not; so 3 divides both $x$ and $y$, and then 9 divides $x^2 - 2y^2 = 3$, which is absurd.

The figure’s counts were made by the box search and then compared, for every $N$ up to 200, with the product over prime factors — two computations that share nothing except the answer. And the bound is attained. At $N = 18$ the only family’s representative $(6, 3)$ sits exactly on the edge of Nagell’s box, at $|y| = 3$ with the bound equal to $2\sqrt{18}/\sqrt 8 = 3$, so the inequality has to be read as non-strict: a search that treats the edge as outside the box finds no family at all and contradicts the factorisation, which says there is one.

Which primes split, and why it is the same question as a square #

The split primes are those for which 2 is a square modulo $p$. That is the clause’s real content: if $p = x^2 - 2y^2$ then $x^2 \equiv 2y^2$ modulo $p$ and 2 is a square; conversely, if 2 is a square modulo $p$, a pigeonhole argument of the kind more things than boxes makes produces a small multiple of $p$ of the form $x^2 - 2y^2$, and the descent in $\mathbb{Z}[\sqrt 2]$ brings it down to $p$ itself. And whether 2 is a square modulo an odd prime is settled by the second supplement to quadratic reciprocity: exactly when $p$ is 1 or 7 more than a multiple of 8, the rule whose eight the two supplements explains, and which sits beside the reciprocity law counting one rectangle twice proves by counting lattice points.

So a question about a hyperbola has an answer made of remainders, and the remainders come from reciprocity. It is the same arrangement as Fermat’s theorem on two squares, where the circle $x^2 + y^2 = p$ has lattice points exactly when $p$ leaves remainder 1 on division by 4, and the two squares actually produced are found by running a Euclidean algorithm half-way. Circle and hyperbola behave identically here because both are norms from a ring of integers with unique factorisation — $\mathbb{Z}[i]$ for the circle, $\mathbb{Z}[\sqrt 2]$ for the hyperbola — and in both the count of solutions is a count of ways to assemble $N$ from the ring’s primes.

The one real difference is the unit. The circle’s ring has four units, $\pm 1$ and $\pm i$, so each factorisation gives four points and the count of lattice points is finite. The hyperbola’s ring has infinitely many, the powers of $1 + \sqrt 2$, so each factorisation gives a whole chain, and the finite object is the number of chains. Jacobi’s formula for points on a circle and the product rule above are the same theorem, divided in the first case by a finite group and in the second by an infinite one.

Families multiply as right-hand sides do #

The product rule suggests that families for 7 and families for 17 should combine into families for $7 \times 17 = 119$, and they do, explicitly.

The two families of 7 are represented by $3 \pm \sqrt 2$ and the two of 17 by $5 \pm 2\sqrt 2$, since $25 - 8 = 17$. Their four products are $19 \pm 11\sqrt 2$ and $11 \pm \sqrt 2$, and each has norm 119: $361 - 242 = 119$ and $121 - 2 = 119$. The divisibility test puts the four in four different families, and the box for 119 — with bound $\sqrt{119/2} \approx 7.7$ — contains representatives of exactly four. Every family of 119 is a product of a family of 7 and a family of 17, and none is left over.

This is Brahmagupta’s composition doing more than it was asked. It was introduced to combine near misses into better near misses; here it combines the solutions of two different equations into all the solutions of a third. The multiplication of norms that makes the chain for a single $N$ also assembles the families for composite $N$ out of the families for its prime factors, which is why the count is multiplicative.

It is also why the rule has to be stated prime by prime. The families of $49 = 7 \times 7$ are not “two times two”, because the products $(3 + \sqrt 2)(3 - \sqrt 2)$ and $(3 - \sqrt 2)(3 + \sqrt 2)$ are the same number: combining a prime with itself produces three families, not four, which is the $e + 1$ of the rule.

What the box and the grid cannot show #

The count from factorisation is special to rings like $\mathbb{Z}[\sqrt 2]$. It depends on unique factorisation, and most rings $\mathbb{Z}[\sqrt D]$ do not have it. In $\mathbb{Z}[\sqrt{10}]$ the prime 3 splits — 10 is a square modulo 3 — but $x^2 - 10y^2 = \pm 3$ has no solution, because modulo 5 it would make $\pm 3$ a square, and the squares modulo 5 are 0, 1 and 4. The factors of 3 exist as ideals and not as numbers — the same failure the integers a field contains meets from the other side, where the right ring is larger than the obvious one. The box search still works there; only the shortcut through factorisation fails, and what replaces it is the class group, which the figures here never need.

The figures draw only positive $N$ and only one branch. For negative $N$ the hyperbola’s branches are the other pair, Nagell’s bound takes a slightly different form, and the unit of norm $-1$, when it exists, trades solutions of $N$ for solutions of $-N$ — $1 + \sqrt 2$ carries $3 + \sqrt 2$ of norm 7 to $5 + 4\sqrt 2$ of norm $-7$. The branch $x < 0$ is the mirror image, $-u$ for every $u$, and adds nothing.

The log strip is exact but thin. It shows where each solution lies on the line and hides how large the numbers are: the solution $437 + 309\sqrt 2$ is the fourth blue dot in the row for 7, at a coordinate of about 6.78, and nothing in the picture says how large its coordinates are.

Still open: whether the shortcut works infinitely often #

The product rule for $D = 2$ rests on unique factorisation in $\mathbb{Z}[\sqrt 2]$, and the same rule works for any $D$ whose ring of integers has class number 1: then every ideal is generated by a number, and every factorisation of $N$ into ideals is a factorisation into numbers, which the unit then spreads into a chain.

Computations find class number 1 for most prime $D$. Among real quadratic fields with prime discriminant, Cohen and Lenstra’s heuristics predict about three quarters, and the tables bear that out as far as they go. But it is not known that infinitely many real quadratic fields have class number 1 at all. Gauss conjectured it in 1801. The imaginary side of the question — which $\mathbb{Q}(\sqrt{-d})$ have class number 1 — was settled in the 1960s with exactly nine fields, and the real side, where this essay’s chains live, remains open.

The difficulty is the unit itself. The class number formula ties the class number to the size of the fundamental solution — the class number times $\ln\varepsilon$ is about $\sqrt D$, up to a factor that grows no faster than a logarithm — and a large unit forces a small class number. Proving the class number is 1 infinitely often would mean proving the unit is large infinitely often in a precise sense, and nobody knows how to control the size of the fundamental solution that finely. How large that solution actually gets is a question with a great deal of data and very little theory.

A finite search where an infinite one was expected #

$x^2 - 2y^2 = 7$ has infinitely many solutions and they are all known after checking three values of $y$. The unit spreads each family into an infinite chain, the logarithm turns the chains into evenly spaced rows, one window of the line holds one member of each, and a window of the line is a bounded arc of the hyperbola that fits in a box.

When a symmetry acts on an infinite set of solutions, count the orbits, not the solutions — and look for a region every orbit must enter. The orbits here are the families; the region is Nagell’s box; and the number of orbits, once found, turns out to be written in the prime factors of $N$ in the same language that decides which primes are sums of two squares.

The same move settles questions that look unrelated. The orbit that must come back counts the states a map can be in rather than the steps it takes, and which primes a form takes shows where the move stops being enough: for $x^2 + 27y^2$ the representations of a prime are finite in number, but no congruence on the prime decides whether there are any. The count of families is always finite. Whether it can be read off remainders is the part that depends on the ring.