Which powers of x are enough

Weierstrass proved in 1885 that every continuous function on a closed interval can be approximated, as closely as anyone wishes and uniformly across the whole interval, by a polynomial. A polynomial is a combination of $1, x, x^2, x^3, \dots$, so the theorem says those powers together reach everything. Bernstein’s construction gave an explicit recipe in 1912, using all the powers up to the degree of the approximation.

Bernstein then asked a question that looks like a minor refinement. Is every power needed? Suppose some are thrown away and only $1, x^{n_1}, x^{n_2}, x^{n_3}, \dots$ are kept. Can those combinations still come as close as desired to everything? Dropping $x^3$ should cost nothing, since it could perhaps be imitated by its neighbours. Dropping most of the powers is harder to judge. Is a sparse sequence of exponents enough, and how sparse is too sparse?

Bernstein’s own partial results suggested the answer might be connected with a sum, and two years later Herman Müntz settled it. The answer is one of the cleanest conditions in analysis: on the interval from 0 to 1, the powers $x^{n_k}$ together with the constant 1 reach everything exactly when $\sum 1/n_k$ diverges. Otto Szász gave the general form in 1916, for exponents that need not be whole numbers.

So the reason to care about whether a sum of reciprocals reaches infinity, which the harmonic series introduced as a curiosity, turns out to be the exact boundary of which functions can be built from which powers. The even numbers have a divergent sum and are enough. So are the primes, since Euler showed that their reciprocals diverge, which makes a thin and irregular sequence of powers as good as the whole. The squares have a convergent sum, $\pi^2/6$, and are not. The whole of that statement can be checked with one product.

Distance as a nearest point #

Müntz’s theorem is about uniform closeness, the worst gap anywhere on the interval. It is simpler first to use a different measure of distance: the integral of the squared difference, the same measure that makes functions on an interval behave like vectors. Two functions have an inner product $\int_0^1 f g\,dx$, and the distance from a function to the combinations of some others is then the length of a perpendicular, a calculation in a space of many dimensions and nothing else.

Powers are unusually pleasant for this, because their inner products are simple:

$$\int_0^1 x^u x^v\, dx = \frac{1}{u + v + 1}.$$

The table of those numbers, with rows and columns running over the chosen exponents, is a generalised Hilbert matrix, famous for being almost singular. It belongs to a family with an exact formula for its determinant, due to Cauchy, in which everything factors into differences and sums of the exponents. And the distance from a point to a flat thing can be written as a ratio of two such determinants, so it factors too. The squared distance from $x^m$ to the combinations of $x^{n_1}, \dots, x^{n_K}$ is

$$d^2 = \frac{1}{2m + 1}\prod_{k=1}^{K}\left(\frac{m - n_k}{m + n_k + 1}\right)^2.$$

This is exact, and it is worth pausing on how unusual that is. Asking for the best approximation by a combination of 150,000 functions would normally require solving 150,000 equations, and it would be numerically hopeless for this particular near-singular matrix. Here it is one product, computed in a moment. To be safe, the formula was tested here against a direct least-squares solve in exact rational arithmetic for four small sets of exponents, and the two agree to all the digits a double can hold.

One factor per power #

Take $m = 1$, so the target is $x$ itself. Each power $n$ that is allowed multiplies the distance by the factor

$$\frac{n - 1}{n + 2} = 1 - \frac{3}{n + 2}.$$

Every factor is less than 1, so adding any power helps. But for large $n$ the factor is close to 1 and helps little. A product of such factors falls to nought exactly when the sum of the amounts being subtracted diverges, as is shown by taking logarithms, and that sum is essentially three times the sum of $1/n$. So the condition for the distance to reach nought is that $\sum 1/n_k$ diverges. That is the whole of Müntz’s theorem in this norm, and it is available in two lines from the formula above.

The figure plots the running logarithm. The even numbers go through 1,600 powers with reciprocal sum 3.978 and pay 11.64. The primes have reciprocal sum 2.515 by the same point and pay 7.24. The squares have reciprocal sum 0.644 and pay 1.85. Each of those is close to three times its reciprocal sum. The small differences come from the early factors, where $n$ is small and the approximation $1 - 3/n$ is not sharp: the first even power multiplies the distance by $1/4$, whereas the estimate would have called that a factor of less than nothing.

The race in the opening figure runs on the same data, carried much further. After 150,000 even powers the distance has fallen to $5.6 \times 10^{-9}$. The primes, after 150,000 of them, are at $1.2 \times 10^{-4}$, still falling, and it is falling at a rate that makes the climb of the reciprocal sum of the primes visible directly: that sum grows like the logarithm of the logarithm, and so the distance shrinks like a power of the logarithm. The primes’ divergence is the slowest kind of divergence anyone meets in ordinary number theory, and the formula converts it into the slowest kind of convergence here.

