The zeros a partial sum cannot avoid

The essays before this one asked how well a Taylor polynomial approximates its function: how much one point determines, how fast the error falls, where the radius of convergence comes from, why interpolation can be made to converge on an ellipse where a Taylor series converges only on a disc. Every one of those questions measured the gap between the polynomial and the function. This one asks something the gap does not show at all: where the approximating polynomials are zero.

For the exponential the question has a sharp edge. The function $e^z$ is never zero anywhere in the complex plane — it is the curve that is its own slope, and its values are all powers of $e$. But its partial sums

$$s_n(z) = 1 + z + \frac{z^2}{2!} + \cdots + \frac{z^n}{n!}$$

are polynomials of degree $n$, and a polynomial of degree $n$ has $n$ zeros. The partial sums converge to $e^z$ everywhere, uniformly on every bounded region, so the zeros cannot stay in any bounded region — they must run away to infinity as $n$ grows. The question is how they run, and the answer is a single curve.

Zeros found in exact arithmetic #

Finding the zeros is harder than it looks, and the difficulty is instructive. The scaled polynomial $s_n(nw)$ has coefficients $n^k/k!$, which for 80 terms range over more than thirty orders of magnitude, and near the left end of the curve the polynomial’s value at a zero is the cancellation of terms of size $e^{0.56n}$ — some $10^{19}$ at $n = 80$. Ordinary floating-point arithmetic, with sixteen digits, cannot see a zero there at all. So the zeros in the figure are computed by Aberth’s method, which refines all $n$ approximations at once, in fixed-point arithmetic carried to 80 or 110 decimal places, until no zero moves by more than $10^{-25}$.

Aberth’s method deserves a sentence of its own, because it is the reason the computation is feasible. Newton’s method finds one zero at a time and must then divide it out, which spoils the remaining polynomial’s coefficients. Aberth’s iteration, published by Oliver Aberth in 1973, moves all $n$ guesses together: each takes a Newton step corrected by a repulsion from all the others, $\Delta_i = \frac{p/p'}{1 - (p/p')\sum_{j \ne i} 1/(w_i - w_j)}$, so that two guesses cannot converge to the same zero. Started on a circle, the guesses spread out, find their zeros, and then converge with the number of correct digits roughly tripling each round. With exact enough arithmetic it never fails on polynomials like these, and the figure’s 80 zeros at $n = 80$ took a few hundred rounds.

Divided by $n$, the zeros of the four partial sums lie in rings around the same egg-shaped curve. The curve is

$$|w\, e^{1-w}| = 1, \qquad |w| \le 1,$$

found by Gábor Szegő in 1924. It passes through $w = 1$ at a corner, and its left tip is at $w = -0.27846\ldots$, the negative real number with $-w e^{1-w} = 1$, which is $-W(1/e)$ in terms of Lambert’s function. Every zero lies just outside the curve, and as $n$ doubles from 10 to 80 the ring of zeros tightens towards it. The partial sums of the exponential are zero along an egg that grows in proportion to $n$.

Two sizes that have to tie #

Why that curve? A partial sum can only vanish where it is far from the function it approximates, and how far it is depends on whether the series has finished its work. For real $x$ the figure measures the size of $s_n(nx)$ on a logarithmic scale, divided by $n$ so that different $n$ can be compared. The values are computed exactly: at a rational point $x = m/64$, the sum $s_n(nx)$ is a ratio of whole numbers, and its logarithm can be read off its digits however much cancellation the terms suffer.

Between the tip and 1 the curves settle on the line $x$, which is $\frac1n \ln e^{nx}$: there the partial sum has converged and is essentially the exponential. Outside that interval they settle on $1 + \ln|x|$, which is $\frac1n$ times the logarithm of the largest term $(n|x|)^n/n!$, by Stirling’s formula. There the partial sum is dominated by the terms near its end, because the series needs more than $n$ terms to converge at $nx$: the terms $(nx)^k/k!$ are still growing when the sum stops.

The two descriptions agree at exactly two points of the real line, $x = 1$ and the tip $x = -0.27846$, and the second is where the dip is: for odd $n$ the partial sum, positive at nought and negative far to the left, crosses zero there. In the complex plane the same contest is between $|e^{nw}| = e^{n\operatorname{Re} w}$ and $|nw|^n/n! \approx e^{n(1 + \ln|w|)}$, and they tie exactly when $\ln|w| + 1 - \operatorname{Re} w = 0$ — when $|w e^{1-w}| = 1$. Szegő’s curve is the set of points where the exponential and the terms the partial sum has not reached are the same size, and only there can they cancel.

How far outside the curve #

The contest can be refereed more precisely. Write $s_n(nw) = e^{nw} - R_n(nw)$, where the remainder is the tail of the series. Near the curve the tail is dominated by its first term, multiplied by a geometric factor: $R_n(nw) \approx \frac{(nw)^{n+1}}{(n+1)!} \cdot \frac{1}{1 - w}$. A zero is where the two sides are equal in size, and taking logarithms, with Stirling’s formula for the factorial, turns that into

