%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[final]{FPSAC2022}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}

\usepackage[backend=bibtex]{biblatex}
\usepackage{paralist}


\newcommand{\Bgf}{{\sf B}}
\newcommand{\Cgf}{{\sf C}}
\newcommand{\Dgf}{{\sf D}}
\newcommand{\Egf}{{\sf E}}
\newcommand{\Fgf}{{\sf F}}
\newcommand{\Ggf}{{\sf G}}
\newcommand{\Hgf}{{\sf H}}
\newcommand{\Lgf}{{\sf L}}
\newcommand{\Pgf}{{\sf P}}
\newcommand{\Qgf}{{\sf Q}}
\newcommand{\Rgf}{{\sf R}}
\newcommand{\Sgf}{{\sf S}}
\newcommand{\Ugf}{{\sf U}}
\newcommand{\Vgf}{{\sf V}}

\newcommand{\cC}{{\mathcal C}}
\newcommand{\cQ}{{\mathcal Q}}
\newcommand{\cW}{{\mathcal W}}

\renewcommand{\th}{\vartheta}

\usepackage{lipsum}

\usepackage{enumitem}
%% define your title in the usual way
\title{Enumeration of Walks with Small Steps Avoiding a Quadrant}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[A.~E.~Price]{Andrew Elvey Price\thanks{\href{mailto:andrew.elvey@univ-tours.fr}{andrew.elvey@univ-tours.fr}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}CNRS, Institut Denis Poisson, Univertsit\'e de Tours, France}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We address the enumeration of walks with weighted small steps avoiding a quadrant. In particular we give an exact, integral-expression solution for the generating function ${\sf C}(x,y;t)$ counting these walks by length and end-point. Moreover, we determine precisely when this generating function is algebraic, D-finite or D-algebraic with respect to $x$, showing that this complexity is the same as for walks in the quarter-plane with the same starting point, as long as the starting point $(p,q)$ of the walks lies in the quarter plane then. Finally, we give an integral-free expression for the solution in the cases where $(p,q)$ lies just outside the quarter plane, that is $p=0$ or $q=0$ with our convention, proving a conjecture of Raschel and Trotignon.}


%% put your keywords here, or comment this out if you don't have them yet
\keywords{lattice path, elliptic function, cone}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, i.e. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%\usepackage[backend=bibtex]{biblatex}
\addbibresource{biblio.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}


The systematic study of walks with small steps in the quarter plane was initiated by Bousquet-M\'elou and Mishna in 2010 \cite{bousquet2010walks}, and since then there has been great progress on the model \cite{bostan2010complete,fayolle2010holonomy,raschel2012counting,mishna2009two,
melczer2014singularity,
bernardi2017counting,kurkova2012functions,dreyfus2018nature,dreyfus2020walks}. The model is defined as follows: given a step set $S\subset\{-1,0,1\}^{2}\setminus\{(0,0)\}$, determine the generating function
\[\Qgf(x,y;t)=\sum_{n=0}^{\infty}\sum_{i,j\geq1}q(i,j;n)t^{n}x^{i}y^{j},\]
where $q(i,j;n)$ is the number of walks of length $n$, starting at $(1,1)$, and ending at $(i,j)$ using steps in $S$ and staying in the strictly positive quadrant.\footnote{Note that most of the literature has considered the equivalent question of walks starting at $(0,0)$ and staying in the non-strictly positive quadrant, for which the resulting generating function is $\frac{1}{xy}Q(x,y;t)$.}
A priori, there are 256 distinct step sets $S$, but after removing duplicates and cases that are equivalent to half-plane models, Bousquet-M\'elou and Mishna identified 79 non-trivial and combinatorially distinct models. The study of these models is now in some sense complete as it is known for each $S$ precisely where the generating function fits into the hierarchy
\[\text{Algebraic}\subset\text{D-finite}\subset\text{D-Algebraic}.\]
Recall that a generating function is called Algebraic with respect to a certain variable if it satisfies some non-trivial polynomial equation whose coefficients are polynomial in that variable, and it is called D-finite (resp. D-algebraic) if it satisfies a linear (resp. polynomial) differential equation with respect to that variable whose coefficients coefficients are polynomial in that variable. For a multivariate series to be algebraic (resp. D-finite, D-algebraic) it must be algebraic (resp. D-finite, D-algebraic) with respect to each variable.

