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:Vp®C that satisfies the rule
f(v1,...,vi+1,vi,...,vp)=-f(v1,...,vp).
This represents a p-volume measure, in the sense that it assigns an (oriented) volume to the paralellepipedic polyhedron determined by the vectors vi. 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:
(fÙy)(v1,...,vp+q) =
 
å
sÎ Sp,q
e(s) f ( vs(1),...,vs(p) ) y ( vs(p+1),...,vs(p+q) )
where Sp,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³0Ap(V) of the vector spaces Ap(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)pqfÙy for a p-form f and 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=TxM. 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,...,xd) =w(ëx1û,...,ëxdû), 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 relation w(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 Ap(V), and can be viewed as a multilinear map from Vp+1 to 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 dw given by
(d w)(x)(v0,...,vp) =
p
å
i=0
(-1)i ( w'(x)(vi) ) (v0,...,
^
v
i
,...,vp).

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. Let wD(x) be the linear map on V defined by w(x+v)=w(x)+wD(x)(v)+R(v) and R(v) is zero for each element v=ei of the canonical basis of V=Rd. Again, (v0,...,vp)|®wD(x)(v0)(v1,...,vp) is alternate in its last p variables only, but the full alternate nature is recovered by the exterior difference dw defined by
(d w)(x)(v0,...,vp) =
p
å
i=0
(-1)i ( wD(x)(vi) ) (v0,...,
^
v
i
,...,vp).
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 (n1,...,nd) the dual basis of the canonical basis of the manifold Rd that contains M. As in the differential setting, the exterior difference dni of the restriction of ni to M (i.e., or the ith coordinate function on M) plays a special role: the dni form a basis for the ring of difference form, and the dni1Ù...Ùdnip for i1<...<ip 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 (dn1,...,dnd): for w=f dni1Ù...Ùdnir, we get
dw=dfÙdni1Ù...Ùdnir
where the exterior differential is df=åi=1d f/xidni, and the exterior difference df=åi=1d(Dif)dni, where Di is the finite difference operator defined by (Dif)(x1,...,xd) =f(x1,...,xi+1,...,xd)-f(x1,...,xd).

In order to make the link between difference forms and summation, we restrict to hypercubic manifolds given by setting some of the coordinates xi 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 dn1Ù...Ùdnd on [ 0,1)d is just f(0,...,0), as is for i1<...<ir the integral of f dni1Ù...Ùdnir on the hypercube defined by 0£xj<1 for each j=ik and xj=0 for all other j. By integration over a union of elementary manifolds, we are naturally led to integral representing sums; for example:
ó
õ
 


Rd
f dn1Ù...Ùd nd =
 
å
(n1,...,nd)ÎZd
f(n1,...,nd).
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 2d faces,
W=F(x1=0)-F(x2=0)+...+(-1)d+1F(xd=0) -F(x1=1)+F(x2=1)+...+(-1)dF(xd=1),
where F(xi=a) is the (oriented) face WÇ{ x|xi=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=
d
å
i=1
fi  d n1Ù...Ù
^
dni
 
Ù...Ùdnd     (1)
we get
ó
õ
 


W
w
=
d
å
i=1
(-1)i ó
õ
 


F(xi=1)-F(xi=0)
fi d n1Ù...Ù
^
dni
 
Ù...Ùdnd
 
= æ
ç
ç
è
d
å
i=1
(-1)ifi(0,...,1,...,0)-
d
å
i=1
(-1)ifi(0,...,0) ö
÷
÷
ø		  dn1Ù...Ùdnd
 
=
d
å
i=1
(-1)i(Difi)(0,...,0) dn1Ù...Ùd nd= ó
õ
 


W
dw.
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,...,xd) =w(ëx1û,...,ëxdû). 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 that w(x1,...,xd) =w(ëx1û,...,ëxdû) on any manifold W that is a linear combination of elementary hypercubic manifolds, we have åWw=åWdw.

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 dw=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 specifically w is given by (1), we obtain
d
å
i=1
 
å
W
fi  d n1Ù...Ù
^
dni
 
Ù...Ùdnd=0,
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 dn and dk for dn1 and dn2, respectively, and consider a closed 1-form w=g dn+f dk, so that Dnf=Dkg.

2.1  Stripe-shaped manifolds

Consider W=R+×[ 0,n ]={ (x,y) | x³0 and 0£ y£ n } and the closed form w obtained for
f(n,k)=
æ
è
m
k
ö
ø
æ
è
n
k
ö
ø
æ
è
p+n+m-k
n+m
ö
ø
  and   g(n,k)=
mk-p(n+1)
(n+m+1)(n+1-k)
f(n,k).
Stokes's theorem on W then yields (after elementary manipulations of binomial sums)
n
å
k=0
æ
è
m
k
ö
ø
æ
è
n
k
ö
ø
æ
è
p+n+m-k
n+m
ö
ø
=
 
å
kÎN
f(n,k)=
 
å
kÎN
f(0,k)+
n
å
l=0
g(l,0) =
æ
è
m+p
m
ö
ø
æ
è
n+p
n
ö
ø
.
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 W to [ 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=g1 dn+f1 dk, the functions fs(n,k)=f1(sn,k) and gs(n,k)=g1(sn,k)+g1(sn+1,k)+...+g1(sn+s-1,k) provide for each s>1 with another closed form ws=gs dn+fs dk. Basing on this, Amdeberhan and Zeilberger [1] derived the following representations for z(3):
z(3)=
5
2
¥
å
n=1
(-1)n-1
æ
è
2n
n
ö
ø
n2
=
1
4
¥
å
n=1
(-1)n-1(56n2-32n+5)
(2n-1)2
æ
è
3n
n
ö
ø
æ
è
2n
n
ö
ø
n3
=
1
72
¥
å
n=0
(-1)n(5265n4+13878n3+13761n2+6120n+1040)
(4n+3)(4n+1)(3n+2)2(3n+1)2(n+1)
æ
è
4n
n
ö
ø
æ
è
3n
n
ö
ø
.
Specifically, they considered W={ (x,y) | y³ë x+1û } and the functions
f1(n,k)=(-1)k
k!2(n-k-1)!
(n+k+1)! (k+1)
  and   g1(n,k)=2(-1)k
k!2(n-k)!
(n+k+1)! (n+1)2
.
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 W to Ws={ (x,y) | y³ së x+1û } leads to other representations [1], like, for s=2,
z(3) =
¥
å
n=0
(-1)nP(n)
80(5n+4)(5n+3)(5n+2)(5n+1)(4n+3)2(4n+1)2(2n+1)2(n+1)
æ
è
5n
n
ö
ø
æ
è
4n
n
ö
ø
where P=1613824n8+7638016n7+15700096n6+18317312n5+13278552n4+6131676n3+1763967n2+289515n+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 ws on Ws, and obtain:
¥
å
n=0
gs(n,0)+
¥
å
k=0
fs(sk+s,k) +
¥
å
k=0
( gs(sk,k)+...+gs(sk+s-1,k) ) =0.
Next, noting that g1(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)
3F2 æ
è
x,y,v+n-1
v,x+y+n
|1 ö
ø		 =
G(x+k)G(y+k)
G(k)G(x+y+k)
3F2 æ
è
x,y,v+k-1
v,x+y+k
|1 ö
ø
and ån+m=s(
2n
n
)(
2m
m
)=4s 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 dn+f dk with hypergeometric coefficients. Since f is hypergeometric in n, one can find some rational function R of (n,k) such that Dkg=Dnf=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=SDnf=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=abfn,k=Fn 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 P0(n,Sn) such that P0· F=0. Proving the identity thus reduces to proving åk=ab(P0· f)(n,k)=0. By restricting to holonomic hypergeometric summands and right-hand sides, Zeilberger's presentation essentially only dealt with the case P0=Sn-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 P0 be a right multiple of Sn-1 and write P0=(Sn-1)R this factorization.

The holonomy of f ensures that there exists a pair (P,Q) with non-zero P such that
( P+(Sk-1)Q ) · f=0.     (2)
Provided that there exists such a pair for P=P0, 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) dk-(Q· f) dn,     (3)
whose coefficients all lie in M is closed:
dw= ( (Sn-1)R· f )  dnÙdk - ( (Sk-1)Q· f )  dkÙdn = ( ( P+(Sk-1)Q ) · f )  dnÙdk=0.

Conversely, assume that there exists a closed form w (with coefficients in M) given by (3). By closedness, we have ((Sn-1)R+(Sk-1)Q)· f=0, whence after summation over k, and provided that R involves neither k nor Sk,
(Sn-1)R·
b
å
k=a
f(n,k)=0.

More generally, if the r-form f dk1Ù...Ùdkr +åi=1r(Pi· f) dnÙdk1Ù...dki^...Ùdkr is closed,
i.e.,   (Sn-1)· f+(Sk1-1)P1· f+...+(Skr-1)Pr· f=0,
the r-fold summation åk1,...,krf 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=df, or more explicitly
-(Q· f)=(Sn-1)·f     and     R· f=(Sk-1)·f.
This always holds if we look for unconstrained f: simply define f by
f(n,k)=
k-1
å
i=0
(R· f)(0,i)-
n-1
å
j=0
(Q· f)(j,k).

The non-trivial problem is to impose fÎM. (For example, when f is hypergeometric, all coefficients of w as well as f have to be rational multiples of f.) Then, not all 1-forms w remain 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
(f*w)(x)(v1,...,vp) =w ( f(x) ) ( f'(x)(v1),...,f'(x)(vp) ) .     (4)

In the difference case, a simple example of a pullback has already been given in Section 2.2: the closed form ws 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 fD for 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 li=åjai,jnj, shifting by 1 with respect to nj after performing the substitution induced by f is equivalent to doing shifts with respect to each li before substituting, as detailed by the formula Sljf*=f*Sn1a1,j... Snran,j. It then follows from a technical but easy calculation that Dljf*=f*åiPi,jDni for some operators Pi,j. Imposing the natural relations f*(f)=f°f and f*(df)=d(f*f) for 0-forms f leads to
 
å
i
f* ( (Dnif) dni ) =
 
å
j
( Dlj(f*f) )  d lj =
 
å
i,j
f*(Pi,jDnif) dlj.
Choosing f such that df=(Dnif) dni, we get f*(g dni)=åjf*(Pi,jg) dlj, 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 by HEVEA.