A Tutorial on Closed Difference Forms (original) (raw)

A Tutorial on Closed Difference Forms

Burkhard Zimmermann

RISC, Linz (Austria)

Algorithms Seminar

January 15, 2001

[summary by Fr�d�ric Chyzak]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract

Zeilberger's theory of closed difference forms provides with a deeper understanding of the creative telescoping method used to prove many (_q_-)hypergeometric (multi-)sum identities, and of ``companion'' or ``dual'' identities. By introducing new types of summation domains, the closed form approach allows to discover new identities of the form ``sum equals sum,'' including new summatory representations of z(3). A transform similar to a pullback (change of variables) of differential forms is introduced, and permits to find more new identites. This summary is freely inspired by [1, 2, 4, 5] and the talk.

1 Comparison Between Differential and Difference Calculi

By mimicking differential calculus [2], Zeilberger has developped a complete difference calculus [4]. This theory, which we recal here, culminates with a discrete analogue to Stokes's theorem.

Given a **C**-vector space V, which will take the role of a tangent space momentarily, an alternate multilinear p-form on _V_is just a multilinear map

f:V _p_�**C** that satisfies the rule

f(_v_1,...,v i+1,v i,...,v p)=-f(_v_1,...,v p).

This represents a _p_-volume measure, in the sense that it assigns an (oriented) volume to the paralellepipedic polyhedron determined by the vectors v i. By a natural convention, 0-forms are just constants. To a _p_-form f and a q_-form y, one associates a (p+q)-form, i.e., a (p+q)-volume measure, by means of the_exterior product f�y:

where S p,q denotes the set of permutations of {1,...,p+q} with s(1)<...<s(p) and s(p+1)<...<s(p+q), and where e(s) denotes the signature of the permutation s. Consider the direct sum A(V)=�p_�0_A p(V) of the vector spaces A p(V) of alternate _p_-forms. By extending the exterior product by linearity, we obtain an associative multiplication on A(V), which becomes a graded algebra with the product rule y�f=(-1)_pq_f�y for a _p_-form fand a _q_-form y.

Next, an alternate difference p-form, or for short a difference _p_-form, is a map

w which to each element x of a real manifold M associates a multilinear _p_-form w(x) on the tangent space _V_=T_x_M. Exterior products of difference forms are defined pointwise. At this point, difference forms and differential forms share the same definition. In the following however, we focus to the case when M is a submanifold of Rd: each w(x) is then an alternate form on V_=Rd. By imposing the additional property w(x1,...,x_d) =w(�x1�,...,�x_d_�), we obtain forms that are piecewise constant, as well as their coefficients. (Compare this situation with the theory in the differential setting, where one insists in having _C_� forms and _C_� coefficients.) The possible variations of forms with x is at the origin of the notions of exterior differential and exterior difference introduced below.

In the differential setting, a kind of a derivation is defined on differential forms in the following way. One starts with the usual derivative

w', which satisfies the asymptotic relationw(x+v)=w(x)+w'(x)(v)+o(v) as v_�0. Each w'(x) is a linear map from V_=Rd to the vector space_A p(V), and can be viewed as a multilinear map from V p+1to C that is not alternate, but alternate in its last_p variables only. Making it alternate by an averaging technique, we obtain the exterior differential _d_w given by

In the difference case, we start with another linearization instead of the derivative w' to define the exterior difference of w, namely by secants instead of tangents. LetwD(x) be the linear map on V defined byw(x+v)=w(x)+wD(x)(v)+R(v) and R(v) is zero for each element _v_=e i of the canonical basis of _V_=Rd. Again, (_v_0,...,v p)|�wD(x)(_v_0)(_v_1,...,v p) is alternate in its last p variables only, but the full alternate nature is recovered by the exterior difference _d_wdefined by

As opposed to the classical exterior differential, exterior difference heavily depends on the choice of a basis on V; but like it, it satisfies _d_�_d_=0.

Denote (_n_1,...,n d) the dual basis of the canonical basis of the manifold Rd that contains M. As in the differential setting, the exterior difference d n i of the restriction of n i to M(i.e., or the i_th coordinate function on M) plays a special role: the d n i form a basis for the ring of difference form, and the_d n _i_1

�...�d n i p for _i_1<...<i p span the vector space (respectively, free module) of _p_-forms. Exterior differential and exterior difference share a formally simple, easy-to-memorize formulation on the canonical basis (d _n_1,...,d n d): for w=f d n i_1�...�_d n i r, we get

