vertex is $1$, these cycles must be disjoint, i.e., $V(C_{i})\cap
V(C_{j})=\emptyset$ and $A(C_{i})\cap A(C_{j})=\emptyset$, for any $i\neq j$.
Denote the set of vertices in the cycles as

$V_{c}=\bigcup_{k=1}^{K}V(C_{1})\cup\dots\cup V(C_{K}).$ (30)

Let $u_{1},\dots,u_{M}$ be the vertices of $C_{1},\dots,C_{m}$ with indegree
at least $2$.

Based on Observation 2, starting from any vertex outside $V_{c}$ there is a
unique path that reaches $V_{c}$. Combining all vertices that reach the cycles
at $u_{m}$ (denoted as $V_{m}$), and the paths from these vertices to $u_{m}$,
we obtain a directed subgraph $T_{m}$, which is connected with $V_{c}$ only
via the vertex $u_{m}$. The subgraphs $T_{m}$’s are disjoint from each other
since they are connected with $V_{c}$ via different vertices. In addition,
each vertex outside of $V_{c}$ lies in exactly one of the subgraph $T_{m}$.
Thus, we can partition the whole graph into the union of the cycles
$C_{1},\dots,C_{K}$ and the subgraphs $T_{1},\dots,T_{M}$.

We then show $T_{m}$’s are trees. For any vertex $v_{0}$ in the subgraph
$T_{m}$, consider the walk $W(v_{0}).$ Any path starting from $v_{0}$ must be
part of $W(v_{0})$. Starting from $v_{0}$ there is only one path from $v_{0}$
to $u_{m}$ which is $W_{1}(v_{0})$, according to Observation 2. Therefore, by
the definition of a directed tree, $T_{m}$ is a directed tree with the root
$u_{m}$. Therefore, we can partition the whole graph into the union of the
cycles $C_{1},\dots,C_{K}$ and subtrees $T_{1},\dots,T_{M}$ with disjoint edge
sets; in addition, the edge sets of the cycles are disjoint, and the root of
$T_{l}$ must be in certain cycle $C_{k}$. It is easy to verify the properties
stated in Lemma 1. This finishes the proof.

####  J.2.2 Proof of Claim J.1

We first prove the case for $d\geq 2$. Suppose the corresponding graph for $Y$
is $G$, and $G$ is decomposed into the union of cycles $C_{1},\dots,C_{K}$ and
trees $T_{1},\dots,T_{m}$. We perform the following operation: pick an
arbitrary tree $T_{m}$ with the root $u_{m}$. The tree is non-empty, thus
there must be an edge $e$ with the head $u_{m}$.

Suppose $v$ is the tail of the edge $e$. Now we remove the edge $e=(v,u_{m})$
and create a new edge $e^{\prime}=(v,v)$. The new edge corresponds to
$y_{v}=x_{v}$. The old edge $(v,u_{m})$ corresponds to $y_{v}=x_{u_{m}}$ (and
a term $h(f(x_{u_{m}})-f(x_{v}))$) if $u_{m}\leq n$ or
$y_{v}=y_{u_{m}-n}\notin\\{x_{1},\dots,x_{n}\\}$ (and a term
$h(f(y_{u_{m}-n})-f(x_{v}))$) if $u_{m}>n$. This change corresponds to the
change of $y_{v}$: we change $y_{v}=x_{u_{m}}$ (if $u_{m}\leq n$) or
$y_{v}=y_{u_{m}-n}$ (if $u_{m}>n$) to $\hat{y}_{v}=x_{v}$. Let
$\hat{y}_{i}=y_{i}$ for any $i\neq v$, and
$\hat{Y}=(\hat{y}_{1},\dots,\hat{y}_{n})$ is the new point.

Previously $v$ is in a tree $T_{m}$ (not its root), now $v$ is the root of a
new tree, and also part of the new cycle (self-loop)
$C_{K+1}=(v,e^{\prime},v)$. In this new graph, the number of vertices in
cycles increases by $1$, thus the value of $g$ increases by $-\frac{1}{n}\log
2$, i.e., $g(\hat{Y})-g(Y)=\frac{1}{n}\log 2$.

Since $d\geq 2$, we can find a path in $\mathbb{R}^{d}$ from a point to
another point without passing any of the points in $\\{x_{1},\dots,x_{n}\\}$.
In the continuous process of moving $y_{v}$ to $\hat{y}_{v}$, the function
value will not change except at the end that $y_{v}=x_{v}$. Thus there is a
non-increasing path from $Y$ to $\hat{Y}$, in the sense that along this path
the function value of $g$ does not decrease.

The illustration of this proof is given below.

(a) Original graph

(b) Modified graph, with improved function value

Figure 26:  Illustration of the proof of Claim J.1. For the figure on the
left, we pick an arbitrary tree with the head being vertex $9$, which
corresponds to $y_{6}=y_{7}$. We change $y_{7}$ to $\hat{y}_{7}=x_{7}$ to
obtain the figure on the right. Since one more cycle is created, the function
value increases by $-\frac{1}{n}\log 2.$

For the case $d=1$, the above proof does not work. The reason is that the path
from $y_{v}$ to $\hat{y}_{v}$ may touch other points in
$\\{x_{1},\dots,x_{n}\\}$ and thus may change the value of $g$. We only need
to make a small modification: we move $y_{v}$ in $\mathbb{R}$ until it touches
a certain $x_{i}$ that corresponds to a vertex in the tree $T_{m}$, at which
point a cycle is created, and the function value increases by at least
$\frac{1}{n}\log 2$. This path is a non-decreasing path, thus the claim is
also proved.

###  J.3 Proof of Theorem 2

Obviously, $g(Y)\triangleq\phi_{\rm R}(Y,X)=\frac{1}{n}\sup_{f\in
C(\mathbb{R}^{d})}\sum_{i=1}^{n}[h(f(x_{i})-f(y_{i}))]\geq h(0)$ (by picking
$f=0$).

Step 1: achieving optimal $g(Y)$. We prove if
$\\{y_{1},\dots,y_{n}\\}=\\{x_{1},\dots,x_{n}\\}$, then $g(Y)=h(0)$.

######  Claim J.2.

Assume $h$ is concave. Then the function $\xi_{\rm
R}(m)=\sup_{(t_{1},\dots,t_{k})\in ZO(m)}\sum_{i=1}^{m}h(t_{i})$ satisfies
$\xi_{\rm R}(m)=mh(0)$, where the set
$ZO(m)=\\{t_{1},t_{2},\dots,t_{m}\in\mathbb{R}:\sum_{i=1}^{m}t_{i}=0\\}$.

The proof of this claim is obvious and skipped here. When
$\\{y_{1},\dots,y_{n}\\}=\\{x_{1},\dots,x_{n}\\}$, we can divide $[n]$ into
multiple cycles $C_{1}\cup\dots\cup C_{K}$, each with length $m_{k}$, and
obtain $\phi_{\rm R}(Y,X)=\frac{1}{n}\sup_{f\in
C(\mathbb{R}^{d})}\sum_{k=1}^{K}\sum_{i=1}^{m_{k}}[h(f(x_{i})-f(y_{i}))]=\frac{1}{n}\sum_{k=1}^{K}\xi{\rm
R}(m_{k})=\frac{1}{n}\sum_{k=1}^{K}m_{k}h(0)=h(0).$

Step 2: compute $g(Y)$ when $y_{i}\in\\{x_{1},\dots,x_{n}\\},\forall i.$
Assume $y_{i}\in\\{x_{1},\dots,x_{n}\\},\forall i.$ We build a directed graph
$G=(V,A)$ as follows (the same graph as in Appendix J.2). The set of vertices
$V=\\{1,2,\dots,n\\}$ represents $x_{1},x_{2},\dots,x_{n}$. We draw a directed
edge $(i,j)\in A$ if $y_{i}=x_{j}$. Note that it is possible to have a self-
loop $(i,i)$, which corresponds to the case $y_{i}=x_{i}$.

According to Lemma 1, this graph can be decomposed into cycles
$C_{1},C_{2},\dots,C_{K}$ and subtrees $T_{1},T_{2},\dots,T_{M}$. We claim
that

$\phi_{\rm R}(Y,X)=\frac{1}{n}\sum_{k=1}^{K}|V(C_{k})|h(0)\geq h(0).$ (31)

The proof of the relation in Eq. (31) is similar to the proof of Eq. (22) used
in the proof of Theorem 2, and briefly explained below. One major part of the
proof is to show that the contribution of the nodes in the cycles is
$\sum_{k=1}^{K}|V(C_{k})|h(0)$. This is similar to Step 1, and is based on
Claim J.2. Another major part of the proof is to show that the contribution of
the nodes in the subtrees is zero, similar to the proof of Eq. (28). This is
because we can utilize Assumption 4.4 to construct a sequence of $f$ values
(similar to Eq. (26)) so that

$f(y_{i})-f(x_{i})=\begin{cases}0,&i\in\bigcup_{k=1}^{K}V(C_{k}),\\\
\alpha_{N},&i\in\bigcup_{m=1}^{M}V(T_{m}).\end{cases}$ (32)

Here $\\{\alpha_{N}\\}_{N=1}^{\infty}$ is a sequence of real numbers so that
$\lim_{N\rightarrow\infty}h(\alpha_{N})=\sup_{t}h(t)=0$. In the case that
$h(\infty)=0$ like RS-GAN, we pick $\alpha_{N}=N$. In the case that $h(a)=0$
for a certain finite number $a$, we can just pick $\alpha_{N}=a,\forall N$
(thus we do not need a sequence but just one choice).

Since the expression of $\phi_{\rm R}(Y,X)$ in Eq. (31) is a scaled version of
the expression of $\phi_{\rm RS}(Y,X)$ (scale by $-\frac{\log 2}{h(0)}$), the
rest of the proof is the same as the proof of Theorem 2.

Step 3: function value for general $Y$ and GMR. This step is the same as the
proof of Theorem J.1. For the value of general $Y$, we build an “augmented
graph” and apply the result in Step 2 to obtain $g(Y)$. To prove GMR, the same
construction as the proof of Theorem J.1 suffices.

##  Appendix K Results in Parameter Space

We will first state the technical assumptions and then present the formal
results in parameter space. The results become somewhat technical due to the
complication of neural-nets. Suppose the discriminator neural net is
$f_{\theta}$ where $\theta\in\mathbb{R}^{J}$ and the generator net is $G_{w}$
where $w\subset\mathbb{R}^{K}.$

######  Assumption K.1.

(representation power of discriminator net): For any distinct vectors
$v_{1},\dots,v_{2n}\in\mathbb{R}^{d}$ , any $b_{1},\dots,b_{2n}\in\mathbb{R}$,
there exists $\theta\in\mathbb{R}^{J}$ such that
$f_{\theta}(v_{i})=b_{i},~{}i=1,\dots,2n.$

######  Assumption K.2.

(representation power of generator net in $\mathcal{W}$) For any distinct
$z_{1},\dots,z_{n}\in\mathbb{R}^{d_{z}}$ and any
$y_{1},\dots,y_{n}\in\mathbb{R}^{d}$, there exists $w\in\mathcal{W}$ such that
$G_{w}(z_{i})=y_{i},i=1,\dots,n$.

For any given $Z=(z_{1},\dots,z_{n})\in\mathbb{R}^{d_{z}\times n}$, and any
$\in\mathcal{W}\subseteq\mathbb{R}^{K}$, we define a set $G^{-1}(Y;Z)$ as
follows: $w\in G^{-1}(Y;Z)$ iff $G_{w}(Z)=Y$ and $w\in\mathcal{W}$.

######  Assumption K.3.

(path-keeping property of generator net; duplication of Assumption 4.6): For
any distinct $z_{1},\dots,z_{n}\in\mathbb{R}^{d_{z}}$, the following holds:
for any continuous path $Y(t),t\in[0,1]$ in the space $\mathbb{R}^{d\times n}$
and any $w_{0}\in G^{-1}(Y(0);Z)$, there is continuous path $w(t),t\in[0,1]$
such that $w(0)=w_{0}$ and $Y(t)=G_{w(t)}(Z),t\in[0,1]$.

We will present sufficient conditions for these assumptions later. Next we
present two main results on the landscape of GANs in the parameter space.

######  Proposition K.1.

(formal version of Proposition 1) Consider the separable-GAN problem
$\min_{w\in\mathbb{R}^{K}}\varphi_{\rm sep}(w),$ where $\varphi_{\rm
sep}(w)=\sup_{\theta}\frac{1}{2n}\sum_{i=1}^{n}[h_{1}(f_{\theta}(x_{i}))+h_{2}(-f_{\theta}(G_{w}(z_{i})))]$
Suppose $h_{1},h_{2}$ satisfy the same assumptions of Theorem 1. Suppose
$G_{w}$ satisfies Assumption K.2 and Assumption 4.6 (with certain
$\mathcal{W}$). Suppose $f_{\theta}$ satisfies Assumption K.1. Then there
exist at least $(n^{n}-n!)$ distinct $w\in\mathcal{W}$ that are not global-
min-reachable.

######  Proposition K.2.

(formal version of Prop. 2) Consider the RpGAN problem
$\min_{w\in\mathbb{R}^{K}}\varphi_{\rm R}(w),$ where $\varphi_{\rm
R}(w)=\sup_{\theta}\frac{1}{n}\sum_{i=1}^{n}[h(f_{\theta}(x_{i}))-f_{\theta}(G_{w}(z_{i}))].$
Suppose $h$ satisfies the same assumptions of Theorem 2. Suppose $G_{w}$
satisfies Assumption K.2 and Assumption 4.6 (with certain $\mathcal{W}$).
Suppose $f_{\theta}$ satisfies Assumption K.1. Then any $w\in\mathcal{W}$ is
global-min-reachable for $\varphi_{\rm R}(w)$.

We have presented two generic results that relies on a few properties of the
neural-nets. These properties can be satisfied by certain neural-nets, as
discussed next. Our results largely rely on recent advanced in neural-net
optimization theory.

###  K.1 Sufficient Conditions for the Assumptions

In this part, we present a set of conditions on neural nets that ensure the
assumptions to hold. We will discuss more conditions in the next subsection.

######  Assumption K.4.

(mildly wide) The last hidden layer has at least $\bar{n}$ neurons, where
$\bar{n}$ is the number of input vectors.

The assumption of width is common in recent theoretical works in neural net
optimization (e.g. [50, 73, 2]). For the generator network, we set
$\bar{n}=n$; for the discriminator network, we set $\bar{n}=2n.$

######  Assumption K.5.

