IDENTITIES IN SEARCH OF IDENTITY ^{1}

Doron Zeilberger ^{2}

Appeared in: J. Theoretical Computer Science, 117(1993), 23-38.

Abstract: The time is ripe to start a science of identities for their own sake, without paying lip-service to high-brow mathematics. Although putting combinatorial, (abstract-) algebraic or analytic flesh and blood on identities did lead and will lead to considerable insight as well as new identities, there is also much to be gained in forgetting advanced mathematics, and starting a new sub-discipline of high-school mathematics called ”the theory of identities”.

Preamble: I would like to add to Xavier Viennot’s charming after-dinner speech, in which he listed a large set of properties that conferences may have, and which were all enjoyed by the present one, in addition to ”something special that comes from the heart”, the following. There are many conferences in which a Bourbaki is an invited speaker, and many conferences in which a software developer is an invited speaker, but this one is the first one, that I know of, that has both (Pierre Cartier and Gaston Gonnet, respectively.) So we are nearing the blissful days of the mathematical messiah in which Concrete shall dwell with Abstract.

Mathematics is a language. The most basic elements of a language are its letters, or characters. One of the most important ”letters” of mathematics is

= .

Definition: A mathematical sentence that has ”=” in its middle is called an identity.

The format of an identity is thus

SOMETHING = SOMETHING ELSE.

Trivial Example: Re(s) = 1/2, for every complex zero s of ζ(s).

Easy Example: ANALYTIC INDEX = TOPOLOGICAL INDEX.

Deep Example: 1+1=2.

Related to the subject of identities, or equalities is the more difficult subject of inequalities. Very often important inequalities are immediate consequences of related equalities, but of course, finding the right equality is not always easy. For example the celebrated identity

\frac{a + b}{2} ≥ \sqrt{a}b follows from the (trivial) equality \frac{a + b}{2} − \sqrt{a}b = \frac{(\sqrt{a} − \sqrt{b})^{2}}{2} .

A similar phenomenon occurs with

1 Written version of an invited talk presented at the Series Formelles et Combinatoire Algebriqueconference, May 2-4, 1991, Bordeaux, France. Delivered on May 4, 9:00 AM (local time), about seven hours after the end of the soirée officiel consisting of a royal dinner and extensive wine tasting, in which the average bottle of wine was consumed by half a participant.

2 Department of Mathematics, Temple University, Philadelphia, PA19122. E-mail address: zeilberg@euclid.math.temple.edu. Supported in part by NSF grant DMS8901690.

3 + 4cosθ + cos(2θ) ≥ 0 ,

of prime-number-fame, that follows immediately from the (trivial) equality

3 + 4cosθ + cos(2θ) = 2(1 + cosθ)^{2} .

A far less trivial example is

3F_{2}({−n, n + α + 2, (α + 1)/2 \atop (α + 3)/2, α + 1} ; t ) ≥ 0 ,

which is the Askey-Gasper inequality of Bieberbach ([deB]) fame. It is an immediate consequence of the stronger Askey-Gasper equality:

3F_{2}({−n, n + α + 2, (α + 1)/2 \atop (α + 3)/2, α + 1}; t) = ∑_{j} EXP LICIT (n, j)^{2 ,}

where ”EXP LICIT (n, j)” is a certain explicit real quantity, see the paper by Ekhad[E5] in this issue.

An even deeper inequality is the following, for which I don’t know any corresponding equality, not even conjectured, and I sure wish I did.

Δ(X, Y) ≥ 0 ,

where

Δ(x, y) := ∫_{−∞}^{∞} ∫_{−∞}^{∞} Φ(t)Φ(s)e^{i(t+s)x}e^{(t−s)y}(t − s)^{2}dtds ,

Φ(t) := ∑_{n=1}^{∞}(2pi^{2}n^{4}e^{9t} − 3πn^{2}e^{5t})e^{−πn^{2}e^{4t}} .

Jensen (see [Va]) showed that this inequality is equivalent to the Riemann Hypothesis.

A random sampler of other famous identities is

∑_{λ|−n} f_{λ}^{2} = n! ,  (Y oung − F robenius)

∑_{λ} s_{λ}(x)s_{λ}(y) = ∏_{i=1}^{∞} ∏_{j=1}^{∞} \frac{1}{1 − x_{i}y_{j}} ,  (Cauchy)

∑_{λ} s_{λ}(x) = ∏_{i=1}^{∞} \frac{1}{1 − x_{i}} ∏_{i=1}^{∞} ∏_{j=i+1}^{∞} \frac{1}{1 − x_{i}x_{j}} ,  (Littlewood)

∏_{αϵR^{+}}(1 − x^{α}) = ∑_{wϵW} x^{w(δ)−δ} ,  (W eyl)

∑_{wϵW} w( ∏_{αϵR^{+}} \frac{1 − tx^{α}}{1 − x^{α}}) = ∏_{i=1}^{l} \frac{(1 − t^{d_{i}})}{1 − t} ,  (Macdonald)

C.T. ∏_{αϵR^{+}}(1 − x^{α})...(1 − q^{a−1}x^{α})(1 − qx^{−α})...(1 − q^{a}x^{−α}) = ∏_{i=1}^{l}[{d_{i}a \atop a}] ,  (Macdonald′)

