The error that predicts itself

Pinned between two sequences followed Archimedes round the circle. Start with a hexagon inside it and a hexagon outside, double the number of sides, and double again; at every stage the circle lies between the two polygons, and the recursion that carries one stage to the next needs only square roots. Six doublings reach the 96-gon and the bracket $3\tfrac{10}{71} < \pi < 3\tfrac{1}{7}$, two correct decimals. The same essay priced the method honestly: the gap shrinks by a factor of about four at each doubling, a little more than half a decimal digit a step, and ten digits would need a polygon of tens of thousands of millions of sides.

That factor of four is the subject here. A gap that shrinks by a known factor is a gap whose future is known, and a sequence whose future is known need not be followed to the end. The polygons were computed for nineteen centuries by people who wanted the area of the circle and had in their hands, at every stage, enough information to predict the stages they had not yet reached. Some of them noticed. Liu Hui, commenting on the Nine Chapters in 263, saw that the slivers each doubling adds shrink by about a quarter. Willebrord Snell in 1621 found a combination of the inscribed and circumscribed perimeters far better than either. Christiaan Huygens in 1654 proved that these improvements are not guesses but bounds. Between them they turned the slowest of the classical calculations into one of the fastest, without drawing a single extra side.

Each doubling adds a quarter of the last #

The area of the regular $n$-gon inscribed in a circle of radius one is $A_n = \tfrac{n}{2}\sin(2\pi/n)$: $n$ thin triangles, each with two sides of length one meeting at the centre. The hexagon has area $2.598076$, the 12-gon exactly $3$, the 24-gon $3.105829$. Each doubling of the sides cuts a small triangle off every side and adds it — a sliver with its base on the old side and its apex on the arc.

The first doubling, hexagon to 12-gon, adds $0.401924$. The second adds $0.105829$, which is $0.263$ times the first. That is already close to a quarter, and the next ratios close in: $0.253$, $0.2508$, $0.2502$. Nobody needs to know why to make use of it. If every future sliver is a quarter of the one before, then all the slivers still to come after the last one drawn add up to

$$\tfrac14 + \tfrac1{16} + \tfrac1{64} + \cdots = \tfrac13$$

of the last one, and the area of the circle can be written down at once:

$$\pi \approx A_{2n} + \tfrac13\,(A_{2n} - A_n).$$

Applied to the 12- and 24-gons, which a careful person can compute by hand in an afternoon, this gives $3.141105$, closer to $\pi$ than the 96-gon’s area of $3.139350$ by a factor of four and a half, and closer than Archimedes’ whole bracket is wide. Applied to the 96- and 192-gons it gives $3.14159253$, seven correct figures. Liu Hui himself took the observation as a reason to add a fixed share of the last sliver; how exactly he rounded it is a matter for historians of his text, but the value he arrived at, $3927/1250 = 3.1416$, he checked against a polygon of 3,072 sides, and the check agreed.

The estimate is cheap because nothing in it is new information. It is the old information — two polygons that had to be computed anyway — read with one more fact about how they relate.

Why the ratio is a quarter #

The quarter has a reason, and the reason is the whole of what makes the trick work. The error of the inscribed polygon, $\pi - A_n$, can be expanded in powers of $1/n$ from the series for the sine:

$$\pi - A_n = \pi - \tfrac{n}{2}\sin\tfrac{2\pi}{n} = \frac{2\pi^3}{3n^2} - \frac{2\pi^5}{15n^4} + \cdots$$

The leading term is a constant over $n^2$. Doubling $n$ divides it by four, so the error of the $2n$-gon is a quarter of the error of the $n$-gon, plus a correction of order $1/n^4$ — and the sliver added in the doubling, being the difference of the two errors, inherits the same law. The ratio of successive slivers is therefore a quarter plus something of order $1/n^2$, and that something is positive, which is why the ratios approach a quarter from above.

So the number four is the 2 of the doubling raised to the 2 of the error’s exponent. It is not a property of circles specifically. Any computation whose error is a constant times $h^2$, for a step size $h$ that is being halved, will show the same ratio between successive improvements, and any such computation can be extrapolated the same way. The trapezium rule for an integral has an error proportional to the square of its step; the central difference for a derivative does too; so does a pendulum’s period computed from the small-angle formula as the amplitude halves. Each of them, run at two step sizes, contains a better answer than either.

