% EJC papers *must* begin with the following two lines. 
\documentclass[12pt,a4paper,leqno]{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,amsfonts}

% 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{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\usepackage{latexsym}
\usepackage[utf8]{inputenc}
\usepackage{stmaryrd}
\usepackage{mathtools}
\usepackage{tikz,pgf}
\usepackage{tikzscale}
\usetikzlibrary{arrows,shapes,calc,decorations.pathreplacing,matrix,positioning}
\tikzstyle{every picture}+=[remember picture]
\newcommand*{\getlength}[2]{\pgfmathsetmacro#1{0.0351459804*#2}}%  Result in `cm`
\setcounter{MaxMatrixCols}{30}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


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

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

\title{\bf Combinatorics meets potential theory}

% 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{Philippe D'Arco \\
\small Institut des Sciences de la Terre de Paris\\[-0.8ex]
\small Université Pierre et Marie Curie\\[-0.8ex] 
\small Paris, France\\
%\small\tt philippe.darco@upmc.fr\\
\and Valentina Lacivita \\
\small Institut du Calcul et de la Simulation\\[-0.8ex]
\small Institut des Sciences de la Terre de Paris\\[-0.8ex]
\small Université Pierre et Marie Curie\\[-0.8ex] 
\small Paris, France\\
%\small\tt valentina.lacivita@upmc.fr\\
\and  Sami Mustapha\\%\thanks{\textit{2010 Mathematics Subject Classification} Primary 05A16, Secondary 60G50.} \\
\small Centre de Mathématiques de Jussieu\\[-0.8ex]
\small Université Pierre et Marie Curie\\[-0.8ex]
\small Paris, France\\
\small\tt sam@math.jussieu.fr
}

\date{\dateline{submission date}{acceptance date}\\
\small Mathematics Subject Classifications: 05A16,60G50}

%\date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\
%\small Mathematics Subject Classifications: 05C88, 05C89}

\begin{document}

\maketitle

\begin{abstract}

Using potential theoretic techniques, we show how it is possible to determine
the  dominant asymptotics for the number of walks of length $n$, restricted to
the positive quadrant and taking  unit steps in a ``balanced'' set $\Gamma$.
The approach is illustrated through an example of inhomogeneous space walk.
This walk takes its steps in $\{ \leftarrow, \uparrow,  \rightarrow,
\downarrow \}$ or  $\{ \swarrow, \leftarrow, \nwarrow, \uparrow, \nearrow,
\rightarrow, \searrow, \downarrow \}$, depending on the parity of the
coordinates of its positions.  The exponential growth of our model is
$(4\phi)^n$, where  $\phi= \frac{1+\sqrt 5}{2}$ denotes the Golden ratio,
while the subexponential growth is like $1/n$. As an application of our
approach we prove the non-D-finiteness in two dimensions of the length
generating functions corresponding to nonsingular small step  sets with an
infinite group and zero-drift.

\bigskip\noindent \textbf{Keywords:} Lattice path enumeration, analytic
combinatorics in several variables, discrete potential theory, discrete
harmonic functions.

\end{abstract}


\section{Introduction} 

Counting lattice walks in a fixed region $\mathcal{ R} \subset
\mathbb{Z}^2$ is one of the most fundamental topics in enumerative
combinatorics. In recent years, the case of walks  confined to the
first quadrant $ \mathcal{Q}=\{(x,y)\in {\mathbb{Z}}^2; \,\, x> 0, \,
y > 0\}$  has been a subject of several important works (see
\cite{BK,BK1,BRS,B3,BM,BP,FR1,KR,KR2,MM,M,MR}).
 
Given a  set $\Gamma$ of allowed steps, the basic enumerative question
is to determine the number of walks confined to $\mathcal{Q}$,
starting from $(x,y) \in \mathcal{Q}$, having length $n=1,2,\dots$ and
taking steps in $\Gamma$ only. A walk in which the set of allowable
steps $\Gamma$ is contained in $\{ \swarrow, \leftarrow, \nwarrow,
\uparrow, \nearrow, \rightarrow, \searrow, \downarrow \}$ is said to
have small steps.

The enumeration of small steps walks restricted to the positive
quadrant  has focused primarily on the associated generating
functions. In contrast  with the corresponding $1$-dimensional
problem, where the generating functions are always
algebraic~\cite{BF,B2,D}, in the $2$-dimensional case, depending on
the choice of the set $\Gamma$, the generating functions  may be
algebraic, D-finite and some times not even D-finite~\cite{B1,B3,BP}.

Three fundamental works should be mentioned. Firstly,  the seminal
work of Bousquet-Mélou and Mishna~\cite{BM} (see also \cite{M})
initiating a complete classification of small steps walks in
$\mathcal{Q}$ and showing that the nature of the generating function
is correlated to the finiteness of a certain group of $2$-dimensional
transformations associated with $\Gamma$.  Bousquet-Mélou and Mishna
proved that among the 256 possible small-step walks, there are exactly
79 different models (up to symmetries) and 23 have a finite
group. Among the 23, they proved that 22 models have D-finite
generating functions (the 23rd was shown algebraic in \cite{BK1}).
Secondly, the Kurkova and Raschel result~\cite{KR2} proving a
conjecture of Bousquet-Mélou and Mishna about the non-D-finiteness
of the trivariate generating function which takes into account the
length of the walk and the position of its endpoint   for the $51$
nonsingular models among the $56$ with infinite groups. 
The remaining 5 models were shown to have non-D-finite length generating functions by Mishna and Rechnitzer~\cite{MR} and Melczer and Mishna~\cite{MM1}.
Thirdly, the Bostan \textit{et al.} result~\cite{BRS} establishing  the
non-D-finiteness of excursions generating functions for the same $51$
nonsingular walks  (the nature of the length generating function for
all quadrant walks is still unknown in those 51 cases).

After the important progress made on understanding small steps
quadrant walks, efforts are now deployed to move one dimension  higher
(small steps walks in octants~\cite{BMKM}) and to address walks with
big jumps (see \cite{BP,FR2}).

A natural question about quadrant walks that has not received any
special attention despite its interest provided the first motivation
for this paper. What does happen if we let the set where the walk
takes its steps depend on its positions?

At first glance, it might seem difficult to investigate inhomogeneous
space walks  because of the great difficulty of analysis of their
generating functions~\cite{LRV}.  A further major difficulty that
appears in the non-homogeneous case is that paths are no longer
equally probable and it is no longer possible to use the counting
formula relating the enumeration problem to the survival probability
in the quadrant to count them (see \cite{DW}).

Our aim is to offer an alternative approach allowing us to investigate
quadrant walks.  To explain the underlying principle we choose to
present this approach through an example. However, our method has a
more general scope and applies in higher dimension  and for models
with longer steps. It relies on a systematic use of tools and
techniques  from discrete potential theory developed in
\cite{KT,M1,M2}. It assumes a centering condition  and requires the
construction of an appropriate harmonic function whose existence is
difficult  to establish in full generality. Nevertheless, if we
restrict ourselves to the homogeneous case,  the method applies quite
generally and offer an alternative to the probabilistic approach.
This allows us to answer some open questions in the subject. We show
in particular in \S 5, that  for the three models with nonsingular
small step set, zero-drift and infinite group (among the 51
nonsingular models considered in \cite{BRS}) the length generating
function is not D-finite.

\section{Model description and main result}

We consider walks that starts at $(x,y) \in \mathcal{Q}$ and  take
their steps $w=w_1,w_2,\dots$ in variable multi-sets $\Gamma \subset
\{ \swarrow, \leftarrow, \nwarrow, \uparrow, \nearrow, \rightarrow,
\searrow, \downarrow \}$  which depend on the position of
$W_j=\sum_{i=1}^j w_i$. We denote by ${\mathcal{Q}}(x,y)$ the set  of
all walks that stay in ${\mathcal{Q}}$ and by $ {\mathcal{Q}}_n(x,y)
\subset {\mathcal{Q}}(x,y)$ the subset of walks of length $n$. The
main quantity we investigate is $\nu_n(x,y)=| {\mathcal{Q}}_n(x,y)|$.

We shall denote by  $\nu_n(x,y; x',y')$ the number of walks $\in
{\mathcal{Q}}_n(x,y)$ ending at $(x',y')\in {\mathcal{Q}}$. The
sequence  $\left(\nu_n(x,y)\right)_{n\in \mathbb{N}}$ satisfies a
multivariate recurrence with non-constant coefficients:
\begin{align*}%\label{eq1}
\nu_{n+1}(x,y) &= \sum_{(x',y')\in {\mathcal{Q}}}
\nu_{n+1}(x,y; x',y') \\ \nonumber
&= \sum_{(x',y')\in {\mathcal{Q}}} \sum_{(h,k)\in \Gamma(x,y)}
\nu_{n}(x+h,y+k; x',y') \\ \nonumber
&= \sum_{(h,k)\in \Gamma(x,y)} \sum_{(x',y')\in {\mathcal{Q}}}
\nu_{n}(x+h,y+k; x',y') \\ \nonumber
&= \sum_{(h,k)\in \Gamma(x,y)} \nu_{n}(x+h,y+k).
\end{align*}
Taking into account the obvious relations, $\nu_0(x,y)=1$, 
$(x,y) \in \mathcal{Q}$ and $\nu_n(x,y)=0$ if $x<0$ or $y<0$, 
we obtain that $\nu_n(x,y)$ is a solution of the following equation,
\begin{equation}\label{eq2}
  \nu_{n+1}(x,y) = \sum_{(h,k) \in \Gamma(x,y) } 
  \nu_n(x+h,y+k),  \,\,\,\,
  \textrm{ for all }  (n;(x,y))\in {\mathbb{N}}
  \times {\mathcal{Q}}
\end{equation}
with:
\begin{equation}\label{eq3}
  \left\{
  \begin{array}{ccc}
  \nu_n(x,y)= 0 &\textrm{ if } &  (x,y)\in \partial  \mathcal{Q},
  \\ \\
  \nu_0(x,y)=1  &\textrm{ for all } & (x,y)\in 
  {\mathcal{Q}},
  \end{array}
  \right.
\end{equation}
Equation \eqref{eq2} combined with the boundary conditions \eqref{eq3}
uniquely determines the sequence $\nu_n(x,y)$ (see Figure~\ref{fig2} 
which gives the number of walks starting from $(1,1)$ and ending 
at $(x',y')$, for $(x',y') \in \llbracket  1,14 \rrbracket \times
\llbracket  1,14  \rrbracket$).


A general principle in combinatorics consists in introducing, for a
fixed  $(x,y)\in {\mathcal{Q}}$, the trivariate generating
power series of the sequence $\nu_n(x,y; x',y')$
\begin{equation}\label{eq4}
F_{x,y}(t;\xi, \eta)=
\sum_{n\geq 0} \left(\sum_{(x',y')\in {\mathcal{Q}}}
\nu_n(x,y; x',y') \xi^{x'}\eta^{y'}\right) t^n.
\end{equation}

We use the notation $F_{x,y}$ to highlight the dependence of the
generating function on the starting point $(x,y)$. It is the
will to understand this dependence that explains our formulation
of the counting problem.

As $\nu_n(x,y; x',y') =0$ as soon as $|x-x'|>n$ or $|y-y'|>n$, the
inner sum in \eqref{eq4} is finite, and $ F_{x,y}(t;\xi, \eta)$ can be
identified with a power series in $t$ with coefficients in
${\mathbb{Q}}[\xi,\eta]$. Choosing $\xi=\eta=1$ yields a power series
whose coefficients count the quadrant walks with prescribed
number of steps. In the classical theory  the growth of the
coefficients of the generating functions is related to  the location
and nature of their singularities~\cite{FO,FS}.  The
generating function methodology, however, seems difficult to implement
in the case of spatially inhomogeneous walks, the recurrences in
\eqref{eq2} being built with ``variable'' coefficients.

In order to make a first step towards understanding spatially
inhomogeneous walks we investigate a new model of walks, taking their
steps $w=w_1,w_2,\dots w_j,\dots$ alternately in one of the two multi-
set $$ \Gamma_{\mbox{even}}= \{  \leftarrow, \uparrow,  \rightarrow,
\downarrow \}\,\subset \Gamma_{\mbox{odd}}= \{ \swarrow, \leftarrow,
\nwarrow, \uparrow, \nearrow, \rightarrow, \searrow, \downarrow \}$$
according to the following rule: if  $ W_j=\sum_{i=1}^jw_i=(x,x+2k),$
$k\in \mathbb{Z}$, then the step $w_{j+1}$ is taken from $
\Gamma_{\mbox{even}}$ and it is taken from  $\Gamma_{\mbox{odd}}$
otherwise (see Figure \ref{fig1}). We call them {\it golden walks}.


It is well known that the number of $n$-steps walks on the square
lattice, with $\leftarrow, \uparrow, \rightarrow$ and $\downarrow$ 
steps (this is the so-called P\'olya walk) that start from
the origin and stay in the first quadrant grows like ${4^n}/{n}$.
On the other hand, the number of $n$-steps quadrant walks taking their
steps in the full set $\{ \swarrow, \leftarrow, \nwarrow, \uparrow,
\nearrow, \rightarrow, \searrow, \downarrow \}$ (the so-called King
walk) grows like ${8^n}/{n}$. In our model the P\'olya walk is
modified so that it is allowed to move from the points whose
coordinates are of opposite parity in the four additional directions
$\swarrow, \nwarrow, \nearrow$ and $\searrow$. How does the
asymptotics of walks of length $n$, restricted to the positive
quadrant, change?
%It may be expected 
%that this number will have an intermediate growth between 
%$ {4^n}/{n}$  and   $ {8^n}/{n}$.
    
\begin{figure}

\begin{center}
\tikzstyle{every picture}+=[remember picture]
\begin{tikzpicture}[,scale=0.5]
  \draw (0,0) -- (8,0);
  \draw (0,0) -- (0,8);
  \draw[->] (0,8) -- (0,9);
  \draw[->] (8,0) -- (9,0);
  \foreach \x in {1,...,8} \draw (\x,0) -- (\x,0.2);
  \foreach \x in {1,...,8} \draw (0,\x) -- (0.2,\x);
  \foreach \x in {1,...,8}{ 
      \foreach \y in {1,...,8}{ 
         \pgfmathadd {\x}{\y};
         \pgfmathparse{Mod(\pgfmathresult,2))==0?1:0}
         \ifnum\pgfmathresult=1 
    	    \draw (\x,\y) circle(0.1cm);
         \else
          \draw (\x,\y) circle(0.065cm); 
	       \fi
      }
  }
  \draw[red, line width=0.3mm,->] (5,7) -- (5,8); 
  \draw[red, line width=0.3mm,->] (5,7) -- (6,7);
  \draw[red, line width=0.3mm,->] (5,7) -- (4,7); 
  \draw[red, line width=0.3mm,->] (5,7) -- (5,6);

  \draw[green, line width=0.3mm,->] (7,6) -- (7,7); 
  \draw[green, line width=0.3mm,->] (7,6) -- (7,5);
  \draw[green, line width=0.3mm,->] (7,6) -- (6,6); 
  \draw[green, line width=0.3mm,->] (7,6) -- (8,6);
  \draw[green, line width=0.3mm,->] (7,6) -- (8,7); 
  \draw[green, line width=0.3mm,->] (7,6) -- (8,5);
  \draw[green, line width=0.3mm,->] (7,6) -- (6,7); 
  \draw[green, line width=0.3mm,->] (7,6) -- (6,5);

  \draw[line width=0.5mm,-> ](1,1)--(2,1)--(2,2)--(2,3)--(3,3)--(3,2)--(4,2)--(4,3)--(5,3)--(5,4)--(4,4)--(3,4)--(3,5)--(2,5)--(3,6);
  \draw[line width=0.5mm,dotted, -> ](1,1)--(1,2)--(2,3)--(3,2)--(4,3)--(5,2)--(6,3)--(5,4)--(6,5)--(5,6)--(4,5)--(3,4)--(2,5)--(2,6)--(3,6);
\end{tikzpicture}
\end{center}

\caption{\label{fig1} Two golden paths among the 238525020 14-steps quadrant
paths, starting from $(1,1)$ and  ending at $(3,6)$. The path corresponding to
the solid line is much more likely than the dotted one (it has probability
$2^{-36}$ vs $2^{-40}$ for the dotted path).}

\end{figure}   

The answer is given by
\begin{theorem}\label{thm1}
  There exist $C,\, c>0$ such that 
  \begin{equation}\label{eq5}
    \frac{\left(4\phi\right)^n xy}{Cn}\leq \nu_n(x,y) \leq
    C\frac{\left(4\phi\right)^n xy}{n}
  \end{equation}
  for all $(x,y) \in {\mathcal{Q}}$ satisfying $x, \, y \leq c\sqrt n,\,\,
  n=1,2,\dots$ and where $\phi= \frac{1+\sqrt 5}{2}$ denotes the Golden ratio.
\end{theorem}

The following remarks may be helpful in placing the above theorem in
the right perspective.

(i) As we are interested mainly by the asymptotic behavior of
$\nu_n(x,y)$, $n\rightarrow \infty$, the condition $x, \, y \leq
c\sqrt n$ is not really restrictive.

(ii) The factor $ \left(4\phi\right)^n$ that appears in \eqref{eq5}
is related to the number of unrestricted paths of length $n$ (see \S
3.2. below). The same factor appears in the estimates of the number of
$n$-steps paths confined to the half-space ${\mathcal{H}}=\{(x,y) \in
{\mathbb{Z}}^2,\,\,y\geq 0\} $ and starting at $(x,y)\in
{\mathcal{H}}$. Note this number $\nu^{\mathcal{H}}_n(x,y)$. Our
method allows to show that
\begin{equation}\label{eq6}
  \frac{\left(4\phi\right)^n y}{C\sqrt{n}}\leq 
  \nu^{\mathcal{H}}_n(x,y) \leq
  C\frac{\left(4\phi\right)^n y}{\sqrt{n}},\,\,\,\,y \leq c\sqrt n.
\end{equation}

(iii) It is important to clarify the connection between the functions
$u(x,y)= xy$, $u^{\mathcal{H}}(x,y)= y$ and the factors  $1/n$ and
$1/\sqrt n$  that appear in the lower and upper bounds  of \eqref{eq5}
and \eqref{eq6}. It will be shown in \S 3.1 below that the function $
u $ satisfies a discrete  heat type equation (see Eq. \eqref{eq10} below).
Moreover, it is positive and vanishes on $ \partial {\mathcal{Q}}$.
The same kind of verification is easily done with $u^{\mathcal{H}}$
which vanishes on $\partial {\mathcal{H}}$. The existence and
uniqueness of discrete harmonic functions was recently established, in
a related context, for spatially inhomogeneous random walks on
orthants in ${\mathbb{Z}}^d$~\cite{BMS}. The same reasoning used in
\cite{BMS}, based on an analog of Theorem~\ref{thm3} below, allows to show in
the case here considered the uniqueness (up to multiplicative
constants) of time-independent positive solutions of Eq. \eqref{eq10}
vanishing on  $\partial{\mathcal{Q}}$. In terms of the function $u$
(resp. $u^{\mathcal{H}}$) the factor $1 / n$ (resp. $1/\sqrt n$) can
be interpreted as $$\frac{1}{u(\sqrt n , \sqrt n )},\,\,\,\,\,\,\,
\left( \mbox{resp. } \,\,\,  \frac{1}{u^{\mathcal{H}}(\sqrt n , \sqrt
n )} \right) $$  and the quotient $xy/n$ (resp.  $y/n$) as
$$\frac{u(x,y)}{u(\sqrt n , \sqrt n )},\,\,\,\,\,\,\, \left(
\mbox{resp. } \,\,\,  \frac{
u^{\mathcal{H}}(x,y)}{u^{\mathcal{H}}(\sqrt n , \sqrt n )} \right). $$
What counts in the choice of the point $(\sqrt n , \sqrt n )$  is that
it is at a distance $\approx \sqrt n$  from the boundary  of
${\mathcal{Q}}$.
 
(iv) Due to the previous considerations, it is natural to divide
$\nu_n(x,y)$ by  $ \left(4\phi\right)^n $ in \eqref{eq5} and try to
find a similar interpretation  for the resulting quotient in terms of
a positive solution of \eqref{eq10} normalized by its value at a point located
at a distance $\approx \sqrt n$ from $\partial{\mathcal{Q}}$. This can
be achieved by considering unrestricted paths.


\section{The heat type equation and the unrestricted paths}

Let ${\mathcal{N}}_n(x,y)$ denote the number of unconstrained walks
starting at $(x,y)$ and of length $n \in {\mathbb{N}}$. We set
${\mathcal{N}}_n(x,y)=1$ for $n=0$ and denote by
${\mathbf{1}}_{\Gamma(x,y)}$ the characteristic function of the set
$\Gamma(x,y)$. ${\mathcal{N}}_n(x,y)$ satisfies the equation
$$
  {\mathcal{N}}_{n+1}(x,y) =\displaystyle \sum_{(h,k)\in
  {\mathbb{Z}}^2} {\mathbf{1}}_{\Gamma(x,y)}(h,k)
  {\mathcal{N}}_n(x+h,y+k),\,\,\,\textrm{ for all } (n;(x,y))\in
  {\mathbb{N}} \times {\mathbb{Z}}^2
$$ 
which implies the relation
\begin{equation}\label{eq7}
  \sum_{(h,k)\in \Gamma(x,y)}
  \frac{{\mathcal{N}}_n(x+h,y+k)}
  {{\mathcal{N}}_{n+1}(x,y)}=1,\,\,\,\textrm{ for all } \, 
  (n;(x,y))\in {\mathbb{N}}
  \times {\mathbb{Z}}^2 . 
  %\leqno(7)
\end{equation}
Let
\begin{equation}\label{eq8} 
  \mathcal{U}(n; (x,y)) =\frac{\nu_n(x,y)}{{\mathcal{N}}_n(x,y)},
  \,\,\,\,\,\, (n;(x,y))\in {\mathbb{N}} \times {\mathcal{Q}} .
  %\leqno(8)
\end{equation}
Dividing \eqref{eq2} by ${\mathcal{N}}_{n+1}(x,y)$ we see that $\mathcal{U}$ satisfies
$$
  {\mathcal{U}}(n+1;(x,y))=\displaystyle \sum_{(h,k)\in  {\mathbb{Z}}^2} 
  {\mathbf{1}}_{\Gamma(x,y)}(h,k) 
  \frac{{\mathcal{N}}_n(x+h,y+k)}{{\mathcal{N}}_{n+1}(x,y)}
  {\mathcal{U}}(n;(x+h,y+k)).
$$ 
Setting
\begin{equation}\label{eq9}
  \pi\left(n;(x,y), (h,k)\right)= {\mathbf{1}}_{\Gamma(x,y)}(h,k)
  \frac{{\mathcal{N}}_n(x+h,y+k)}{{\mathcal{N}}_{n+1}(x,y)}; 
  %\leqno(9)
\end{equation}
and using \eqref{eq7} we can rewrite this equation     
$$
  {\mathcal{U}}(n+1;(x,y)) -   
  \mathcal{U}(n; (x,y)) = \displaystyle \sum_{(h,k)} 
  \pi\left(n;(x,y), (h,k)\right)
  \Big( {\mathcal{U}}(n;(x+h,y+k))-\mathcal{U}(n; (x,y)) \Big).
$$ 
Introducing the discrete time and space derivatives
\begin{align*}
  \partial_n {\mathcal{U}}(n; (x,y)) & = {\mathcal{U}}(n+1;(x,y)) -   
  \mathcal{U}(n; (x,y))\\
  \nabla_{(h,k)}{\mathcal{U}}(n; (x,y)) & = {\mathcal{U}}(n;(x+h,y+k)) -   
  \mathcal{U}(n; (x,y)),
\end{align*}
we see that ${\mathcal{U}}(n; (x,y))$ satisfies the following
discrete heat type equation:
\begin{equation}\label{eq10}
  \partial_n {\mathcal{U}}(n; (x,y))= \sum_{(h,k) \in {\mathbb{Z}}^2} 
  \pi\left(n;(x,y), (h,k)\right)\nabla_{(h,k)}{\mathcal{U}}(n; (x,y)) . 
  %\leqno(10)
\end{equation}

     
\subsection{The harmonic function $u$.} 
Let us show that the  function $u: 
\mathcal{Q} \rightarrow {\mathbb{R}}$, $(x,y) \rightarrow u(x,y)=xy$
satisfies equation \eqref{eq10} in the case of golden walks. As $u$ is
independent  of $n$ the left-hand side is zero. To compute the right-hand side
we first observe  that $u(x+h,y+k)-u(x,y)= xk+yh+hk$. This implies that
\begin{align*}
  \sum_{(h,k)\in \mathbb{Z}^2} &
  \pi\left(n;(x,y), (h,k)\right)\nabla_{(h,k)}{u}(x,y) = 
  x \sum_{(h,k)\in \mathbb{Z}^2} 
  \pi\left(n;(x,y), (h,k)\right)k \\
  &+y  \sum_{(h,k)\in \mathbb{Z}^2} 
  \pi\left(n;(x,y), (h,k)\right)h 
  + \sum_{(h,k)\in \mathbb{Z}^2} 
  \pi\left(n;(x,y), (h,k)\right)hk.
\end{align*}
This shows that for $u$ to be solution of \eqref{eq10} requires (see \eqref{eq9})
\begin{align}\label{eq11}
  \sum_{(h,k) \in \Gamma(x,y)} \mathcal{N}_n(x+h,y+k)h & = 
  \sum_{(h,k) \in \Gamma(x,y)} \mathcal{N}_n(x+h,y+k)k 
  \\ \nonumber & = \sum_{(h,k) \in \Gamma(x,y)} 
  \pi\left(n;(x,y),(h,k)\right)hk = 0.
  %\leqno(11)
\end{align}
 
\subsection{Counting the unrestricted paths.} 
Let ${\mathcal{N}}_n(x,y)$ denote  the number of unrestricted walks
starting at $(x,y)$ and of length $n \in {\mathbb{N}}$.  We have
$$
  {\mathcal{N}}_n(x,y) = {\mathcal{N}}_n^o(x,y)+{\mathcal{N}}_n^e(x,y),
$$
where ${\mathcal{N}}_n^o(x,y)$ (resp. ${\mathcal{N}}^e_n(x,y)$) denote 
the number of walks ending on odd sites, i.e. sites $(x',y')$ such that
$y'-x'\equiv 1 \mbox{ mod}(2)$ (resp. on even sites). Since every odd
site is accessible from its eight neighbors, we have
\begin{equation}\label{eq12}
  {\mathcal{N}}^o_{n+1}(x,y) = 4{\mathcal{N}}^o_n(x,y) 
  + 4{\mathcal{N}}^e_n(x,y). 
  %\leqno(12)
\end{equation}
In contrast, even sites are accessible only from their four odd neighbors.
This implies that
\begin{equation}\label{eq13}
  {\mathcal{N}}^e_{n+1}(x,y) = 4{\mathcal{N}}^o_n(x,y)
  %\leqno(13)
\end{equation}
Adding \eqref{eq12} and \eqref{eq13} we obtain
$$
  {\mathcal{N}}_{n+1}(x,y) = 4({\mathcal{N}}^o_n(x,y)+{\mathcal{N}}^e_n(x,y))+
  4{\mathcal{N}}^o_n(x,y) = 4{\mathcal{N}}_n(x,y)+16{\mathcal{N}}_{n-1}(x,y).
$$
Setting ${\mathcal{F}}_n(x,y)= 4^{-n} {\mathcal{N}}_n(x,y)$ we obtain
$$
  {\mathcal{F}}_{n+1}(x,y)= {\mathcal{F}}_n(x,y)+{\mathcal{F}}_{n-1}(x,y)
$$
which shows that $\left( {\mathcal{F}}_n(x,y)\right)$ is a Fibonacci 
sequence. Using the initial conditions
$$
  \left\{
  \begin{array}{ccc}
  {\mathcal{F}}_0(x,y) = 1,\,\,\,\, {\mathcal{F}}_1(x,y) = 1
  &\textrm{ if } &  y-x \equiv 0 \mbox{ mod}(2)
  \\ \\
  {\mathcal{F}}_0(x,y) = 1,\,\,\,\, {\mathcal{F}}_1(x,y) = 2
  &\textrm{ if } &  y-x \equiv 1 \mbox{ mod}(2)
  \end{array}
  \right.
$$
we deduce the following formulas:
\begin{equation}\label{eq14}
  {\mathcal{N}}_{n}(x,y)= 4^n F_{n+1}= \frac{4^n}{\sqrt{5}}
  \left( \phi^{n+1} -\overline{\phi}^{n+1}\right)
  \textrm{ if } y-x \equiv 0 \mbox{ mod}(2) 
  %\leqno(14)
\end{equation}
\begin{equation}\label{eq15}
  {\mathcal{N}}_{n}(x,y)= 4^n F_{n+2}= \frac{4^n}{\sqrt{5}}
  \left( \phi^{n+2} -\overline{\phi}^{n+2}\right)
  \textrm{ if } y-x \equiv 1 \mbox{ mod}(2) 
  %\leqno(15)
\end{equation} 
where $\overline{\phi}=\frac{1-\sqrt{5}}{2}$ and $F_n$ denotes
the $n^{th}$ Fibonacci number; the second equality in \eqref{eq14} and \eqref{eq15}
results from the Binet's Fibonacci number formula.

From \eqref{eq14} and \eqref{eq15} it follows immediately that
${\mathcal{N}}_n(x+h,y+k)= {\mathcal{N}}_n(x-h,y+k)$,
${\mathcal{N}}_n(x+h,y+k)= {\mathcal{N}}_n(x+h,y-k)$
for each step $(h,k) \in \Gamma(x,y)$.
Combining with the symmetries of $\Gamma(x,y)$, we deduce \eqref{eq11}.  
 
On the other hand, using \eqref{eq9}, \eqref{eq14} and \eqref{eq15}
we deduce that
$$ 
  \pi\left(n;(x,y), (h,k)\right)=\frac{1}{4} 
  {\mathbf{1}}_{\Gamma_{{\mbox{even}}}}(h,k),
$$
in the case where $y-x \equiv 0 \mbox{ mod}(2)$, and that 
$$ 
  \pi\left(n;(x,y), (h,k)\right) = \frac{F_{n+1}}{4F_{n+3}}
  {\mathbf{1}}_{\Gamma_{{\mbox{even}}}}(h,k) + \frac{F_{n+2}}{4F_{n+3}}
  {\mathbf{1}}_{\Gamma_{{\mbox{odd}}}\setminus \Gamma_{{\mbox{even}}}}(h,k)
$$
in the case  where $y-x \equiv 1 \mbox{ mod}(2)$.
We will retain from the previous calculations, the following facts:
\begin{equation}\label{eq16}
  \frac{1}{C} (4\phi)^n \leq {\mathcal{N}}_{n}(x,y) 
  \leq C (4\phi)^n,\,\,\,  
  \mbox{  uniformly  in } (x,y) \in \mathbb{Z}^2 
  %\leqno(16)
\end{equation}
and
\begin{equation}\label{eq17}
  \pi\left(n;(x,y), (h,k)\right) \geq 
  \alpha {\mathbf{1}}_{\Gamma_{{\mbox{even}}}}(h,k),\,\,
  \mbox{  uniformly  in } (x,y);\,(h,k) \in \mathbb{Z}^2
  %\leqno(17)
\end{equation}
for appropriate $C,\,\alpha>0$.
 
\subsection{Towards the proof of Theorem 1} 
It follows from \eqref{eq16} that 
$$
  \frac{ \nu_n(x,y)}{C{\mathcal{N}}_{n}(x,y)} \leq \frac{\nu_n(x,y)}{(4\phi)^n} 
  \leq C \frac{ \nu_n(x,y)}{{\mathcal{N}}_{n}(x,y)}.
$$
Using \eqref{eq8} and the obvious inequality $\mathcal{U}(n; (x,y)) \leq 1$; 
we see then that in order to establish the upper bound of Theorem~\ref{thm1}, 
it is sufficient to show that
\begin{equation}\label{eq18}
  \frac{\mathcal{U}(n; (x,y))}{\mathcal{U}(n; (\sqrt n ,\sqrt n ))}
  \leq C \frac{u(x,y)}{u(\sqrt n , \sqrt n  )  }. 
  %\leqno(18)
\end{equation}
For the lower estimate we will need to reverse inequality \eqref{eq18} and a 
lower bound 
\begin{equation}\label{eq19}
  \mathcal{U}(n; (\sqrt n ,\sqrt n )) \geq c, \,\,\,\, n\geq C, 
  %\leqno(19)
\end{equation}
for appropriate $c,\, C>0$. It is discrete potential theory that will allow us
to establish \eqref{eq18}, its reverse and the lower bound \eqref{eq19}.


\section{Discrete potential theory and Proof of Theorem~\ref{thm1}}

Ideas from potential theory, in particular, harmonic functions,
maximum principle, Harnack inequalities and their parabolic and
boundary variants have  strong connections with our problem. In fact
general concepts of potential theory, have been borrowed since a long
time by discrete probability theory~\cite{Doo,S1}. This proved very
useful and successful for random walk analysis~\cite{L1,L2}. While it
is beyond the scope of this paper to explain in detail the related
concepts, we will try to explain the main tools that are relevant to
our problem, i.e. Harnack inequalities. For this we need to introduce
some notation.

Two points in $\mathbb{Z}^2$  will be said to be adjacent if the
distance between them is unity. A subset  $A \subset \mathbb{Z}^2$  of
cardinality $|A|\geq 2$ will be called connected if for any two points
of $A$ there is a path consisting of  segments of unit length
connecting them in such a manner that the end  points of these
segments are all  in $A$. A set of points is a domain if it is
connected. The symbol $A$ will  be used in the following to denote a
domain of $\mathbb{Z}^2$.

Given a map $\Gamma: (s,t) \in \mathbb{Z}^2 \rightarrow  \Gamma(s,t)
\subset  \mathbb{Z}^2 $, we define the boundary $\partial_\Gamma A$ of
$A$ (with respect to $\Gamma$) by
$$ 
  \partial_\Gamma A= \{ (x',y')\in A^c,\,\,\,\,(x',y')=(x+h,y+k),\,\,\,\,
  \mbox{ for some } (x,y)\in A \mbox{ and } (h,k)\in \Gamma(x,y)\}.
$$ 

We shall assume that $\Gamma$ satisfies:
\begin{equation}\label{eq20}
  \mbox{There exists } C>0,\,\,\,\,
  \,\,\,\,|\Gamma(x,y)|\leq C,\,\,\,\,\,\,\,\,
  \{ \leftarrow, \uparrow, 
  \rightarrow, \downarrow \}\,\subset \Gamma(x,y),\,\,\,\,\,
  (x,y) \in \mathbb{Z}^2. 
 %\leqno(20)
\end{equation}

The closure of $A$ will be denoted by $\overline A$ and defined by
$$
  \overline A = A\cup \partial_\Gamma A.
$$

For a cylindrical subset $B=A\times \{a\leq  n \leq b\}\subset
{\mathbb{Z}}^2\times {\mathbb{Z}}$  where $a<b \in {\mathbb{Z}}$ we
define the lateral boundary and the parabolic boundary of $B$ by 
$$
  \partial_l B= \bigcup_{a<n<b}\partial_\Gamma A\times\{n\},\,\,\,\,\,\,\,  
  \partial_p B= \partial_l B \cup\left({\overline A}
  \times\{ a\}\right),$$ and we let  $$\overline B=B\cup \partial_p B.
$$

Let $\Gamma$ satisfying \eqref{eq20} and
$\Pi:\mathbb{N}\times\mathbb{Z}^{2}\times {\mathbb{Z}}^2
\rightarrow\lbrack0,1]$ be such that
\begin{equation}\label{eq21}
  \Pi(n;(x,y);(h,k)) = 0, \mbox{if} \,\,(h,k) \not\in \Gamma(x,y)
  %\leqno(21) 
\end{equation}   
and
\begin{equation}\label{eq22} 
  \sum_{(h,k)\in\Gamma(x,y)}\Pi(n;(x,y);(h,k)) = 1,\quad
  n\in\mathbb{N},\,\, \quad (x,y)\in\mathbb{Z}^{2}, 
\end{equation}
\begin{equation}\label{eq23}
  \smashoperator[r]{\sum_{(h,k)\in\Gamma(x,y)}}\Pi(n;(x,y);(h,k))h=
  \smashoperator[r]{\sum_{(h,k)\in\Gamma(x,y)}}\Pi(n;(x,y);(h,k))k=0, \quad
  n\in\mathbb{N},\ (x,y)\in\mathbb{Z}^{2}, 
  %\leqno(22)????
\end{equation}  
there exists $\alpha>0$ such that
\begin{equation}\label{eq24}
  \Pi(n; (x,y); (h,k))\geq\alpha;\,\,\,\quad n\in\mathbb{N},\,\, 
  \quad (x,y)\in \mathbb{Z}^2,\: (h,k)\in \{ \leftarrow, \uparrow, 
  \rightarrow, \downarrow \}.
\end{equation}

We shall also assume that $\Pi$ is strongly aperiodic. This means
that, given any $(x,y) \in {\mathbb{Z}}^2$, there exists some integer
$n_0=n_0(x,y)$ such that $\Pi(n; (0,0); (x,y)))>0$ for all $n\geq n_0$.

Let $v: \overline B \longrightarrow \mathbb{R}$, where 
$B=A\times \{a\leq n \leq b\} \subset \mathbb{Z}^2\times \mathbb{Z}$.
We say that $v$ is $\Pi$-caloric in $B$ if
$$
  v((x,y);n+1) = \sum_{(h,k)\in \Gamma(x,y)}
  \Pi(n;(x,y);(h,k)) v((x+h,y+k);n),
$$
for all $((x,y);n)\in A\times \{a\leq n <b\}$.

The concept of a $\Pi$-caloric function generalizes the notion of
discrete harmonic function. In particular, caloric functions satisfy
an adapted version of the maximum principle. More precisely, a caloric
function on a finite set $B$ attains its maximum in $\overline B$ on
the lateral boundary $ \partial_l B$.  Another  basic property of
harmonic functions is Harnack principle, which states that a
positive harmonic function on a ball of radius $R$  is roughly
constant on the ball with the same center and radius $R/2$. Harnack
principle generalizes  for nonnegative $\Pi$-caloric as follows.


\begin{theorem} \label{thm2} (Refer to \cite{KT1,KT})  Let $\Gamma$
and $\Pi$ satisfy \eqref{eq20}-\eqref{eq24}.
Then there exists a constant $C=C(\alpha,\Gamma)>0$ such that, for any
$((x,y);s)\in \mathbb{Z}^2\times\mathbb{Z}$, $R\geq 1$  and any
nonnegative $\Pi$-caloric function $v: {\overline{B_{2R}(x,y)}} \times
\{s-4R^2\leq n \leq s\} \longrightarrow \mathbb{R}$, we have
\begin{align} \label{eq25}
  \max&\left\{v((x',y');n);\quad (x',y')\in B_R(x,y),\,\,\,\,
  s-3R^2 \leq n \leq s-2R^2\right\} \,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\, 
  \\ \nonumber
  %\leqno(24)
  &\leq C\, \min \left\{v((x',y');n); \quad (x',y')\in 
  B_R(x,y),\,\,\, s-R^2\leq n  \leq s \right\},
\end{align}
where $B_{R}(x,y)$ denotes the discrete ball in $\mathbb{Z}^2$ centered
on $(x,y)$ and of radius $R$.
\end{theorem}

Kuo and Trudinger proved their Harnack principle in the setting of implicit difference schemes. To see how the explicit case, which corresponds to our Theorem~\ref{thm2}, can be obtained by their method one can proceed as follows.
Start with [\cite{KT}, \S 2] and replace it by [\cite{KT1}, \S 3] (rewritten
in the case $\alpha=1$,  and taking into account all the simplifications
implied by the assumptions \eqref{eq20}-\eqref{eq24}),  then carry out the same steps as in [\cite{KT}, \S 3]
until Eq. (3.17) on page 409. 
This is sufficient because we can always assume $R$ large enough and there is no need to remove the restriction contained in (3.17). This gives an analogue of Lemma 3.2 of [\cite{KT}, \S 3] valid in the present context. A weak Harnack inequality can be derived by an adaptation of the procedure introduced by Krylov and Safanov [\cite{KS1}, \S 2] for the continuous case. Harnack principle follows then as a direct consequence of the weak Harnack inequality (see \cite{KT}, \S 4).  

In the proof of Theorem~\ref{thm1}, together with Theorem~\ref{thm2}
we need the following boundary variant of \eqref{eq25}. In classical
potential theory, the boundary Harnack principle describes the
boundary behavior of positive  harmonic functions vanishing on a
portion of the boundary~\cite{A,JK}. It asserts that two positive
harmonic functions vanishing on a portion of the boundary decay at the
same rate. This principle generalizes to $\Pi$-caloric functions. The
proof  in [\cite{M1}, \S 5.1, \S 5.2 and \S 5.3], given for
nonnegative ${\mathcal L}$-caloric functions in cylindrical domains,
is based only on the maximum and Harnack principles and can be readily
extended to  $\Pi$-caloric functions.

\begin{theorem}\label{thm3} Let $\Gamma$ and $\Pi$ satisfying
\eqref{eq20}-\eqref{eq24}. Then, there exists a
constant $K>1$ such that for all  $s\in \mathbb{N}$,  $R>K$ and all
couple of  nonnegative $\Pi$-caloric  functions
$$ 
  v_1,\,v_2: {\overline{(\mathcal{Q}\cap B_{3KR})\times
  \{s-9 K^2R^2\leq n \leq s+9K^2R^2\}}} \subset 
  \mathbb{Z}^2\times \mathbb{Z}\longrightarrow {\mathbb{R} }
$$
with $v_1=0$ on ${(\partial_\Gamma \mathcal{Q}\cap B_{2KR})
\times\{s-4 K^2R^2\leq n \leq s+4K^2R^2\}}$, we have 
\begin{align*}
  \max \Big\{\frac{v_1((x,y);n)}{v_2((x,y);n)},&\,\,\,\,
  ((x,y); n) \in  {(\mathcal{Q}\cap B_{R}))\times\{s-2 R^2\leq n 
  \leq s\}}\Big\} \\
  &\leq C\frac{v_1((KR, KR);s+2K^2R^2)}
  {v_2((KR, KR);s-2K^2R^2)},  