∑_{n=0}^{∞} \frac{q^{n^{2}}}{(1 − q)(1 − q^{2})...(1 − q^{n})} = ∏_{n=0}^{∞} \frac{1}{(1 − q^{5n+1})(1 − q^{5n+4})} ,  (R − R)

∑_{n=1}^{∞} \frac{1}{n^{3}} = \frac{5}{2} ∑_{n=1}^{∞} \frac{(−1)^{n−1}}{n^{3}({2n \atop n})} .  (Apery)

SYNTAX vs. SEMANTICS

There are (at least) two approaches to mathematics (or life for that matter.) The syntactical approach, that looks at the form or format of things, and the semantical approach, that looks for substance, meaning etc. Logic and much of computer science are syntactical, but of course once you have a syntactical theory, it is a theory, hence a meaningful theory, and hence has meaning. In a sense, all of mathematics is syntactical, because it looks for the form of things. Marshal Mcluhan said that yesterday’s form is tomorrow’s content, and so on, so one has an infinite onion, and everything is both semantical and syntactical. In particular:

NOBODY HAS A MONOPOLY ON MEANING AND INSIGHT.

One of the greatest triumphs of the syntactical approach is Schutzenberger’s approach of coding combinatorial objects as words in formal languages. This was used very successfully by the ecole bordelaise (e.g. [D-V].) Another major success, partially inspired by the former, is the beautiful combinatorial approach of Foata and the école lotharingiento special function identities (e.g. [Fo]). In it, one abandons the ”analytical” meaning of special functions qua functions, and looks at the identities syntactically as a formal relations amongst formal power series, making issues of convergence superfluous, and, in fact, meaningless, since what used to be (real, complex, or whatever) variables, denoted by letters, become the letters themselves, i.e. turn into (usually commuting) indeterminates. Then one introduces a combinatorial structure, for which the given relation is the ”shadow”, i.e. the weight enumerator, according to appropriate statistics. I should also mention the extremely fruitful species, pursued vigorously by the ecole Québecoise (e.g [B-L-L]) that once again, can be viewed both as a syntactical theory and as a semantical theory.

Semantical creatures always look for meaning and insight. Many times they find it, and it’s great. Other times they find it, and who cares?, 50 pages of semantical conceptual abstract nonsense to ”understand” some identity. Yet other times, the insight is completely in the beholder’s eyes, like a Rorschach test.

Also what constitutes ”insight” is a matter of personal taste. To fancy algebraists,

INSIGHT=REPRESENTATION THEORY PROOF.

To combinatorialists, on the other hand,

INSIGHT= COMBINATORIAL (PREFERABLY BIJECTIVE) PROOF,

while some folks don’t care at all about insight. They only care whether a result is true or false. Shalosh B. Ekhad belongs to the latter category.

Take for example the good old Young-Frobenius identity

n! = ∑_{λ|−n} f_{λ}f_{λ} .  (Y − F)

The representation theory proof says that both sides count the dimension of the regular representation of S_{n}. The right side, because the multiplicity of the irreducible representation λ in the regular representation equals its dimension f_{λ}. See Bruce Sagan’s [Sa] recent beautifully written book. ^{3}

The combinatorial proof of the Young-Frobenius identity is through the Robinson-Schensted bijection. The left hand side counts the cardinality of S_{n}, while the right hand side counts the cardinality of pairs of tableaux of the same shape, having n cells. That they are equinumerous follows from the fact that they are in bijection.

However, there is a short proof of this identity (due, I think, to Robinson, and that was shown to me a long time ago by Herb Wilf), that only uses high-school algebra. It goes as follows. First one proves

nf_{λ} = ∑_{λ^{+}→λ} f_{λ^{+}} .  (∗)

Recall that f_{λ} is defined as the number of standard tableaux of shape lambda, or equivalently, the number of paths in Young’s lattice λ = λ^{(n)} → λ^{(n−1)} → λ^{(n−2)} → ... → empty, where λ → μ means that μ is a subshape of lambda, and they differ by one cell. They satisfy the obvious recurrence

f_{λ} = ∑_{λ^{−}←λ} f_{λ^{−}} .  (∗∗)

Now one proves (*) by induction, using (**).

nf_{λ} =^{(∗∗)} f_{λ} + ∑_{λ^{−}←λ}(n − 1)f_{λ^{−}} =^{(∗)_{n−1}} f_{λ} + ∑_{λ^{−}←λ} ∑_{λ^{−+}→λ^{−}} f_{λ^{−+}} .

3 I only take issue with p. 96, line 3, word 9: ”(complicated)” should be replaced by ”deep and intricate, yet gorgeous”.

Now the summation set lambda^{−+} is the set of all shapes obtained by deleting a cell and then adding a cell. This set it ”almost” the set lambda^{+−} obtained by adding a cell and then deleting one. Indeed if the deleted cell and the added cell are distint, then there is a 1-1 correspondence between the action of delete-then-add and that of add-then-delete. The only possible discrepancy is when the added and deleted cells are the same. The number of ways of deleting a cell and then adding it back equals the number of distinct parts of the shape, while the number of ways of adding-then-deleting is the number of distinct parts plus one, since one can add a new row of one cell at the very bottom (and then delete it). So, as multisets, we have

