A denominator that reaches past the radius

The series $x - \tfrac{x^2}{2} + \tfrac{x^3}{3} - \cdots$ is the logarithm $\ln(1+x)$, and it is only the logarithm for $|x| < 1$. Beyond that its terms grow, the partial sums swing further from the curve with every term added, and no number of terms computes $\ln 4$.

Moving the centre was one answer: expand about a point nearer to where the value is wanted, and walk the series out one overlapping disc at a time. That answer changes where the information is taken from. There is a second answer that takes exactly the same information — the coefficients at nought — and changes only what is built from it.

The quotients are Padé approximants, and the reason they work is not that a quotient is more flexible in some vague sense. It is a specific thing a quotient can do and a polynomial cannot: vanish in the denominator.

As many conditions as unknowns #

A Padé approximant of order $[m/n]$ is a quotient $P(x)/Q(x)$, with $P$ of degree at most $m$, $Q$ of degree at most $n$, and $Q(0) = 1$, whose own series agrees with the function’s series for as many terms as possible. There are $m + 1$ coefficients in $P$ and $n$ free ones in $Q$, so $m + n + 1$ conditions can be imposed: agreement through the term in $x^{m+n}$.

The conditions are linear, which is the whole reason the construction is practical. Multiply through by $Q$ and the requirement becomes $Q(x)f(x) - P(x) = O(x^{m+n+1})$. The coefficients of $x^{m+1}$ to $x^{m+n}$ in that product involve only $Q$, since $P$ has no terms that high, so they are $n$ equations for the $n$ unknowns of $Q$. Then $P$ is read off the lower terms.

The smallest non-trivial case can be done in a line. The series of $\ln(1+x)$ starts $0 + x - \tfrac12 x^2$. For $[1/1]$, $Q = 1 + qx$, and the coefficient of $x^2$ in $Q f$ is $q - \tfrac12$, which must vanish; so $q = \tfrac12$, and $P = x$. The approximant is

$$\frac{x}{1 + x/2} = \frac{2x}{2 + x}.$$

It uses the three numbers $0$, $1$ and $-\tfrac12$, which are exactly the numbers the Taylor sum of degree two uses. At $x = 1$ the Taylor sum gives $0.5$ and the quotient gives $2/3$, against $\ln 2 = 0.693$. At $x = 3$ the Taylor sum gives $3 - 4.5 = -1.5$ and the quotient gives $6/5 = 1.2$, against $\ln 4 = 1.386$. Same information, arranged differently, and one arrangement is already usable where the other has stopped meaning anything.

Why a polynomial cannot do it #

A polynomial is finite everywhere and has no singularities, and the Taylor sums of $\ln(1+x)$ are polynomials trying to approximate a function that has one, at $x = -1$.

The radius is the distance to that singularity, measured in the plane, and it is the same in every direction. So the singularity on the left at $-1$ decides what happens on the right at $3$: a polynomial approximation built at nought is constrained to a disc, and a disc does not know that the trouble is on only one side. The sums fail at $x = 3$ not because anything is wrong at $3$ but because $3$ is further from nought than $-1$ is.

A quotient has a way out. Its denominator can vanish, and where it vanishes the quotient blows up — which is precisely what the function does at a pole. So a quotient can place a pole on or near the function’s singularity and absorb it there, and once the singularity is accounted for nothing ties the approximation to a disc any more.

The clearest demonstration is a function that is a quotient.

That $[2/2]$ approximant is $1/(1+x^2)$ itself: the linear system finds $Q = 1 + x^2$ and $P = 1$, and the poles land exactly on $\pm i$. The Taylor sums were never going to get there, because no polynomial has a pole; the quotient needed only to find the denominator, and five coefficients were enough to determine it.

Five coefficients that know where the pole is #

