The Polynomial Growth of an Operator Ideal
==========================================
(Joint work with Frederic Chyzak and Bruno Salvy)


Algorithms for holonomic systems were long believed to be restricted to
holonomic systems. But they are not. It turns out that they admit
natural generalizations to certain classes of non-holonomic systems.

Phrased in the notion of operator algebras, a system of
differential-difference equations corresponds to an ideal of
annihilating operators. The system is called holonomic if the
corresponding ideal has dimension zero. A function is called holonomic
if it is the solution of a holonomic system. The main structural
property of the class of holonomic functions is that adding,
multiplying, stretching, shrinking, evaluating, differentiating,
integrating, and summing holonomic functions gives back a holonomic
function as result. The proofs of these "closure properties" directly
imply algorithms for finding annihilating operators of sums, products,
etc. of holonomic functions given holonomic systems of the operands.

In a contribution to ISSAC'09, we pointed out that most of this extends
directly from zero-dimensional ideals to ideals of any dimension $d$.
For example, it can be shown that if two functions $f_1$ and $f_2$ are
annihilated by operator ideals of dimensions $d_1$ and $d_2$, then
$f_1+f_2$ will be annihilated by an ideal of dimension at most
$\max(d_1,d_2)$ and $f_1\times f_2$ will be annihilated by an ideal of
dimension at most $d_1+d_2$. Bases for annihilating ideals of $f_1+f_2$
or $f_1\times f_2$ can be computed from annihilating ideals for $f_1$
and $f_2$ very much as in the holonomic (i.e., zero-dimensional) case.

Somewhat trickier than the other closure properties is only the case of
definite summation. Here, in addition to the ideal dimension, another
mysterious parameter enters the bound for the dimension of the sum's
annihilating ideal. We call it the polynomial growth. The polynomial
growth is meant to unify peculiarities which already arise in the
zero-dimensional case (holonomic versus d-finite functions) and even for
classical hypergeometric summation (proper versus improper terms), but
unfortunately it does not yet resolve these issues to our full satisfaction.

In the talk, after giving a brief overview of the classical holonomic
systems methodology and a summary of the results of our ISSAC'09 paper,
we will report on the current state of struggle concerning possible
definitions, desired properties, and effective computation of the
polynomial growth of a given operator ideal.