{λ^{+−}} = λ ∪ {λ^{−+}} .

Putting this above, and using (**) once again, we get that

nf_{λ} = ∑_{λ^{+}→λ} ∑_{λ^{+−}←λ^{+}} f_{λ^{+−}} = ∑_{λ^{+}→λ} f_{λ^{+}} . QED

The readers are invited to show how (*) implies (Y-F). A careful scrutiny of the proof shows that it is in fact the ”algebraization” of the Robinson-Schensted proof, and conversely, the Robinson-Schensted algorithm is the ”bijectification” of the above proof.

A NEW SCIENCE IS BORN

I propose to start a new SCIENCE, to be called IDENTITY SCIENCE (IS for short). In it identities will be studied for their own sake, and one will try to use the minimum amount of concepts, at least of concepts from other parts of mathematics. Group theoretical, combinatorial and other conceptual and insightful proofs will be banned, except when there is hope of stripping the foreign concepts away. This fanaticism will serve a very important purpose. I believe, with Hemingway, that less is more, and with modern painters and composers that extreme ugliness is beautifulon ”no conceptual proofs please” is based on the following hope:

COMPLETE LACK OF INSIGHT WILL LEAD TO NEW KINDS OF INSIGHTS.

I will now give a few examples of families of identities, drawn from my own personal experience, and will try and rate them according to whether they are utterly trivial, trivial, trivial but expensive, trivial in principle, and not yet trivial. Since the word ”trivial” has an offensive ring to it, I will replace it by shaloshable, in honor of my faithful servant Shalosh B. Ekhad.

At the bottom of the ladder are rational function identities with a fixed number of terms and variables. For example

\frac{1}{x} + \frac{1}{y} + \frac{1}{z} = \frac{xy + xz + yz}{xyz} .

These are, of course, utterly shaloshable. Not yet shaloshable are rational function identities with an arbitrary number of variables and terms, for example, the so-called Good identity, that was used by Good[Go] to give a 1-line proof of Dyson’s conjecture:

∑_{i=1}^{n} \frac{1}{∏_{j≠i}(1 − x_{i}/x_{j})} = 1 ,

which is an easy, albeit human, exercise in using Lagrange interpolation: put p(x) = 1, and then x = 0 in

p(x) = ∑_{i=1}^{n} p(x_{i})\frac{∏_{j≠i}(x − x_{j})}{∏_{j≠i}(x_{i} − x_{j})} .  (Lagrange)

It would be nice to define precisely a wide class of ”Good” identities, perhaps those involving ∑ and ∏ a finite number of times, with the ranges of summation and product having a certain form, and make them shaloshable, perhaps by mechanizing Lagrange interpolation.

The next level of identities are single sum binomial coefficient identities. These can always be written in the form

∑ ∏ = ∏ ,

or more verbosely,

∑_{k=−∞}^{∞} ∏_{k′=1}^{k} R(n, k′) = Constant · ∏_{n′=1}^{n} S(n′) ,

where both R(n, k′) and S(n′) are rational functions of their arguments.

For example, the good old binomial theorem can be written as

∑_{k=−∞}^{∞} ∏_{k′=1}^{k} \frac{n − k′ + 1}{k′} = ∏_{n′=1}^{n} 2 .

The same ”atomic” notation can be used for multi-sum binomial coefficients identities. For example, the trinomial theorem can be written as

∑_{k_{1}=−∞}^{∞} ∑_{k_{2}=−∞}^{∞} ∏_{k′_{1}=1}^{k_{1}} \frac{n − k′_{1} + 1}{k′_{1}} ∏_{k′_{2}=1}^{k_{2}} \frac{n − k_{1} − k′_{2} + 1}{k′_{2}} = ∏_{n′=1}^{n} 3 .  (trinomial)

We now know ^{4} that

4 [Z1][Z2][Z3][Z5][WZ1][WZ2] (see also [A-Z]), but this goes back to my error-ridden Sister Celine paper [Z0], in which I tried to show that ”all binomial coefficients identities are trivial” by basing this on a formalization of Sister Celine’s technique, that was done sloppily and inaccurately. Recently Peter Paule pointed my attention to a paper by Verbaeten of 1974, [Ve], that formalizes Sister ALL BINOMIAL COEFFICIENT (≡ HYPERGEOMETRIC) IDENTITIES ARE SHALOSHABLE.

The format of the most common binomial coefficient identity is

∑_{k} NICE(n, k) = \overline{NICE}(n) ,

where a function F (n, k) is ”nice” if it’s closed form (F (n + 1, k)/F (n, k) and F (n, k + 1)/F (n, k) are rational functions,) and, to avoid pathologies like 1/(n+k^{2}), we also require that it’s holonomic (see[Z1]). For example

∑_{k}({n \atop k}) = 2^{n ,} ∑_{k}({n \atop k})^{2} = ({2n \atop n}) , ∑_{k}(−1)^{k}({2n \atop n + k})^{3} = \frac{(3n)!}{n!^{3}} .

