A table that never reaches π

The harmonic series has no sum, and it fails to have one in the most delicate possible way. Its terms shrink to nothing, its partial sums grow like a logarithm, and any faster decay, even by an extra power of a logarithm, would make it converge. A sequence that diverges this slowly is exactly the kind of object that can sit on the boundary of an inequality, and this essay is about one such boundary, where it produces two constants, $\pi$ and 2, and prevents any vector from ever reaching them.

The table is simple to describe. Its first row is $1, \tfrac12, \tfrac13, \tfrac14, \ldots$, its second row is the same with the first entry removed, and so on. So the entry in row $i$ and column $j$ is $1/(i + j - 1)$. Every row and every column is a tail of the harmonic series. None of them can be summed, so an infinite table of this kind might be expected to multiply vectors into infinity. It does not. David Hilbert noticed around 1906 that the table acts as a bounded map on sequences of finite squared length, and Issai Schur found its exact constant in 1911. That constant is $\pi$, and no circle appears anywhere in the table.

Measuring the stretch #

The right measure of a table acting on vectors is its largest stretch: the most that $|Ax|$ can exceed $|x|$, over all non-zero $x$. For a symmetric table this equals its largest eigenvalue, the top of the sphere’s height function, and it can be found by repeatedly multiplying a vector by the table and rescaling. Doing that, at sizes from one up to 2,000, gives the first exact data.

At size one, the table is the single entry 1. At size two the eigenvalue is $2/3 + \sqrt{4/9 - 1/12}$, which is 1.26759, and the calculation can be done by hand. By size 8 it is 1.6959, by 20 it is 1.9071, by 200 it is 2.2743, and at 2,000 it is 2.5013.

The numbers grow, and they grow astonishingly slowly. A hundred times more rows, from 20 to 2,000, adds about 0.6. That is the signature of a logarithm, and Nicolaas de Bruijn and Herbert Wilf found the exact form in 1962:

$$\lambda_n \approx \pi - \frac{\pi^5}{2 (\ln n)^2}.$$

The gap to $\pi$ falls only as the square of the logarithm of the size. Their estimate at a trillion rows gives about 2.94, which still leaves a gap of 0.2. At 2,000 the estimate is much too low, since it gives only about 0.49 against the real 2.50, so these small tables are nowhere near its range of validity; the further terms decay slowly as well. A table can be arbitrarily large and arbitrarily far from what a simple extrapolation predicts. This is the first point at which a picture would mislead. If the curve were shown only up to a thousand rows, it would look as if it might level off near 2.5, and the true limit would come as a shock.

The vector being chased #

The computation also gives the best vector, and that is more informative than the number. Its entries for a table of 2,000 rows fall off along a straight line on logarithmic axes, with slope $-\tfrac12$, until near the end of the table, where they are cut down more steeply.

So the extremal vector is trying to be $x_k = 1/\sqrt k$. Using that vector in the table of 2,000 rows gives a quotient of 2.4470, close to the top. The reason it cannot actually be used in an infinite table is the point. Its squared length is

$$\sum_k \left(\frac{1}{\sqrt k}\right)^2 = \sum_k \frac 1k,$$

the harmonic series itself. It diverges. The vector that would reach $\pi$ has infinite length, so it is not a vector in the space, and every genuine vector falls short. It diverges so slowly that truncating it costs almost nothing, and the truncation can be done at any size, so the supremum is exactly $\pi$ and never attained. That explains the strangely slow convergence as well. To get close to $\pi$, the cut-off vector has to have a long stretch on which it really does look like $1/\sqrt k$, and the length of that stretch is measured on the logarithmic scale on which its squared length grows. So the gap is a function of $\ln n$ rather than of $n$. The theorem about the table and the divergence of the harmonic series are one fact seen from two sides.

There is no eigenvector, either, which is an unfamiliar situation for a symmetric table. Wilhelm Magnus proved in 1950 that the infinite table has no eigenvalues at all, with a purely continuous spectrum filling the interval from 0 to $\pi$. The finite tables have the opposite problem. Their smallest eigenvalues fall exponentially fast, by a factor of about $e^{3.5}$ per row. That makes them the classic example of a badly conditioned matrix, whose inverses are exact and enormous and which defeat ordinary numerical linear algebra at a few dozen rows. That is because this table has another meaning, which leads back to polynomial approximation.

Another reading of the same table #

The entry $1/(i + j - 1)$ is an integral:

$$\frac{1}{i + j - 1} = \int_0^1 x^{i - 1}\, x^{j - 1}\, dx.$$

