COMPUTERIZED DECONSTRUCTION

Doron ZEILBERGER ^{1}

Abstract: The inequality (DERRIDA+TURING)>(DERRIDA)+(TURING) will be illustrated by computerized deconstruction of Roger Apéry’s miraculous proofs of irrationality.

Preamble

It is a pleasure to be here, and I thank William Sit for inviting me and giving me the opportunity to listen to the fascinating talks by Gert-Martin Gruel and Sam Dooley this morning. I also enjoyed the interesting posters and software demonstrations.

Gert-Martin Gruel started his intriguing talk about SINGULAR by quoting Sir Michael Atiyah’s ‘provocative’ statement ([At]) that likened the use of Computer Algebra Systems (and more generally of algebra itself) to a Faustian agreement whose cost is the sale of the ‘geometrical intuition’ soul. This made Gert-Martin feel a bit guilty.

While a guru like Atiyah deserves to be taken seriously no matter what he says, I disagree with his prejudiced statements whose anthropocentric tenor reminds me of another (one-time) Oxford don, G.H. Hardy. Hardy’s ‘apology’ used to outrage me, with the artificial and fictional dichotomy of pure vs. applied, trivial vs. non-trivial, and mathematics being a ‘young man’s game’. In fact the hero of today’s talk, Roger Apéry, is a great counterexample to the last statement, since he was sixty-two when he made the breakthrough that was going to immortalize him.

Because of Sir Michael’s immense stature, most people who disagree with him feel that they have to be polite and defensive. One beautiful defense of combinatorics, and more generally of the ‘problemsolving culture’, against Atiyah’s ‘theory-building’-supremacy, was launched by Tim Gowers[G]. I highly recommend it!

But another strategy of rebuttal to elitist and prejudiced opinions is offense. So let me counteract provocation by provocation, and state the following:

Computer Algebra Systems are NOT the Devil but the new MESSIAH that will take us out of the current utterly trivial phase of human-made mathematics into the much deeper semi-trivial computer-generated phase of future mathematics. Even more important, Computer Algebra Systems will turn out to be much more than just a ‘tool’,

rence,AperyAcc,AperyAppx available from

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg@math.rutgers.edu , http://www.math.rutgers.edu/~zeilberg/ . First version: June 21, 2002. Expanded version of a plenary talk given at ECCAD 2002, LaGuardia Community College of the City University of New York, May 18, 2002, organized by William Sit and Jerry Ianni. Accompanied by the Maple packages PADE,AperyWZ,AperyRecurhttp://www.math.rutgers.edu/~zeilberg/apery.html . Supported in part by the NSF.

since the methodology of computer-assisted and computer-generated research will rule in the future, and will make past mathematics seem like alchemy and astrology, or, at best, theology.

Developers of CASs, and the people who design and implement the algorithms, are the unsung heroes of this budding revolution. Even today CASs are still a marginal subject (sociologically speaking, of course). For example, it is a scandal that Bruno Buchberger, whose impact on mathematics, present and future, is at least as great as Atiyah’s, does not get the same recognition as the latter. But all revolutions take time, and let’s hope that once we become top dogs, we will be kinder and more tolerant to the future underdogs, including those that will continue to practice ‘naked-brain math’.

Geometrical vs. Combinatorial Intuition

According to Atiyah, the first half of the 20th century was dominated by Hilbert (i.e. ‘formalism’ and algebra) while the second half was dominated by Poincaré (‘geometrical intuition’, the reign of Topology). Between the lines he patronizes the mathematicians of the 19th century with their focus on the local and on explicit formulas.

But, as Tim Gowers has recently pointed out to me, combinatorial intuition, that is behind humans’ symbolic manipulation capabilities, is equally important for progress. Hence it is unfair and untrue to emphasize geometrical intuition at the expense of our, at least as important, combinatorial intuition, and dismiss algebra as ‘mindless turning of a crank’.

Ultimately, Hilbert’s formalist approach will prove the winner (if contest it is). After all, as was observed by Gregory Chaitin, it lead, via Turing, to programming, which is the epitome of formalism. Now Programming will survive long after Topology will be forgotten.

Furthermore, you can only go so far with ‘geometrical intuition’. Atiyah himself admits that Topology greatly advanced thanks to physics (e.g. Yang-Mills, Seiberg-Witten). But he seems to be unaware that it is not the ‘physical intuition’ in the physics, but the combinatorial nature of the physics culture that was so crucial. Once combinatorics will get more advanced (thanks to computers), it will advance Topology, and everything else, much more.

Math and Philo

Math is perfect (in principle), but mathematicians are not (because they are humans), hence the mathematics that (human) mathematicians do is influenced by the weltanschauung of the people around them. For example the intuitionists were influenced by phenomenology, and the Bourbakists by structuralism. Not to mention the notorious Nazi mathematicians who believed in German intuition as opposed to ‘Jewish’ formalism (never mind that Hilbert was a Protestant). Conversely, mathematics had a profound influence on philosophy as far back as Pythagoras, through Plato, Spinoza, Kant, Frege, Wittgenstein, Russel, Husserl, Heidegger, and almost everybody, all the way to Derrida. Speaking of Derrida, Vladimir Tasic has a very insightful paper[T], soon to be expanded into a book, about Deconstruction and mathematics.

In this lecture, I will not discuss philosophy per se, but will attempt to show how Derrida’s seminal insights have the potential to revolutionize the practice of doing mathematics. When interfaced with the computer, of course.

Not all mathematicians and scientists appreciate Jacques Derrida, and for some, like Alan Sokal, he is a dangerous enemy of science and ‘progress’, since he, along with his fellow postmodernists, seem to undermine the blind faith of most mathematicians in immutable truths. But I am sure that once we get over these hang-ups, and learn how to deconstruct mathematics, both globally and locally, we will be much better off, and this will enable us to advance mathematics from its present utterly trivial state to a much more advanced, semi-trivial, state.

Global Deconstruction of Math

