A root lifted one digit at a time

Multiplying on a dial splits it into cycles whose lengths grow by a factor of the prime as the dial runs up the powers of that prime. Roots of equations behave the same way, and far more usefully. On a dial of seven, $3 \times 3 = 9$, and nine leaves two on division by seven. So $3$ is a square root of $2$ on that dial, and so is $4$, since $4 \times 4 = 16 = 2 + 14$. Now ask the same question on a dial of forty-nine. There are forty-nine residues to try, and a search would try them all.

There is a better way, and it is the whole of this essay. Any square root of $2$ on the dial of forty-nine is, in particular, a square root of $2$ on the dial of seven — reducing both sides of $x^2 \equiv 2 \pmod{49}$ gives $x^2 \equiv 2 \pmod 7$. So it must be $3$ or $4$ plus a multiple of seven, and only fourteen candidates remain. Of the seven lifts of $3$, exactly one works, and it is $10$: $100 = 2 + 2 \times 49$. On the dial of $343$ exactly one of the seven lifts of $10$ works, and it is $108$. The roots do not have to be searched for at all. They are lifted, one power of seven at a time, and each lift is the solution of a linear equation.

Kurt Hensel made this into a theorem around 1900, and then into a number system. The lifts go on for ever, each one adding a digit on the left of the root’s base-seven expansion, and the infinite string of digits they build is a genuine square root of $2$ — not among the real numbers, but among the seven-adic numbers, where two numbers are close when their difference is divisible by a high power of seven.

A tree that never branches #

Search every residue on the dials of $7$, $49$, $343$ and $2401$ and draw the square roots of $2$ on each, joining each root to the root it reduces to on the dial one step smaller.

The tree has two trunks and no branches. On every dial there are exactly two square roots of $2$ — one reducing to $3$, one to $4$ — and the root on each dial determines the root on the next. The search checked every residue at every level; the regularity it found is what the theorem predicts. Notice also that the two trunks are negatives of each other on every dial: $3 + 4 = 7$, $10 + 39 = 49$, $108 + 235 = 343$, $2166 + 235 = 2401$. If $x$ squares to $2$, so does $-x$, and on a dial of odd size $x$ and $-x$ are never the same residue.

What the tree does not show is why each root has exactly one lift, and the reason is the most useful idea in the subject: to lift a root, solve the tangent-line equation.

The next digit is a tangent line #

Suppose $x_0$ is a square root of $2$ on the dial of $7^k$. The candidates on the next dial are $x_0 + t\cdot 7^k$ for $t = 0, 1, \ldots, 6$. Square one:

$$(x_0 + t\,7^k)^2 = x_0^2 + 2x_0\,t\,7^k + t^2\,7^{2k}.$$

The last term is a multiple of $7^{k+1}$ and can be ignored. So the condition for a lift is

$$x_0^2 - 2 + 2x_0\,t\,7^k \equiv 0 \pmod{7^{k+1}},$$

and since $x_0^2 - 2$ is already a multiple of $7^k$ — that is what it means for $x_0$ to be a root on the smaller dial — everything can be divided by $7^k$, leaving

$$\frac{x_0^2 - 2}{7^k} + 2x_0\,t \equiv 0 \pmod 7.$$

That is a linear equation for the single digit $t$, on the dial of seven. It has exactly one solution provided $2x_0$ is not a multiple of seven, because then $2x_0$ has an inverse on that dial and $t$ is determined. And $2x_0$ is not a multiple of seven: seven is odd, and $x_0$ is not a multiple of seven because $x_0^2 \equiv 2$. So every root has exactly one lift, at every level. The figures confirm it by trying all seven candidate digits and finding exactly one that works, the one the formula gives.

The quantity $2x_0$ is the derivative of $x^2 - 2$ at $x_0$, and the equation above is what Newton’s method does with it: replace the curve by its tangent line at the current guess, and solve the tangent line for the correction. The derivative was built to say how a function responds to a small change in its input. On a dial, “small” means “a multiple of a high power of seven”, and the derivative says how the function responds to that. Hensel’s lemma is Newton’s method in which nearness means divisibility. If the derivative at the root is not divisible by the prime, the root lifts uniquely; if it is, the lemma is silent and anything can happen.

The digits of a new number #

Record the lifts in base seven and a pattern appears that is invisible in base ten. Each lift keeps every digit the previous root had and adds exactly one more, on the left.

In base ten the lifts $3, 10, 108, 2166, 4567, \ldots$ look unrelated. In base seven they are $3$, $13$, $213$, $6213$, $16213$, and so on: each is the previous one with a digit prepended. That is simply what “a lift” means — the new root agrees with the old one on the smaller dial, so its last $k$ base-seven digits are the old root’s, and the new information is one digit further left.