Let’s describe the WZ methodology[WZ2] of proving such identities. First make the right hand side as nice as can be:

∑_{k} \frac{NICE(n, k)}{\overline{NICE}(n)} = 1 .

Of course thou shall not divide by zero, so if \overline{NICE} is identically zero, then, just let it be. Now let’s call the summand above F (n, k), and we have to prove that its definite sum from k = −∞ to k = ∞ is identically 1 (or zero.) It turns out ([WZ1],[WZ2]) that there always ^{5} exists a WZ mate, G(n, k), such that the following is true

F (n + 1, k) − F (n, k) = G(n, k + 1) − G(n, k) .  (W Z)

Not only that,

G(n, k) = RAT IONAL(n, k) · F (n, k) .

META-THEOREM: FOR ANY GIVEN BINOMIAL COEFFICIENTS IDENTITY, VERIFY-ING (WZ) IS A PURELY ROUTINE MATTER

Proof: Dividing (WZ) by F (n, k), we have to verify

\frac{F (n + 1, k)}{F (n, k)} − 1 = \frac{G(n, k + 1)}{F (n, k + 1)} × \frac{F (n, k + 1)}{F (n, k)} − \frac{G(n, k)}{F (n, k)} .

Celine’s technique correctly. However both Sister Celine and Verbaeten were only interested in finding recurrence relations for polynomials. The significance for proving identities was first realized in [Z0]. So were it possible to rewrite history, like it used to be in some countries, I would have rewritten [Z0] with full reference to [Ve].

5 Well, almost always, and something more general, that still enables us to prove the identity, is always true, see [WZ2][Z2].

Since F is closed-form, and from the fact that G/F is a rational function, it follows that all the above ratios are rational functions, and hence the identity is routinely verifiable.

Let’s give a WZ proof of (1 + 1)^{2} = 2^{n}.

Verbose Proof: We have to prove

∑_{k} \frac{({n \atop k})}{2^{n}} = 1.

We cleverly construct

G(n, k) := \frac{−1}{2^{n+1}} ({n \atop k − 1}) ( = \frac{−k}{2(n − k + 1)}F (n, k) ) ,

with the motive that

F (n + 1, k) − F (n, k) = G(n, k + 1) − G(n, k) , (check!) ,  (W Z)

Summing (WZ) with respect to k gives

∑_{k} F (n + 1, k) − ∑_{k} F (n, k) = ∑_{k}(G(n, k + 1) − G(n, k)) = 0, (by telescoping).

So L(n) := ∑_{k} F (n, k) , satisfies L(n + 1) − L(n) = 0 for every n ≥ 0 .

Since L(0) = 1 (check!), it follows that L(n) ≡ 1. QED

All WZ proofs have the same monotone style, after all they were generated by a (deterministic) program. After a few identities they become repetitive. The only thing that changes is the input F (n, k) (given by the ”theorem” part) and the corresponding output, G(n, k), that is always of the form R(n, k)F (n, k), for some rational function R(n, k). Assuming that the reader is familiar with the WZ methodology, that can be explained once and for all, all that the prover has to supply is the rational function R(n, k). Thus

Terse Proof:

R(n, k) = \frac{−k}{2(n − k + 1)} QED .

However, MAPLE is readily available (for < 1000 US dollars), and my program is available for free. Since R(n, k) can be easily reproduced by any computer, it is even unnecessary to present the rational function. Thus, An Even Terser Proof: QED . ^{6}

Since the WZ method is not yet as well known as it should be, at present Shalosh B. Ekhad uses the ”terse” style, but not yet the ”even terser” style. For an impressive example of what Shalosh can do, see its paper [E5] in this issue. See also [E1-4],[E-Z].

It is not true in general, that

L(n) := ∑_{k} NICE(n, k) ,

is itself always ”nice”, but something weaker is always true. For L(n) to be nice, it has to satisfy

\frac{L(n + 1)}{L(n)} = \frac{P OL(n)}{P OL′(n)} , i.e. ,

P OL′(n)L(n + 1) − P OL(n)L(n) = 0,

which is a first order homogeneous linear recurrence equation with polynomial coefficients. In general L(n) is guaranteed ([Z0],[Z1]) to be a solution of some linear recurrence equation with polynomial coefficients, but not necessarily of first order. Such L(n) are called P-recursive or holonomic. So L(n) satisfies an equation of the form

P OL(n)L(n) + P OL′(n)L(n + 1) + P OL′′(n)L(n + 2) + ...P OL^{(s)}(n)L(n + s) = 0,

Example:

L(n) := ∑_{k}({n − k \atop k}) satisfies L(n) − L(n − 1) − L(n − 2) = 0.

It follows that all the identities of the form

6 This is reminiscent of an old Jewish joke. The proud father of a newborn son wants to inform, via telegram, his father (the baby’s grandfather), of the event, so that he can come to the brit (ritual circumcision.) The first version he had was: ”Dear Papa, Please come to the brit of your newborn grandson”. Since every word costs money, he is trying to see if he can make it shorter. First he gets rid of the words ”Dear”, then ”please”, then ”Papa”, then ”newborn” (it must be newborn) then ”grandson” (whoever heard of a brit for a daughter), and so on, until he gets the empty telegram. He then feels silly about sending an empty telegram, and forgets about the whole thing. Of course, the mistake was at the end. Had the grandfather received an empty telegram, it would have signaled to him that something important happened to his son, that necessitated visiting him. Similarly, in the ”even terser proof”,one is not allowed to drop the ”QED”, or if one has imperial tastes (see Paulos’s masterpiece [Pa]), the QED. The ”QED” is the writer’s word of honor that he actually ran the program, and it did produce a certain R(n, k).