\end{align*}
where $B_{R}$ denotes the discrete ball $B_{R}(0,0)$ and 
$C=C(\alpha,\Gamma)>0.$ 
\end{theorem}

We now have all the ingredients to prove Theorem~\ref{thm1}. The
kernel $\pi$ defined by \eqref{eq9} satisfies all the conditions
required in order to apply Theorems~\ref{thm2} and \ref{thm3}.
$\Gamma_{\mbox{even}}$,  $\Gamma_{\mbox{odd}}$ satisfy in an obvious
way \eqref{eq20}. \eqref{eq22} is implied by the normalization
condition \eqref{eq7}.  \eqref{eq23} is a consequence of \eqref{eq11}
and \eqref{eq24} follows from \eqref{eq17}.

\begin{proof}[Proof Theorem~\ref{thm1}] Note that in the proof of
Theorem~\ref{thm1} we can assume $n\geq C$ for a large constant $C>0$. Otherwise \eqref{eq5} becomes evident because
$$ 
  1 \leq \nu_n(x,y) \leq  8^C,\,\,\,\, \frac{1}{C} \leq \frac{xy}{n} \leq 1 
$$
if we assume $1\leq x\, ,y \leq \sqrt n$ and $n\leq C$.

Assuming $n$ large enough, it becomes possible to apply Theorem~\ref{thm3}.
The crucial observation is that each of the functions $(n;
(x,y))\longrightarrow u(x,y)$ and $(n; (x,y))\longrightarrow \mathcal{U}(n;
(x,y))$, initially defined on $\mathbb{N} \times \overline{\mathcal{Q}}$, can
be extended to all $\mathbb{Z} \times \overline{\mathcal{Q}}$. As for the
first, this simply happens because it is independent of $n$; as for the
second, the extension can be done by setting
\begin{equation}\label{eq26}
  \mathcal{U}(n; (x,y)) \equiv 1, \,\,\,\,\,(n; (x,y))\in 
  (\mathbb{Z}_{-}) \times \overline{\mathcal{Q}}.
  %\leqno(25)