_d_w=d f_�_d n i_1�...�_d n i r

where the exterior differential is d f_=�_i_=1_d_� f/�x_i d n i, and the exterior difference d f_=�_i_=1_d(D_i_ f)d n i, where D_i_ is the finite difference operator defined by (D_i_ f)(x1,...,x_d_) =f(x1,...,x_i_+1,...,x_d_)-f(x1,...,x_d_).

In order to make the link between difference forms and summation, we restrict to hypercubic manifolds given by setting some of the coordinates

x_i_ to 0 and letting all others vary freely in [ 0,1), and to the manifolds obtained after translating the latter by vectors with integer entries. Note that all those elementary manifolds (in various dimensions) have volume 1, and that we have restricted difference forms to be constant on such sets. As a consequence, the integral of a form_f_ d n_1�...�_d n d on [ 0,1)d is just f(0,...,0), as is for i_1<...<i r the integral of_f d n i_1�...�_d n i r on the hypercube defined by 0�x_j_<1 for each _j_=i k and x_j_=0 for all other j. By integration over a union of elementary manifolds, we are naturally led to integral representing sums; for example:

| | � � | f d n_1�...�_d | n _d_= | f(_n_1,...,n d). | | ------ | -------------------- | --------- | ---------------------- |

We are now ready to derive a difference variant of Stokes's theorem: consider the oriented hypercube W=[ 0,1)d and its boundary �W defined as usual as a formal linear combination of 2_d_ faces,

�W=F(x1=0)-F(x2=0)+...+(-1)d+1_F_(x_d_=0) -F(x1=1)+F(x2=1)+...+(-1)d F(x_d_=1),

where F(x_i_=a) is the (oriented) faceW�{ x|x_i_=a }. Boundaries of other elementary manifolds are obtained by translating �W, keeping the same coefficients. In this way, we can define the integral of a form over a linear combination of manifolds to be the very same linear combination of integrals of the same form over the manifolds. For

| | w= | f i d | n_1�...� | �...�_d n d (1) | | ------ | ----------- | --------- | -------------------- |

we get

We could have as well considered forms w defined on the integer lattice Zd, and defined their sums �Ww on a manifold W by the integrals �Ww of the form w extended to Rd by w(x1,...,x_d_) =w(�x1�,...,�x_d_�). We shall adopt this equivalent viewpoint from the next section on. By linearity with respect to manifolds, we obtain the following discrete variant of Stokes's formula [4].

Theorem 1 [Zeilberger--Stokes formula] For any difference p-form w such thatw(x 1 ,...,x d ) =w(�x 1 �,...,�x d �) on any manifold W that is a linear combination of elementary hypercubic manifolds, we have� �W w=� W d w .

2 Closed Form Identities (Pun Intended!)

An interesting situation is that of a closed (difference) form, which by definition is a difference form w such that _d_w=0. In this case, the sum��Ww=0 for any manifold W on all of which W is defined, owing to Theorem 1 above. If more specificallyw is given by (1), we obtain in other words a relation between a priori infinite sums! Using the leeway available in the choice of W yields several kinds of identities: sum equals constant, sum equals sum, etc. In the following, we detail this situation in the special case _r_=2. Let us denote d n and d k for d _n_1 and d n_2, respectively, and consider a closed 1-form w=g d n+f d k, so that D_n f_=D_k g.

2.1 Stripe-shaped manifolds

ConsiderW=R+�[ 0,n ]={ (x,y) | _x_�0 and 0� _y_� n } and the closed form w obtained for

Stokes's theorem on W then yields (after elementary manipulations of binomial sums)

| | = | f(n,k)= | f(0,k)+ | g(l,0) = | . | | ----- | ------------- | ----------- | ------------ | - |

More generally, many closed-form identities like the one above, where ``closed form'' now means that both the summand and the sum are hypergeometric sequences, correspond to a ``closed form'' that involves the summand as one of its coefficients. Hence Zeilberger's ``pun intended.''

But some magic takes place here: changing

Wto [ 0,k ]�**R**+ and summing with respect to n instead of k, the same method sometimes yields a companion identity. Moreover, the more variables there are, the more amplified this phenomenon is: for r variables and in lucky cases where all summations make sense, a single closed difference (_r_-1)-form with hypergeometric coefficients can be viewed as a simultaneous encoding of r closed form summation identities [4].