Of the 79 models proposed by Mishna and Bousquet-M\'elou, 4 models admit an algebraic generating function \cite{bousquet2010walks,bostan2010complete}, 19 further models admit a D-finite generating function \cite{bousquet2010walks,fayolle2010holonomy}, 9 further models admit a D-algebraic generating function \cite{bernardi2017counting,kurkova2012functions} and the remaining 47 models admit a generating function which is not D-algebraic \cite{dreyfus2018nature,dreyfus2020walks}. Moreover, in the 74 cases known as {\em non-singular}, an exact integral expression is known for the generating function \cite{raschel2012counting}, while other exact expressions are known in the $5$ singular cases \cite{mishna2009two,melczer2014singularity}. In recent years a number of articles have focused on the equivalent question for walks avoiding a quadrant \cite{bousquet2016square,raschel2018walks,bousquet_wallner,dreyfus2020nature,
bousquet21+}, that is determining the generating function $\Cgf(x,y;t)$ which counts walks starting at $(1,1)$ whose intermediate points are required to lie in the three-quadrant cone
\[\mathcal{C}=\{(i,j):i>0\text{ or }j>0\}.\]
Between them these 5 articles classify 10 models into the complexity hierarchy (algebraic, D-finite, D-algebraic), while excursions have been enumerated for  4 further models \cite{budd2017winding,elveyprice_winding_FPSAC}. Remarkably the generating function has the same nature in each case as in the quarter plane, a fact that led Dreyfus and Trotignon to conjecture that the nature is the same for any of the 74 non-singular step-sets $S$ \cite{dreyfus2020walks}. We give exact integral expression solutions for $\Cgf(x,y;t)$ in each of these 74 cases, analogous to those of Raschel in the quarter-plane \cite{raschel2012counting}. We then prove that the nature of $\Cgf(x,y;t)$ as a function of $x$ (or $y$) is the same as that of $\Qgf(x,y;t)$, and we conjecture that these series also have the same nature as functions of $t$. In fact we do this in the more general setting of walks with {\em weighted} steps and starting at any point in the positive quadrant or on the positive $x$-axis.

Note that by our definition, steps directly between $(1,0)$ and $(0,1)$ are allowed, whereas they are forbidden in \cite{bousquet_wallner}, for example. We expect the generating function for the model where these steps are forbidden to be closely related to the the model that we study, as found in \cite[Section 8]{bousquet_wallner} for king walks, so we do not expect this to affect difference the nature of the generating function.

%In Section ... we do stuff. ADD MORE OUTLINE.

\section{Functional equations for walks avoiding a quadrant}
We start with a step-set $S\subset\{-1,0,1\}^{2}\setminus\{(0,0)\}$, a weight $w_{s}>0$ for each $s\in S$ and a starting point $(p,q)$ with $p>0$, $q\geq0$. We will determine the generating function $\Cgf(x,y;t)$ counting walks starting at $(p,q)$, taking steps from $S$ with all intermediate points lying in the three-quadrant cone $\mathcal{C}$ and with the weight of the walk being the product of the weights $w_s$ of the steps. Note that the standard starting point is $(p,q)=(1,1)$ and in the unweighted case $w_s=1$ for each $s\in S$.

The following lemma results from considering the final step of a walk counted by $\Cgf(x,y;t)$:
\begin{lem}\label{lem:3q_eq1}
Define the single step generating function $\Pgf(x,y)$ by
\[\Pgf(x,y)=\sum_{(\alpha,\beta)\in S}w_{(\alpha,\beta)}x^{\alpha}y^{\beta}\]
Then there are series $A_{H}(\frac{1}{x};t)\in\frac{t}{x}\mathbb{Z}[\frac{1}{x}][[t]]$, $A_{V}(\frac{1}{y};t)\in\frac{t}{y}\mathbb{Z}[\frac{1}{y}][[t]]$ and $B(t)\in t\mathbb{Z}[[t]]$ which satisfy
\begin{equation}\Cgf(x,y;t)=x^{p}y^{q}+t\Pgf(x,y)\Cgf(x,y;t)-B(t)-A_{H}\left(\frac{1}{x};t\right)-A_{V}\left(\frac{1}{y};t\right).\label{eq:three_quarter_full}\end{equation}
Moreover, this equation together with the fact that $c(i,j;n)=0$ for $i,j\leq 0$, characterises the generating function
\[\Cgf(x,y;t)=\sum_{t\geq 0}\sum_{i,j\in\mathbb{Z}} c(i,j;n)x^{i}y^{j}t^{n},\]
as well as the series $A_{H}$, $A_{V}$ and $B$.
\end{lem}
The series $A_{H}$, $A_{V}$ and $B$ in the lemma above can be understood combinatorially: They count walks starting at $(p,q)$ and ending just outside $\mathcal C$ whose intermediate points all lie within $\mathcal{C}$. More precisely, $A_{H}(\frac{1}{x};t)$  counts those walks ending on the negative $x$-axis, $A_{V}(\frac{1}{y};t)$ counts those walks ending on the negative $y$-axis, and $B(t)$ counts those walks ending at $(0,0)$.
\begin{figure}[ht]
\centering
   \includegraphics[scale=1.2]{Three_quarter_quadrants_FPSAC.pdf}
   \caption{The three-quadrant cone $\mathcal{C}$ partitioned into three quadrants $\mathcal{Q}_{1}$, $\mathcal{Q}_{0}$ and $\mathcal{Q}_{-1}$.}
   \label{fig:three_quarter_quadrants}
\end{figure}

The unusual condition that the coefficients $c(i,j;n)$ of $\Cgf(x,y;t)$ vanish for $i,j\leq 0$ makes this equation difficult to solve directly, so we partition $\mathcal{C}$ into three quadrants $\cQ_{-1}=\{(i,j):i>0,~j<0\}$, $\cQ_{0}=\{(i,j):i>0,~j\geq0\}$ and $\cQ_{1}=\{(i,j):i\leq0,~j>0\}$, as shown in figure \ref{fig:three_quarter_quadrants}. A similar decomposition was used in \cite{bousquet2016square,bousquet_wallner}, but we have shifted the quadrants $\cQ_{-1},\cQ_{0}$ down one space compared to those articles so that it is impossible to step directly between $\cQ_{-1}$ and $\cQ_{1}$ and so that our condition on the starting point $(p,q)$ is now that $(p,q)\in \cQ_{0}$.

