% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theo}{Theorem}
\newtheorem{lem}[theo]{Lemma}
\newtheorem{coro}[theo]{Corollary}
\newtheorem{prop}[theo]{Proposition}
\newtheorem{fact}[theo]{Fact}
\newtheorem{observation}[theo]{Observation}
\newtheorem{claim}[theo]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theo]{Definition}
\newtheorem{exam}[theo]{Example}
\newtheorem{conjecture}[theo]{Conjecture}
\newtheorem{open}[theo]{Open Problem}
\newtheorem{problem}[theo]{Problem}
\newtheorem{question}[theo]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theo]{Remark}
\newtheorem{note}[theo]{Note}

\def\CT{\mathop{\mathrm{CT}}}
\newcommand\pa[1]{\partial_{ #1}}
\def\pax{\partial_x}
\def\res{\mathop{\mathrm{res}}}
\def\reseq{ \mathop{\equiv }_\mathrm{res}}
\def\rem{\mathrm{rem}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Residue reduced form of a rational function as an iterated Laurent series}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Guoce Xin \\ %\thanks{Supported by NASA grant ABC123.}\\
\small Department of mathematics\\[-0.8ex]
\small Capital Normal University\\[-0.8ex]
\small Beijing 100048, P.R. China\\
\small\tt guoce.xin@gmail.com\\
\and
Yue Zhou\thanks{Corresponding author}\\
\small School of Mathematics and Statistics\\[-0.8ex]
\small Central South University\\[-0.8ex]
\small Changsha 410075, P.R. China\\
\small\tt nkzhouyue@gmail.com
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Nov 20, 2012}{XX}\\
\small Mathematics Subject Classifications: 11Y60, 11R58}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
  Lipshitz showed that the diagonal of a D-finite power series is still D-finite, but his proof seems hard to implement. This paper may be regarded as the first step towards an efficient algorithm realizing Lipshitz's theory. We show that the idea of a reduced form may be a big saving for computing the D-finite functional equation. For the residue in one variable of a rational function, we develop an algorithm for computing its minimal algebraic functional equation.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} diagonal; residue; algebraic; D-finite
\end{abstract}

\section{Introduction}
\label{sec:in}

The following rational power series
\[A(x,y,z)= \frac{1} {\left({1-x}\right)^{2}\left({1-y}\right)^{2}
\left({1-z}\right)^{2}\left({1-y-x}\right)\left({1-z-y}\right)\left({1-z-x}\right)},\]
came from polyomino enumerations \cite{AH10}.
Recently the first author was asked to compute the diagonal $F(t)$ of $A(x,y,z)$, that is,
\[ F(t)=\sum_{n\ge 0} [x^n y^n z^n] A(x,y,z) t^n = \CT_{x,y} A(x,y,t/xy),\]
where $[x^n y^n z^n]$ means to take the coefficient of $x^n y^n z^n$, $\CT_{x,y}$ means to take the constant term in $x$ and $y$, and \( A(x,y,t/xy) \) is regarded as a power series in \( t \) with coefficients Laurent series in \( x \) and \( y \). This is our archetype.

The general theory of Lipshitz shows that the diagonal generating function $F(t)$ is D-finite \cite{L88}, which means that there exist polynomials $a_0(t),a_1(t),\dots,a_d(t)$ such that $a_d(t)\ne 0$ and
$$ a_d(t) F^{(d)}(t) +a_{d-1} F^{(d-1)}(t) + \cdots +a_0 F(t)=0.$$
However Lipshitz's proof seems to give too large a degree bound to efficiently deliver the desired D-finite functional equation.

In this paper we show how the idea of reduced form can be used to develop an efficient algorithm realizing Lipshitz theory, at least in some special cases. The basic idea is as follows. Suppose we need to compute the residue $\res_x Q(x,t)$.
Since the residue of a differential is $0$, we can deal with $\res_x \overline{Q}(x,t)$ instead where $\overline{Q}(x,t)=Q(x,t)-\pa x P(x,t)$ for a suitably chosen $P(x,t)$. Then $\overline{Q}(x,t)$ will have some nice minimal property leading to some nice consequences.

This idea works nicely when $Q(x,t)$ is a rational function (usually containing other variables), which is the main object of study in this paper. We use the field of iterated Laurent series of \cite{Xin04} to characterize the series expansion of $Q(x,t)$. See Section \ref{sec:ILS} for a brief description. Then the reduced form can be simplified further. As a consequence, a D-finite equation of small order for $\res_x Q(x,t)$ is easily constructed. It is also well-known that $\res_x Q(x,t)$ is in fact algebraic. We present an algorithm for computing the minimal algebraic functional equation for $\res_x Q(x)$ without using details of the roots of the denominator. As an example, we find that the diagonal generating function $F(t)$ is algebraic of degree $6$, with coefficients polynomials %\comment{GX: required change}
in $t$ of degree $61$.

Many combinatorial problems can be reduced to the computation of the residue in several variables of certain rational functions. Given a rational function, it is a hard problem even for deciding the nullity of its residue. Lipshitz's theorem applies, but it is clearly not economic to use D-finiteness to characterize rational functions. Thus our algorithm may be taken as the initial step before applying Lipshitz's theorem.
The potential for the idea of reduced form in the general case is discussed
in Section \ref{sec:potential}.




\section{Residue reduced form of a rational function}

Let \( K \) be a field of characteristic \( 0 \) and \( x \) a variable. Given a rational function \( Q(x)\in K(x) \), define \( Q_1(x) \) to be residue equivalent to \( Q(x) \) if there exists \( R(x) \) such that \( Q(x)=Q_1(x)+\pax R(x) \), where \( \pax \) is short for \( \frac{\partial}{\partial x} \). Denote
\[ Q(x) \reseq Q_1(x) \Leftrightarrow   Q(x)=Q_1(x)+\pax R(x) \textrm{ for some } R(x)\in K(x).\]

There are existing algorithms for finding \( Q_1(x) \) and \( R(x) \) simultaneously with \( Q_1(x) \) minimal in some sense. Such a representation is useful when integrating \( Q(x) \). In the context of residue computation, we are only interested in finding the minimal \( Q_1(x) \), since the residue of \( \pax R(x) \) is always \( 0 \), which explains the term residue equivalent. The following result is well-known.

\begin{prop}\label{p-RRF}
  Suppose \( Q(x)\in K(x) \) has denominator \( D_1(x)^{r_1}\cdots D_k(x)^{r_k} \), where the \( D_i(x)\in K[x] \) are irreducible. Then there exist
\( p_1(x),\dots, p_k(x)\in K[x] \) with \( \deg p_i(x) <\deg D_i(x) \) such that
\[Q(x) \reseq \frac{p_1(x)}{D_1(x)} +\cdots + \frac{p_k(x)}{D_k(x)}.\]
The right hand side is called the RRF (short for residue reduced form) of \( Q(x) \).
\end{prop}
\begin{proof}
  By the partial fraction decomposition, we may write
\[Q(x) = P(x) + \frac{N_1(x)}{D_1(x)^{r_1}}+ \cdots +\frac{N_k}{D_k(x)^{r_k}},\]
where \( P(x) \) is a polynomial and \( N_i(x) \) is a polynomial of degree less than \( r_i \deg D_i(x) \).
It is clear that
\( P(x)\reseq 0 \) since \( \int P(x) dx  \) is a polynomial. Thus it is sufficient to show that

\begin{align}
  \label{e-D-r}\frac{N_i(x)}{D_i(x)^{r_i}} \reseq \frac{p_i(x)}{D_i(x)}