∑ ∏ RAT IONAL = ∑ ∏ RAT IONAL′ or equivalently ∑_{k} NICE(n, k) = ∑_{k} NICE′(n, k) ,

are shaloshable. Just find recurrences for either sides and check whether they are the same, or at least ”equivalent”, and that the appropriate boundary conditions match.

All the ”hairy” parts in Apéry’s [Ap] proof that ζ(3) is irrational ([vdP]) are shaloshable (see [Z4]). Indeed, Shalosh can prove in a few seconds that

b(n) := ∑_{k}({n \atop k})^{2}({n + k \atop k})^{2 ,}

and

a(n) := ∑_{k}({n \atop k})^{2}({n + k \atop k})^{2}[ ∑_{m=1}^{n} \frac{1}{m^{3}} + ∑_{m=1}^{k} \frac{(−1)^{m+1}}{2m^{3} ({n \atop m})({n+m \atop m})}] ,

are solutions of

n^{3}x_{n} − (34n^{3} − 51n^{2} + 27n − 5)x_{n−1} + (n − 1)^{3}x_{n−2 = 0}.

Proof:QED.

The WZ method, and the more general method of [Z2] found many new identities, in addition to proving many known ones (and being able to prove all terminating single-sum hypergeometric identities.) However, being ”new” doesn’t mean ”interesting”. As was pointed out by Blackwell, it is possible to discover a new identity by taking any two 10-digit numbers and then multiplying them together, and the resulting identity is most likely new. What we want is new and interesting. Even more exciting would be a use of the WZ method to prove an identity needed by someone desperately in order to prove an open problem. Such a dramatic use of the WZ method was recently given by George Andrews [An], who, in the course of his proof of the Mills-Robbins-Rumsey conjecture about the number of totally symmetric, self complementary plane partitions, needed to evaluate

4F_{3}({−i , 8/3 , j + 3 , 5/2 \atop 5/3 , −2j , 2j + 6} ; −8) ,

which he was unable to do by any of the previously known methods. The WZ method solved it in a few seconds.

Everything discussed so far applies just as well to q-analogues, except that the WZ miracle doesn’t happen so often, and one does have to resort to q-creative telescoping [WZ3].

Definition: a(n) is q-nice if

\frac{a(n + 1)}{a(n)} = RAT IONAL(q, q^{n}) .

The prototype of a q-nice function is the q-analog of n!: (q)_{n} := (1 − q)(1 − q^{2})...(1 − q^{n}).

By the same token, a function F (n, k) of two discrete variables is q − nice if

\frac{F (n + 1, k)}{F (n, k)} = R_{1}(q^{n}, q^{k}, q) , \frac{F (n, k + 1)}{F (n, k)} = R_{2}(q^{n}, q^{k}, q) ,

where R_{1} and R_{2} are rational functions of all their arguments. The obvious extension holds for functions F (k_{1}, ..., k_{r}) of several discrete variables. Particularly nice closed form functions, that include all those that occur ”in nature”, are products of integer powers of terms of the form

(q)_{a_{1}k_{1}+a_{2}k_{2}+...+a_{r}k_{r}+c} , a_{i} integers,

multiplied by any polynomial P (q^{k_{1}}, ..., q^{k_{r}}, q) times q to the power any quadratic form in the k_{1}, ..., k_{r}. For example the q-binomial coefficients (q)_{n}/((q)_{k}(q)_{n−k}). Such closed form functions are called, in [WZ3], proper closed form

Theorem:

a(n) := ∑_{k_{1}} ... ∑_{k_{r}} ”q − NICE”(n, k_{1}, ..., k_{r})

is q-P-recursive, and one can find (fairly) fast the recurrence. Here, by ”q-NICE” we mean ”proper closed form”.

Shalosh and its colleague Sol Tre have recently[E-T] given a new and very short proof of the Rogers-Ramanujan identity:

∑_{k=0}^{∞} \frac{q^{k^{2}}}{(q)_{k}} = ∏_{n=0}^{∞} \frac{1}{(1 − q^{5n+1})(1 − q^{5n+4})} .  (R − R)

Well, not really. It would be a great moment for computerkind when Shalosh (or any of its brethren) will be able to generate a proof for an arbitrary identity of Rogers-Ramanujan type. ^{7} There is