%It is convenient to write the equation above in terms of the Kernel $K(x,y;t):=1-tP(x,y)$.

Now, for $j=-1,0,1$, we define $\Qgf_{j}(x,y;t)$ to be the generating function counting walks in $\cC$, starting at $(p,q)$ and ending in $\cQ_{j}$, so
\[\Cgf(x,y;t)=\Qgf_{-1}(x,y;t)+\Qgf_{0}(x,y;t)+\Qgf_{1}(x,y;t),\]
and $\Qgf_{-1}\in\frac{x}{y}\mathbb{Z}\left[x,\frac{1}{y}\right][[t]]$, $\Qgf_{0}\in x\mathbb{Z}\left[x,y\right][[t]]$ and $\Qgf_{1}\in y\mathbb{Z}\left[\frac{1}{x},y\right][[t]]$. The following lemma rewrites \eqref{eq:three_quarter_full} as three equations characterising $\Qgf_{-1}(x,y;t)$, $\Qgf_{0}(x,y;t)$ and $\Qgf_{1}(x,y;t)$.
\begin{lem}
Define the kernel $K(x,y;t)=t\Pgf(x,y)-1$. There are series $V_{1}(y;t),V_{2}(y;t)\in\mathbb{Z}[y][[t]]$ and $H_{1}(x;t),H_{2}(x;t)\in\mathbb{Z}[x][[t]]$ satisfying the three equations
\begin{align}
K(x,y;t)\Qgf_{-1}(x,y;t)&=A_{V}\left(\frac{1}{y};t\right)+H_{1}(x;t)+\frac{1}{y}H_{2}(x;t)\label{eq:three_quarter_-1}\\
K(x,y;t)\Qgf_{0}(x,y;t)&=-xy+B\left(t\right)-V_{1}(y;t)-xV_{2}(y;t)-H_{1}(x;t)-\frac{1}{y}H_{2}(x;t)\label{eq:three_quarter_0}\\
K(x,y;t)\Qgf_{1}(x,y;t)&=A_{H}\left(\frac{1}{x};t\right)+V_{1}(y;t)+xV_{2}(y;t)\label{eq:three_quarter_1}.
\end{align}
Moreover, these three equations characterise the series $V_{1}(y;t)$, $V_{2}(y;t)$, $\Qgf_{-1}(x,y;t)$, $\Qgf_{0}(x,y;t)$, $\Qgf_{1}(x,y;t)$, $H_{1}(x;t)$, $H_{2}(x;t)$, $A_{H}\left(\frac{1}{x};t\right)$, $A_{V}\left(\frac{1}{y};t\right)$ and $B(t)$.
\end{lem}
Combinatorially, the series $(V_{1}(0;t)-V_{1}(y;t))$ (resp. $xV_{2}(y;t)$, $(H_{1}(x;t)-H_{1}(0,t))$, $\frac{1}{y}(H_{2}(0;t)-H_{2}(x;t))$) counts walks whose final step is from $\cQ_{0}$ (resp. $\cQ_{1}$, $\cQ_{-1}$, $\cQ_{0}$) to $\cQ_{1}$ (resp. $\cQ_{0}$, $\cQ_{0}$, $\cQ_{-1}$).
\subsection{Parameterisation of the kernel curve}
Following the method used in the quarter plane pioneered by Fayolle and Raschel \cite{fayolle1999random,raschel2012counting} we start by fixing $t\in\left(0,\frac{1}{\sum_{s\in S}w_{s}}\right)$ and then we consider the curve $\cW=\{(x,y):K(x,y;t)=0\}$. From now on, we will make the following assumption:\newline
\textbf{Assumption:} $S$ is a non-singular step-set. That is, for any line $\ell$ through the origin, at least one element of $S$ lies on each side of $\ell$.\newline
As explained in \cite{bousquet_wallner}, if $S$ did not have this property, the generating function $\Cgf(x,y;t)$ would be algebraic.

Under this assumption, the curve $\cW$ is known to have genus $1$, so we will be able to parameterise it using elliptic functions $X(z)$ and $Y(z)$. More precisely the following lemma follows from \cite[Proposition 2.1, Lemma 2.6]{dreyfus2019differential}.