2.2 Triangular-shaped manifolds

Zeilberger observed that for a closed form w1=_g_1 d n+_f_1 d k, the functions f s(n,k)=f_1(sn,k) and_g s(n,k)=_g_1(sn,k)+_g_1(sn+1,k)+...+_g_1(sn+_s_-1,k) provide for each _s_>1 with another closed form w_s_=g s d n+f s d k. Basing on this, Amdeberhan and Zeilberger [1] derived the following representations for z(3):

Specifically, they consideredW={ (x,y) | _y_�� x+1� } and the functions

The representations above have respectively been obtained for _s_=1, 2, and 3; their general terms decrease like O(_n_-3/24-n), O(_n_-227-n), O(_n_-264-n), respectively---at the cost of more and more operations for each term, though! Changing Wto W_s_={ (x,y) | _y_� _s_� x+1� } leads to other representations [1], like, for _s_=2,

where_P_=1613824_n_8+7638016_n_7+15700096_n_6+18317312_n_5+13278552_n_4+6131676_n_3+1763967_n_2+289515_n_+20782. The general term is now O(_n_-2(27/3125)-n), with 27/3125�115.74.

To sketch the proof, we apply Stokes's theorem to

w_s_on W_s_, and obtain:

| | g s(n,0)+ | f s(sk+s,k) + | ( | g s(sk,k)+...+g s(sk+_s_-1,k) | ) | =0. | | ------------------ | ----------------------- | - | ---------------------------------------------- | - | ---- |

Next, noting that _g_1(n,0)=2/(n+1)3 and grouping the sums over _k_yields the announced identity.

2.3 Finite triangular-shaped and rectangular-shaped manifolds

Other identities like

| | G(x+n)G(y+n) G(n)G(x+y+n) | 3_F_2 | �� | |1 | �� | = | G(x+k)G(y+k) G(k)G(x+y+k) | 3_F_2 | �� | |1 | �� | | -------------------------------------------- | ----- | -- | --- | -- | -- | ----------------------------------------- | ----- | -- | --- | -- |

and �n+m_=s()()=4_s are based on other choices for W, like a rectangle [ 0,k ]�[ 0,n ] or a ``triangle'' { (x,y) | � _x_�+� _y_�� s } for W [5].

3 Closed Forms with Holonomic Coefficients

Consider a closed form w=g d n+f d k with hypergeometric coefficients. Since f is hypergeometric in n, one can find some rational function R of (n,k) such that D_k_ g_=D_n _f_=Rf. It is also well-known that if a hypergeometric sequences h has a hypergeometric anti-difference H, there has to be some rational function S such that _H_=Sh. Here we get _g_=S_D_n _f_=SRf. This situation extends to more variables, which legitimates Zeilberger's focus to closed forms whose coefficients are all multiples of the same hypergeometric sequence f by polynomials in the variables; he called such forms WZ forms [4]. Here we extend this situation to forms whose coefficients are rational multiples of the same holonomic sequence, and make the link between closed forms and creative telescoping explicit.

Let a summation identity

�_k_=a b f n,_k_=F n be given, where both f and F are holonomic �-finite sequences. In view of verifying it, knowing F allows to compute a non-zero operator_P_0(n,S n) such that _P_0� _F_=0. Proving the identity thus reduces to proving �_k_=a b(_P_0� f)(n,k)=0. By restricting to holonomic hypergeometric summands and right-hand sides, Zeilberger's presentation essentially only dealt with the case_P_0=S n_-1: F can always be assumed to be 1, otherwise we replace_f(n,k) with f(n,k)/F(n). In this spirit, we now require that_P_0 be a right multiple of S _n_-1 and write _P_0=(S _n_-1)R this factorization.

The holonomy of f ensures that there exists a pair (P,Q) with non-zero P such that

Provided that there exists such a pair for _P_=_P_0, the operator _Q_can be computed by Chyzak's �-finite extension of Gosper's algorithm [3]. Let A be the algebra of difference operators with respect to n and k with coefficients that are rational functions in n and k, and introduce the module _M_=_A_� f. The form

w=(_R_� f) d _k_-(_Q_� f) d n, (3)

whose coefficients all lie in M is closed:

Conversely, assume that there exists a closed form w (with coefficients in M) given by (3). By closedness, we have ((S _n_-1)R+(S _k_-1)Q)� _f_=0, whence after summation over k, and provided that R involves neither _k_nor S k,
More generally, if the r_-form f d k_1�...�_d k r+�_i_=1_r(P _i_� f) d n_�_d _k_1�...d k i_^...�_d k r is closed,

