\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.38}{23(3)}{2016}

\usepackage{amsfonts}
\usepackage{amsthm,amsmath,amssymb}
\usepackage{cite,color}
\usepackage{dsfont}
\usepackage{mathrsfs}
\usepackage{epsfig}
\usepackage{longtable}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}



\newtheorem{theo}{Theorem}
\newtheorem{prop}[theo]{Proposition}
\newtheorem{coro}[theo]{Corollary}
\newtheorem{defi}[theo]{Definition}
\newtheorem{lem}[theo]{Lemma}
\newtheorem{exm}[theo]{Example}
\newtheorem{conj}[theo]{Conjecture}
\makeatletter \@addtoreset{equation}{section}
\@addtoreset{theo}{section} \makeatother

\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\renewcommand{\thesection}{\arabic{section}}
\renewcommand{\thetheo}{\arabic{section}.\arabic{theo}}

\newcommand{\bN} { {\mathbb{N}}}
\newcommand{\bC} { {\mathbb{C}}}
\newcommand{\bQ} { {\mathbb{Q}}}
\newcommand{\bZ} { {\mathbb{Z}}}
\newcommand{\bR} { {\mathbb{R}}}
\newcommand{\bF} { {\mathbb{F}}}
\newcommand{\bK} { {\mathbb{K}}}
\newcommand{\bE} { {\mathbb{E}}}
\newcommand{\cS} { {\mathcal{S}}}
\newcommand{\cA} { {\mathcal{A}}}

\def\qed{\hfill \rule{4pt}{7pt}}
\def\pf{\noindent {\it Proof.} }
\def\red{\textcolor{red}}



\title{\bf  Infinite Orders and Non-D-finite Property of \\
  $3$-Dimensional Lattice Walks}
\author{Daniel K. Du\\
\small Center for Applied Mathematics \\[-0.8ex]
\small Tianjin University\\[-0.8ex] 
\small Tianjin 300072, P. R. China \\
\small\tt daniel@tju.edu.cn\\
\and
Qing-Hu Hou\\
\small Center for Applied Mathematics \\[-0.8ex]
\small Tianjin University\\[-0.8ex] 
\small Tianjin 300072, P. R. China \\
\small\tt qh\_hou@tju.edu.cn\\
\and
Rong-Hua Wang\\
\small Center for Combinatorics, LPMC-TJKLC\\[-0.8ex]
\small Nankai University\\[-0.8ex] 
\small Tianjin 300071, P. R. China \\
\small\tt wangwang@mail.nankai.edu.cn\\
}

\date{\dateline{Jul 14, 2015}{Aug 9, 2016}{Aug 19, 2016} \\
\small Mathematics Subject Classifications: 05A15, 05A16}         
\begin{document}

\maketitle
\begin{abstract}
Recently, Bostan and his coauthors investigated lattice walks restricted to the non-negative octant $\mathbb{N}^3$.
For the $35548$ non-trivial models with at most six steps, they found that many models are associated to a group
of order at least $200$ and conjectured these groups were in fact infinite groups.
In this paper, we first confirm these conjectures and then consider the non-D-finite property of the generating function for some of these models.

%\bigskip\noindent \textbf{Keywords:} lattice walks; infinite group; D-finite
\end{abstract}

\section{Introduction}
The objective of this paper is to use the properties of Jacobian matrix at fixed points to derive the infiniteness of groups associated with certain  lattice walks restricted to the positive octant.
Furthermore, we present the non-D-finiteness of corresponding generating functions for some lattice walks of infinite order by considering the asymptotic behavior of their coefficients.

Counting walks in a fixed region of the lattice $\bZ^d$ is a classical topic
in enumerative combinatorics~\cite{Maher1978,GesselZeilberger1992,Mishna2009,Raschel2012} and in probability theory~\cite{Narayana1979,Mohanty1979}.
In the past few years, lattice path models restricted to the quarter plane and the positive octant have received special attention, and recent works~\cite{BBKM2015,MelouMishna2010,BostanKauers2010,KurkovaRaschel2011
,BostanRaschelSalvy2014,MishnaRechnitzer2009,MelczerMishna2014} have shown how they can help us better understand generating functions of lattice walks.

Many recent papers dealt with the enumeration of lattice walks with prescribed steps confined to the positive quadrant. In fact, Bousquet-M\'{e}lou and Mishna~\cite{MelouMishna2010} proved that among the $2^8$ possible cases of small-step walks in the quarter plane, there were exactly $79$ inherently different cases.
Then, they showed that $23$ of these models were associated with a finite group, of which $22$ admitted D-finite generating functions (see, for example~\cite{Stanley1980} for an overview on D-finite series).
The $23$rd model, known as Gessel walks, was proven D-finite, and even algebraic, by Bostan and Kauers~\cite{BostanKauers2010}.
Moreover, it was conjectured in \cite{MelouMishna2010} that the $56$ remaining models with infinite group had non-D-finite generating functions.
This was proved by Kurkova and Raschel~\cite{KurkovaRaschel2011} for the $51$ nonsingular walks.
The remaining ones are the five so called singular models:
\begin{align}\label{EQ:five singulars}
& \mathcal{A}=[[-1,1],[1,-1],[1,1]],\ \mathcal{B}=[[-1,1],[1,-1],[0,1],[1,0]],\nonumber\\
& \mathcal{C}=[[-1,1],[1,-1],[0,1]],\ \mathcal{D}=[[-1,1],[1,-1],[0,1],[1,1]],\nonumber\\
& \mathcal{E}=[[-1,1],[1,-1],[0,1],[1,0],[1,1]].
\end{align}
%\begin{align*}
%& \mathcal{A}=\{{\rm NW,NE,SE}\},\ \mathcal{B}=\{{\rm NW,N,E,SE}\},\ \mathcal{C}=\{{\rm NW,N,NE,E,SE}\}, \\
%& \mathcal{D}=\{{\rm NW,N,SE}\}, \ \mathcal{E}=\{{\rm NW,N,NE,SE}\},
%\end{align*}
%where ${\rm NW}\equiv(-1,1),\ {\rm N}\equiv(0,1),\ {\rm NE}\equiv(1,1)$, $etc$.
The non-D-finiteness of these $5$ singular models was proved by Mishna and Rechnitzer~\cite{MishnaRechnitzer2009} and Melczer and Mishna~\cite{MelczerMishna2014}. The classification is now complete for walks with steps in $\{0,\pm1\}^2$: the generating function is D-finite if and only if a certain group associated with the model is finite.

Recently, Bostan and his coauthors~\cite{BBKM2015} considered the analogous problem for lattice walks confined to the non-negative octant $\mathbb{N}^3$.
They showed that there are $35548$ non-trivial models with at most six steps.
Each model corresponds to a group which plays an important role in exploring the properties of the generating function.
They found that many models are associated to a group of order at least $200$ and conjectured these groups were in fact infinite groups.

In this paper, we utilize two methods employed by Bousquet-M\'{e}lou and Mishna~\cite{MelouMishna2010} to confirm these conjectures via considering models of dimension two and three, respectively.
For the notation of dimension of a model, one can refer to  Definition \ref{DEFI:dimension}.

