Zeilberger's algorithm in practice

Discussion in 'Math Research' started by Kevin Buzzard, Feb 14, 2005.

1. Kevin BuzzardGuest

For several unrelated reasons I decided it was about time that I learnt
how to use Zeilberger's method to solve combinatorial identities. There
are two that I need to solve at the current time, the easier of which
is

\begin{lemma} If $j\geq1$ and $i\geq j+1$ are integers
then
$$\sum_{a=j}^{i-1}\frac{3(2a+j-1)!j(2i-2a)!}{(a-j)!(a+2j)!(i-a-1)!(i-a+2)!} =\frac{(2i+j)!(j+1)}{(i-j-1)!(i+2j+2)!}.$$
\end{lemma}

In this thread I will attempt to verify this lemma by attempting to
get a computer to generate a proof for me, and I will narrowly fail,
of thing and know the next trick to try. I should say that I don't
actually know if the lemma is true But I've checked it in lots
of cases and am highly optimistic.

Here's (my understanding of) how Zeilberger et al's approach works.
The left hand side of the above piece of TeX looks like

L(i,j):=sum_{a=j}^{i-1} F(i,j,a)

and the right hand side looks like R(i,j). We want to prove L=R.
We'll do this as follows. Firstly we let the program EKHAD8
(available at http://www.math.rutgers.edu/~zeilberg/programsAB.html )
find functions A(i,j), B(i,j) and G(i,j,a) such that

A(i,j)F(i,j,a)+B(i,j)F(i+1,j,a)=G(i,j,a+1)-G(i,j,a)

[This is the clever bit, finding such functions. EKHAD8 finds them
with very little difficulty. The beauty is that once it has found them,
verifying the equation is trivial]. Summing from a=j to i-1
we deduce

(*) A(i,j)L(i,j)+B(i,j)L(i+1,j)=H(i,j)

where H(i,j) is independent of a. We want to prove our identity L(i,j)=R(i,j)
for a fixed j by induction on i>=j+1. The base case i=j+1 is easily checked.
For general i>=j+1 we firstly check that (*) holds if both occurrences of
L(i,j) are replaced by R(i,j)'s; this is easy in my case. Now we'd like
to say that we are done by induction. Unfortunately I don't quite think that
we are, it seems to me that I have to check that B(i,j) is never zero
for any i>=j+1. In my case, unfortunately, B(i,j) has a factor of

2 2 3 4 3 2 2 3 2 2
-9 i j - 9 i j - 9 j + 2 i + 3 i j - 3 i j - 2 j + 6 i + 6 i j + 9 j

+ 4 i + 2 j

and so it seems that I've ended up having to verify that the above polynomial
never vanishes for j>=1 and i>=j+1. I don't know whether this is true, or even
whether to expect that it is true. I also feel that I shouldn't be having
to do this. Can anyone tell me the next trick to try? This phenomenon
is presumably a standard one.

Cheers,

Kevin Buzzard

Kevin Buzzard, Feb 14, 2005

2. Fred the Wonder WormGuest

[ Polynomial rewritten for my convenience using * and ^ ]

f = -9*i^2*j^2 - 9*i*j^3 - 9*j^4 + 2*i^3 + 3*i^2*j - 3*i*j^2
- 2*j^3 + 6*i^2 + 6*i*j + 9*j^2 + 4*i + 2*j
I can't address your more general concerns, but I can show that the
result you want for this polynomial. Firstly, set i = j + 1 + a
and j = 1 + b to change the relevant ranges to a >= 0, b >= 0:

f = 2*a^3 - 9*a^2*b^2 - 9*a^2*b + 12*a^2 - 27*a*b^3 - 90*a*b^2 - 63*a*b
+ 22*a - 27*b^4 - 135*b^3 - 222*b^2 - 114*b + 12

Specialising a to be 0,1,2 successively, the only integral roots b
are seen to be -2, hence we can assume a >= 3. Similarly, for b = 0
the only integral roots for a are -3,-2,-1, so we can assume b >= 1.
Making the further changes c = a+3, d = b+1 gives

f = 2*c^3 - 9*c^2*d^2 - 27*c^2*d + 12*c^2 - 27*c*d^3 - 225*c*d^2
- 486*c*d - 140*c - 27*d^4 - 324*d^3 - 1383*d^2 - 2286*d - 960

Further investigation suggests there are no integral roots for
non-negative c or d, which is cause for hope. Taking the discriminant
of f with respect to c;

Disc(f,c) = -(3*d + 5)*(3*d + 7)*(2187*d^8 + 34992*d^7 + 239841*d^6
+ 918540*d^5 + 2146824*d^4 + 3131136*d^3
+ 2779200*d^2 + 1370880*d + 287488)

This is clearly negative for all d >= 0, thus if we fix d then f is
a cubic in c with exactly one real root. A certain amount of
experimentation and some luck led to noting that this root is quite
close to 9/2*d^2 + 33/2*d + 26/3. It is easy to see that the two
nearest integers bracket the root.

f(9/2*d^2 + 33/2*d + 8, d) = -27*d^4 - 216*d^3 - 609*d^2 - 708*d - 288
< 0
f(9/2*d^2 + 33/2*d + 9, d) = 27/2*d^4 + 108*d^3 + 645/2*d^2 + 426*d + 210
Thus for any integer d >= 0 there is no integral root c (and hopefully

Cheers,
Geoff.

Fred the Wonder Worm, Feb 15, 2005

3. Kevin BuzzardGuest

and Fred the Wonder Worm <> replied:
[elegant proof that the quartic had no integer points]

Thanks also to Dave Rusin for emailing me a proof (essentially the same proof,
in fact).

After taking a day off and then coming back to the problem, I managed
to find the "correct" solution (I was well aware that Wilf and Zeilberger
would not have got the Steele prize for reducing the theory of
combinatorial identities to the (much much harder) theory
of finding integer solutions to equations!). For those that are
interested, here's what to do: I wanted to prove a result of the form
told me how to solve problems of the form sum_a F(n,a)=G(n). So I had
one variable too many. I decided to just set n=i and then try to solve
infinitely many problems, one for each j. I ran into difficulties; there
might be finitely many j for which the strategy doesn't work.
I then set n=j and tried letting i be the free variable. I ran into
the same difficulties. I really just wanted to work in a rational
function field C(j) and to prove sum_a F(a,i,j)=G(i,j) as an identity
in this field. But I couldn't because G(i,j) wasn't, for fixed i,
a polynomial in j and, for fixed j, wasn't a polynomial in i.
A simplified example would be the function (2i)!/(i+j)!(i-j)!; for
fixed i this function isn't in C(j) (the function field) and for fixed j
this isn't in C(i). But for fixed i-j it *is* in C(j), so I made some linear
substitutions and then got the method to work. At the end of the day
I still had the same nasty plane quartic but now all I had to do was to prove
that for a fixed i it wasn't the zero *polynomial* in j, rather than
to show that it had no zeroes, which was easy.

I feel a whole lot wiser now. Thanks to all who replied,

Kevin

Kevin Buzzard, Feb 17, 2005