\end{equation}
The second relation in the boundary conditions \eqref{eq3} satisfied by
$\nu(n; (x,y))$ guarantees that the extension \eqref{eq26} is $\pi$-caloric in
$\mathbb{Z} \times {\mathcal{Q}}$. The idea of such a construction is inspired
by the proof of Lemma 4.1 in \cite{SY}.

We now have at our disposal two positive $\pi$-caloric functions
satisfying conditions of Theorem~\ref{thm3} that we will be able to compare.
Setting $v_1((x,y); n)= \mathcal{U}(n; (x,y)) $, $v_2((x,y); n)= u(x,y)$,
$s=n$ and $R=\sqrt{n}/4K$, we deduce then that
\begin{equation}\label{eq27}
  \frac{\mathcal{U}\big(n; (x,y)\big)}{u\big(x,y\big)}
  \leq C\frac{\mathcal{U}\big(9n/8; (\sqrt n/4,\sqrt n/4)\big)}
  {u\big(\sqrt n/4 , \sqrt n/4\big)}. 
  %\leqno(26)
\end{equation}
   
Now we observe that if $(x,y) \in \mathcal{Q}$ is such that  $x,\, y\geq
c\sqrt n$ then $ \mathcal{U}(n; (x,y)) \geq c'$, for appropriate positive
constants $c,\,c'>0$. This follows from \eqref{eq26} and an application of
Harnack inequality \eqref{eq25}. This remark also allows to see that,
in the same way, \eqref{eq19} is an immediate consequence of Harnack
principle.