More specifically, for the cases of models of dimension two, Bostan $et\ al.$ \cite{BBKM2015} showed that there were $527$ models of cardinality at most $6$.
They found that $118$ models are associated to a finite group of order at most $8$, and conjectured that the remaining $409$ ones associated to a group of infinite order. Our first result is to confirm this conjecture as follows.

\begin{theo}\label{CJ:409}
The $409$ two-dimensional models associated to groups of order at least $200$ are in fact associated to infinite groups.
\end{theo}

At the end of this paper, we will prove that the generating functions for most of these models are not D-finite, which means that their generating functions do not satisfy any non-trivial linear differential recurrences with polynomial coefficients.
\begin{theo}\label{ND:384}
For these $409$ two-dimensional models associated to infinite groups,
the generating functions of the excursions of the $366$ non-singular models are all non-D-finite,
and there are $18$ singular models with non-D-finite generating functions.
\end{theo}

For the cases of three-dimensional models, Bostan $et\ al.$~\cite{BBKM2015} showed that there were $20634$ models associated to a group of order at least $200$ and conjectured the order to be infinite.
Our third result is the confirmation of this conjecture.

\begin{theo}\label{CJ:20634}
The $20634$ three-dimensional models associated with groups of order at least $200$ are in fact associated with infinite groups.
\end{theo}

This paper is organized as follows. In Section $2$, We first recall some notations.
Then we derive the infiniteness of groups associated with certain models in Section $3$. Meanwhile
the proof of Theorem \ref{CJ:409} and Theorem \ref{CJ:20634} will be presented, respectively.
Section $4$ discusses the non-D-finite property, and the proof of Theorem \ref{ND:384} will be presented.



\section{Preliminaries}
To make this paper self-contained, we now recall some definitions and notations.
In particular, we shall use the dimension, the characteristic polynomial and the associated group of models.

Given the hyper cubic lattice $\mathbb{Z}^d$, a finite set of \emph{steps} $\mathcal{S}\subset\{-1,0,1\}^d $ is called a \emph{model} as adopted in \cite{BBKM2015}.
An $\mathcal{S}$-\emph{walk} is defined to be any walk which starts from the origin $(0,0,0)$ and takes its steps in $\mathcal{S}$.
In particular, we focus on \emph{octant walks}, which are $\mathcal{S}$-walks remaining in the non-negative octant $\mathbb{N}^3$, with $\mathbb{N}=\{0,1,2,\dots\}$.
Then we have
\begin{defi}\label{DEFI:genfun}
The $\emph{complete generating function}$ of an octant walk is
\[
O(x,y,z;t)=\sum_{i,j,k,n\geq 0}o(i,j,k;n)x^iy^jz^kt^n,
\]
where $o(i,j,k;n)$ is the number of $n$-step walks in the octant that end at position $(i,j,k)$.
The specialization $O(0,0,0;t)$ counts $\mathcal{S}$-walks returning to the origin, called $\mathcal{S}$-\emph{excursions}.
\end{defi}
To shorten notation, steps of $\mathbb{Z}^d$ will be denoted by $d$-letter words. For example, $\overline{1}10$ stands for the step $(-1,1,0)$.
In fact, an $\mathcal{S}$-\emph{walk} of length $n$ can be viewed as a word $w=w_1w_2\cdots w_n$
made up of letters of $\mathcal{S}$. For each step $s\in \mathcal{S}$, let $a_s$ be the number of occurrences of $s$ in $w$.
Then $w$ ends in the positive octant if and only if the following three linear inequalities hold
\begin{equation}\label{EQ:dimension}
\sum_{s\in \mathcal{S}} a_ss_x\geq0,\ \sum_{s\in \mathcal{S}} a_ss_y\geq0,\ \sum_{s\in \mathcal{S}} a_ss_z\geq0,
\end{equation}
where $s=\{s_x,s_y,s_z\}$ are steps in $\mathcal{S}$.
Consequently, $w=w_1w_2\cdots w_n$~\mbox{remains} in the octant if $w_1w_2\cdots w_i$, for each $1\leq i\leq n$, satisfies these inequalities.

Now we are ready to give the definition of dimension of a model as follows.
\begin{defi}\label{DEFI:dimension}
Let $d\in\{0,1,2,3\}$. A model $\mathcal{S}$ is said to have dimension $d$ if both of the following two conditions are satisfied:
\begin{itemize}
\item[{\rm (1)}] There exist $d$ inequalities in Equation~\eqref{EQ:dimension} such that any $|\mathcal{S}|$-tuple $(a_s)_{s\in \mathcal{S}}$ of non-negative integers satisfying these $d$ inequalities satisfies in fact all three of them.
\item[{\rm (2)}] For any $i\in\{0,1,\ldots,d-1\}$, if we substitute $i$ for $d$ in the above statement, the first condition will not be satisfied.
%% there exists a $|\mathcal{S}|$-tuple $(a_s)_{s\in \mathcal{S}}$ of non-negative integers satisfying $i$ inequalities in Equation~\eqref{EQ:dimension}, but
\end{itemize}
\end{defi}

Given a model $\mathcal{S}$ of cubic lattice, we denote by $S(x,y,z)$ the Laurent polynomial
\[
S(x,y,z)=\sum_{ijk\in S}x^iy^jz^k.
\]
According to the degrees of $x,y$ and $z$, respectively, $S(x,y,z)$ can be written as
\begin{align*}
S(x,y,z)& =\overline{x}A_{-}(y,z)+A_{0}(y,z)+xA_{+}(y,z)\\
        & =\overline{y}B_{-}(x,z)+B_{0}(x,z)+yB_{+}(x,z)\\
        & =\overline{z}C_{-}(x,y)+C_{0}(x,y)+zC_{+}(x,y),
\end{align*}
where $\overline{x}=1/x,\ \overline{y}=1/y,\hbox{ and }\overline{z}=1/z$. We call $S(x,y,z)$ the \emph{characteristic polynomial} of $\mathcal{S}$.


Let us first assume that $\mathcal{S}$ is $3$-dimensional. Then it has a positive and a negative step in each direction, and for any $\alpha\in\{A,B,C\}$, $\alpha_{+}, \alpha_{-}$ are non-zero.
Now we introduce the notation of the group associated with a model.
\begin{defi}\label{DEFI:groups}
For a given model $\mathcal{S}$, the \emph{group} associated with $\mathcal{S}$ is defined as the group $G(\mathcal{S})$ of birational transformations of the variables $[x,y,z]$ generated by the following three involutions
\[
\phi([x,y,z])=\left[\overline{x}\frac{A_{-}(y,z)}{A_{+}(y,z)},y,z\right],
\]
\[
\psi([x,y,z])=\left[x,\overline{y}\frac{B_{-}(x,z)}{B_{+}(x,z)},z\right],
\]
\[
\tau([x,y,z])=\left[x,y,\overline{z}\frac{C_{-}(x,y)}{C_{+}(x,y)}\right].
\]
\end{defi}
By construction, $G(\mathcal{S})$ fixes the characteristic polynomial $S(x,y,z)$.