(smooth enough activation) The activation function $\sigma$ is an analytic
function, and the $k$-th order derivatives $\sigma^{(k)}(0)$ are non-zero, for
$k=0,1,2,\dots,\bar{n},$ where $\bar{n}$ is the number of input vectors.

The assumption of the neuron activation is satisfied by sigmoid, tanh,
SoftPlus, swish, etc.

For the generator network, consider a fully neural network
$G_{w}(z)=W_{H}\sigma(W_{H-1}\dots W_{2}\sigma(W_{1}z))$ that maps
$z\in\mathbb{R}^{d_{z}}$ to $G_{w}(z)\in\mathbb{R}^{d}$. Define
$T_{k}(z)=\sigma(W_{k-1}\dots W_{2}\sigma(W_{1}z))\in\mathbb{R}^{d_{k}}$ where
$d_{k}$ is the number of neurons in the $k$-th hidden layer. Then we can write
$G_{w}(z)=W_{H}T_{H}(z)$, where $W_{H}\in\mathbb{R}^{d\times d_{H}}$. Let
$Z=(z_{1},\dots,z_{n})$ and let
$T_{k}(Z)=(T_{k}(z_{1}),\dots,T_{k}(z_{n}))\in\mathbb{R}^{d_{k}\times n},$
$k=1,2,\dots,H.$ Define $\mathcal{W}=\\{w=(W_{1},\dots,W_{H}):T_{H}(Z)\text{is
full rank}\\}$.

We will prove that under these two assumptions on the neural nets, the
landscape of RpGAN is better than that of SepGAN.

######  Proposition K.3.

Suppose $h_{1},h_{2},h$ sastify assumptions in Theorem 1 and Theorem 2.
Suppose $G_{w},f_{\theta}$ satisfies Assump. K.5 and K.4 ($\bar{n}=n$ for
$G_{w}$, and $\bar{n}=2n$ for $f_{\theta}$). Then there exist at least
$(n^{n}-n!)$ distinct $w\in\mathcal{W}$ that are not GMR for $\varphi_{\rm
Sep}(w)$. In contrast, any $w\in\mathcal{W}$ is global-min-reachable for
$\varphi_{\rm R}(w)$.

This proposition is the corollary of Prop. K.1 and Prop. K.2; we only need to
verify the assumptions in the two propositions. The following series of claims
provide such verification.

######  Claim K.1.

Suppose Assumptions K.4 and K.5 hold for the generator net $G_{w}$ with
distinct input $z_{1},\dots,z_{n}$. Then
$\mathcal{W}=\\{(W_{1},\dots,W_{H}):T_{H}(Z)\text{ is full rank}\\}$ is a
dense set in $\mathbb{R}^{K}$. In addition, Assumption K.2 holds.

This full-rank condition was used in a few works of neural-net landscape
analysis (e.g. [72]). In GAN area, [7] studied invertible generator nets
$G_{w}$ where the weights are restricted to a subset of $\mathbb{R}^{K}$ to
avoid singularities. As the set $\mathcal{W}$ is dense, intuitively the
iterates will stay in this set for most of the time. However, rigorously
proving that the iterates stay in this set is not easy, and is one of the
major challenges of current neural-network analysis. For instance, [38]) shows
that for very wide neural networks with proper initialization along the
training trajectory of gradient descent the neural-tangent kernel (a matrix
related to $T_{H}(Z)$) is full rank. A similar analysis can prove that the
matrix $T_{H}(Z)$ stays full rank during training under similar conditions. We
do not attempt to develop the more complicated convergence analysis for
general neural-nets here and leave it to future work.

######  Claim K.2.

Suppose Assumptions K.4 and K.5 hold for the generator net $G_{w}$ with
distinct input $z_{1},\dots,z_{n}$. Then it satisfies Assumption 4.6 with
$\mathcal{W}$ defined in Claim K.1.

Assumption K.1 can be shown to hold under a similar condition to that in Claim
K.1.

######  Claim K.3.

Consider a fully connected neural network
$f_{\theta}(z)=\theta_{H}\sigma(\theta_{H-1}\dots\theta_{2}\sigma(\theta_{1}z))$
that maps $u\in\mathbb{R}^{d}$ to $f_{\theta}(u)\in\mathbb{R}$ and suppose
Assumptions K.4 and K.5 hold. Then Assumption K.1 holds.

The proofs of the claims are given in Appendix K.5.

With these claims, we can immediately prove Prop. K.3.

Proof of Prop. K.3: According to Claim K.2, K.1, K.3, the assumptions of Prop.
K.3 imply the assumptions of Prop. K.1 and Prop. K.2. Therefore, the
conclusions of Prop. K.1 and Prop. K.2 hold. Since the conclusion of Prop. K.3
is the combination of the the conclusions of Prop. K.1 and Prop. K.2, it also
holds. $\Box$

###  K.2 Other Sufficient Conditions

Assumption K.3 (path-keeping property) is the key assumption. Various results
in neural-net theory can ensure this assumption (or its variant) holds, and we
have utilized one of the simplest such results in the last subsection. We
recommend to check [80] which describes a bigger picture about various
landscape results. In this subsection, we briefly discuss other possible
results applicable to GAN.

We start with a strong conjecture about neural net landscape, which only
requires a wide final hidden layer but no condition on the depth and
activation.

######  Conjecture K.1.

Suppose $g_{\theta}$ is a fully connected neural net with any depth and any
continuous activation, and it satisfies Assumption K.4 (i.e. a mildly wide
final hidden layer). Assume $\ell(y,\hat{y})$ is convex in $\hat{y}$, then the
empirical loss function of a supervised learning problem
$\sum_{i=1}^{n}\ell(y_{i},g_{\theta}(x_{i}))$ is global-min-reachable for any
point.

We then describe a related conjecture for GAN, which is easy to prove if
Conjecture K.1 holds.

Conjecture 1 (informal): Suppose $G_{w}$ is a fully connected net satisfying
Assump. K.4 (i.e. a mildly wide final hidden layer). Suppose $G_{w}$ and
$f_{\theta}$ are expressive enough (i.e. Assump. K.2 and Assump. K.1 hold).
Then the RpGAN loss has a benign landscape, in the sense that any point is GMR
for $\varphi_{\rm R}(w)$. In contrast, the SepGAN loss does not have this
property.

Unfortunately, we are not aware of any existing work that has proved
Conjecture K.1, thus we are not able to prove Conjecture 1 above for now.
Venturi et al. [84] proved a special case of Conjecture K.1 for $L=1$ (one
hidden layer), and other works such as Li et al. [50] prove a weaker version
of Conjecture K.1; see [80] for other related results. The precise version of
Conjecture K.1 seems non-trivial to prove.

We list two results on GAN that can be derived from weaker versions of
Conjecture K.1; both results apply to the whole space instead of the dense
subset $\mathcal{W}$.

Result 1 (1-hidden-layer): Suppose $G_{w}$ is 1-hidden-layer network with any
continuous activation. Suppose it satisfies Assump. K.4 (i.e. a mildly wide
final hidden layer). Suppose $G_{w}$ and $f_{\theta}$ are expressive enough
(i.e. Assump. K.2 and Assump. K.1 hold). Then the RpGAN loss satisfies GMR for
any point. This result is based on Venturi et al. [84].

Result 2: Suppose $G_{w}$ is a fully connected network with any continuous
activation and any number of layers. Suppose it satisfies Assump. K.4 (i.e. a
mildly wide final hidden layer). Suppose $G_{w}$ and $f_{\theta}$ are
expressive enough (i.e. Assump. K.2 and K.1 hold). Then the RpGAN loss has no
sub-optimal set-wise local minima (see [50, Def. 1] for the definition). This
result is based on Li et al. [50].

Due to space constraint, we do not present the proofs of the above two results
(combining them with GANs is somewhat cumbersome). The high-level proof
framework is similar to that of Prop. K.3.

###  K.3 Proofs of Propositions for Parameter Space

Proof of Proposition K.1. The basic idea is to build a relation between the
points in the parameter space to the points in the function space.

Denote $\mathcal{L}_{\rm
sep}(w;\theta)=\frac{1}{2n}\sum_{i=1}^{n}[h_{1}(f_{\theta}(x_{i}))+h_{2}(-f_{\theta}(G_{w}(z_{i})))]$,
then $\varphi_{\rm sep}(w)=\sup_{\theta}\mathcal{L}_{\rm sep}(w;\theta).$
Denote $L_{\rm
sep}(Y;f)=\frac{1}{2n}\sum_{i=1}^{n}[h_{1}(f(x_{i}))+h_{2}(-f(y_{i}))]$, and
$\phi(Y,X)=\sup_{f}L_{\rm sep}(Y;f).$ Note that in the definition of the two
functions above, the discriminator is hidden in the $\sup$ operators, thus we
have freedom to pick the discriminator values (unlike the generator space
which we have to check all $w$ in the inverse of $Y$).

Our goal is to analyze the landscape of $\varphi_{\rm sep}(w)$, based on the
previously proved result on the landscape of $\phi(Y,X)$. We first show that
the image of $\varphi_{\rm sep}(\hat{w})$ is the same as that of $\phi_{\rm
sep}(\hat{Y},X)$.

Define $G^{-1}(Y)\triangleq\\{w:G_{w}(z_{i})=y_{i},i=1,\dots,n\\}.$ We first
prove that

$\phi_{\rm sep}(\hat{Y},X)=\varphi_{\rm sep}(\hat{w}),~{}\forall~{}\hat{w}\in
G^{-1}(\hat{Y}).$ (33)

Suppose $\phi_{\rm sep}(\hat{Y},X)=\alpha$. This implies that $L_{\rm
sep}(\hat{Y};f)\leq\alpha$ for any $f$; in addition, for any $\epsilon>0$
there exists $\hat{f}\in C(\mathbb{R}^{d})$ such that

$L_{\rm sep}(\hat{Y};\hat{f})\geq\alpha-\epsilon.$ (34)

According to Assumption K.1, there exists $\theta^{*}$ such that
$f_{\theta^{*}}(x_{i})=\hat{f}(x_{i}),~{}\forall~{}i$, and
$f_{\theta^{*}}(u)=\hat{f}(u),\forall~{}u\in\\{y_{1},\dots,y_{n}\\}\backslash\\{x_{1},\dots,x_{n}\\}$.
In other words, there exists $\theta^{*}$ such that

$f_{\theta^{*}}(x_{i})=\hat{f}(x_{i}),~{}f_{\theta^{*}}(y_{i})=\hat{f}(y_{i}),~{}\forall~{}i.$
(35)

Then we have

$\displaystyle\mathcal{L}_{\rm sep}(\hat{w};\theta^{*}(\epsilon))$
$\displaystyle=\frac{1}{2n}\sum_{i=1}^{n}[h_{1}(f_{\theta^{*}}(x_{i}))+h_{2}(-f_{\theta^{*}}(G_{\hat{w}}(z_{i})))]\overset{\rm(i)}{=}\sum_{i=1}^{n}[h_{1}(f_{\theta^{*}}(x_{i}))+h_{2}(-f_{\theta^{*}}(\hat{y}_{j}))]$
$\displaystyle\overset{\rm(ii)}{=}\frac{1}{2n}\sum_{i=1}^{n}[h_{1}(\hat{f}(x_{i}))+h_{2}(-\hat{f}(\hat{y}_{i}))]=L_{\rm
sep}(\hat{Y};\hat{f})\overset{\rm(iii)}{\geq}\alpha-\epsilon.$

In the above chain, (i) is due to the assumption $\hat{w}\in G^{-1}(\hat{Y})$
(which implies $G_{\hat{w}}(z_{j})=\hat{y}_{j}$), (ii) is due to the choice of
$\theta^{*}$. (iii) is due to (34).

Therefore, we have $\varphi_{\rm sep}(\hat{w})=\sup_{\theta}\mathcal{L}_{\rm
sep}(\hat{w};\theta)\geq\mathcal{L}_{\rm
sep}(\hat{w};\theta^{*}(\epsilon))\geq\alpha-\epsilon.$ Since this holds for
any $\epsilon$, we have $\varphi_{\rm sep}(\hat{w})\geq\alpha.$ Similarly,
from $\mathcal{L}_{\rm sep}(\hat{w};\theta)\leq\alpha$ we can obtain
$\varphi_{\rm sep}(\hat{w})\leq\alpha.$ Therefore $\varphi_{\rm
sep}(\hat{w})=\alpha=\phi_{\rm sep}(\hat{Y},X).$ This finishes the proof of
(33).

Define

$\displaystyle Q(X)\triangleq\\{Y=(y_{1},\dots,y_{n})\mid
y_{i}\in\\{x_{1},\dots,x_{n}\\},i\in\\{1,2,\dots,n\\};y_{i}=y_{j}\text{ for
some }i\neq j\\}.$

Any $Y\in Q(X)$ is a mode-collapsed pattern. According to Theorem 1, any $Y\in
Q(X)$ is a strict local minimum of $\phi_{\rm sep}(Y,X)$, and thus $Y$ is not
GMR. Therefore $\hat{w}\in G^{-1}(Y)$ where $Y\in Q(X)$ is not GMR; this is
because a non-decreasing path in the parameter space will be mapped to a non-
decreasing path in the function space, causing contradiction. Finally,
according to Assumption K.2, for any $Y$ there exists at least one pre-image
$w\in G^{-1}(Y)\cap\mathcal{W}$. There are $(n^{n}-n!)$ elements in $Q(X)$,
thus there are at least $(n^{n}-n!)$ points in $\mathcal{W}$ that are not
global-min-reachable. $\Box$

Proof of Proposition K.2. Similar to Eq. (33), we have $\varphi_{\rm
R}(w)=\phi_{\rm R}(Y,X)$ for any $w\in G^{-1}(Y)$. We need to prove that there
is a non-decreasing path from any $w_{0}\in\mathcal{W}$ to $w^{*}$, where
$w^{*}$ is a certain global minimum. Let $Y_{0}=G_{w_{0}}(z_{1},\dots,z_{n})$.
According to Thm. 2, there is a continuous path $Y(t)$ from $Y_{0}$ to $Y^{*}$
along which the loss value $\phi_{\rm R}(Y(t),X)$ is non-increasing. According
to Assump. 4.6, there is a continuous path $w(t)$ such that $w(0)=\hat{w}$,
$Y(t)=G_{w(t)}(Z),t\in[0,1]$. Along this path, the value $\varphi_{\rm
R}(w(t))=\phi_{\rm R}(Y(t),X)$ is non-increasing, and at the end the function
value $\varphi_{\rm R}(w(1))=\phi_{\rm R}(Y^{*},X)$ is the minimal value of
$\varphi_{\rm R}(w)$. Thus the existence of such a path is proved. $\Box$

