Yesterday Doron Zeilberger talked at the British Combinatorial Conference.

As always it was a stimulating performance, challenging the audience’s assumptions (not least about whether it is permissible to use electronic equipment during a lecture). I won’t discuss the whole thing, but the idea seems worth commenting on.

Suppose you ask your students to prove that the sum of squares of the first *n* natural numbers is *n*(*n*+1)(2*n*+1)/6. Probably they will say: this is true for *n* = 0 (the empty sum is equal to (0·1·1)/6), and then verify that if it is true for a value *n* then it is true for *n*+1 (by adding (*n*+1)^{2} to both sides of the equation). There is also, as he said, quite a good chance that they will not really understand what they are doing, but simply try to parrot what their professor told them.

On the other hand, a student who wrote

- empty sum = 0 = (0·1·1)/6
- 1
^{2} = 1 = (1·2·3)/6
- 1
^{2}+2^{2} = 5 = (2·3·5)/6
- 1
^{2}+2^{2}+3^{2} = 14 = (3·4·7)/6

would get 9 out of 10 from Doron, because all you have to do is mutter an incantation and this is a perfectly valid proof.

In this case, the incantation [my word, he just muttered “mutter something”] is: “both sides are obviously polynomials of degree 3; if they agree at four points then they are the same”.

In a slightly more elevated form, this principle applies to a lot of mathematics. He claims that many papers are published proving results which could be done just be a finite calculation. In his words, every theorem is trivial in God’s eyes, so no paper should be rejected on the grounds of triviality; but some papers, like cigarette packets, should carry warnings that the theorem can be proved by calculation.

His opinion of the Riemann hypothesis is: Odlyzko proved that the first billion Riemann zeros have real part 1/2; sometime in the next fifty years someone will come up with the appropriate incantation to show that only a finite amount of calculation is needed, maybe as few as 50 zeros, so Odlyzko did far more than was necessary.

As usual with Doron’s lectures, I was entertained but not convinced.

### Like this:

Like Loading...

*Related*

##
About Peter Cameron

I count all the things that need to be counted.

Ok, so why is $\sum_{i=0}^n i^2$ “obviously a polynomial of degree three? It doesn’t have the syntactic form of a polynomial. I mean, yes, I know it’s a polynomial of degree three but seeing the word “obvious” makes me suspicious. It seems like it’s hiding a theorem about “sums of polynomials are polynomials” that (when made more explicit) might already have the result you’re trying to prove as a special case, so that invoking the theorem and then listing some examples is no more powerful than invoking the theorem without the examples.

Sorry, a bit of sleight of hand on my part. Looking at differences you can see that a polynomial of degree d satisfies a (d+1)-term recurrence; then sums of sequences satisfying a recurrence theselves satisfy a recurrence. But I agree that something is hidden here; that is one of my problems with this philosophy (it regards this kind of argument as less deep than the laundry-list calculation).

First, thank to Peter for this nice account of my talk. Regarding David Eppstein’s remark, you prove

ONE and FOR ALL a GENERAL theorem

The indefinite sum of a polynomial of degree d is d+1

this can be done in several ways. My favorite is to use the fact that the natural basis

for discrete math are the polynomials f_k(n):=binomial(n,k) and then this fact follows

from the Pascal triangle recurrence. Another way is linear algebra use undetmined coefficients

writing a generic polynomial of degree d+1 and then solving a system of linear equations

with d+2 unknowns and d+1 equations.

This general theorem may one day completely proved by computer, once there is an infra-structure (it may be already in ATP efforts, that I am not familiar with, but that’s not the point)

But ONCE this theorem is established ANY statement of the form

Sum(f(i),i=1..N)= F(N)

is checkable by checking if for 0<=n<=N+1 .

Another way, by the DEFINITION of indefinite sum any such statement is

equivalent to

F(N)-F(N-1)=f(N), and F(0)=0

where both sides are polynomials of degree d.

But that's just a trivial metaphor. In my talk I talked about the C-finite ansatz and there

are lots of papers (and books) that prove identities amongsts them, see

and references therein, and the survey based on my talk

BUT even this is a trivial metaphor. There are many other (some already known,

e.g. the holonomic ansatz and Silviu Radu's beautiful work on automating

Ramanujan-type congruences), and some yet-to-be discovered, including the

fact that that to prove that the real part of all the non-trivial zeros of zeta(s)

equal 1/2 follow from the fact that is is true for the first one hundred (or whatever).

-Doron Zeilberger

Doron, Thanks for your comments, your very stimulating talk at Royal Holloway, and for several conversations there – and for this comment. Peter.