Using the fact that 
$$
  c\leq \mathcal{U}\big(9n/8; (\sqrt n/4,\sqrt n/4)\big) \approx
  \mathcal{U}(n; (\sqrt n ,\sqrt n )) \leq 1
$$
and 
$$
  u(\sqrt n/4,\sqrt n/4) \approx u(\sqrt n ,\sqrt n )
$$
which easily results from the application of Harnack principle \eqref{eq25} 
we deduce \eqref{eq18}.

To reverse inequality \eqref{eq27} we repeat the above reasoning exchanging
$v_1$ and $v_2$. This gives
$$ 
  \frac{u(x,y)}{\mathcal{U}\big(n; (x,y\big))}
  \leq C\frac{u\big({\sqrt n}/4,{\sqrt n}/4\big)} 
  {\mathcal{U}\big(7n/8; ({\sqrt n}/4,{\sqrt n}/4)\big)}.
$$ 
Using Harnack inequality and \eqref{eq19} we get the desired inequality. 
This completes the proof of Theorem~\ref{thm1}.
\end{proof}


\section{Extensions and excursions}

Our potential theoretic strategy relies on two crucial points: the existence
of a positive harmonic function $u$ vanishing on the boundary of $\partial
\mathcal{Q}$ and the centering assumption \eqref{eq23}. Once achieved the
construction of such a function,  the machinery applies and gives, the
following bounds:
\begin{equation}\label{eq28}
  \frac{\mathcal{N}_n(x,y)u(x,y)}{Cu\big({\sqrt n},{\sqrt n}\big)}
  \leq \nu_n(x,y) \leq \frac{C\mathcal{N}_n(x,y)u(x,y)}{u\big({\sqrt n},{\sqrt n}\big)},
  %\,\,\,\leqno(27)