###  K.4 A technical lemma

We present a technical lemma, that slightly generalizes [50, Proposition 1].

######  Assumption K.6.

$v_{1},v_{2},\dots,v_{m}\in\mathbb{R}^{d}$ are distinct, i.e., $v_{i}\neq
v_{j}$ for any $i\neq j$.

######  Lemma 2.

Define $T_{H}(V)=(\sigma(W_{H-1}\dots
W_{2}\sigma(W_{1}v_{i})))_{i=1}^{m}\in\mathbb{R}^{d_{H}\times m}$. Suppose
Assumptions K.4, K.5 and K.6 hold. Then the set
$\Omega=\\{(W_{1},\dots,W_{H-1}):\text{rank}(T_{H}(V))<m\\}$ has zero measure.

This claim is slightly different from [50, Proposition 1], which requires the
input vectors to have one distinct dimension (i.e., there exists $j$ such that
$v_{1j},\dots,v_{m,j}$ are distinct); here we only require the input vectors
to be distinct. It is not hard to link “distinct vectors” to “vectors with one
distinct dimension” by a variable transformation.

######  Claim K.4.

Suppose $v_{1},\dots,v_{m}\in\mathbb{R}^{d}$ are distinct. Then for generic
matrix $W\in\mathbb{R}^{d\times d}$, for the vectors
$\bar{v}_{i}=Wv_{i}\in\mathbb{R}^{d},i=1,\dots,n$, there exists $j$ such that
$\bar{v}_{1j},\dots,\bar{v}_{m,j}$ are distinct.

###### Proof.

Define the set $\Omega_{0}=\\{u\mid u\in\mathbb{R}^{1\times d},\exists i\neq
j\text{ s.t. }u^{T}v_{i}=u^{T}v_{j}\\}$. This is the union of $d(d-1)$
hyperplanes $\Omega_{ij}\triangleq\\{u\mid u\in\mathbb{R}^{1\times
d},u^{T}v_{i}=u^{T}v_{j}\\}$. Each hyperplane $\Omega_{ij}$ is a zero-measure
set, thus the union of them $\Omega_{0}$ is also a zero-measure set. Let $u$
be the first row of $W$, then $u$ is generic vector and thus not in
$\Omega_{0}$, which implies $\bar{v}_{11},\dots,\bar{v}_{m,1}$ are distinct. ∎

Proof of Lemma 2: Pick a generic matrix $A\in\mathbb{R}^{d_{v}\times d_{v}}$,
then $\bar{v}_{i}=Av_{i}\in\mathbb{R}^{d_{v}\times 1}$ has one distinct
dimension, i.e., there exists $j$ such that $\bar{v}_{1j},\dots,\bar{v}_{m,j}$
are distinct. In addition, we can assume $A$ is full rank (since it is
generic). Define

$\bar{T}_{H}(\bar{V})=(\sigma(W_{H-1}\dots
W_{2}\sigma(\bar{W}_{1}\bar{v}_{1})),\dots,\sigma(W_{H-1}\dots
W_{2}\sigma(\bar{W}_{1}\bar{v}_{m}))\in\mathbb{R}^{d_{H}\times m}.$

According to [50, Prop. 1], the set
$\bar{\Omega}=\\{(\bar{W}_{1},W_{2},W_{3},\dots,W_{H-1}):\text{rank}(\bar{T}_{H}(\bar{V}))<m\\}$
has zero measure. With the transformation
$\eta_{0}(\bar{W}_{1})=\bar{W}_{1}A^{-1}$, we have $\sigma(W_{H-1}\dots
W_{2}\sigma(\bar{W}_{1}\bar{v}_{i}))=\sigma(W_{H-1}\dots
W_{2}\sigma(W_{1}v_{i})),~{}\forall~{}i$ and thus
$\bar{T}_{H}(\bar{V})=T_{H}(V).$ Define
$\eta(\bar{W_{1}},W_{2},\dots,W_{m})=(\bar{W}_{1}A^{-1},W_{2},\dots,W_{m})$,
then $\eta$ is a homeomorphism between $\bar{\Omega}$ and $\Omega$. Therefore
the set $\Omega=\\{(W_{1},\dots,W_{H-1}):\text{rank}(T_{H}(V))<m\\}$ has zero
measure. $\Box$

###  K.5 Proof of claims

Proof of Claim K.1: According to Lemma 2, $\mathcal{W}$ is a dense subset of
$\mathbb{R}^{J}$ (in fact, $\Omega$ is defined for a general neural network,
and $\mathcal{W}$ is defined for the generator network, thus an instance of
$\Omega$). As a result, there exists $(W_{1},\dots,W_{H-1})$ such that
$T_{H}(Z)$ has rank at least $n$. Thus for any
$y_{1},y_{2},\dots,y_{n}\in\mathbb{R}^{d}$, there exists $W_{H}$ such that
$W_{H}T_{H}(Z)=(y_{1},\dots,y_{n})$. $\Box$

Proof of Claim K.2:  For any continuous path $Y(t),t\in[0,1]$ in the space
$\mathbb{R}^{d\times n}$, any $w_{0}\in G^{-1}(Y(0))$ and any $\epsilon>0$,
our goal is to show that there exists a continuous path $w(t),t\in[0,1]$ such
that $w(0)=w_{0}$ and $Y(t)=G_{w(t)}(Z),t\in[0,1]$.

Due to the assumption of $w_{0}\in\mathcal{W}$, we know that $w_{0}$
corresponds to a rank-$n$ post-activation matrix $T_{H}(Z)$. Suppose
$w_{0}=(W_{1},\dots,W_{H})$ and
$T_{H}(Z)=(T_{H}(z_{1}),\dots,T_{H}(z_{n}))\in\mathbb{R}^{d_{H}\times n}$ has
rank $n$. Since $T_{H}(Z)$ is full rank, for any path from $Y(0)$ to $Y(1)$,
we can continuously change $W_{H}$ such that the output of $G_{w}(Z)$ changes
from $Y(0)$ to $Y(1)$. Thus there exists a continuous path $w(t),t\in[0,1]$
such that $w(0)=w_{0}$ and $Y(t)=G_{w(t)}(Z),t\in[0,1]$. $\Box$

Proof of Claim K.3: This is a direct application of Lemma 2. Different from
Claim K.2, here we apply Lemma 2 to the discriminator network. $\Box$

##  Appendix L Discussion of Wasserstein GAN

W-GAN is a popular formulation of GAN, so a natural question is whether we can
prove a similar landscape result for W-GAN. Consider W-GAN formulation
(empirical version) $\min_{Y}\phi_{\rm W}(Y,X),$ where

$\phi_{\rm W}(Y,X)=\max_{|f|_{L}\leq
1}\frac{1}{n}\sum_{i=1}^{n}[f(x_{i})-f(y_{i})].$

For simplicity we consider the same number of generated samples and true
samples. It can be viewed as a special case of RpGAN where $h(t)=-t$; it can
also be viewed as a special case of SepGAN where $h_{1}(t)=h_{2}(t)=-t$.

However, the major complication is the Lipschitz constraint. It makes the
computation of the function values much harder. For the case of $n=2$, the
function value of $\phi_{\rm W}(Y,X)$ is provided in the following claim.

######  Claim L.1.

Suppose $n=2$. Denote $a_{1}=x_{1},a_{2}=x_{2},a_{3}=y_{1},a_{4}=y_{2}$. The
value of $\phi_{\rm W}(Y,X)$ is

$\displaystyle\max_{u_{1},u_{2},u_{3},u_{4}\in\mathbb{R}}$ $\displaystyle
u_{1}+u_{2}-u_{3}-u_{4},$ s.t.
$\displaystyle|u_{i}-u_{j}|\leq\|a_{i}-a_{j}\|,\forall i,j\in\\{1,2,3,4\\}.$

This claim is not hard to prove, and we skip the proof here.

This claim indicates that computing $\phi_{\rm W}(Y,X)$ is equivalent to
solving a linear program (LP). Solving LP itself is computationally feasible,
but our landscape analysis requires to infer about the global landscape of
$\phi_{\rm W}(Y,X)$ as a function of $Y$. In classical optimization, it is
possible to state that the optimal value of an LP is a convex function of a
certain parameter (e.g. the coefficient of the objective). But in our LP
$y_{i}$’s appear in multiple positions of the LP, and we are not aware of an
existing result that can be readily applied.

Similar to Kantorovich-Rubinstein Duality, we can write down the dual problem
of the LP where the objective is linear combination of $\|a_{i}-a_{j}\|$.
However, it is still not clear what to say about the global landscape, due to
the lack of closed-form solutions.

Finally, we remark that although W-GAN has a strong theoretical appeal, it did
not replace JS-GAN or simple variants of JS-GAN in recent GAN models. For
instance, SN-GAN [67] and BigGAN [18] use hinge-GAN.

(a) Generator | (b) Discriminator
---|---
$z\in\mathbb{R}^{128}\sim{\mathcal{N}}(0,I)$ |  image $x\in[-1,1]^{H\times W\times 3}$
128 $\rightarrow h\times w\times$ 512/c, dense, linear |  $3\times 3$, stride 1 conv, 64/c
$4\times 4$, stride 2 deconv, 256/c, BN, ReLU |  $4\times 4$, stride 2 conv, 128/c
|  $3\times 3$, stride 1 conv, 128/c
$4\times 4$, stride 2 deconv, 128/c, BN, ReLU |  $4\times 4$, stride 2 conv, 256/c
|  $3\times 3$, stride 1 conv, 256/c
$4\times 4$, stride 2 deconv, 64/c, BN, ReLU |  $4\times 4$, stride 2 conv, 512/c
|  $3\times 3$, stride 1 conv, 512/c
$3\times 3$, stride 1 conv, 3, Tanh |  $h\times w\times 512/c\rightarrow s$, linear
Table 7: CNN models for CIFAR-10 and STL-10 used in our experiments on image
Generation. h = w = 4, H = W = 32 for CIFAR-10. h = w = 6, H = W = 48 for
STL-10. c=1, 2 and 4 for the regular, 1/2 and 1/4 channel structures
respectively. All layers of D use LReLU-0.1 (except the final dense ‘’linear”
layer).

(a) Generator | (b) Discriminator
---|---
$z\in{\mathbb{R}}^{128}\sim{\mathcal{N}}(0,I)$ | $x\in[-1,1]^{256\times 256\times 3}$
reshape $\rightarrow$ $128\times 1\times 1$ |  $4\times 4$, stride 2 conv, 32,
$4\times 4$, stride 1 deconv, BN, 1024 |  $4\times 4$, stride 2 conv, 64
$4\times 4$, stride 2 deconv, BN, 512 |  $4\times 4$, stride 2 conv, 128
$4\times 4$, stride 2 deconv, BN, 256 |  $4\times 4$, stride 2 conv, 256
$4\times 4$, stride 2 deconv, BN, 128 |  $4\times 4$, stride 2 conv, 512
$4\times 4$, stride 2 deconv, BN, 64 |  $4\times 4$, stride 2 conv, 1024
$4\times 4$, stride 2 deconv, BN, 32 |  dense $\rightarrow$ 1
$4\times 4$, stride 2 deconv, 3, Tanh |
Table 8: CNN model architecture for size 256 LSUN used in our experiments on
high resolution image generation. All layers of G use ReLU (except one layer
with Tanh); all layers of D use LReLU-0.1.

(a) Generator | (b) Discriminator
---|---
$z\in\mathbb{R}^{128}\sim{\mathcal{N}}(0,I)$ |  image $x\in[-1,1]^{32\times 32\times 3}$
dense, $4\times 4\times 256$/c | ResBlock down 128/c
ResBlock up 256/c | ResBlock down 128/c
ResBlock up 256/c | ResBlock down 128/c
ResBlock up 256/c | ResBlock down 128/c
BN, ReLU, $3\times 3$ conv, 3 Tanh | LReLU 0.1
| Global sum pooling
|  dense $\rightarrow$ 1
Table 9: Resnet architecture for CIFAR-10. c=1, 2 and 4 for the regular, 1/2
and 1/4 channel structures respectively.

(a) Generator | (b) Discriminator
---|---
$z\in\mathbb{R}^{128}\sim{\mathcal{N}}(0,I)$ |  image $x\in[-1,1]^{48\times 48\times 3}$
dense, $6\times 6\times 512$/c | ResBlock down 64/c
ResBlock up 256/c | ResBlock down 128/c
ResBlock up 128/c | ResBlock down 256/c
ResBlock up 64/c | ResBlock down 512/c
BN, ReLU, $3\times 3$ conv, 3 Tanh | ResBlock down 1024/c
| LReLU 0.1
| Global sum pooling
|  dense $\rightarrow$ 1
Table 10: Resnet architecture for STL-10. c=1, 2 and 4 for the regular, 1/2
and 1/4 channel structures respectively.

(a) Generator | (b) Discriminator
---|---
$z\in\mathbb{R}^{128}\sim{\mathcal{N}}(0,I)$ |  image $x\in[-1,1]^{32\times 32\times 3}$
dense, $4\times 4\times 128$ | BRes down (64, 32, 64)
BRes up (128, 64, 128) | BRes down (64, 32, 64)
BRes up (128, 64, 128) | BRes down (64, 32, 64)
BRes up (128, 64, 128) | BRes down (64, 32, 64)
BN, ReLU, $3\times 3$ conv, 3 Tanh | LReLU 0.1
| Global sum pooling
|  dense $\rightarrow$ 1
Table 11: BottleNeck Resnet models for CIFAR-10. BRes refers to BottleNeck
ResBlock. BRes $(a,b,c)$ refers to the Bottleneck resblock with (input, hidden
and output) being $(a,b,c)$.

(a) Generator | (b) Discriminator
---|---
$z\in{\mathbb{R}}^{128}\sim{\mathcal{N}}(0,I)$ |  image $x\in[-1,1]^{48\times 48\times 3}$
dense, $6\times 6\times 256$ | BRes down (3, 16, 32)
BRes up (256, 64, 128) | BRes down (32, 16, 64)
BRes up (128, 32, 64) | BRes down (64, 32, 128)
BRes up (64, 16, 32) | BRes down (128, 64, 256)
BN, ReLU, $3\times 3$ conv, 3 Tanh | BRes down (256, 128, 512)
| LReLU 0.1
| Global sum pooling
|  dense $\rightarrow$ 1
Table 12: BottleNeck Resnet models for STL-10.

RS-GAN generator learning rate
---
|  | CIFAR-10 | STL-10
CNN | No normalization | 2e-4 | 5e-4
Regular + SN | 5e-4 | 5e-4
channel/2 + SN | 5e-4 | 5e-4
channel/4 + SN | 2e-4 | 5e-4
ResNet | Regular+SN | 1.5e-3 | 1e-3
channel/2 + SN | 1.5e-3 | 1e-3
channel/4 + SN | 1e-3 | 5e-4
BottleNeck | 1e-3 | 1e-3

WGAN-GP Hyper-parameters
---
generator learning rate | 1e-4
discriminator learning rate | 1e-4
$\beta_{1}$ | 0.5
$\beta_{2}$ | 0.9
Gradient penalty $\lambda$ | 10
# D iterations per G iteration | 5

Table 13: Learning rate for RS-GAN in each setting. Hyper-parameters used for
WGAN-GP


11institutetext: Shaoshi Chen 22institutetext: KLMM, Academy of Mathematics
and Systems Science, Chinese Academy of Sciences,
Beijing 100190, (China)
School of Mathematical Sciences, University of Chinese Academy of Sciences,
Beijing 100049, (China)
22email<EMAIL_ADDRESS>
This work was supported by the NSFC grants 11501552, 11688101 and by the
Frontier Key Project (QYZDJ-SSW-SYS022) and the Fund of the Youth Innovation
Promotion Association, CAS

# How to generate all possible rational Wilf-Zeilberger pairs?

Dedicated to the memory of Jonathan M. Borwein and Ann Johnson

Shaoshi Chen

###### Abstract

A Wilf–Zeilberger pair $(F,G)$ in the discrete case satisfies the equation

$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k).$