So this table is a Gram matrix, the table of inner products of the functions $1, x, x^2, \ldots$ on the unit interval. That is the table met in which powers of $x$ are enough, where least squares with powers had to solve it. It is also what explains the tiny eigenvalues. The powers of $x$ on an interval are nearly dependent, since $x^{20}$ and $x^{21}$ are almost the same curve, so the table of their inner products is almost singular. And it gives a completely different way to see that the table is positive. Whatever the vector, $\sum a_i a_j/(i + j - 1)$ is the integral of the square of a polynomial, which cannot be negative.

The same reading gives the upper limit by way of an integral on a circle, which is how Hilbert’s constant was first attacked. The double sum can be written as an integral of $f(t)g(t)$ against a function whose size is bounded by a constant on the circle, which yields $\pi$ again, a calculation with a Fourier series as its starting point. Tables whose entries depend only on $i + j$ are called Hankel matrices, and Zeev Nehari’s theorem of 1957 says that such a table is bounded exactly when its entries are the Fourier coefficients of some bounded function. Here that function is an explicit sawtooth with size $\pi$. So the constant has a meaning. It is the largest value of a function whose Fourier coefficients are the harmonic series. That is the connection that makes the result stop looking accidental, and it is also why the circle shows up. The series $\sum \sin(kt)/k$ sums to a sawtooth with values up to $\pi/2$, one of the first Fourier series ever written down.

One integral #

There is a shorter proof that shows where the number comes from without any of this. Issai Schur’s test bounds a table with non-negative entries by choosing weights. Apply the Cauchy–Schwarz inequality to $\sum a_j a_k/(j + k)$, after writing each term as a product of two square roots and pulling a factor of $(j/k)^{1/4}$ across. What is left to bound is, for each fixed $j$,

$$\sum_{k \ge 1} \frac{1}{j + k} \sqrt{\frac jk} = \sum_{k \ge 1} \frac 1j \cdot \frac{1}{(1 + k/j)\sqrt{k/j}}.$$

That is a rectangle sum for the function $f(x) = 1/(\sqrt x(1 + x))$, with rectangles of width $1/j$.

Because $f$ falls steadily, the rectangle sum lies below the area under the curve, and the substitution $x = \tan^2 t$ turns the area into

$$\int_0^\infty \frac{dx}{\sqrt x (1 + x)} = \int_0^{\pi/2} 2\, dt = \pi.$$

That is where the circle comes from. An arctangent lurks in the integral of $1/(1 + x)$ against $1/\sqrt x$. It is the same as the circle in Leibniz’s series, and it comes from one substitution. And now both features of the theorem can be read from one picture. The bound is $\pi$ because the area is $\pi$. Nothing reaches $\pi$ because the rectangle sum is strictly below the area. The table in the figure is the case $1/(j + k)$; the table starting at $1/(i + j - 1)$ needs a half-step shift in the rectangles, and the bound becomes a midpoint rule on a convex curve, which also falls below the area, as the convexity of a curve requires.

Hardy and the running average #

The same construction works for a different operation. Given a sequence $a_1, a_2, \ldots$, form the running averages $A_n = (a_1 + \cdots + a_n)/n$. Averaging seems as if it should make things smaller. A single spike is indeed flattened: $(1, 0, 0, \ldots)$ has squared length 1, and its running averages have squared length $\sum 1/n^2 = \pi^2/6$. That is already larger, which is the kind of number Basel’s problem gives, and it shows that averaging is not a contraction. So how much can it stretch?

G. H. Hardy proved in 1920 that the stretch is bounded, and Edmund Landau established the exact constant: the largest stretch of the averaging table is exactly 2. The computation at sizes up to 800 gives 1.1441 at 2, 1.4924 at 20, 1.6729 at 200, and 1.7393 at 800, with the same logarithmic slowness as before.

The explanation is the same as for $\pi$, but it is simpler. The nearly extremal vector is again $a_k = 1/\sqrt k$. Its running sum is $\sum_{j \le n} 1/\sqrt j \approx 2\sqrt n$, by comparing with an integral, so its running average is about $2/\sqrt n$. The average is the term multiplied by exactly 2, at every $n$. That is the whole of the constant. The vector would reach it, and the squared length of that vector is the harmonic series again, so it is not a vector. Hardy’s inequality has become a standard tool in the theory of differential equations, in its continuous form, for bounding a function by its derivative, and it is one of the first results that students of analysis meet where the extremal case does not exist.

A whole family, ending at $e$ #

Hardy’s inequality comes with a power. For every $p > 1$,

$$\sum_n A_n^p \le \left(\frac{p}{p - 1}\right)^p \sum_n a_n^p,$$

and the constant is the best possible. The extremal shape is now $a_k = k^{-1/p}$, whose $p$-th powers are, once again, the harmonic series.