Suppose $\mathcal{S}$ is a $2$-dimensional model, for which the $z$-condition can be ignored. The corresponding group
$G({\cal S})$ is the group generated by $\phi$ and $\psi$.

\section{Infiniteness of Associated Groups }\label{SE:NonInfite}

In this section, we consider the $35548$ non-trivial models with at most six steps and confined to the non-negative octant $\mathbb{N}^3$.
We derive the infiniteness of these groups by giving the proofs of Theorem \ref{CJ:409} and Theorem \ref{CJ:20634}, respectively.

%\subsection{Two Dimensional Octant Models}\label{SE:2D}
\subsection{The Proof of Theorem \ref{CJ:409}}\label{SE:2D}
When dealing with a model of dimension two, we consider the projection of the model to a plane throughout this paper. Then the model is a multi-set of $\{\overline{1},0,1\}^2\setminus \{0,0\}$.

In order to show the infiniteness of groups associated to two dimensional octant models, we first introduce the method of fixed point argument given by Bousquet-M\'{e}lou and Mishna~\cite{MelouMishna2010}.


Assume that $\theta=\psi\circ\phi$ is well-defined in the  neighborhood of $(a,b)\in\mathbb{C}^2$, which was fixed by $\theta$.  Note that $a$ and $b$ are algebraic over $\bQ$. Let us write $\theta=(\theta_1,\theta_2)$, where $\theta_1$ and $\theta_2$ are the two coordinates of $\theta$. Each $\theta_i$ sends the pair $(x,y)$ to a rational function of $x$ and $y$. The local expansion of $\theta$ around $(a,b)$ reads
\[
\theta(a+u,b+v)=(a,b)+(u,v)J_{\theta}(a,b)+O(u^2)+O(v^2)+O(uv),
\]
where $J_{\theta}(a,b)$ is the Jacobian matrix of $\theta$ at $(a,b)$:
\[
J_{\theta}(a,b)=\left(
    \begin{matrix}{}
       \frac{\partial \theta_1}{\partial x}(a,b) & \frac{\partial \theta_2}{\partial x}(a,b) \\[6pt]
       \frac{\partial \theta_1}{\partial y}(a,b) & \frac{\partial \theta_2}{\partial y}(a,b)
    \end{matrix}
    \right).
\]
Iterating the above expansion gives
\begin{equation}\label{EQ:J^m}
\theta^m(a+u,b+v)=(a,b)+(u,v)J_{\theta}^m(a,b)+O(u^2)+O(v^2)+O(uv),
\end{equation}
where $m$ is a positive integer.

Assume that $\theta$ is of order $n$. Then $\theta^n(a+u,b+v)=(a,b)+(u,v)$ and Equation~\eqref{EQ:J^m} show that $J_{\theta}^n(a,b)$ is the identity matrix. In particular, all eigenvalues of $J_{\theta}(a,b)$ are roots of unity. This provides a strategy for proving that a group $G(\mathcal{S})$ is infinite.


We now give some properties on the fixed points of $\theta=\psi \circ \phi$ and the Jacobian matrices, which will simplify our computations.
\begin{prop}
$(a,b)$ is a fixed point of $\theta$ if and only if it is a fixed point of $\phi$ and $\psi$.
\end{prop}
\pf
Suppose $(a,b)$ is a fixed point of $\theta$. Assume that $\phi(a,b)=(u,b)$. Then we have $\psi(u,b)=(a,b)$. By definition, $\psi$ preserves the first coordinate. We thus have $u=a$ and $(a,b)$ is a fixed point of $\phi$ and $\psi$. The inverse assertion holds straightforwardly. \qed


This proposition indicates that the fixed point $(a,b)$ of $\theta$ can be determined by the equations
\[
  \frac{A_{-}(b)}{A_{+}(b)} = a^2  \quad \mbox{and} \quad \frac{B_{-}(a)}{B_{+}(a)} = b^2.
\]
Moreover, we require that $a$ and $b$ are both non-zero. Now we rewrite the left hand sides of the above two equations in reduced form by canceling the common divisor of the numerator and the denominator and we get
\[
  \frac{p_1(b)}{q_1(b)} = a^2  \quad \mbox{and} \quad \frac{p_2(a)}{q_2(a)} = b^2.
\]
We need to find the solutions of the polynomial systems
\[
  p_1(y) - x^2 q_1(y) = 0, \quad p_2(x) - y^2 q_2(x) = 0, \quad xy \not = 0.
\]
Such systems can be solved by  the
Gr\"obner basis theory introduced by Buchberger~\cite{Buchberger1965} or the {\tt Maple} package {\tt epsilon} developed by Wang \cite{Wang2002}.
In this paper, we use the standard {\tt Maple} command {\tt Groebner[Basis]} to solve such systems. In fact, suppose
\[
F=[ p_1(y) - x^2 q_1(y), p_2(x) - y^2 q_2(x), 1-xyt ].
\]
We may apply the command
\begin{center}
{
\tt
fpt:=Groebner[Basis](F, plex(t,y,x))
}
\end{center}
and take the intersection
\begin{center}
{
\tt
fp = fpt $\cap\ \bC$[x,y].
}
\end{center}
to find the equations satisfied by the fixed points. When {\tt fp=[1]}, there exists no fixed point and the method fails.