We present a structural description of all possible rational Wilf–Zeilberger
pairs and their continuous and mixed analogues.

##  1 Introduction

The Wilf–Zeilberger (abbr. WZ) theory Wilf1992 ; WilfZeilberger1992 ;
PWZbook1996  has become a bridge between symbolic computation and
combinatorics. Through this bridge, not only classical combinatorial
identities from handbooks and long-standing conjectures in combinatorics, such
as Gessel’s conjecture KKZ2009 ; Bostan2010  and $q$-TSPP conjecture KKZ2011 ,
are proved algorithmically, but also some new identities and conjectures
related to mathematical constants, such as $\pi$ and zeta values, are
discovered via computerized guessing Gessel1995 ; Borwein2004 ; Sun2011 ;
CHZ2016 .

WZ-pair is one of leading concepts in the WZ theory that was originally
introduced in WilfZeilberger1992  with a recent brief description in
Tefera2010 . In the discrete case, a WZ-pair $(F(n,k),G(n,k))$ satisfies the
WZ equation

$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k),$

where both $F$ and $G$ are hypergeometric terms, i.e., their shift quotients
with respect to $n$ and $k$ are rational functions in $n$ and $k$,
respectively. Once a WZ-pair is given, one can sum on both sides of the above
equation over $k$ from $0$ to $\infty$ to get

$\sum_{k=0}^{\infty}F(n+1,k)-\sum_{k=0}^{\infty}F(n,k)=\lim_{k\rightarrow\infty}G(n,k+1)-G(n,0).$

If $G(n,0)$ and $\lim_{k\rightarrow\infty}G(n,k+1)$ are $0$ then we obtain

$\sum_{k=0}^{\infty}F(n+1,k)=\sum_{k=0}^{\infty}F(n,k),$

which implies that $\sum_{k=0}^{\infty}F(n,k)$ is independent of $n$. Thus, we
get the identity $\sum_{k=0}^{\infty}F(n,k)=c$, where the constant $c$ can be
determined by evaluating the sum for one value of $n$. We may also get a
companion identity by summing the WZ-equation over $n$. For instance, the pair
$(F,G)$ with

$F=\frac{\binom{n}{k}^{2}}{\binom{2n}{n}}\quad\text{and}\quad
G={\frac{(2k-3n-3){k}^{2}}{2(2n+1)(-n-1+k)^{2}}}\cdot\frac{\binom{n}{k}^{2}}{\binom{2n}{n}}$

leads to two identities

$\sum_{k=0}^{\infty}\binom{n}{k}^{2}=\binom{2n}{n}\quad\text{and}\quad\sum_{n=0}^{\infty}\frac{(3n-2k+1)}{2(2n+1)\binom{2n}{n}}\binom{n}{k}^{2}=1.$

Besides to prove combinatorial identities, WZ-pairs have many other
applications. One of the applications can be traced back to Andrei Markov’s
1890 method for convergence-acceleration of series for computing $\zeta(3)$,
which leads to the Markov-WZ method MZ2004 ; Kondratieva2005 ; Mohammed2005 .
WZ-pairs also play a central role in the study of finding Ramanujan-type and
Zeilberger-type series for constants involving $\pi$ in EZ1994 ; Guillera2002
; Guillera2006 ; Guillera2010 ; Guillera2013 ; Liu2012 ; Zudilin2011 ; HKS2018
, zeta values Pilehrood2008a ; Pilehrood2008b  and their $q$-analogues
Pilehrood2011 ; GuoLiu2018 ; GuoZudilin2018 . Most recent applications are
related to congruences and super congruences Zudilin2009 ; Long2011 ; Sun2011
; Sun2012 ; Sun2013 ; Sun2013b ; Guo2017 ; Guo2018 .

For appreciation we select some remarkable $(q)$-series about $\pi,\zeta(3)$
together with (super)-congruences whose proofs can be obtained via WZ-pairs as
follows (this list is surely not comprehensive):

  1. 1.

Ramanujan’s series for $1/\pi$: first recorded in Ramanujan’s second notebook,
proved by Bauer in Bauer1859 , and by Ekhad and Zeilberger using WZ-pairs in
EZ1994 . For a nice survey on Ramanujan’s series, see BBC2009 .

$\frac{2}{\pi}=\sum_{k=0}^{\infty}\frac{4k+1}{(-64)^{k}}\binom{2k}{k}^{3}.$

  2. 2.

Guillera’s series for $1/\pi^{2}$: found and proved by Guillera in 2002 using
WZ-pairs Guillera2002 . For more results on Ramanujan-type series for
$1/\pi^{2}$, see Zudilin’s surveys Zudilin2007 ; Zudilin2011 .

$\frac{128}{\pi^{2}}=\sum_{k=0}^{\infty}(-1)^{k}\binom{2k}{k}^{5}\frac{820k^{2}+180k+13}{2^{20k}}.$

  3. 3.

Guillera’s Zeilberger-type series for $\pi^{2}$: found and proved by Guillera
using WZ-pairs in Guillera2008 .

$\frac{\pi^{2}}{2}=\sum_{k=1}^{\infty}\frac{(3k-1)16^{k}}{k^{3}\binom{2k}{k}^{3}}.$

  4. 4.

Markov–Apéry’s series for $\zeta(3)$: first discovered by Andrei Markov in
1890, used by Apéry for his irrationality proof, and proved by Zeilberger
using WZ-pairs in Zeilberger1993 .

$\zeta(3)=\frac{5}{2}\sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{k^{3}\binom{2k}{k}}.$

  5. 5.

Amdeberhan’s series for $\zeta(3)$: proved by Amdeberhan in 1996 using WZ-
pairs Amdeberhan1996 .

$\zeta(3)=\frac{1}{4}\sum_{k=1}^{\infty}(-1)^{k-1}\frac{56k^{2}-32k+5}{k^{3}(2k-1)^{2}\binom{2k}{k}\binom{3k}{k}}.$

  6. 6.

Bailey–Borwein–Bradley identity: experimentally discovered and proved by
Bailey et al. in BBB2006 , a proof using the Markov-WZ method is given in
Pilehrood2008b ; Pilehrood2008b  and its $q$-analogue is presented in
Pilehrood2011 .

$\sum_{k=0}^{\infty}\zeta(2k+2)z^{2k}=3\sum_{k=1}^{\infty}\frac{1}{\binom{2k}{k}(k^{2}-z^{2})}\prod_{m=1}^{k-1}\frac{m^{2}-4z^{2}}{m^{2}-z^{2}},\quad\text{$z\in{\mathbb{C}}$
with $|z|<1$}.$

  7. 7.

van Hamme’s supercongruence I: first conjectured by van Hamme Hamme1997 ,
proved by Mortenson Mortenson2008  using ${}_{6}F_{5}$ transformations and by
Zudilin Zudilin2009  using WZ-pairs.

$\sum_{k=0}^{\frac{p-1}{2}}\frac{4k+1}{(-64)^{k}}\binom{2k}{k}^{3}\equiv
p(-1)^{\frac{p-1}{2}}(\text{mod}~{}p^{3}),$

where $p$ is an odd prime and the multiplicative inverse of $(-64)^{k}$ should
be computed modulo $p^{3}$.

  8. 8.

van Hamme’s supercongruence II: first conjectured by van Hamme Hamme1997 ,
proved by Long Long2011  using hypergeometric evaluation identities, one of
which is obtained by Gessel using WZ-pairs in Gessel1995 .

$\sum_{k=0}^{\frac{p-1}{2}}{\frac{6k+1}{256^{k}}}\binom{2k}{k}^{3}\equiv
p(-1)^{\frac{p-1}{2}}(\text{mod}~{}p^{4}),$

where $p>3$ is a prime and the multiplicative inverse of $(256)^{k}$ should be
computed modulo $p^{4}$.

  9. 9.

Guo’s $q$-analogue of van Hamme’s supercongruence I: discovered and proved
recently by Guo using WZ-pairs in Guo2018 .

$\sum_{k=0}^{\frac{p-1}{2}}(-1)^{k}q^{k^{2}}[4k+1]_{q}\frac{(q;q^{2})_{k}^{3}}{(q^{2};q^{2})_{k}^{3}}\equiv[p]_{q}q^{\frac{(p-1)^{2}}{4}}(-1)^{\frac{p-1}{2}}\pmod{[p]_{q}^{3}},$

where for $n\in{\mathbb{N}}$, $(a;q)_{n}:=(1-a)(1-aq)\cdots(1-aq^{n-1})$ with
$(a;q)_{0}=1$, $[n]_{q}=1+q+\cdots+q^{n-1}$ and $p$ is an odd prime.

  10. 10.

Hou–Krattenthaler–Sun’s $q$-analogue of Guillera’s Zeilberger-type series for
$\pi^{2}$: inspired by a recent conjecture on supercongruence by Guo in
Guo2018b , and proved using WZ-pairs in HKS2018 . This work is also connected
to other emerging developments on $q$-analogues of series for famous constants
and formulae Sun2018 ; GuoZudilin2018 ; GuoLiu2018 .

$2\sum_{k=0}^{\infty}q^{2k^{2}+2k}(1+q^{2k^{2}+2}-2q^{4k+3})\frac{(q^{2};q^{2})_{k}^{3}}{(q;q^{2})^{3}_{k+1}(-1;q)_{2k+3}}=\sum_{k=0}^{\infty}\frac{q^{2k}}{(1-q^{2k+1})^{2}}.$

For applications, it is crucial to have WZ-pairs at hand. In the previous
work, WZ-pairs are obtained either by guessing from the identities to be
proved using Gosper’s algorithm or by certain transformations from a given WZ-
pair Gessel1995 . Riordan in the preface of his book Riordan1968  commented
that “the central fact developed is that identities are both inexhaustible and
unpredictable; the age-old dream of putting order in this chaos is doomed to
failure ”. As an optimistic respond to Riordan’s comment, Gessel in his
talk111The talk was given at the Waterloo Workshop in Computer Algebra (in
honor of Herbert Wilf’s 80th birthday), Wilfrid Laurier University, May 28,
2011. For the talk slides, see the link:
http://people.brandeis.edu/~gessel/homepage/slides/wilf80-slides.pdf on the WZ
method motivated with some examples that “WZ forms bring order to this chaos
”, where WZ-forms are a multivariate generalization of WZ-pairs Zeilberger1993
. With the hope of discovering more combinatorial identities in an intrinsic
and algorithmic way, it is natural and challenging to ask the following
question.

###### Problem 1

How to generate all possible WZ-pairs algorithmically?

This problem seems quite open, but every promising project needs a starting
point. In Liu2015 , Liu had described the structure of a special class of
analytic WZ-functions with $F=G$ in terms of Rogers–Szegö polynomials and
Stieltjes–Wigert polynomials in the $q$-shift case. In Sun2012 , Sun studied
the relation between generating functions of $F(n,k)$ and $G(n,k)$ if $(F,G)$
is a WZ-pair and applied this relation to prove some combinatorial identities.
In this paper, we solve the problem completely for the first non-trivial case,
namely, the case of rational WZ-pairs. To this end, let us first introduce
some notations. Throughout this paper, let $K$ be a field of characteristic
zero and $K(x,y)$ be the field of rational functions in $x$ and $y$ over $K$.
Let $D_{x}=\partial/\partial_{x}$ and $D_{y}=\partial/\partial_{y}$ be the
usual derivations with respect to $x$ and $y$, respectively. The shift
operators ${\sigma}_{x}$ and ${\sigma}_{y}$ are defined respectively as

${\sigma}_{x}(f(x,y))=f(x+1,y)\quad\text{and}\quad{\sigma}_{y}(f(x,y))=f(x,y+1)\quad\text{for
$f\in K(x,y)$.}$

For any $q\in K\setminus\\{0\\}$, we define the $q$-shift operators
$\tau_{q,x}$ and $\tau_{q,y}$ respectively as

$\tau_{q,x}(f(x,y))=f(qx,y)\quad\text{and}\quad\tau_{q,y}(f(x,y))=f(x,qy)\quad\text{for
$f\in K(x,y)$.}$

For $z\in\\{x,y\\}$, let $\Delta_{z}$ and $\Delta_{q,z}$ denote the difference
and $q$-difference operators defined by $\Delta_{z}(f)={\sigma}_{z}(f)-f$ and
$\Delta_{q,z}(f)=\tau_{q,z}(f)-f$ for $f\in K(x,y)$, respectively.

###### Definition 1

Let $\partial_{x}\in\\{D_{x},\Delta_{x},\Delta_{q,x}\\}$ and
$\partial_{y}\in\\{D_{y},\Delta_{y},\Delta_{q,y}\\}$. A pair $(f,g)$ with
$f,g\in K(x,y)$ is called a _WZ-pair_ with respect to
$(\partial_{x},\partial_{y})$ in $K(x,y)$ if
$\partial_{x}(f)=\partial_{y}(g)$.