How five numbers located a pole at $\pm i$ is worth seeing, because it says what the denominator’s equations really are. The coefficients of $1/(1+x^2)$ are $1, 0, -1, 0, 1, 0, \ldots$, and they obey a rule: each is minus the one two places before. Written as $c_k + c_{k-2} = 0$, that rule is the identity $(1 + x^2)f(x) = 1$, read off one power of $x$ at a time. The linear system for $Q$ asks exactly this question — which short list of multipliers makes the coefficients satisfy a fixed recurrence beyond some point — and a recurrence of that kind is a denominator written sideways.

The general version is a theorem. A function whose only singularities inside some disc are $n$ poles has coefficients that are, far enough out, dominated by those poles: a pole at $a$ contributes a term like $A\,a^{-k}$ to the $k$-th coefficient, times a polynomial in $k$ if the pole is repeated. A sequence assembled from $n$ such geometric pieces satisfies a linear recurrence with $n + 1$ terms, and the roots of that recurrence’s characteristic polynomial are the reciprocals $1/a$. The approximants of order $[m/n]$, with $n$ equal to the number of poles, solve for that recurrence approximately; as $m$ grows their poles converge to the function’s poles and the approximants converge to the function throughout the disc, the poles themselves excepted. That is de Montessus de Ballore’s theorem, from 1902.

The denominator is the recurrence the coefficients eventually obey, and finding it is the same act as locating the poles. It is the rational counterpart of reading a sequence’s growth off its generating function’s nearest singularity: the same information, read in the other direction — from the coefficients to the singularity — and turned into something that can be evaluated at a point.

For a simple pole the whole thing can be done by hand. The coefficients of $1/(1-2x)$ are the powers $2^k$, each twice the one before. The recurrence $c_k - 2c_{k-1} = 0$ is the denominator $1 - 2x$, and the approximant of order $[0/1]$ is the function exactly. The Taylor sum of degree $N$ at $x = 1$, outside the radius of one half, is $2^{N+1} - 1$, and the function there is $-1$: every additional term doubles an error that was already the wrong sign.

The example is special in one way — the function is rational — and ordinary in the way that matters. For a function that is not a quotient, the approximant cannot land its poles on a singularity it cannot reproduce exactly. What it does instead is the most interesting thing in the subject.

The poles line up along the cut #

The logarithm’s singularity at $-1$ is not a pole. It is a branch point, and continuing $\ln(1+z)$ around it changes its value by $2\pi i$, so the function cannot be made single-valued on the plane without cutting it along a ray — conventionally everything to the left of $-1$.

A quotient of polynomials has poles and nothing else, so it cannot have a cut. What the diagonal approximants do is build one out of poles.

No pole leaves the real axis and none lands to the right of $-1$. As the order grows, the poles crowd towards $-1$ and spread out along the ray, and in the limit they fill it. The denominator is imitating the cut by standing poles along it, and everywhere off the cut — including all of the real axis to the right of $-1$, including $x = 3$ and $x = 100$ — the approximants converge.

The positions are not arbitrary, and the reason they are what they are is the connection the subject is best known for. The logarithm can be written as an integral,

$$\frac{\ln(1+x)}{x} = \int_0^1 \frac{dt}{1 + xt},$$

and approximating that integral by a weighted sum of $n$ values of the integrand gives $\sum_i w_i/(1 + x t_i)$ — a quotient of polynomials with poles at $x = -1/t_i$. If the sample points $t_i$ and weights $w_i$ are those of Gaussian quadrature on $[0, 1]$, the rule integrates every polynomial of degree up to $2n - 1$ exactly, and expanding $1/(1+xt)$ in powers of $x$ shows that this is exactly the statement that the sum matches the series through $2n$ coefficients. So the Padé approximant of order $[n/n]$ is $x$ times the $n$-point Gaussian quadrature of that integral, and its poles are at minus the reciprocals of the Gauss nodes. The figure finds the poles as roots of the exact denominator and, separately, finds the nodes by Newton’s method on Legendre’s recurrence, and the two lists agree.

The nodes are the roots of the Legendre polynomials, which are what Gram–Schmidt manufactures from the powers of x under the product $\int_{-1}^1 fg$. A question about extending a logarithm past its radius and a question about straightening a basis of polynomials have the same answer, and it is a set of points that has been known since 1814.

