Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In the book "A = B" by Petkovesk, Wilf, and Zeilberger, (downloadable here), the authors provide several algorithmic methods for finding closed forms or recurrences for sums involving e.g. binomial coefficients. Even more exciting, their methods provide seemingly short certificates for the truth of these computer-verified claims. In particular, the WZ method prints a single rational function as such a certificate.

In more detail, here is the broad outline of the WZ method, where I directly quote from page 25 of "A = B":

  1. Suppose that you wish to prove an identity of the form $\sum_k t(n, k) = rhs(n)$, and let’s assume, for now, that for each n it is true that the summand $t(n, k)$ vanishes for all $k$ outside of some finite interval.
  2. Divide through by the right hand side, so the identity that you wish to prove now reads as $\sum_k F (n, k) = 1$, where $F (n, k) = t(n, k)/rhs(n)$.
  3. Let $R(n, k)$ be the rational function that the WZ method provides as the proof of your identity (this is described in Chapter 7 of "A=B"). Define a new function $G(n, k) = R(n, k)F (n, k).$
  4. You will now observe that the equation $$F (n + 1, k) − F (n, k) = G(n, k + 1) − G(n, k)$$ is true. Sum that equation over all integers $k$, and note that the right side telescopes to 0. The result is that $$\sum_k F (n + 1, k) = \sum_k F (n, k),$$ hence we have shown that $\sum_k F (n, k)$ is independent of $n$, i.e., is constant.
  5. Verify that the constant is $1$ by checking that $F (0, k) = 1$.

What I want to know is:

Are there known bounds on the length of these certificates $R(n, k)$, in terms of the length of the description of the combinatorial sum in question? If so, what are they?

share|improve this question
    
By the way, I am also interested in bounds in cases where the domain is restricted to, say, certain kinds of combinatorial sums. –  Daniel Litt Jun 22 '10 at 16:14
add comment

1 Answer

up vote 6 down vote accepted

Already for the case of Gosper summation (single-variable), it is known that things can get exponentially larger than the input, because the 'answer' fundamentally depends on the dispersion of the input term. You will find much more comprehensive answers in the papers of Sergei Abramov as well as those of Marko Petkovsek (especially so in their joint papers!)

The disperson of a polynomial $p(x)$ is the largest integer $n$ such that $p(x)$ and $p(x+n)$ have a non-trivial gcd. A good understanding of how dispersion enters the picture can be gotten from the paper Shiftless decomposition and polynomial-time rational summation.

share|improve this answer
    
Well, the paper you reference gives exponential-size certificates upon division---this is not unexpected. My question is really whether there are more compact representations. The "Shiftless decomposition..." paper seems to be a step in this direction. By the way, I am having trouble finding comments on my question in Abramov/Petkovesk; do you have a reference to a specific paper? –  Daniel Litt Jun 22 '10 at 16:02
    
Sorry, I don't really have a specific reference. This is the sort of 'folk knowledge' that the experts know (and onlookers like me learn) but is hard to find in print. You have to dig it out. And it really is because of the dispersion that things get large, it is not due to an artifact of the division. –  Jacques Carette Jun 22 '10 at 16:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.