i.e., (S _n_-1)� f+(S _k_1-1)_P_1� f+...+(S k _r_-1)P _r_� _f_=0,

the _r_-fold summation �_k_1,...,k r f yields a constant with respect to n.

4 Extended WZ Cohomology

Is it easily shown that any 1-form with coefficients defined on Zr is exact. Even more is true: any 1-form with holonomic coefficients derives from a holonomic sequence. More specifically, a 1-form w given by (3) is exact if and only if there exists a function f(n,k) such that w=_d_f, or more explicitly

-(_Q_� f)=(S _n_-1)�f and _R_� _f_=(S _k_-1)�f.

This always holds if we look for unconstrained f: simply define f by

The non-trivial problem is to impose f�M. (For example, when_f_ is hypergeometric, all coefficients of w as well as fhave to be rational multiples of f.) Then, not all 1-forms wremain exact. Vieweing closed forms modulo exact forms we are led to a cohomology that Zeilberger named _WZ cohomology_in [4] in the case of hypergeometric f, and that we call extended WZ cohomology in the more general case of holonomic �-finite f. Following Zeilberger [4], we suggest the following extended research problem: characterize those holonomic �-finite sequences f for which there exists a non-exact closed form with coefficients in _M_=_A_� f and compute the corresponding cohomology.

5 Pullbacks

In the differential case, the notion of pullback propagates a change of variables in functions to the level of differential forms, thus permitting change of variables in integrals: for a differentiable map f from a manifold N to another manifold M, one gets a mapping f* that transforms a _p_-form w on M to a_p_-form on N while preserving closedness of forms by simply requiring

In the difference case, a simple example of a pullback has already been given in Section 2.2: the closed form w_s_ is the pullback of the closed form w1 under the map given by f(n,k)=(sn,k). However, no simple definition of a pullback seems possible: the obvious guess that mimicks (4), substituting fDfor f', unfortunately does not preserve closedness (taking finite differences is not a local operation). Zimmermann [5] and Gessel independently gave a definition for the case of a linear mapping f that maps integer points to integer points.

The key observation is that for a linear transform _l_=

f(n), defined by l i_=�_j a i,j n j, shifting by 1 with respect to n _j_after performing the substitution induced by f is equivalent to doing shifts with respect to each l i before substituting, as detailed by the formula S l _j_f*=f*S n_1_a_1,j...S n r a n,j. It then follows from a technical but easy calculation that D_l j_f*=f*�_i P i,j_D_n _i_for some operators P i,j. Imposing the natural relationsf*(f)=_f_�f and f*(d f)=d(f*f) for 0-forms f leads to

| | f* | ( | (D_n_ i f) d n i | ) | = | ( | D_l_ j(f*f) | ) | d | l _j_= | f*(P i,j_D_n i f) d l j. | | ------ | - | -------------------------- | - | -- | - | ---------------- | - | --- | --------- | ----------------------------------------- |

Choosing f such that d f_=(D_n i f) d n i, we getf*(g d n i)=�_j_f*(P i,j g) d l j, a definition that proves to preserve closedness.

References

[1]

Amdeberhan (Tewodros) and Zeilberger (Doron). -- Hypergeometric series acceleration via the WZ method. Electronic Journal of Combinatorics, vol. 4, n°2, 1997, p. Research Paper 3. 4 pages. -- The Wilf Festschrift (Philadelphia, PA, 1996).

[2]

Cartan (Henri). --Cours de calcul diff�rentiel. -- Hermann, Paris, 1977, Collection M�thodes.

[3]

Chyzak (Fr�d�ric). -- An extension of Zeilberger's fast algorithm to general holonomic functions. Discrete Mathematics, vol. 217, n°1-3, 2000, pp. 115--134. -- Formal power series and algebraic combinatorics (Vienna, 1997).

[4]

Zeilberger (Doron). -- Closed form (pun intended!). In A tribute to Emil Grosswald: number theory and related analysis, pp. 579--607. -- American Mathematical Society, Providence, RI, 1993.

[5]

Zimmermann (Burkhard). --Difference forms and hypergeometric summation. -- Master's thesis, Universit�t Wien, Vienna, Austria, February 2000.

This document was translated from LATEX byHEVEA.