The same coefficients, spent twice #

The comparison worth making is not between an approximant and a Taylor sum of the same degree. It is between the two ways of spending the same coefficients: the $[n/n]$ approximant uses $2n + 1$ of them, exactly as many as the Taylor sum of degree $2n$.

The factor of nine is not a coincidence of the drawing. For a function of this kind the error of the diagonal approximants shrinks geometrically, at a rate fixed by how far the point is from the cut in a sense that the cut itself defines. At a point $x$ on the positive axis the rate per order is $\bigl((\sqrt{1+x}+1)/(\sqrt{1+x}-1)\bigr)^2$. At $x = 3$ the square root is $2$, the ratio is $3$, and its square is $9$ — which is what the ten measured errors settle on.

The formula also says what happens far away. At $x = 100$ the square root is a little over $10$, the rate per order is about $1.49$, and the approximants still converge — slowly, but at a point a hundred times beyond the radius, where the Taylor series’ hundredth term is larger than $10^{197}$. And it says the rate only degrades as $x$ approaches the cut, never as it merely grows.

Inside the radius too #

The case for the quotient is not only that it goes where the series cannot. Where both converge, it spends the coefficients better.

The Taylor sum at $x = 0.5$ gains two terms per order, each term about a quarter of the size of the one two before, so a factor of four per order is what it can manage. The approximant’s rate from the same formula is about $98$, and the measured sequence is approaching it. Sixteen coefficients buy seven digits one way and sixteen the other.

That is the practical version of the whole story, and it is why rational approximation is used in numerical libraries for functions like the exponential of a matrix, where the coefficients are cheap and each evaluation of the approximant is a linear solve. The series is the source of the information; how that information is turned into a number is a separate decision, and the polynomial is not the only candidate.

When there is nothing to imitate #

The poles of an approximant are where it spends its extra freedom, so a function with no singularities at all is a good test of whether the freedom is being wasted.

For the exponential, whose Taylor series converges everywhere, the diagonal approximants still exist and still beat the Taylor sums of the same size — their poles simply move away from the origin as the order grows, off into the complex plane, where they do no harm on any bounded region. The quotient does not invent singularities the function lacks. It keeps them at a distance that grows with the order, which is the rational version of the Taylor series’ infinite radius.

Those approximants to $e^x$ have a history out of proportion to their size. Hermite used rational approximations to exponentials in 1873 to prove that $e$ is transcendental — the first number shown to be so that was not built for the purpose — and the proof works by showing the approximations are too good for $e$ to satisfy any polynomial equation with whole-number coefficients. The same objects that are computationally convenient turned out to encode an arithmetic fact.

A method of approximation is also a source of inequalities, and inequalities are what arithmetic proofs are made of. Approached too fast to be algebraic is the same mechanism with fractions in place of rational functions.

Where the method needs care #

The approximant need not exist in the form asked for. For $1/(1+x^2)$ there is no approximant of order $[1/1]$ with $Q(0) = 1$: its coefficient of $x$ is nought, the linear system is singular, and the figure above uses $[2/2]$ for that reason. The general theory arranges approximants in a table and handles the missing entries, which occur in square blocks.

Noise in the coefficients produces false poles. If the coefficients are measured or rounded, the approximant can acquire a pole and a zero almost on top of each other, cancelling except in a tiny neighbourhood — a Froissart doublet. It is harmless away from itself and catastrophic near it, and it is why the figures here solve for the denominators in exact rational arithmetic. For the logarithm the linear system is a close relative of the Hilbert matrix, and in double precision it has lost most of its digits by order eight.

Convergence is not uniform in general. For functions whose singularities are poles, the diagonal approximants converge in a weaker sense — outside sets that can be made as small as wanted, but whose position can wander — and spurious poles can appear anywhere for a few orders before moving off. The clean picture of poles lined up on a cut belongs to functions built as integrals like the one above, and for those it is a theorem. For functions with several branch points the cuts the approximants choose are the ones of least capacity, which need not be the ones anybody would draw.