Jacques Derrida deconstructed Western metaphysics by challenging binary opposites like cause and effect, presence and absence, speech and writing, and identity and difference, with a tacit dominant concept in every pair. We should likewise deconstruct the pairs rigorous vs. non-rigorous (see [Z2]), pure vs. applied, theorem vs. conjecture, empirical vs. theoretical, and a priori truth vs. experimental truth, and the closely related dichotomy deduction vs. induction.

As argued in [Z2], the default proof, in the future, will be non-rigorous, since we won’t be able to afford completely rigorous proofs, except for the most trivial results, with semi-rigorous proofs a transitional compromise. The supremacy of pure mathematics, fortunately, is already declining, as it is realized that the distinction is only sociological. Also, in the future, the lines of demarcation between ‘theorem’ and ‘conjecture’ will be blurred, and all (non-trivial) knowledge, even ‘theoretical’, will be empirical and inductive, in the sense that it will be all computer-generated.

Local Deconstruction

Since so far mathematical proofs are written by humans, they always suffer, to varying extents, redundancy and hiding the bottom-line idea in a smoke-screen of human fluff. Also, sometimes a good proof starts out combinatorial, but then gets ruined by “mainstreamers” who dislike both “combinatorics” and “heavy computations”. For example, I LOVE, and really understand, Viggo Brun’s beautiful and seminal original paper on the Goldbach problem, and the subsequent improvements by Buchstab, Wang, Chen, and others. But when I tried to read a contemporary account I got very depressed. All the beautiful combinatorial ideas got ruined by human verbiage, boring definitions, and endless notation.

In this lecture, I will propose a methodology of starting out with a human proof, stripping it of its tacit human over-head and fluff, then ENCAPSULATING and formalizing it as COMBINATORIAL OBJECTS (in the general sense, in which algebra is part of combinatorics), then PROGRAMMING and trying to let the computer try to find new objects of the same kind. Often, the formalized object suggests natural generalizations, that in turn, can be programmed, and this can continue indefinitely, always getting feedback from the computer’s output.

This is, in a way, a computerized version of Tim Gowers’s Pólya project (see his website).

Now, when I say proof, I don’t always mean it in the Euclidean sense of a sequence of statements glued by logical deduction. Many so-called proofs are really algorithms or other objects (equations, recurrences, etc.) in disguise, and once deconstructed can often be found by computer-search.

I will illustrate this methodology by deconstructing, in four different ways, one of my all-time favorites: Roger Apéry’s proof of the irrationality of ζ(3).

The immediate motivation, of course, is to find irrationality proofs of other (preferably famous) constants. Although I haven’t succeeded yet, I believe that with more systematic and extensive computer searches, this will come to pass. Even more importantly, the methodology illustrated here should be instrumental in solving other major open problems.

While my computer and I couldn’t find new irrationality proofs, we did find lots of new stuff, notably new accelerating recurrences for certain families of constants defined by slowly-converging infinite series.

A Crash Course on Irrational Numbers

The first crisis in mathematics, about 2500 years ago, was caused by the discovery that the squareroot of 2 is not a ratio of integers, and we all know the standard proof. However, the original proof was better, and in modern notation it says that if m > n are integers such that m^{2} − 2n^{2} = 0 then so are m′ = 2n − m and n′ = m − n. Now this reduction formula could have been easily found by computer. This is an example of an ansatz ( in this case linear reduction) that encapsulates an approach, and makes it amenable to computer search.

It is an easy exercise to prove that e is irrational (do it right now!, Hint: consider the partial sums), but it is not quite as easy, but still not too hard, to do it for π. This was first proved by Lambert about 250 years ago. Yet no one has any clue today how to prove the irrationality of e + π, eπ (at least one of them is, though (why?)), The Euler-Mascheroni constant γ, Catalan’s constant C, or ζ(2k + 1) for k > 1. Hence it was very exciting news, back in 1978, when Roger Apéry proved that ζ(3) is irrational.

The general approach used by Apéry , that probably goes back to Euler, for proving the irrationality of a given constant α is to construct (explicitly, or recursively, or at any rate, effectively) a sequence of rational numbers a_{n}/b_{n} (where a_{n} and b_{n} are integers), such that a_{n}/b_{n} → α ‘fast enough’, more precisely, such that there exists δ > 0 and a constant C > 0 such that for all n > 0,

0 < |\frac{a_{n}}{b_{n}} − α| < \frac{C}{b_{n}^{1+δ}} .  (AP P X)

To deduce irrationality, assume that α = c/d, then

|\frac{a_{n}}{b_{n}} − α| = |\frac{a_{n}}{b_{n}} − \frac{c}{d}| = |\frac{a_{n}d − b_{n}c}{db_{n}}| > \frac{(1/d)}{b_{n}},

a contradiction.

If the sequence b_{n} is of exponential growth, then it is easy to see that the existence of such a δ implies irrationality measure 1 + 1/δ (see [vdP]), so one game people play is to try to lower the world’s record, by constructing better and better approximating sequences that decrease the known upper bound for the irrationality measure of the studied constant.

Note that whenever b_{n} is of exponential growth, say b_{n} = O(A^{n}) for some A > 1, then the error in the approximation (AP P X) is O(1/(A^{(1+δ)})^{n}), hence is of interest from a numerical-analysis point of view even when δ < 0, provided that δ > −1. If δ is less than 0, but, close to it, there is always hope that some accelerated variant of the approximating sequence will make it. Hence, while it is a major breakthrough to find an approximating sequence for a famous constant with δ > 0, it is still of interest to get δ as big as possible, even if it is negative.

The Continued Fraction Ansatz

There is a well-known, and extremely simple, algorithm to construct a sequence of rational approximations, a_{n}/b_{n}, for any given constant (let’s call it α), with the impressive δ = 1! The algorithm is called continued fraction conversion, and the a_{n}/b_{n} are the so-called convergents.

In Maple one types:

convert(alpha, confrac, a) ;

and then typing a; will give you the sequence of convergents up to the precision implied by Digits. Setting Digits higher and higher, will get you further and further.

There is only one slight problem with this beautiful idea. The sequence {a_{n}/b_{n}} has to be an infinite sequence, in other words, the continued-fraction expansion must be non-terminating, in other words, the constant α must be irrational. But that is exactly what we are trying to prove!, so this is circular reasoning.