The squares, meanwhile, have stopped. Take the product over every square from 4 upward and it converges to a limit, 0.0905. The powers of two stop sooner and lower, at 0.0350: the first few powers do a lot of good and then the exponents race off too quickly to contribute. It is striking that 0.0350 is below 0.0905 although the powers of two are far sparser than the squares, and the reason is that the early factors matter most. The powers 2, 4 and 8 are of more use than 4, 9 and 16. Sparse does not mean uniformly worse: the question is what the sum is doing, and it converges in both cases.

What the fit looks like when it fails #

Why should a combination of squares be unable to imitate $x$? The picture says why at once.

Each power in the combination is flat near the origin, and the higher it is, the flatter and later it lifts. The target has slope 1 at the origin and meets nought only there. So the combination runs below the target on the left and has to overshoot on the right to do what it can with the integral. The best square-integral fit with five squares has distance 0.143. Its worst gap is 0.252, a quarter of the full height of the target.

The same picture explains why a combination of higher and higher powers can sometimes succeed. A power like $x^{100}$ is nearly nought except near the right-hand end, so it is a device for making a local correction near 1. Differences of two high powers, with enormous coefficients and opposite signs, can be concentrated at any point of the interval, in the way that a difference of two very steep curves makes a narrow bump. A family of exponents has to be dense enough for these corrections to be placed near the origin, which is where the exponents are most at a disadvantage. If the exponents are too sparse, there are not enough close pairs to build the bumps near the left-hand end, and that is what a convergent sum means here. Writing $x = e^{-t}$ turns powers into exponentials $e^{-nt}$, and a bump near the origin in $x$ is a bump far out in $t$. Sparse exponents then mean poor resolution far from the start, and the issue becomes one of how much a set of frequencies can resolve, which is the shape of question the Fourier transform was built to answer.

With six even powers the distance is already down to 0.0186, against the five squares’ 0.143. The fit is still flat at the origin, since every even power is, and a smooth function of $x^2$ can never have slope 1 at nought. But it can have enormous slope immediately to the right of it, and that is enough. The worst gap is 0.046, located at $x \approx 0.10$, not far from the origin.

Everything else stays out of reach too #

When the squares fail, the failure is not specific to the function $x$. Suppose only the exponents $1, 4, 9, 16, \dots$ are available. Their closed span, everything that can be approached by combinations of them, then contains only functions of a very special kind, and no power of $x$ other than these appears in it.

The formula works for every target exponent $m$. With $x^2$ as the target, the distance is 0.0183, and with $x^3$ it is 0.0030. The distances fall quickly as the power rises, to $2.1 \times 10^{-7}$ at $x^{20}$, because high powers are small over most of the interval and so a small correction goes a long way. A power with a small distance is effectively reachable in any practical computation, but for the theorem a small distance and a zero distance are as different as they can be. A close look at the product shows that a factor vanishes exactly when $m$ equals one of the $n_k$, and otherwise the product converges to a positive number. So a function in the closed span of the squares can have only squares as its powers: the refinement due to James Clarkson, Paul Erdős and Laurent Schwartz shows that, when $\sum 1/n_k$ is finite, every function in the closed span extends to an analytic function away from the origin, with a power series in only those exponents. Nothing is added to the list by taking limits, and this is what it means for the family to be incomplete.

Average closeness and closeness everywhere #

The square-integral distance permits failure in small places, and Weierstrass’s theorem does not. A function can be close to $x$ in average squared error while being wrong by a fixed amount on a shrinking strip beside the origin, so a formula for one kind of distance does not immediately deliver the other. To pass to uniform closeness, Müntz needs one further step.

The numbers show the gap between the two measures, and it is exactly near the origin. With eight even powers the average distance is 0.0126, while the worst gap is 0.0357, near $x = 0.076$. The worst place keeps moving left as powers are added. It was at $x = 0.141$ for four powers and $x = 0.099$ for six, a slow advance towards the place where every combination of even powers has slope nought and the target does not.

The step that connects the two uses a trick. If a function is the integral of its derivative, then uniform closeness of the function follows from square-integral closeness of the derivative, because $|\int_0^x (f' - g')|$ is at most the length of the interval times the square-integral distance between the derivatives, by the Cauchy–Schwarz inequality. A power $x^m$ differentiates to $m x^{m-1}$. So approximating $x^{m-1}$ by the powers $x^{n_k - 1}$ in average implies approximating $x^m$ by the powers $x^{n_k}$ uniformly, up to the constant term. And the divergence of $\sum 1/n_k$ and of $\sum 1/(n_k - 1)$ are the same condition. So the theorem for square-integral distance transfers to the theorem for uniform distance, at the cost of one exponent, and the constant function 1 has to be kept in the list, since every other power vanishes at the origin.

A surprising product #

The factor in the formula has been seen before, in a different mathematical life. Replace $m$ by a complex variable $z$ and read the product as a function:

$$B(z) = \prod_{k}\frac{z - n_k}{z + n_k + 1}.$$