\end{equation} 
$(x,y) \in {\mathcal{Q}},\,\,\,x, \, y \leq c\sqrt n,\,\, n=1,2,\dots$,
where ${\mathcal{N}}_n(x,y)$ denotes the number of unrestricted walks starting 
at $(x,y)$ and having length $n$.

In the case of centered homogeneous small steps walks, the existence of $u$
follows from the results of K. Raschel~\cite{R3} since in this case the kernel
$\pi(n; (x,y); (h,k))$ is given by $$    \pi(n; (x,y);
(h,k))=\frac{1}{|\Gamma|} $$ and the function $u$ is the discrete harmonic
function explicitly constructed in \cite{R3}.
 
Using the results of \cite{BRS} (see step sets with number 30, 40 and 42 in
column ``Tag'' of Table 2 of \cite{BRS}), we easily deduce the following.

\begin{theorem}\label{thm4} 
Let $\Gamma$ be any of the three nonsingular step
sets  associated with an infinite group and having zero-drift (i.e. $\Gamma=
\{  \nearrow, \uparrow, \leftarrow, \swarrow, \searrow \}$,  $\{ \swarrow,
\nwarrow, \uparrow,  \rightarrow, \searrow \}$ or $ \{   \nwarrow,  \nearrow,
\leftarrow, \searrow, \downarrow \}$). Then for any $(x,y) \in \mathcal{Q}$
the length generating function for walks that start from $(x,y)$ and always
stay in $ \mathcal{Q}$ is not D-finite. 
\end{theorem}