But, if we (or the computer) can guess a pattern, belonging to an explicit ansatz, then we can define α′ to be the constant that is given by the infinite (simple) continued fraction obeying that pattern. Then we can prove (either manually or, preferably, automatically) that α′ = α, and since α′ is a priori irrational (being given by an effective infinite simple continued fraction), we have a proof that α is indeed irrational.

To emphasize the simplicity of this approach, let me not use the built-in Maple continued-fraction conversion command, but a home-made one, CF(a,k), that inputs a constant a and an integer k, and outputs the first k terms in its continued-fraction representation.

CF:=proc(a,k) local n:  Digits:= 100:
if k=0 then RETURN([]) else n:=trunc(evalf(a)):RETURN([n,op(CF(1/(a-n),k-1)]):  fi:
end:

Now the fun begins!

Typing: CF(sqrt(2),20); would immediately return: [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2].

You don’t have to be a genius to conjecture that the continued fraction of \sqrt{2} is [1, 2^{∞}]. Calling this latter number α′, we see immediately that α′ = 1 + 1/α′′ where α′′ = [2^{∞}], which implies that α′′ = 2 + 1/α′′, which yields α′′ = 1 + \sqrt{2}, and hence α′ = \sqrt{2}, QED.

I did the above example in great detail in order to illustrate that it can be easily mechanized. The computer can be trivially programmed to do the following steps: (i) detect the ultimate period of the sequence (of course of bounded length) , (ii) define the conjectured infinite continued fraction, (iii) find automatically the algebraic equation it satisfies, and finally (iv) identify it with the input constant, that in this case has to be a solution of a quadratic equation.

Of course, this is but an extremely simple toy example. We already know, thanks to Legendre, that a continued fraction is ultimately periodic if and only if it is a quadratic irrationality, and we also know the classical and easy result, that algebraic numbers whose minimal equation have degree higher than one are irrational. But, if we did not know that, then the above procedure could be used to proved the irrationality of \sqrt{5}, \sqrt{7}, etc., and at the same time establish their optimal irrationality measure, which is 2.

Another example is CF(sqrt(3),20); that yields

[1,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1],

and we are immediately lead to conjecture that \sqrt{3} = [1, (1, 2)^{∞}], and once conjectured, it is trivial (and purely mechanical) to prove.

A more interesting pattern emerges with CF(exp(1),20); that yields

[2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,1,1] ,

for which it is also easy to detect a pattern. It is slightly harder to prove from scratch that the infinite continued fraction of e is indeed what the above suggests (one has to find a more general statement, also by computer experimentation, and then use WZ theory).

Consider instead the better looking:

CF((exp(1)-1)/(exp(1)+1),20); that yields
[0,2,6,10,14,18,22,26,30,34,38,42,46,50,54,58,62,66,70,74] .

Just as easy is

CF((exp(1/2)-1)/(exp(1/2)+1),20); that yields
[0,4,12,20,28,36,44,52,60,68,76,84,92,100,108,116,124,132,140,148] ,

and

CF((exp(1/3)-1)/(exp(1/3)+1),20); that yields
[0,6,18,30,42,54,66,78,90,102,114,126,138,150,162,174,186,198,210,222] .

From which the human (or machine!) can easily guess that the continued-fraction of (exp(1/k) − 1)/(exp(1/k) + 1) is

[0, 2k, 6k, 10k, 14k, …, (2 + 4i)k, …].

Now this more general statement can easily be proved, both by human and machine.

Empirical AND Rigorous Math

The general strategy for using computer experiments in order to obtain rigorous results is the following.

Step 1: Input P roblem(n), parameterized by integer n.

Step 2: Apply a standard (or new) numerical algorithm to get Answer(n) for n = 1, 2, ..., 100 (or whatever).

Step 3: Have the human, or much better still, the machine, guess, from the output of Step 2, the symbolic answer Answer(n), for symbolic n (being a nominalist, I prefer to talk about n as a letter rather than say arbitrary n; the latter reflects Fortran mentality of thinking of n as a variable standing for concrete integers). How can a machine guess? Easy. All you have to do is teach it ansatzes to do ‘curve-fitting’, e.g. the Salvy-Zimmermann Maple package gfun, or Sloane’s superseeker (based on the former, I believe, that in turn was inspired by the pioneering efforts of Simon Plouffe). See also my package (available from my website) SCHUTZENBERGER.

Step 4: Have the machine automatically prove the guess of Step 3, by ‘plugging’ Answer(n) into the algorithm, keeping n as a symbol. This should imply a certain identity, that should be automatically provable provided it belongs to the right ansatz, for example rational functions (since Viete), or the holonomic ansatz (since WZ). If it does not fit into a known ansatz (framework) you can either cheat and find a human (possibly computer-aided) ad-hoc proof, or better still, develop a new algorithmic proof machine for a new ansatz that will include Answer(n) and the needed identity. Also remember the Pólya Principle, of finding the trivializing generalization, that is, look for Answer′(n, m_{1}, m_{2}, ..) that is algorithmic, and such that Answer(n) = Answer′(n, 0, 0, ..).

Another Venerable Algorithm: Padé Approximation

Recall that if a function f(x) has a Taylor expansion around x = 0, then the (m, n) Padé approximant is the rational function P_{m,n}(x)/Q_{m,n}(x), where P_{m,n}(x), Q_{m,n}(x) are polynomials in x of degrees m and n respectively (and Q_{m,n}(0) ≠ 0), and

f(x) − \frac{P_{m,n}(x)}{Q_{m,n}(x)} = O(x^{m+n+1}) ,

or equivalently,

f(x)Q_{m,n}(x) − P_{m,n}(x) = O(x^{m+n+1}) .  (P ade)

Now, using undetermined coefficients, one can easily write a simple procedure that inputs f(x), and specific integers m and n, and outputs the corresponding P_{m,n}(x) and Q_{m,n}(x). All one has to do is use basic linear algebra that is built-in in Maple (and of course in most other systems), via solve (or its more specialized variant linsolve).

While Padé approximation is built-in in Maple, it is always a good idea to write your own version, since then it is easier to modify and generalize. Hence I wrote my own home-made package PADE, available from the website of this article. Let’s play with e^{x}.

First download PADE to your current directory. Then go into maple by typing maple (or xmaple, or clicking on the Maple icon or whatever is applicable on your computer). Once in Maple, type read PADE; (depending on the system, you may have to type-in the full path). Now follow the on-line help. The main procedure is Pade1, whose syntax is Pade1(f,x,m,n);.

Inputting Pade1(exp(x),x,1,1); yields

−\frac{2 + x}{−2 + x} ,

while inputting Pade1(exp(x),x,2,2); yields

\frac{12 + 6x + x^{2}}{12 − 6x + x^{2}} ,

and inputting Pade1(exp(x),x,3,3); yields

−\frac{120 + 60x + 12x^{2} + x^{3}}{−120 + 60x − 12x^{2} + x^{3}} ,

and inputting Pade1(exp(x),x,4,4); yields

\frac{1680 + 840x + 180x^{2} + 20x^{3} + x^{4}}{1680 − 840x + 180x^{2} − 20x^{3} + x^{4}} .

It is obvious already that there must be some “pattern”, if nothing else because the coefficients are round, i.e. products of small primes, which usually indicates that they are expressible in terms of factorials. Since the denominator Q_{n,n}(x) seems to equal P_{n,n}(−x), let’s focus on the numerator, P_{n,n}(x). In order to study the coefficients, let’s define on the fly,

a:=(i,j)->coeff((-1)**i*numer(Pade1(exp(x),x,i,i),x,i-j);

Now the leading coefficients, for i = 0 … 10, are obtained by typing

seq(a(i,0),i=0..10); ,
which returns 1,1,1,1,1,1,1,1,1,1,1 .

Hence we are safe in conjecturing that a(i, 0) = 1 for all i ≥ 0. Next, let’s look at the second-to-leading coefficient, by typing

seq(a(i,1),i=0..10);
which returns: 0,2,6,12,20,30,42,56,72,90,110 .

Any human with IQ ≥ 110 can guess that a(i, 1) = i(i + 1). To be more sure, we can type

seq(a(i,1)/(i*(i+1),i=1..20);
and indeed get : 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 .
Next, let’s type: seq(a(i,2),i=1..10); .

This looks a bit more complicated, but inspired by the conjectured explicit expression for a(i, 1), let’s try

seq(a(i,2)/(i*(i+1)),i=1..10);
which returns: 0,2,5,9,14,20,27,35,44,54 .

This is clearly (i − 1)(i + 2)/2, for i = 1..10. This leads us to input:

seq(a(i,2)/((i-1)*i*(i+1)*(i+2)/2),i=2..20);
with the output: 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 .

Even though there is already a “pattern of patterns” emerging, in order to be safe, try next:

seq(a(i,3)/((i-2)*(i-1)*i*(i+1)*(i+2)*(i+3)/6),i=3..20);

with the outcome

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 .

And finally define

b:=(i,k)->a(i,k)-(i+k)!/((i-k)!*k!);,

and test:

seq (seq(b(i,k),i=1..12),k=1..10);

to get the very promising output:

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0 .

This leads us to conjecture that:

P_{n,n}(x) = ∑_{k=0}^{n} \frac{(n + k)!}{(n − k)!k!}x^{n−k} ,  (P adeNumer)

and

Q_{n,n}(x) = ∑_{k=0}^{n} \frac{(n + k)!}{(n − k)!k!}(−x)^{n−k} .  (P adeDenom)

But this is all very nice, would the humanist say, yet it is still just a conjecture, we surely need a human to prove this conjecture for all n, don’t we?

As a matter of fact, we don’t! Plugging the symbolic answers (P adeNumer) and (P adeDenom), and

e^{x} = ∑_{k=0}^{∞} \frac{x^{k}}{k!} ,

into (P ade), and comparing coefficients on both sides, results in a binomial coefficients identity, that thanks to W and Z (and of course, Sister Celine) is now completely automated. In this very simple example the identity turned out to be well-known (it is Vandermonde-Chu), but that’s a historical accident.

The next argument of the human chauvinist would be that perhaps each step is computer-aided, or even computer-generated, but the above derivation, as a whole, is human reasoning par excellence, the way Euler, Gauss, Riemann, Ramanujan, and all the other great (and not-so-great) mathematicians have always worked, but using paper-and-pencil instead of a computer. Hence the only difference is quantitative, where the computer fills-in the details a bit faster. Hence (would the humanist continue), this is not a true paradigm shift, but merely one of convenience. Recall George Andrews’s famous line: “a computer is nothing but a pencil with power-steering”.

To this wicked son thou shall reply: all the above steps, of guessing, and meta-guessing, and formulating the general conjecture, and proving, can be combined automatically, and then it would be done much faster than the above ‘interactive’ mode. It is true that, since at present the programming is still done by humans, it may be a good idea to first get a feel for it by playing interactively, but NOT for proving ‘new results’, that’s a waste of time! The only purpose is to inspire us to write a good guessing/proving program, that ultimately can explore many more ansatzes, and look for much more complicated patterns, than any human can do, even by interacting with a computer.

To get an irrationality proof for e = exp(1), plug-in x = 1. P_{n,n}(1) and Q_{n,n}(1) are obviously integers, and the Zeilberger algorithm gives a three-term recurrence that easily implies the wellknwon fact that the irrationality measure of e is exactly 2.

Apéry’s Miraculous Proof

Apéry’s original proof, as described in his notorious June 1978 Marseille-Luminy talk (see [vdP]) was a sketch consisting of unlikely assertions. The details were worked out by Henri Cohen and Don Zagier, and were beautifully described in van der Poorten’s lively exposition.

Here is a summary:

Step 1: The sequence of partial sums of ζ(3),

c(n) := ∑_{m=1}^{n} \frac{1}{m^{3}} ,

converge extremely slowly to ζ(3). Hence, let’s pull out of the hat the following double sequence

c(n, k) := ∑_{m=1}^{n} \frac{1}{m^{3}} + ∑_{m=1}^{k} \frac{(−1)^{m−1}}{2m^{3}\binom{n}{m}\binom{n+m}{m}} ,

that has the property that c(n, k) → ζ(3) as n → ∞, uniformly in k. In particular, |ζ(3) − c(n, n)| is exponentially small.

Step 2: The drawback of the c(n, n) is that they seem to have a huge denominator, so the implied (experimental) δ in very negative. On the other hand the denominators of the c(n) = c(n, 0) are not too bad, they are lcm(1, 2, …, n)^{3} = O(e^{3n}). So let’s try to form a weighted average, for a judicious choice of weights b(n, k),

x_{n} := \frac{∑_{k=0}^{n} b(n, k)c(n, k)}{∑_{k=0}^{n} b(n, k)} .

Now, let’s pull out of the hat the choice

b(n, k) = \binom{n}{k}^{2}\binom{n + k}{k}^{2} ,

and Voilá!, modulo checking out the details, the sequence of rational numbers x_{n} has the desired property: |ζ(3) − x_{n}| < C/denom(x_{n})^{1+δ} for δ = .08 … > 0.

But how in the world did Apéry come up with this miraculous c(n, k) and b(n, k)? In [Z1] (section 13), I placed Apéry’s proofs in the context of WZ theory, and indeed succeeded in mechanizing all the steps but one (the very easy human step of proving that 2c(n, k)\binom{n+k}{k} has denominator equal to lcm(1, 2, …, n)^{3}). All this is now streamlined and generalized in the new Maple package AperyWZ. I also wrote general procedures that input arbitrary W Z pairs and arbitrary (closed-form) weights b(n, k), trying to find the corresponding δ for the new constants that emerge.

A User’s Manual for the Maple package AperyWZ

Download AperyWZ from the website of this article

http://www.math.rutgers.edu/~zeilberg/apery.html,

and also download EKHAD, and put them in the same directory. To get on-line help for AperyWZ type Ezra(); (ezra(); is for help with EKHAD). To get help with a specific procedure, type Ezra(procedure name); . One of the important procedures is zeilWZPv, and to get help with it type: Ezra(zeilWZPv); (its terse version is simply zeilWZP).

As suggested there, try:

zeilWZPv(binomial(n,k)*binomial(n+k,k),WZlog2,k,n,N) ;
zeilWZPv(binomial(n,k)**2*binomial(n+k,k),WZzeta2,k,n,N);
zeilWZPv(binomial(n,k)**2*binomial(n+k,k)**2,WZzeta3,k,n,N) ;

to automatically perform all the non-trivial steps in Apéry’s proofs of the irrationality proofs of log 2, ζ(2) and ζ(3) respectively.

WZlog2, WZzeta2, WZzeta3 are the WZ-pairs that give rise to the miraculous c(n, k) (as potential function) constructed by Apéry for the irrationality proofs (see [Z1]).

You should also check out Acc, that automatically produces (rigorously!) the famous accelerated sums that are spin-offs of Apéry’s proofs, and here one can easily get lots of new results. Look also at Constant1. See the sample input and output files in

http://www.math.rutgers.edu/~zeilberg/apery.html .

How to get new WZ-pairs?

One gold mine of WZ-pairs are explicit well-known hypergeometric identities. The WZ-pairs that feature in the irrationality proofs of log 2, ζ(2) and ζ(3) turn out to be specializations of the WZpairs that come from the Vandermonde-Chu, Kummer, and Dixon identities, respectively.

The procedures WZchu, WZkummer, WZdixon allow one to construct other WZ pairs.

Starting Out from Binomial Coefficients Sums

Sometimes it pays to rewrite history, and not worry so much how brilliant proofs were actually made, but how they could have been made or perhaps should have been made.

So forget about ζ(3), ζ(2), log 2 or any other specific constant, and let’s take as our starting point a binomial coefficient sum

b(n) := ∑_{k=0}^{n} b(n, k) ,

where b(n, k) is a hypergeometric term. Thanks to the so-called Zeilberger algorithm and WZ theory, it satisfies some homogeneous linear recurrence equation with polynomial coefficients, with the obvious initial values b(0) = b(0, 0), b(1) = b(1, 0) + b(1, 1), . . .. Now define an associated sequence a(n), as the solution of the same recurrence with other initial values, (e.g. if ORDER=2 then take a(0) = 1, a(1) = 0). Then, if all goes well (and often it does), a(n)/b(n) converges to some (as yet unknown) number α, and since the convergence is fast, we can determine α to high precision.

Then we go to Borweins’ RevENG website, or send E-mail to Simon Plouffe, and check if the constant α is well-known, and not yet proved to be irrational. And if things go really well it would be (conjecturally for now). Then you go back and find, still empirically a δ such that |a(n)/b(n)−α| < C/(denom(a(n)/b(n))^{1+δ}. If things go amazingly well then δ > 0, and you would almost have a proof that α is irrational. Of course, you would still have to prove rigorously that your α is the same as the one suggested by RevENG, and that indeed δ > 0. But this shouldn’t be too hard, with such a high motivation.

This is implemented in the Maple package AperyRecurrence.

The Maple package AperyRecurrence

After downloading it, make sure that you also have EKHAD in the same directory. Now go into

Maple and type: read AperyRecurrence;, followed by Ezra();.

The main procedure is Roger. For example, to reproduce the Apéry miracles type:

Roger(binomial(n,k)*binomial(n+k,k),k,n,20, 40);
Roger(binomial(n,k)**2*binomial(n+k,k),k,n,20, 40);
Roger(binomial(n,k)**2*binomial(n+k,k)**2,k,n,20, 40);

since the second component, δ, is positive, this means that there probably is an irrationality proof behind the approximating sequence. Since the first components are ‘famous’ (log 2, ζ(2), ζ(3) respectively), there would have been reason to rejoice, had it been discovered this way. See the sample input and output files in the webpage mentioned above.

It would be interesting to conduct a systematic search, coupled with the RevENG machine.

Apéry’s ORIGINAL Proof

It is hard to believe that any human (or even computer) can pull out of the hat the ‘winning’ c(n, k) and b(n, k) that produced the irrationality proofs, even by WZ-hindsight. Frits Beukers [Be] was able to dispel some of the magic, and do away with recurrences, and his interesting approach deserves its own computerized deconstruction. Beukers’s approach was extended by Hata[Ha], and Rhin and Viola, who hold the current record for the irrationality measure of ζ(3).

But the mystery still remained: How in the world did Apéry come up with his marvelous proof?.

Fortunately for posterity, Roger Apéry gave away his secret, in a little-cited, somewhat sketchy, but gorgeous paper [Ap], entitled “Interpolation de fractions continues et irrationalité de certaine constantes” published in 1981 by the French National Library in their Bulletin de la section des sciences du C.T.H.S. #3 p. 37-53. One should also mention the exposition and elaboration of Apéry’s ideas (delivered in a Bordeaux talk) by C. Batut and M. Olivier [BO], that was an excellent human deconstruction. But for our purposes it is best to read the master rather then the disciples, and I will now follow Apéry’s account in [Ap] very closely.

A Human Description of Apéry’s Brilliant Acceleration-Convergence Approach

The terms of the sequence of partial sums of ζ(3),

\frac{a(n)}{b(n)} := ∑_{i=1}^{n} \frac{1}{i^{3}} ,

have relatively ‘small’ denominators (lcm(1, …, n)^{3} = O(e^{3n})) but very slow convergence.

Let’s write

b(n) = n!^{3} , a(n) := n!^{3}(∑_{i=1}^{n} \frac{1}{i^{3}} )

Then we have

b(n + 1) − (n + 1)^{3}b(n) = 0 , a(n + 1) − (n + 1)^{3}a(n) = b(n) .

Introducing the shift operator N, where, for any sequence f(n), N^{r}f(n) := f(n + r), the above can be written as

(N − (n + 1)^{3})b = 0 , (N − (n + 1)^{3})a = b ,

and applying (N − (n + 1)^{3}) to both sides yields

(N − (n + 1)^{3})^{2}b = 0 , (N − (n + 1)^{3})^{2}a = 0 .

Expanding gives:

b(n + 2) − ((n + 2)^{3} + (n + 1)^{3})b(n + 1) + (n + 2)^{3}(n + 1)^{3}b(n) = 0 ,
a(n + 2) − ((n + 2)^{3} + (n + 1)^{3})a(n + 1) + (n + 2)^{3}(n + 1)^{3}a(n) = 0 .

Hence ζ(3) may be defined as lim_{n→∞} a(n)/b(n) where a(n) and b(n) are both solutions of the same recurrence, namely

x(n + 2) − ((n + 2)^{3} + (n + 1)^{3})x(n + 1) + (n + 2)^{3}(n + 1)^{3}x(n) = 0 ,

but with different initial values: b(0) = 1, b(1) = 1, and a(0) = 0, a(1) = 1.

Now we can forget about the original definition of ζ(3) (as an infinite series) and define it, uniquely, by the three-tuple

[ope(N, n), [a0, a1], [b0, b1]] .

Now let P (n) be any discrete function, and perform the transformation

x(n) → P (n)x(n) + x(n + 1) ,

Defining a′(n) = P (n)a(n) + a(n + 1) , b′(n) = P (n)b(n) + b(n + 1), we have

lim_{n→∞} a′(n)/b′(n) = lim_{n→∞} a(n)/b(n) .

But Apéry is trying to look for a judicious choice of P (n) such that the rate of convergence of

lim_{n→∞} a′(n)/b′(n)

to the desired constant, ζ(3), is faster then the rate of convergence of the original

lim_{n→∞} a(n)/b(n) .

Using elementary linear algebra (that is easily programmed in Maple), one can get (automatically) the 2nd order recurrence operator Ope_{1}(N, n) annihilating x′(n) = P (n)x(n) + x(n + 1).

So far P (n) could have been anything, but if one wishes to stay in the holonomic ansatz , we have to restrict attention to polynomial P (n). Writing P (n) in generic form, in increasing powers of n,

P (n) = c_{0} + c_{1}n + c_{2}n^{2} + … + c_{d}n^{d} ,

(where d is the guessed degree of P (n)), and plugging it in, we get the operator Ope_{1}(N, n) whose coefficients of N^{0}, N^{1}, N^{2} are polynomials in n and quadratic in the (yet) undetermined coefficients c_{0}, c_{1}, …, c_{d}. It turns out that for best convergence, the coeff. of N^{2} in Ope_{1}(N, n) should be of degree 0 in n. Hence to find the good c_{0}, c_{1}, …, c_{d}, we (or the computer) have to solve a system of non-linear (in fact quadratic) equations in the unknown coefficients c_{0}, c_{1}, …, c_{d}. There is no a priori guarantee that there is a solution, or that the solution would consist of rational numbers. But, as Apéry put it, si on a de la chance, things work out.

Now we have a new operator description of the desired constant,

[[Ope_{1}(N, n), [a0′, a1′], [b0′, b1′]] ,

where the coefficient of N^{2} in Ope_{1}(N, n) is a constant (or in general, of the smallest possible degree (in n) as possible), and a0′ = P (0)a0+a1, a1′ = P (1)a1+a(2), b0′ = P (0)b0+b1, b1′ = P (1)b1+b(2).

Now let’s try and repeat this process indefinitely. Let’s call the previous P (n), P_{0}(n). Then we next get (hopefully) a good P_{1}(n) that turns the already better Ope_{1}(N, n) into something better still, Ope_{2}(N, n). If all goes well, we can keep going indefinitely, getting a sequence of 2nd-order recurrence operators {Ope_{m}(N, n)} and accelerating polynomials P_{m}(n).

Now the second miracle that happened to Apéry (for log 2, ζ(2), and ζ(3)) was that not only did the increasingly better Ope_{m}(N, n), and the accompanying P_{m}(n), seem to exist for all m, but something even more amazing happened.

It turned out that Ope_{m}(N, n) and P_{m}(n) are also polynomials in the index m! Now if Ope_{m}(n, N) and P_{m}(n) are indeed polynomials in m, then it is easy for the computer to guess them, and we can write Ope_{m}(n, N) = OP E(m, n, N) and P_{m}(n) = P(m, n), then plugging the symbolic P(m, n) into the accelerating procedure described above with OP E(m, n, N) as input, should give the output OP E(m + 1, n, N), and this would be a rigorous proof of the scheme.

Calling the solutions of the ‘m^{th}-row’, a(m, n) and b(m, n), we now have a two-dimensional scheme such that for each m,

lim_{n→∞} \frac{a(m, n)}{b(m, n)} = ζ(3) ,

for every m ≥ 0, where the convergence rate gets better and better as m increases.

The next miracle was that b(m, n) was not only divisible by n!^{3} (as was to be expected) but by m!^{3}n!^{3}. Finally {A_{n}/B_{n}} where B_{n} := b(n, n)/n!^{6} and A_{n} := a(n, n)/n!^{6}, turned out to be the winning sequence that converges to ζ(3) fast enough to get a positive δ.

Note that the acceleration-improvements from one row to the next is only polynomial, i.e. the δ for each individual row is still the worst-possible δ = −1. But, like for Cantor and Turing, the diagonal saved the day.

With this (original) Apéry approach, it is not necessary to use the Zeilberger algorithm, one can automatically get the recurrence satisfied by both a(n, n) and b(n, n) (and hence by A_{n} and B_{n}), automatically using elementary linear algebra as follows.

The two-dimensional scheme is uniquely defined by x(0, n) = x_{0}(n) and

x(m + 1, n) = P(m, n)x(m, n) + x(m, n + 1) .

In operator notation we have that x(i, n) = a(i, n) and x(i, n) = b(i, n) are annihilated by the operator M − I − P(m, n)N (where M is the shift operator in m: Mx(m, n) := x(m + 1, n)), as well as OP E(m, n, N). Now using linear-algebra (that has been programmed into AperyAcc described below) we (or rather the computer) can easily find a diagonal recurrence of the form OP ER(m, n, MN) annihilating both a(m, n) and b(m, n), and hence an ordinary recurrence operator OP ER(n, N) annihilating both a(n, n) and b(n, n), and finally one annihilating both A_{n} and B_{n}.

Complete Automation of Apéry’s Heuristic Method

Now that we have the general approach (thanks to the genius of Apéry), we can program all the steps, including the guessing ones, and streamline them, letting the computer do everything, and outputting failure if it does not work out (unfortunately, it does not work for ζ(4) or ζ(5), at least not directly).

A Slightly More Global Approach

In a way, the input was the (ordinary) recurrence operator ope(n, N) (and the initial conditions, but these are not relevant), and the outputs were the polynomial in two variables P(m, n) and the operator OP E(m, n, N). We could find these outputs directly, if they exist, by writing OP E(m, n, N) and P(m, n) generically, letting Maple automatically generate the set of equations implied by OP E(0, n, N) = ope(n, N) and the fact that if x′(n) = P(m, n)x(n) + x(n + 1), where x(n) is a solution of OP E(m, n, N)x(n) = 0 then x′(n) is annihilated by OP E(m + 1, n, N) (this is all done automatically, we never have to see the resulting equations in the guessed coefficients). Then Maple can directly find the miraculous P(m, n), without the intermediate guessing. Of course, solving the system of equations is just implicit guessing, so the difference between the two approaches is not fundamental.

The advantage of the latter approach is that once we find the magic P(m, n) (and its associated OP E(m, n, N)), by doing undetermined coefficients, we don’t have to do the final verification stage (because that’s how we found it in the first-place). In the previous, piecemeal method, the initial P(m, n) was but a conjecture, and one had to verify it. (Not that it is a big deal, it takes a few seconds).

The Maple Package AperyAcc

The downloading is analogous to the previous packages. The main procedures are Aperyh (or if you want the output in operator notation, AperyhOper), and AccRec, AperyNes, AperySeq, Appx, and RatImp. We refer the readers to the on-line help (invoked by typing ezra(); then ezra(procedure name);). Sample inputs and outputs can be viewed in the webpage of this article

http://www.math.rutgers.edu/~zeilberg/apery.html.

Even though I was unable to find new irrationalities, AccRec does give amazing recurrences that converge exponentially fast to constants defined by slowly converging series. For example AccRec(- (2*n-1)**2,-1,n,N); finds in a few seconds, and completely automatically, the recurrence for the fast computation of Catalan’s constant, found, by semi-human means by Zudilin[Zu].

The Trivializing Hindsight

I believe that the procedure explained above (based on Apéry’s own honest account [Ap]) is much more natural and motivated than the official version presented in [vdP], that is the epitome of ad-hocness, and also more natural than Beukers’s elegant version.

But a close scrutiny of Apéry’s approach, as implemented in AperyAcc, leads to yet a simpler approach, at least for the discovery of the proof. Once you have the magic sequence, filling-in the details is a comparably minor task.

Recall that initially

b(0, n) = n!^{3} , a(0, n) = n!^{3} ∑_{i=1}^{n} \frac{1}{i^{3}} .

By repeatedly using a(m+1, n) = P(m, n)a(m, n)+a(m, n+1), and b(m+1, n) = P(m, n)b(m, n)+ b(m, n + 1), we can write

b(m, n) = n!^{3}B(m, n) , a(m, n) = n!^{3}B(m, n) ∑_{i=1}^{n} \frac{1}{i^{3}} + n!^{3}C(m, n) ,

for some polynomials in n, B(m, n), C(m, n), for m = 0, 1, 2, . . .. These can be computed automatically for each specific m, but in general there is no guarantee that there is an explicit expression for it as a function of m and n (although in Apéry’s case it was true).

Hence, we have that the approximants coming from the m^{th}-row

\frac{a(m, n)}{b(m, n)} = ∑_{i=1}^{n} \frac{1}{i^{3}} + \frac{C(m, n)}{B(m, n)} ,

where the degree, in n, of B(m, n), is 2m, and the degree of C(m, n) is 2m − 2. Writing

R_{m}(n) = \frac{C(m, n)}{B(m, n)} ,

we see that the rational function R_{m}(n) is such that

∑_{i=1}^{n} \frac{1}{i^{3}} + R_{m}(n) ≈ ζ(3) ,  (Keruv)

for large n. This means that R_{m}(n) is a ‘rational-function improvement’ added to the partial sums of the defining series of ζ(3) in order to get it to be much closer to ζ(3).

Plugging in n = n − 1 in (Keruv) and subtracting from the original yields

\frac{1}{n^{3}} + R_{m}(n) − R_{m}(n − 1) ≈ 0 ,

and indeed, the left-hand side turns out to be a rational function with denominator of degree 4m+3 and numerator of degree 0!. Of course, it would have been nice if we could have replaced the ≈ by = above, but then ∑_{i=1}^{n} 1/i^{3} would have been Gosperable (i.e. Indefinitely summable in closed-form), which would have meant that ζ(3) was rational, so it is just as well...

So, by hindsight, this is the most straightforward approach! Let’s generalize it to trying to find irrationality proofs (or at least, good diophantine approximations) for constants given by infinite series of the form

α := ∑_{i=1}^{∞} \frac{1}{pol(i)} ,

where pol(i) a polynomial in i.

Define the best partial-sum rational improvement of degree m, to be that rational function, let’s call it again R_{m}(n), of denominator of degree m in n and numerator of degree m − degree(pol, n) + 1 such that the rational function

\frac{1}{pol(n)} + R_{m}(n) − R_{m}(n − 1) ,  (P ashut)

has numerator of least possible degree. It is very easy to write a procedure for finding such R_{m}(n), for any specific positive integer m, by expressing the given rational function in generic form, plugging into (P ashut), and equating to 0 the coefficients of the positive powers of n of the numerator of the resulting rational function, solving, and plugging back. Once again, Maple has to solve a system of non-linear equations with quite a few unknowns, but surprisingly it does it very well, and not only that, the coefficients turn out to be rational numbers (at least in the simple Apéry cases and all the other cases that I have tried).

Once the computer cranked out R_{m}(n) for, say, 0 ≤ m ≤ 30, we look at the sequence of rational numbers

c_{n} := ∑_{i=1}^{n} \frac{1}{pol(i)} + R_{n}(n) ,

and, empirically estimate the δ. If δ > 0 then we should open a bottle of Champagne, and then complete the proof by any means (human, computer, or combination thereof). If the empirical δ is negative, don’t be sad! Better luck next time!

It is true that using this simple approach, even for pol(i) = i^{2} (for ζ(2)) and pol(i) = i^{3} (for zeta(3)) only indicates that a proof is in sight, rather than gives such a proof. But it is not hard to complete this approach into a full proof (if you are feeling lazy, you can always E-mail Don Zagier or Henri Cohen).

What would have worked in Apéry’s cases is the following. Once you have the R_{m}(n) = B_{m}(n)/C_{m}(n) you can use gfun or findrec to guess recurrences for B_{m} and C_{m} in n, and also in m, thereby getting, empirically for now the OP E(m, n, N) and P(m, n) of the previous approach, and once guessed, it is completely routine to finish-up the proof rigorously and automatically using the previous package AccRec.

The Maple Package AperyAppx

All this is implemented in the Maple package AperyAppx, downloadable from this article’s webpage. The main procedure is RatAppx. See the sample input and output files in the webpage of this article. The package handles the more general case of improving the acceleration of the partial sums of convergent series of the form

α := ∑_{i=1}^{∞} \frac{Cf(i)}{pol(i)} ,

where Cf(i) is closed form.

Conclusion

In her excellent book about Derrida, Christina Howells ([Ho], p. 2) describes the Deconstruction strategy practiced by him as follows. “In all his books and essays Derrida is a scrupulous, meticulous, patient reader, determined to disentangle what has been conflated, to bring to light what has been concealed, and to pay scrupulous attention to marginalia and footnotes, in the expectation that what has been relegated to the margins may prove paradoxically central to a less parochial understanding of the text”.

In this lecture, and the accompanying Maple packages, I tried to apply these principles to human mathematical proofs that have been conflated to suit human predilections and writing styles, and that were meant to be consumed by humans.

By careful analysis of a human proof, one can hopefully extract the core ideas and core objects, and then computerize them. Also the marginalia, in this case Apéry’s little known ‘expository’ and motivational paper, proved to be crucial for a successful computerized deconstruction.

This is but a very crude beginning, but I am sure that it is not the end.

REFERENCES

[Ap] Roger Apéry, “Interpolation de fractions continues et irrationalité de certaine constantes” Bulletin de la section des sciences du C.T.H.S. #3 p. 37-53, 1981.

[At] Sir Michael Atiyah, Mathematics in the 20th Century, Bull. London Math. Soc. 34 (2002), 1-15.

[BO] Christian Batut and Michel Olivier, Sur L’Accéleration de la Convergence de certaines Fractions Continues, Séminaire de Théorie des Nombres Année 1979-1989- exposé no. 23.

[Be] Frits Beukers, A note on the Irrationality of ζ(2) and ζ(3), Bull. London Math. Soc. 11 (1979), 268-272.

[G] W. Timothy Gowers, The Two Cultures of Mathematics, in: “Mathematics: Frontiers and Perspectives”, edited by V. Arnold et. al., Amer. Math. Soc., Providence, 2000.

[Ha] Masayoshi Hata, A new irrationality measure for ζ(3), Acta Arith. 92 (2000), 47-57.

[Ho] Christina Howells, “Derrida”, Polity Press, Cambridge, UK, 1998.

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

[T] Vladimir Tasic, Poststructuralism and Deconstruction: A Mathematical History, available from his website.

[Z1] Doron Zeilberger, Closed Form (pun intended!), in: “Special volume in memory of Emil Grosswald”, M. Knopp and M. Sheingorn, eds., Contemporary Mathematics 143 579-607, AMS, Providence (1993).

[Z2] Doron Zeilberger, Theorems for a price: Tomorrow’s semi-rigorous mathematical culture, Notices of the Amer. Math. Soc. 40 # 8, 978-981 (Oct. 1993). Reprinted: Math. Intell. 16, no. 4, 11-14 (Fall 1994).

[Zu] Wadim Zudilin, Apéry-like Difference Equations for Catalan’s Constant, preprint,

arXiv:math.NT/0201024, available from xxx.arXiv.org .