Carried on for ever, the process builds an infinite string of digits running to the left, $\ldots 21216213$, with the property that its last $k$ digits square to $2$ on the dial of $7^k$ for every $k$. Hensel’s idea was to take that string seriously as a number. Strings of base-$p$ digits running infinitely to the left can be added and multiplied digit by digit with carries, exactly as whole numbers are, and they form a number system, the $p$-adic integers. In the seven-adic integers the string above is a square root of $2$, in the same sense that the decimal $1.41421\ldots$, with digits running infinitely to the right, is a square root of $2$ among the real numbers.

The two constructions are mirror images, and the mirror is the notion of distance. Among the real numbers, $1.41421$ is close to $\sqrt 2$ because their difference is small in size. Among the seven-adic numbers, $1802916$ is close to the root because their difference is divisible by $7^8$. Alexander Ostrowski proved in 1916 that these are the only two kinds of distance the rational numbers admit — size, and divisibility by one prime — so the real numbers and the $p$-adic numbers, one system for each prime, are all the ways there are of filling in the gaps between fractions.

Newton’s method, doubling the digits #

Newton’s method for a real square root doubles the number of correct decimal places at every step once it is close. The same happens seven-adically, and it is more dramatic, because each step is exact arithmetic on whole numbers.

The one-digit-at-a-time lifting of the previous figure is Newton’s method run with its correction truncated to a single digit. Run the full correction instead — $x \leftarrow x - (x^2 - 2)/(2x)$, with the division done on a dial of a large power of seven — and the agreement goes $1, 2, 4, 8, 16, 32$ digits. The reason is the one that makes Newton’s method fast among the real numbers: the error after a step is proportional to the square of the error before it, and squaring a number divisible by $7^k$ gives one divisible by $7^{2k}$. Quadratic convergence is a statement about how errors multiply, and it does not care whether error is measured by size or by divisibility.

Where the slope vanishes #

The lemma needs the derivative not to be divisible by the prime. For square roots, the derivative is $2x$, and there is exactly one prime that divides $2x$ for every $x$: the prime two. On dials that are powers of two, the tree of square roots behaves quite differently.

The square roots of $17$ show it. On the dial of two there is one, $1$. On the dial of four there are two, $1$ and $3$. On the dial of eight there are four: every odd number squares to $1$ on the dial of eight, and $17 \equiv 1$. Then the count stays at four, but the tree reshuffles at every level: on the dial of sixteen, the roots $1$ and $7$ each have two lifts and the roots $3$ and $5$ have none. The tangent-line equation has become $0 \cdot t \equiv$ something, which has either no solution or every solution, and the tree branches where it has every solution and dies where it has none.

There is a stronger form of the lemma that handles this. If the derivative at a root is divisible by exactly $p^e$, the root lifts provided the function vanishes there to one more than twice that power, $p^{2e+1}$. For square roots at the prime two, $e = 1$, so a root on the dial of eight lifts all the way up, and the consequence is clean: an odd number is a square in the two-adic integers exactly when it leaves remainder $1$ on division by $8$. Seventeen does, so it has two-adic square roots; $3$, $5$ and $7$ do not, and have no square roots on the dial of eight or any higher power of two.

A vanishing derivative, in both worlds #

The failure at two has an exact counterpart among the real numbers, and seeing the two side by side is the clearest way to understand what the derivative is doing in each. Newton’s method for a real root converges quadratically — doubling the correct digits — only when the derivative is not zero at the root. At a double root, where the curve touches the axis instead of crossing it, the derivative vanishes, the tangent line is flat, and the method slows to halving the error at each step: one correct binary digit per step instead of twice as many.

On a dial the same vanishing has a different symptom. The tangent-line equation for the next digit is $f'(x_0)\,t \equiv -f(x_0)/p^k \pmod p$, and when $p$ divides $f'(x_0)$ the coefficient of $t$ is zero on the dial of $p$. The equation stops determining $t$: either every digit works or none does. So where the real method slows down, the $p$-adic method loses uniqueness, and the tree branches or dies. In both worlds the cure is the same — look one order deeper, at how fast the function vanishes compared with its derivative — and in both worlds a root where the derivative vanishes is a root where the function is flatter than a line, so a small change in the input changes the output by much less than usual. Among the reals that makes the root hard to locate; on a dial it makes many residues equally good.

Which primes have a square root of two #

The seven-adic square root of $2$ exists because $2$ is a square on the dial of seven, and the lifting does the rest. The same is true at every odd prime: $2$ has a $p$-adic square root exactly when it is a square modulo $p$. Which primes those are is the second supplement to quadratic reciprocity: $2$ is a square modulo an odd prime $p$ exactly when $p$ leaves $1$ or $7$ on division by $8$ — so for $7$, $17$, $23$, $31$, $41$ and half of all primes, and not for $3$, $5$, $11$, $13$, $19$ and the other half. At those, $\sqrt 2$ has no $p$-adic existence at all.