Each factor vanishes at $z = n_k$ and has modulus below 1 on the right half of the plane $\operatorname{Re} z > -\tfrac12$, and modulus exactly 1 on its boundary. That makes it a Blaschke product, an object from the theory of bounded analytic functions, built to have prescribed zeros and nothing else. Wilhelm Blaschke’s theorem of 1915 says when such a product exists: a bounded analytic function on a half-plane can vanish at a sequence of points tending to infinity along the real axis, without being identically nought, exactly when the sum of the reciprocals of those points converges.

That is Müntz’s condition, seen from the other side. Suppose $\sum 1/n_k$ converges. Then the Blaschke product is a bounded analytic function that vanishes at each $n_k$ and at no other point, and after a small adjustment this function can be written as an integral of a fixed measure against $x^z$, a route to the theorem that Walter Rudin made standard. So a certain measure on the interval is perpendicular to all the powers $x^{n_k}$ and not to other powers, which is exactly the statement that those powers are not enough. If the sum diverges, no such function exists except nought, no such measure exists, and the powers are enough. The theorem about approximation and the theorem about zeros are the same theorem, one being the dual of the other, in the same way that the zeros of the sine function determine it through a product. A question about real functions on an interval is decided by how many zeros a complex function may have.

No finite stretch of a family can say #

It is natural to ask whether the condition can be seen in a calculation. It cannot, in the strongest sense: for any finite number of powers the combination does something, and the sum over finitely many reciprocals is finite in every case. What differs is only the tail.

The figure runs three families of exponents close to the boundary. Doubled and rounded to whole numbers, $k \ln k$ has a divergent reciprocal sum; $k(\ln k)^2$ and $k^{1.1}$ have convergent ones. After a million powers, the distances are 0.0075, 0.0747 and $3 \times 10^{-5}$ respectively. So the family with a convergent sum, $k^{1.1}$, is hundreds of times closer to the target than the family whose sum diverges. It will stop near $6 \times 10^{-7}$, and the first family, which must eventually go lower, goes on shrinking like $(\ln K)^{-3/2}$. To pass that level the first family needs about $10^{3{,}100}$ powers.

Small cases lie here to an extreme degree. The theorem distinguishes the two families perfectly and no computation that could ever be performed distinguishes them in the right order. The right way to see it is to read the formula, not the curve.

What the computations leave out #

The product formula gives the exact square-integral distance and was tested against exact least squares only on small systems, as a check on the formula rather than a proof of it. The best fits in the figures were computed by solving small systems in double precision, and that limits them to seven or eight powers; beyond that the matrix is too close to singular for a double to solve accurately, which is the reason the formula is valuable. A fit with a hundred powers cannot be drawn this way, and its coefficients would be astronomically large with alternating signs.

The theorem is stated for uniform closeness, and the figures show the average distance. The argument connecting the two was given in outline, for whole-number exponents and for the interval from 0 to 1; Szász’s version for complex exponents, and the versions on intervals not touching the origin, need more care and were not drawn. Limits such as 0.0905 are values of a convergent product truncated at two million factors, and they are accurate to the digits shown but are not closed forms in any useful sense. Finally, the numbers on the slowly converging family in the last figure are extrapolated from the rate $(\ln K)^{-3/2}$, not from any computation at that scale.

Still open: how few coefficients the fit can afford #

Müntz’s theorem says nothing about the size of the approximations. A combination reaching within $\varepsilon$ of the target can have coefficients of astronomical size and opposite signs, and in practice a computation that relies on such cancellation fails long before the theorem takes effect. So there is a question the theorem does not answer: what can be approximated with bounded coefficients? The classical work of Peter Borwein and Tamás Erdélyi on Müntz polynomials shows that many inequalities familiar from ordinary polynomials survive with the right modifications, among them versions of Remez and of Chebyshev; and there are precise estimates of the rate of convergence, due to Newman and others, when $n_k$ is the sequence of a fixed power of $k$. But rates for irregular sequences such as the primes are understood only up to fairly crude factors, and how the geometry of a particular sparse set of exponents constrains its Müntz polynomials, beyond the sum of reciprocals, is an active question rather than a settled one.

A sum decides #

Powers of $x$ reach every continuous function on the interval exactly when the reciprocals of their exponents add up to infinity. In the square-integral norm that is a one-line consequence of an exact product, in which a power $n$ reduces the distance by a factor $1 - 3/(n + 2)$; the even powers and the primes therefore reach everything, the squares stop at a distance of 0.0905 from $x$, and the condition is the dual of Blaschke’s theorem on the zeros of bounded analytic functions.

So the harmonic series, whose divergence looks like an isolated curiosity with no bearing on anything, marks the exact edge of what can be built from powers. The primes are thin enough that their reciprocal sum only just escapes, and they escape for this purpose too. Whichever side a sequence falls on is decided at infinity, which is why no calculation performed on the early exponents can reveal it.