Strip Mining in the Abandoned Orefields of Nineteenth Century Mathematics

0. Apology

This was my 1984 (NYU) talk. My 1986 (Stanford) conference talk began

“The last time Dick [Jenks] asked me to do this, my talk was so weird, and my slides so complicated that I left much of my audience exhausted and confused. By way of remedy, we have amassed here today an array of video equipment so expensive that it can actually reduce mathematics to the intellectual level of daytime TV. So kick back, shift your brain into neutral, and we’ll watch a few pictures whose only purpose is to leave you relaxed and confused.”

I then had the great fortune to project onto a huge, bright screen, a live, relatively disaster free, forty minute color animation. (Let me assure those who attended that the backup videotape would have been a disaster by comparison. You just can’t tape most of that stuff, or even convert it to current broadcast standard.)

Although the talk was fun, it contained little suitable for print publication. “The medium was the message.” That is, the novelty was not so much in the mathematical concepts presented, but rather in the way that motion (particularly zooming) and color could vivify those concepts.

We look forward to an era of electronic publication in which widely available, muscular, high definition graphics engines will let us vivify for each other genuinely interesting mathematics.

Meanwhile, all I can offer is atonement for yet another misdeed at the aforementioned (NYU) conference—due to a two-year separation from TEX, I never contributed to the proceedings. Here then is a slightly less incoherent rendition of my 1984 talk.

1. Teaser

By strip mining, I meant applying the power of a modern symbolic processor, particularly via undetermined coefficients, to old fashioned investigations that were computationally inaccessible to the old fashioned investigators.

I feel sometimes like a kid at the controls of huge, bucket wheel excavator, chewing indiscriminately into apparently mined out formations, yet finding paydirt through sheer, childish brutality.

Random excavations, such as with Berlekamp’s factoring algorithm, produce random nuggets:

\frac{(x − a)^{3}}{(z − x)^{3}(x − y)^{3}} + \frac{(y − a)^{3}}{(x − y)^{3}(y − z)^{3}} + \frac{(z − a)^{3}}{(y − z)^{3}(z − x)^{3}} = 3\frac{(x − a)(y − a)(z − a)}{(x − y)^{2}(y − z)^{2}(z − x)^{2}}

\frac{1}{(w − x)^{3}(w − y)^{3}(w − z)^{3}} +\frac{1}{(x − y)^{3}(x − z)^{3}(x − w)^{3}}

+\frac{1}{(y − z)^{3}(y − w)^{3}(y − x)^{3}} + \frac{1}{(z − w)^{3}(z − x)^{3}(z − y)^{3}}

= 3\frac{(w − x − y + z)(w − x + y − z)(w + x − y − z)}{(w − x)^{2}(w − y)^{2}(w − z)^{2}(x − y)^{2}(x − z)^{2}(y − z)^{2}} ,

as does fooling with the trigonometric simplifiers:

sin(x − w) sin(x − y) sin(y − w) sin(y − z) sin(z − w) sin(z − x)
+ cos(x − w) cos(x − y) sin(y − w) cos(y − z) cos(z − w) sin(z − x)
+ cos(x − w) sin(x − y) cos(y − w) cos(y − z) sin(z − w) cos(z − x)
+ sin(x − w) cos(x − y) cos(y − w) sin(y − z) cos(z − w) cos(z − x) = 0.

These results are just like the factorization of x^{2} − y^{2}, or the sine addition formula, only millions of times less useful. They lead one to speculate whether algebraic engines in the Renaissance might have made this sort of thing into an art form.

More systematic excavations churn up bigger clumps of pay dirt:

∑_{n≥0}(1 − q^{6n+ \frac{1}{2}} )\frac{(q^{−1/2}, q^{3/2}; q)_{2n}}{(q^{2}; q)_{4n}} \frac{(q^{5/2}/a, a; q^{5})_{n}}{(q^{3/2}/a, a/q; q)_{n}} q^{n}

= \frac{(\sqrt{q}; q)_{∞}(a; q^{5})_{∞}}{(q^{2}, a/q; q)_{∞}} (\frac{(a/\sqrt{q}; q)_{∞}(q^{5}; q^{5})_{∞}}{(q^{5/2}, aq^{5/2}; q^{5})_{∞}} − \frac{a}{q} \frac{(\sqrt{q}; q)_{∞}(q^{5/2}/a; q^{5})_{∞}}{(q^{3/2}/a; q)_{∞}} ∑_{n≥0}(−a^{2})^{n}q^{5n^{2}/2})

is but one of dozens of identities that can be extracted from a single mathematical structure uncovered by a brute force attack on certain simultaneous polynomial equations. I call such a structure a “path invariant matrix system.” Points in some space are linked by edges that are labeled with matrices in such a way that the matrix product taken along any path depends only on the endpoints. The path invariance condition on minimal loops induces polynomial equations among the matrix elements. A successful solution then provides a limitless space of closed contours, each yielding a correct identity, several of which may be concise enough to be interesting.