7 It turns out that this problem was the seed to Paul Cohen’s proof of the independence of the continuum hypothesis. In his own words([A-A-R],p.50): ”Because of my interest in number theory, however, I did become spontaneously interested in the idea of finding a decision procedure for certain identities, such as the famous Rogers-Ramanujan identity. I thought that a procedure might exist analogous to, let’s say, checking an identity in algebra between polynomials. There are various famous identities involving formal power series.” (...) ”I saw that the first problem would be to develop some kind of formal system and then make an inductive analysis of the complexity of the statements. In a remarkable twist this crude idea was to resurface in the method of ’forcing’ that I invented in my proof of the independence of the continuum hypothesis.” no way that, today, Shalosh can prove (R-R) directly, since both left side and right side have no parameters to spare. What Shalosh can prove is a more general (and hence easier) identity, stated (and, as it so happened, also first proved) by the human George Andrews (see [E-T]):

∑_{k=0}^{n} \frac{q^{k^{2}}(q; q)_{∞}}{(q)_{k}(q)_{n−k}} = ∑_{j=−n}^{n} \frac{(−1)^{j}q^{(5j^{2}+j)/2}(q; q)_{∞}}{(q)_{n−j}(q)_{n+j}} .  (R − R − finite)

Shalosh and Sol also had to prove, and did prove, the following finite identity:

\frac{(q^{5}; q^{5})_{∞}(q^{2}; q^{5})_{n}(q^{3}; q^{5})_{n}}{(q; q)_{∞}} = ∑_{j=−n}^{n}(−1)^{j}q^{(5j^{2}+j)/2}[{2n \atop n + j}]_{q^{5}} \frac{(q^{5}; q^{5})_{∞}}{(q; q)_{∞}} .  (q − binomial)

The original Rogers-Ramanujan identity follows immediately upon letting n → ∞ in the above two shaloshable identities.

What’s happening here? Shalosh cannot prove an identity a = b directly, so we need a human to conjecture a finite form A(n) = B(n), which is shaloshable, and such that A(∞) = a, and B(∞) = b. In the R-R case, in fact, the human had to conjecture two finite identities

A(n) = C(n) , B(n) = D(n) ,

such that C(∞) = D(∞) and A(∞) = a , B(∞) = b. It might be that every identity of ”Rogers-Ramanujan” type

∑_{k=0}^{∞} t(k) = ∑_{k=0}^{∞} s(k) ,

or

∑_{k=0}^{∞} t(k) = ∏_{k=0}^{∞} Rational(q, q^{k}) ,

where both t(k) and s(k) are ”nice” (i.e. t(k + 1)/t(k) and s(k + 1)/s(k) are rational functions in (q^{k}, q)) has corresponding ”finite forms” which are, of course, shaloshable. Even if this is not the case in general, or if it is, but it’s too hard to prove, it would be interesting to develop heuristics for ”guessing” possible finite forms, which would then be routinely provable.

Going back to the ordinary case, the hypergeometric identity ([vdP])

∑_{n=1}^{∞} \frac{1}{n^{3}} = \frac{5}{2} ∑_{n=1}^{∞} \frac{(−1)^{n−1}}{n^{3}({2n \atop n})} ,  (Apery)

is not directly shaloshable, but the ”finite form”

∑_{n=1}^{N} \frac{1}{n^{3}} = \frac{5}{2} ∑_{n=1}^{N} \frac{(−1)^{n−1}}{n^{3}({2n \atop n})} + ∑_{k=1}^{N} \frac{(−1)^{k}}{2k^{3}({N+k \atop k})({N \atop k})} ,

which immediately implies it by taking N → ∞, is shaloshable.

The complete elliptic integral of the first kind K(k) is nothing but _{2}F_{1}(1/2, 1/2 ; 1 ; k^{2}). It follows that the ”exact evaluations” (see [S-C]; [B-B], p. 298) at the so called ”singular values” are just certain infinite hypergeometric series that happen to be expressed in terms of Γ’s at rational points. I conjecture that all these are just ”tips of icebergs” of finite, shaloshable identities. To obtain the infinite series corresponding to the K(k) of interest, one would have, of course, to use Carlson’s theorem (e.g.[Ba],p. 36ff), but this is very standard. For example, the evaluations of the third singular value K(k_{3}),

K(\sqrt{2}(\sqrt{3} − 1)/4) = \frac{3^{1/4}Γ(1/3)^{3}}{2^{7/3}π} ,

is obtained by ”plugging” n = −1/2 in (the non-terminating extension of) the following shaloshable identity:

2F_{1}({−n, 3n + 2 \atop n + 3/2}; (\sqrt{3} + 2)/4) = \frac{(3/2)_{n}}{(4/3)_{n}} (−4/3\sqrt{3})^{n} .

K(k_{1}), K(k_{2}), and K(k_{4}) also have terminating versions. Shalosh, and its bigger siblings D.U.King and Ralbag, are now trying to find terminating versions of further evaluations, and also of Ramanujan’s (1/99)^{4} famous formula for 1/π.

The Next Ten Years of IS

IS should not be confined to any one kind of identities. The reason that I talked so much about hypergeometric identities is merely personal. We should try and find other kinds of identities that can be made shaloshable, either in principle, or better still, in practice.

Another worthy project, alluded to above, is to make shaloshable as wide as possible a class of rational function identities that will include the Good identity and its various analogs given by Gustafson and Milne[Gu-Mi]. In [Z6] I give Lagrange interpolation proofs, in the spirit of Good[Go] and Gustafson and Milne [Gu-Mi], of several ”fancy” formulas that arise in representation theory and other parts of (”advanced”, ”graduate level”) algebra. It would be nice to make it all shaloshable.