The set of all rational WZ-pairs in $K(x,y)$ with respect to
$(\partial_{x},\partial_{y})$ forms a linear space over $K$, denoted by
${\mathcal{P}}_{(\partial_{x},\partial_{y})}$. A WZ-pair $(f,g)$ with respect
to $(\partial_{x},\partial_{y})$ is said to be _exact 222This is motivated by
the fact that a differential form $\omega=gdx+fdy$ with $f,g\in K(x,y)$ is
exact in $K(x,y)$ if and only if $f=D_{y}(h)$ and $g=D_{x}(h)$ for some $h\in
K(x,y)$._ if there exists $h\in K(x,y)$ such that $f=\partial_{y}(h)$ and
$g=\partial_{x}(h)$. Let ${\mathcal{E}}_{(\partial_{x},\partial_{y})}$ denote
the set of all exact WZ-pairs with respect to $(\partial_{x},\partial_{y})$,
which forms a subspace of ${\mathcal{P}}_{(\partial_{x},\partial_{y})}$. The
goal of this paper is to provide an explicit description of the structure of
the quotient space
${\mathcal{P}}_{(\partial_{x},\partial_{y})}/{\mathcal{E}}_{(\partial_{x},\partial_{y})}$.

The remainder of this paper is organized as follows. As our key tools, residue
criteria for rational integrability and summability are recalled in Section 2.
In Section 3, we present structure theorems for rational WZ-pairs in three
different settings. This paper ends with a conclusion along with some remarks
on the future research.

##  2 Residue criteria

In this section, we recall the notion of residues and their ($q$-)discrete
analogues for rational functions and some residue criteria for rational
integrability and summability from BronsteinBook ; ChenSinger2012 ;
HouWang2015 .

Let $F$ be a field of characteristic zero and $F(z)$ be the field of rational
functions in $z$ over $F$. Let $D_{z}$ be the usual derivation on $F(z)$ such
that $D_{z}(z)=1$ and $D_{z}(c)$=0 for all $c\in F$. A rational function $f\in
F(z)$ is said to be _$D_{z}$ -integrable_ in $F(z)$ if $f=D_{z}(g)$ for some
$g\in F(z)$. By the irreducible partial fraction decomposition, one can always
uniquely write $f\in F(z)$ as

$f=q+\sum_{i=1}^{n}\sum_{j=1}^{m_{i}}\frac{a_{i,j}}{d_{i}^{j}},$ (1)

where $q,a_{i,j},d_{i}\in F[z]$, $\deg_{z}(a_{i,j})<\deg_{z}(d_{i})$ and the
$d_{i}$’s are distinct irreducible and monic polynomials. We call $a_{i,1}$
the _pseudo $D_{z}$-residue_ of $f$ at $d_{i}$, denoted by
$\text{pres}_{D_{z}}(f,d_{i})$. For an irreducible polynomial $p\in F[z]$, we
let ${\mathcal{O}}_{p}$ denote the set

${\mathcal{O}}_{p}:=\left\\{\frac{a}{b}\in F(z)\mid\text{$a,b\in F[z]$
with~{}$\gcd(a,b)$ and ${p}\nmid b$}\right\\},$

and let ${\mathcal{R}}_{p}$ denote the set $\\{f\in F(z)\mid
pf\in{\mathcal{O}}_{p}\\}$. If $f\in{\mathcal{R}}_{p}$, the pseudo-residue
$\text{pres}_{D_{z}}(f,p)$ is called the _$D_{z}$ -residue_ of $f$ at $p$,
denoted by ${\operatorname{res}}_{D_{z}}(f,p)$. The following example shows
that pseudo-residues may not be the obstructions for $D_{z}$-integrability in
$F(z)$.

###### Example 1

Let $F:={\mathbb{Q}}$ and $f=(1-x^{2})/(x^{2}+1)^{2}$. Then the irreducible
partial fraction decomposition of $f$ is of the form

$f=\frac{2}{(x^{2}+1)^{2}}-\frac{1}{x^{2}+1}.$

The pseudo-residue of $f$ at $x^{2}+1$ is $-1$, which is nonzero. However, $f$
is $D_{z}$-integrable in $F(z)$ since $f=D_{z}(x/(x^{2}+1))$.

The following lemma shows that $D_{z}$-residues are the only obstructions for
$D_{z}$-integrability of rational functions with squarefree denominators, so
are pseudo-residues if $F$ is algebraically closed.

###### Lemma 1

(ChenSinger2012, , Proposition 2.2) Let $f=a/b\in F(z)$ be such that $a,b\in
F[z]$, $\gcd(a,b)=1$. If $b$ is squarefree, then $f$ is $D_{z}$-integrable in
$F(z)$ if and only if ${\operatorname{res}}_{D_{z}}(f,d)=0$ for any
irreducible factor $d$ of $b$. If $F$ is algebraically closed, then $f$ is
$D_{z}$-integrable in $F(z)$ if and only if
$\text{pres}_{D_{z}}(f,z-\alpha)=0$ for any root $\alpha$ of the denominator
$b$.

By the Ostrogradsky–Hermite reduction Ostrogradsky1845 ; Hermite1872 ;
BronsteinBook , we can decompose a rational function $f\in F(z)$ as
$f=D_{z}(g)+a/b$, where $g\in F(z)$ and $a,b\in F[z]$ are such that
$\deg_{z}(a)<\deg_{z}(b),\gcd(a,b)=1$, and $b$ is a squarefree polynomial in
$F[z]$. By Lemma 1, $f$ is $D_{z}$-integrable in $F(z)$ if and only if $a=0$.

We now recall the ($q$-)discrete analogue of $D_{z}$-residues introduced in
ChenSinger2012 ; HouWang2015 . Let $\phi$ be an automorphism of $F(z)$ that
fixes $F$. For a polynomial $p\in F[z]$, we call the set $\\{\phi^{i}(p)\mid
i\in{\mathbb{Z}}\\}$ the _$\phi$ -orbit_ of $p$, denoted by $[p]_{\phi}$. Two
polynomials $p,q\in F[z]$ are said to be $\phi$-equivalent (denoted as
$p\sim_{\phi}q$) if they are in the same $\phi$-orbit, i.e., $p=\phi^{i}(q)$
for some $i\in{\mathbb{Z}}$. For any $a,b\in F(z)$ and $m\in{\mathbb{Z}}$, we
have

$\frac{a}{\phi^{m}(b)}=\phi(g)-g+\frac{\phi^{-m}(a)}{b},$ (2)

where $g$ is equal to $\sum_{i=0}^{m-1}\frac{\phi^{i-m}(a)}{\phi^{i}(b)}$ if
$m\geq 0$, and equal to $-\sum_{i=0}^{-m-1}\frac{\phi^{i}(a)}{\phi^{m+i}(b)}$
if $m<0$.

Let ${\sigma}_{z}$ be the shift operator with respect to $z$ defined by
${\sigma}_{z}(f(z))=f(z+1)$. Note that ${\sigma}_{z}$ is an automorphism of
$F(z)$ that fixes $F$. A rational function $f\in F(z)$ is said to be
_${\sigma}_{z}$ -summable_ in $F(z)$ if $f={\sigma}_{z}(g)-g$ for some $g\in
F(z)$. For any $f\in F(z)$, we can uniquely decompose it into the form

$f=p(z)+\sum_{i=1}^{n}\sum_{j=1}^{m_{i}}\sum_{\ell=0}^{e_{i,j}}\frac{a_{i,j,\ell}}{{\sigma}_{z}^{\ell}(d_{i})^{j}},$
(3)

where $p,a_{i,j,\ell},d_{i}\in F[z]$, $\deg_{z}(a_{i,j,\ell})<\deg_{z}(d_{i})$
and the $d_{i}$’s are irreducible and monic polynomials such that no two of
them are ${\sigma}_{z}$-equivalent. We call the sum
$\sum_{\ell=0}^{e_{i,j}}{\sigma}_{z}^{-\ell}(a_{i,j,\ell})$ the
_${\sigma}_{z}$ -residue_ of $f$ at $d_{i}$ of multiplicity $j$, denoted by
${\operatorname{res}}_{{\sigma}_{z}}(f,d_{i},j)$. Recently, the notion of
${\sigma}_{z}$-residues has been generalized to the case of rational functions
over elliptic curves (Dreyfus2018, , Appendix B). The following lemma is a
discrete analogue of Lemma 1 which shows that ${\sigma}_{z}$-residues are the
only obstructions for ${\sigma}_{z}$-summability in the field $F(z)$.

###### Lemma 2

(ChenSinger2012, , Proposition 2.5) Let $f=a/b\in F(z)$ be such that $a,b\in
F[z]$ and $\gcd(a,b)=1$. Then $f$ is ${\sigma}_{z}$-summable in $F(z)$ if and
only if ${\operatorname{res}}_{{\sigma}_{z}}(f,d,j)=0$ for any irreducible
factor $d$ of the denominator $b$ of any multiplicity $j\in{\mathbb{N}}$.

By Abramov’s reduction Abramov1975 ; Abramov1995b , we can decompose a
rational function $f\in F(z)$ as

$f=\Delta_{z}(g)+\sum_{i=1}^{n}\sum_{j=1}^{m_{i}}\frac{a_{i,j}}{b_{i}^{j}},$

where $g\in F(z)$ and $a_{i,j},b_{i}\in F[z]$ are such that
$\deg_{z}(a_{i,j})<\deg_{z}(b_{i})$ and the $b_{i}$’s are irreducible and
monic polynomials in distinct ${\sigma}_{z}$-orbits. By Lemma 2, $h$ is
${\sigma}_{z}$-summable in $F(z)$ if and only if $a_{i,j}=0$ for all $i,j$
with $1\leq i\leq n$ and $1\leq j\leq m_{i}$.

Let $q$ be a nonzero element of $F$ such that $q^{m}\neq 1$ for all nonzero
$m\in{\mathbb{Z}}$ and let $\tau_{q,z}$ be the $q$-shift operator with respect
to $z$ defined by $\tau_{q,z}(f(z))=f(qz)$. Since $q$ is nonzero, $\tau_{q,z}$
is an automorphism of $F(z)$ that fixes $F$. A rational function $f\in F(z)$
is said to be _$\tau_{q,z}$ -summable_ in $F(z)$ if $f=\tau_{q,z}(g)-g$ for
some $g\in F(z)$. For any $f\in F(z)$, we can uniquely decompose it into the
form

$f=c+zp_{1}+\frac{p_{2}}{z^{s}}+\sum_{i=1}^{n}\sum_{j=1}^{m_{i}}\sum_{\ell=0}^{e_{i,j}}\frac{a_{i,j,\ell}}{\tau_{q,z}^{\ell}(d_{i})^{j}},$
(4)

where $c\in F,s,n,m_{i},e_{i,j}\in{\mathbb{N}}$ with $s\neq 0$, and
$p_{1},p_{2},a_{i,j,\ell},d_{i}\in F[z]$ are such that $\deg_{z}(p_{2})<s$,
$\deg_{z}(a_{i,j,\ell})<\deg_{z}(d_{i})$, and $p_{2}$ is either zero or has
nonzero constant term, i.e., $p_{2}(0)\neq 0$. Moreover, the $d_{i}$’s are
irreducible and monic polynomials in distinct $\tau_{q,z}$-orbits and $z\nmid
d_{i}$ for all $i$ with $1\leq i\leq n$. We call the constant $c$ the
_$\tau_{q,z}$ -residue_ of $f$ at infinity, denoted by
${\operatorname{res}}_{\tau_{q,z}}(f,\infty)$ and call the sum
$\sum_{\ell=0}^{e_{i,j}}\tau_{q,z}^{-\ell}(a_{i,j,\ell})$ the _$\tau_{q,z}$
-residue_ of $f$ at $d_{i}$ of multiplicity $j$, denoted by
${\operatorname{res}}_{\tau_{q,z}}(f,d_{i},j)$. A $q$-analogue of Lemma 2 is
as follows.

###### Lemma 3

(ChenSinger2012, , Proposition 2.10) Let $f=a/b\in F(z)$ be such that $a,b\in
F[z]$ and $\gcd(a,b)=1$. Then $f$ is $\tau_{q,z}$-summable in $F(z)$ if and
only if ${\operatorname{res}}_{\tau_{q,z}}(f,\infty)=0$ and
${\operatorname{res}}_{\tau_{q,z}}(f,d,j)=0$ for any irreducible factor $d$ of
the denominator $b$ of any multiplicity $j\in{\mathbb{N}}$.

By a $q$-analogue of Abramov’s reduction Abramov1995b , we can decompose a
rational function $f\in F(z)$ as

$f=\Delta_{q,z}(g)+c+\sum_{i=1}^{n}\sum_{j=1}^{m_{i}}\frac{a_{i,j}}{b_{i}^{j}},$

where $g\in F(z),c\in F,$ and $a_{i,j},b_{i}\in F[z]$ are such that
$\deg_{z}(a_{i,j})<\deg_{z}(b_{i})$ and the $b_{i}$’s are irreducible and
monic polynomials in distinct ${\sigma}_{z}$-orbits and $\gcd(z,b_{i})=1$ for
all $i$ with $1\leq i\leq n$. By Lemma 3, $f$ is $\tau_{q,z}$-summable in
$F(z)$ if and only if $c=0$ and $a_{i,j}=0$ for all $i,j$ with $1\leq i\leq n$
and $1\leq j\leq m_{i}$.

###### Remark 1

Note that pseudo-residues are essentially different from residues in the
differential case, but not needed in the shift and $q$-shift cases.

##  3 Structure theorems

In this section, we present structure theorems for rational WZ-pairs in terms
of some special pairs. Throughout this section, we will assume that $K$ is an
algebraically closed field of characteristic zero and let
$\partial_{x}\in\\{D_{x},\Delta_{x},\Delta_{q,x}\\}$ and
$\partial_{y}\in\\{D_{y},\Delta_{y},\Delta_{q,y}\\}$.

We first consider the special case that $q\in K$ is a root of unity. Assume
that $m$ is the minimal positive integer such that $q^{m}=1$. For any $f\in
K(x,y)$, it is easy to show that $\tau_{q,y}(f)=f$ if and only if $f\in
K(x)(y^{m})$. Note that $K(x,y)$ is a finite algebraic extension of
$K(x)(y^{m})$ of degree $m$. In the following theorem, we show that WZ-pairs
in this special case are of a very simple form.

###### Theorem 3.1

Let $\partial_{x}\in\\{D_{x},\Delta_{x},\Delta_{q,x}\\}$ and $f,g\in K(x,y)$
be such that $\partial_{x}(f)=\Delta_{q,y}(g)$. Then there exist rational
functions $h\in K(x,y)$ and $a,b\in K(x,y^{m})$ such that $\partial_{x}(a)=0$
and

