Zeilberger's algorithm in practice

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

  1. 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

    \begin{lemma} If $j\geq1$ and $i\geq j+1$ are integers

    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,
    and I would appreciate comments from people who know about this sort
    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


    [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
    [fixed width font alert]

    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.


    Kevin Buzzard
    Kevin Buzzard, Feb 14, 2005
    1. Advertisements

  2. [ 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
    your result follows).

    Fred the Wonder Worm, Feb 15, 2005
    1. Advertisements

  3. 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
    sum_a F(a,i,j)=G(i,j). The method I read about in the book "A=B"
    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 Buzzard, Feb 17, 2005
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.