Gustafson and Milne (e.g. [Gu],[Gu-Mi],[Mi]) are pursuing an ambitious and impressive program of finding and proving multi-variate hypergeometric identities with an arbitrary number of sigmas (e.g.[Mi],[Gu]). Now for each fixed number of sigmas their identities are shaloshable. For fixed=1,2,3 in practice, but for fixed > 5 probably only in principle. But, please wait a minute! Computers and Humans should not compete against each other, but COOPERATE. One of the most fundamental identities in this theory, that was the starting point for Milne’s and Gustafson’s work, is Holman’s [Ho] U(N) generalization of Gauss’s _{2}F_{1}(1) identity. I let Shalosh find WZ proofs for N = 1, 2, 3 and THEY WERE GORGEOUS, and looked very much alike. So any human could see the pattern and formulate a general WZ proof, valid for any N. Only now the resulting ”purely routine” rational function identity of the multi-variate generalization([WZ3]) of the Meta-theorem is no longer routine at all, since now we have a rational function identity involving a general (arbitrary) number of variables and terms. Although not routine (at present), it was nevertheless an easy human exercise in using Lagrange interpolation (see [WZ3]). I am almost sure that it is possible to give WZ proofs to all the multi-variate hypergeometric identities of Gustafson and Milne. Of course, discovering (i.e. conjecturing) the identities at the first place is a completely different matter, for which one needs human ingenuity and insight. Other multi-variate identities one may want to WZ-ize are the beautiful multi-variate extension of Foata and Garsia [F-G] of the Mehler formula, the Foata-Strehl extension of the Hille-Hardy formula [F-S], and Strehl’s[St] many beautiful new multi-variate formulas given in his impressive habilationsschrift.

A big terra incognita is a WZ approach to Gaussian Sum Analogs of hypergeometric and Barnestype identities. The first to prove such an analog was Anna Helversen-Pasotto[He], which was a true landmark. Today this field is very active (e.g. [Gr-St]) and so far I don’t see how to WZ-ize it.

The quintessential holonomic sequence is n!. But what about (n!)!, ((n!)!)!, and so on. Perhaps one should define a whole hierarchy of ”generalized holonomic functions”. A function is 0-holonomic if it’s a rational function. It’s 1-holonomic if it’s a solution of a linear recurrence equation whose coefficients are 0-holonomic functions (i.e. rational functions). So one can define r-holonomic functions as solutions of linear recurrence equations whose coefficients are (r − 1)−holonomic functions. So much for single variable. For several variables, we would need some technical conditions to avoid pathologies. It would be interesting to develop a theory of identities for these higher holonomic functions.

Gödel and Turing (and later Hartmanis, Cook, and Karp) taught us that computers cannot do everything. However, I bet that they can do many many more things than one imagines today. It would be fun to exploit the great power of our machines in innovative ways, that will show that they are far from just ”dumb calculating jocks”, but equal, and in many respects, superior, colleagues.

REFERENCES

[A-A-R] D.J. Albers, G.L. Alexanderson, and C. Reid, ”MORE MATHEMATICAL PEOPLE”, Harcourt Brace Jovanovich, Boston, 1990.

[A-Z] G. Almkvist and D. Zeilberger, The method of differentiating under the integral sign, J. Symbolic Computation 10(1990), 571-591.

[An] G.E. Andrews, Plane Partitions V: the T.S.S.C.P.P conjecture, J. Comb. Th. (ser. A), to appear.

[Ap] R. Apéry, Irrationalite de ζ(2) et ζ(3), Asterisque 61(1979), 11-13.

[Ba] W.N. Bailey, ”GENERALIZED HYPERGEOMETRIC SERIES”, Cambridge Math. Tract No. 32, Cambridge University Press, London and New York, 1935. (Reprinted:Hafner, New York, 1964).

[B-L-L] F. Bergeron, G. Labelle, and P. Leroux,”COMBINATOIRE ET STRUCTURES AR-BORESCENTES”, a book in preparation.

[B-B] J.M. Borwein and P.B. Borwein, ”PI AND THE AGM”, John Wiley, New York, 1987.

[deB] L. de Branges, A proof of the Bieberbach conjecture, Acta Math. 154(1985), 137-152.

[D-V] M.P. Delest and G.X. Viennot, Algebraic languages and polyominoes enumeration, Theor. Comp. Sci. 34(1984), 169-206.

[E1] S.B. Ekhad, Short proofs of two hypergeometric summation formulas of Karlsson, Proc. of the Amer. Math. Soc. 107(1989),1143-1144.

[E2] , A very short proof of Dixon’s theorem, J. Comb. Theo. Series A 54(1990), 141-142.

[E3] , A one-line proof of the Habsieger-Zeilberger G_{2} constant term identity, J. Comput. Appl. Math. 34(1991), 133-134.

[E4] , Short Proof Of A ”Strange” Combinatorial Identity Conjectured by Gosper, Discrete Math, to appear.