2. Matrices Before getting into path invariance, let me extol some notational, analytic, and computational virtues of matrix products. First, notice how cumbersome are the conventional notations for an identity such as

∏_{k≥1} ( \begin{matrix}\frac{k^{2}}{(4k + 2)^{2}} & \frac{30k − 11}{16k(2k − 1)} \\ 0 & 1 \end{matrix} ) = ( \begin{matrix}0 & ζ(3) \\ 0 & 1 \end{matrix} ) .

Hypergeometrically, you get a ridiculous \frac{19}{16}_{6}F_{5}[\frac{1}{16}]. As a straight sum, you can do as well as

∑_{k≥1} \frac{30k − 11}{4(2k − 1)k^{3}\binom{2k}{k}^{2}} = ζ(3),

but, taken literally, this says something rather silly: add up a sequence of terms whose kth contains products of k factors, in this case \binom{2k}{k}^{2}. Now most of us know the trick of incrementally computing each term from the previous, but this is nowhere hinted in the sum. Furthermore, you’ll need a less-than-obvious auxiliary variable to avoid the wasted effort of cancelling out factors introduced in the term just preceding, or, more seriously, to avoid division by 0 if the numerator of the preceding term happens to vanish (e.g, if the 11 above were instead a 90).

Now suppose that you want a very precise value of ζ(3), and thus wish to sum n terms of this series. You will find it dramatically cheaper to write out instead the first n matrices, and then pairwise multiply to form ⌈n/2⌉ products, and repeat until only one matrix remains. (In 1985, I used this technique, essentially due to R. Schroeppel, to temporarily steal the π computation record from Japan.)

This representation of simple sums as 2 × 2 matrix products is merely a special case (a vanishing off-diagonal) of the well known representation of nested homographic functions. When a diagonal element vanishes, you have a continued fraction. It is strange that so fruitful a representation is applied so rarely to sums. Perhaps discouraging is the apparent nonlinearity of the matrix product form, (partially) concealing such familiar operations as termwise differentiation or combination with other series. We shall see that a small bag of tricks, again based on path invariance, more than remedies these problems.

Even greater simplifications are possible with larger matrices:

∑_{n=0}^{m} a_{n}x^{n−1} ∑_{k=0}^{n−1} \frac{b_{k}}{k!} = ∏_{n=0}^{m} ( \begin{matrix}\frac{x}{n + 1} & b_{n} & 0 \\ 0 & x & a_{n} \\ 0 & 0 & 1 \end{matrix} )_{1,3} ,

where the subscript_{1,3} means the upper right element. Here, the matrix product not only vaporizes a nested loop, but also dispels an artificial asymmetry between a_{i} and b_{i}. They can, in fact, be switched via summation by parts, but then they are asymmetrical the other way!

And here is a way to get factorable multiple sums:

∑_{i=0}^{m} ∑_{j=0}^{m} a_{i}b_{j} = ∏_{n=0}^{m} ( \begin{matrix}1 & a_{n} & b_{n} & a_{n}b_{n} \\ 0 & 1 & 0 & b_{n} \\ 0 & 0 & 1 & a_{n} \\ 0 & 0 & 0 & 1 \end{matrix} )_{1,4} .

Perhaps most important of all are those sadly neglected recurrences that can be expressed by products of denser, (typically) nontriangular matrices. Who knows what we might find, once emancipated from our feebly notated sums, (scalar) products, and continued fractions? One enticement is a smooth generalization of the notion of “closed form”: a recurrence is in simpler (and therefore more canonical) form when it is the product of smaller or sparser matrices. Fully closed form is a 1×1, i.e. scalar product. The importance of such products, by the way, is almost purely their uniqueness and comparability, since they usually converge more slowly than most of the higher order recurrences that they canonicalize.

3. Path Invariance

This idea was crystalized by Kevin Karplus while a student in the only course I ever taught. Label the edges of some sort of directed, multiply connected graph with matrices so that their product, taken along any connected sequence of edges, depends only on the endpoints. Usually, the graph is piecewise grid-like, and it is sufficient to demonstrate path invariance around each of the grid cells, and around the (usually) triangular cells where the grids patch together. For example, a purely two dimensional, path invariant grid would look like

\begin{aligned}k & ↑ \\ & & → \\ & & n \end{aligned}  \begin{matrix}⋮ & ⋮ \\ | & | \\ ⋯⟶ & • & −N_{k+1,n}⟶ & • & −⋯ \\ ↑ & ↑ \\ K_{k,n} & K_{k,n+1} \\ | & | \\ ⋯⟶ & • & −N_{k,n}⟶ & • & −⋯ \\ ↑ & ↑ \\ ⋮ & ⋮ \end{matrix}

where the matrices N_{k,n} and K_{k,n} satisfy the invariance

N_{k,n}K_{k,n+1} = K_{k,n}N_{k+1,n},