\begin{lem}\label{lem:param}
There are meromorphic functions $X(z),Y(z) \colon \mathbb{C}\to\mathbb{C}\cup\{\infty\}$ and numbers $\gamma,\tau\in i\mathbb{R}$ with $\Im(\pi\tau)>\Im(2\gamma)>0$ satisfying the following conditions
\begin{compactitem}
\item $K(X(z),Y(z))=0$
\item $X(z)=X(z+\pi)=X(z+\pi\tau)=X(-\gamma-z)$
\item $Y(z)=Y(z+\pi)=X(z+\pi\tau)=Y(\gamma-z)$
\item $|X(-\frac{\gamma}{2})|,|Y(\frac{\gamma}{2})|<1$
\item Counting with multiplicity, the functions $X(z)$ and $Y(z)$ each contain two poles and two roots in each fundamental domain $\{z_{c}+r_{1}\pi+r_{2}\pi\tau:r_{1},r_{2}\in[0,1)\}$.
\end{compactitem}
Moreover, $X(z)$ and $Y(z)$ are differentially algebraic with respect to $z$.
\end{lem}
We intend to substitute $x\to X(z)$ and $y\to Y(z)$ into \eqref{eq:three_quarter_-1}, \eqref{eq:three_quarter_0} and \eqref{eq:three_quarter_1}, however we can only do this as long as the series in these equations converge, which occurs as long as $|x|\leq 1\leq |y|$ for \eqref{eq:three_quarter_-1}, $|x|,|y|\leq 1$ for \eqref{eq:three_quarter_0} and $|y|\leq 1\leq |x|$ for \eqref{eq:three_quarter_1}. So to substitute $x\to X(z)$ and $y\to Y(z)$, we need to understand how $|X(z)|$ and $|Y(z)|$ compare to $1$, for which we use the following lemma, which follows from \cite[Lemma 2.9]{dreyfus2019differential}.
\begin{figure}[ht]
\centering
   \includegraphics[scale=0.5]{Omega_chart_nopng.pdf}
   \caption{The complex plane partitioned into regions $\Omega_{j}$. For $z$ on the blue lines, $|Y(z)|=1$, while on the red lines $|X(z)|=1$.}
   \label{fig:Omega_chart}
\end{figure}
\begin{lem}\label{lem:Omega}
The complex plane can be partitioned into simply connected regions $\{\Omega_{s}\}_{s\in\mathbb{Z}}$ (see Figure \ref{fig:Omega_chart}) satisfying
\begin{align*}
\bigcup_{s\in\mathbb{Z}}\Omega_{4s}\cup\Omega_{4s+1}&=\{z\in\mathbb{C}:|Y(z)|<1\},\\
\bigcup_{s\in\mathbb{Z}}\Omega_{4s}\cup\Omega_{4s-1}&=\{z\in\mathbb{C}:|X(z)|<1\}
\end{align*}
and for $s\in\mathbb{Z}$,
\begin{align*}
\pi+\Omega_{s}&=\Omega_{s},\\
s\pi\tau+\gamma-\Omega_{2s}\cup\Omega_{2s+1}&=\Omega_{2s}\cup\Omega_{2s+1},\\
s\pi\tau-\gamma-\Omega_{2s}\cup\Omega_{2s-1}&=\Omega_{2s}\cup\Omega_{2s-1}.
\end{align*}
\end{lem}
%\begin{lem}
%The complex plane can be partitioned into simply connected regions $\{\Omega_{s}\}_{s\in\mathbb{Z}}$ satisfying for each $s\in\mathbb{Z}$%\notea{Is this known already?}
%\begin{itemize}
%\item For $z\in\Omega_{4s}$, we have $|X(z)|<1$ and $|Y(z)|<1$,
%\item For $z\in\Omega_{4s+1}$, we have $|Y(z)|<1$ and $|X(z)|\geq1$,
%\item For $z\in\Omega_{4s+2}$, we have $|X(z)|\geq1$ and $|Y(z)|\geq1$,
%\item For $z\in\Omega_{4s+3}$, we have $|Y(z)|\geq1$ and $|X(z)|<1$.
%\item $\Omega_{s}=\Omega_{s}+\pi$,
%\item $\Omega_{s+4}=\Omega_{s}+\pi\tau$,
%\item $\Omega_{s}\cup\Omega_{s+1}$ is simply connected,
%\item $s\pi\tau+\gamma-\Omega_{2s}\cup\Omega_{2s+1}=\Omega_{2s}\cup\Omega_{2s+1}$,
%\item $s\pi\tau-\gamma-\Omega_{2s}\cup\Omega_{2s-1}=\Omega_{2s}\cup\Omega_{2s-1}$.
%\end{itemize}
%\end{lem}

\subsection{Analytic reformulation of functional equations}

Using the results in the previous section, we can substitute $x=X(z)$ and $y=Y(z)$ into \eqref{eq:three_quarter_-1}, \eqref{eq:three_quarter_0} and \eqref{eq:three_quarter_1} for $z$ in the regions $\Omega_{-1}$, $\Omega_{0}$ and $\Omega_{1}$, respectively, yielding \eqref{eq:3qinz-1}, \eqref{eq:3qinz0} and \eqref{eq:3qinz1} in the following proposition:
\begin{prop}
The functions
\begin{align}
\label{eq:LHdefinition}L_{H}(z)&:=H_{1}(X(z);t)+\frac{1}{Y(z)}H_{2}(X(z);t),\qquad&&\text{for $z\in\Omega_{0}\cup\Omega_{-1}$},\\
\label{eq:LVdefinition}L_{V}(z)&:=V_{1}(Y(z);t)+X(z)V_{2}(Y(z);t),\qquad&&\text{for $z\in\Omega_{0}\cup\Omega_{1}$},\\
\label{eq:PVdefinition}P_{V}(z)&:=A_{V}\left(\frac{1}{Y(z)};t\right),\qquad&&\text{for $z\in\Omega_{-1}\cup\Omega_{-2}$},\\
\label{eq:PHdefinition}P_{H}(z)&:=A_{H}\left(\frac{1}{X(z)};t\right),\qquad&&\text{for $z\in\Omega_{1}\cup\Omega_{2}$}.
\end{align}
are well defined and satisfy the equations
\begin{align}
0&=P_{V}(z)+L_{H}(z)\label{eq:3qinz-1}\qquad&&\text{for $z\in\Omega_{-1}$},\\
0&=-X(z)^{p}Y(z)^{q}+B\left(t\right)-L_{V}(z)-L_{H}(z)\label{eq:3qinz0}\qquad&&\text{for $z\in\Omega_{0}$},\\
0&=P_{H}(z)+L_{V}(z)\label{eq:3qinz1}\qquad&&\text{for $z\in\Omega_{1}$}\\
P_{H}(z)&=P_{H}(\pi\tau-\gamma-z)=P_{H}(z+\pi)\label{eq:PH_flippy}\qquad&&\text{}\\
P_{V}(z)&=P_{V}(-\pi\tau+\gamma-z)=P_{V}(z+\pi)\label{eq:PV_flippy}\qquad&&\text{}.
\end{align}
\end{prop}