The essay on turning a slow series geometric made the general point that every accelerator is a model of the error — geometric for Aitken, a power series in $1/n$ for Richardson — and succeeds exactly on the sequences whose errors have that shape. The polygons of the circle are the oldest case where the shape is known exactly, because it comes from the series of the sine. The extrapolation is Richardson’s, written out by Lewis Fry Richardson in 1911 for the solution of differential equations; the polygons had been carrying it for sixteen hundred years.

The third that a parabola explains #

There is a second way to see where the third comes from, and it is the one Huygens used, because it can be made into a proof without any series at all.

Take one side of the inscribed $n$-gon. The circle bulges beyond it in a thin segment, and the sliver that doubling adds on that side is the triangle inscribed in that segment, with its apex at the midpoint of the arc. The circle’s area is the polygon plus $n$ such segments, so everything depends on how the segment compares with its triangle. If the arc were a parabola, the comparison would be exact and old: Archimedes proved, in the Quadrature of the Parabola, that a parabolic segment is precisely $4/3$ of the triangle inscribed in it in this way, by an exhaustion with triangles inside triangles whose areas form the series $1 + \tfrac14 + \tfrac1{16} + \cdots$.

A short arc of a circle is very nearly a parabola — the two agree to second order at the top, and the segment flattens towards a parabolic one as the arc shortens. So the circle’s segment is very nearly $4/3$ of its triangle, and the circle is very nearly

$$A_n + \tfrac43\,(A_{2n} - A_n) = A_{2n} + \tfrac13\,(A_{2n} - A_n),$$

the same formula from a different direction. The ratio for the hexagon’s segment is $1.3522873$; for the 12-gon, $1.3379439$; for 384 sides, $1.3333378$. It is always larger than $4/3$, and that is the content of Huygens’s lemma: a circular segment smaller than a semicircle exceeds four-thirds of its inscribed triangle. With that lemma the estimate becomes an inequality,

$$\pi > A_{2n} + \tfrac13\,(A_{2n} - A_n),$$

a lower bound on the circle as rigorous as Archimedes’ and with an error a hundred times smaller at the 96-gon. Huygens proved it in De circuli magnitudine inventa, together with a matching upper bound, in 1654, with Euclid’s tools. The improvement was available to Archimedes himself, who had proved the parabola’s $4/3$ and had all the polygons; what he did not have was the habit of looking at the error as a quantity with a law of its own.

The comparison carries a small lesson about pictures. Stretching the figure upwards, as the drawing above does so that a sliver of a few hundredths can be seen at all, changes every area by the same factor and so changes no ratio. The circle becomes an ellipse and the parabola stays a parabola, and the claim — segment over triangle, a little above $4/3$ — survives the distortion intact.

Two digits become four, and four become six #

The plain polygons gain two digits for every tenfold increase in the number of sides: an error of $2\pi^3/(3n^2)$, about $20.7/n^2$. The extrapolated value cancels that leading term and is left with the next one, of order $1/n^4$, so it gains four digits per tenfold increase; measured, its error is $163.2/(2n)^4$ to four figures across the whole range, the constant $8\pi^5/15$ that the series predicts.

Nothing stops the trick being applied again. The extrapolated values have an error that is a constant over $n^4$, so doubling $n$ divides it by sixteen, and the same argument with sixteen in place of four gives a second step,

$$L'_{2n} = L_{2n} + \tfrac1{15}\,(L_{2n} - L_n),$$

whose error falls like $1/n^6$. From the 96-, 192- and 384-gons this gives π to within $8\times10^{-13}$, twelve decimals from three polygons that by themselves agree with π to three. A third step divides by sixty-three and leaves an error of order $1/n^8$, and so on: the table of repeated extrapolations is Romberg’s method for integrals, which Werner Romberg published in 1955 and which is still how a careful calculator integrates a smooth function on an interval. The essay on where to take the samples found that Gauss’s choice of points beats any evenly spaced rule; Romberg’s table is the best that can be done when the spacing is not a free choice, by reading the evenly spaced answers as a sequence whose errors are known.

The plot shows the steps as straight lines of increasing slope on logarithmic axes, and that straightness is the precondition of everything. An extrapolation is only as good as the model of the error behind it. Where the model is exact — the sine’s series, with its powers of $1/n^2$ and nothing else — each step removes one term and the line steepens by two. Applied to a sequence whose error has a different shape, the same formula removes nothing and can make matters worse: Aitken’s process, which assumes a geometric error, does almost nothing to the partial sums of $\sum 1/k^2$, whose error is $1/n$. The circle’s polygons are a case where the model is not a hope but a theorem.

