Five powers of two, seven more than a square

Subtract 7 from a power of two. From 8 that gives 1, a square. From 16, 9; from 32, 25; from 128, 121; all squares. From 32,768 it gives 32,761, which is $181^2$. In 1913 Srinivasa Ramanujan posed, in the Journal of the Indian Mathematical Society, the question whether these five — $n = 3, 4, 5, 7, 15$ — are the only powers of two that exceed a square by 7. Nobody answered for thirty-five years, and when Trygve Nagell did, in 1948, the answer was yes, and the proof went through a number system where seven has a square root.

The equation $2^n - 7 = x^2$ is a small, isolated problem with an unusual reach. Its proof is a model of how unique factorisation in a larger ring settles a question about ordinary integers. And the same five solutions, rewritten, answer a question from the theory of error-correcting codes: for which lengths a code that corrects two errors could be perfect.

Testing every exponent #

The first thing to do with such a question is to compute. For each $n$, form $2^n - 7$ exactly as a whole number, take its integer square root by Newton’s method in exact arithmetic, and check whether the root squared gives the number back. Doubles cannot do this past about $n = 53$, where the numbers outgrow their precision; exact integers can, and the check for every $n$ up to 10,000 — numbers with up to 3,011 digits — takes a fraction of a second. It finds exactly the five solutions and nothing else.

The hero shows the near misses. For each $n$ it measures how far $2^n - 7$ lies from the nearest square, as a fraction of the gap between the squares on either side, so that 0 means a square and $\tfrac12$ means as far from one as possible. The values look random, scattered between the two extremes, which is what one would expect if being a square were a matter of chance. Since the gap between consecutive squares near $2^n$ is about $2^{n/2+1}$, the chance that a random number of that size is a square is about $2^{-n/2}$, and the expected number of solutions beyond $n = 15$ is the sum of those chances, $2^{-8} + 2^{-8.5} + \cdots$, about 0.01. The heuristic predicts that solutions dry up quickly. It does not prove it, and the gap between 7 and 15 shows that the small cases are no guide to where the last solution lies.

A number system where 2 has factors #

Nagell’s proof begins by factorising $x^2 + 7$. Over the integers it does not factor, but in the complex numbers it is $(x + \sqrt{-7})(x - \sqrt{-7})$. The right setting is the ring of numbers

$$\frac{a + b\sqrt{-7}}{2}, \qquad a \equiv b \pmod 2,$$

the integers of the field obtained by adjoining $\sqrt{-7}$ to the rationals. In it the prime 2 is not prime: with $\alpha = (1 + \sqrt{-7})/2$ and its conjugate $\bar\alpha$, one has $\alpha\bar\alpha = 2$, since $(1 + 7)/4 = 2$.

And this ring has unique factorisation: every element factors into primes in only one way, up to the units $\pm 1$. That is a rare property. Among the rings built in this way from the square root of a negative integer, only nine have it — those for −1, −2, −3, −7, −11, −19, −43, −67, −163 — a list Gauss conjectured and that was completed by Heegner, Baker and Stark in the 1950s and 1960s. The class number measures how badly unique factorisation fails in the others, and for $-7$ it is 1.

Now suppose $2^n - 7 = x^2$ with $x$ odd and $n \ge 3$. Then

$$\frac{x + \sqrt{-7}}{2} \cdot \frac{x - \sqrt{-7}}{2} = \frac{x^2 + 7}{4} = 2^{n-2} = \alpha^{n-2}\bar\alpha^{\,n-2}.$$

The two factors on the left have no common prime factor, because any common factor would divide their difference $\sqrt{-7}$, and 7 does not divide a power of 2. Unique factorisation then forces each factor to be a unit times a power of one of the two primes: $(x + \sqrt{-7})/2 = \pm\alpha^{n-2}$ or $\pm\bar\alpha^{\,n-2}$. Comparing the $\sqrt{-7}$ parts, a solution needs the $\sqrt{-7}$ coordinate of $\alpha^{n-2}$ to be $\pm\tfrac12$.

The same move, made before #

Factoring an equation in a larger ring was an old idea by 1948. Euler used the numbers $a + b\sqrt{-2}$ to show that $y^2 + 2 = x^3$ has only the solution $5^2 + 2 = 3^3$, so that 26 is the only number squeezed between a square and a cube, a fact Fermat had claimed. Gauss’s integers $a + bi$ settle which primes are sums of two squares, by factoring $a^2 + b^2 = (a + bi)(a - bi)$. In each case the argument is the one above: two coprime factors whose product is a power, unique factorisation forcing each factor to be a power up to a unit, and a comparison of coordinates that leaves a much smaller problem.