While these equations are a priori defined on different sets, they can be used to show that the functions extend meromorphically to all of $\mathbb{C}$, and so the equations hold on all of $\mathbb{C}$. Simply taking the sum of the three equations \eqref{eq:3qinz-1}, \eqref{eq:3qinz0} and \eqref{eq:3qinz1} yields \eqref{eq:PH_PV_nice} in the theorem below.
\begin{thm}\label{thm:PH_PV_characterisation}
The functions $P_{H}(z)$ and $P_{V}(z)$ extend to meromorphic functions on $\mathbb{C}$ which, along with the constant $B(t)$, are uniquely defined by the equation
\begin{equation}X(z)^{p}Y(z)^{q}=P_{V}(z)+B(t)+P_{H}(z)\label{eq:PH_PV_nice},\end{equation}
along with \eqref{eq:PH_flippy}, \eqref{eq:PV_flippy} and the conditions
\begin{compactitem}
\item $P_{H}(z)$ has no poles in $\Omega_{0}\cup\Omega_{1}\cup\Omega_{2}$,
\item the poles of $X(z)$ for $z\in\Omega_{1}\cup\Omega_{2}$ are roots of $P_{H}(z)$,
\item $P_{V}(z)$ has no poles in $\Omega_{0}\cup\Omega_{-1}\cup\Omega_{-2}$,
\item the poles of $Y(z)$ for $z\in\Omega_{-1}\cup\Omega_{-2}$ are roots of $P_{Y}(z)$.
\end{compactitem}
\end{thm}

%At first glance it may seem that \eqref{eq:PH_PV_nice} follows from substituting $(x,y)=(X(z),Y(z))$ directly into \eqref{eq:three_quarter_full}, however this ignores the questions of whether the series involved converge and the fact that $P_{H}(z)$ and $P_{V}(z)$ are defined on non-intersecting domains. So in some sense the intermediate steps are just used to understand which domains should be used to define $P_{H}(z)$ and $P_{V}(z)$.

Note that combining \eqref{eq:PH_PV_nice}, \eqref{eq:PH_flippy}, \eqref{eq:PV_flippy} yields
\begin{equation}P_{H}(2\pi\tau-2\gamma+z)-P_{H}(z)=W(z),\label{eq:PH_qdiff}\end{equation}
where $W(z)$ is an elliptic function with periods $\pi$ and $\pi\tau$ given by
\[W(z):=\left(X(z-2\gamma)^{p}-X(z)^{p}\right)Y(z)^{q}.\]

\section{Solving the functional equation}
In the previous section we reduced the problem to finding the unique meromorphic functions $P_{V},P_{H} \colon \mathbb{C}\to\mathbb{C}\cup\{\infty\}$ and constant $B(t)$ characterised by Theorem \ref{thm:PH_PV_characterisation} (for each $t$), as these determine $A_{H}(\frac{1}{x},t)$ and $A_{V}(\frac{1}{y},t)$ using \ref{eq:PHdefinition} and \ref{eq:PVdefinition}, respectively, after which $\Cgf(x,y;t)$ is determined by \eqref{eq:three_quarter_full}. An analogous result was found by Raschel for walks in the quarter plane \cite{raschel2012counting}, the main difference being that the transformations $z\to \pi\tau-\gamma-z$ and $z\to -\pi\tau+\gamma-z$ which fix $P_{H}(z)$ and $P_{V}(z)$ are $z\to \gamma-z$ and $z\to -\gamma-z$ in the quarter plane. Raschel used this equation to derive an integral-expression solution determining $\Qgf(x,y;t)$, and the equation has since been used to determine precisely when $\Qgf(x,y;t)$ is differentially algebraic \cite{bernardi2017counting,dreyfus2018nature,hardouin2020differentially} and to determine when it is algebraic or D-finite with respect to $x$ or $y$ \cite{fayolle2010holonomy,kurkova2012functions}.  