So the real number $\sqrt 2$, which cannot be a fraction, has a $p$-adic counterpart at half the primes and none at the other half. The number $-1$ behaves similarly, with a square root at the primes that leave $1$ on division by $4$. Every rational number’s squareness is decided prime by prime in this way, and the $p$-adic numbers are the language in which “prime by prime” becomes a statement about a single object at each prime.

Counting roots on every dial #

The two behaviours — unique lifting at odd primes, a mod-eight condition at two — are clearest side by side, in a count of square roots on every prime-power dial.

Read down any column at an odd prime and the count is constant: $2$ if the number is a square on the dial of the prime itself, $0$ if it is not, and the same at every power above. So for odd primes the question “is $a$ a square modulo $p^k$?” is decided entirely on the dial of $p$ — which is the question quadratic reciprocity answers. The column for $3$ at the prime three shows the one exception, when the prime divides the number: $3$ has the single root $0$ modulo $3$, and none modulo $9$, because any multiple of three squares to a multiple of nine.

At the prime two the pattern is the mod-eight rule. Modulo $2$ every odd number is a square; modulo $4$ only those that leave $1$ are; from eight on, it has four square roots or none, according as it is $1 \bmod 8$ or not. The four roots are $\pm x$ and $\pm x + 2^{k-1}$, which is where the branching in the tree comes from: on a dial of a power of two, adding half the dial to a square root gives another square root, since $(x + 2^{k-1})^2 = x^2 + 2^k x + 2^{2k-2}$.

From every dial to the rationals #

The lifting argument has a consequence that runs the other way, and it is the reason the $p$-adic numbers became central to number theory rather than a curiosity. If an equation with whole-number coefficients has a solution in rational numbers, then clearing denominators it has solutions on every dial, and it has a real solution. So an equation that fails on some dial has no rational solution — a cheap and powerful obstruction. Combined with solving on several dials at once, it is how most “no solution” proofs in elementary number theory work.

Hensel’s lemma makes the obstruction checkable: an equation is solvable on every power of $p$ as soon as it is solvable on one small dial with a nonvanishing derivative, so “solvable on every dial” is decided by finitely many checks. The deep question is the converse — whether solvability on every dial and among the reals forces a rational solution. For quadratic equations it does: that is the Hasse–Minkowski theorem, proved by Helmut Hasse in 1921 and 1923 from Minkowski’s earlier work on quadratic forms. For cubic equations it does not. Ernst Selmer showed in 1951 that

$$3x^3 + 4y^3 + 5z^3 = 0$$

has solutions with $x, y, z$ not all zero on every dial and among the reals, and none in whole numbers. The local–global principle holds for squares and fails for cubes, and measuring how it fails is one of the central problems of modern number theory.

What the dials cannot show #

They cannot show the infinite number. Every figure stops at a finite power of the prime — the table at $7^8$, the tree at $7^4$, Newton’s method at thirty-two digits. The seven-adic square root of $2$ is the limit of all of them, and the figures show its first digits and the rule that produces the rest, not the number itself.

They cannot show why only two distances exist. Ostrowski’s theorem, that size and divisibility by a prime are the only ways to measure distance between fractions, is quoted, not drawn; nothing in a picture of dials rules out a third.

And they cannot show Selmer’s cubic failing. That $3x^3 + 4y^3 + 5z^3 = 0$ has no nontrivial whole-number solution is proved by an argument about the arithmetic of a cubic field, not by searching; a search, however long, would only fail to find one.

Still open: are the digits random #

The seven-adic digits of $\sqrt 2$ begin $3, 1, 2, 6, 1, 2, 1, 2$, and the decimal digits begin $1, 4, 1, 4, 2, 1, 3, 5$. Both expansions are infinite and never repeat, since $\sqrt 2$ is irrational. Whether either is normal — whether each digit appears, in the long run, one time in seven or one time in ten, and each block of digits with its fair share — is not known for either. It is not known for any algebraic irrational number in any base, real or $p$-adic. The digits are completely determined, each one computable by the lifting of this essay, and nobody can say whether they are evenly spread.

One digit, one linear equation #

A root of a polynomial on a dial of $p^k$ lifts to the dial of $p^{k+1}$ by solving a linear equation for one digit, and when the derivative at the root is not divisible by $p$ the lift is unique. For $x^2 = 2$ and $p = 7$ that makes a tree with two trunks and no branches, and the digits the lifts add build a seven-adic number, $\ldots 21216213$, whose square is $2$. Newton’s method run in the same arithmetic doubles the digits at every step.

At the prime two the derivative $2x$ always vanishes, the tree branches and dies, and an odd number is a two-adic square exactly when it is $1 \bmod 8$. Across all prime powers, the count of square roots is fixed at the prime itself for every odd prime. Solvability on every dial is necessary for a rational solution; for squares it is also sufficient, and for cubes, as Selmer’s equation shows, it is not.

When a problem can be solved approximately, ask what “approximately” means — divisibility is an approximation too, and with it Newton’s method builds new numbers.