The method’s weak point is the uniqueness. Euler’s argument for $y^2 + 2 = x^3$ is correct because the ring with $\sqrt{-2}$ factors uniquely; the same argument in a ring that does not, such as the one with $\sqrt{-5}$, gives wrong answers, and the history of attempts on Fermat’s last theorem includes a famous proof that silently assumed unique factorisation where it fails. A factorisation that hides its primes showed how factorisation can fail in a simple multiplicative system, and the fundamental theorem is exactly what the ordinary integers have that such systems lack. Nagell’s proof works because $-7$ is one of the nine lucky cases, and Euler’s convenient numbers are a related list of numbers $n$ for which the forms $x^2 + ny^2$ are similarly well behaved.

The sequence that decides it #

Write $\alpha^k = (a_k + b_k\sqrt{-7})/2$. Because $\alpha$ satisfies $\alpha^2 = \alpha - 2$, both coordinates obey the recurrence $b_{k+1} = b_k - 2b_{k-1}$, starting $b_1 = b_2 = 1$. The equation has reduced to a question about one integer sequence: for which $k$ is $b_k = \pm 1$?

The sequence runs 1, 1, −1, −3, −1, 5, 7, −3, −17, −11, 23, 45, −1, −91, −89, 93 and onwards. Its terms grow like $2^{k/2}$, since $|\alpha| = \sqrt 2$, while their signs wander because the angle of $\alpha$ is not a rational fraction of a turn. It returns to $\pm 1$ at $k = 1, 2, 3, 5$ and 13, and the figure’s exact computation to $k = 400$ finds no other. Each check is confirmed by the norm identity $a_k^2 + 7b_k^2 = 2^{k+2}$, which holds at every step. With $n = k + 2$ the five values give exactly the five solutions: $n = 3, 4, 5, 7, 15$.

The gap from 5 to 13 is where the large last solution comes from. By $k = 13$ the terms have reached the hundreds, and $b_{13} = -1$ is an accident of signs that cancel almost perfectly, the same kind of near-cancellation that makes $181^2$ fall exactly seven short of $2^{15}$.

Nagell’s proof that no further $\pm 1$ occurs expands $\alpha^k = ((1 + \sqrt{-7})/2)^k$ by the binomial theorem and reads the $\sqrt{-7}$ coefficient modulo powers of 7. The condition $b_k = \pm 1$ becomes a congruence on $k$ that can hold only for a few residue classes, and within those a second congruence modulo a higher power of 7 leaves only the five values. The argument is short, a page or two, once the ring is in place; the ring is what turns an equation in two unknowns with no visible structure into a statement about a single recurrence.

It is worth seeing how unlikely the five values are. Among the 387 terms computed after $b_{13}$, the smallest in absolute value is $b_{18} = 85$, and the next are 89, 91, 93 and then $b_{26} = 181$; the sequence’s typical size, $2^{k/2}$, outruns any chance of returning to 1 within a few dozen steps. The real content of Nagell’s proof is ruling out a return at very large $k$, where the sequence’s size makes such a return heuristically absurd but where nothing elementary forbids it. The congruence argument does that by showing that a return to $\pm 1$ at any $k$ would force $k$ into a residue class that, modulo a high enough power of 7, contains only the five known values.

Why congruences alone are not enough #

A natural first attempt avoids the ring altogether. If $2^n - 7$ is a square, it must be a square modulo every integer $m$, and the powers of two repeat modulo $m$, so each modulus rules out whole residue classes of $n$.

Ten moduli rule out most exponents below 120, but 12 survive: the five true solutions and seven others, 23, 27, 47, 67, 95, 103 and 115, at which $2^n - 7$ is a square modulo every one of the ten moduli and yet not a square. More moduli would rule out some of these and leave others, and there is no reason to expect any finite set of congruences to rule out every false candidate. A congruence sees only remainders; whether a number is a square depends on its size as well. Nagell’s proof uses congruences, but on the exponent of $\alpha$, after the ring has fixed the shape of every solution, and that is a different and much stronger use.

Seven is the exception #

Replace 7 by any odd $D$. For most $D$ up to 255 there is no exponent or just one; for $D = 1, 15, 23, 31, 63, 127, 255$ there are two, mostly because $D = 2^k - 1$ gives the trivial solution $2^k - D = 1$; and only $D = 7$ has five. Frits Beukers proved in 1981 that for every $D$ other than 7 the number of solutions is small and bounded explicitly, using the theory of how well algebraic numbers can be approximated by fractions.

The exceptionality of 7 has a reason the figures can point to. The proof for $D = 7$ needs both that the ring for $\sqrt{-7}$ factorises uniquely and that 2 splits in it into two primes. Among the nine rings with unique factorisation, 2 splits only in the one for $-7$; for the others it stays prime or is a square. So the argument that makes 7 tractable is the same coincidence that gives it more solutions than any other $D$: 2 has a factor $\alpha$ in that ring whose powers can come close to $\pm\tfrac12\sqrt{-7}$ more than once.

Triangular numbers and a perfect code #

Multiply $t(t + 1)/2 = 2^m - 1$ by 8 and add 1: it becomes $(2t + 1)^2 = 2^{m+3} - 7$. So the numbers one less than a power of two that are also triangular — written in binary as a run of ones — correspond exactly to the solutions of Ramanujan’s equation, and there are five of them: 0, 1, 3, 15 and $4{,}095 = 90 \cdot 91/2$.