Due to this striking similarity we were able to use these methods to prove the same results for $\Cgf(x,y;t)$, in particular showing that it is algebraic, D-finite or D-algebraic with respect to $x$ (or $y$) in the same cases as $\Qgf(x,y;t)$. We note that Fayolle and Raschel also showed that the unweighted models that are algebraic or D-finite with respect to $t$ have the same nature with respect to $t$, however these results relied on the precise ratios $\frac{\pi\tau}{\gamma}$ that could occur in these cases, so they do not apply so readily to our equation. Nonetheless, we expect that the same result holds for $\Cgf(x,y;t)$.

\subsection{Integral expression}\label{sec:integral}
In this section we give integral expressions analogous to those of Raschel \cite{raschel2012counting} which determine $P_{V}(z)$ and $P_{H}(z)$ exactly. In order to write these expressions, we define an auxiliary elliptic function $\omega(z)$ which satisfies 
\[\omega(z)=\omega(\pi\tau-\gamma-z)=\omega(-\pi\tau+\gamma-z)=\omega(z+\pi)\] and shares the poles of $X(z)$ in $\Omega_{1}\cup\Omega_{2}$, while $1/\omega(z)$ has the same poles as $Y(z)$ in $\Omega_{-1}\cup\Omega_{-2}$. Finally, $\omega(z)/X(z)$ converges to $1$ at the poles of $X(z)$ in $\Omega_{1}\cup\Omega_{2}$.
\begin{thm}\label{thm:integral}
%Let $\delta, \pi\tau-\gamma-\delta\in\Omega_{1}\cup\Omega_{2}$ be the poles of $X(z)$ in this region, and let $\epsilon, -\pi\tau+\gamma-\epsilon\in\Omega_{-1}\cup\Omega_{-2}$ be the poles of $Y(z)$ in this region. Define $\omega(z)$ by
%\[\omega(z):=\frac{\th(z-\epsilon,2\pi\tau-2\gamma)\th(z-\pi\tau+\gamma+\epsilon,2\pi\tau-2\gamma)}{\th(z-\delta,2\pi\tau-2\gamma)\th(z-\pi\tau+\gamma+\delta,2\pi\tau-2\gamma)}.\]
Let $z_{0}\in\Omega_{0}$ and let $\mathcal{L}$ be a path from $z_{0}$ to $z_{0}+\pi$ contained in the closure $\overline{\Omega_{0}}$ of $\Omega_{0}$. Then $P_{V}(z)$, $P_{H}(z)$ and $B(t)$ are given by the integrals
\begin{align}
P_{H}(u)&=\frac{1}{2\pi i t}\int_{\mathcal{L}}X(z)^{p}Y(z)^{q}\frac{\omega'(z)}{\omega(z)-\omega(u)}dz\qquad&&\text{for $u\in\Omega_{1}\cup\Omega_{2}$}\label{eq:PH_integral}\\
P_{V}(u)&=-\frac{1}{2\pi i t}\int_{\mathcal{L}}X(z)^{p}Y(z)^{q}\frac{\omega(u)}{\omega(z)}\frac{\omega'(z)}{\omega(z)-\omega(u)}dz\qquad&&\text{for $u\in\Omega_{-1}\cup\Omega_{-2}$}\label{eq:PV_integral}\\
B(t)&=-\frac{1}{2\pi i t}\int_{\mathcal{L}}X(z)^{p}Y(z)^{q}\frac{\omega'(z)}{\omega(z)}dz\qquad\label{eq:C_integral}&&
\end{align}
\end{thm}
The proof of this theorem involves checking that these expressions satisfy the conditions in Theorem \ref{thm:PH_PV_characterisation}.

\subsection{Classification of $\Cgf(x,y;t)$ into complexity hierarchy}\label{sec:classification}
In this section we very briefly describe the properties of the step set $S$, or equivalently $X(z)$ and $Y(z)$, which determine the nature of the generating function $\Cgf(x,y;t)$.

In certain cases, called {\em finite group} cases, $\gamma=\frac{M}{N}\pi\tau$ for some positive $M,N\in\mathbb{Z}$ independent of $t$. Then applying \eqref{eq:PH_qdiff} $N$ times yields
\[P_{H}(2\pi\tau(N-M)+z)-P_{H}(z)=P_{H}((2\pi\tau-2\gamma)N+z)-P_{H}(z)=E(z),\]
where $E(z)$ is called the orbit sum of the model. We can use this equation to solve for $P_{H}(z)$, yielding an expression for $\Cgf(x,y;t)$ which is D-finite in $x$. in the cases where $E(z)=0$, we can even prove that $\Cgf(x,y;t)$ is algebraic in $x$.

In all other cases we have $\frac{\gamma}{\pi\tau}\notin\mathbb{Q}$ for generic $t$. The model is then said to decouple if there are rational functions $R_{1}$, $R_{2}$ satisfying $X(z)^{p}Y(z)^{q}=R_{1}(X(z))+R_{2}(Y(z))$. These cases can be solved  (with integral-free expressions) as, using \eqref{eq:PH_PV_nice}, the function
\[f(z):=R_{1}(X(z))-P_{H}(z)=-R_{2}(Y(z))+B(t)+P_{v}(z)\]
is an elliptic function which can be determined exactly. In these cases every function used is D-algebraic in all of its variables.

Finally in the infinite group cases which do not decouple, the generating function can be shown to be non-D-algebraic in $x$ using Galois theory of $q$-difference equations, as in \cite{dreyfus2018nature,hardouin2020differentially} for $\Qgf(x,y;t)$.

\subsection{Special case: walks starting on $x$-axis}\label{sec:xaxis}
We will now study the special cases where the walk starts at some point $(p,0)$ for $p>0$. Trotignon and Raschel conjectured that with this starting point all finite group models admit algebraic generating functions \cite{raschel2018walks}. Indeed, if $q=0$ it is easy to see that the orbit sum $E(z)$ defined is section \ref{sec:classification} is equal to $0$, so this follows from our more general results. Moreover, if $q=0$, the model trivially decouples, so even in the infinite group case the generating function $\Cgf(x,y;t)$ is D-algebraic.

The following lemma follows directly from Theorem \ref{thm:PH_PV_characterisation}, where $\omega(z)$ is defined as in Section \ref{sec:integral}.
\begin{lem}\label{lem:P-xaxis}
If the starting point of the walks is $(p,0)$ for some $p\geq 1$, then there is a degree $p$ polynomial $H$ satisfying
\begin{align}
P_{V}(z)&=H(\omega(z))-H(0),\\
B(t)&=H(0),\\
P_{H}(z)&=X(z)^{p}-H(\omega(z)).\label{eq:PH_jstart}
\end{align}
Moreover, this polynomial is uniquely determined by the fact that the right hand side of \eqref{eq:PH_jstart} has a root at $z=\delta$.
\end{lem}
In fact, we can convert these directly to formulae for $A_{H}$, $A_{V}$ and $B$ using series $W_{1}\left(\frac{1}{x};t\right)\in x\mathbb{Z}[\frac{1}{x}][[t]]$ and $W_{2}\left(\frac{1}{y};t\right)\in \frac{1}{y}\mathbb{Z}[\frac{1}{y}][[t]]$ satisfying $W_{1}\left(\frac{1}{X(z)};t\right)=\omega(z)$
for $z\in\Omega_{-1}\cup\Omega_{-2}$ and $W_{2}\left(\frac{1}{Y(z)};t\right)=\omega(z)$ for $z\in\Omega_{1}\cup\Omega_{2}$. Note that these depend on the step-set but not the starting point $(p,q)$ of the walk. For general $p$, we can rewrite Lemma \ref{lem:P-xaxis} as the following theorem:
\begin{thm}\label{thm:p0}
If the starting point of the walks is $(p,0)$ for some $p\geq 1$, then there is a degree $p$ polynomial $H$ satisfying
\begin{align}
A_{V}\left(\frac{1}{y}\right)&=H\left(W_{2}\left(\frac{1}{y};t\right)\right)-H(0),\\
B(t)&=H(0),\\
A_{H}\left(\frac{1}{x}\right)&=x^{p}-H\left(W_{1}\left(\frac{1}{x};t\right)\right).\label{eq:A_jstart}
\end{align}
Moreover, this polynomial is uniquely determined by the fact that the right hand side of \eqref{eq:A_jstart} is a series in $\frac{1}{x}\mathbb{Z}[\frac{1}{x}][[t]]$.
\end{thm}
In the $p=1$ case, we have $W_{2}\left(\frac{1}{y};t\right)=A_{V}\left(\frac{1}{y}\right)$ and $W_{1}\left(\frac{1}{x};t\right)=x-B(t)-A_{H}\left(\frac{1}{x}\right)$, which can be used as alternative definitions for $W_{1}$ and $W_{2}$.
\subsection{Special case: simple walks}
We now describe the case of simple walks, that is, unweighted walks with step-set $S=\{(0,1),(1,0),(0,-1),(-1,0)\}$. In this case $X(z)$ and $Y(z)$ can be written in terms of the Jacobi theta function
\[\th(z,\tau):=\sum_{n=0}^{\infty}e^{i\pi\tau n(n+1)}\left(e^{(2n+1)iz}-e^{-(2n+1)iz}\right).\]
as
\begin{align*}
X(z)&=e^{-i\gamma}\frac{\th(z,\tau)\th(z+\gamma,\tau)}{\th(z-\gamma,\tau)\th(z+2\gamma,\tau)}~~~~~\text{and}~~~~~Y(z)=e^{-i\gamma}\frac{\th(z,\tau)\th(z-\gamma,\tau)}{\th(z+\gamma,\tau)\th(z-2\gamma,\tau)},
\end{align*}
where $\gamma=\frac{\pi\tau}{4}$ and is related to $t$ by
\[e^{-i\gamma}\frac{\th\left(\frac{\gamma}{2},\tau\right)^{2}}{\th\left(\frac{3\gamma}{2},\tau\right)^{2}}=\frac{1+2t-\sqrt{1+4t}}{2t}.\]
Moreover, the function $\omega(z)$ defined in Section \ref{sec:integral} is given by
\[\omega(z)=e^{-3i\gamma}\frac{\th(2\gamma,\tau)\th'(0,\frac{3\tau}{2})\th(\gamma,\frac{3\tau}{2})}{\th'(0,\tau)\th(2\gamma,\frac{3\tau}{2})\th(3\gamma,\frac{3\tau}{2})}\cdot\frac{\th(z+\gamma,\frac{3\tau}{2})\th(z+2\gamma,\frac{3\tau}{2})}{\th(z-\gamma,\frac{3\tau}{2})\th(z+4\gamma,\frac{3\tau}{2})},\]
%\[e^{-2i\gamma}\frac{\th(z+\gamma,\frac{3\tau}{2})\th(z+2\gamma,\frac{3\tau}{2})}{\th(z-\gamma,\frac{3\tau}{2})\th(z+4\gamma,\frac{3\tau}{2})},\]
which has $\pi$ and $\frac{3\pi\tau}{2}$ as periods. Since $X(z)$ and $\omega(z)$ share the periods $\pi$ and $3\pi\tau$, they are related by a polynomial equation. %In the case that $(p,q)=(1,0)$, we get the following simple formula for $P_{V}(z)$:
%\[P_{V}(z)=e^{-3i\gamma}\frac{\th(2\gamma,\tau)\th'(0,\frac{3\tau}{2})\th(\gamma,\frac{3\tau}{2})}{\th'(0,\tau)\th(2\gamma,\frac{3\tau}{2})\th(3\gamma,\frac{3\tau}{2})}\cdot\frac{\th(z+\gamma,\frac{3\tau}{2})\th(z+2\gamma,\frac{3\tau}{2})}{\th(z-\gamma,\frac{3\tau}{2})\th(z+4\gamma,\frac{3\tau}{2})}\]
One such equation is
\[\frac{1}{2t}-Y(z)-\frac{1}{Y(z)}=X(z)+\frac{1}{X(z)}-\frac{1}{2t}=\frac{\omega(z)+c_{1}}{\omega(z)-c_{1}}\left(\omega(z)+\frac{c_{1}^{2}}{\omega(z)}+c_{2}\right),\]
where $c_{1}$ and $c_{2}$ are given by
\begin{align*}
c_{1}%=\omega(0)
&=-e^{-i\gamma}\frac{\th(2\gamma,\tau)\th'(0,\frac{3\tau}{2})\th(\gamma,\frac{3\tau}{2})}{\th'(0,\tau)\th(2\gamma,\frac{3\tau}{2})\th(3\gamma,\frac{3\tau}{2})},\\
c_{2}&
%=-\frac{1+4t}{2t}\cdot \frac{P_{V}(\frac{\gamma}{2})-c_{1}}{P_{V}(\frac{\gamma}{2})+c_{1}}-P_{V}\left(\frac{\gamma}{2}\right)-\frac{c_{1}^{2}}{P_{V}(\frac{\gamma}{2})}
=\frac{1+4t}{2t}\cdot \frac{1+c_{3}}{1-c_{3}}+c_{1}c_{3}+\frac{c_{1}}{c_{3}},~~~~~~~\text{where}~~~~~~~c_{3}=-e^{i\gamma}\frac{\th(\frac{5\gamma}{2},\frac{3\pi\tau}{2})}{\th(\frac{\gamma}{2},\frac{3\pi\tau}{2})}.
\end{align*}
So the series $W_{1}\left(\frac{1}{x};t\right)\in x\mathbb{Z}[\frac{1}{x}]$ and $W_{2}\left(\frac{1}{y};t\right)\in \frac{1}{y}\mathbb{Z}[\frac{1}{y}]$ defined in Section \ref{sec:xaxis} satisfy 
\begin{align*}-\frac{1}{2t}+x+\frac{1}{x}&=\frac{W_{1}\left(\frac{1}{x};t\right)+c_{1}}{W_{1}\left(\frac{1}{x};t\right)-c_{1}}\left(W_{1}\left(\frac{1}{x};t\right)+\frac{c_{1}^{2}}{W_{1}\left(\frac{1}{x};t\right)}+c_{2}\right),\\\frac{1}{2t}-y-\frac{1}{y}&=\frac{W_{2}\left(\frac{1}{y};t\right)+c_{1}}{W_{2}\left(\frac{1}{y};t\right)-c_{1}}\left(W_{2}\left(\frac{1}{y};t\right)+\frac{c_{1}^{2}}{W_{2}\left(\frac{1}{y};t\right)}+c_{2}\right).\end{align*}
Then for any starting point $(p,0)$, the generating functions $A_{H}$, $A_{V}$, $B$ and hence $\Cgf(x,y;t)$ can be determined by Theorem \ref{thm:p0}. Moreover, $c_{1}$, $c_{2}$ and $t$ can be shown to be modular functions of $\tau$, so they are all algebraically related. Hence in these cases the generating function $\Cgf(x,y;t)$ is algebraic in $t$ as well as the other variables.
\section{Nature of $\Cgf(x,y;t)$ with respect to $t$}
The main remaining problem is to prove that the generating function $\Cgf(x,y;t)$ has the same nature (algebraic, D-finite, D-algebraic) as a function of $t$ as it does as a function of $x$ and $y$. Even for $\Qgf(x,y;t)$, which counts walks confined to a quadrant, this has not been proven for weighted models, so it is not surprising that we have so far been unable to prove it for $\Cgf(x,y;t)$. However, we expect that if this is proven for $\Qgf(x,y;t)$, the result for $\Cgf(x,y;t)$ will follow using the same method applied to Theorem \ref{thm:PH_PV_characterisation}.

\printbibliography



\end{document}
