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 Cvector space V, which will take the role of a tangent
space momentarily, an alternate multilinear pform 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 pvolume measure, in the sense that it assigns an
(oriented) volume to the paralellepipedic polyhedron determined by the
vectors v_{i}. By a natural convention, 0forms are just constants.
To a pform f and a qform y, one associates a
(p+q)form, i.e., a (p+q)volume measure, by means of the
exterior product fÙy:
(fÙy)(v_{1},...,v_{p+q}) = 

e(s)
f 
( 
v_{s(1)},...,v_{s(p)} 
) 
y 
( 
v_{s(p+1)},...,v_{s(p+q)} 
) 
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 pforms. 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 pform f
and a qform y.
Next, an alternate difference pform, or for short a
difference pform, is a map w which to each element x of
a real manifold M associates a multilinear pform 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 R^{d}:
each w(x) is then an alternate form on V=R^{d}. By
imposing the additional property w(x_{1},...,x_{d})
=w(ëx_{1}û,...,ë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 relation
w(x+v)=w(x)+w'(x)(v)+o(v) as v®0.
Each w'(x) is a linear map from V=R^{d} to the vector space
A_{p}(V), and can be viewed as a multilinear map from V^{p+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)(v_{0},...,v_{p})
= 

(1)^{i} 
( 
w'(x)(v_{i}) 
) 
(v_{0},..., 

,...,v_{p}).

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
w^{D}(x) be the linear map on V defined by
w(x+v)=w(x)+w^{D}(x)(v)+R(v) and R(v) is
zero for each element v=e_{i} of the canonical basis of V=R^{d}.
Again,
(v_{0},...,v_{p})®w^{D}(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 dw
defined by
(d 
w)(x)(v_{0},...,v_{p})
= 

(1)^{i} 
( 
w^{D}(x)(v_{i}) 
) 
(v_{0},..., 

,...,v_{p}).

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 R^{d} that contains M. As in the differential setting,
the exterior difference dn_{i} of the restriction of n_{i} to M
(i.e., or the ith coordinate function on M) plays a special role:
the dn_{i} form a basis for the ring of difference form, and the
d_{ni1}Ù...Ùdn_{ip} for i_{1}<...<i_{p} span
the vector space (respectively, free module) of pforms. Exterior
differential and exterior difference share a formally simple,
easytomemorize formulation on the canonical basis
(dn_{1},...,dn_{d}):
for w=f dn_{i1}Ù...Ùdn_{ir}, we get
dw=dfÙdn_{i1}Ù...Ùdn_{ir}
where the exterior differential is df=å_{i=1}^{d}¶
f/¶x_{i}dn_{i}, and the exterior difference df=å_{i=1}^{d}(D_{i}f)dn_{i}, where D_{i} is the finite
difference operator defined by (D_{i}f)(x_{1},...,x_{d})
=f(x_{1},...,x_{i}+1,...,x_{d})f(x_{1},...,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 dn_{1}Ù...Ùdn_{d} on [ 0,1)^{d} is
just f(0,...,0), as is for i_{1}<...<i_{r} the integral of
f dn_{i1}Ù...Ùdn_{ir} 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 dn_{1}Ù...Ùd 
n_{d}
= 

å 
(n_{1},...,n_{d})ÎZ^{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 2d faces,
¶W=F(x_{1}=0)F(x_{2}=0)+...+(1)^{d+1}F(x_{d}=0)
F(x_{1}=1)+F(x_{2}=1)+...+(1)^{d}F(x_{d}=1),
where F(x_{i}=a) is the (oriented) face
WÇ{ xx_{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}Ù...Ù 

Ù...Ùdn_{d}
(1) 
we get

= 

(1)^{i} 
ó
õ 

f_{i} d 
n_{1}Ù...Ù 

Ù...Ùdn_{d} 


= 
æ
ç
ç
è 

(1)^{i}f_{i}(0,...,1,...,0) 

(1)^{i}f_{i}(0,...,0) 
ö
÷
÷
ø 
dn_{1}Ù...Ùdn_{d} 


= 

(1)^{i}(D_{i}f_{i})(0,...,0) dn_{1}Ù...Ùd 
n_{d}= 
ó
õ 

dw. 

We could have as well considered forms w defined on the integer
lattice Z^{d}, and defined their sums å_{W}w on a
manifold W by the integrals ò_{W}w of the
form w extended to R^{d} by w(x_{1},...,x_{d})
=w(ëx_{1}û,...,ë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 [ZeilbergerStokes formula]
For any difference pform w such that
w(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}dw.
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
å_{¶W}w=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


f_{i}
d 
n_{1}Ù...Ù 

Ù...Ùdn_{d}=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 dn_{1} and dn_{2},
respectively, and consider a closed 1form w=g dn+f dk,
so that D_{n}f=D_{k}g.
2.1 Stripeshaped manifolds
Consider
W=R^{+}×[ 0,n ]={ (x,y)  x³0 and
0£ y£ n } and the closed form w obtained for
f(n,k)= 



and
g(n,k)= 

f(n,k).

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 closedform 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 (r1)form with
hypergeometric coefficients can be viewed as a simultaneous encoding
of r closed form summation identities [4].
2.2 Triangularshaped manifolds
Zeilberger observed that for a closed form w_{1}=g_{1} dn+f_{1} dk, 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+s1,k) provide for
each s>1 with another closed form w_{s}=g_{s} dn+f_{s} dk.
Basing on this, Amdeberhan and Zeilberger [1] derived the
following representations for z(3):
z(3)= 



= 


(1)^{n1}(56n^{2}32n+5) 



= 


(1)^{n}(5265n^{4}+13878n^{3}+13761n^{2}+6120n+1040) 

(4n+3)(4n+1)(3n+2)^{2}(3n+1)^{2}(n+1) 




.

Specifically, they considered
W={ (x,y)  y³ë x+1û } and
the functions
f_{1}(n,k)=(1)^{k} 
k!^{2}(nk1)! 

(n+k+1)! (k+1) 

and
g_{1}(n,k)=2(1)^{k} 
k!^{2}(nk)! 

(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/2}4^{n}),
O(n^{2}27^{n}), O(n^{2}64^{n}), respectivelyat the cost
of more and more operations for each term, though! Changing W
to W_{s}={ (x,y)  y³ së
x+1û } leads to other representations [1],
like, for s=2,
z(3)
= 

(1)^{n}P(n) 

80(5n+4)(5n+3)(5n+2)(5n+1)(4n+3)^{2}(4n+1)^{2}(2n+1)^{2}(n+1) 




where
P=1613824n^{8}+7638016n^{7}+15700096n^{6}+18317312n^{5}+13278552n^{4}+6131676n^{3}+1763967n^{2}+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 w_{s}
on W_{s}, and obtain:


g_{s}(n,0)+ 

f_{s}(sk+s,k)
+ 

( 
g_{s}(sk,k)+...+g_{s}(sk+s1,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 triangularshaped and rectangularshaped 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 dn+f dk 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 wellknown that if a hypergeometric sequences h has a
hypergeometric antidifference H, there has to be some rational
function S such that H=Sh. Here we get g=SD_{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 nonzero 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 righthand 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
nonzero P such that

( 
P+(S_{k}1)Q 
) 
· f=0.
(2) 
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)
dk(
Q· f)
dn,
(3)
whose coefficients all lie in M is closed:
dw= 
( 
(S_{n}1)R· f 
) 
dnÙdk
 
( 
(S_{k}1)Q· f 
) 
dkÙdn
= 
( 
( 
P+(S_{k}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 ((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 rform f dk_{1}Ù...Ùdk_{r}
+å_{i=1}^{r}(P_{i}· f) dnÙdk_{1}Ù...dk_{i}^{^}...Ùdk_{r} is
closed,
i.e.,
(S_{n}1)· f+(S_{k1}1)P_{1}· f+...+(S_{kr}1)P_{r}· f=0,
the rfold summation å_{k1,...,kr}f yields a constant with
respect to n.
4 Extended WZ Cohomology
Is it easily shown that any 1form with coefficients defined
on Z^{r} is exact. Even more is true: any 1form with holonomic
coefficients derives from a holonomic sequence. More specifically, a
1form 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)=(S_{n}1)·f
and
R· f=(S_{k}1)·f.
This always holds if we look for unconstrained f: simply
define f by
f(n,k)= 

(R· 
f)(0,i) 

(Q· f)(j,k). 
The nontrivial 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 1forms 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 nonexact 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 pform w on M to a
pform on N while preserving closedness of forms by simply
requiring
(f^{*}w)(x)(v_{1},...,v_{p})
=w 
( 
f(x) 
) 
( 
f'(x)(v_{1}),...,f'(x)(v_{p}) 
) 
.
(4) 
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 w_{1} 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 f^{D}
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 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_{lj}f^{*}=f^{*}S_{n1}^{a1,j}...
S_{nr}^{an,j}. It then follows from a technical but easy
calculation that D_{lj}f^{*}=f^{*}å_{i}P_{i,j}D_{ni}
for some operators P_{i,j}. Imposing the natural relations
f^{*}(f)=f°f and f^{*}(df)=d(f^{*}f) for
0forms f leads to


f^{*} 
( 
(D_{ni}f) dn_{i} 
) 
= 

( 
D_{lj}(f^{*}f) 
) 
d 
l_{j}
= 

f^{*}(P_{i,j}D_{ni}f) dl_{j}.

Choosing f such that df=(D_{ni}f) dn_{i}, we get
f^{*}(g dn_{i})=å_{j}f^{*}(P_{i,j}g) dl_{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°13,
2000, pp. 115134. 
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. 579607. 
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 L^{A}T_{E}X by
H^{E}V^{E}A.