[E5] , A Short, Elementary, and Easy, WZ proof of the Askey-Gasper inequality that was used by de Branges in his proof of the Bieberbach conjecture, this issue. [E-T] S. B. Ekhad and S.Tre, A purely verification proof of the first Rogers-Ramanujan identity, J. Comb. The. Ser. A 54(1990), 309-311. [E-Z] S.B. Ekhad and D. Zeilberger, A 21st century proof of Dougall’s hypergeometric sum identity, J. Math. Anal. Appl. 147(1990), 610-611.

[Fo] D. Foata,Combinatoire des identites sur les polynomes orthogonaux,in ”Proc.Inter.Congress of Math. [Warsaw, Aug. 16-24, 1983]”, 1541-1553, Varsovie, 1983. [F-G] D.Foata and A.Garsia, A combinatorial approach of the Mehler formulas for Hermite polynomials. In ”Relations between combinatorics and other branches of mathematics,Columbus, 1978”, 163-179, Amer. Math. Soc., Providence, 1979. [F-S] D. Foata nd V. Strehl, Une extension multiline’aire de la formule d’Erde’lyi pour les produits de fonctions hyperge’metriques confluentes, C.R. Acad. Sc. Paris, 293(1981), 517-520. [Ga-Go] F. Garvan and G. Gonnet, Macdonald’s constant term conjectures for the exceptional root systems, Bulletin (new series) of the Amer. Math. Soc. 24(1991), 343-347.

[Go] I.J. Good,Short proof of a conjecture bt Dyson,J. Math. Phys. 11(1970), 1884. [Gr-St] J. Greene and D. Stanton, A character sum evaluation and Gaussian hypergeometric series, J. Number Theo. 23(1986), 136-148.

[Gu] R.A. Gustafson, A generalization of Selberg’s beta integral, Bulletin (new series) of the Amer. Math. Soc. 22(1990), 97-105. [Gu-Mi] R.A. Gustafson and S.C. Milne, Schur functions, Good’s identity, and hypergeometric series well poised in SU(n), Adv. in Math. 57(1985), 209-225.

[He] A. Helversen-Pasotto, L’identité de Barnes pour les corps finis, C.R. Acad. Sci. Paris, Se’rie A, 286(1978), 297-300.

[Ho] W.J. Holman III, Summation theorems for hypergeometric series in U(n), SIAM J. Math. Anal. 11(1980), 523-532.

[Ma] I.G. Macdonald, Some conjectures for root systems, SIAM J. Math. Anal. 13(1982), 988-1007.

[Mi] S.C. Milne, A q-analog of the Gauss Summation Theorem for hypergeometric series in U(n), Adv. Math. 72(1988) 59–131.

[Pa] J.A. Paulos,”BEYOND NUMERACY, ruminations of a numbers man”, Alfred A. Knopf, New York, 1991.

[vdP] A. van der Poorten, A Proof that Euler missed..., Apéry’s proof of the irrationality of ζ(3), Math. Intel. 1(1979), 195-203.

[Sa] B. Sagan,”THE SYMMETRIC GROUP”, Wadsworth & Brooks/Cole, Pacific Grove, California, 1991. [S-C] A. Selberg and S. Chowla, ”On Epstein’s zeta function”, J. Reine Ang. Math. 227(1967), 86-110.

[St] V. Strehl, ”ZYKEL-ENUMERATION BEI LOCAL-STRUKTURIEN FUNKTIONEN”, Habilationsschrift, Universita:t Erlangen-Nürnberg, Germany, 1990.

[Va] R.S. Varga, ”SCIENTIFIC COMPUTATION ON MATHEMATICAL PROBLEMS AND CONJECTURES”, CBMS-NSF Regional Conference Series in Applied mathematics 60, SIAM, Philadelphia, 1990.

[V] P. Verbaeten, The automatic construction of pure recurrence relations, Proc. EUROSAM ’74, ACM-SIGSAM Bulletin 8(1974), 96-98.

[WZ1] H.S. Wilf and D. Zeilberger, Towards computerized proofs of identities, Bulletin of the Amer. Math. Soc. 23(1990), 77-83.

[WZ2] , Rational functions certify combinatorial identities, J. Amer. Math. Soc. 3(1990), 147-158.

[WZ3] ,A general theory of multi-variate hypergeometric identities, in preparation.

[Z0] D. Zeilberger, Sister Celine’s technique and its generalizations, J. Math. Anal. Appl. 85(1982), 114-145.

[Z1] , A Holonomic systems approach to special functions identities, J. of Computational and Applied Math. 32(1990), 321-368.

[Z2] , A Fast Algorithm for proving terminating hypergeometric identities, Discrete Math 80(1990), 207-211.

[Z3] , The method of creative telescoping, J. Symbolic Computation 11(1991), 195-204.

[Z4] , Closed Form (pun intended!), to appear in: ”Special volume in memory of Emil Grosswald”, M. Knopp, ed., Contemporary Mathematics, AMS.

[Z5] , Three recitations on Holonomic Systems and Hypergeometric Series, Proceeding of the Séminaire Lotharingien de combinatoire 24, IRMA, Strasbourg, to appear.

[Z6] , Plain (Lagrange interpolation) proofs of Fancy (representation theory) formulas, in preparation. July 25, 1991