The proof of Theorem~\ref{thm4} is based on the form of the function $u(x,y)$
constructed in \cite{R3}. It follows from \cite{DW}, that in case of step
set $\Gamma= \{  \nearrow, \uparrow, \leftarrow, \swarrow, \searrow \}$,  this
function satisfies $u\big({\sqrt n},{\sqrt n}\big) \approx
n^{{\pi}/{2\arccos\left(-\frac{1}{4} \right)}} =
n^{{\pi}/{2\left(\pi-\arccos\left(\frac{1}{4} \right)\right)}},\,\,\,
n\rightarrow \infty$, and $u\big({\sqrt n},{\sqrt n}\big) \approx
n^{{\pi}/{2\arccos\left(\frac{1}{4} \right)}},\,\,\, n\rightarrow \infty$  in
the case of step sets $\{ \swarrow,  \nwarrow, \uparrow,  \rightarrow,
\searrow \}$ or $ \{ \nwarrow,  \nearrow, \leftarrow, \searrow, \downarrow
\}$

On the other hand, it is easy to see that $\pi/2\arccos({1}/{4})$ is
irrational (see \cite{V}).
A consequence of the irrationality of $\pi/2\arccos\left({1}/{4} \right)$ is
that the asymptotics obtained for $u\big({\sqrt n},{\sqrt n}\big)$ are not
compatible with the growth of coefficients of D-finite series with integer-valued exponentially bounded coefficients (see \cite{BRS}, Theorem 3).

Another interesting aspect of \eqref{eq28} is that it generalizes to models
with longer steps and also in higher dimensions (we should then use \cite{BMS}
instead of \cite{R3} to deduce the existence of the harmonic function $u$).
For instance, the asymptotics obtained by Melczer and Mishna in \cite{MM} for
$d$-dimensional highly symmetric walks
$$ 
  s_n \approx \mathcal{|S|}^n n^{-d/2},
$$ 
where $s_n$ denotes the number of walks of length $n$ taking steps in
$\mathcal{S}$, starting at the origin, and never leaving the positive orthant,
can be retrieved easily using \eqref{eq28}. Indeed, one can readily verify
that for $d$-dimensional highly symmetric walks the function
$$
  u(x_1,x_2,..,x_d)= x_1x_2...x_d,\,\,\,\,(x_1,x_2,...,x_d)\in \mathbb{N^\star}^d
$$ 
is a positive harmonic function vanishing on the boundary of
$\mathbb{N^\star}^d$  and it is immediate that $u(\sqrt n, \sqrt n,\dots \sqrt
n)$ equals the polynomial factor $n^{d/2}$.
 
For symmetric walks in Weyl chambers one can use the harmonic functions
constructed in \cite{EK,KS} (see also \cite{S2}).

Finally the upper bound in \eqref{eq28} can also be used to derive upper
estimates for excursions. Let us take, for example, the  highly symmetric
walks considered in \cite{MM}. Let us use the same notation as in \S 2 and
denote by  $\nu_n(x_1,...,x_d; y_1,...,y_d)$ the number of walks of length $n$
taking steps in $\mathcal{S}$, starting from $(x_1,...,x_d)$, ending at
$(y_1,...,y_d)$, and never leaving the positive orthant. We have:
\begin{align*}
  \frac{\nu_{3n}(x_1,\dots x_d; y_1,\dots y_d)}{|\mathcal{S}|^{3n}}
  &=\sum_{(z_1,\dots z_d) \in \mathbb{N^\star}^d}
  \sum_{(z'_1,\dots z'_d) \in \mathbb{N^\star}^d}
  \frac{\nu_n(x_1,\dots x_d; z_1,\dots z_d)}{ |\mathcal{S}|^{n}}
  \\ \nonumber
  &\times
  \frac{\nu_n(z_1,\dots z_d; z'_1,\dots z'_d)}{ |\mathcal{S}|^{n}}
  \times
  \frac{\nu_n(z'_1,\dots z'_d; y_1,\dots y_d)}{ |\mathcal{S}|^{n}}
\end{align*}
Using the well known upper bound random walk estimate (\cite{S1}, 
Chapter II, Proposition 7.6) 
$$ \frac{\nu_n(z_1,\dots z_d; z'_1,\dots z'_d)}{ |\mathcal{S}|^{n}}
\leq C n^{-d/2}$$
and combining with \eqref{eq28} we deduce that
%the estimates
%$$ \nu_{n}(x_1,...,x_d) \leq
%\frac{C|\mathcal{S}|^{n} x_1...x_d}
%{n^{d/2}},\,\,\,\,\, \nu_{n}( y_1,...,y_d) \leq
%\frac{C|\mathcal{S}|^{n} y_1...y_d}
%{n^{d/2}},$$
%(where $n$ is assumed large enough)  which result from (27), we deduce
$$ \nu_{n}(x_1,\dots x_d; y_1,\dots y_d) \leq C
\frac{|\mathcal{S}|^{n} (x_1...x_d)(y_1...y_d)}
{n^{3d/2}}.$$
It follows that
 the number of walks
$e_n$
of length $n$
taking steps in $\mathcal{S}$, beginning and ending at the origin, and never leaving the positive orthant satisfies
$$ e_n=\mathcal{O}\left(
\frac{C|\mathcal{S}|^{n}} 
{n^{3d/2}}\right),$$
which gives an alternative proof of Theorem 7.2 of \cite{MM}.

\subsection*{Acknowledgements}
We are grateful to the referee for carefully reading the manuscript and making thoughtful comments and remarks. This work, partially undertaken within the framework of CALSIMLAB, is supported by the public grant ANR-11-LABX-0037-01 overseen by the French National Research Agency (ANR) as part of the ``Investissements d'Avenir'' program (reference: ANR-11-IDEX-0004-02). S.M. would like to thank Kilian Raschel  for stimulating discussions on the subject and for having informed him that the authors of Ref. \cite{BRS} have realized shortly after the publication of their paper that their method allows to obtain Theorem~\ref{thm4}.


\begin{thebibliography}{10}

\bibitem{A} A.~Ancona. \newblock Principe de Harnack à la frontière et
théorème de Fatou pour un opérateur elliptique dans un domaine Lipschitzien.
\newblock {\em Ann. Inst. Fourier}, 37:313--338, 2001.

\bibitem{BF} C. Banderier and P. Flajolet. \newblock Basic analytic
combinatorics of directed lattice paths. \newblock {\em Theoret. Comput. Sci.},
281:37--80, 2002.