$$n \ln|w\, e^{1-w}| - \ln|1 - w| + \ln|w| \approx \tfrac12 \ln(2\pi n).$$

The figure evaluates the left side at every computed zero. For each $n$ the values span a range of less than a hundredth, and they sit on the prediction: at $n = 80$ they lie between 3.113 and 3.121 against $\tfrac12\ln(160\pi) = 3.110$; at $n = 10$, where the approximations are cruder, they lie at 2.13 against 2.07. Every zero sits on one level curve of a single function, chosen by nothing but a comparison of sizes.

That says how far outside Szegő’s curve the zeros lie. The left side is $n$ times the logarithm of $|we^{1-w}|$, so on the zeros that logarithm is about $\ln(2\pi n)/(2n)$, a positive number that shrinks like $(\ln n)/n$. The zeros approach the curve from outside, and slowly: at 80 terms they are still about four hundredths beyond it. Near $w = 1$ the factor $|1 - w|$ becomes small and the correction grows, which is why the zeros thin out towards the curve’s corner and leave a visible gap there in the first figure: near the corner they approach more slowly, a refinement Albert Edrei, Edward Saff and Richard Varga worked out in detail in 1983.

Half an exponential at the corner #

The corner of the curve, at $w = 1$, is where the partial sum stops at exactly the point where the terms are largest: $s_n(n)$ adds the terms $n^k/k!$ up to $k = n$, the peak. Dividing by $e^n$ turns the terms into the probabilities of a Poisson distribution with mean $n$, and $e^{-n}s_n(n)$ is the chance that such a count is at most its mean. By the central limit theorem that chance tends to one half, and so at the corner the partial sum is half the exponential. Ramanujan posed exactly this in 1911: he asked for the number $\theta_n$ with $e^n/2 = s_{n-1}(n) + \theta_n n^n/n!$, and conjectured that $\theta_n$ lies between $\tfrac12$ and $\tfrac13$ and tends to $\tfrac13$. Szegő proved it in 1928, using the same comparison of sizes that drew his curve.

Donald Newman and Theodore Rivlin showed in 1972 what happens on a small scale around the corner: there $s_n(nw)/e^{nw}$ follows the complementary error function of the bell curve, so the transition between “converged” and “not yet converged” has width about $1/\sqrt n$ and the shape of a normal tail. That is why the zeros thin out near the corner — the partial sum is a sizeable fraction of the exponential there, not a small remainder against it, and cancellation needs the zeros to keep their distance.

The one real zero #

The real line is where the approach can be watched most precisely. An even partial sum of the exponential has no real zero — it is positive for every real $x$, a fact that can be proved by noticing that its minimum, where $s_n'(x) = s_{n-1}(x) = 0$, equals $x^n/n! > 0$. An odd one has exactly one, and the figure finds it for every odd $n$ in steps of four from 5 to 201, by bisection on the exact sign of $s_n$ at rational points: forty halvings, each deciding the sign of a whole number with thousands of digits.

Divided by $n$, the real zeros fall towards the tip from outside: $-0.436$ at $n = 5$, $-0.310$ at 29, $-0.289$ at 101 and $-0.284$ at 201, still six thousandths short of $-0.27846$. The line through them is the prediction from the balance above, solved along the real axis to first order, and from $n = 29$ on it agrees with the computed zeros to a few parts in ten thousand. The slow approach is the $(\ln n)/n$ of the previous section, seen at a single point: halving the distance to the tip needs a little more than doubling $n$.

The same comparison explains why no zero ever falls inside the curve. Inside it the partial sum is the exponential plus a remainder smaller than the exponential, and a function that differs from a zero-free one by less than that one’s own size has no zeros either — Rouché’s theorem — so all $n$ zeros must lie outside, which is what every figure shows.

Jentzsch’s theorem: a series with a finite radius #

The exponential converges everywhere, which is why its zeros escape to infinity and must be scaled down to be seen. A series with a finite radius of convergence behaves differently, and the theorem that describes it is older. Robert Jentzsch proved in 1916 that for any power series with radius of convergence 1, every point of the unit circle is a limit of zeros of the partial sums. The zeros cannot escape and cannot stay strictly inside — inside the disc the partial sums converge to the function, which has only finitely many zeros in any smaller disc — and so they pile up on the circle, all of it.

The figure takes the series $z + z^2/2 + z^3/3 + \cdots$ of $-\ln(1 - z)$, which converges inside the unit disc and diverges outside, and computes the zeros of its partial sums divided by $z$ in ordinary floating point, where the coefficients $1, \tfrac12, \ldots, \tfrac1n$ are tame enough to allow it, checking each zero by substitution. At 12 terms the 11 zeros lie on a ring of radius about 1.24; at 48 terms the 47 lie between 1.059 and 1.092; at 192 terms the 191 lie between 1.016 and 1.030, all of them just outside the circle and closing in from there.

