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?

  • $\begingroup$ By the way, I am also interested in bounds in cases where the domain is restricted to, say, certain kinds of combinatorial sums. $\endgroup$ – Daniel Litt Jun 22 '10 at 16:14

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.

  • $\begingroup$ 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? $\endgroup$ – Daniel Litt Jun 22 '10 at 16:02
  • $\begingroup$ 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. $\endgroup$ – Jacques Carette Jun 22 '10 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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