%% 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[submission]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc
\articlenumber{26}
\addbibresource{26.bib}
%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{graphicx}
\usepackage{lipsum}
\usepackage{verbatim}
\usepackage{subcaption}
\usepackage{tikz}
\usetikzlibrary{decorations.markings}
\usepackage{color}
% this forces equation labels to be the normal size
\makeatletter
\def\maketag@@@#1{\hbox{\m@th\normalfont\normalsize#1}}
\makeatother
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\crefname{conjecture}{Conjecture}{Conjectures}
%% define your title in the usual way
\title[Quarter-plane lattice paths with interacting boundaries]{Quarter-plane lattice paths with interacting boundaries: Kreweras and friends}
%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Nicholas R. Beaton\thanks{\href{mailto:nrbeaton@unimelb.edu.au}{nrbeaton@unimelb.edu.au}}, Aleksander L. Owczarek\thanks{\href{mailto:owczarek@unimelb.edu.au}{owczarek@unimelb.edu.au}}, and Ruijie Xu\thanks{\href{mailto:ruijiex1@student.unimelb.edu.au}{ruijiex1@student.unimelb.edu.au}}}
%% then use \addressmark to match authors to institutions here
\address{School of Mathematics and Statistics, University of Melbourne, Australia}
%% 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 study lattice paths in the quarter-plane which accrue weights with each visit to the $x$-axis, the $y$-axis and the origin. In particular, we address two cases which were only partially solved in a recent work by Beaton, Owczarek and Rechnitzer (2018): Kreweras and reverse Kreweras paths. Without weights these are two of the famous algebraic quarter-plane models. We show that the reverse Kreweras model remains algebraic for all possible weights, while the nature of the Kreweras model appears to depend on the value of the weights and the endpoint of the paths.}
%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}
%% put your keywords here, or comment this out if you don't have them yet
\keywords{lattice paths, quarter-plane, kernel method, algebraic generating functions}
%% 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, ie. [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
%\addbibresource{reportbib.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands
\newcommand{\nicksays}[1]{\textbf{\color{red}#1}}
\newcommand{\olx}{\overline{x}}
\newcommand{\oly}{\overline{y}}
\newcommand{\ola}{\overline{a}}
\newcommand{\olb}{\overline{b}}
\newcommand{\olc}{\overline{c}}
\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}
Lattice paths in the quarter-plane have led to a rich body of research in combinatorics, with connections to probability theory, algebra, complex analysis and statistical physics~\cite{bostan2009automatic,bousquet2005walks,bousquet2010walks,fayolle1999random,mishna2009classifying,raschel2012}. The standard practice is to choose a subset $\mathcal S$ of the eight ``short'' steps $\{\text{E}, \text{NE}, \text{N}, \text{NW}, \text{W}, \text{SW}, \text{S}, \text{SE}\}$ and study the properties of random walks which are only allowed to take steps from $\mathcal S$. These properties may include the number of paths of length $n$ and the asymptotics thereof, the nature of the generating function counting the paths, or bijections with other combinatorial objects. The answers to these questions may depend on where the paths start and end: it is common to consider paths which start at the origin, but they can be conditioned to end back at the origin, on one of the boundaries, or anywhere in the quarter-plane.
One connection with statistical physics was explored in~\cite{tabbara_exact_2014}. The subject was a two-dimensional model of interacting directed polymers above an impenetrable surface. Two paths of length $n$ start at the origin and each can step NE or SE; they can share vertices and edges but cannot cross; and they must remain on or above the $x$-axis. Two weights (in physics these are known as \emph{Boltzmann weights} or \emph{fugacities}) were introduced: every time the bottom walk touches the surface it accrues weight $a$, and every time the two walks touch they accrue weight $c$ (when both happen at once the weight is $ac$). The goal was to compute the generating function
\begin{equation}
F(z;a,c) = \sum_{n,m_a,m_c}f_{n,m_a,m_c} z^n a^{m_a} c^{m_c}
\end{equation}
where $f_{n,m_a,m_c}$ is the number of configurations of length $n$ with $m_a$ visits to the surface and $m_c$ shared vertices. From a physics perspective, it is the singularity structure of $F(z;a,c)$ which is of interest, as this can be used to determine the \emph{free energy} and the \emph{phase diagram} of the model. (For brevity we will dwell no further on physics here.)
The connection to a quarter-plane path may not be immediately obvious but is in fact straightforward. Every polymer configuration of length $n$ can be mapped to a single quarter-plane path taking steps in $\mathcal{S} = \{\text{E}, \text{NW}, \text{W}, \text{SE}\}$. When the pair both step NE (resp.~SE), the quarter-plane path steps E (resp.~W); when the pair step away from each other (resp.~towards each other), the quarter-plane path steps NW (resp.~SE). Moreover, vertices in the boundary visited by the bottom polymer correspond to visits to the $y$-axis by the single path, and shared vertices between the two polymers correspond to visits to the $x$-axis by the single path. The numbers $f_{n,m_a,m_c}$ can thus be repurposed -- they now count quarter-plane paths of length $n$ taking steps from $\mathcal{S}$, with $m_a$ visits to the $y$-axis and $m_c$ visits to the $x$-axis.
\begingroup\emergencystretch=1em
This idea was recently expanded in~\cite{beaton2018exact}, where the authors studied all 23 non-isomorphic step sets whose generating functions are known to be algebraic or D-finite~\cite{raschel2012}, and considered what happens when visits to the $x$- and $y$-axes are taken into account. In particular, they associated weight $a$ with the $x$-axis and weight $b$ with the $y$-axis, and investigated the properties of the generating function of walks which start and end at the origin for different values of $(a,b)$. For two models ($\{\text{NE},\text{NW},\text{SW},\text{SE}\}$ and $\{\text{NE},\text{N},\text{NW},\text{SW},\text{S},\text{SE}\}$) it was proved that the generating function is D-finite for all $(a,b)$;\footnote{The D-finiteness of the second of these was overlooked in the first version of~\cite{beaton2018exact}.} for some others it was shown that the nature of the generating function depends on the values of $(a,b)$; but for many, no solution could be found at all.
\endgroup
One intriguing case which was partially solved in~\cite{beaton2018exact} is Kreweras walks ($\{\text{NE}, \text{W}, \text{S}\}$). When $(a,b)=(1,1)$ this is one of only four cases which have algebraic generating functions~\cite{bousquet2005walks}; it was shown in~\cite{beaton2018exact} that this also holds when $a=b$. That result easily generalises to walks ending anywhere, or on the boundaries. However, series analysis using the Ore algebra package for Sage~\cite{kauers2015ore} indicated that the generating function for walks ending at the origin is in fact algebraic \emph{for all} $(a,b)$. Note that for walks ending at the origin, the generating function for reverse Kreweras walks ($\{\text{E}, \text{N}, \text{SW}\}$) is identical to the Kreweras generating function. For walks ending elsewhere, they are not the same.
It is the Kreweras and reverse Kreweras models which are the focus of this extended abstract. We generalise the work of~\cite{beaton2018exact} by including a third weight $c$ for visits to the origin. For walks ending at the origin, we prove that the generating function is algebraic for all $(a,b,c)$. The solution involves multiple applications of the kernel method. Along the way we also show that for reverse Kreweras walks, the generating functions for walks ending anywhere, or on the boundaries, are also algebraic. Surprisingly, however, things seem to be different for Kreweras walks: when $a\neq b$ and $a,b\neq 1$, the solutions become much more complicated, and it seems likely that they are not even D-finite.
They layout of the remainder of this paper is as follows. In \cref{sec:definitions} we give some definitions and state the main results. Then in \cref{sec:reverse} we outline the methodology for solving reverse Kreweras walks for general $(a,b,c)$. In \cref{sec:kreweras} we discuss Kreweras walks and how they differ from the reverse Kreweras model. Some comments and further questions are discussed in \cref{sec:conclusion}.
There are a number of complicated polynomials and algebraic expressions which we were unable to fit into this extended abstract. A \textsc{Mathematica} notebook is available on the second author's website\footnote{\href{http://www.nicholasbeaton.com/papers.html}{www.nicholasbeaton.com/papers}} which provides these quantities and verifies a number of equations. A longer paper which covers this and other material is also in preparation.
\section{The model and main results}\label{sec:definitions}
\subsection{Definition and notations}
We first define some operations and notations used in this paper. We write $[x^i]f(x)$ as the coefficient of $[x^i]$ in the power series expansion of $f(x)$. Similarly, $[x^>]f(x)$, $[x^<]f(x)$, and $[x^\geq]f(x)$ are the terms with positive, negative and non-negative powers of $x$.
Next, recall that a function $f(x)$ is \emph{algebraic} if there exists a polynomial $P(x,y)$ such that $P(x,f(x)) = 0$; $f(x)$ is \emph{differentiably finite} (D-finite) if it is a solution to a linear ODE whose coefficients are polynomials in $x$; and $f(x)$ is \emph{differentiably algebraic} (D-algebraic) if there exists a polynomial $R(x,y_0,\dots,y_k)$ such that $R(x,f(x),f'(x),\dots,f^{(k)}(x)) = 0$. All algebraic functions are D-finite and all D-finite functions are D-algebraic. The ratio of two D-finite functions is D-algebraic, but in general not D-finite.
For a given step set, we denote by $q_{n,k,l,h,v,u}$ the number of walks of length $n$ that start at $(0,0)$ and end at $(k,l)$, which visit the horizontal boundary (except the origin) $h$ times, the vertical boundary (except the origin) $v$ times, and the origin $u$ times (the initial vertex does not count as a visit). See \cref{fig:paths}. The associated generating function is
\begin{equation}
Q(t;x,y;a,b,c)\equiv Q(x,y) = \sum_{n\geq 0}t^n\sum_{k,\ell,h,v,u\geq 0}q_{n,k,\ell,h,v,u}x^k y^\ell a^h b^v c^u\equiv \sum_{n\geq 0}t^n Q_n(x,y).\label{function}
\end{equation}
We also define generating functions for walks ending on a diagonal line:
\begin{equation}
Q^\mathrm{d}_j(t;x;a,b,c) \equiv Q^\mathrm{d}_j(x) = \sum_{n\geq 0}t^n\sum_{k,h,v,u\geq 0}q_{n,k,k+j,h,v,u}x^k a^h b^v c^u.
\end{equation}
Finally, for brevity, write
\begin{equation}
Q_{i,j}(t;a,b,c) \equiv Q_{i,j} = [x^i y^j]Q(x,y).
\end{equation}
We will write $\olx = \frac1x$ and likewise for other variables.
\subsection{The general functional equation}
For a given step set $\mathcal{S} \subset \{-1,0,1\}\times \{-1,0,1\}$, the \emph{step set generator} is
\begin{equation}
S(x,y) = \sum_{(i,j)\in \mathcal{S}}x^i y^j.
\end{equation}
We then write
\begin{equation}\label{S}
S(x,y) = A_{-1}(x)\oly + A_0(x) + A_1(x)y = B_{-1}(y)\olx + B_0(y) + B_{1}(y)x.
\end{equation}
In addition, we denote $\epsilon = [x^{-1}y^{-1}]S(x,y)$.
The following theorem can be proved in exactly the same way as~\cite[Theorem~6]{beaton2018exact}; the only difference is that weight $ab$ was used for visits to the origin in that paper, while weight $c$ is used here.
\begin{theorem}\label{thm:main_func_eqn}
The generating function $Q(x,y)$, with weight $a$ associated with vertices on the $x$-axis (except the origin), weight $b$ associated with vertices on the $y$-axis (except the origin) and weight $c$ associated with the origin, satisfies the functional equation
\begin{multline}\label{eqn:main_func_eqn}
xyK(x,y)Q(x,y) = xy\olc + x\Big(y-y\ola-tA_{-1}(x)\Big)Q(x,0) + y\left(x-x\olb-tB_{-1}(y)\right)Q(0,y) \\
+\left(xy\left(\ola + \olb - \olc - 1\right) + t\epsilon\right)Q_{0,0}
\end{multline}
where $K(x,y) = 1-tS(x,y)$ is the \emph{kernel} of the model.
\end{theorem}
\begin{figure}
\centering
\resizebox{0.45\textwidth}{!}{
\begin{tikzpicture}
\tikzset{ac/.style={circle, line width=1.5pt, draw=black, fill=red, inner sep=2.5pt}}
\tikzset{bc/.style={circle, line width=1.5pt, draw=black, fill=blue, inner sep=2.5pt}}
\tikzset{cc/.style={circle, line width=1.5pt, draw=black, fill=black, inner sep=2.5pt}}
\tikzset{vert/.style={circle, line width=1.5pt, draw=black, fill=white, inner sep=2.5pt}}
\draw [gray, line width=10pt] (-0.2,5.8) -- (-0.2,-0.2) -- (5.8,-0.2);
\begin{scope}[line width=3pt, decoration={markings,mark=at position 0.65 with {\arrow{>}}}]
\draw [postaction=decorate] (0,0) node [cc] {} -- (1,1);
\draw [postaction=decorate] (1,1) node [vert] {} -- (1,0);
\draw [postaction=decorate] (1,0) node [ac] {} -- (2,1);
\draw [postaction=decorate] (2,1) node [vert] {} -- (3,2);
\draw [postaction=decorate] (3,2) node [vert] {} -- (2,2);
\draw [postaction=decorate] (2,2) node [vert] {} -- (3,3);
\draw [postaction=decorate] (3,3) node [vert] {} -- (2,3);
\draw [postaction=decorate] (2,3) node [vert] {} -- (1,3);
\draw [postaction=decorate] (1,3) node [vert] {} -- (0,3);
\draw [postaction=decorate] (0,3) node [bc] {} -- (0,2);
\draw [postaction=decorate] (0,2) node [bc] {} -- (1,3);
\draw [postaction=decorate] (1,3) node [vert] {} -- (2,4);
\draw [postaction=decorate] (2,4) node [vert] {} -- (3,5);
\draw [postaction=decorate] (3,5) node [vert] {} -- (3,4);
\draw [postaction=decorate] (3,4) node [vert] {} -- (4,5);
\draw [postaction=decorate] (4,5) node [vert] {} -- (4,4);
\draw [postaction=decorate] (4,4) node [vert] {} -- (4,3);
\draw [postaction=decorate] (4,3) node [vert] {} -- (4,2);
\draw [postaction=decorate] (4,2) node [vert] {} -- (5,3);
\draw [postaction=decorate] (5,3) node [vert] {} -- (5,2);
\draw [postaction=decorate] (5,2) node [vert] {} -- (5,1);
\draw [postaction=decorate] (5,1) node [vert] {} -- (5,0);
\draw [postaction=decorate] (5,0) node [ac] {} -- (4,0);
\draw [postaction=decorate] (4,0) node [ac] {} -- (3,0);
\draw [postaction=decorate] (3,0) node [ac] {} -- (4,1) node [vert] {};
\end{scope}
\draw [line width=2pt, <->] (8,2) -- (8,3) -- (9,4);
\draw [line width=2pt, ->] (8,3) -- (7,3);
\end{tikzpicture}
}
\caption{A Kreweras path of length 25 in the quarter-plane. This path contributes weight $t^{25}x^4ya^4b^2$ to the generating function $Q(x,y)$.}
\label{fig:paths}
\end{figure}
\subsection{Main results}
For reverse Kreweras walks, the step set is $\{\text{E},\text{N},\text{SW}\}$. Then~\eqref{eqn:main_func_eqn} becomes
\begin{multline}\label{eqn:rk_main_func_eqn}
xy(1-t(x+y+\olx\oly))Q(x,y) = xy\olc + x\Big(y - y\ola - t\olx\Big)Q(x,0) + y\Big(x - x\olb - t\oly\Big)Q(0,y) \\
+\Big(xy\Big(\ola+\olb-\olc-1\Big)+t\Big)Q_{0,0}.
\end{multline}
Our aim is to solve this equation. From previous work~\cite{bousquet2005walks,bousquet2010walks,mishna2009classifying}, it is known that $Q(x,y)$ is algebraic when $a=b=c=1$. For arbitrary $a,b,c$, we have the following theorem.
\begin{theorem}\label{1111}
For reverse Kreweras walks, the generation functions $Q_{0,0}$, $Q(x,0)$, $Q(0,y)$ and $Q(x,y)$ are algebraic for all $(a,b,c)$.
\end{theorem}
\begin{corollary}\label{cor:Krew_q00_alg}
For Kreweras walks, the generating function $Q_{0,0}$ is algebraic for all $(a,b,c)$.
\end{corollary}
Some further conjectures and questions are given in \cref{sec:kreweras,sec:conclusion}.
\section{Reverse Kreweras walks via the algebraic kernel method}\label{sec:reverse}
When $a=b=c=1$, the solutions for all 23 D-finite quarter-plane models can be found by first exploiting the symmetries of the kernel, and applying them to the main functional equation~\eqref{eqn:main_func_eqn} in order to obtain new equations.\footnote{For a few special models there are also other methods -- see \cite[Tables 1--3]{bousquet2010walks} for a thorough roundup.} To then apply the \emph{algebraic kernel method}, these equations are combined in order to eliminate certain terms, and then new equations are found by separating the parts which have positive, negative and/or zero powers of $x$ or $y$~\cite{bousquet2005walks}.
This is one method that has been used to solve the $a=b=c=1$ cases for both Kreweras and reverse Kreweras~\cite{bousquet2005walks,bousquet2010walks,mishna2009classifying}, as well as the $a=b$ and $c=ab$ case for Kreweras~\cite{beaton2018exact}. Each time only half of the symmetries of the kernel were used; the particular combination used is called a \emph{half-orbit sum}. Here we will again use the algebraic kernel method, however, we will make use of \emph{both full- and half-orbit sums}.
The whole process is comprised of three main steps. First, we will recall the symmetry group of the kernel and use it to take the full-orbit sum, and extract the constant term with respect to $y$ and then the positive and negative parts with respect to $x$, to obtain two ``reflection symmetries''. Secondly, we take a half-orbit sum and again take the constant term with respect to $y$, use the equations obtained from the full-orbit sum to eliminate certain terms, and then once again take the positive and negative parts with respect to $x$. This yields two equations which each have a kernel-like form. Finally, we cancel both new kernels and combine the resulting equations to obtain the solution.
\subsection{The group and the full-orbit sum}
Recall that $S(x,y) = x + y + \olx\oly$, and notice that the transformations
\begin{equation}
\phi :(x,y) \mapsto (\olx\oly,y) \quad\text{and}\quad \psi:(x,y) \mapsto (x,\olx\oly)
\end{equation}
do not change the kernel. These two transformations are involutions, and generate a group of order six, known as the \emph{group} of the model. The group is isomorphic to $D_3$. The full set of symmetries is
\begin{equation}\label{symmetries}
(x,y) \stackrel{\phi}{\to} (\olx\oly,y) \stackrel{\psi}{\to} (\olx\oly,x) \stackrel{\phi}{\to} (y,x) \stackrel{\psi}{\to} (y,\olx\oly) \stackrel{\phi}{\to} (x,\olx\oly).
\end{equation}
Applying these six symmetries to~\eqref{eqn:rk_main_func_eqn} gives six equations, and an appropriate linear combination eliminates all terms on the right-hand side.
%\footnote{For unweighted quarter-plane models, this is a hallmark of algebraicity.}
The resulting equation is (after dividing by the kernel and clearing denominators)
\begin{multline}\label{eqn:rk_full_orbit_sum}
y(1-b+txb)(1-a+tya)Q(x,y) - \olx(1-a+tya)(tb+xy-xyb)Q(\olx\oly,y) \\
+ \olx(1-b+tyb)(ta+xy-xya)Q(y,\olx\oly) - y(1-a+txa)(1-b+tyb)Q(y,x) \\
+\olx(1-a+txa)(tb+xy-xyb)Q(\olx\oly,x) - \olx(1-b+txb)(ta+xy-xya)Q(x,\olx\oly) = 0.
\end{multline}
The next step is to compute the constant term with respect to $y$ of~\eqref{eqn:rk_full_orbit_sum}. This is straightforward, and for brevity we omit the full expression. After exploiting several boundary relations, it involves unknowns $Q(x,0)$, $Q(0,x)$, $Q^\mathrm{d}_0(\olx)$, $Q^\mathrm{d}_1(\olx)$ and $Q_{0,0}$, with coefficients that are Laurent polynomials in $x$.
To conclude this section, we take the non-negative and non-positive parts of this equation. The first relates $Q(x,0)$ and $Q(0,x)$:
\begin{multline}\label{eqn:rk_y0_posx}
0= \olx\ola\olb\olc(a-b)\left(t^2abc - xc(1-a-b+ab) + tx^2(ab - ac - bc + abc)\right)Q_{0,0} \\
- t^2a(b-1)Q_{1,0}- \olx\ola(1-b+tbx)\left(t^2a^2+x(1-a)(1-txa)\right)Q(x,0) \\
+t^2(a-1)bQ_{0,1} + \olx\olb(1-a+txa)\left(t^2b^2+x(1-b)(1-txb)\right)Q(0,x) -tx(a-b)\olc.
\end{multline}
The second relates $Q^\mathrm{d}_0(\olx)$ and $Q^\mathrm{d}_1(\olx)$:
\begin{multline}\label{eqn:rk_y0_negx}
\olx\olc\left(t^2(ab + ac - bc - abc) + x(1 - b - c + bc)\right. \\
\left. + t^3xabc - tx^2(a - ab - c - ac + bc + abc) + t^2x^3ac(b-1)\right)Q_{0,0} \\
-\olx\left(t^2(2a - 2b - ab) + t^3xab + tx^2(1 + a - b - ab) + x(1+t^2x^2a)(b-1)\right)Q^\mathrm{d}_0(\olx) \\
-t\olx^2\left(2t^2ab + x(2 - a - b) - tx^2(a + b - 2ab)\right)Q^\mathrm{d}_1(\olx) \\
+t^2(a-1)bQ_{0,1} - t^2a(b-1)Q_{1,0} - \olx\olc\left(t^2ab - x(1-txa)(b-1)\right) = 0.
\end{multline}
When $a=b$ these equations are of no use: the first is just a linear combination of the obvious identities $Q(x,0)=Q(0,x)$ and $Q_{1,0}=Q_{0,1}$, while the second is just the relationship between $Q^\mathrm{d}_0(x)$ and $Q^\mathrm{d}_1(x) = \olx Q^\mathrm{d}_{-1}(x)$, evaluated at $x\mapsto\olx$.
\subsection{The half-orbit sum}
We start this section in a similar way as the non-interacting case~\cite{mishna2009classifying}. We put aside~\eqref{eqn:rk_y0_posx} and~\eqref{eqn:rk_y0_negx} and return to the main functional equation~\eqref{eqn:rk_main_func_eqn}. We again use the kernel symmetries~\eqref{symmetries}, but this time only half of them: $(x,y)$, $(\olx\oly,y)$ and $(\olx\oly,x)$. We choose these three in order to get an equation involving $Q(x,0)$ and $Q(0,x)$, so that~\eqref{eqn:rk_y0_posx} can be used to eliminate terms.
Eliminating $Q(0,y)$ and $Q(\olx\oly,0)$ gives a single equation of the form
\begin{multline}
K(x,y)\left(\alpha_{x,y}Q(x,y) + \alpha_{\olx\oly,y}Q(\olx\oly,y) + \alpha_{\olx\oly,x}Q(\olx\oly,x)\right) \\
= \alpha + \alpha_{x,0}Q(x,0) + \alpha_{0,x}Q(0,x) + \alpha_{0,0}Q_{0,0}
\end{multline}
where the coefficients are all Laurent polynomials in $x$ and $y$.
We then divide by $K(x,y)$ and take the constant term with respect to $y$. The left-hand side involves essentially the same calculations as for~\eqref{eqn:rk_full_orbit_sum}. The right side is more complicated because of the $K(x,y)$ in the denominator. However, as per~\cite{bousquet2005walks}, it is possible to write
\begin{equation}\label{eqn:rk_kernel_partial_frac}
\frac{1}{K(x,y)} = A_1 + \frac{A_2}{1-y/\gamma_+} + \frac{A_3}{1- \oly \gamma_- },
\end{equation}
where the $A_i$ are power series in $t$ and independent of $y$, and $\gamma_\pm$ are roots of the kernel:
\begin{equation}
\gamma_+ = \frac{1-tx+\sqrt{\Delta}}{2t} = t^{-1} + O(1) \quad\text{and}\quad \gamma_- = \frac{1-tx-\sqrt{\Delta}}{2t} = t\olx + O(t^2)
\end{equation}
and $\Delta = (1-tx)^2-4t^2\olx$.
With this expansion in hand we can compute the constant term of the right-hand side, and after exploiting boundary relations, end up with an equation of the form
\begin{equation}
\beta + \beta_{x,0}Q(x,0) + \beta_{0,x}Q(0,x) + \beta^\mathrm{d}_{0}Q^\mathrm{d}_0(\olx) + \beta^\mathrm{d}_{1}Q^\mathrm{d}_1(\olx) + \beta_{0,0}Q_{0,0} = 0
\end{equation}
where $\beta^\mathrm{d}_0$ and $\beta^\mathrm{d}_1$ are Laurent polynomials in $x$ and the remaining coefficients are algebraic functions.
At this point we make use of relations~\eqref{eqn:rk_y0_posx} and~\eqref{eqn:rk_y0_negx} that we obtained via the full-orbit sum, and eliminate $Q(0,x)$ and $Q^\mathrm{d}_1(\olx)$. Rearranging,
\begin{multline}\label{eqn:rk_halforbitsum_y0}
\mu_{x,0}Q(x,0) = (\mu+\nu\sqrt{\Delta}) + \nu^\mathrm{d}_0\sqrt{\Delta}Q^\mathrm{d}_0(\olx) \\ + (\mu_{0,0}+\nu_{0,0}\sqrt{\Delta})Q_{0,0} + (\mu_{0,1}+\nu_{0,1}\sqrt{\Delta})Q_{0,1} + (\mu_{1,0}+\nu_{1,0}\sqrt{\Delta})Q_{1,0},
\end{multline}
where the $\mu$ and $\nu$ are all \emph{polynomials} in $x$.
The goal now is to split~\eqref{eqn:rk_halforbitsum_y0} apart into two equations -- one involving $Q(x,0)$ and one involving $Q^\mathrm{d}_0(\olx)$. This can be done by computing the non-negative and non-positive parts (with respect to $x$) of~\eqref{eqn:rk_halforbitsum_y0}. However, the fact that all coefficients are now algebraic complicates matters considerably.
The key insight which allows us to proceed is that $\Delta$ can be factorised in a very useful way~\cite{bousquet2005walks}. The three roots of $\Delta$ are
\begin{align}
\delta_1 &= 4t^2 + 32t^5 + 448t^8 + \dots \\
\delta_{2,3} &= t^{-1} \pm 2t^{1/2} - 2t^2 \pm 5t^{7/2} - \dots
\end{align}
so that
\begin{equation}\label{eqn:rk_Delta_factorisation}
\Delta = \frac{4t^2}{\delta_1}(1-\delta_1\olx)\left(1-\frac{x}{\delta_2}\right)\left(1-\frac{x}{\delta_3}\right).
\end{equation}
Then define
\begin{equation}
\Delta_0 = \frac{4t^2}{\delta_1}, \qquad \Delta_- = 1-\delta_1\olx, \qquad\text{and}\qquad \Delta_+ = \left(1-\frac{x}{\delta_2}\right)\left(1-\frac{x}{\delta_3}\right).
\end{equation}
We have
\begin{align}
\frac{1}{\sqrt{\Delta_+}} &= 1+tx+t^2x^2+t^3x^3+t^4(6x+x^4)+\dots \\
\sqrt{\Delta_0\Delta_-} &= 1 - 2t^2\olx - 4t^3 - 2t^4\olx^2 - 8t^5\olx + \dots
\end{align}
We now take~\eqref{eqn:rk_halforbitsum_y0} and divide by $\sqrt{\Delta_+}$. Each $\mu$ term, divided by $\sqrt{\Delta_+}$, produces only non-negative powers of $x$. Each $\nu$ term, now multiplied by $\sqrt{\Delta_0\Delta_-}$, produces only finitely many non-negative powers of $x$. And importantly, $Q^\mathrm{d}_0(\olx)$ is multiplied by $\sqrt{\Delta_0\Delta_-}$. It is thus possible to compute the positive and non-positive parts of~\eqref{eqn:rk_halforbitsum_y0}. Doing so, rearranging a bit and sending $x\mapsto\olx$ in the second equation gives the expressions
\begin{align}
P_{x,0}Q(x,0) &= \sigma + \sigma_{0,0}Q_{0,0} + \sigma_{0,1}Q_{0,1} + \sigma_{1,0}Q_{1,0} \label{eqn:qx0_pos} \\
P^\mathrm{d}_0Q^\mathrm{d}_0(x) &= \tau + \tau_{0,0}Q_{0,0} + \tau_{0,1}Q_{0,1} + \tau_{1,0}Q_{1,0},\label{eqn:qdx_nonpos}
\end{align}
where
\begin{align}
P_{x,0} &= \left(t^2a^2 - x(1-txa)(a-1)\right)\left(2t^2ab + x(2-a-b) + tx^2(2ab-a-b)\right) \\
P^\mathrm{d}_0 &= \left((ta-x)(a-1) + t^2x^2a^2\right)\left((tb-x)(b-1) + t^2x^2b^2\right)
\end{align}
and the $\sigma$ and $\tau$ coefficients are algebraic functions.
\subsection{The classical kernel method and the algebraic solution}
The forms of~\eqref{eqn:qx0_pos} and~\eqref{eqn:qdx_nonpos} now point to a possible way forward. Each root of $P_{x,0}$ or $P^\mathrm{d}_0$ (in $x$) which has a power series expansion in $t$ will (assuming nothing goes wrong on the right-hand side) give a linear equation in $Q_{0,0}$, $Q_{0,1}$ and $Q_{1,0}$. If three independent equations can be found, we will be done.
Each of the four quadratic factors yields one useful root. From $P_{x,0}$ we have
\begin{align}
\rho_1 &= \frac{t^2a^2}{a-1} + \frac{t^5a^5}{(a-1)^2} + \frac{2t^8a^8}{(a-1)^3} + \frac{5t^{11}a^{11}}{(a-1)^4} + \dots \\
\rho_2 &= \frac{2t^2ab}{a+b-2} + \frac{4t^5a^2b^2(2ab-a-b)}{(a+b-2)^3} + \frac{16t^8a^3b^3 (2ab-a-b)^2}{(a + b-2)^5}
%+ \frac{80t^{11}a^4b^4(2ab-a - b)^3}{(a + b-2)^7 }
+ \dots \\
\intertext{and from $P^\mathrm{d}_0$}
\rho_3 &= ta + \frac{t^4a^4}{a-1} + \frac{2t^7a^7}{(a-1)^2} + \frac{5t^{10}a^{10}}{(a-1)^3} + \frac{14t^{13}a^{13}}{(a-1)^4} + \dots \\
\rho_4 &= tb + \frac{t^4b^4}{b-1} + \frac{2t^7b^7}{(b-1)^2} + \frac{5t^{10}b^{10}}{(b-1)^3} + \frac{14t^{13}b^{13}}{(b-1)^4} + \dots
\end{align}
Substituting into~\eqref{eqn:qx0_pos} and~\eqref{eqn:qdx_nonpos} appropriately, we confirm that none of the $\sigma$ and $\tau$ terms vanish. We thus get four equations of the form
\begin{equation}
0 = \zeta^{(i)} + \zeta^{(i)}_{0,0}Q_{0,0} + \zeta^{(i)}_{0,1}Q_{0,1} + \zeta^{(i)}_{1,0}Q_{1,0} \qquad \text{for } i=1,\dots,4.
\end{equation}
The final question, then, is which combination(s) of these equations, if any, give a solution. That is, for which $i,j,k$ is the determinant
\begin{equation}
D_{i,j,k} = \zeta^{(i)}_{0,0} \zeta^{(j)}_{0,1} \zeta^{(k)}_{1,0} - \zeta^{(i)}_{0,0} \zeta^{(j)}_{1,0} \zeta^{(k)}_{0,1} - \zeta^{(i)}_{0,1} \zeta^{(j)}_{0,0} \zeta^{(k)}_{1,0} + \zeta^{(i)}_{0,1} \zeta^{(j)}_{1,0} \zeta^{(k)}_{0,0} + \zeta^{(i)}_{1,0} \zeta^{(j)}_{0,0} \zeta^{(k)}_{0,1} - \zeta^{(i)}_{1,0} \zeta^{(j)}_{0,1} \zeta^{(k)}_{0,0}
\end{equation}
non-zero? Curiously, we have $D_{1,2,3} = 0$ while
\begin{align}
D_{1,2,4} &= \frac{4t^{14}a^8 b^5 \olc(a-2) (a-b)^2 (a b-1)}{(a+b-2)^2} + O\big(t^{15}\big) \\
D_{1,3,4} &= -t^{12}a^8b^3\olc (a-1) (b-1) (2 b-1) (a-b)^2 + O\big(t^{13}\big) \\
D_{2,3,4} &= -\frac{4 t^{12} a^6 b^5 \olc(a-1)^2 (b-1) (a-b)^2 (a b-1)}{(a+b-2)^2} + O\big(t^{13}\big).
\end{align}
Choosing one of the valid combinations gives algebraic solutions to $Q_{0,0}$, $Q_{0,1}$ and $Q_{1,0}$. By back-substitution into~\eqref{eqn:qx0_pos} we then get the solution to $Q(x,0)$, and then~\eqref{eqn:rk_y0_posx} gives $Q(0,x)$ (and hence $Q(0,y)$). Finally, the original equation~\eqref{eqn:rk_main_func_eqn} yields $Q(x,y)$.
At this point the reader may notice some special cases where things appear to break down, namely $b=2-a$, $a=1$ or $b=1$. When $b=2-a$ the second factor in $P_{x,0}$ loses its $x$ term, and as a result no longer has a power series root (ie.~$\rho_2$ is no longer valid). However, roots $\rho_1$, $\rho_3$ and $\rho_4$ remain valid, and this combination still works.
When $b=1$ the system simplifies dramatically. This is because $\sigma_{1,0} = 0$ when $b=1$, while the other $\sigma$ coefficients do not vanish. It thus suffices to check that substituting $\rho_1$ and $\rho_2$ into~\eqref{eqn:qx0_pos} gives two independent equations at $b=1$, which it does, since
\begin{equation}
D_{1,2} = \zeta^{(1)}_{0,0}\zeta^{(2)}_{0,1} - \zeta^{(1)}_{0,1}\zeta^{(2)}_{0,0} = 2t^7a^6\olc (a-1) (a-2) + O\big(t^8\big).
\end{equation}
Back-substitution again yields the solutions to the other generating functions. Naturally the $a=1$ case is just a reflection of $b=1$.
\section{Kreweras walks}\label{sec:kreweras}
Recall that $S(x,y) = \olx + \oly + xy$ for Kreweras walks, so that the generating function $Q_{0,0}$ is the same for Kreweras and reverse Kreweras, but all other generating functions are different. For Kreweras, the main functional equation~\eqref{eqn:main_func_eqn} is
\begin{multline}\label{eqn:k_main_func_eqn}
xy(1-t(xy+\olx+\oly))Q(x,y) = xy\olc + x\Big(y-y\ola-t\Big)Q(x,0) + y\left(x-x\olb-t\right)Q(0,y) \\
+xy\left(\ola + \olb - \olc - 1\right)Q_{0,0}
\end{multline}
and the symmetry group of the kernel is still~\eqref{symmetries}.
%We know that the generating function of Kreweras Walk ending at the origin is exactly the same as that of reverse Kreweras Walk. Since we can reverse the direction of each step in a configuration of Kreweras Walk then we get Reverse Kreweras Walk. Thus, there is a bijection between them. So we conclude that for Kreweras Walk with interaction, the generating function of walks ending at the origin is algebraic. However, this does not hold for Kreweras Walk ending at an arbitrary point. The simulation result shows that they are not algebraic, or even not D-finite.
%We now give an explanation for this phenomenon by kernel method. We use some recent result of D-algebraic quarter walks, which can be seen as an extension of the result of model 1- 17 in \cite{beaton2018exact}.
Attempting to proceed in the same way as reverse Kreweras immediately leads to trouble. The full-orbit sum does not vanish; instead, the right-hand side is (after clearing denominators and dividing by the kernel)
\begin{equation}\label{eqn:krew_fullorbitsum_rhs}
\frac{1}{K(x,y)}t^3(x-y)(1-x^2y)(1-xy^2)(a-b)\olc\left(ab-(ab - ac - bc + abc)Q_{0,0}\right).
\end{equation}
The left-hand side is very similar to~\eqref{eqn:rk_full_orbit_sum}.
When $a=b$ this cancels and an algebraic solution follows, as found in~\cite{beaton2018exact} (in that paper $a=b=c$, but in fact the value of $c$ has no effect on the solvability). When $a\neq b$, we can still divide by the kernel and compute the constant term with respect to $y$. Since the left-hand side is almost the same as~\eqref{eqn:rk_full_orbit_sum}, that part poses no difficulty, and leads to an expression involving $Q(x,0)$, $Q(0,x)$, $Q^\mathrm{d}_0(\olx)$, $Q^\mathrm{d}_1(\olx)$ and $Q_{0,0}$, with coefficients that are Laurent polynomials in $x$. On the right-hand side~\eqref{eqn:krew_fullorbitsum_rhs}, we can compute a partial fraction expansion of $1/K(x,y)$ similarly to~\eqref{eqn:rk_kernel_partial_frac}, and get something of the form
\begin{equation}\label{eqn:krew_fullorbitsum_y0_rhs}
\left(\kappa+\frac{\lambda}{\sqrt{\Delta'}}\right) + \left(\kappa_{0,0}+\frac{\lambda_{0,0}}{\sqrt{\Delta'}}\right)Q_{0,0}
\end{equation}
where $\Delta'= (1-t\olx)^2-4t^2x$ and the $\kappa$ and $\lambda$ are Laurent polynomials in $x$.
Here, then, our quest for an algebraic solution fails. By factorising $\Delta'$ as we did for $\Delta$ in~\eqref{eqn:rk_Delta_factorisation}, we can remove either the positive or negative powers of $x$ from~\eqref{eqn:krew_fullorbitsum_y0_rhs}. Whichever we choose, however, will make the left-hand side unworkable: either we get infinitely many positive $x$ powers multiplied by $Q^\mathrm{d}_0(\olx)$ and $Q^\mathrm{d}_1(\olx)$, or infinitely many negative powers multiplied by $Q(x,0)$ and $Q(0,x)$. As a result, we are forced to deal with~\eqref{eqn:krew_fullorbitsum_y0_rhs} directly, and taking the positive or negative part with respect to $x$ moves us away from algebraicity and into the realm of D-finite functions.
At this point we have not attempted to push through the solution for Kreweras walks any further. With the further manipulations that would be required, it is likely that not even D-finiteness is preserved. Indeed, we have generated 3000 terms of $Q(1,1)$, $Q(0,1)$ and $Q(1,0)$ for $(a,b,c) = (2,3,6)$, and analysis with the Ore algebra package for Sage~\cite{kauers2015ore} turned up no potential D-finite solution.
However, when $a=1$ or $b=1$, a D-finite solution was found via series analysis. This may be for the same reason that the reverse Kreweras case simplifies considerably when $b=1$: a coefficient in the final set of equations may vanish.
We thus have the following conjectures.\footnote{Note added in revision: We now have reason to believe that \cref{conj:krew_ab_nonDfinite} is incorrect, and that these generating functions are in fact D-finite. A write-up of these results is currently in preparation.}
\begin{conjecture}\label{conj:krew_ab_nonDfinite}
When $a\neq b$ and $a,b\neq1$, the generating functions $Q(1,1)$, $Q(0,1)$ and $Q(1,0)$ for Kreweras walks are not D-finite.
\end{conjecture}
\begin{conjecture}\label{conj:krew_a1orb1_Dfinite}
If $a=1$ or $b=1$ (but not both), the generating functions $Q(1,1)$, $Q(0,1)$ and $Q(1,0)$ for Kreweras walks are D-finite but not algebraic.
\end{conjecture}
Also observe that when $ab - ac - bc + abc = 0$, the $Q_{0,0}$ term disappears in~\eqref{eqn:krew_fullorbitsum_rhs}. Further series analysis leads us to the following conjecture.
\begin{conjecture}\label{conj:krew_abc_curve_dfinite}
If $ab - ac - bc + abc = 0$ then the generating functions $Q(1,1)$, $Q(0,1)$ and $Q(1,0)$ for Kreweras walks are D-finite.
\end{conjecture}
\Cref{conj:krew_ab_nonDfinite} naturally extends to $Q(x,y)$, $Q(0,y)$ and $Q(x,0)$. We offer no suggestion as to whether \cref{conj:krew_a1orb1_Dfinite,conj:krew_abc_curve_dfinite} are also true for $Q(x,y)$, $Q(0,y)$ and $Q(x,0)$.
%%
%%
%%
\section{Final thoughts and other problems}\label{sec:conclusion}
If \cref{conj:krew_ab_nonDfinite} is true then it is surprising for at least two reasons. Firstly, such a big difference between the generating function $Q(1,1)$ for Kreweras and reverse Kreweras is unexpected, since $Q(0,0)$ is \emph{identical} for both of them, for any $(a,b,c)$. Secondly, this is the first instance (that we are aware of) where the generating function $Q(1,1)$ is \emph{more complicated} than the generating function $Q(0,0)$. (There are at least two cases where the reverse is true, namely $\{\text{N},\text{W},\text{SE}\}$ and $\{\text{E},\text{N},\text{NW},\text{W},\text{S},\text{SE}\}$~\cite{mishna2009classifying}.)
A number of questions also arise:
\begin{itemize}
\item Can the algebraicity of $Q(0,0)$ (\cref{cor:Krew_q00_alg}) be established from~\eqref{eqn:k_main_func_eqn} directly, without using reverse Kreweras walks?
\item Can \cref{conj:krew_a1orb1_Dfinite,conj:krew_abc_curve_dfinite} be proved using the same method as reverse Kreweras? Does the $ab - ac - bc + abc$ factor have an analogue for any other models?
%\item Is the factor $(ab - ac - bc + abc)$ in~\eqref{eqn:krew_fullorbitsum_rhs} significant? Does cancelling this factor make anything simpler?
\item The ``double Kreweras'' model $\{\text{E},\text{NE},\text{N},\text{W},\text{SW},\text{S}\}$ has the same group as Kreweras and reverse Kreweras, and the unweighted case is also algebraic. What can be done to solve this model?
\item Are there any other cases where $Q(1,1)$ is more complicated than $Q(0,0)$?
\end{itemize}
%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\begingroup\emergencystretch=1em
\renewcommand*{\bibfont}{\small}
\printbibliography
\endgroup
\end{document}