\end{align}
holds for some \( p_i(x)\in K[x] \).
We prove this by induction on \( r_i \). Equation \eqref{e-D-r} clearly holds when \( r_i=1 \). Assume \eqref{e-D-r} holds for \( r_i<r \). Consider
\[ \pax \frac{L(x)}{D_i(x)^{r-1}} = \frac{\pax L(x)}{D_i(x)^{r-1}}-\frac{(r-1) L(x) \pax D_i(x)}{D_i(x)^{r}} .\]
Choose \( L(x)=\rem( \frac{1}{r-1} N_i(x) \alpha(x), D_i(x)) \), where $\rem(A,B)$
denotes the reminder of $A$ divided by $B$
and \( \alpha(x) \pax D_i(x)+\beta(x) D_i(x)=1 \). Then  \( N_i(x)-(r-1) L(x) \pax D_i(x) =0 \pmod{D_i(x)} \). This implies that
\[ \frac{N_i(x)}{D_i(x)^r} + \pax \frac{L(x)}{D_i(x)^{r-1}} = \frac{\overline{N}(x)}{D_i(x)^{r'}}\]
for some \( \overline{N}(x) \) and \( r'<r \). Then by the induction hypothesis we have
\[ \frac{N_i(x)}{D_i(x)^r} \reseq  \frac{\overline{N}(x)}{D_i(x)^{r'}} \reseq \frac{p_i(x)}{D_i(x)}.\]
This completes the proof.

\end{proof}
%\begin{remark}
%The $r'$ in the above proof can only be $r-1$.
%Since \( N_i(x)-(r-1) L(x) \pax D_i(x) =0 \pmod{D_i(x)} \) and
%$\deg(N_i(x)),\deg(L(x))<\deg(D_i(x))$, if follows that
%$N_i(x)-(r-1) L(x) \pax D_i(x) =0$ or $N_i(x)-(r-1) L(x) \pax D_i(x) =a D_i(x)$ for some $a \in K$.
%Therefore
%
%\[ \frac{N_i(x)}{D_i(x)^r} + \pax \frac{L(x)}{D_i(x)^{r-1}} = \frac{N_i(x)-(r-1) L(x) \pax D_i(x)}{D_i(x)^{r}}+\frac{\pax L(x)}{D_i(x)^{r-1}}
%=\frac{\overline{N}(x)}{D_i(x)^{r-1}}.\]
%
%\end{remark}

Here is an outline of the algorithm for RRF.
\begin{center}
{\large\textbf{RRF algorithm}}
\end{center}

\emph{INPUT}: A rational function $Q(x)$.

\emph{OUTPUT}: The RRF of $Q(x)$ in $x$.
\begin{enumerate}
\item As in the proof, write $Q(x)$ as:
$Q(x)=P(x)+\sum_{i=1}^k\frac{N_i(x)}{D_i(x)^{r_i}}$.

\item For $i=1,\ldots,k$ do:

\ \ \ \ \ let $r:=r_i$, $P_i(x):=N_i(x)$, and find $\alpha(x)$ so that $\alpha(x) \pax D_i(x)+\beta(x) D_i(x)=1$; %GX: I put \alpha(x) earlier

\ \ \ \ \ while $r>1$ do:

\ \ \ \ \ \ \ \ \ \ find $P_i'(x)$ such that
\[ \frac{P_i'(x)}{D_i(x)^{r'}} = \frac{P_i(x)}{D_i(x)^r} + \pax \frac{L(x)}{D_i(x)^{r-1}},\]
\ \ \ \ \ \ \ \ \ \ where $L(x):= \rem( \frac{1}{r-1} P_i(x) \alpha(x), D_i(x))$;

\ \ \ \ \ \ \ \ \ \ let $r:=r'$, $P_i(x):=P_i'(x)$.

\ \ \ \ \ $p_i(x):=\rem(P_{i}(x),D_i(x))$.

\item Return $\frac{p_1(x)}{D_1(x)} +\cdots + \frac{p_k(x)}{D_k(x)}$.
\end{enumerate}
\qed



\section{Residue reduced form in a field of iterated Laurent series\label{sec:ILS}}
Let \( \mathcal{K}=K((x_n))\cdots ((x_1)) \) be the field of iterated Laurent series and let \( x \) be one of the variables.
Then a rational function \( Q(x) \) has a unique series expansion in \( \mathcal K \)
and hence the residue \( \res_x Q(x) \) is defined to be the residue of the series
expansion of \( Q(x) \). It should be noted that \( Q(x) \) may have different residue
in different field of iterated Laurent series, so we must specify the working field
when taking residues.  This treatment works for almost all residue calculations
since \( \mathcal{K} \) is maximal in some sense.
In particular \( \mathcal{K} \) includes the field \( K(x_1,\dots,x_n) \)
of rational functions as a subfield. See \cite{Xin04} for more details.

Our ultimate goal is to compute or characterize the residue \( \res_x Q(x) \) of a rational function \( Q(x) \). We need some basic facts for elements in \( \mathcal K \). The field \( \mathcal{K} \) defines a total order \( 0<x_1\ll x_2\ll\cdots \ll x_n <1\) on the variables, which induces a total group order on the group of monomials. Here we only need the following two facts.

\begin{enumerate}
\item  A monomial \( M=x_1^{k_1}\cdots x_n^{k_n}\ne  1 \) is said to be \emph{small} if \( k_1=\cdots=k_s=0 \), \( k_{s+1}>0 \), otherwise it is said to be \emph{large}. The initial term of a Laurent polynomial is the term with the largest monomial.

    For example, in the field $K((x))((y))((t))$, the initial term of $x+x^2y+t/x$ is $x$.

\item If \( F\in \mathcal K \) and the initial term of \( 1-F \) is \( 1 \), then \( (1-F)^{-1} \) and \( \log (1-F)^{-1} \) are also in \( \mathcal K \) and we have the following series expansion:
 \begin{align*}
   \frac{1}{1-F} = \sum_{m\ge 0} F^m, \quad \mathrm{ and }\quad  \log \frac{1}{1-F} = \sum_{m\ge 1} \frac{1}{m} F^m.
 \end{align*}
%%Suppose a polynomial \( P \) is written as \( P=cM+P' \) with initial term \( cM \). Then the expansion of \( P^{-1} \) is given by
%%\[ \frac{1}{cM+P'} = \frac{1}{cM(1+P'/cM)} = \sum_{n\geq 0} (-P')^n(cM)^{-n-1}.\]
\end{enumerate}

Let \( D(x) \) be an irreducible polynomial of degree \( d \) with initial term \( cM \). Then \( D(x) \) is said to be \emph{crucial} if \( 1\le \deg_x cM \le d-1 \). Our main result is the following.
\begin{theo}\label{t-ILSRRF}
 Suppose a rational function \( Q(x) \) has denominator \( D_1(x)^{r_1} \cdots D_k(x)^{r_k} \). Then there exist
\( p_i(x) \) and a constant \( C \) free of \( x \) such that it holds in \( \mathcal K \) that
\[  Q(x) \reseq \frac{C}{x}+ \sum_{i} \frac{p_i(x)}{D_i(x)},\]
where the sum ranges over all crucial irreducible factors \( D_i \), and \( \deg_x p_i(x)\le \deg_x D_i(x)-2 \). The right hand side is called the ILSRRF (Iterated Laurent series residue reduced form) of \( Q(x) \).
\end{theo}
\begin{proof}
By Proposition \ref{p-RRF}, we may assume the RRF of \( Q(x) \) is given by
\[
Q (x) = \frac{p_1(x)}{D_1(x)}+\cdots + \frac{p_k(x)}{D_k(x)}.
\]

By linearity, it is sufficient to consider \( p(x)/D(x) \). Let \( cM \) be the initial term of \( D(x) \), and denote by \( d=\deg_x D(x) \), and \( \ell=\deg_x cM \). Write \( D(x)=a_0+a_1x+\cdots +a_d x^d \), and \( p(x)=b_0+b_1x+\cdots +b_{d-1} x^{d-1} \). Note that \( a_0\ne 0 \) unless \( D(x)=x \), since \( D(x) \) is irreducible. We can simplify by the following three cases.

i) If \( \ell=0 \), then
\[\frac{p(x)}{D(x)} = \frac{p(x)}{a_0(1+a_1x/a_0+ \cdots +a_d x^d/a_0)}= \sum_{n\ge 0} \frac{p(x)}{a_0} (-1)^n
(a_1x/a_0+ \cdots +a_d x^d/a_0)^n \]
has only nonnegative powers in \( x \). It follows that \( \res_x p(x)/D(x)=0 \).

ii) If \( \ell=d \), then
\begin{align*}
  \frac{p(x)}{D(x)} &=\frac{p(x)}{a_d x^d (1+\frac{a_{d-1}}{a_dx}+ \cdots +\frac{a_0}{a_d x^d})} \\
&=\sum_{n\ge 0} (\frac{b_0}{a_d x^d}+\frac{b_1}{a_d x^{d-1}}+\cdots + \frac{b_{d-1}}{a_dx}) (-1)^n
(\frac{a_{d-1}}{a_dx}+ \cdots +\frac{a_0}{a_d x^d})^n .
\end{align*}
It follows that \( \res_x p(x)/D(x) = b_{d-1}/a_d  . \)

iii) If \( 0<\ell<d \), then \( D(x) \) is crucial and we do not have an expression as simple as above. However, since the initial term of \( D(x)/a_\ell x^\ell \) is \( 1 \), \( \log \frac{D(x)}{a_\ell x^\ell} \in \mathcal{K} \). Therefore
\[ \res_x \pax \log \frac{D(x)}{a_\ell x^\ell} = \res_x \frac{\pax D(x)}{D(x)} - \ell=0.\]
Thus if we write
\[ \frac{p(x)}{D(x)} -\frac{b_{d-1}}{da_d}  \frac{\pax D(x)}{D(x)} =\frac{\overline{p}(x)}{D(x)},\]
then \( \overline p (x) \) has degree no more than \( d-2 \) and it follows that
\[ \res_x \frac{p(x)}{D(x)}  =\res_x \frac{\overline p(x)}{D(x)} + \frac{\ell b_{d-1}}{d a_d}.\]
\end{proof}

Based on the proof, we give an algorithm for computing the ILSRRF
of a rational function.
\begin{center}
{\large \textbf{ILSRRF algorithm}}
\end{center}

\emph{INPUT:} A rational function $Q(x)$ and a working field $K((x_n))\cdots ((x_1))$,
$x$ is one of the variables.

\emph{OUTPUT:} The ILSRRF of $Q(x)$ in $x$.

\begin{enumerate}
\item By the RRF algorithm, let the RRF of $Q(x)$ be
\[
Q (x) = \frac{p_1(x)}{D_1(x)}+\cdots + \frac{p_k(x)}{D_k(x)}.
\]


\item Let $C:=0$;

  for $i=1,\ldots,k$ do:

\ \ \ \ \     $d:=\deg_x D_i(x)$;

\ \ \ \ \     $[x^{d}]D_i(x):=a_d$;

\ \ \ \ \     $[x^{d-1}]p_i(x):=b_{d-1}$.

\ \ \ \ \ find the initial term $cM$ of $D_i(x)$ and let $l:=\deg_x cM$;

\ \ \ \ \ if $l= d$, then $C:=C+b_{d-1}/(a_dx)$;

\ \ \ \ \ else if $l>0$, then $C:=C+p_i(x)/D_i(x)-b_{d-1}\pax D_i(x)/(da_dD_i(x))+lb_{d-1}/(da_dx)$.

\item Return $C$.
\end{enumerate}
\qed

\section{The D-finite functional equation}
We follow the notations of the last section. Let \( t \) be another variable. An iterated Laurent series \( G(t)\in \mathcal K \) is said to be D-finite if there exist polynomials \( a_0(t),a_1(t),\dots, a_d(t)  \) such that
 \[a_d \pa{ t}^d G(t)+\cdots + a_1 \pa{t} G(t) +a_0 G(t)=0,\]
where \( a_d \) is nonzero. The smallest such \( d \) is called the order of the D-finiteness of \( G(t) \). This slightly extends Stanley's concept of D-finite generating functions. See \cite{Stan99} for more information on the concepts of D-finite and P-recursive.

A direct consequence of Theorem \ref{t-ILSRRF} is the following.
\begin{theo}\label{t-Dfinite}
Let \( Q(x,t) \) be a rational function with irreducible denominator factors \( D_1,\dots, D_k \). Then the residue \( \res_x Q(x,t) \) in \( \mathcal K \) is D-finite of order at most \( 1+\sum_i (\deg_x D_i -1) \), where the sum ranges over all crucial \( D_i \).
\end{theo}
\begin{proof}
Assume the crucial \( D_i \)'s are \( D_1,\dots, D_s \). Write \( G(t)=\res_x Q(x,t) \). Let \( \mathcal{L} \) be the linear space spanned by \( x^{-1} \) and \( \{ x^{i_j}/ D_i(x,t): 1\le i\le s,\  0\le i_j \le \deg_x D_i(x,t) -2\} \), where the coefficients are rational functions free of \( x \). Then \( \dim \mathcal L =d:=1+ \sum_{i=1}^s (\deg_x D_i(x,t)-1) \).

By Theorem \ref{t-ILSRRF}, there exists \( Q_0(x,t)\in \mathcal L \) such that \( G(t)=\res_x Q_0(x,t) \). Recursively define \( Q_i(x,t) \) to be the ILSRRF of \( \pa{t} Q_{i-1}(x,t) \). Then it is clear that
\[\frac{\partial^i}{\partial t^i} G(t)= \res_x Q_i(x,t), \text{ and }  Q_i(x,t)\in \mathcal L.\]
Then by the method of undetermined coefficients we can find the \( a_i \)'s not all zero  such that
\[ a_0 Q_0(x,t)+a_1 Q_1(x,t) \cdots +a_d Q_d(x,t)=0,\]
which implies the D-finiteness of \( G(t) \) through taking residues.
\end{proof}

Theorem \ref{t-Dfinite} guarantees the existence of an annihilating operator \( L=a_d \pa{t}^d +\cdots +a_1 \pa t +a_0 \) for \( \res_x Q(x,t) \), i.e., \( L \res_x Q(x,t)=0 \). Suppose the minimal annihilating operator is \( M \). It is not hard to show that \( M \) must be a right factor of \( L \). Thus to find \( M \), we need to search for all right factors of \( L \). This is hard since factorization for differential operators is hard, due to the noncommutative relation \( \pa t t =1+t \pa t \).


\section{The algebraic functional equation \label{sec:alg}}
We first recall some known results.
Let \( K \) be a field. An element \( \alpha \) is algebraic over \( K \) if there is a polynomial \( p(x)\in K[x] \) such that \( p(\alpha)=0. \) Such a polynomial of minimal degree is called the minimal polynomial (we do not need the monic condition).  Assume \( p(x) \) is the minimal polynomial of \( \alpha \) and \( \deg p(x)=d \). Then it is clear that \( p(x) \) is irreducible and \( K(\alpha) \) is isomorphic to \( K[x]/\langle p(x) \rangle \). Thus when regarded as a \( K \)-linear space, \( K(\alpha) \) has the canonical basis \( \{ 1,\alpha, \dots, \alpha^{d-1} \} \), and hence has dimension \( d \).  A direct consequence is the following.

\begin{lem}\label{lem-rat}
  Suppose \( \alpha \) is algebraic of degree \( d \). Then for any rational function  \( R(x) \), \( R(\alpha) \) is algebraic of degree at most \( d \).
\end{lem}
\begin{proof}
Define \( P_0(x)=1 \), and define \( P_i(x) \) with degree less than \( d \) to be the representation of \( R^i(\alpha) \) as \( P_i(\alpha) \)  for \( i=0,1,\dots, d \). Then
\( P_0(x), \dots, P_d(x) \) are \( K \)-linearly dependent. By the method of undetermined coefficients, we can find the \( a_i\in K \) not all zero so that \( a_0P_0(x)+a_1 P_1(x)+\cdots +a_d P_d(x)=0. \) Then \( q(x)=a_0+a_1x+\cdots a_d x^d \) satisfies \( q(P(\alpha))=0 \). This completes the proof.
\end{proof}


From the above proof that we can easily get an algorithm for computing an algebraic
functional equation for $R(\alpha)$.

\begin{center}
{\large \textbf{AFE algorithm}}
\end{center}

\emph{INPUT:} A rational function $R(x)$ and an algebraic functional equation $Eq(x)$ for $\alpha$
with degree $d$.

\emph{OUTPUT:} An algebraic functional equation for $R(\alpha)$.

\begin{enumerate}
\item Let $P(\alpha)$ be the result of rationalizing of the denominator of $R(\alpha)$.

\item By the method of undetermined coefficients, find the \( a_i\in K \) not all zero
such that  \( a_0+a_1 P(\alpha)+\cdots +a_d P(\alpha)^d=0. \)


\item Return $a_0+a_1x+\cdots a_d x^d$.
\end{enumerate}
\qed

Note that in the AFE algorithm, we do not need the explicit form of $\alpha$.

The following result is stronger than Lemma \ref{lem-rat}.
\begin{lem}\label{lem-rat-strong}
  Suppose \( \alpha \) is algebraic of degree \( d \). Let \( R(x) \) be a rational function and $m(x)$ be the minimal polynomial of
  \( R(\alpha) \). Then $\deg m(x)$ divides \( d \).
\end{lem}
\begin{proof}
Denote by $b=\deg m(x)$. Suppose $M(x)$ is the minimal polynomial of $\alpha$ and $M(x)$ has roots $\{\alpha_i\}_{1\le i\le d}$. We claim that $m(x)$ is also the minimal polynomial of $R(\alpha_i)$ for all $i$. This is because $m(R(\alpha_i))=0$ if and only if
$m(R(x)) \equiv 0 \pmod{M(x)}$.

Consider $q(x)=(x-R(\alpha_1))\cdots (x-
R(\alpha_d))$. Since $q(x)$ is symmetric in the $\alpha_i$, it follows that $q(x)\in K[x]$ and hence $m(x)$ divides $q(x)$. On the other hand, each irreducible factor of $q(x)$ must vanish at $R(\alpha_i)$ for some $i$ and therefore be divisible by $m(x)$. It follows that $q(x)$ must be equal to $m(x)^{d/b}$ up to a constant factor.
\end{proof}



Another useful fact is that the set of algebraic elements form a field. In particular, we need the following.
\begin{lem}\label{l-alg-add}
If \( \alpha \) and \( \beta \) are both algebraic then \( \alpha+\beta \) is algebraic.
\end{lem}
\begin{proof}
Let \( \gamma=\alpha+\beta \). Suppose the minimal polynomials of \( \alpha \) and \( \beta \) are \( p(x) \) and \( q(x) \) with \( \deg p(x)=d \) and \( \deg q(x)=\ell \). We provide two ways to find \( P(x)\in K[x] \) such that \( P(\gamma)=0 \).

The classical way:  It is clear that \( \gamma^n=(\alpha+\beta)^n \) is a linear combination of \( \alpha^i\beta^j \), where \( 0\le i< d, 0\le j < \ell \). Therefore \( \{ (\alpha+\beta)^n : 0\le n \le d\ell \} \) is linearly dependent, and hence we can find \( P(x) \in K[x] \) of degree at most \( d\ell \) such that \( P(\gamma)=0 \) by the method of undetermined coefficients.

An alternative way: Construct \( P(x)=\prod_{i=1}^d \prod_{j=1}^\ell (x-\alpha_i-\beta_j) \), where the \( \alpha_i \) are all the roots of \( p(x) \) and the \( \beta_j \) are all the roots of \( q(x) \). Then it is clear that \( P(\alpha+\beta)=0 \), and \( P(x) \) is symmetric in the \( \alpha_i \)'s and in the \( \beta_j \)'s and hence belongs to \( K[x] \). It is a matter of how to rewrite \( P(x) \) without the \( \alpha_i \) and \( \beta_j \). We can write \( P(x)=p(x-\beta_1)\cdots p(x-\beta_\ell) \). Indeed, if we let \( \overline{p}(z)=p(x-z) \) then the roots of \( \overline{p}(z) \) are \( x-\alpha_i \), and \( P(x) \) is just the resultant of \( \overline{p}(z) \) and \( q(z) \), which has a determinant representation of size \( d+\ell \).
\end{proof}

\begin{center}
{\large \textbf{AFE2 algorithm }}
\end{center}

\emph{INPUT:} An algebraic functional equation $p(x)$ for $\alpha$ and an  algebraic functional equation $q(x)$ for $\beta$.

\emph{OUTPUT:} A minimal polynomial of $\alpha+\beta$.

\begin{enumerate}
\item Let $R(x)$ be the resultant of $p(x-z)$ and $q(z)$ with respect to $z$.

\item Find an irreducible factor $P(x)$ of $R(x)$ such that $P(\alpha+\beta)=0$.

\item Return $P(x)$.
\end{enumerate}
\qed


\begin{remark}\label{rem-alg-2}
  It should be noted that if \( \beta_i=r_i(\beta) \) for some polynomials \( r_i(x) \),
  then \( P(x)= p(x-r_1(\beta))\cdots p(x-r_\ell(\beta)) \),
  whose standard representation contains no \( \beta \).
  %This always happens if \( \ell=2 \).
  For example, if \( \ell=2 \) and we know that one root $\beta_1$ of $q(x)$ is of the form $c_1+c_2\sqrt{\beta}$, then $P(x)$ can be written as $p(x-c_1-c_2\sqrt{\beta})p(x-c_1+c_2\sqrt{\beta})$, which contains no $\sqrt{\beta}$ after simplification.
\end{remark}

\begin{remark}\label{rem-alg-sym}
  Let \( \alpha_i, i=1,\dots, d \) be the roots of \( p(x) \). We claim that \( \gamma=\alpha_1+\cdots +\alpha_s \) is algebraic of degree at most \( \binom{d}{s} \). Let \( P(x)=\prod_{|S|=s}\big(x-\sum_{i\in S} \alpha_i \big) \). Then \( P(\gamma)=0 \), \( \deg P(x)= \binom{d}{s} \), and \( P(x) \) is symmetric in the \( \alpha_i \) and hence belongs to \( K[x] \).
\end{remark}

The following theorem slightly generalizes the well-known result that the diagonal of a rational generating function in two variables is algebraic.
\begin{theo}\label{thm-min}
For any rational function \( Q(x) \) in \( \mathcal K \), the residue of \( Q(x) \) in \( x \) is algebraic, and there is an algorithm to find the minimal polynomial of \( \res_x Q(x) \).
\end{theo}
\begin{proof}
The proof is classical. Here we address how to find the minimal polynomial of \( \res_x Q(x) \).

Assume the ILSRRF of \( Q(x) \) is a linear combination of \( p(x)/D(x) \) as described in Theorem \ref{t-ILSRRF}. Since linear combinations of algebraic elements are algebraic, it is sufficient to show that \( \res_x p(x)/D(x) \) is algebraic.

In some field extension, \( D(x) \) can be factored as \( a_d(x-\alpha_1)\cdots (x-\alpha_d) \). We have the following partial fraction decomposition:
\begin{align*}
   \frac{p(x)}{D(x)} &= \sum_{i=1}^d \frac{p(x)}{D(x)/(x-\alpha_i)}\Big|_{x=\alpha_i} \cdot \frac{1}{x-\alpha_i}\\
                     &= \sum_{i=1}^d \frac{p(\alpha_i)} {\pax D(\alpha_i)} \cdot \frac{1}{x-\alpha_i}.
\end{align*}
Suppose the initial term of \( D(x) \) is \( cM \) with \( s=\deg_x cM \). By renaming the \( \alpha_i \)'s we may assume  \( \alpha_i/x \) is small for \( i=1,2,\dots,r \) and \( \alpha_i/x \) is large for \( i=r+1,\dots, d \). Then we have
 \[ \res_x \frac{p(x)}{D(x)} = \sum_{i=1}^r \frac{p(\alpha_i)}{\pax D(\alpha_i)}.\]

By the AFE algorithm, we can find \( P_i(x)\in K[x] \) of degree at most \( d \) such that \( P_i( \frac{p(\alpha_i)}{\pax D(\alpha_i)})=0 \). It is clear that \( P_i(x)=P_j(x) \), and therefore by finding \( r \) we can apply  Remark \ref{rem-alg-sym} to find \( \overline{P}(x) \) having \( \res_x \frac{p(x)}{D(x)} \) as a root.

We need not compute \( \alpha_i \) to get the value of \( r \). Indeed we must have \( r=s \). With the condition given above, we can write
\[D(x)= (-1)^{d-s} a_d x^s \alpha_{r+1}\cdots \alpha_d (1-\alpha_1/x)\cdots (1-\alpha_s/x) (1-x/\alpha_{s+1}) \cdots (1-x/\alpha_d),\]
where each factor in parenthesis has \( 1 \) as the initial term. It follows that the initial term of \( D(x) \) must have degree \( r \) in \( x \), and hence \( r=s \).

Finally, by the AFE2 algorithm we can find a polynomial \( A(z) \) having \( \res_x Q(x) \) as a root. By checking for all irreducible factors of \( A(z) \), we can find the minimal polynomial.
\end{proof}
%For those \( D(x) \) of degree \( 2 \), we can have explicit expression by the quadratic formula.
\begin{remark}\label{rem-sumroot}
 The following fact will be used in our algorithm.
 Since $\deg p(x)\leq d-2$, we have
 $$  \sum_{i=1}^d \frac{p(\alpha_i)}{\pax D(\alpha_i)}%=\res_{x=\infty} \frac{p(x)}{D(x)}
 = \frac{[x^{d-1}] p(x)}{[x^d] D(x)} =0.$$
If we take $R(x)=p(x)/\pax D(x)$ in the proof of Lemma \ref{lem-rat-strong}, then we deduce that $[x^{b-1}] m(x)=0$.
\end{remark}

Here is an outline of the algorithm for finding the minimal polynomial,
suppose the working field is $\mathbb{C}((x))((t))$.
\begin{center}
{\large \textbf{MP algorithm}}
\end{center}

\emph{INPUT:} A rational function $Q(x)$ in \( \mathcal K \).

\emph{OUTPUT:} The minimal polynomial of $\res_x Q(x)$.

\begin{enumerate}
\item  By the ILSRRF algorithm,
let the ILSRRF of $\res_x Q(x)$ with respect to $x$ be
    \begin{align*}
    \res_x Q(x) \reseq C+ \sum_{i=1}^k \res_x \frac{p_i(x)}{D_i(x)}.
    \end{align*}

\item Find the initial term $cM_i(x)$ of each $D_i(x)$, and let $l_i:=\deg_x cM_i(x)$; then $D_i(x)$ has $l_i$ small roots, and
    \[\res_x \frac{p_i(x)}{D_i(x)}=\sum_{j=1}^{l_i} \frac{p_{i}(\alpha_j)}{\pax D_{i}(\alpha_j)},\]
    where the $\alpha_j(j=1,\ldots,l_i)$ are the small roots of $D_i(x)$.

\item For $i=1,\ldots,k$ do:

\ \ \ \ \ let $\deg D_i(x)=d_i$;
 find \( P_i(Z)\in K[Z] \)  such that \( P_i( \frac{p_i(\alpha_1)}{\pax D(\alpha_1)})=0 \) by the AFE algorithm;
%and let $\deg P_i(Z)=r$;
%\textbf{{ZY: I state that $\deg P_i(Z)=r$ to avoid $[a^{d_i}]P_i(Z)=0$}. GX: I find a problem here. I thought
%that $r$ must be equal to $d$. It would be good to have an example for $r<d$. I think it should be true that the roots of
%$m(x)$ divides evenly for small $\alpha_i$. That is the multiset $\{R(\alpha_1),\dots, R(\alpha_s)\}$ has each element appears $sr/d$ times.
%I do not know if this is correct. If correct, the computation will decrease faster. We can choose to forget this problem.
% There also seems to have
%a index confliction.}

\ \ \ \ \ if $l_i=1$, then take $F_i(Z):=P_i(Z)$;

\ \ \ \ \ else if $1<l_i\leq d_i/2$, let $R(Z):=P_i(Z)$;
 for $j=1,\ldots,l_i-1$, do:
let $R(Z)$ be the resultant of $R(Z-y)$ and $P_i(y)$ with respect to $y$;
 find an irreducible factor $F_i(Z)$ of $R(Z)$ such that
$F_i(\res_x \frac{p_i(x)}{D_i(x)})=0$;

\ \ \ \ \ else if $d_i/2<l_i\leq d_i-1$, let $R(Z):=P_i(Z)$;
 for $j=1,\ldots,d_i-l_i-1$, do:
let $R(Z)$ be the resultant of $R(Z-y)$ and $P_i(y)$ with respect to $y$;
%let $a=-\frac{[Z^{r-1}]P_i(Z)}{[Z^{r}]P_i(Z)}$ \textbf{$a=0$ by the remark} and
by Remark \ref{rem-sumroot} we can take $R(Z)=R(-Z)$;
find an irreducible factor $F_i(Z)$ of $R(Z)$ such that
$F_i(\res_x \frac{p_i(x)}{D_i(x)})=0$;

%\ \ \ \ \ else if $l_i=d_i-1$, let $a=-\frac{[Z^{d_i-1}]P_i(Z)}{[Z^{d_i}]P_i(Z)}$, then take $F_i(x):=P_i(a-Z)$???;

\ \ \ \ \ for all the cases, $F_i(Z)$ is an algebraic functional equation for $\res_x \frac{p_i(x)}{D_i(x)}$.

\item Recursively apply the AFE2 algorithm to $C$ and $F_1(Z),\ldots,F_k(Z)$ to get the minimal polynomial of $\res_x Q(x)$.

\end{enumerate}
\qed
%\comment{we need only deal with the case $l_i\le d_i/2$, for otherwise we can use the fact $\alpha_1+\cdot +\alpha_{d_i}\in K$. Please make correction accordingly.}

We conclude this section by giving three examples. The residues can be interpreted
as certain lattice paths in the plane. The degree of the algebraic functional equations for these residues
are lower than estimated. Our working field is $\mathbb{C}((x))((t))$.

\begin{exam}\label{examran1}
Consider the residue:
$$F(t)=\res_x  \frac{1}{{x}\left( 1-{\frac {t}{{x}^{2}}}-{x}^{4}t \right) }
=\res_x {\frac {x}{{x}^{2}-t-{x}^{6}t}}.$$
Because the denominator ${x}^{2}-t-{x}^{6}t$
has initial term $x^2$, then it has two small roots. By Remark \ref{rem-alg-sym},
the residue is algebraic of degree at most 15. But by the MP algorithm,
we obtain the following algebraic functional equation of  degree 3 for $F(t)$.
$$1+3\,Z+\left( 27\,{t}^{3}-4 \right) {Z}^{3}.$$
\end{exam}

\begin{exam}\label{examran2}
Consider the residue:
$$F(t)=\res_x   \frac{1}{x\left( 1-{\frac {t}{x}}-xt-{\frac {t}{{x}^{2}}}-{x}^{2}t \right) }
=\res_x {\frac {x}{{x}^{2}-xt-{x}^{3}t-t-{x}^{4}t}}.$$
Because the denominator ${x}^{2}-xt-{x}^{3}t-t-{x}^{4}t$
has initial term $x^2$, then it has two small roots. By Remark \ref{rem-alg-sym},
the residue is algebraic of order at most 6. But by the MP algorithm,
we obtain the following algebraic functional equation of  degree 4 for $F(t)$.
$$ \left( 4+9\,t \right)  \left( 4\,t-1 \right) ^{2}{Z}^{4}-2\, \left( 4
\,t-1 \right)  \left( 3\,t-2 \right) {Z}^{2}+t.$$
\end{exam}

\begin{exam}\label{examran3}
Consider the residue:
$$F(t)=\res_x  \frac{1}{{x}\left( 1-{\frac {{t}^{3}}{{
x}^{2}}}-{\frac {{t}^{4}}{{x}^{2}}}-{x}^{2}t -{x}^{2}{t}^{2}\right)}
=\res_x {\frac {x}{{x}^{2}+{x}^{4}t-{x}^{4}{t}^{2}-{t}^{3}-{t}^{4}}}.
$$
Because the denominator ${x}^{2}+{x}^{4}t-{x}^{4}{t}^{2}-{t}^{3}-{t}^{4}$
has initial term $x^2$, then it has two small roots. By Remark \ref{rem-alg-sym},
the residue is algebraic of order at most 6. But by the MP algorithm,
we obtain the following algebraic functional equation of  degree 2 for $F(t)$.
$$1+ \left( 2\,{t}^{3}+2\,{t}^{2}-1 \right)  \left( 2\,{t}^{3}+2\,{t}^{2
}+1 \right) {Z}^{2}.$$
\end{exam}


\section{The archetype}

Let $A(x,y,z)$ be as in Section \ref{sec:in}, and
let \( B(x,y,t)=A(x,y,t/xy) \). Then we need to compute
\begin{align*}
F(t)&=\res_{x,y} \frac{B(x,y,t)}{xy}  \\
&= \res_{x,y} \frac{1} {xy\left({1-x}\right)^{2}\left({1-y}\right)^{2}\left({1-\frac{t}{xy}}\right)^{2}\left({1-y-x}\right)
\left({1-\frac{t}{xy}-y}\right)\left({1-\frac{t}{xy}-x}\right)}.
\end{align*}
Our working field is \( \mathbb{C}((x))((y))((t)) \).

We eliminate \( y \) first. Compute the ILSRRF with respect to \( y \). The result is

 \[\res_y \frac{B(x,y,t)}{xy} =Q(x,t) -\res_y \frac{x^{3}} {\left({1-x}\right)^{2}t^{2}\left({-t+{x}^{2}-{x}^{3}}\right)\left({-t+xy-x{y}^{2}}\right)},\]
where \( Q(x,t) \) is a complicated rational function, whose ILSRRF with respect to \( x \) is given by
\begin{multline*}
  Q(x,t) \reseq 2\frac{1-6\,t+10\,{t}^{2}} {\left({1-4\,t}\right)t^{4}\left({x-t-{x}^{2}}\right)}
-\frac{1} {3}\frac{2-2\,x-22\,t+19\,tx+47\,{t}^{2}-26\,{t}^{2}x} {t^{4}\left({1-8\,t}\right)\left({x-t-2\,{x}^{2}+{x}^{3}}\right)}\\
-\frac{1} {3}\frac{2\,x-3\,t-19\,tx+21\,{t}^{2}+26\,{t}^{2}x} {t^{4}\left({1-8\,t}\right)\left({-t+{x}^{2}-{x}^{3}}\right)}
-\frac{2} {3}\frac{1-12\,t+42\,{t}^{2}-95\,{t}^{3}+51\,{t}^{4}-48\,{t}^{5}-2\,{t}^{6}} {t^{4}\left({1-t}\right)^{4}x \left({1-8\,t}\right)}.
\end{multline*}

The remaining residue in \( y \) is computed as follows.
\begin{align*}
  \res_y \frac{1}{\left({-t+xy-x{y}^{2}}\right)} &= \frac{1}{x-2xY} = \frac{1}{x \sqrt{1-4t/x}},
\end{align*}
where \( Y \) is the unique small root of \( -t+xy-x{y}^{2} \) for \( y \) given by
\[ Y= \frac{1-\sqrt{1-4t/x}}{2} = \frac{t}{x} +\cdots .\]

Similar argument gives
\[ \res_x \frac{1}{\left({x-t-{x}^{2}}\right)} = \frac{1}{1-2X}=\frac{1}{\sqrt{1-4t}},\]
where \( X= \frac{1-\sqrt{1-4t}}{2}=t+\cdots \).

In summary, \( F(t) \) is equal to \( B_1+B_2+B_3+B_4 \), where
\begin{align*}
  B_1&= -\frac{2} {3}\frac{1-12\,t+42\,{t}^{2}-95\,{t}^{3}+51\,{t}^{4}-48\,{t}^{5}-2\,{t}^{6}} {t^{4}\left({1-t}\right)^{4} \left({1-8\,t}\right)}+ 2\frac{1-6\,t+10\,{t}^{2}} {\left({1-4\,t}\right)t^{4}\sqrt{1-4t}},\\
B_2&=\res_x
-\frac{1} {3}\frac{2-2\,x-22\,t+19\,tx+47\,{t}^{2}-26\,{t}^{2}x} {t^{4}\left({1-8\,t}\right)\left({x-t-2\,{x}^{2}+{x}^{3}}\right)},\\
B_3&=-\res_x \frac{1} {3}\frac{2\,x-3\,t-19\,tx+21\,{t}^{2}+26\,{t}^{2}x} {t^{4}\left({1-8\,t}\right)\left({-t+{x}^{2}-{x}^{3}}\right)},\\
B_4&= \res_x \frac{x^{3}} {\left({1-x}\right)^{2}t^{2}\left({-t+{x}^{2}-{x}^{3}}\right)\sqrt{x^2-4tx}}
.
\end{align*}

Our first try is to obtain the D-finite equation. The equation for \( B_1,B_2,B_3 \) are easy. For \( B_4 \), we could use a similar idea of \cite{XZ09} to find the D-finite equation. Combining these together, we could obtain a D-finite equation for \( F(t) \).

%\comment{I added the following.}
The D-finite equation for \( F(t) \) is of order 4, but is too lengthy to be put here. This equation can be obtained by other methods, such as the theory of hypergeometric sum. Zeilberger can compute it quickly using his software.


A. Goupil believes that \( F(t) \) is algebraic \cite{A} and he is right. It is clear that \( B_1,B_2,B_3 \) are algebraic. We need to show that \( B_4 \) is algebraic, too. Note that the general theory only shows that \( B_4 \) is \( D \)-finite.

We need the well-known Jacobi's change of variable formula. See, e.g., \cite{XIN06}.
\begin{theo}[Jacobi's Residue Formula] Let \(y=f(x)\in \mathbb{C}((x)) \) be a Laurent
series and let \(b\) be the integer such that \(f(x)/x^b\) is a
formal power series with nonzero constant term. Then for any formal
series \(G(y)\) such that the composition \(G(f(x))\) is a Laurent
series, we have \vspace{-2mm}
\begin{align}
 \res_x G(f(x)) \frac{\partial
f}{\partial x} =b \res_y G(y). \label{e-Jacobi}
\end{align}
\end{theo}

We make the change of variable \( x=u^{-1}(u+t)^2 \). Then
\[ \sqrt{x^2-4tx} = u^{-1}(u+t)(u-t).\]
The advantage of this change of variable is that the square root disappears, and we are left with a residue of a rational function. This change of variable is inspired by the well-known fact if we set \( x=u(1+u)^{-2} \), \( \sqrt{1-4x} \) becomes a rational function in \( u \). One more thing we need to take care is how to treat \( u \): solving \( x=u^{-1}(u+t)^2 \) for \( u \) gives
\[ u=-t+\frac{x+\sqrt{x^2-4tx}}{2}=x+\cdots, \text{ or }\  u=-t+\frac{x-\sqrt{x^2-4tx}}{2}=\frac{t^2}{x}+\cdots .\]
We choose the former representation, which means \( u \) has initial term \( x \) and we shall just treat \( u \) the same as \( x \) and hence we can replace \( u \) by \( x \) and still work in the field \( \mathbb{C}((x))((t)) \) of iterated Laurent series.
If we choose the latter representation, then \( u \) has initial term \( t^2/x \). Thus $u$ is smaller than $t$ and we need the theory of Malcev-Neumann series to continue.

To avoid producing more denominator factors, we apply this change of variable to \( B_3+B_4 \). This gives the residue in \( u \) of a rational function. Now replacing \( u \) by \( x \) and applying the ILSRRF algorithm with respect to \( x \), we obtain
 \begin{align*}
 B_3+B_4=&-\frac{1} {3}\frac{1-8\,t+4\,{t}^{2}} {t^{4}\left({1-8\,t}\right)}+\frac{1-6\,t+10\,{t}^{2}} {\left({1-4\,t}\right)t^{4}\sqrt{1-4t}} \\
&-\res_x \frac{2} {3}\frac{2\,x-22\,tx-3\,{t}^{2}+47\,{t}^{2}x+21\,{t}^{3}} {t^{4}\left({1-8\,t}\right)\left({{x}^{2}-{x}^{3}-3\,t{x}^{2}-3\,{t}^{2}x-{t}^{3}}\right)}.
\end{align*}

Together with the formulas for \( B_1 \) and \( B_2 \), we obtain
\(F(t) = C_1+C_2+C_3+C_4,\)
where
\begin{align*}
  C_1&=-\frac{1-4\,t+10\,{t}^{2}-6\,{t}^{3}+5\,{t}^{4}} {\left({1-t}\right)^{4}t^{4}},\\
C_2 &=3\frac{1-6\,t+10\,{t}^{2}} {t^{4}\left({1-4\,t}\right)\sqrt{1-4 t}}, \\
C_3 &= -\res_x\frac{1} {3} \frac{2-2\,x-22\,t+19\,tx+47\,{t}^{2}-26\,{t}^{2}x} {t^{4}\left({1-8\,t}\right)\left({x-t-2\,{x}^{2}+{x}^{3}}\right)},\\
C_4 &= -\res_x \frac{2} {3} \frac{2\,x-22\,tx-3\,{t}^{2}+47\,{t}^{2}x+21\,{t}^{3}} {t^{4}\left({1-8\,t}\right)\left({{x}^{2}-{x}^{3}-3\,t{x}^{2}-3\,{t}^{2}x-{t}^{3}}\right)}.
\end{align*}
Now we deal with \( C_3 \) first.
The denominator factor \(  -x+2\,{x}^{2}-{x}^{3}+t \) has initial term \( -x \), and hence has a unique small root denoted \( R_3 \). Then the residue is computed as
\[C_3 = -\frac{1} {3}\frac{2-2\,R_{{3}}-22\,t+19\,tR_{{3}}+47\,{t}^{2}-26\,{t}^{2}R_{{3}}} {t^{4}\left({1-8\,t}\right)\left({1-4\,R_{{3}}+3\,{R_{{3}}}^{2}}\right)}.\]
Since \( R_3 \) is algebraic of degree \( 3 \), \( C_3 \) is algebraic of degree at most \( 3 \). By the AFE algorithm we obtain an algebraic functional equation for \( C_3 \) as follows.
\begin{multline*}
  g_3(Z)= 27 \left( 27t-4 \right)  \left( 8t-1 \right) ^{3}{Z}^{3}{t}^{12}
+9 \left( 8t-1 \right) \left( 2314{t}^{4}-2272
{t}^{3}+720{t}^{2}-91t+4 \right) Z{t}^{4}\\
+17576{t}^{6}-59259{t}^{5}+47838{t
}^{4}-16864{t}^{3}+2928{t}^{2}-246t+8.
\end{multline*}


Next we deal with \( C_4 \). The denominator factor \( {t}^{3}+3\,{t}^{2}x+3\,t{x}^{2}-{x}^{2}+{x}^{3} \) has initial term  \( -x^2 \) and hence has two small roots. Thus the residue is computed as
\[C_4 = \sum_{R_4} -\frac{2} {3}\frac{2\,R_{{4}}-22\,tR_{{4}}-3\,{t}^{2}+47\,{t}^{2}R_{{4}}+21\,{t}^{3}} {t^{4}\left({1-8\,t}\right)\left({2\,R_{{4}}-3\,{R_{{4}}}^{2}-6\,tR_{{4}}-3\,{t}^{2}}\right)},\]
where the sum ranges over the two small roots of the denominator factor. By the AFE algorithm we can get an algebraic functional equation for one term, which is the following degree \( 3 \) polynomial.
{\small \begin{multline*}
  \overline{g}_4(Z)=27\, \left( 27\,t-4 \right)  \left( 8\,t-1 \right) ^{3}{Z}^{3}{t}^{12}
+36\, \left( 8\,t-1 \right)  \left( 2314\,{t}^{4}-2272\,{t}^{3}+720\,{
t}^{2}-91\,t+4 \right) Z{t}^{4}\\-64+134912\,{t}^{3}-23424\,{t}^{2}+1968
\,t-140608\,{t}^{6}+474072\,{t}^{5}-382704\,{t}^{4}.
\end{multline*}}
Suppose the above polynomial has \( \alpha_1,\alpha_2,\alpha_3 \) as the three roots. Then \( C_4=\alpha_1+\alpha_2 \) by suitably permuting the \( \alpha \)'s. Notice that \( \alpha_1+\alpha_2+\alpha_3=0 \). The algebraic functional equation for \( C_4 \) must be \( -\overline{g}_4(-Z) \), so
{\small \begin{multline*}
  g_4(Z)=27\, \left( 27\,t-4 \right)  \left( 8\,t-1 \right) ^{3}{Z}^{3}{t}^{12}
+36\, \left( 8\,t-1 \right)  \left( 2314\,{t}^{4}-2272\,{t}^{3}+720\,{
t}^{2}-91\,t+4 \right) Z{t}^{4}\\-(-64+134912\,{t}^{3}-23424\,{t}^{2}+1968
\,t-140608\,{t}^{6}+474072\,{t}^{5}-382704\,{t}^{4}).
\end{multline*}}

Applying the AFE2 algorithm to \( C_3+C_4 \) we obtain the minimal polynomial of \( C_3+C_4 \) as follows.
\begin{multline*}
  g_{34}(Z)=  \left( 1416\,{t}^{14}+4\,{t}^{12}-123\,{t}^{13}+13824\,{t}^{16}-7232
\,{t}^{15} \right) {Z}^{3}\\+ \left( -12\,{t}^{4}-61470\,{t}^{8}+369\,{t
}^{5}+24096\,{t}^{7}-4344\,{t}^{6}+55536\,{t}^{9} \right) Z\\+17576\,{t}
^{6}-59259\,{t}^{5}+47838\,{t}^{4}-16864\,{t}^{3}+2928\,{t}^{2}-246\,t
+8
.
\end{multline*}
To obtain the minimal polynomial of \( C_2+C_3+C_4 \) it is easier to use Remark \ref{rem-alg-2}: the minimal polynomial divides \( g_{234}=g_{34}(Z+C_2)g_{34}(Z-C_2) \), which is checked to be irreducible. The final step for the minimal polynomial of \( C_1+C_2+C_3+C_4 \) is easy, and we finally obtain the minimal polynomial of the diagonal as follows.
\[g(Z)=7776-7776Z+t\cdot (\text{a lengthy polynomial}).\]
 The degree of \( g(Z) \) is \( 6 \) in \( Z \) and \( 61 \) in \( t \). This shows that to guess \( g(Z) \) using something like the gfun package is too expensive. Finally, we remark that \( g(Z) \) has  a unique power series root and this root has constant \( 1 \).


\section{More examples}
%\comment{You shall combine Examples 10, 11, 16}

The following examples are chosen from \cite{PW08}.
Our working field for dealing with the examples is $\mathbb{C}((x))((t))$
or $\mathbb{C}((x))((y))((t))$.

\begin{exam}\cite[4.5,7.3,4.6]{PW08}\label{exam1}
The following three diagonals are simple and similar.
\begin{align}
F_1(t)=&\mathrm{diag} \frac{2}{1+2x+\sqrt{1-4x}-2xy}=
\res_{x} \frac{2}{x(1+2x+\sqrt{1-4x}-2x\frac{t}{x})}, \\
F_2(t)=&\mathrm{diag} \frac{2}{1+\sqrt {1-4\,{x}^{2}}-2\,xy}
=\res_x \frac{2}{ x\left( 1+\sqrt {1-4\,{x}^{2}}-2\,t \right) },\\
F_3(t)=&\mathrm{diag} {\frac {xy \left( 1-x \right) ^{3}}{ \left( 1-x \right) ^{4}-xy
\left( 1-x-{x}^{2}+{x}^{3}+{x}^{2}y \right) }} \nonumber \\
=&
\res_{x} {\frac {t \left( 1-x \right) ^{3}}{x\big( \left( 1-x \right) ^{4}-t
 \left( 1-x-{x}^{2}+{x}^{3}+{x}t \right)\big) }}.
\end{align}
%The working field is $\mathbb{C}((x))((t))$.
For $F_1(t)$ and $F_2(t)$ we need Jacobi's residue
formula to deal with the square root.
For $F_1$ we make the change of variable $x=u(1+u)^{-2}$. Then
$\sqrt{1-4x}=(1-u)/(1+u)$,
and
 $$F_1(t)=\res_u {\frac { \left( 1-u \right)  \left( 1+u \right) }{u \left( 1-t+2\,u-
2\,tu-t{u}^{2} \right) }}.$$
Solving $x=u(1+u)^{-2}$ for $u$ gives
$$u={\frac {-2\,x+1+\sqrt {1-4\,x}}{2x}}=1/x-2-x+\cdots, \ \ \mbox{or} \ \ u=-{\frac {2\,x-1+\sqrt {1-4\,x}}{2x}}=x+\cdots.$$
We choose the later representation and treat $u$ the same as $x$.

For $F_2$ we make the change of variable $x=u(1+{u}^{2})^{-1}$.
Then $\sqrt {1-4x^2}=(1-u)(1+u)/(1+u^2)$, and
$$F_2(t)=\res_u {\frac { \left( 1-u \right)  \left( 1+u \right) }{u \left( 1-t-t{u}^{2
} \right) }}.$$
Solving $x=u(1+{u}^{2})^{-1}$ for $u$ gives
$$u={\frac {1+\sqrt {1-4\,{x}^{2}}}{2x}}=\frac{1}{x}+\cdots, \ \ \mbox{or} \ \
u={\frac {1-\sqrt {1-4\,{x}^{2}}}{2x}}=x+\cdots.$$
We choose the later representation and treat $u$ the same as $x$.

$F_1(t),F_2(t)$ and $F_3(t)$ are all of the form
$$\res_x q(t)\frac{1+x \cdot r(x)}{x(1-t+x\cdot p(x,t))},$$
where $q,r,p$ are polynomials. It is easy to get the above residues even without the
ILSRRF algorithm. Then
\begin{align*}
F_1(t)=F_2(t)=\frac{1}{1-t}, \quad F_3(t)=\frac{t}{1-t}.
\end{align*}
\end{exam}

%\begin{exam}\cite[4.6]{PW08}\label{exam2}
%Compute the diagonal
%\begin{align}
%F(t)=\mathrm{diag} {\frac {xy \left( 1-x \right) ^{3}}{ \left( 1-x \right) ^{4}-xy
%\left( 1-x-{x}^{2}+{x}^{3}+{x}^{2}y \right) }}
%=
%\res_{x} {\frac {x\frac{t}{x} \left( 1-x \right) ^{3}}{x\big( \left( 1-x \right) ^{4}-x\frac{t}{x}
% \left( 1-x-{x}^{2}+{x}^{3}+{x}^{2}\frac{t}{x} \right)\big) }}
%.
%\end{align}
%%The working field is $\mathbb{C}((x))((t))$.
%Apply ILSRRF algorithm with respect to $x$, we obtain
%$$F(t)=\res_x\frac{t}{(1-t)x}=\frac{t}{(1-t)}.$$
%\end{exam}

\begin{exam}\cite[4.10]{PW08}\label{exam3}
Compute the diagonal
\begin{align}
F(t)=\mathrm{diag} {\frac {1}{ \left( 1-z \left( 1-{x}^{2}{y}^{2} \right)  \right)
 \left( 1-x \left( 1+y \right)  \right) }}
=
\res_{x,y} {\frac {1}{xy \big( 1-\frac{t}{xy} \left( 1-{x}^{2}{y}^{2} \right)  \big)
 \left( 1-x \left( 1+y \right)  \right) }}.
\end{align}
%The working field is $\mathbb{C}((x))((y))((t))$.
Applying the ILSRRF algorithm with respect to $y$, we obtain
$F(t)=B_1+B_2,$
where
\begin{align*}
&B_1=\res_x \frac {1}{2x \left( 1-x-2
\,tx+t{x}^{2} \right) }, \\
&B_2=-\res_{x,y}{\frac {2\,tx-2\,t-1}{2 \left( 1-x-2\,tx+t{x}^{2} \right)
 \left( xy-t+t{x}^{2}{y}^{2} \right) }}.
 \end{align*}
 Applying the ILSRRF algorithm to $B_1$ with respect to $x$, we get
 $$B_1=\res_x \frac{1}{2x}=\frac{1}{2}.$$
Since the initial term of $xy-t+t{x}^{2}{y}^{2}$ in the denominator of $B_2$ is $xy$,
there is a unique small root for $y$. Solving $xy-t+t{x}^{2}{y}^{2}=0$ for $y$ gives
$$y={\frac {-1+\sqrt {1+4\,{t}^{2}}}{2 tx}}=\frac{t}{x}+\cdots, \ \ \mbox{or} \ \ y=-{\frac {1+\sqrt {1+4\,{t}^{2}}}{2tx}}=-\frac{x}{t}-\frac{t}{x}+\cdots.$$
%\comment{changed We choose the former representation.}
The former one is small. It follows that
\begin{align*}
B_2=&-\res_{x}{\frac {2\,tx-2\,t-1}{2 \left( 1-x-2\,tx+t{x}^{2} \right)
 \partial_y\left( xy-t+t{x}^{2}{y}^{2} \right) }}\bigg|_{y={\frac {-1+\sqrt {1+4\,{t}^{2}}}{2 tx}}}\\
 =& -\res_x {\frac {2\,tx-2\,t-1}{2 \left( 1-x-2\,tx+t{x}^{2} \right)
 x \sqrt {1+4\,{t}^{2}}  }}.
 \end{align*}
Applying the ILSRRF algorithm with respect to $x$, we obtain
\begin{align*}
B_2=\res_x{\frac {1+2\,t}{2x\sqrt {1+4\,{t}^{2}}}}={\frac {1+2\,t}{2\sqrt {1+4\,{t}^{2}}}}.
\end{align*}
Then $$F(t)={\frac {1+2\,t}{2\sqrt {1+4\,{t}^{2}}}}+\frac{1}{2}.$$
\end{exam}

\begin{exam}\cite[5.3]{PW08}\label{exam4}
Compute the diagonal
\begin{align*}
F(t)=&\mathrm{diag}{\frac {1+{x}^{2}{y}^{3}+{x}^{2}{y}^{4}+{x}^{3}{y}^{4}-{x}^{3}{y}^{6}}
{1-x-y+{x}^{2}{y}^{3}-{x}^{3}{y}^{3}-{x}^{4}{y}^{4}-{x}^{3}{y}^{6}+{x}^{4}{y}^{6}}} \\
=& \res_x \left( 1+{\frac {{t}^{3}}{x}}+{\frac {{t}^{4}}{{x}^{2}}}+{\frac {{t}^
{4}}{x}}-{\frac {{t}^{6}}{{x}^{3}}} \right)  \left( x \left( 1-x-{
\frac {t}{x}}+{\frac {{t}^{3}}{x}}-{t}^{3}-{t}^{4}-{\frac {{t}^{6}}{{x
}^{3}}}+{\frac {{t}^{6}}{{x}^{2}}} \right)  \right) ^{-1}.
\end{align*}
%The working field is $\mathbb{C}((x))((t))$.
Applying the ILSRRF algorithm with respect to $x$, we obtain
\begin{align*}
F(t)=-\frac{1}{4}\,\res_x{\frac {-{t}^{3}{x}^{2}-{t}^{4}{x}^{2}-4\,{t}^{4}x-2\,xt-4\,{t}^
{4}+3\,{t}^{6}-3\,{x}^{2}-2\,{t}^{3}x}{{x}^{3}-{x}^{4}-t{x}^{2}+{t}^{3
}{x}^{2}-{t}^{3}{x}^{3}-{t}^{4}{x}^{3}-{t}^{6}+{t}^{6}x}}+\frac{1}{4}.
\end{align*}
The denominator ${x}^{3}-{x}^{4}-t{x}^{2}+{t}^{3
}{x}^{2}-{t}^{3}{x}^{3}-{t}^{4}{x}^{3}-{t}^{6}+{t}^{6}x$
has initial term $x^3$, hence has three small roots.
Then the residue is computed as
$$F(t)=\sum_{R}Q(R)+\frac{1}{4},
$$
where the sum ranges over the three small roots of the denominator and
$$Q(R)=-\frac{1}{4}\,{\frac {-{t}^{3}{R}^{2}-{t}^{4}{R}^{2}-4\,{t}^{4}R-2\,Rt-4\,{t}^
{4}+3\,{t}^{6}-3\,{R}^{2}-2\,{t}^{3}R}{3\,{R}^{2}-4\,{R}^{3}-2\,Rt+2\,
{t}^{3}R-3\,{t}^{3}{R}^{2}-3\,{t}^{4}{R}^{2}+{t}^{6}}}.$$
Applying the AFE algorithm, we can get an algebraic functional equation
for $Q(R)$, which is the following degree 4 polynomial.
\begin{align*}
\overline{g}(Z)=a_4Z^4+a_3Z^3+a_2Z^2+a_1Z+a_0,
\end{align*}
where
{\small \begin{align*}
a_4=&256\, \left( t+1 \right)  \left( 4\,{t}^{20}+8\,{t}^{19}-23\,{t}^{18}-
63\,{t}^{17}-62\,{t}^{16}-26\,{t}^{15}+43\,{t}^{14}+11\,{t}^{13}+182\,
{t}^{12}+56\,{t}^{11} \right.\\
&\left.-{t}^{10}+203\,{t}^{9}-66\,{t}^{8}-154\,{t}^{7}+
286\,{t}^{6}-368\,{t}^{5}+233\,{t}^{4}-75\,{t}^{3}-8\,{t}^{2}+20\,t-4
 \right),\\
a_3=&0,\\
a_2=&-384\,{t}^{21}-1152\,{t}^{20}+1440\,{t}^{19}+8256\,{t}^{18}+8928\,{t}^
{17}-3840\,{t}^{16}-20064\,{t}^{15}-17728\,{t}^{14} \\
&-12640\,{t}^{13}-
8256\,{t}^{12}+18016\,{t}^{11}+15680\,{t}^{10}+8352\,{t}^{9}+29824\,{t
}^{8}+10624\,{t}^{7}-8000\,{t}^{6} \\
&+6816\,{t}^{5}-6464\,{t}^{4}-2528\,{
t}^{3}+1408\,{t}^{2}-768\,t+1152, \\
a_1=&128\,{t}^{21}+384\,{t}^{20}-480\,{t}^{19}-2752\,{t}^{18}-2464\,{t}^{17
}+3328\,{t}^{16}+9504\,{t}^{15}+6976\,{t}^{14}+1696\,{t}^{13} \\
&-448\,{t}
^{12}-8352\,{t}^{11}-8256\,{t}^{10}-3552\,{t}^{9}-9344\,{t}^{8}-6656\,
{t}^{7}+2240\,{t}^{6}-1248\,{t}^{5}-2112\,{t}^{4}\\
&+1312\,{t}^{3}+640\,{
t}^{2}+128\,t+512, \\
a_0=&-12\,{t}^{21}-36\,{t}^{20}+45\,{t}^{19}+258\,{t}^{18}+183\,{t}^{17}-
504\,{t}^{16}-1139\,{t}^{15}-690\,{t}^{14}+173\,{t}^{13}+390\,{t}^{12} \\
&+907\,{t}^{11}+882\,{t}^{10}+229\,{t}^{9}+692\,{t}^{8}+868\,{t}^{7}+22
\,{t}^{6}+21\,{t}^{5}+518\,{t}^{4}-87\,{t}^{3}-260\,{t}^{2} \\
&+256\,t+60.
\end{align*}}
Suppose the above polynomial has $r_1,r_2,r_3,r_4$ as its four roots.
Then $\sum_{R}Q(R)=r_1+r_2+r_3$ by suitably permuting the
$r$'s. Notice that $r_1+\cdots+r_4=0$, then the algebraic functional equation
for  $\sum_{R}Q(R)$ must be $\overline{g}(-Z)$. Thus the algebraic functional equation for $F(t)$ is
\begin{align*}
g(Z)=\overline{g}(-Z+\frac{1}{4})=a_4(Z-\frac{1}{4})^4+a_2(Z-\frac{1}{4})^2-a_1(Z-\frac{1}{4})+a_0.
\end{align*}
\end{exam}

\begin{exam}\cite[6.3]{PW08}\label{exam5}
Compute the diagonal
\begin{align*}
F(t)&=\mathrm{diag} {\frac {3xz \left( 1-z \right)  \left( 3-z \right) }{ \left( 1-3\,y
 \left( 1+z \right) ^{2} \right)  \left( 27-xz \left( 3-z \right) ^{2}
 \right) }}\\
 &=\res_{x,y}
 \frac{3\,t \left( 1-{\frac {t}{xy}} \right)  \left( 3-{\frac {t}{xy}}
 \right)}
 {x{y}^{2} \left( 1-3\,y \left( 1+{\frac {t}{xy}} \right) ^{2} \right)
 \left( 27-t \left( 3-{\frac {t}{xy}} \right) ^{2}{y}^{-1} \right) }.
\end{align*}
%The working field is $\mathbb{C}((x))((y))((t))$.
Applying the ILSRRF algorithm with respect to $y$, we obtain
\begin{align*}
F(t)=\res_x Q(x,t)+\res_{x,y}R(x,y,t),
\end{align*}
where
\begin{align*}
Q(x,t)=-{\frac {x \left( 3\,{x}^{2}-72\,tx-2\,t{x}^{2}+378\,{t}^{2}+32\,
x{t}^{2} \right) }{ 2\left( -{x}^{4}-378\,{t}^{2}{x}^{2}-32\,{t}^{2}{x}
^{3}+864\,{t}^{3}x+36\,t{x}^{3}+256\,{t}^{3}{x}^{2}+729\,{t}^{3}+{x}^{
4}t \right) }},
\end{align*}
and
\begin{align*}
R(x,y,t)=&{\frac {{x}^{2} \left( -3\,{x}^{3}-756\,x{t}^{2}-112\,{t}^{2}{x}^
{2}+1296\,{t}^{3}+90\,t{x}^{2}+768\,{t}^{3}x+4\,t{x}^{3} \right) }{2
 \left( -{x}^{2}y+3\,{x}^{2}{y}^{2}+6\,xyt+3\,{t}^{2} \right) }} \\
 &\cdot \left(
-{x}^{4}-378\,{t}^{2}{x}^{2}-32\,{t}^{2}{x}^{3}+864\,{t}^{3}x+36\,t{x}
^{3}+256\,{t}^{3}{x}^{2}+729\,{t}^{3}+{x}^{4}t \right)^{-1}.
\end{align*}
Applying the ILSRRF algorithm to $Q(x,t)$ with respect to $x$, we get
\begin{align*}
\res_x Q(x,t)={\frac {3-2t}{2(1-t)}}.
\end{align*}
The denominator factor  $-{x}^{2}y+3\,{x}^{2}{y}^{2}+6\,xyt+3\,{t}^{2}$
has initial term $-x^2y$. Thus it has the following unique small root
$${\frac {x-6t-\sqrt {{x}^{2}-12\,tx}}{6x}}.$$
It follows that
\begin{align*}
\res&_yR(x,y,t)\\
&={\frac {x \left( -x+12\,t \right)  \left( 108\,{t}^{2}+64\,x{t}^
{2}-54\,tx-4\,t{x}^{2}+3\,{x}^{2} \right) }{2\sqrt {x \left( x-12\,t
 \right) } \left( {x}^{4}+378\,{t}^{2}{x}^{2}+32\,{t}^{2}{x}^{3}-864
\,{t}^{3}x-36\,t{x}^{3}-256\,{t}^{3}{x}^{2}-729\,{t}^{3}-{x}^{4}t
 \right) }}.
 \end{align*}
We make the change of variable $x={ \left( u+3\,t \right) ^{2}{u^{-1}}}$. Then
$\sqrt{x(x-12t)}=(u+3t)(u-3t)/u$.
Solving $x={ \left( u+3\,t \right) ^{2}{u^{-1}}}$ for $u$ gives
$$u=\frac{x}{2}-3\,t+\,\frac{\sqrt {{x}^{2}-12\,tx}}{2}=x+\cdots, \ \ \mbox{or} \ \ u=\frac{x}{2}-3\,t-\,\frac{\sqrt {{x}^{2}-12\,tx}}{2}=9t^2/x+\cdots.$$
We choose the former representation and treat $u$ the same as $x$. Therefore
doing the Jacobi's change of variable and applying the ILSRRF algorithm with respect to $x$,
we obtain
\begin{align*}
\res_{x,y}R(x,y,t)={\frac {4\,t-3}{ 2\left( 1-t \right) }}.
\end{align*}
Then
\begin{align*}
F(t)=\frac{t}{1-t}.
\end{align*}
\end{exam}

\begin{exam}\cite[7.1]{PW08}\label{exam6}
Compute the diagonal
\begin{align*}
F(t)=\mathrm{diag}  \frac{1}{\left( 1+\sqrt {1-x}-y \right)}
=\res_{x}\frac{1}{\left( 1+\sqrt {1-x}-{\frac {t}{x}} \right) x}.
\end{align*}
%The working field is $\mathbb{C}((x))((t))$.
We make the change of variable $x={\frac {4u}{ \left( 1+u \right) ^{2}}}$.
Then $\sqrt {1-x}=\frac{1-u}{1+u}$, and
$$F(t)=\res_u \,{\frac {-4(1-u)}{-8\,u+t+3\,tu+3\,t{u}^{2}+t{u}^{3}}}.$$
Solving $x={\frac {4u}{ \left( 1+u \right) ^{2}}}$ for $u$ gives
$$u={\frac {-x+2+2\,\sqrt {1-x}}{x}}=\frac{4}{x}+\cdots, \ \ \mbox{or} \ \
u={\frac{-x+2-2\,\sqrt {1-x}}{x}}=\frac{1}{4}x+\cdots.$$
So we choose the later representation and treat $u$ the same as $x$.
The initial term of the denominator $-8u+t+3tu+3tu^2+tu^3$
is $u$. Then the residue is computed as
$$F(t)=\,{\frac {-4(1-R)}{-8+3\,t+6\,tR+3\,t{R}^{2}}},$$
where $R$ is the unique small root of $-8u+t+3tu+3tu^2+tu^3$.
Applying the AFE algorithm, we can get the following algebraic functional equation
for $F(t)$.
$$ \left( 27\,t-32 \right) t{Z}^{3}+ \left( -12\,t+16 \right) Z+8\,t-8.$$
\end{exam}

%\begin{exam}\cite[7.3]{PW08}\label{exam7}
%Compute the diagonal
%$$F(t)=\mathrm{diag} \frac{2}{1+\sqrt {1-4\,{x}^{2}}-2\,xy}
%=\res_x \frac{2}{ \left( 1+\sqrt {1-4\,{x}^{2}}-2\,t \right) x}.$$
%%The working field is $\mathbb{C}((x))((t))$.
%We make the change of variable by $x={\frac {u}{1+{u}^{2}}}$.
%Then $\sqrt {1-4x^2}=\frac{(1-u)(1+u)}{1+u^2}$, and
%$$F(t)=\res_u {\frac { \left( -1+u \right)  \left( 1+u \right) }{u \left( -1+t{u}^{2
%}+t \right) }}.$$
%Solving $x={\frac {u}{1+{u}^{2}}}$ for $u$ gives
%$$u={\frac {1+\sqrt {1-4\,{x}^{2}}}{2x}}=\frac{1}{x}+\cdots, \ \ \mbox{or} \ \
%u={\frac {1-\sqrt {1-4\,{x}^{2}}}{2x}}=x+\cdots.$$
%We choose the later representation and treat $u$ the same as $x$.
%Apply ILSRRF algorithm with respect to $u$, we get
%$$F(t)=\frac{1}{1-t}.$$
%\end{exam}

\begin{exam}\cite[8.2]{PW08}\label{exam8}
Compute the diagonal
$$F(t)=\mathrm{diag} {\frac {1+xy+{x}^{2}{y}^{2}}{1-x-y+xy-{x}^{2}{y}^{2}}}
=\res_x \frac{1+t+t^2}{\left( x-x^2-t+tx-{t}^{2}x \right) }.$$
%The working field is $\mathbb{C}((x))((t))$.
The denominator factor $\left( x-x^2-t+tx-{t}^{2}x \right)$ has initial term
$x$ and hence has a unique small root
$$\frac{1+\,t-\,{t}^{2}-\,\sqrt {-2\,t+1-{t}^{2}-2\,{t}^{3}+{t}^{4}}}{2}=t+\cdots.$$
Then the residue is
$$F(t)=\sqrt{\frac {1+t+{t}^{2}}{1-3\,t+{t}^{2}}}.$$
\end{exam}




\section{Potential for the general Lipshitz theorem\label{sec:potential}}

It is possible to simplify residues in more variables.
Suppose \( x \) and \( y \) are two variables in \( \mathcal K \), and \( Q(x,y) \) is a rational function. Then \( \res_{x,y} Q(x,y) \) might not be algebraic. We hope to find simple conditions for \( Q(x,y) \) to have an algebraic residue in \( x \) and \( y \).

The natural condition would be that %\comment{that added here}
\( \res_x Q(x,y) \) or \( \res_y Q(x,y) \) is indeed rational.
This raises the following question: Given a rational function \( Q(x,y) \), determine if \( \res_x Q(x,y) \) is rational or not. If the answer is positive, then give the explicit rational function.

Let \( G=\res_x Q(x,y) \). Then \( G \) is rational if and only if its minimal polynomial is of degree \( 1 \). Since the minimal polynomial can be computed, we have an algorithm to determine if \( G \) is rational. Note that the D-finite approach is not appealing.
%\comment{You are right, I changed accordingly.}
If $G=p(y)/q(y)$ is rational, then $G$ satisfies the following first order D-finite
equation:
$$q(y)^2\partial_y G(y)-q(y)\partial_y p(y)+p(y)\partial_y q(y)=0.$$
However, it is hard to find the minimal order D-finite equation.

\medskip
Jacobi's residue formula is powerful, but there is no general rule on how to make the change of variables.
By studying our archetype, we find a new class of rational functions for which we can always make a change of variable to simplify further.
Consider residues of the following type
\[\res_{x,y} \frac{p(x,y)}{q(x) D(x,y)},\]
where \( p,q,D \) are polynomials with \( \deg_y p(x,y)< \deg_y D(x,y) \), and \( D(x,y) \) is irreducible. If \( \deg_x D(x,y)=1 \), then we can solve \( D(x,y) \) for \( x \), giving \( x=f(y) \) for rational $f$. We claim that \( D(f(u),y) \) has \( y-u \) as a factor since  \( D(f(u),u)=0. \) Therefore, by making the change of variable \( x=f(u) \), we obtain
\[\res_{x,y} \frac{p(x,y)}{q(x) D(x,y)}=\res_{u,y} \frac{p(f(u),y)}{q(f(u)) D(f(u),y)}\cdot \pa u f(u).\]
Applying the ILSRRF algorithm with respect to \( y \) gives the residue of a simpler rational function.
In particular, if $\deg_y D(x,y)=2$ and $\deg_x D(x,y)=1$, then $\res_{x,y} \frac{p(x,y)}{q(x) D(x,y)}$ is algebraic.

For example, when computing \( \res_{x,y} x^{-1}y^{-1}B(x,y,t/xy) \), we met the following residue
\[\res_{x,y} \frac{x^{3}} {\left({1-x}\right)^{2}t^{2}\left({-t+{x}^{2}-{x}^{3}}\right)\left({-t+xy-x{y}^{2}}\right)}.\]
If we make the change of variable \( x=t(u-u^2)^{-1} \), then we get
\[\res_{u,y} {\frac { \left( -1+2\,u \right)  \left( -1+u \right) u}{ \left( u-1+y
 \right)  \left( u-y \right)  \left( t-{u}^{2}+{u}^{3} \right)
 \left( t-u+2\,{u}^{2}-{u}^{3} \right)  \left( -u+{u}^{2}+t \right) ^{
2}}}.
\]
Elimination of $y$ must give a rational function, but one must be careful:
\[ u=\frac{1+\sqrt{1-4t/x}}{2} =1-t/x+\cdots \text{ or }\ u =\frac{1-\sqrt{1-4t/x}}{2} =t/x +\cdots.  \]
It follows that we can only chose the later and regard $u$ as $t/x$. We omit the rest of
the computation for brevity.

\medskip
For residue in two or more variables, we need Lipshitz's D-finite theory.
Lipshitz's idea can be reformulated as follows in its simple form.
Let $f$ be an iterated Laurent series. Suppose $f$ is D-finite in variables $x$ and $t$. Then there exist
nonzero linear partial differential operators $P_1(x,t;\pa x)$ and $P_2(x,t;\pa t)$, called annihilating operators, such that
$$ P_1(x,t;\pa x) f=0, \   P_2(x,t;\pa t) f=0.$$
To show that $\res_x f$ is D-finite in $t$, it is sufficient to find operators $L_1$ and $L_2$ such that
$$L_1(x,t;\pa x,\pa t) P_1(x,t;\pa x) +L_2(x,t;\pa x,\pa t) P_2(x,t;\pa t) =P_3(t;\pa x,\pa t) $$
is free of $x$.
Then $\res_x f$ will be annihilated by $P_3(t;0,\pa t)$.
%$$0=\res_x  P_3(t;\pa x,\pa t) f = P_3(t;0,\pa t) \res_x f .$$
%This will show that $\res_x f$ is D-finite in $t$.
Lipshitz showed the existence of $L_1$ and $L_2$ by a clever dimension counting argument, but the dimension is usually too huge in practice.

It has been observed that we only need an annihilating operator of the form
$P_4(t;\pa t) +\pa x (P_5(x,t;\pa x,\pa t))$. Algorithms along this line have been developed. See \cite[Chapter~9]{AB} for explanation and references therein.

The idea of a reduced form can be used to simplify  the computation.
By using $P_1$ we can define a reduced form for $Q(x,t)\pa t^i f$, where $Q(x,t)$ is a rational function. By the reduced form, it will be easy to see that the $\pa t^k f$ have similar reduced forms, and then deduce that they lie in a finite dimensional space. Then solving a system of linear equation will give the desired D-finite equation. It is possible to use the powerful Jacobi's residue formula to reduce the dimension. This idea performs well when $f=\sqrt{S}$ for some rational function $S$. See \cite{XZ09}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
The authors are indebted to the referee for many
helpful comments.
This work was supported by the
National Science Foundation of China (No. 11171231, 11101435)
and the Science and Technology Planning Project of Hunan Province, China
(No. 2012FJ4085).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{A}
A. Goupil, private communication, August 2010.

\bibitem{AH10}
A. Goupil and H. Cloutier.
\newblock 3D Polyominoes inscribed in a rectangular prism.
\newblock preprint, arXiv:1009.4859.

\bibitem{L88}
L. Lipshitz.
\newblock The diagonal of a D-finite power series is D-finite.
\newblock {\em J. Algebra}, 113(2):373--378, 1988.

\bibitem{PW08}
R. Pemantle and M. Wilson.
\newblock Twenty combinatorial examples of asymptotics derived
from multivariate generating functions.
\newblock \emph{SIAM Review}, 50:199--272, 2008.

\bibitem{AB}
M. Petkovsek, H. Wilf, and D. Zeilberger.
\newblock {\em A=B}.
\newblock A K Peters, Ltd., Wellesley, MA, 1996.


\bibitem{Stan99}
R.P. Stanley.
\newblock {\em Enumerative Combinatorics, II}.
\newblock Cambridge University Press, 1999.

\bibitem{Xin04}
G.~Xin.
\newblock A fast algorithm for {M}ac{M}ahon's partition analysis.
\newblock {\em Electron. J. Combin.}, 11:R58, 2004.

\bibitem{XIN06}
G.~Xin.
\newblock A residue theorem for Malcev-Neumann series.
\newblock {\em Adv. in Appl. Math.}, 35:271--293, 2005.

\bibitem{XZ09}
G.~Xin and T.Y.J.~Zhang.
\newblock Enumeration of bilaterally symmetric 3-noncrossing partitions.
\newblock {\em Discrete Math.}, 309:2497--2509, 2009.


\bibitem{Zeil90}
D.~Zeilberger.
\newblock A holonomic systems approach to special functions identities.
\newblock {\em J. Comput. Appl. Math.}, 32:321--368, 1990.

\bibitem{Zei91}
D.~Zeilberger.
\newblock The method of creative telescoping.
\newblock {\em J. Symb. Computation}, 11:195--204, 1991.

\end{thebibliography}

\end{document}