%\bibitem{B} P. Bauman, \textit{Positive solutions of elliptic equations in %nondivergence form and their adjoints}, Arkiv Math. \textbf{22} (1984), 153-173.
%\bibitem{BMR} O. Bernardi, M. Bousquet-Mélou and K. Raschel,
% \textit{  Counting quadrant walks via Tutte's invariant method},
% ArXiv: 1511.04298 
%, 2015.
% \bibitem{Bi1}  P. Biane, \textit{Quantum random walk on the dual of
%   $SU(n)$.} Probab. Theory Related Fields \textbf{89} (1991)
%117-129.
%\bibitem{Bi2} P. Biane, \textit{Minuscule weights and random walks on lattices,}
%In Quantum probability \& related topics, 51-65. World Sci. Publ.,
%River Edge, NJ (1992).

\bibitem{BK} A. Bostan and M. Kauers. \newblock Automatic classification of restricted lattice walks. \newblock In {\em DMCTS Proceedings of the 21st Internatinal Conference on Formal Powers and Algebraic Combinatorics}, pages 203--217, FPSAC'09, Hagenberg, Austria, 2009.

\bibitem{BK1} A. Bostan and M. Kauers. \newblock The complete generating function for Gessel walks is algebraic. \newblock {\em Proc. Amer. Math. Soc.}, 138:3063--3078, 2010.  

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

\bibitem{BMKM} A. Bostan, M. Bousquet-Mélou, M. Kauers and S. Melczer.
\newblock{Walks confined to the positive octant}, \newblock to appear in {\em Annals of Comb.}, arXiv:1409.3669, 2014.

\bibitem{BMS} A. Bouaziz, S. Mustapha and M. Sifi. \newblock{Discrete harmonic functions on an orthant in $\mathbb{Z}^{d}$}. \newblock {\em Elect. Com. Proba.}, 1-13, 2015.

\bibitem{B1} M. Bousquet-Mélou. \newblock{Counting walks in the  quarter plane}. 
In {\em Mathematics and computer science, II (Versailles 2001)}, Trends Math., pages 49--67, Birkhäuser, Basel, 2002. 

\bibitem{B2} M. Bousquet-Mélou. \newblock{Linear reccurences with constant coefficients: the multivariate case}. \newblock {\em Discrete Math.}, 225:51--75, 2000.

\bibitem{B3} M. Bousquet-Mélou. \newblock{Walks in the quarter plane: Kreweras' algebraic model}. \newblock {\em Ann. Appl. Probab.}, 15:1451--1491, 2005.

% \bibitem{B4} M. Bousquet-Mélou,  \textit{
%Plane lattice walks avoiding a quadrant},ArXiv: 1511.02111, 2015.

\bibitem{BM} M. Bousquet-Mélou and M. Mishna. \newblock{Walks with small steps in the quarter plane}. \newblock {\em Contemp. Math.}, 520:1--40, 2010.

\bibitem{BP} M. Bousquet-Mélou and M. Petkovsec. \newblock{Walks confined in a quadrant are not always D-finite}. \newblock {\em Theoret. Comput. Sci.}, 307:257--276, 2005.

\bibitem{DW} D. Denisov and V. Wachtel. \newblock{Random Walks in Cones}. \newblock {\em Ann. Probab.}, 43:992--1044, 2015.

%\bibitem{Doo} J.~L. Doob. \newblock{Discrete potential theory and boundaries}. \newblock {\em J. Math. and Mech.}, 8:433--458, 1959.

\bibitem{D} P. Duchon. \newblock{On the enumeration and generation of generalized
 Dyck words}. \newblock {\em Discrete Math.}, 225:121--135, 2000.

\bibitem{Doo} R.~J. Duffin. \newblock{Discrete potential theory}. \newblock {\em Duke Math. J.}, 20:233--251, 1953.

\bibitem{EK} P. Eichelsbacher and W. König. \newblock{ Ordered random walks}. 
\newblock {\em Electron. J. Probab.}, 13:1307--1336, 2008.

%\bibitem{FIM} 
%  G. Fayolle, R. Iasnogorodski, and V. Malyshev.
%Random walks in the quarter-plane, volume 40 of
%Applications of Mathematics (New York), Springer-Verlag, Berlin, 1999.

\bibitem{FR1} G. Fayolle and K. Raschel. \newblock{ On the holonomy or algebraicity of generating functions counting lattice walks in the quarter plane}. \newblock {\em Markov Process. Related Fields}, 16:485--496, 2010.

\bibitem{FR2} G. Fayolle and K. Raschel. \newblock{About a possible analytic approach for walks in the quarter plane with arbitrary big jumps}. \newblock {\em C. R. Math. Acad. Sci. Paris}, 353:89--94, 2015.

%\bibitem{F} M. E. Fisher, \textit{Walks, walls, wetting and melting}, 
%J. Stat. Phys. \textbf{34} (1984), 667-729.

\bibitem{FO} Ph. Flajolet and A. M. Odlyzko. \newblock{Singular analysis of generating functions}. \newblock {\em SIAM Jour. in Algebraic and Discrete 
Methods}, 3:216--240, 1990.

\bibitem{FS} Ph. Flajolet and R. Sedgewick. \newblock{Analytic Combinatorics}. \newblock Cambridge University Press, Cambridge, 2009.

\bibitem{JK} D. Jerison and C. Kenig. \newblock{ Boundary behavior of harmonic functions in non-tangentially accessible domains}. \newblock {\em Advances in 
Math.}, 146:1-68, 1982. 

\bibitem{KS} W. König  and  P. Schmid. \newblock{ Random walks conditioned to stay in Weyl chambers of type C and D}. \newblock {\em Elect. Comm. Probab.}, 15:286--296, 2010.

\bibitem{KS1} N.~V. Krylov  and  M.~V. Safanov. \newblock{Certains properties of 
solutions of parabolic equations with mesurable coefficients}. \newblock {\em Izv. Akad. Nauk. SSSR}, 40:161--175, 1980.

\bibitem{KT} H.~J. Kuo and N.~S. Trudinger. \newblock{Local estimates for 
parabolic difference operators}. \newblock {\em Jour. of Differential Equations}, 122:398--413, 1995.

\bibitem{KT1} H.~J. Kuo and N.~S. Trudinger. \newblock{Evolving monotone difference operators on general space-time meshes}. \newblock {\em Duke Math. J.}, 91:587-607, 1998.

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

%\bibitem{KR1} I. Kurkova and K. Raschel, \textit{Random walks in $\mathbb{Z}^2_+$ %with non-zero drift absorbed at the axes},
%Bulletin de la Société Mathématique de France \textbf{139}, (2011), 341-387.

\bibitem{KR2} I. Kurkova and K. Raschel. \newblock{On the functions counting 
walks with small steps in the quarter plane}. \newblock {\em Publ.
Math. Inst. Hautes Etudes Sci.}, 116:69--114, 2012.

\bibitem{L1} G.~F. Lawler. \newblock{Estimates for differences and Harnack inequality for difference operators coming from random walks with symmetric,
spatially inhomogeneous, increments}. \newblock {\em Proc London Math. Soc.}, 
63:552--568, 1991.

\bibitem{L2} G.~F. Lawler. \newblock{\em Intersection of Random Walks}. \newblock  Birkhäuser, 1996. 

\bibitem{LRV} Lafitte-Godillon,  K. Raschel  and Viet Chi Tran. \newblock{
Extinction probabilities for a distylous plant population modeled by an inhomogeneous random walk on the positive quadrant}. \newblock {\em SIAM Journal on Applied Mathematics}, 73:700--722, 2013.

\bibitem{MM1}  S. Melczer and M. Mishna. \newblock Singularity analysis via the iterated kernel method. \newblock {\em Comb. Proba. Comput.}, 23:861--888, 2014

\bibitem{MM} S. Melczer and M. Mishna. \newblock{Enumerating lattice paths with symmetries through multivariate diagonals}. \newblock arXiv:1402.1230v3, 2014.

\bibitem{M} M. Mishna. \newblock{Classifying lattice walks restricted to the quarter plane}. \newblock {\em J. Combin. Theory Ser. A}, 116:460--447, 2009.

\bibitem{MR} M. Mishna and A. Rechnitzer. \newblock{Two non-holonomic lattice walks in the quarter plane}. \newblock {\em Theoret. Comput. Sci.}, 410:3616--3630, 2009.

\bibitem{M1} S. Mustapha. \newblock{Gaussian estimates for spatially inhomogeneous random walks on $\mathbb{Z}^d$}. \newblock {\em The Annals of Probability}, 34:264--283, 2006.

\bibitem{M2} S. Mustapha. \newblock{Gambler's ruin estimates for random walks with symmetric spatially inhomogeneous increments}. \newblock {\em Bernoulli}, 13:131--147, 2007.

\bibitem{R3} K. Raschel. \newblock{Random walks in the quarter plane, discrete harmonic functions and conformal mappings, with an appendix by Sandro Franceschi}. 
\newblock {\em Stochastic Processes and their Applications}, 124:3147--3178, 2014.

\bibitem{SY} M. V. Safonov and Y. Yuan. \newblock{Doubling properties for second order parabolic equations}. \newblock {\em Annals of Mathematics}, 150:313--327, 1999.

\bibitem{S1} F. Spitzer. \newblock{\em Principles of Random Walks}. Second edition, Graduate Texts in Mathematics, Springer-Verlag, 1976.

 \bibitem{S2} R. Steinberg. \newblock{Differential equations invariant under finite reflexion group}. \newblock {\em Trans. of the American Math. Soc.}, 112:392--400, 1964. 

\bibitem{V} J.~L. Varona. \newblock Rational values of the arccosine function. \newblock {\em Cent. Eur. J. Math.}, 4:319--322, 2006.

\end{thebibliography}            


\newlength{\myll}
\settowidth{\myll}{\footnotesize 33889143}
\tikzstyle{every node}=[font=\scriptsize]
\getlength{\myl}{\myll}

\newcommand{\gc}{
\begin{tikzpicture}[baseline={(current bounding box.center)}]
\draw (0,0) circle (0.1);
\end{tikzpicture}}
\newcommand{\pc}{
\begin{tikzpicture}[baseline={(current bounding box.center)}]
\draw (0,0) circle (0.065);
\end{tikzpicture}}
\newcommand{\mv}[1][]{%
\begin{tikzpicture}[baseline={(current bounding box.center)}] 
\draw [white,inner sep=0, outer sep=0] (-0.375*\the\myll,-0.375*\the\myll) rectangle (0.375*\the\myll,0.375*\the\myll);
\draw (0,0) circle (0.1) ;
\draw [inner sep=0, outer sep=0] node [rotate=90]at (-0.15,0) {#1};
\end{tikzpicture}
}
%
\newcommand{\pv}[1][]{%
\begin{tikzpicture}[baseline={(current bounding box.center)}] 
\draw [white,inner sep=0, outer sep=0] (-0.375*\the\myll,-0.375*\the\myll) rectangle (0.375*\the\myll,0.375*\the\myll);
\draw [inner sep=0, outer sep=0](0,0) circle (0.065) ;
\draw [inner sep=0, outer sep=0] node [rotate=90]at (-0.15,0) {#1};
\end{tikzpicture}
}
%
\newcommand{\mvr}[1][]{%
\begin{tikzpicture}[baseline={(current bounding box.center)}] 
\draw [white,inner sep=0, outer sep=0] (-0.375*\the\myll,-0.375*\the\myll) rectangle (0.375*\the\myll,0.375*\the\myll);
\draw [red,inner sep=0, outer sep=0] node [rotate=90]at (-0.15,0) {#1};
\draw [red,inner sep=0, outer sep=0] (0,0) circle (0.1) ;
\end{tikzpicture}
}
\newcommand{\mh}[1][]{%
\begin{tikzpicture}[baseline={(current bounding box.center)}] 
\draw [white,inner sep=0, outer sep=0] (-0.375*\the\myll,-0.375*\the\myll) rectangle (0.375*\the\myll,0.375*\the\myll);
\draw [inner sep=0, outer sep=0] (0,0) circle (0.1) %;
[inner sep=0, outer sep=0] node at (0,0.15) {#1};
\end{tikzpicture}
}
\newcommand{\ph}[1][]{%
\begin{tikzpicture}[baseline={(current bounding box.center)}] 
\draw [white,inner sep=0, outer sep=0] (-0.375*\the\myll,-0.375*\the\myll) rectangle (0.375*\the\myll,0.375*\the\myll);
\draw [inner sep=0, outer sep=0] (0,0) circle (0.065) %;
[inner sep=0, outer sep=0] node at (0,0.15) {#1};
\end{tikzpicture}
}
\newcommand{\mhr}[1][]{%
\begin{tikzpicture}[baseline={(current bounding box.center)}]
\draw [white,inner sep=0,outer sep=0] (-0.375*\the\myll,-0.375*\the\myll) rectangle (0.375*\the\myll,0.375*\the\myll);
\draw [red,inner sep=0, outer sep=0] (0,0) circle (0.1) ;
\draw [red,inner sep=0, outer sep=0] node at (0,0.15) {#1};
\end{tikzpicture}
}

\begin{figure}
%
\tikzset{pair/.style={circle,draw=red,minimum size=0.1cm,inner sep=0,outer sep=0,anchor=center,label=center,align=center}}

\begin{tikzpicture}
\tikzstyle{every node}=[font=\scriptsize]
%
%dessine les axes
%\draw [->](-8.0*0.75*\myl,-8.0*0.75*\myl) -- (8.0*0.75*\myl,-8.0*0.75*\myl);
%\draw [->](-8.0*0.75*\myl,-8.0*0.75*\myl) -- (-8.0*0.75*\myl,8.0*0.75*\myl); %axe y

%place les tickmarks et les graduations
%\foreach \x [evaluate=\x as \cx using -8.000+0.75*\x*\myl] in {1,...,10}{
% \draw [inner sep=0, outer sep=0](-8.0*0.75*\myl,\cx-0.05) -- (-8.0*0.75*\myl+0.2,%%\cx-0.05) node [left,xshift=-2ex] {\x}; % axe y
 %\draw [inner sep=0, outer sep=0](\cx,-8.0*0.75*\myl) -- (\cx,-8.0*0.75*\myl+0.2)  %node [below,yshift=-2ex] {\x}; % axe x
%}
%
%place les labels d'axes
%\draw (-8.000+0.75*15.8*\myl,-8.000) node [below,yshift=-0.75ex]{\small x};
%\draw (-8.000,-8.000+0.75*15.8*\myl) node [left,xshift=-0.75ex]{\small y};
%

\matrix[matrix of nodes, row sep={0.75*\myll,between origins}, column sep={0.75*\myll,between origins},
xshift=0pt,yshift=0pt, inner sep=0, outer sep=0
]{
     \mh[1806]&      \ph[6752]&      \mh[3534]&      \ph[7432]&      \mh[2490]&     \ph[4080]&      \mh[938]&    \ph[1296]&     \mh[198]&    \ph[240]&     \mh[22]&   \ph[24]&     \mh[1]&  \ph[1]&  \mhr[0]\\
     %
    \pv[35484]&     \mv[31432]&     \pv[72108]&     \mv[33824]&     \pv[54612]&    \mv[17720]&    \pv[22820]&    \mv[5184]&    \pv[5532]&    \mv[840]&    \pv[748]&   \mv[68]&   \pv[ 49]& \mvr[2]&   \ph[1]\\
    %
   \gc        &      \pc      &     \gc       &     \pc       &     \gc       &     \pc      &     \gc      &      \pc    &      \gc    &   \pc      &    \gc     &   \pc    &   \mhr[92]&  \pc  &   \mh[1]\\
   %
   \pv[878336]&    \mv[853856]&   \pv[1804176]&    \mv[941792]&   \pv[1393488]&   \mv[512544]&   \pv[596512]&  \mv[156992]&  \pv[147744]&  \mv[26644]&  \pv[20150]&\mvr[2244]&  \ph[1294]&  \gc  &  \ph[24]\\
   %
   \gc        &      \pc      &     \gc       &    \pc        &     \gc       &    \pc       &    \gc       &      \pc    &   \gc       &   \pc      & \mhr[32104]&    \pc   &  \mh[1764]&  \pc  &  \mh[22]\\
\pv[8262020]&\mv[8530296]&\pv[17113652]&\mv[9575776]&\pv[13432460]&\mv[5362184]&\pv[5878908]& \mv[1705688]& \pv[1493031]&\mvr[302470]& \ph[208191]&  \gc     & \ph[13480]&  \gc  & \ph[240]\\
%
    \gc       &      \pc      &       \gc     &     \pc       &      \gc      &       \pc    &   \gc        &    \pc      &\mhr[1970964]&  \pc       & \mh[257223]&     \pc  & \mh[14838]&   \pc & \mh[198]\\
	      %
\pv[40328704]&\mv[43419072]&\pv[84078688]&\mv[49377344]&\pv[66841312]&\mv[28254232]&\pv[29801100]&\mvr[9261736]& \ph[7745340]&    \gc     &\ph[1107504]&    \gc   & \ph[73232]&   \gc &\ph[1296]\\
%
   \gc        &    \pc        &    \gc        &   \pc         &     \gc       &     \pc      &\mhr[32204368]&   \pc       & \mh[8088906]&    \pc     &\mh[1096718]&   \pc    & \mh[66234]&  \pc  & \mh[938]\\
	      %
\pv[113856460]&\mv[126227944]&\pv[238525020]&\mv[144910092]&\pv[191468929]&\mvr[84251826]& \ph[86608641]&    \gc      &\ph[22940784]&   \gc      &\ph[3355752]&      \gc &\ph[227320]&   \gc &\ph[4080]\\
%
 \gc          &    \pc        &    \gc        &    \pc        &\mhr[166600380]&    \pc       & \mh[73848257]&     \pc     &\mh[18972126]&   \pc      &\mh[2649814]&    \pc   &\mh[166322]&  \pc  &\mh[2490]\\
	      %
\pv[188720640]&\mv[213358364]& \pv[396696346]&\mvr[246518076]& \ph[320604194]&     \gc      &\ph[146521480]&   \gc       &\ph[39353880]&  \gc       &\ph[5858744]&  \gc     &\ph[405288]& \gc   &\ph[7432]\\
%
   \gc        &    \pc        &\mhr[263287320]&    \pc        & \mh[210154736]&   \pc        & \mh[94148894]&   \pc       &\mh[24550938]&   \pc      &\mh[3498850]&   \pc    &\mh[225750]& \pc   &\mh[3534]\\
   %
\pv[160901247]&\mvr[183966822]& \ph[338891431]&     \gc       & \ph[274990200]&  \gc         &\ph[126450688]&  \gc        &\ph[34251264]&   \gc      &\ph[5155496]&  \gc     &\ph[361656]&  \gc  &\ph[6752]\\
%
\mhr[60207948]&     \pc       & \mh[126008175]&     \pc       & \mh[100917470]&  \pc         & \mh[45448158]&  \pc        &\mh[11939610]&  \pc       &\mh[1718970]&  \pc     &\mh[112510]& \pc   &\mh[1806]\\
};
%\end{scope}
\end{tikzpicture}

\caption{\label{fig2} The number of 14-steps paths starting at $(1,1)$ and 
ending at $(x',y')$, for $(x',y') \in   \llbracket  1,14   \rrbracket
\times \llbracket  1,14  \rrbracket$.}

\end{figure} 

 
\end{document}

  