There is no remainder formula. A Taylor sum comes with an error term that has one unknown in it, and replacing the unknown by its worst case gives a guaranteed bound from the derivatives alone. Nothing of the kind exists for a general quotient: the error of an approximant depends on how well its poles have imitated singularities it cannot see, and the coefficients used to build it do not say. What practice does instead is compare consecutive orders and treat their agreement as evidence — a reasonable heuristic that a Froissart doublet can fool, since two orders can agree everywhere except near a false pole that only one of them has. For functions defined by integrals like the logarithm’s there are guaranteed bounds, because at a positive $x$ two neighbouring sequences of approximants close in on the true value from opposite sides and bracket it — but that is a property of the function, not of the method.

And the approximant does not know where the function is defined. On the cut itself the approximants do not converge to anything sensible, and nothing about a single approximant warns that a point is near a cut rather than merely near a pole.

Padé’s table, and the integrals behind it #

The approximants are older than the name. Jacobi and Cauchy wrote down rational interpolants; Frobenius studied the systematic arrangement of approximants by numerator and denominator degree in 1881; Hermite used them for the exponential in 1873. Henri Padé’s thesis of 1892 organised them into the table that bears his name and studied its structure, including the blocks of repeated entries.

The connection to integrals and continued fractions is Stieltjes’, in the work of 1894 that also founded the moment problem. He showed that functions given by integrals of the form above have continued-fraction expansions whose truncations are exactly the diagonal approximants, and that their poles interlace and lie on the support of the integral — which is the lined-up picture, proved thirty years before anybody could have drawn it.

That order of events is common in analysis and worth noticing. The objects were computed for a century before anybody could say which functions they converge for, and the answer, when it came, was a statement about where the function’s singularities are rather than about the approximants.

What an overlapping curve hides #

In the opening figure the two quotients lie on top of the logarithm, and that is the point of the figure and its limitation. An error of $3\times10^{-4}$ is a fraction of a pixel, so the drawing can distinguish a method that works from one that fails and cannot distinguish two that work. The rate figures exist because the curves could not show it.

The pole figure shows a window of the ray, and the approximants’ outermost poles lie beyond it: the drawing shows that the poles are on the cut and cannot show them filling it, which is the claim about the limit.

And nothing here shows the function’s other values. Past the cut the logarithm continues onto further sheets, differing by multiples of $2\pi i$, and the approximants — being single-valued — see only the sheet they were built on. The walk around the singularity that reaches the other sheets is a different construction, and no quotient of polynomials performs it.

Still open: a series with no radius at all #

Everything here assumed the series converges somewhere. Some do not converge anywhere except at nought — their coefficients grow like factorials — and they arise constantly: as expansions of integrals, of solutions to differential equations, of quantities in physics. Such a series has radius zero, so every method that reads a function off its disc of convergence says there is nothing to read.

A series that converges nowhere takes up that case, and it turns out to be a case where the Taylor sum is excellent if it is stopped at the right place, and where the Padé approximants — which need only coefficients, not convergence — converge anyway. Laurent series, which allow negative powers and describe a function around a singularity rather than avoiding it, are the other direction the same question points, and the equation a sequence satisfies is where the location and kind of a singularity turn into the growth of the coefficients.

Changing the form, not the centre #

The move here is worth separating from the mathematics, because it applies well beyond series.

The Taylor series failed at $x = 3$ and there were two responses. One changed where the information came from — a new centre, new derivatives, a walk of discs. The other kept the information and changed what was built from it. The second is cheaper, since the coefficients were already known, and in this case it was also better, since it reached every point off the cut at once rather than one disc at a time.

When an approximation fails, ask whether it is the information or the form that is inadequate. A polynomial through evenly spaced points failed because of where the points were, which was the information; a polynomial built from coefficients at nought failed because it was a polynomial, which was the form. The two failures look identical on a graph, and the repairs are completely different.