$f=\Delta_{q,y}(h)+a\quad\text{and}\quad g=\partial_{x}(h)+b.$

Moreover, we have $a\in K(y^{m})$ if $\partial_{x}\in\\{D_{x},\Delta_{x}\\}$
and $a\in K(x^{m},y^{m})$ if $\partial_{x}=\Delta_{q,x}$.

###### Proof

By Lemma 2.4 in ChenSinger2014 , any rational function $f\in K(x,y)$ can be
decomposed as

$f=\Delta_{q,y}(h)+a,\quad\text{where~{}$h\in K(x,y)$ and~{}$a\in
K(x)(y^{m})$}.$ (5)

Moreover, $f$ is $\tau_{q,y}$-summable in $K(x,y)$ if and only if $a=0$. Then

$\partial_{x}(f)=\Delta_{q,y}(\partial_{x}(h))+\partial_{x}(a).$

Note that $\partial_{x}(a)\in K(x)(y^{m})$, which implies that
$\partial_{x}(a)=0$ because $\partial_{x}(f)$ is $\tau_{q,y}$-summable in
$K(x,y)$. Then $\Delta_{q,y}(g)=\Delta_{q,y}(\partial_{x}(h))$. So
$g=\partial_{x}(h)+b$ for some $b\in K(x,y^{m})$. This completes the proof.
$\Box$

From now on, we assume that $q$ is not a root of unity. We will investigate
WZ-pairs in three different cases according to the choice of the pair
$(\partial_{x},\partial_{y})$.

###  3.1 The differential case

In the continuous setting, we consider WZ-pairs with respect to
$(D_{x},D_{y})$, i.e., the pairs of the form $(f,g)$ with $f,g\in K(x,y)$
satisfying $D_{x}(f)=D_{y}(g)$.

###### Definition 2

A WZ-pair $(f,g)$ with respect to $(D_{x},D_{y})$ is called a _log-derivative_
pair if there exists nonzero $h\in K(x,y)$ such that $f=D_{y}(h)/h$ and
$g=D_{x}(h)/h$.

The following theorem shows that any WZ-pair in the continuous case is a
linear combination of exact and log-derivative pairs, which was first proved
by Christopher in Christopher1999  and then extended to the multivariate case
in Zoladek1998 ; ChenThesis2011 .

###### Theorem 3.2

Let $f,g\in K(x,y)$ be such that $D_{x}(f)=D_{y}(g)$. Then there exist
rational functions $a,b_{1},\ldots,b_{n}\in K(x,y)$ and nonzero constants
$c_{1},\ldots,c_{n}\in K$ such that

$f=D_{y}(a)+\sum_{i=1}^{n}c_{i}\frac{D_{y}(b_{i})}{b_{i}}\quad\text{and}\quad
g=D_{x}(a)+\sum_{i=1}^{n}c_{i}\frac{D_{x}(b_{i})}{b_{i}}.$

###### Proof

The proof in the case when $K$ is the field of complex numbers can be found in
(Christopher1999, , Theorem 2) and in the case when $K$ is any algebraically
closed field of characteristic zero can be found in (ChenThesis2011, , Theorem
4.4.3).

###### Corollary 1

The quotient space
${\mathcal{P}}_{(D_{x},D_{y})}/{\mathcal{E}}_{(D_{x},D_{y})}$ is spanned over
$K$ by the set

$\\{(f,g)+{\mathcal{E}}_{(D_{x},D_{y})}\mid\text{$f,g\in K(x,y)$ such that
$(f,g)$ is a log-derivative pair}\\}.$

###### Remark 2

A differentiable function $h(x,y)$ is said to be hyperexponential over
${\mathbb{C}}(x,y)$ if $D_{x}(h)=fh$ and $D_{y}(h)=gh$ for some
$f,g\in{\mathbb{C}}(x,y)$. The above theorem enables us to obtain the
multiplicative structure of hyperexponential functions, i.e., any
hyperexponential function $h(x,y)$ can be written as
$h=\exp(a)\cdot\prod_{i=1}^{n}b_{i}^{c_{i}}$ for some
$a,b_{i}\in{\mathbb{C}}(x,y)$ and $c_{i}\in{\mathbb{C}}$.

###  3.2 The ($q$)-shift case

In the discrete setting, we consider WZ-pairs with respect to
$(\partial_{x},\partial_{y})$ with
$\partial_{x}\in\\{\Delta_{x},\Delta_{q,x}\\}$ and
$\partial_{y}\in\\{\Delta_{y},\Delta_{q,y}\\}$, i.e., the pairs of the form
$(f,g)$ with $f,g\in K(x,y)$ satisfying $\partial_{x}(f)=\partial_{y}(g)$.

Let $\theta_{x}\in\\{{\sigma}_{x},\tau_{q,x}\\}$ and
$\theta_{y}\in\\{{\sigma}_{y},\tau_{q,y}\\}$. For any nonzero
$m\in{\mathbb{Z}}$, $\theta_{x}^{m}$ is also an automorphism on $K(x,y)$ that
fixes $K(y)$, i.e., for any $f\in K(x,y)$, $\theta_{x}^{m}(f)=f$ if and only
if $f\in K(y)$. The ring of polynomials in $\theta_{x}$ and $\theta_{y}$ over
$K$ is denoted by $K[\theta_{x},\theta_{y}]$. For any
$p=\sum_{i,j}c_{i,j}\theta_{x}^{i}\theta_{y}^{j}\in K[\theta_{x},\theta_{y}]$
and $f\in K(x,y)$, we define the action $p\bullet
f=\sum_{i,j}c_{i,j}\theta_{x}^{i}(\theta_{y}^{j}(f))$. Then $K(x,y)$ can be
viewed as a $K[\theta_{x},\theta_{y}]$-module. Let
$G=\langle\theta_{x},\theta_{y}\rangle$ be the free abelian group generated by
$\theta_{x}$ and $\theta_{y}$. Let $f\in K(x,y)$ and $H$ be a subgroup of $G$.
We call the set $\\{c\theta(f)\mid c\in K\setminus\\{0\\},\theta\in H\\}$ the
_$H$ -orbit_ at $f$, denoted by $[f]_{H}$. Two elements $f,g\in K(x,y)$ are
said to be $H$-equivalent if $[f]_{H}=[g]_{H}$, denoted by $f\sim_{H}g$. The
relation $\sim_{H}$ is an equivalence relation. A rational function $f\in
K(x,y)$ is said to be _$(\theta_{x},\theta_{y})$ -invariant_ if there exist
$m,n\in{\mathbb{Z}}$, not all zero, such that
$\theta_{x}^{m}\theta_{y}^{n}(f)=f$. All possible
$(\theta_{x},\theta_{y})$-invariant rational functions have been completely
characterized in AbramovPetkovsek2002a ; Ore1930 ; Sato1990 ; CFFJ2012 ;
CCFFL2015 . We summarize the characterization as follows.

###### Proposition 1

Let $f\in K(x,y)$ be $(\theta_{x},\theta_{y})$-invariant, i.e., there exist
$m,n\in{\mathbb{Z}}$, not all zero, such that
$\theta_{x}^{m}\theta_{y}^{n}(f)=f$. Set $\bar{n}=n/\gcd(m,n)$ and
$\bar{m}=m/\gcd(m,n)$. Then

  * 1.

if $\theta_{x}={\sigma}_{x}$ and $\theta_{y}={\sigma}_{y}$, then
$f=g(\bar{n}x-\bar{m}y)$ for some $g\in K(z)$;

  * 2.

if $\theta_{x}=\tau_{q,x}$, $\theta_{y}=\tau_{q,y}$, then
$f=g(x^{\bar{n}}y^{-\bar{m}})$ for some $g\in K(z)$;

  * 3.

if $\theta_{x}={\sigma}_{x}$, $\theta_{y}=\tau_{q,y}$, then $f\in K(x)$ if
$m=0$, $f\in K(y)$ if $n=0$, and $f\in K$ if $mn\neq 0$.

We introduce a discrete analogue of the log-derivative pairs.

###### Definition 3

A WZ-pair $(f,g)$ with respect to $(\partial_{x},\partial_{y})$ is called a
_cyclic_ pair if there exists a $(\theta_{x},\theta_{y})$-invariant $h\in
K(x,y)$ such that

$f=\frac{\theta_{x}^{s}-1}{\theta_{x}-1}\bullet h\quad\text{and}\quad
g=\frac{\theta_{y}^{t}-1}{\theta_{y}-1}\bullet h,$

where $s,t\in{\mathbb{Z}}$ are not all zero satisfying that
$\theta_{x}^{s}(h)=\theta_{y}^{t}(h)$.

In the above definition, we may always assume that $s\geq 0$. Note that for
any $n\in{\mathbb{Z}}$ we have