The same trick on the perimeter #

Archimedes worked with perimeters rather than areas: the half-perimeters of the inscribed and circumscribed $n$-gons, $n\sin(\pi/n)$ and $n\tan(\pi/n)$, trap π between them. Their errors have the same shape and opposite signs. The inscribed half-perimeter falls short by $\pi^3/(6n^2)$ and the circumscribed one overshoots by $\pi^3/(3n^2)$, twice as much, to leading order, both read off from the series for the sine and the tangent in the way an error with an unknown in it described.

An overshoot twice the shortfall means that two parts of the lower value and one of the upper cancel the leading term exactly:

$$\pi \approx \tfrac13\left(2n\sin\tfrac{\pi}{n} + n\tan\tfrac{\pi}{n}\right),$$

with an error of $\pi^5/(20n^4)$, measured at $15.30/n^4$ against the predicted $15.301$. This is Snell’s rule, from his Cyclometricus of 1621, and Huygens again supplied the proof that the combination is an upper bound for every $n$. It uses one polygon rather than two consecutive ones: the inscribed and circumscribed figures of the same side count already contain the two estimates that the area method had to get from a doubling. The 96-gon read this way gives $3.1415928338$, off by two parts in ten million, where the same polygon read Archimedes’ way gives an interval seventeen ten-thousandths wide.

The weights two and one are familiar from somewhere else. Simpson’s rule for an integral is two parts of the midpoint rule and one of the trapezium rule, $(2M + T)/3$, and for the same reason: the midpoint rule’s error is minus one half of the trapezium rule’s, to leading order, so the two to one mixture cancels it and leaves an error two orders smaller. Snell’s inscribed side is the midpoint rule of the arc and his tangent the trapezium — one estimate from inside, one from outside, with errors in a known ratio — and his rule is Simpson’s, written for a circle a century before Simpson. The parabola stands behind both, as it stood behind Liu Hui’s third: Simpson’s rule is exact for parabolas, and the circle’s arc is a parabola to the order that the weights correct.

Old values, recomputed #

Each of the historical values can be recomputed from the polygon it came from, with modern arithmetic carrying sixty digits so that the only error left is the method’s.

Archimedes’ bracket is $3.141032 < \pi < 3.142715$. The extrapolation from the 96- and 192-gons lands within $1\times10^{-7}$ — closer than the 3,072-gon, which is off by $2\times10^{-6}$, though the 3,072-gon took five more doublings and five more square roots extracted to a dozen figures. Zu Chongzhi, around 480, gave $3.1415926 < \pi < 3.1415927$ and the fraction $355/113$, which is right to six decimals and was not found again in Europe for more than a thousand years. His book, the Zhui Shu, is lost, and how he got the bounds is not recorded. What can be said is that Liu Hui’s own inequality, $A_{2n} < \pi < A_{2n} + (A_{2n} - A_n)$, produces exactly those bounds when it is applied at 24,576 and 49,152 sides, and not at one doubling fewer, where its upper end is $3.14159272$. Either Zu worked with polygons of tens of thousands of sides, extracting a square root to sixteen figures for each doubling, or he had something better that went with the book.

The comparison makes the point of the whole story. The 96-gon is the same polygon in every row where it appears, and the digits it yields depend entirely on what its user knew about its error. Archimedes treated the error as unknown and bounded it. Liu Hui treated it as shrinking by a quarter and summed it. Snell treated it as two errors in the ratio two to one and cancelled them. Each successive piece of knowledge about the error was worth several digits, at no cost in arithmetic.

The other road went on. Ludolph van Ceulen reached thirty-five places in 1610 with plain doubling and a polygon of $2^{62}$ sides, and al-Kāshī two centuries earlier had reached sixteen with a polygon of $3 \cdot 2^{28}$ sides, the same man who found the sine of one degree by iteration. Christoph Grienberger, using Snell’s rule, passed van Ceulen’s digits in 1630 with far smaller polygons. Then Machin’s arctangent series of 1706, which converges at a fixed proportion a term, made the whole polygon enterprise a historical curiosity.

An estimate and a bound are different things #

There is a temptation to read Huygens as merely tidying up Liu Hui, and it should be resisted. An extrapolation is a prediction: it says what the sequence will converge to if the error keeps the shape it has shown so far. A bound is a guarantee that holds whatever the sequence does next. For the circle the two coincide, but only because a further fact — the segment always exceeds four-thirds of its triangle — was proved, and that fact is not obvious from any finite run of numbers. The ratios $1.352$, $1.338$, $1.334$ fall towards $4/3$ from above, but a table cannot rule out that some later ratio dips below.