The triangular form makes the result easy to state and hard to guess. The numbers $2^m - 1$ are 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, and among them the triangular ones are 1, 3, 15 and 4,095 — the last a surprise after a gap of eight, since 4,095 is the sum $1 + 2 + \cdots + 90$. In binary, 4,095 is twelve ones. A reader who checked the first dozen values by hand would find all five and might well conjecture that there are infinitely many; the theorem says there are no more, and that the twelve ones of 4,095 are the last run of ones that can be laid out as a triangle.

That last number is the surprising connection. A binary code of length $\ell$ that corrects two errors is perfect if the balls of radius 2 around its codewords exactly fill the space of all $2^\ell$ words. Each ball contains $1 + \ell + \binom{\ell}{2}$ words, so a perfect code needs that number to be a power of two. Multiplying by 8 and rearranging turns this into $(2\ell + 1)^2 = 2^{r+3} - 7$ — Ramanujan’s equation again. Its solutions give $\ell = 0, 1, 2, 5$ and 90. The first four are trivial or degenerate codes; the last is the famous length 90, where $1 + 90 + 4{,}005 = 4{,}096 = 2^{12}$ exactly, so the arithmetic allows a perfect two-error-correcting code of length 90 with $2^{78}$ codewords. The essay on perfect codes showed that no such code exists, by a counting argument on words of weight three. So the five solutions of a question Ramanujan asked as a curiosity are exactly the five lengths at which a perfect code of this kind passes the first test, and Nagell’s theorem is what guarantees no other length ever does.

Ten thousand exponents, then Nagell’s proof #

The search is complete only to $n = 10{,}000$ and the sequence only to $k = 400$; beyond that the pictures cannot see, and the statement that no solution exists there rests on Nagell’s proof, which is described here and not reproduced in full. The heuristic that solutions are rare, about one chance in a hundred of any beyond 15, is a heuristic: it treats $2^n - 7$ as a random number, which it is not. The census of other $D$ stops at $n = 300$, and Beukers’s theorem, not the census, bounds their solutions.

The heuristic deserves one more caution, because it has misled before, on equations met elsewhere among these essays. Sums with too few primes counted triples $a + b = c$ whose prime factors are unusually small, and the abc conjecture, which would bound them, implies at once that $2^n - 7 = x^2$ has finitely many solutions — but gives no way to find them. A heuristic count and a conjecture both point to finitely many; only the ring argument says which, and that is the difference between believing a list complete and knowing it.

Powers checked exactly, the ring argument quoted #

Computed here: $2^n - 7$ for every $n$ up to 10,000 in exact integers with integer square roots, finding exactly $n = 3, 4, 5, 7, 15$ and $x = 1, 3, 5, 11, 181$; the coordinates $a_k, b_k$ of $\alpha^k$ exactly to $k = 400$, with the norm $a_k^2 + 7b_k^2 = 2^{k+2}$ checked at every step and $b_k = \pm 1$ found only at $k = 1, 2, 3, 5, 13$; the congruence sieve for $n$ up to 120; the counts for every odd $D$ up to 255 and $n$ up to 300; and the triangular numbers, checked against $t(t+1)/2$.

Quoted: Ramanujan’s question of 1913 and Nagell’s proof of 1948; the classification of the nine imaginary quadratic fields with unique factorisation; Beukers’s bound; and the non-existence of the perfect code of length 90.

Still open: the generalised equation #

For which $D$ and which bases does $x^2 + D = p^n$ have more than a few solutions, and how many can it have at most? For base 2 Beukers’s work bounds the count for every $D$, but the best possible bound for $D \ne 7$ is not settled in every form of the question, and for odd prime bases $p$ in place of 2 the corresponding results are less complete. More broadly, the Ramanujan–Nagell equation is an instance of the problem of perfect powers in recurrence sequences — when a term of a sequence like $b_k$ equals $\pm 1$ or a perfect power — and the general theory, through Baker’s bounds on linear forms in logarithms, gives finiteness with bounds so large that a computer cannot close the gap. For Fibonacci numbers the perfect powers were found only in 2006, by Yann Bugeaud, Maurice Mignotte and Samir Siksek, using methods from the proof of Fermat’s last theorem; for most such sequences the question is still open.

The ring that closes the question #

$2^n - 7$ is a square only for $n = 3, 4, 5, 7$ and 15. Exact computation finds those five and no others up to $n = 10{,}000$; congruences cannot rule out every other $n$; and Nagell’s proof does, by factorising $x^2 + 7$ in the ring where $2 = \alpha\bar\alpha$ with $\alpha = (1 + \sqrt{-7})/2$, so that every solution is a power of $\alpha$ whose $\sqrt{-7}$ part is $\pm\tfrac12$ — which happens only at the exponents 1, 2, 3, 5 and 13. The same five solutions are the lengths at which a perfect two-error-correcting code passes the counting test, the last of them the impossible 90.