a sort of discrete Cauchy-Riemann condition. For example, we might have

N_{k,n} := ( \begin{matrix}\frac{q^{k}}{1 − q^{n+1}} & 1 − q^{k} \\ 0 & 1 \end{matrix} ) , K_{k,n} := ( \begin{matrix}\frac{q^{n}}{1 − q^{k+1}} & 1 − q^{n} \\ 0 & 1 \end{matrix} ) .

Then

N_{k,n}K_{k,n+1} = K_{k,n}N_{k+1,n} = ( \begin{matrix}\frac{q^{n+k+1}}{(1 − q^{n+1})(1 − q^{k+1})} & 1 \\ 0 & 1 \end{matrix} ) .

If we now equate the two path products along a rectangle starting at n = 0, k = a and closing at n = n_{max}, k = k_{max}, and then let (k_{max}, n_{max}) → (∞, ∞) (however they wish, in this case), then we have, after a limit interchange justifiable when |q| < 1,

∏_{n≥0} ( \begin{matrix}\frac{q^{a}}{1 − q^{n+1}} & 1 − q^{a} \\ 0 & 1 \end{matrix} ) ∏_{k≥a} ( \begin{matrix}0 & 1 \\ 0 & 1 \end{matrix} ) = ∏_{k≥a} ( \begin{matrix}\frac{1}{1 − q^{k+1}} & 0 \\ 0 & 1 \end{matrix} ) ∏_{n≥0} ( \begin{matrix}0 & 1 \\ 0 & 1 \end{matrix} ) .

Expanding the infinite products, (and, for convergence, assuming |q^{a}| < 1, i.e. ℜa > 0),

\begin{matrix}( \begin{matrix}0 & (1 − q^{a})(1 + \frac{q^{a}}{1−q} (1 + \frac{q^{a}}{1−q^{2}} (1 + ⋯))) \\ 0 & 1 \end{matrix} ) & ( \begin{matrix}0 & 1 \\ 0 & 1 \end{matrix} ) \\ = ( \begin{matrix}\frac{1}{1 − q^{a+1}} \frac{1}{1 − q^{a+2}} \frac{1}{1 − q^{a+3}} ⋯ & 0 \\ 0 & 1 \end{matrix} ) ( \begin{matrix}0 & 1 \\ 0 & 1 \end{matrix} ) , \end{matrix}

or, equating the upper right elements and dividing by 1 − q^{a},

1+ \frac{q^{a}}{1 − q} + \frac{q^{2a}}{(1 − q)(1 − q^{2})} + \frac{q^{3a}}{(1 − q)(1 − q^{2})(1 − q^{3})} +⋯ = \frac{1}{1 − q^{a}} \frac{1}{1 − q^{a+1}} \frac{1}{1 − q^{a+2}} · · · .

Given path invariance, we can adjoin the reverses of those edges with invertible labels. And we can freely shortcut any connected sequence of edges by a single edge, since its associated matrix is uniquely determined. In particular, we can draw the diagonals J_{j} connecting those nodes where k − n = a:

⋮  ⋮  J_{j+1}
|  |
⋯⟶•−N_{j+a+1,j}⟶•−⋯
↑  ↑
K_{j+a,j}  J_{j} K_{j+a,j+1}
|  |
⋯⟶•−N_{j+a,j}⟶•−⋯
↑  ↑
J_{j−1}  ⋮  ⋮

Then

J_{j} := N_{j+a,j}K_{j+a,j+1} = K_{j+a,j}N_{j+a+1,j} = ( \begin{matrix}\frac{q^{2j+a+1}}{(1 − q^{j+1})(1 − q^{j+a+1})} & 1 \\ 0 & 1 \end{matrix} ) ,

and the shortcut across the whole rectangle is equivalent to the previous edge traversals:

∏_{j≥0} J_{j} = ∏_{n≥0} N_{a,n} ∏_{k≥a} K_{k,∞} = ∏_{k≥a} K_{k,0} ∏_{n≥0} N_{∞,n},

that is

1+\frac{q^{a+1}}{(1 − q)(1 − q^{a+1})} + \frac{q^{2a+4}}{(1 − q)(1 − q^{2})(1 − q^{a+1})(1 − q^{a+2})}

+\frac{q^{3a+9}}{(1 − q)(1 − q^{2})(1 − q^{3})(1 − q^{a+1})(1 − q^{a+2})(1 − q^{a+3})} + ⋯

= (1 − q^{a})(1 + \frac{q^{a}}{1 − q} + \frac{q^{2a}}{(1 − q)(1 − q^{2})} + \frac{q^{3a}}{(1 − q)(1 − q^{2})(1 − q^{3})} + ⋯)

= \frac{1}{1 − q^{a+1}} \frac{1}{1 − q^{a+2}} \frac{1}{1 − q^{a+3}} · · · .

The quadratically progressing exponent in the diagonal sum enhances convergence both numerically, and in the symbolic power series expansion at q = 0.