When applying the above method to each of the $409$ two-dimensional models, there   always exists an element of {\tt fpt} with a non-zero constant leading coefficient with respect to $t$.
Then according to the extension theorem in~\cite[page 118]{CoxLittleO'shea1992}, we know
{\tt fp} is a basis of the equations satisfied by the fixed points.



%%The command {\tt RegSer} in Maple package {\tt epsilon} developed by D.~M. Wang~\cite{Wang2002} can solve such system. By using
%%\begin{center}
%%{\tt
%%  RegSer([[$p_1(y) - x^2 q_1(y), p_2(x) - y^2 q_2(x)$], [$xy$]], [$x,y$]),
%%}
%%\end{center}


%%\begin{defi}
%%In vector calculus, the Jacobian matrix is the matrix of all first-order partial derivatives of a vector-valued function. Specifically, if we wirte $\theta=\psi \circ \phi$ into the form $\theta=(\theta_1,\theta_2)$, where $\theta_1$ and $\theta_2$ are the two coordinates of $\theta$, then the Jacobian matrix of $\theta$ at $(a,b)$ was defined as
%%\[
%%J_{\theta}=\left(
%%    \begin{matrix}{}
%%       \frac{\partial \theta_1}{\partial x}(a,b) &  \frac{\partial \theta_1}{\partial y}(a,b)\\[6pt]
%%      \frac{\partial \theta_2}{\partial x}(a,b) & \frac{\partial \theta_2}{\partial y}(a,b)
%%    \end{matrix}
%%    \right).
%%\]
%%\end{defi}

The determinant of the Jacobian matrix $J_\theta$ at fixed points satisfies the following property.
\begin{lem}
The determinant of the Jacobian matrix $J_\theta$ at fixed points is~$1$.
\end{lem}
\pf Suppose $(a,b)$ was fixed by $\theta$. By the chain rule, we have
$J_\theta(a,b) = J_\psi(a,b) \cdot J_\phi(a,b)$. While
\[
J_\phi(a,b) = \left( \begin{array}{cc} -\frac{1}{a^2} \frac{p_1(b)}{q_1(b)} & \left. \frac{\partial (p_1(y)/xq_1(y))}{\partial y} \right|_{(a,b)} \\ 0 & 1  \end{array} \right)
 = \left( \begin{array}{cc} -1 & * \\ 0 & 1  \end{array} \right),
\]
and
\[
J_\psi(a,b) = \left( \begin{array}{cc} 1 & 0 \\
\left. \frac{\partial (p_2(x)/yq_2(x))}{\partial x} \right|_{(a,b)} & -\frac{1}{b^2} \frac{p_2(a)}{q_2(a)} \end{array} \right)
 = \left( \begin{array}{cc} 1 & 0 \\ * & -1  \end{array} \right).
\]
Therefore, the determinant of $J_\theta$ is $(-1) \cdot (-1)=1$. \qed


Let $p(X,x,y)$ be the numerator of
\begin{align*}
\chi(X)& = {\rm det}(X Id-J_{\theta}(x,y))\\
      &=X^2 - \left( \frac{\partial (p_2(x)/yq_2(x))}{\partial x} \cdot
         \frac{\partial (p_1(y)/xq_1(y))}{\partial y} - 2 \right) X + 1,
\end{align*}
and
{\tt fp}=[p1,p2,\ldots,pk] be a basis on the equations satisfied by the fixed points $(x,y)$.
Once again, we use
\begin{center}
  \tt  Groebner[Basis]([p,p1,p2,\ldots,pk], plex(x, y, X))
\end{center}
to obtain an equation $q(X)$ satisfied by $X$, which is an eigenvalue of $J_\theta(x,y)$.
To verify whether the eigenvalues of $J_\theta(x,y)$ are roots of unity, we only need to check whether the irreducible factors of $q(X)$ are cyclotomic polynomials.



To make the above statements easier to understand, we present several examples.
\begin{exm}\label{EXP:irreducible}
Suppose $\mathcal{S}=[\overline{1}\overline{1}, \overline{1}0, 0\overline{1}, 11]$, the corresponding characteristic polynomial is
\[
\frac{1}{xy}+\frac{1}{x}+\frac{1}{y}+xy.
\]
Then we derive
\[
A_{-}(y)=1+\frac{1}{y},\ A_{+}(y)=y,\ B_{-}(x)=1+\frac{1}{x},\ B_{+}(x)=x.
\]
Applying the command {\tt Groebner[Basis]}, we obtain $[-1-x+x^4, y-x]$, which implies that a fixed point $(x,y)$ must satisfy
\[
-1-x+x^4 = 0, \quad y-x=0.
\]
Let $p(X,x,y)$ be the numerator of $\chi(X)$, we get
\[
p(X,x,y)=X^2x^4y^4-Xyx-2Xx-2Xy-4X+2Xx^4y^4+x^4y^4.
\]
%%\begin{align*}
%%p(X,x,y)=& X^2x^2y^2+3X^2x^2y^3+3X^2x^2y^4+X^2x^2y^5+X+4Xy\\
%%         &+6Xy^2+4Xy^3+Xy^4-3Xy^4x^4-Xy^5x^4-Xy^3x^3\\
%%         &-Xx^3y^2+x^2y^2+3x^2y^3+3x^2y^4+x^2y^5.
%%\end{align*}
Using {\tt Groebner[Basis]} once again, we obtain
%%\begin{align*}
%%& {\tt Groebner[Basis]}([p(X,x,y), -1-x+x^4, y-x], {\tt plex}(x, y, X))\\
%%    & =[q(X),q1(X,y),q2(X,x)],
%%\end{align*}
%%where
\[
q(X)=1-19X-X^2-124X^3+3X^4-124X^5-X^6-19X^7+X^8,
\]
implying that the eigenvalues of the Jacobian matrix satisfy $q(X)=0$.
It's easy to check that $q(X)$ is irreducible and not a cyclotomic polynomial. Hence the eigenvalues of the Jacobian matrix are not roots of unity and thus
$\mathcal{S}=[\overline{1}\overline{1}, \overline{1}0, 0\overline{1}, 11]$ is associated with an infinite group.
\end{exm}


%%In practice, when dealing with a two-dimensional model, we may obtain a much more complicated $q(x)$.
The following example deals with a more complicated case.
\begin{exm}
Suppose $\mathcal{S}=[\overline{1}0, \overline{1}1, \overline{1}1, \overline{1}1,0\overline{1}, 11]$.
By similar discussions as in Example~\ref{EXP:irreducible}, we find that the fixed point $(x,y)$ of $\theta$ must satisfy the following two equations:
\[
p1(x)=-3+9x-x^2-6x^3+x^5=0 \text{ and } p2(x,y)=1+3x-x^3+6y=0.
\]
Let $p(X,x,y)$ be the numerator of $\chi(X)$, we get
\begin{align*}
p(X,x,y)=&9X^2y^3x+6X^2y^3x^3+X^2y^3x^5+3X-Xx^2+18Xxy^3\\
&+12Xx^3y^3+2Xx^5y^3+9xy^3+6x^3y^3+x^5y^3.
\end{align*}
Using {\tt Groebner[Basis]} once again, we obtain
\begin{align}\label{EQ:q(X)}
& {\tt Groebner[Basis]}([p(X,x,y), p1(x), p2(x,y)], {\tt plex}(x, y, X))\nonumber\\
& =[q(X),q_1(X,y),q_2(X,x)],
\end{align}
where
\begin{align*}
q(X)=& 27X^{10}-216X^9-2267X^8-7881X^7-15249X^6-18785X^5\\
     & -15249X^4-7881X^3-2267X^2-216X+27,
\end{align*}
\begin{align*}
q_1(X,y)=& -458244+4456350X+33544804X^2+91401861X^3+139937762X^4\\
        & +134228180X^5 +80122341X^6+26311990X^7\\
        & +2933118X^8-337419X^9+44874y
\end{align*}
and
\begin{align*}
q_2(X,x)=& -543942+4825089X+40138304X^2+114480051X^3\\
        & +180619657X^4+177429229X^5+108213837X^6+36257324X^7\\
        & +4134537X^8-470313X^9+22437x.
\end{align*}
It's easy to check that $q(X)$ has two irreducible factors
$
X^2+X+1
$
and
~$
27X^8-243X^7-2051X^6-5587X^5-7611X^4-5587X^3-2051X^2-243X+27.
$
Since the second factor is not a cyclotomic polynomial, we can find $X_0$ which is not a root of unity such that $q(X_0)=0$. Substituting $X$ by $X_0$ in $q1(X,y)$ and $q2(X,x)$, we get $x_0$ and $y_0$ such that
\[
q_1(X_0,y_0)=0\quad {and}\quad q_2(X_0,x_0)=0.
\]
According to Equation~\eqref{EQ:q(X)}, we know that $(x_0,y_0)$ was fixed by $\theta$ and $p(X,x_0,y_0)$ is an equation satisfied by the eigenvalues of $J_{\theta}(x_0,y_0)$.
From Equation~\eqref{EQ:q(X)}, it's easy to verify that $p(X_0,x_0,y_0)=0$.
As $X_0$ is not a root of unity, we know~$\mathcal{S}=[\overline{1}0, \overline{1}1, \overline{1}1, \overline{1}1,0\overline{1}, 1]$ is associated with an infinite group.
\end{exm}

\begin{exm}\label{EX:not determined}
Suppose $\mathcal{S}=[\overline{1}1, \overline{1}1, 1\overline{1}, 10]$, then the corresponding characteristic polynomial is
\[
S(x,y)=\frac{2y}{x}+\frac{x}{y}+x,
\]
and
\[
A_{-}(y)=2y,\ A_{+}(y)=1/y+1,\ B_{-}(x)=x,\ B_{+}(x)=2/x.
\]
Applying the command {\tt Groebner[Basis]}, the output is {\tt [1]} and the method fails.
\end{exm}

By similar discussions as in the above examples, we can show $379$ of all the $409$ two-dimensional models are associated with infinite groups.
There are $30$ models left, such as $\mathcal{S}=[\overline{1}1, \overline{1}1, 1\overline{1}, 10]$ in Example~\ref{EX:not determined}. When canceling the repeated steps, all these models will be reduced to one of the set
$SS=\{\mathcal{A},\mathcal{A}^{r},\mathcal{B},\mathcal{B}^{r},\mathcal{C},\mathcal{C}^{r},\mathcal{D},\mathcal{D}^{r},
\mathcal{E},\mathcal{E}^{r}\}$, the elements of which are the five singular models in Equation \eqref{EQ:five singulars} or their $x/y$ reflection.
The five singular models were proved associated with an infinite group by the valuation argument.

The valuation argument was given by Bousquet-M\'{e}lou and Mishna in~\cite{MelouMishna2010}. In fact, they defined the \emph{valuation} of a Laurent series $F(t)$ to be the smallest $d$ such that $t^d$ occurs in $F(t)$ with a non-zero coefficient. Suppose $z$ is an indeterminate, and $x$, $y$ are Laurent series in $z$ with coefficients in $\bQ$, of respective valuations $a$ and $b$. Assuming that the \emph{trailing} coefficients of these series, namely $[z^a]x$ and $[z^b]y$, are positive. Defining $x'$ by $\phi(x,y)=(x',y)$. Then the trailing coefficient of $x'$ (and $y$) is positive, and it's easy to check that the valuation of $x'$ (and $y$) only depends on $a$ and $b$:
\[
 \Phi(a,b):=(\hbox{val}(x'),\hbox{val}(y))=\begin{cases}
  {\left(-a+b(v_{-1}^{(y)}-v_{1}^{(y)}),b\right)}, & \mbox{if $b \ge 0$}; \\[15pt]
   \left(-a+b(d_{-1}^{(y)}-d_{1}^{(y)}),b\right), & \mbox{if $b \leq 0$};
\end{cases}
\]
where $v_i^{(y)}$ (resp. $d_{i}^{(y)}$) denotes the valuation (resp. degree) in $y$ of $A_i(y)$, for $i=\pm1$.
Similarly, $\psi(x,y)=(x,y')$ is well defined, and the valuations of $x$ and $y'$ only depend on $a$ and $b$:
\[
 \Psi(a,b):=(\hbox{val}(x),\hbox{val}(y'))=\begin{cases}
  {\left(a,-b+a(v_{-1}^{(x)}-v_{1}^{(x)})\right)}, & \mbox{if $a \ge 0$}; \\[15pt]
   \left(a,-b+a(d_{-1}^{(x)}-d_{1}^{(x)})\right), & \mbox{if $a \leq 0$};
\end{cases}
\]
where $v_i^{(x)}$ (resp. $d_{i}^{(x)}$) denotes the valuation (resp. degree) in $x$ of $B_i(x)$, for $i=\pm1$. For a given model $\mathcal{S}$, in order to prove the associated group $G$ is infinite, it suffices to prove that the group $G'$ generated by $\Phi$ and $\Psi$ is infinite. To prove the latter statement, it suffices to exhibit $(a,b)\in\mathbb{Z}^2$ such that the orbit of $(a,b)$ under the action of $G'$ is infinite. For the five singular models, Bousquet-M\'{e}lou and Mishna derived by induction on $n$ that
\[
(\Psi\circ\Phi)^n(1,2)=(2n+1,2n+2)\quad\hbox{ and }\quad
\Phi(\Psi\circ\Phi)^n=(2n+3,2n+2).
\]
Hence the orbit of $(1,2)$ under the action of $\Phi$ and $\Psi$ is infinite, and so are the groups $G'$ and $G$.

It's easy to check that the repeated steps do not change the value of $\Phi(a,b)$ and $\Psi(a,b)$ according to the definition of valuation.
Thus, we can derive that the remaining $30$ models are all associated with infinite groups.

This completes the proof of Theorem \ref{CJ:409}.

%\subsection{Three Dimensional Octant Models}\label{SE:3D}
\subsection{The Proof of Theorem \ref{CJ:20634}}\label{SE:3D}
In this section, we consider the three-dimensional models. The proof of Theorem \ref{CJ:20634} is similar to the proof for the two-dimensional ones.
Indeed, for three-dimensional cases, we could consider $\phi \circ \psi$, $\phi \circ \tau$ and $\psi \circ \tau$,
instead of $\theta = \psi \circ \phi$ in the cases of two-dimensional models. Moreover, we need only to concern two variables by fixing the third variable with any given value.
More precisely, we will set the third variable to be $1/7$.

The following lemma indicates that we only need to consider one of $\phi \circ \psi$ and $\psi \circ \phi$.
\begin{lem}
If the eigenvalues of $J_{\phi \circ \psi}$ are roots of unity, then so are $J_{\psi \circ \phi}$.
\end{lem}
\pf Notice that the determinant of $J_\theta$ is $1$. The eigenvalues of $J_\theta$ are both roots of unity or neither of the eigenvalues is root of unity. Since $(\psi \circ \phi)^{-1} = \phi \circ \psi$, we have
$J_{\phi \circ \psi}^{-1} =  J_{\psi \circ \phi}$. Thus, the eigenvalues of $J_{\phi \circ \psi}$ are the reciprocal of those of $J_{\psi \circ \phi}$ and hence they are both roots of unity or none of them are roots of unity. \qed

By applying the fixed point method as in Section \ref{SE:2D} to the $20634$ three-dimensional models, we are left with $69$ models that can not be proved to have an infinite group.
Project these models to two-dimensional ones (we have three choices) and remove the repeated steps, one can find that they all fall in the set $$SS=\{\mathcal{A},\mathcal{A}^{r},\mathcal{B},\mathcal{B}^{r},\mathcal{C},\mathcal{C}^{r},\mathcal{D},\mathcal{D}^{r},
\mathcal{E},\mathcal{E}^{r}\}.$$ The elements of $SS$ are the five singular models and their $x/y$ reflection.
%The elements of this set are the five singular models which have been proved with an infinite group by the valuation argument.
Thus the remaining $69$ models are all associated with infinite groups.

This completes the proof of Theorem \ref{CJ:20634}.

\section{The non-D-finite Property}

In this section, we mainly discuss the non-D-finite property of the generating function of
the $409$ two-dimensional models associated with an infinite order and give the proof of
Theorem \ref{ND:384}.


As shown in Section~\ref{SE:2D}, by projecting to a plane, these two-dimensional models are reduced to multi-sets of $\{\overline{1},0,1\}^2\setminus \{0,0\}$.
For a $2$D octant model where the $z$-condition is redundant, we focus on the complete generating function
\begin{equation}\label{EQ:genfun2D}
O(x,y;t):=O(x,y,1;t),
\end{equation}
which counts quadrant walks with steps in multiset $S'=\{ij:ijk\in S\}$.
Note that non-D-finiteness of $O(x,y;t)$ implies the non-D-finiteness of $O(x,y,z;t)$.
The main objective of this section is to study the non-D-finite property of $O(x,y;t)$.
We further reduce to consider the non-D-finiteness of the generating function $O(0,0;t)$ of the excursions.


Firstly, we consider the $\emph{nonsingular walks}$, which are walks having at least one step from the set $\{(-1,0), (-1,-1), (0,-1)\}$.
Our proof is a multi-set analogue of the proof given by Bostan $ et\ al.$~\cite{BostanRaschelSalvy2014}, where they proved that the generating function of the excursion corresponding to any of the $51$ nonsingular models having no repeated step and with infinite group were not D-finite.

The non-D-finiteness is based on the asymptotic behavior of the coefficients.
\begin{prop}\label{TH:NotD}{\rm(c.f. Thm. 3 in~\cite{BostanRaschelSalvy2014})}
Let $(a_n)_{n\geq 0}$ be an integer-valued sequence whose $n$-th term $a_n$ behaves
asymptotically like $K\cdot \rho^n\cdot n^{\alpha}$, for some real constant $K>0$. If the growth constant $\rho$ is transcendental, or if the singular exponent $\alpha$ is irrational, then the generating function $A(t)=\sum_{n>0}a_nt^n$ is not D-finite.
\end{prop}

Bostan $ et\ al.$ considered the non-degeneracy of the walk: for all $(i,j)\in \mathbb{N}^2$, the set $\{n\in\mathbb{N} \colon o(i,j;n)\neq 0\}$ is nonempty; furthermore, the walk is said to be $\emph{aperiodic}$ when the gcd of the elements of this set is $1$ for all $(i,j)$. Otherwise, it is $\emph{periodic}$ and this gcd is the period. They restated a result of Denisov and Wachtel~\cite{DenisovWachtel2013} in the following way.

\begin{prop}\label{TH:asymptotic}
Let $\mathcal{S}\subset\{0,\pm1\}^2$ be the step set of a walk in the quarter plane $\mathbb{N}^2$, which is not contained in a half-plane. Let $e_n$ denote the number of excursions of length $n$ using only steps in $\mathcal{S}$, and let $\chi$ denote the characteristic polynomial $\sum_{(i,j)\in\mathcal{S}}x^iy^j$ of the step set $\mathcal{S}$. Then the system
\begin{equation}\label{eq-chi}
\frac{\partial\chi}{\partial x}=\frac{\partial\chi}{\partial y}=0
\end{equation}
has a unique solution $(x_0,y_0)\in\mathbb{R}_{>0}^2$. Next, define
\begin{equation}\label{eq-alpha}
\rho:=\chi(x_0,y_0),\quad c:=\frac{\frac{\partial^2\chi}{\partial x\partial y}}{\sqrt{\frac{\partial^2\chi}{\partial x^2}\cdot\frac{\partial^2\chi}{\partial y^2}}}(x_0,y_0),\quad \alpha:=-1-\frac{\pi}{\arccos(-c)}.
\end{equation}
Then there exists a constant $K>0$, which only depends on $\mathcal{S}$, such that
\begin{itemize}
\item
if the walk is aperiodic, then
$e_n\sim K\cdot\rho^n\cdot n^{\alpha}.$
\item
if the walk is periodic (then of periodic $2$), then
\[e_{2n}\sim K\cdot\rho^{2n}\cdot(2n)^\alpha,\quad e_{2n+1}=0.\]
\end{itemize}
\end{prop}

%Then they gave an algorithmic proof that for any of the $51$ nonsingular models confined to the positive quadrant, the singular exponent $\alpha$ in the asymptotic expansion of excursion sequence was an irratinal number. Thus by the above two theorems, the generating function $O(0,0;t)$ is not D-finite.

To prove this proposition,
Bostan et al.~\cite{BostanRaschelSalvy2014} assigned each step with a probability $x_0^iy_0^j/\chi(x_0,y_0)$ so that the expectation of the movement is zero. This condition leads to the equations~\eqref{eq-chi}. Once the probability model is set up, the asymptotic estimation is obtained by considering the exist time of the random walk.

Now consider the case when the set $\mathcal{S}$ is replaced by a multi-set. In this case, we shall assign each step with a probability $r_{i,j}x_0^iy_0^j/\chi(x_0,y_0)$, where $r_{i,j}$ was the multiplicity of $(i,j)\in\mathcal{S}$. Then Bostan's augment works smoothly for the rest parts. We thus see that Proposition~\ref{TH:asymptotic} still holds when $\mathcal{S}$ is a multi-set.

By Propositions~\ref{TH:NotD} and \ref{TH:asymptotic}, if $\alpha$ given by \eqref{eq-alpha} is not a rational number, then the excursion generating function $O(0,0;t)$ is not D-finite. Bostan also presented an algorithm to determine whether $\alpha$ is rational. We apply this algorithm to the $366$ non-singular models of dimensional two. It turns out that all of them correspond to irrational $\alpha$. Hence the generating function of these models are not D-finite.

The algorithmic irrationality proof fails for the $43$ singular models, which were listed in the Appendix, Table~\ref{TB:43}. However, we find that all these models can be reduced to one of the $5$ singular models or their $x/y$ symmetry, when getting rid of the repeated steps.
The $5$ singular models were proved to have non-D-finite generating function by Mishna and Rechnitzer~\cite{MishnaRechnitzer2009} and Melczer and Mishna~\cite{MelczerMishna2014} using the iterated kernel method, a variant of the kernel method.

As we know, $\mathcal{A}=[[-1,1],[1,-1],[1,1]]$ is one of the $5$ singular models and its generating function is not D-finite. Now we rewrite the complete generating function of $\mathcal{A}$ into the following form:
\[
O(x,y;t)=\sum_{\substack{n_1,n_2,n_3\geq 0 }}o(n_1,n_2,n_3)x^{ -n_1+n_2+n_3}y^{n_1-n_2+n_3}t^{n_1+n_2+n_3},
\]
where $o(n_1,n_2,n_3)$ denotes the number of walks in the quarter plane with the $i$-th element of $\mathcal{A}$ appears $n_i$ times. Then it's easy to see that $(-n_1+n_2+n_3,\ n_1-n_2+n_3)$ denotes the ending point. Suppose $\mathcal{A^{'}}$ is a multi-set which can be reduced to $\mathcal{A}$ through getting rid of the repeated steps, and the $i$-th element of $\mathcal{A}$ repeats $r_i$ times in $\mathcal{A^{'}}$. Then the complete generating function for $\mathcal{A^{'}}$ can be given as
\[
O'(x,y;t)=\sum_{\substack{n_1,n_2,n_3\geq 0}}r_1^{n_1}r_2^{n_2}r_3^{n_3}o(n_1,n_2,n_3)x^{ -n_1+n_2+n_3}y^{n_1-n_2+n_3}t^{n_1+n_2+n_3}.
\]
It's easy to verify that
\[
O'(x,y;t)=O(\sqrt{\frac{r_3}{r_1}}x,\sqrt{\frac{r_3}{r_2}}y;\sqrt{r_1r_2}t),
\]
which implies that $O'(x,y;t)$ is not D-finite, since algebraic substitution does not change the D-finite property. There are $7$ of the $43$ singular models can be reduced to $\mathcal{A}=[[-1,1],[1,-1],[1,1]]$ or its $x/y$ symmetry $\mathcal{A}^{r}$.
The above discussions show that the corresponding generating function for these $7$ models are all not D-finite.

Similar discussions for $\mathcal{C}=[[-1,1],[1,-1],[0,1]]$ will lead to the non-D-finiteness of the generating functions for another $11$ singular models. From Table~\ref{TB:43}, we can see that models numbered $19,27$ and $40$ are in fact $\mathcal{B},\mathcal{D}$ and $\mathcal{E}$ in Equation~\eqref{EQ:five singulars}, thus the generating functions are not D-finite.


At this stage, we have shown that the generating functions of the $366$ nonsingular models and $21$ of all the $43$ singular models have non-D-finite generating functions. According to this fact and results from~\cite{KurkovaRaschel2011,BostanRaschelSalvy2014,MelczerMishna2014,MishnaRechnitzer2009}, we make the following conjecture.
\begin{conj}
The generating functions of the $43$ singular models, in Table~\ref{TB:43}, are all non-D-finite.
\end{conj}


\subsection*{Acknowledgements}
 We wish to thank Professor Manuel Kauers for helpful suggestions. This work was supported by the 973 Project, the PCSIRT Project of the Ministry of Education and the National Science Foundation of China.
%the 973 Project, the PCSIRT Project of the Ministry of
%Education,  and the National Science Foundation of China
%--------------------------------------------------------------------

\begin{thebibliography}{99}
\bibitem{BBKM2015}
A.~Bostan, M.~Bousquet-M\'{e}lou, M.~Kauers and S.~Melczer,
 \newblock On~$3$-dimensional lattice walks confined to the positive octant,
 \newblock {\em Ann. Comb.} 2015. \arxiv{1409.3669}.

\bibitem{BostanKauers2010}
A.~Bostan and M.~Kauers,
 \newblock The complete generating function for {G}essel walks is algebraic,
\newblock {\em Proc. Amer. Math. Soc.} \textbf{138(9)}, 3063--3078 (2010).
With an appendix by Mark van Hoeij.

\bibitem{BostanRaschelSalvy2014}
A.~Bostan, K.~Raschel and B.~Salvy,
 \newblock Non-D-finite excursions in the quarter plane,
\newblock {\em J. Combin. Theory Ser. A.}\textbf{121}, 45--63 (2014).



\bibitem{MelouMishna2010}
M.~Bousquet-M{\'e}lou and M.~Mishna,
 \newblock Walks with small steps in the quarter plane,
\newblock {\em In Algorithmic probability and combinatorics, Contemp. Math.} \textbf{520}, 1--39 (2010).


\bibitem{Buchberger1965}
B.~Buchberger,
 \newblock Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal.
\newblock {\em J. Symbolic Compt.} \textbf{41(3)}, 475--511 (2006).

\bibitem{CoxLittleO'shea1992}
D.~Cox, J.~Little and D. O'shea,
 \newblock {\em  Ideals, Varieties, and Algorithms}, 3rd ed.
Springer, New York, 2013.


\bibitem{DenisovWachtel2013}
D.~Denisov and V.~Wachtel,
 \newblock Random walks in cones. 
 \newblock {\em Ann.Probab.}
\textbf{43(3)}, 992--1044 (2015).



\bibitem{GesselZeilberger1992}
I.M. Gessel and D.~Zeilberger,
 \newblock Random walk in a Weyl chamber,
\newblock {\em Proc. Amer. Math. Soc.} \textbf{115(1)}, 27--31 (1992).

\bibitem{KurkovaRaschel2011}
I.~Kurkova and K.~Raschel,
 \newblock Explicit expression for the generating function counting Gessel's   walks,
\newblock {\em Adv. in Appl. Math.} \textbf{47(3)}, 414--433 (2011).

\bibitem{Maher1978}
M.A. Maher,
 \newblock Random walks on the positive quadant,
ProQuest LLC, Ann Arbor, MI, 1978.
Thesis (Ph.D.)--University of Rochester.

\bibitem{MelczerMishna2014}
S.~Melczer and M.~Mishna,
 \newblock Singularity analysis via the iterated kernel method,
\newblock {\em Combin. Probab. Comput.} \textbf{23(5)}, 861--888 (2014).


\bibitem{Mishna2009}
M.~Mishna,
 \newblock Classifying lattice walks restricted to the quarter plane,
\newblock {\em J. Combin. Theory Ser. A.} \textbf{116(2)}, 460--477 (2009).

\bibitem{MishnaRechnitzer2009}
M.~Mishna and A.~Rechnitzer,
 \newblock Two non-holonomic lattice walks in the quarter plane.
\newblock {\em Theoret. Comput. Sci.} 410(38-40), 3616--3630 (2009).


\bibitem{Mohanty1979}
S.G. Mohanty,
 \newblock {\em  Lattice path counting and applications},
Academic Press [Harcourt Brace Jovanovich, Publishers], New
  York-London-Toronto, Ont., 1979.
Probability and Mathematical Statistics.

\bibitem{Narayana1979}
T.V. Narayana,
 \newblock {\em Lattice path combinatorics with statistical applications},
Mathematical Expositions Ser.
University of Toronto Press, Toronto, Ont., 1979.

\bibitem{Raschel2012}
K.~Raschel,
 \newblock Counting walks in a quadrant: a unified approach via boundary value
  problems,
\newblock {\em J. Eur. Math. Soc.}\textbf{14(3)}, 749--777 (2012).

\bibitem{Stanley1980}
R.P. Stanley,
 \newblock Differentiably finite power series,
\newblock {\em European J. Combin.} \textbf{1(2)}, 175--188 (1980).

\bibitem{Wang2002}
D.~M. Wang,
 \newblock Epsilon: A Library of Software Tools for Polynomial Elimination. A. M.
Cohen, X.-S. Gao, N. Takayama. 
\newblock {\em Proceedings of the First International Congress of
Mathematical Software - ICMS 2002, Aug 2002,} P\'{e}kin, Chine, World Scientific, pp.379--389 (2002).


\end{thebibliography}


{\section*{Appendix}\label{SECT:appendix}

\begin{longtable}{|c|l|c|}
\hline \rule{0pt}{5pt}
{\small Number} & {\small Models} & {\small Reduced Models} \\ [3pt]
\hline \rule{0pt}{5pt}
$1$
&
$[[-1, 1], [1, -1], [1, 1]]$
&
\\[3pt]
$2$
&
$[[-1, 1], [-1, 1], [1, -1], [1, 1]]$
&
\\[3pt]
$3$
&
$[[-1, 1], [1, -1], [1, 1], [1, 1]]$
&
\\[3pt]
$4$
&
$[[-1, 1], [-1, 1], [-1, 1], [1, -1], [1, 1]]$
&
$[[-1, 1], [1, -1], [1, 1]]$
\\[3pt]
$5$
&
$[[-1, 1], [-1, 1], [1, -1], [1, -1], [1, 1]]$
&
\\[3pt]
$6$
&
$[[-1, 1], [-1, 1], [1, -1], [1, 1], [1, 1]]$
&
\\[3pt]
$7$
&
$[[-1, 1], [-1, 1], [1, -1], [1, 1], [1, -1], [1, 1]]$
&
\\[3pt]
\hline
$8$
&
$[[-1, 1], [0, 1], [1, -1]]$
&
\\[3pt]
$9$
&
$[[-1, 1], [-1, 1], [0, 1], [1, -1]]$
&
\\[3pt]
$10$
&
$[[-1, 1], [-1, 1], [1, -1], [1, 0]]$
&
\\[3pt]
$11$
&
$[[-1, 1], [0, 1], [0, 1], [1, -1]]$
&
\\[3pt]
$12$
&
$[[-1, 1], [-1, 1], [-1, 1], [0, 1], [1, -1]]$
&
\\[3pt]
$13$
&
$[[-1, 1], [-1, 1], [-1, 1], [1, -1], [1, 0]]$
&
$[[-1, 1], [1, -1], [0, 1]]$
\\[3pt]
$14$
&
$[[-1, 1], [-1, 1], [0, 1], [0, 1], [1, -1]]$
&
\\[3pt]
$15$
&
$[[-1, 1], [-1, 1], [0, 1], [1, -1], [1, -1]]$
&
\\[3pt]
$16$
&
$[[-1, 1], [-1, 1], [1, -1], [1, 0], [1, 0]]$
&
\\[3pt]
$17$
&
$[[-1, 1], [-1, 1], [-1, 1], [0, 1], [0, 1], [1, -1]]$
&
\\[3pt]
$18$
&
$[[-1, 1], [-1, 1], [0, 1], [0, 1], [1, -1], [1, -1]]$
&
\\[3pt]
\hline
$19$
&
$[[-1, 1], [0, 1], [1, -1], [1, 0]]$
&
\\[3pt]
$20$
&
$[[-1, 1], [-1, 1], [0, 1], [1, -1], [1, 0]]$
&
\\[3pt]
$21$
&
$[[-1, 1], [0, 1], [0, 1], [1, -1], [1, 0]]$
&
\\[3pt]
$22$
&
$[[-1, 1], [-1, 1], [-1, 1], [0, 1], [1, -1], [1, 0]]$
&
\\[3pt]
$23$
&
$[[-1, 1], [-1, 1], [0, 1], [0, 1], [1, -1], [1, 0]]$
&
$[[-1, 1], [1, -1], [0, 1], [1, 0]]$
\\[3pt]
$24$
&
$[[-1, 1], [-1, 1], [0, 1], [1, -1], [1, -1], [1, 0]]$
&
\\[3pt]
$25$
&
$[[-1, 1], [-1, 1], [0, 1], [1, -1], [1, 0], [1, 0]]$
&
\\[3pt]
$26$
&
$[[-1, 1], [0, 1], [0, 1], [1, -1], [1, 0], [1, 0]]$
&
\\[3pt]
\hline
$27$
&
$[[-1, 1], [0, 1], [1, -1], [1, 1]]$
&
\\[3pt]
$28$
&
$[[-1, 1], [-1, 1], [0, 1], [1, -1], [1, 1]]$
&
\\[3pt]
$29$
&
$[[-1, 1], [-1, 1], [1, -1], [1, 0], [1, 1]]$
&
\\[3pt]
$30$
&
$[[-1, 1], [0, 1], [0, 1], [1, -1], [1, 1]]$
&
\\[3pt]
$31$
&
$[[-1, 1], [0, 1], [1, -1], [1, 1], [1, 1]]$
&
\\[3pt]
$32$
&
$[[-1, 1], [-1, 1], [-1, 1], [0, 1], [1, -1], [1, 1]]$
&
\\[3pt]
$33$
&
$[[-1, 1], [-1, 1], [-1, 1], [1, -1], [1, 0], [1, 1]]$
&
$[[-1, 1], [1, -1], [0, 1], [1, 1]]$
\\[3pt]
$34$
&
$[[-1, 1], [-1, 1], [0, 1], [0, 1], [1, -1], [1, 1]]$
&
\\[3pt]
$35$
&
$[[-1, 1], [-1, 1], [0, 1], [1, -1], [1, -1], [1, 1]]$
&
\\[3pt]
$36$
&
$[[-1, 1], [-1, 1], [0, 1], [1, -1], [1, 1], [1, 1]]$
&
\\[3pt]
$37$
&
$[[-1, 1], [-1, 1], [1, -1], [1, 0], [1, 0], [1, 1]]$
&
\\[3pt]
$38$
&
$[[-1, 1], [-1, 1], [1, -1], [1, 0], [1, 1], [1, 1]]$
&
\\[3pt]
$39$
&
$[[-1, 1], [0, 1], [0, 1], [1, -1], [1, 1], [1, 1]]$
&
\\[3pt]
\hline
$40$
&
$[[-1, 1], [0, 1], [1, -1], [1, 0], [1, 1]]$
&
\\[3pt]
$41$
&
$[[-1, 1], [-1, 1], [0, 1], [1, -1], [1, 0], [1, 1]]$
&
$[[-1, 1], [1, -1], [0, 1], [1, 0], [1, 1]]$
\\[3pt]
$42$
&
$[[-1, 1], [0, 1], [0, 1], [1, -1], [1, 0], [1, 1]]$
&
\\[3pt]
$43$
&
$[[-1, 1], [0, 1], [1, -1], [1, 0], [1, 1], [1, 1]]$
&
\\[3pt]
\hline
\caption{$43$ singular models.}\label{TB:43}

\end{longtable}



\end{document}