The difference matters as soon as the method leaves the circle. Richardson extrapolation applied to a numerical integral of a function with a hidden kink, or to a sequence whose error has a $\log n$ in it, produces a confident number that is wrong, and the polygons’ tidy straight lines on a logarithmic plot are the exception rather than the rule. Practitioners therefore watch the ratios themselves: when the successive differences of an extrapolation table stop shrinking by the predicted factor, the model of the error has failed, and the extra digits it seemed to give are noise. In the polygons the ratios behave perfectly — the quarter is approached monotonically, the segment ratio falls monotonically — and that monotonicity is what Huygens’s proofs turn into inequalities.

The circle has a second guarantee that most applications lack. Its polygons can be computed exactly, as nested square roots, so the only error in the extrapolated value is the method’s. In a numerical integral or a differential equation the computed values carry rounding, and an extrapolation that subtracts nearly equal numbers and divides by fifteen or sixty-three magnifies it. Romberg’s tables run in double precision are good for about six or seven steps before the rounding catches up, and the steeper lines in the error plot would, in sixteen-digit arithmetic, bend flat at $10^{-16}$. Sixty digits put that floor out of sight.

What the extrapolation does not change #

None of this makes π any less transcendental, and none of it brings the circle closer to being squared. Every value in every row above is a finite expression in square roots of square roots of rational numbers — constructible, in the technical sense — and each is only an approximation; the extrapolation changes how fast the approximations improve, never whether one of them is exact. The lunes of the five crescents that can be squared are the opposite case: regions bounded by arcs whose areas are exactly polygonal because two multiples of π cancel. Here nothing cancels π; the extrapolation cancels only the leading term of an error, and an error with infinitely many terms is never cancelled in a finite number of steps.

Nor does extrapolation change the logic of the original dissection. The rings of a disc laid out straight make a triangle of base $2\pi r$ and height $r$, and the area is $\pi r^2$ whatever the speed at which anyone can compute π. What changed between Archimedes and Huygens was not the geometry but the attitude to the error. Archimedes’ error was a quantity to be trapped and made small; Liu Hui’s and Huygens’s was a quantity with structure, to be measured, modelled and subtracted. That second attitude is the one behind nearly every numerical method in use — the step-halving of an ordinary-differential-equation solver, the extrapolated tables of the integrators, the convergence acceleration that lets a physicist sum a perturbation series — and its first appearance is in the slivers of a polygon inside a circle.

The same attitude is what lets the length round an ellipse be written so accurately by Ramanujan’s formula: a cheap expression whose error is known to begin at a high power of the eccentricity, rather than an expensive one that is merely small. The ellipse’s perimeter, unlike the circle’s, has no exact expression at all in elementary terms, so there the knowledge of how the error behaves is not a shortcut to a number that could be had another way. It is the only way to have the number at all.

Still open: how much the polygons alone can give #

The polygons with $6\cdot 2^k$ sides form a sequence of algebraic numbers converging to π, and the extrapolation table built on them converges much faster, with every column’s error a known power of $1/n$. A natural question follows, which the historical calculators did not ask: among all the combinations of the first $k$ polygon areas with rational weights, which approximates π best, and how fast can such combinations converge? Romberg’s weights are optimal for removing terms of an expansion one at a time, but the expansion of $\pi - A_n$ is an alternating series in $1/n^2$ with known coefficients, and weights tuned to those coefficients can do better at a fixed $k$. How much better is a question about the sine’s series rather than about circles, and the answer, as far as the polygons are concerned, is less written down than its age would suggest.

The deeper version asks how close an algebraic number of a given degree and size can be to π, a question in the theory of transcendence. For fractions it is the irrationality measure: Kurt Mahler showed in 1953 that $|\pi - p/q|$ cannot fall below $q^{-42}$ for large $q$, an exponent Doron Zeilberger and Wadim Zudilin brought down to about $7.10$ in 2020, while the truth is believed to be $2$. For algebraic numbers of higher degree the corresponding transcendence measures are known and are much further still from what is believed. The polygon values are a family of algebraic numbers of steadily rising degree, and how efficient they are in that sense — measured against the best possible approximation of each degree, rather than against the number of sides — is a comparison nobody seems to have made.