Evenly spread #

Not only do the zeros approach the circle; they spread evenly round it. The figure sorts the 191 angles and plots the share of zeros below each angle, against the diagonal an exactly even spread would give. The largest departure is 0.004 of a turn. Paul Erdős and Pál Turán proved in 1950 that this is the generic behaviour: the angles of a polynomial’s zeros are evenly distributed unless the polynomial’s coefficients vary enormously in size, and they gave an explicit bound in terms of the ratio between the largest coefficient and the geometric mean of the first and last. For coefficients $1, \tfrac12, \ldots, \tfrac1n$ that ratio is only $\sqrt n$, and the bound forces near-perfect evenness.

The roots of unity are the extreme case — the zeros of $z^n - 1$, perfectly even and exactly on the circle — and the partial sums of $1/(1 - z)$, which are $(1 - z^{n+1})/(1 - z)$, have exactly those zeros less the one at 1. Jentzsch’s theorem says that every series with radius 1 behaves, at its partial sums, a little like that one. The exponential is the opposite extreme: its coefficients $1/k!$ fall faster than any geometric sequence, the Erdős–Turán ratio is enormous, and its zeros, far from spreading evenly round a circle, gather on Szegő’s lopsided egg.

Where the result is used #

The zeros of partial sums are not only a curiosity of complex analysis. A truncated Taylor series is the simplest rational approximation, and its zeros are its poles’ mirror image in the more general Padé approximants that numerical software uses to evaluate functions; Szegő’s curve and its relatives describe where those approximants misbehave. Numerical methods for differential equations are built from truncated exponentials: the explicit Runge–Kutta method of order four advances a step by multiplying by $s_4(h\lambda)$, and the method is stable exactly where $|s_4(h\lambda)| \le 1$ — a region of the complex plane whose shape is governed by the same contest between the exponential and its tail, and whose boundary passes between the zeros. Richard Varga and his collaborators used Szegő’s curve to bound how large such stability regions can be for methods of every order.

The same idea, that a function and its approximation can only agree to vanish where some balance of sizes ties, recurs in the sine rebuilt from its zeros, where the product over the zeros converges only because the zeros are spread out in a way the function’s growth dictates.

What the computations show and assume #

The zeros are computed, not quoted, and to far more digits than the drawing needs; the bisection for the real zeros is exact in its decisions. What the computations cannot show is the limit itself — the curve is Szegő’s theorem, and the figures show finite $n$ approaching it at the rate the balance predicts. The balance is an asymptotic statement, derived by keeping the first term of the tail and Stirling’s formula, and its success on every zero to within a few hundredths is evidence for that derivation, not a proof of an error bound.

For Jentzsch’s theorem the figures show one series. Its zeros lie outside the circle, but that is a property of this series’ positive, decreasing coefficients — the Eneström–Kakeya theorem places all zeros of such a polynomial outside the unit disc — and not part of Jentzsch’s theorem, which allows zeros on either side. The Eneström–Kakeya argument is short enough to give. For a polynomial $a_0 + a_1 z + \cdots + a_m z^m$ with $a_0 \ge a_1 \ge \cdots \ge a_m > 0$, multiply by $1 - z$: the product is $a_0 - (a_0 - a_1)z - (a_1 - a_2)z^2 - \cdots - a_m z^{m+1}$, and for $|z| < 1$ the subtracted terms add up in size to less than $a_0$, since their coefficients are positive and total exactly $a_0$. So the product cannot vanish inside the disc, and neither can the polynomial. The coefficients $1, \tfrac12, \ldots, \tfrac1n$ are positive and decreasing, which is why every zero in the Jentzsch figure is outside.

Still open: the zeros of other functions’ partial sums #

Szegő’s description extends to the sine, the cosine and many entire functions whose growth is regular enough, and the corrections near the corner of the curve are understood for the exponential. What is not understood in general is the fine structure: how the zeros of partial sums of an arbitrary entire function are distributed when its growth is irregular, and how the zeros approach the curve near points where the limiting description breaks down. Partial results by Edrei, Saff, Varga and others cover classes of functions; a description for all entire functions of finite order, of the kind Szegő gave for the exponential, is not known. And for the partial sums of the Riemann zeta function’s Dirichlet series — sums of $n^{-s}$ rather than powers of $z$ — the analogous question of where the zeros lie, and how they approach the line on which the Riemann hypothesis places the zeros of the full function, has a large literature and no complete answer.

Where a polynomial must vanish #

The partial sums of the exponential have n zeros each, though the exponential has none, and scaled by n the zeros approach the curve |w e^(1−w)| = 1 from outside, at a distance that shrinks like (ln n)/n. The curve is where the exponential and the terms the partial sum has not yet reached are the same size, the one place a cancellation can happen, and balancing the two one order further places every computed zero to within a few hundredths. A series with a finite radius sends its partial sums’ zeros instead to its circle of convergence, all the way round and evenly spread. In both cases the zeros of the approximations record where the approximation has not yet finished its work.