$\frac{\theta_{y}^{n}-1}{\theta_{y}-1}=\left\\{\begin{array}[]{ll}\sum_{j=0}^{n-1}\theta_{y}^{j},&\hbox{$n\geq
0$;}\\\ -\sum_{j=1}^{-n}\theta_{y}^{-j},&\hbox{$n<0$.}\end{array}\right.$

###### Example 2

Let $a\in K(y)$ and $b\in K(x)$. Then both $(a,0)$ and $(0,b)$ are cyclic by
taking $h=a,s=1,t=0$ and $h=b,s=0,t=1$, respectively. Let $p=2x+3y$. Then the
pair $(f,g)$ with

$f=\frac{1}{p}+\frac{1}{{\sigma}_{x}(p)}+\frac{1}{{\sigma}_{x}^{2}(p)}\quad\text{and}\quad
g=\frac{1}{p}+\frac{1}{{\sigma}_{y}(p)}$

is a cyclic WZ-pair with respect to $(\Delta_{x},\Delta_{y})$.

Let $V_{0}=K(x)[y]$ and $V_{m}$ be the set of all rational functions of the
form $\sum_{i=1}^{I}{a_{i}}/{b_{i}^{m}}$, where
$m\in{\mathbb{Z}}_{+},a_{i},b_{i},\in K(x)[y]$,
$\deg_{y}(a_{i})<\deg_{y}(b_{i})$ and the $b_{i}$’s are distinct irreducible
polynomials in the ring $K(x)[y]$. By definition, the set $V_{m}$ forms a
subspace of $K(x,y)$ as a vector spaces over $K(x)$. By the irreducible
partial fraction decomposition, any $f\in K(x,y)$ can be uniquely decomposed
into $f=f_{0}+f_{1}+\cdots+f_{n}$ with $f_{i}\in V_{i}$ and so
$K(x,y)=\bigoplus_{i=0}^{\infty}V_{i}$. The following lemma shows that the
space $V_{m}$ is invariant under certain shift operators.

###### Lemma 4

Let $f\in V_{m}$ and $P\in K(x)[\theta_{x},\theta_{y}]$. Then $P(f)\in V_{m}$.

###### Proof

Let $f=\sum_{i=1}^{I}a_{i}/b_{i}^{m}$ and
$P=\sum_{i,j}p_{i,j}\theta_{x}^{i}\theta_{y}^{j}$. For any
$\theta=\theta_{x}^{i}\theta_{y}^{j}$ with $i,j,k\in{\mathbb{Z}}$,
$\theta(b_{i})$ is still irreducible and
$\deg_{y}(\theta(a_{i}))<\deg_{y}(\theta(b_{i}))$. Then all of the simple
fractions
${p_{i,j}\theta_{x}^{i}\theta_{y}^{j}(a_{i})}/{\theta_{x}^{i}\theta_{y}^{j}(b_{i})^{n}}$
appearing in $P(f)$ are proper in $y$ and have irreducible denominators. If
some of denominators are the same, we can simplify them by adding the
numerators to get a simple fraction. After this simplification, we see that
$P(f)$ can be written in the same form as $f$, so it is in $V_{m}$. $\Box$

###### Lemma 5

Let $p$ be a monic polynomial in $K(x)[y]$. If
$\theta_{x}^{m}(p)=c\theta_{y}^{n}(p)$ for some $c\in K(x)$ and
$m,n\in{\mathbb{Z}}$ with $m,n$ being not both zero, then $c\in K$.

###### Proof

Write $p=\sum_{i=0}^{d}p_{i}y^{i}$ with $p_{i}\in K(x)$ and $p_{d}=1$. Then

$\theta_{x}^{m}(p)=\sum_{i=0}^{d}\theta_{x}^{m}(p_{i})y^{i}=c\sum_{i=0}^{d}p_{i}\theta_{y}^{n}(y^{i})=c\theta_{y}^{n}(p).$

Comparing the leading coefficients in $y$ yields $c=1$ if
$\theta_{y}={\sigma}_{y}$ and $c=q^{-nd}$ if $\theta_{y}=\tau_{q,y}$. Thus,
$c\in K$ because $q\in K$. $\Box$

###### Lemma 6

Let $f\in K(x,y)$ be a rational function of the form

$f=\frac{a_{0}}{b^{m}}+\frac{a_{1}}{\theta_{x}(b^{m})}+\cdots+\frac{a_{n}}{\theta_{x}^{n}(b^{m})},$

where $m\in{\mathbb{Z}}_{+},n\in{\mathbb{N}},a_{0},a_{1},\ldots,a_{n}\in
K(x)[y]$ with $a_{n}\neq 0$ and $b\in K(x)[y]$ are such that
$\deg_{y}(a_{i})<\deg_{y}(b)$ and $b$ is an irreducible and monic polynomial
in $K(x)[y]$ such that $\theta_{x}^{i}(b)$ and $\theta_{x}^{j}(b)$ are not
$\theta_{y}$-equivalent for all $i,j\in\\{0,1,\ldots,n\\}$ with $i\neq j$. If
$\theta_{x}(f)-f=\theta_{y}(g)-g$ for some $g\in K(x,y)$, then $(f,g)$ is
cyclic.

###### Proof

By a direct calculation, we have

$\theta_{x}(f)-f=\frac{\theta_{x}(a_{n})}{\theta_{x}^{n+1}(b^{m})}-\frac{a_{0}}{b^{m}}+\frac{\theta_{x}(a_{0})-a_{1}}{\theta_{x}(b^{m})}+\cdots+\frac{\theta_{x}(a_{n-1})-a_{n}}{\theta_{x}^{n}(b^{m})}.$

If $\theta_{x}(f)-f=\theta_{y}(g)-g$ for some $g\in K(x,y)$, then all of the
$\theta_{y}$-residues at distinct $\theta_{y}$-orbits of $\theta_{x}(f)-f$ are
zero by residue criteria in Section 2. Since
$b^{m},\theta_{x}(b^{m}),\ldots,\theta_{x}^{n}(b^{m})$ are in distinct
$\theta_{y}$-orbits, $\theta_{x}^{n+1}(b^{m})$ must be $\theta_{y}$-equivalent
to one of them. Otherwise, we get

$a_{0}=0,\quad\theta_{x}(a_{0})-a_{1}=0,\quad\ldots,\quad\theta_{x}(a_{n-1})-a_{n}=0,\quad\text{and}\quad\theta_{x}(a_{n})=0.$

Since $\theta_{x}$ is an automorphism on $K(x,y)$, we have
$a_{0}=a_{1}=\cdots=a_{n}=0$, which contradicts the assumption that $a_{n}\neq
0$. If $\theta_{x}^{n+1}(b^{m})$ is $\theta_{y}$-equivalent to
$\theta_{x}^{i}(b^{m})$ for some $0<i\leq n$, so is
$\theta_{x}^{n+1-i}(b^{m})$, which contradicts the assumption. Thus,
$\theta_{x}^{n+1}(b^{m})=c\theta_{y}^{t}(b^{m})$ for some $c\in
K(x)\setminus\\{0\\}$ and $t\in{\mathbb{Z}}$. By Lemma 5, we have $c\in
K\setminus\\{0\\}$. A direct calculation leads to

$\displaystyle\theta_{x}(f)-f$
$\displaystyle{=}\frac{\theta_{x}(a_{n})}{\theta_{x}^{n+1}(b^{m})}{-}\frac{a_{0}}{b^{m}}+\sum_{i=1}^{n}\frac{\theta_{x}(a_{i-1})-a_{i}}{\theta_{x}^{i}(b^{m})}{=}\frac{\theta_{x}(a_{n})}{c\theta_{y}^{t}(b^{m})}{-}\frac{a_{0}}{b^{m}}+\sum_{i=1}^{n}\frac{\theta_{x}(a_{i-1})-a_{i}}{\theta_{x}^{i}(b^{m})}$
$\displaystyle{=}\frac{\theta_{y}^{-t}\theta_{x}(a_{n}/c)-a_{0}}{b^{m}}+\sum_{i=1}^{n}\frac{\theta_{x}(a_{i-1})-a_{i}}{\theta_{x}^{i}(b^{m})}+\theta_{y}(u)-u$

for some $u\in K(x,y)$ using the formula (2). By the residue criteria, we then
get $a_{0}=\theta_{y}^{-t}\theta_{x}(a_{n}/c),a_{1}=\theta_{x}(a_{0}),\ldots,$
and $a_{n}=\theta_{x}(a_{n-1})$. This implies that
$\theta_{x}^{n+1}(a_{0})=c\theta_{y}^{t}(a_{0})$ and
$a_{i}=\theta_{x}^{i}(a_{0})$ for $i\in\\{1,\ldots,n\\}$. So
$f=\frac{\theta_{x}^{n+1}-1}{\theta_{x}-1}\bullet h$ with $h=a_{0}/b^{m}$,
which leads to

$\theta_{x}(f)-f=\theta_{x}^{n+1}(h)-h=\theta_{y}^{t}(h)-h=\theta_{y}(g)-g\quad\text{with}\quad
g=\frac{\theta_{y}^{t}-1}{\theta_{y}-1}\bullet h.$

Thus, $(f,g)$ is a cyclic WZ-pair. $\Box$

The following theorem is a discrete analogue of Theorem 3.2.

###### Theorem 3.3

Let $f,g\in K(x,y)$ be such that $\partial_{x}(f)=\partial_{y}(g)$. Then there
exist rational functions $a,b_{1},\ldots,b_{n}\in K(x,y)$ such that

$f=\partial_{y}(a)+\sum_{i=1}^{n}\frac{\theta_{x}^{s_{i}}-1}{\theta_{x}-1}\bullet
b_{i}\quad\text{and}\quad
g=\partial_{x}(a)+\sum_{i=1}^{n}\frac{\theta_{y}^{t_{i}}-1}{\theta_{y}-1}\bullet
b_{i},$

where for each $i\in\\{1,\ldots,n\\}$ we have
$\theta_{x}^{s_{i}}(b_{i})=\theta_{y}^{t_{i}}(b_{i})$ for some
$s_{i}\in{\mathbb{N}}$ and $t_{i}\in{\mathbb{Z}}$ with $s_{i},t_{i}$ not all
zero.

###### Proof

By Abramov’s reduction and its $q$-analogue, we can decompose $f$ as

$f=\partial_{y}(a)+c+\sum_{j=1}^{J}f_{j}\quad\text{
with~{}$f_{j}=\sum_{i=1}^{I}\sum_{\ell=0}^{L_{i,j}}\frac{a_{i,j,\ell}}{\theta_{x}^{\ell}(b_{i}^{j})}$},$

where $a\in K(x,y),c\in K(x)$, and $a_{i,j,\ell}b_{i}\in K(x)[y]$ such that
$c=0$ if $\theta_{y}={\sigma}_{y}$, $\deg_{y}(a_{i,j,\ell})<\deg_{y}(b_{i})$,
and the $b_{i}$’s are irreducible and monic polynomials belonging to distinct
$G$-orbits where $G=\langle\theta_{x},\theta_{y}\rangle$. Moreover,
$\theta_{x}^{\ell_{1}}(b_{i}^{j})$ and $\theta_{x}^{\ell_{2}}(b_{i}^{j})$ are
in distinct $\theta_{y}$-orbits if $\ell_{1}\neq\ell_{2}$. By applying Lemma 4
to the equation $\theta_{x}(f)-f=\theta_{y}(g)-g$, we get that
$\theta_{x}(c)-c$ is $\theta_{y}$-summable and so is $\theta_{x}(f_{j})-f_{j}$
for each multiplicity $j\in\\{1,\ldots,J\\}$. By residue criteria for
$\theta_{y}$-sumability and the assumption that the $b_{i}$’s are in distinct
$\langle\theta_{x},\theta_{y}\rangle$-orbits, we have $\theta_{x}(c)-c=0$ and
for each $i\in\\{1,\ldots,I\\}$, the rational function
$f_{i,j}:=\sum_{\ell=0}^{L_{i,j}}{a_{i,j,\ell}}/{\theta_{x}^{\ell}(b_{i}^{j})}$
is either equal to zero or there exists $g_{i,j}\in K(x,y)$ such that
$\theta_{x}(f_{i,j})-f_{i,j}=\theta_{y}(g_{i,j})-g_{i,j}$. Then
$(f_{i,j},g_{i,j})$ is cyclic by Lemma 6 for every $i,j$ with $1\leq i\leq I$
and $1\leq j\leq J$. So the pair $(f,g)$ can be written as

$(f,g)=(\partial_{y}(a),\partial_{x}(a))+(c,0)+\sum_{i=1}^{I}\sum_{j=1}^{J}(f_{i,j},g_{i,j}).$

This completes the proof. $\Box$

###### Corollary 2

The quotient space
${\mathcal{P}}_{(\partial_{x},\partial_{y})}/{\mathcal{E}}_{(\partial_{x},\partial_{y})}$
is spanned over $K$ by the set

$\\{(f,g)+{\mathcal{E}}_{(\partial_{x},\partial_{y})}\mid\text{$f,g\in K(x,y)$
such that $(f,g)$ is a cyclic pair}\\}.$

###  3.3 The mixed case

In the mixed continuous-discrete setting, we consider the rational WZ-pairs
with respect to $(\theta_{x}-1,D_{y})$ with
$\theta_{x}\in\\{{\sigma}_{x},\tau_{q,x}\\}$.

###### Lemma 7

Let $p$ be an irreducible and monic polynomial in $K(x)[y]$. Then for any
nonzero $m\in{\mathbb{Z}}$, we have either $\gcd(p,\theta_{x}^{m}(p))=1$ or
$p\in K[y]$.

###### Proof

Since $\theta_{x}$ is an automorphism on $K(x,y)$, $\theta_{x}^{i}(p)$ is
irreducible in $K(x)[y]$ for any $i\in{\mathbb{Z}}$. If
$\gcd(p,\theta_{x}^{m}(p))\neq 1$, then $\theta_{x}^{m}(p)=cp$ for some $c\in
K(x)$. Write $p=\sum_{i=0}^{d}p_{i}y^{i}$ with $p_{i}\in K(x)$ and $p_{d}=1$.
Then $\theta_{x}^{m}(p)=cp$ implies that $\theta_{x}^{m}(p_{i})=cp_{i}$ for
all $i$ with $0\leq i\leq d$. Then $c=1$ and $p_{i}\in K$ for all $i$ with
$0\leq i\leq d-1$. So $p\in K[y]$. $\Box$

The structure of WZ-pairs in the mixed setting is as follows.

###### Theorem 3.4

Let $f,g\in K(x,y)$ be such that $\theta_{x}(f)-f=D_{y}(g)$. Then there exist
$h\in K(x,y)$, $u\in K(y)$ and $v\in K(x)$ such that

$f=D_{y}(h)+u\quad\text{and}\quad g=\theta_{x}(h)-h+v.$

###### Proof

By the Ostrogradsky–Hermite reduction, we decompose $f$ into the form

$f=D_{y}(h)+\sum_{i=1}^{I}\sum_{j=0}^{J_{i}}\frac{a_{i,j}}{\theta_{x}^{j}(b_{i})},$

where $h\in K(x,y)$ and $a_{i,j},b_{i}\in K(x)[y]$ with $a_{i,J_{i}}\neq 0$,
$\deg_{y}(a_{i,j})<\deg_{y}(b_{i})$ and $b_{i}$ being irreducible and monic
polynomials in $y$ over $K(x)$ such that the $b_{i}$’s are in distinct
$\theta_{x}$-orbits. By a direct calculation, we get

$\theta_{x}(f)-f=D_{y}(\theta_{x}(h)-h)+\sum_{i=1}^{I}\left(\frac{\theta_{x}(a_{i,J_{i}})}{\theta_{x}^{J_{i}+1}(b_{i})}-\frac{a_{i,0}}{b_{i}}+\sum_{j=1}^{J_{i}}\frac{\theta_{x}(a_{i,j-1})-a_{i,j}}{\theta_{x}^{j}(b_{i})}\right).$

For all $i,j$ with $1\leq i\leq I$ and $0\leq j\leq J_{i}+1$, the
$\theta_{x}^{j}(b_{i})$’s are irreducible and monic polynomials in $y$ over
$K(x)$. We first show that for each $i\in\\{1,\ldots,I\\}$, we have $b_{i}\in
K[y]$. Suppose that there exists $i_{0}\in\\{1,\ldots,I\\}$, $b_{i_{0}}\notin
K[y]$. Then $\gcd(\theta_{x}^{m}(b_{i_{0}}),b_{i_{0}})=1$ for any nonzero
$m\in{\mathbb{Z}}$ by Lemma 7. Since $\theta_{x}(f)-f$ is $D_{y}$-integrable
in $K(x,y)$, we have $\theta_{x}(a_{i_{0},J_{i_{0}}})=0$ by Lemma 1. Then
$a_{i_{0},J_{i_{0}}}=0$, which contradicts the assumption that
$a_{i,J_{i}}\neq 0$ for all $i$ with $1\leq i\leq I$. Since $b_{i}\in K[y]$,
$f$ can be written as

$f=D_{y}(h)+\sum_{i=1}^{I}\frac{a_{i}}{b_{i}},\quad\text{where
$a_{i}:=\sum_{j=0}^{J_{i}}a_{i,j}$.}$

Since $\theta_{x}(f)-f$ is $D_{y}$-integrable in $K(x,y)$ and since

$\theta_{x}(f)-f=D_{y}(\theta_{x}(h)-h)+\sum_{i=1}^{I}\frac{\theta_{x}(a_{i})-a_{i}}{b_{i}},$

we have $\theta_{x}(a_{i})-a_{i}=0$ for each $i\in\\{1,\ldots,I\\}$ by Lemma
1. This implies that $a_{i}\in K(y)$ and $f=D_{y}(h)+u$ with
$u=\sum_{i=1}^{I}a_{i}/b_{i}\in K(y)$. Since $\theta_{x}(f)-f=D_{y}(g)$, we
get $D_{y}(g-(\theta_{x}(h)-h))=0$. Then $g=\theta_{x}(h)-h+v$ for some $v\in
K(x)$. $\Box$

###### Corollary 3

The quotient space
${\mathcal{P}}_{(\theta_{x}-1,D_{y})}/{\mathcal{E}}_{(\theta_{x}-1,D_{y})}$ is
spanned over $K$ by the set

$\\{(f,g)+{\mathcal{E}}_{(\theta_{x}-1,D_{y})}\mid\text{$f\in K(y)$ and $g\in
K(x)$}\\}.$

##  4 Conclusion

We have explicitly described the structure of rational WZ-pairs in terms of
special pairs. With structure theorems, we can easily generate rational WZ-
pairs, which solves Problem 1 in the rational case completely. For the future
research, the next direction is to solve the problem in the cases of more
general functions. Using the terminology of Gessel in Gessel1995 , a
hypergeometric term $F(x,y)$ is said to be a _WZ-function_ if there exists
another hypergeometric term $G(x,y)$ such that $(F,G)$ is a WZ-pair. In the
scheme of creative telescoping, $(F,G)$ being a WZ-pair with respect to
$(\partial_{x},\partial_{y})$ is equivalent to that $\partial_{x}$ being a
telescoper for $F$ with certificate $G$. Complete criteria for the existence
of telescopers for hypergeometric terms and their variants are known
Abramov2003 ; ChenHouMu2005 ; CCFFL2015 . With the help of existence criteria
for telescopers, one can show that $F(x,y)$ can be decomposed as the sum
$F=\partial_{y}(H_{1})+H_{2}$ with $H_{1},H_{2}$ being hypergeometric terms
and $H_{2}$ is of proper form (see definition in WilfZeilberger1992 ;
Gessel1995 ) if $F$ is a WZ-function. So it is promising to apply the ideas in
the study of the existence problem of telescopers to explore the structure of
WZ-pairs.

Acknowledgment. I would like to thank Prof. Victor J.W. Guo and Prof. Zhi-Wei
Sun for many discussions on series for special constants, (super)-congruences
and their $q$-analogues that can be proved using the WZ method. I am also very
grateful to Ruyong Feng and Rong-Hua Wang for many constructive comments on
the earlier version of this paper. I also thank the anonymous reviewers for
their constructive and detailed comments.

## References

  * [1] Sergei A. Abramov.  The rational component of the solution of a first order linear recurrence relation with rational right hand side.  Ž. Vyčisl. Mat. i Mat. Fiz., 15(4):1035–1039, 1090, 1975\.
  * [2] Sergei A. Abramov.  Indefinite sums of rational functions.  In ISSAC ’95: Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, pp. 303–308, New York, NY, USA, 1995. ACM.
  * [3] Sergei A. Abramov.  When does Zeilberger’s algorithm succeed?  Adv. in Appl. Math., 30(3):424–441, 2003.
  * [4] Sergei A. Abramov and Marko Petkovšek.  On the structure of multivariate hypergeometric terms.  Adv. in Appl. Math., 29(3):386–411, 2002.
  * [5] Tewodros Amdeberhan.  Faster and faster convergent series for $\zeta(3)$.  Electron. J. Combin., 3(1):Research Paper 13, approx. 2, 1996.
  * [6] David H. Bailey, Jonathan M. Borwein, and David M. Bradley.  Experimental determination of Apéry-like identities for $\zeta(2n+2)$.  Experiment. Math., 15(3):281–289, 2006.
  * [7] Nayandeep Deka Baruah, Bruce C. Berndt, and Heng Huat Chan.  Ramanujan’s series for $1/\pi$: a survey.  Amer. Math. Monthly, 116(7):567–587, 2009.
  * [8] Gustav C. Bauer.  Von den Coefficienten der Reihen von Kugelfunctionen einer Variablen.  J. Reine Angew. Math., 56:101–121, 1859.
  * [9] Jonathan Borwein, David Bailey, and Roland Girgensohn.  Experimentation in mathematics: Computational paths to discovery.  A K Peters/CRC Press, 2004.
  * [10] Alin Bostan and Manuel Kauers.  The complete generating function for Gessel walks is algebraic.  Proceedings of the American Mathematical Society, 138(9):3063–3078, 2010.
  * [11] Manuel Bronstein.  Symbolic Integration I: Transcendental Functions.  Springer-Verlag, Berlin, second edition, 2005.
  * [12] Shaoshi Chen.  Some Applications of Differential-Difference Algebra to Creative Telescoping.  PhD Thesis, Ecole Polytechnique LIX, 2011.
  * [13] Shaoshi Chen, Frédéric Chyzak, Ruyong Feng, Guofeng Fu, and Ziming Li.  On the existence of telescopers for mixed hypergeometric terms.  J. Symbolic Comput., 68(part 1):1–26, 2015.
  * [14] Shaoshi Chen, Ruyong Feng, Guofeng Fu, and Jin Kang.  Multiplicative decompositions of multivariate $q$-hypergeometric terms.  J. Systems Sci. Math. Sci., 32(8):1019–1032, 2012.
  * [15] Shaoshi Chen and Michael F. Singer.  Residues and telescopers for bivariate rational functions.  Adv. in Appl. Math., 49(2):111–133, 2012.
  * [16] Shaoshi Chen and Michael F. Singer.  On the summability of bivariate rational functions.  J. Algebra, 409:320–343, 2014.
  * [17] William Y. C. Chen, Qing-Hu Hou, and Yan-Ping Mu.  Applicability of the $q$-analogue of Zeilberger’s algorithm.  J. Symbolic Comput., 39(2):155–170, 2005.
  * [18] William Y. C. Chen, Qing-Hu Hou, and Doron Zeilberger.  Automated discovery and proof of congruence theorems for partial sums of combinatorial sequences.  J. Difference Equ. Appl., 22(6):780–788, 2016.
  * [19] Colin Christopher.  Liouvillian first integrals of second order polynomial differential equations.  Electron. J. Differential Equations, 49:1–7, 1999.
  * [20] Thomas Dreyfus, Charlotte Hardouin, Julien Roques, and Michael F. Singer.  On the nature of the generating series of walks in the quarter plane.  Invent. Math., Jan 2018, https://doi.org/10.1007/s00222-018-0787-z.
  * [21] Shalosh B. Ekhad and Doron Zeilberger.  A WZ proof of Ramanujan’s formula for $\pi$.  In Geometry, analysis and mechanics, pages 107–108. World Sci. Publ., River Edge, NJ, 1994.
  * [22] Ira M. Gessel.  Finding identities with the WZ method.  J. Symb. Comput., 20(5-6):537–566, November 1995.
  * [23] Jesús Guillera.  Some binomial series obtained by the WZ-method.  Adv. in Appl. Math., 29(4):599–603, 2002.
  * [24] Jesús Guillera.  Generators of some Ramanujan formulas.  Ramanujan J., 11(1):41–48, 2006.
  * [25] Jesús Guillera.  Hypergeometric identities for 10 extended Ramanujan-type series.  Ramanujan J., 15(2):219–234, 2008.
  * [26] Jesús Guillera.  On WZ-pairs which prove Ramanujan series.  Ramanujan J., 22(3):249–259, 2010.
  * [27] Jesús Guillera.  WZ-proofs of “divergent” Ramanujan-type series.  In Advances in combinatorics, pages 187–195. Springer, Heidelberg, 2013.
  * [28] Victor J. W. Guo.  Some generalizations of a supercongruence of van Hamme.  Integral Transforms and Spec. Funct., (1):1–12, 2017.
  * [29] Victor J. W. Guo.  A $q$-analogue of a Ramanujan-type supercongruence involving central binomial coefficients.  J. of Math. Analysis and Applications, 458(1):590–600, 2018.
  * [30] Victor J. W. Guo.  A $q$-analogues of the (J.2) supercongruence of van Hamme.  To appear in J. of Math. Analysis and Applications, 2018\.
  * [31] Victor J. W. Guo and Ji-Cai Liu.  $q$-analogues of two Ramanujan-type formulas for $1/\pi$.  To appear in J. Difference Equ. Appl., 2018.
  * [32] Victor J. W. Guo and Wadim Zudilin.  Ramanujan-type formulae for $1/\pi$: $q$-analogues.  To appear in Integral Transforms Spec. Funct., https://doi.org/10.1080/10652469.2018.1454448, 2018.
  * [33] Charles Hermite.  Sur l’intégration des fractions rationnelles.  Ann. Sci. École Norm. Sup. (2), 1:215–218, 1872.
  * [34] Khodabakhsh Hessami Pilehrood and Tatiana Hessami Pilehrood.  Generating function identities for $\zeta(2n+2),\ \zeta(2n+3)$ via the WZ method.  Electron. J. Combin., 15(1): Research Paper 35, 9, 2008.
  * [35] Khodabakhsh Hessami Pilehrood and Tatiana Hessami Pilehrood.  Simultaneous generation for zeta values by the Markov-WZ method.  Discrete Math. Theor. Comput. Sci., 10(3):115–123, 2008.
  * [36] Khodabakhsh Hessami Pilehrood and Tatiana Hessami Pilehrood.  A $q$-analogue of the Bailey-Borwein-Bradley identity.  J. Symbolic Comput., 46(6):699–711, 2011.
  * [37] Qing-Hu Hou, Christian Krattenthaler, and Zhi-Wei Sun.  On $q$-analogues of some series for $\pi$ and $\pi^{2}$.  Preprint: arXiv:1802.01506, 2018.
  * [38] Qing-Hu Hou and Rong-Hua Wang.  An algorithm for deciding the summability of bivariate rational functions.  Adv. in Appl. Math., 64:31 – 49, 2015.
  * [39] Manuel Kauers, Christoph Koutschan, and Doron Zeilberger.  Proof of Ira Gessel’s lattice path conjecture.  Proc. Natl. Acad. Sci. USA, 106(28):11502–11505, 2009.
  * [40] Margo Kondratieva and Sergey Sadov.  Markov’s transformation of series and the WZ method.  Adv. in Appl. Math., 34(2):393–407, 2005.
  * [41] Christoph Koutschan, Manuel Kauers, and Doron Zeilberger.  Proof of George Andrews’s and David Robbins’s $q$-TSPP conjecture.  Proc. Natl. Acad. Sci. USA, 108(6):2196–2199, 2011.
  * [42] Zhi-Guo Liu.  Gauss summation and Ramanujan-type series for $1/\pi$.  International Journal of Number Theory, 08(02):289–297, 2012.
  * [43] Zhi-Guo Liu.  A $q$-extension of a partial differential equation and the Hahn polynomials.  Ramanujan J., 38(3):481–501, 2015.
  * [44] Ling Long.  Hypergeometric evaluation identities and supercongruences.  Pacific J. Math., 249(2):405–418, 2011.
  * [45] Mohamud Mohammed.  The $q$-Markov-WZ method.  Ann. Comb., 9(2):205–221, 2005.
  * [46] Mohamud Mohammed and Doron Zeilberger.  The Markov-WZ method.  Electron. J. Combin., 11(1):205–221, 2004.
  * [47] Eric Mortenson.  A $p$-adic supercongruence conjecture of van Hamme.  Proceedings of the American Mathematical Society, 136(12):4321–4328, 2008.
  * [48] Oystein Ore.  Sur la forme des fonctions hypergéométriques de plusieurs variables.  J. Math. Pures Appl. (9), 9(4):311–326, 1930.
  * [49] Mikhail Vasil’evich Ostrogradskiĭ.  De l’intégration des fractions rationnelles.  Bull. de la classe physico-mathématique de l’Acad. Impériale des Sciences de Saint-Pétersbourg, 4:145–167, 286–300, 1845\.
  * [50] Marko Petkovšek, Herbert S. Wilf, and Doron Zeilberger.  $A=B$.  A K Peters Ltd., Wellesley, MA, 1996.  With a foreword by Donald E. Knuth.
  * [51] John Riordan.  Combinatorial Identities, John Wiley & Sons, Inc., 1968.
  * [52] Mikio Sato.  Theory of prehomogeneous vector spaces (algebraic part)—the English translation of Sato’s lecture from Shintani’s note.  Nagoya Math. J., 120:1–34, 1990.  Notes by Takuro Shintani, Translated from the Japanese by Masakazu Muro.
  * [53] Xiaomin Sun.  Some Discussions on Three Kinds of WZ-equations.  Master thesis, Soochow University, April 2012.  Supervised by Xinrong Ma.
  * [54] Zhi-Wei Sun.  Super congruences and Euler numbers.  Sci. China Math., 54(12):2509–2535, 2011.
  * [55] Zhi-Wei Sun.  A refinement of a congruence result by van hamme and mortenson.  Illinois Journal of Mathematics, 56(3):967–979, 2012.
  * [56] Zhi-Wei Sun.  Conjectures involving arithmetical sequences.  in: Number Theory: Arithmetic in Shangri-La (eds., S. Kanemitsu, H. Li and J. Liu), Proc. 6th China-Japan Seminar (Shanghai, August 15-17, 2011), World Sci., Singapore, pages 244–258, 2013.
  * [57] Zhi-Wei Sun.  Products and sums divisible by central binomial coefficients.  Electron. J. Combin., 20(1):91–109(19), 2013.
  * [58] Zhi-Wei Sun.  Two $q$-analogues of Euler’s formula $\zeta(2)=\pi^{2}/6$.  Preprint: arXiv:arXiv:1802.01473, 2018.
  * [59] Akalu Tefera.  What is $\dots$ a Wilf-Zeilberger pair?  Notices Amer. Math. Soc., 57(4):508–509, 2010.
  * [60] Lucien van Hamme.  Some conjectures concerning partial sums of generalized hypergeometric series.  In $p$-adic functional analysis (Nijmegen, 1996), volume 192 of Lecture Notes in Pure and Appl. Math., pages 223–236. Dekker, New York, 1997.
  * [61] Herbert S. Wilf and Doron Zeilberger.  An algorithmic proof theory for hypergeometric (ordinary and “$q$”) multisum/integral identities.  Invent. Math., 108(3):575–633, 1992.
  * [62] Herbert S. Wilf and Doron Zeilberger.  Rational function certification of multisum/integral/“$q$” identities.  Bull. Amer. Math. Soc. (N.S.), 27(1):148–153, 1992.
  * [63] Doron Zeilberger.  Closed form (pun intended!).  In A tribute to Emil Grosswald: number theory and related analysis, volume 143 of Contemp. Math., pages 579–607. Amer. Math. Soc., Providence, RI, 1993.
  * [64] Henryk Zoladek.  The extended monodromy group and Liouvillian first integrals.  J. Dynam. Control Systems, 4(1):1–28, 1998.
  * [65] Wadim Zudilin.  More Ramanujan-type formulas for $1/\pi^{2}$.  Russian Math. Surveys, 62(3):634–636, 2007.
  * [66] Wadim Zudilin.  Ramanujan-type supercongruences.  J. Number Theory, 129(8):1848–1857, 2009.
  * [67] Wadim Zudilin.  Arithmetic hypergeometric series.  Russian Math. Surveys,, 66(2):369 C420, 2011.


$\gamma(\boldsymbol{b})\,=\,\frac{1}{2\sqrt{\frac{2(a_{1}^{2}\mu_{1}^{2}+a_{2}^{2}\mu_{2}^{2})^{3}(a_{1}^{2}b_{1}^{2}\mu_{1}^{2}+a_{2}^{2}b_{2}^{2}\mu_{2}^{2})}{8a_{1}^{8}b_{1}^{4}\mu_{1}^{8}+8a_{1}^{6}b_{1}^{2}a_{2}^{2}(b_{1}+b_{2})^{2}\mu_{1}^{6}\mu_{2}^{2}+a_{1}^{4}a_{2}^{4}(b_{1}+b_{2})^{2}(b_{1}^{2}+10b_{1}b_{2}+b_{2}^{2})\mu_{1}^{4}\mu_{2}^{4}+8a_{1}^{2}a_{2}^{6}b_{2}^{2}(b_{1}+b_{2})^{2}\mu_{1}^{2}\mu_{2}^{6}+8a_{2}^{8}b_{2}^{4}\mu_{2}^{8}}}}$
(190)

It is messy but straightforward to write the derivatives of $\gamma$ w.r.t.
$b_{1}$ and $b_{2}$ evaluated at $b_{1}=b_{2}=1$ (which gives $\zeta_{1}$ and
$\zeta_{2}$) to see that for any derivative of order $m\leq 8$ the above
yields $\zeta_{1}=\zeta_{2}$ and at $m=9$ one obtains,

$|\zeta_{1}|-|\zeta_{2}|\,=\,\frac{5670}{\|\boldsymbol{A}\boldsymbol{\mu}\|^{18}}(a_{1}a_{2}\mu_{1}\mu_{2})^{8}(a_{1}^{2}\mu_{1}^{2}-a_{2}^{2}\mu_{2}^{2})\,.$
(191)