The curve has two informative ends. As $p$ falls to one, the constant goes to infinity. It must: at $p = 1$, a single spike $(1, 0, 0, \ldots)$ gives running averages $1, \tfrac12, \tfrac13, \ldots$, whose sum is the harmonic series, so nothing can bound it. At $p = 2$, the constant is 4, the square of the stretch 2. At $p = 3$ it is 3.375.

As $p$ grows, the constant falls towards $\lim (1 + 1/(p - 1))^p = e$, and it has a meaning there too. Replace each $a_n$ by $a_n^{1/p}$, apply the inequality, and let $p$ go to infinity. The mean of the $p$-th roots, raised to the $p$-th power, tends to the geometric mean, and that gives Carleman’s inequality of 1923:

$$\sum_n (a_1 a_2 \cdots a_n)^{1/n} \le e \sum_n a_n.$$

So $e$ arrives at the end of a family that began with the harmonic series, and it too is the best possible and never attained. Carleman needed this for a problem about when a function is determined by its moments. An inequality is usually a tool, but here the sequence of best constants is itself an interesting sequence, and it runs from infinity through 4 down to $e$. The same structure, a slowly diverging vector just out of reach, gives them all.

What the numbers do not settle #

Power iteration at size 2,000 is accurate to about the digits shown, but it does not by itself establish that the sequence is heading for $\pi$, and the figures would not suggest so. Nothing computed here distinguishes a limit of $\pi$ from a limit of 3 or 4. The theorem does that, from the proof using one integral. The asymptotic dashed curve is an analytic estimate, and it is not close to the computed points at small sizes, so no direct comparison between the two was possible in this range. In the calculations that were possible, these slow rates mean that the computed data can never test the leading constant: it would take a table of astronomically many rows to reach the formula’s own range.

So what the pictures supply is a sense of how slow this is and what the extremal shape looks like. The limits are proved, by the argument given and by those quoted. The picture of a smoothly rising curve hides one more fact too. The continuous spectrum means that the finite tables’ eigenvalues fill out a whole interval as the size grows, so these curves are only the top of a growing, dense family.

What was computed and what was quoted #

The stretches of both tables were computed by power iteration on the exact entries, at sizes shown, with several hundred or more iterations, and the small cases agree with the exact formula. The sizes are not large enough to test the asymptotic formula. The integral was computed numerically to seven places and evaluated exactly above. The best vector and the quotient at $1/\sqrt k$ were computed at size 2,000.

The theorems of Hilbert, Schur, Hardy, Landau, Carleman, Magnus, Nehari and de Bruijn and Wilf are quoted, with the proofs given where they fit, and their attributions and dates are from standard accounts. The claim about the smallest eigenvalues falling like $e^{3.5n}$ is quoted and was not measured here, though the near-dependence of the powers of $x$ is direct.

Still open: the right constants away from two #

For $p = 2$ the story is as complete as anything in analysis. For matrices of this shape acting from one $\ell^p$ space to another, it is less so. Hilbert’s inequality for general $p$ has the constant $\pi/\sin(\pi/p)$, also known exactly. But what is the exact stretch of the finite table for any fixed size, and what are the lower-order terms? de Bruijn and Wilf give the leading gap, and Hans Widom and others have studied the rest. The next terms are known in forms involving $\ln \ln n$, but there is no closed form for $\lambda_n$ at any large $n$, and no one expects one.

A sharper and more active question concerns the same table restricted to subsets of the rows. Take only rows and columns indexed by some sparse set of numbers: what is the largest stretch of the table on the primes, or on the squares? The answer depends on how quickly the set thins out and on what kind of cancellation is available. Multiplicative versions, with $1/\mathrm{lcm}(i, j)$ or with $\sqrt{(i,j)/[i,j]}$ in the entries, have been studied by Gál, Aistleitner, Seip and others, and those give large values of the zeta function on a line, so the question has real arithmetic behind it. The limit for one kind of subset depends on how the harmonic series of the primes grows, and the exact constants remain unknown.

A vector of infinite length #

The table with entries $1/(i + j - 1)$ stretches every vector by less than $\pi$, the running-average table by less than 2, and neither constant is ever reached. The bound comes from one falling curve whose area is $\pi$, or from one calculation showing that a slowly decaying tail doubles under averaging.

The reason that nothing reaches them is a shared one. Each inequality would be an equality on a sequence of the shape $k^{-1/p}$, whose $p$-th powers are the harmonic series. It diverges, so that sequence has no norm, and it diverges so slowly that truncating it is nearly free. Every finite version therefore comes close, and the gap closes only on the scale of a logarithm. It is a strange way for a constant to be sharp, and it is the harmonic series’ own doing. Its divergence decides where the constant is, and how slowly it can be approached.