%% 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}{Lemma}
\newtheorem {pr}[thm]{Proposition}
\theoremstyle{remark}
\newtheorem {eg}[thm]{Example}
\newcommand{\edit}[1]{\textcolor{red}{EDIT: \texttt{#1}}} 
\newcommand{\TG}[1]{\textcolor{blue} {#1}}
\newcommand{\MW}[1]{\textcolor{red} {#1}}
\usepackage{cleveref}
%\usepackage{lipsum}
\usepackage{bm}

\bmdefine{\ww}{w}
\bmdefine{\xx}{x}
\bmdefine{\yy}{y}
\bmdefine{\zz}{z}
\bmdefine{\rr}{r}
\def\one{\mathbf{1}} % all ones
\def\zero{\mathbf{0}} % all zeros

%% define your title in the usual way
\title[Multivariate Algebraic Asymptotics]{Asymptotics of Coefficients of Algebraic Series Via Embedding Into Rational Series (Extended Abstract)}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%\author[Optional shorter names]{Longer names me\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1}, \and you\addressmark{2}}
\author[T.~Greenwood, S.~Melczer, T.~Ruza, and M.~C.~Wilson]{Torin Greenwood\thanks{\href{mailto:torin.greenwood@ndsu.edu}{torin.greenwood@ndsu.edu}}\addressmark{1}, Stephen Melczer\addressmark{2}, Tiadora Ruza\addressmark{2}, \\ \and Mark C. Wilson\thanks{\href{mailto:markwilson@umass.edu}{markwilson@umass.edu}}\addressmark{3}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, North Dakota State University \\ \addressmark{2}Department of Combinatorics and Optimization, University of Waterloo \\
\addressmark{3}Department of Mathematics \& Statistics, University of Massachusetts Amherst }

%% 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 present a strategy for computing asymptotics of coefficients of $d$-variate algebraic generating functions. Using known constructions, we embed the coefficient array into an array represented by a rational generating functions in $d+1$ variables, and then apply ACSV theory to analyse the latter. This method allows us to give systematic results in the multivariate case, seems more promising than trying to derive analogs of the rational ACSV theory for algebraic GFs, and gives the prospect of further improvements as embedding methods are studied in more detail.}

\resumetitle{R\'{e}sum\'{e}}
%% put your French abstract here, or comment this out if you don't have one
\resume{Nous présentons une stratégie pour la computation des asymptotiques des coefficients de $d$-variable fonctions génératrices algébriques. En utilisant des constructions connues, nous imbriquons le tableau des coefficients dans un tableau qui est représenté par une fonction génératrice rationnelle en $d+1$ variables et puis nous appliquons la théorie ACSV pour analyser ce dernier. Cette méthode nous permettons de donner des résultats systématiques dans le cas multivarié, semble plus prometteuse qu’essayant de dériver un équivalent à la théorie ACSV rationnelle pour les fonctions génératrices algébriques et elle donne la perspective aux améliorations futurs à mesure que les méthodes d’imbrications sont étudiées en plus détailles.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{generating function, ACSV, analytic combinatorics in several variables}

%% 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
\usepackage[backend=bibtex]{biblatex}
%\DeclareFieldFormat[article,periodical]{number}{}
%\renewbibmacro{in:}{%
%  \ifentrytype{article}{}{%
%  \printtext{\bibstring{in}\intitlepunct}}}
%\DeclareFieldFormat[article,incollection]{pages}{#1}%
%\AtEveryBibitem{%
%  \clearfield{note}%
%}

\addbibresource{mvgf.bib}


\begin{document}

\maketitle

\section{Introduction}
\label{s:intro}

Algebraic generating functions (GFs) occur throughout combinatorics and its applications. Combinatorial situations that frequently lead to algebraic GFs include: recursive structures described by context-free languages, such as binary trees and constrained (random) walks; RNA secondary structures; applications of the kernel method, the quadratic method for maps, and generalizations. %\cite{BoJe2006}. 
Our catalog of test problems \cite{GrMW2021} lists 20 algebraic GFs occurring in the recent research literature, 19 of which are multivariate.

A classic univariate example is the Catalan GF
$$
\frac{1 - \sqrt{1 - 4x}}{2x} = \sum_{n\geq 0} a_n x^n
$$
where $a_n$ can be interpreted as the number of  noncrossing partitions of $\{1, \dots, n\}$, binary trees with $n$ nodes, rooted ordered trees with $n$ edges, Dyck paths of semilength $n$, \textit{etc.} Asymptotics of coefficients of univariate algebraic GFs, such as this one, can be derived systematically via the local  \emph{singularity analysis} of Flajolet and Odlyzko \cite{FlOd1990} combined with a global analysis of singularities of the GF \cite{FlSe2009, Chab2002}.
Thus the Catalan GF is easily shown to have $n$th coefficient asymptotic to $4^{n}/\sqrt{\pi n^3}$, which in this simple case can be verified  using the explicit formula $a_n = (2n)!/((n+1)!n!)$ and Stirling's approximation.

However, in more than one variable, there is no such general procedure, and there are many situations where we genuinely want asymptotic information about specific coefficients of multivariate GFs. For example, a Schr\"{o}der tree is a rooted plane tree on $n$ leaves where each non-leaf vertex has at least two children.  The GF encoding the number $a_{m, n}$ of Schr\"{o}der trees with $m$ leaves and $n$ vertices satisfies the algebraic equation
$$V(x, y) := \sum_{m, n = 0}^\infty a_{m, n} x^my^n = xy + \frac{y(V(x,y))^2}{1- V (x, y)}.$$
For large {$m$ and $n$}, approximately how many trees with {$m$ leaves and $n$ vertices} are there? 

The most obvious method of attack on such a problem is to try to mimic the custom contour of integration used by Flajolet and Odlyzko. Apart from the PhD thesis work of Greenwood~\cite{Gree2018}, little has been done in this direction. For the results of that substantial work to apply, an explicit formula for the GF in the form $H^{-\beta}$ is required for some $\beta \not\in \mathbb{Z}_{< 0}$.  The dominant singularity of $1/H$ must be a smooth minimal critical point, $H$ must be analytic near the origin, and $H$ must satisfy some partial derivative constraints at the critical point. Creating a general method from this seems rather daunting.  {The full version of this paper will include examples where this method will not apply.}

Multivariate asymptotics are considerably more difficult to derive than in the univariate case, owing to the much greater range of geometries for the singular set of the GF. Even rational functions prove highly nontrivial, in sharp contrast to their algorithmic analysis in the univariate case. Previous work by Bender, Richmond and Gao \cite{BeRi1983, GaRi1992} deals with limit laws for multivariate situations including algebraic GFs, but does not address the detailed asymptotic questions we need here (corresponding in their model to estimating the probability generating function).
However, the long-running ACSV program \cite{PeWi2013} 
%started by Pemantle and Wilson
has by now made rational multivariate GFs quite manageable in many cases. Our main approach here is to 
% \MW{use known results to}
embed the array of coefficients of an algebraic GF into a higher-dimensional array represented by a rational function, and then use the existing ACSV theory to derive asymptotics. This idea was suggested in  \cite{RaWi2012a} but has barely been explored since then. 
% \MW{As usual in mathematics, the law of conservation of difficulty applies, and this method is far from being a panacea.  However, it works surprisingly well in many cases.}
%
Here we make progress toward a systematic method, by classifying all examples in our recently collated test problem collection \cite{GrMW2021}, and presenting complete results in \cref{s:examples} for some of them. Complete details are in the accompanying \SageMath~worksheet, \url{http://acsvproject.com/AlgSage.ipynb}. {To compute asymptotics for the GF $f(\mathbf{x})$:
\begin{enumerate}
    \item {\bf Preprocess.}  Adding finitely many terms to $f$ or making a variable substitution may help attain necessary embedding conditions, and may lead to nicer \emph{combinatorial} embeddings, where all coefficients are non-negative.  (See \cref{ss:preprocess}.)
    % modifying $f(\mathbf{x})$ by changing a finite number of leading terms or making a variable substitution can lead to an embedding that is easier to analyze.  Preprocessing can help find \emph{combinatorial} embeddings, where all coefficients in the embedding are non-negative.  (See \cref{ss:preprocess}.)
    \item {\bf Embed.} Using \cref{pr:saf1}, encode the coefficients of $f(\mathbf{x})$ as the elementary diagonal of a rational function $F(Y, \mathbf{x})$ in one additional variable.  This step requires that $f$ is divisible by some variable occurring in $f$ and that the minimal polynomial for $f$ has a non-zero derivative at the origin.  (See \cref{ss:embed}.)
    % \item {\bf Apply ACSV.}
    % \begin{enumerate}
        \item {\bf Identify critical points.} If $F(Y, \mathbf{x}) = G(Y, \mathbf{x})/H(Y, \mathbf{x})$, use a system of polynomial equations derived from $H$ to identify critical points that may contribute to the asymptotics.  Because of space, we restrict to the case where we can find an embedding where $1/H(Y, \mathbf{x})$ is combinatorial, allowing us to identify minimal critical points more easily.
        % verify more easily when critical points are minimal.  
        We leave more advanced ACSV issues, such as noncombinatorial embeddings and critical points at infinity, to follow-up work. (See \cref{ss:ACSV}.)
        \item {\bf Compute asymptotics.} Once the contributing critical points are identified, asymptotics may be computed algorithmically.  (See our \SageMath~worksheet.)
    % \end{enumerate}
\end{enumerate}

}



\section{Basic theory}
\label{s:theory}

Let $F(\xx) = \sum_{\rr} a_\rr \xx^\rr$ be a GF in $d$ variables that is algebraic with minimal polynomial $P(Y, \xx)$. 
%Thus 
%$$
%P(F(\xx), \xx) = 0.
%$$
For the Catalan example above, $P(Y,x) = xY^2 - Y + 1$.%
% , \MW{and for the Schr\"{o}der tree example, $P(Y, x, y) = (y + 1)Y^2 - (xy + 1)Y + xy$}
% {The Narayana numbers in Example 4 below are a refinement of the Catalan numbers, with $P(Y,x,y) = xY^2 - Y(1-x(y-1)) + 1$. As expected, this specializes to the Catalan case on setting $y=1$.}


\subsection{Embedding using rational GFs}
\label{ss:embed}

%The entire method would be of no use if we could not embed using rational functions. Fortunately, there is a commonly occurring special case. 
% \MW{It has long been known that the diagonal $\Delta F(t): = \sum_{n} a_{nn} t^n$ of a bivariate rational GF $F(x,y) = \sum_{r,s} a_{rs} x^r y^s$ is always algebraic \cite{Stan1999}. There is a less well known inverse to the diagonal mapping.} 

\begin{pr}[\cite{Furs1967}]
\label{pr:furst}
Suppose that $f$ is a univariate algebraic power series defined by the polynomial $P(Y,x)$, that $f(0) = 0$, and that $\partial P/\partial Y(0,0) \neq 0$. Then $f$ is the diagonal $\Delta F$ of 
the power series 
$$
F(Y, x):= \frac{Y^2P_Y(Y,Yx)}{P(Y, Yx)}.
$$
\end{pr}
The condition that {$f(0) = 0$} is necessary for the formula, since the constant term of 
$Y^2P_Y(Y,Yx)$ is zero. Also, $\partial P/\partial Y(0,0) \neq 0$ is necessary: it says  that the algebraic function defined by $P$ has a single branch of multiplicity $1$ that passes through the origin. 

\begin{eg}
\label{eg:catalan}
The Catalan GF has nonzero constant term, so there are two obvious ways to apply \cref{pr:furst}. Subtracting the constant term yields the embedding into 
$$
F_1(Y,x) = \frac{Y\left(1 - 2Y^2x - 2Yx\right)}{1 - (Y^2x + 2Yx + x)}.
$$
We could instead multiply by $x$ to obtain the shifted Catalan GF whose $n$th coefficient is $a_{n-1}$. This yields an embedding into
$$
F_2(Y,x) = \frac{Y(1-2Y)}{1-Y-x}.
$$
In other words, $a_n$ is the $(n,n)$ coefficient of $F_1$ and the $(n+1,n+1)$ coefficient of $F_2$.
\end{eg}

There is a substantial lack of uniqueness in the embedding, since adding any bivariate rational GF with zero diagonal will not change the diagonal.  

\Cref{pr:furst} in fact generalizes to a less well known result in an arbitrary number of variables, which also allows for a single branch of higher multiplicity. When $d\geq 3$ there are various notions of diagonal. {The \emph{elementary diagonal} of a GF $F(\mathbf{x})$ is the $(d-1)$-variate GF encoding the coefficients from $F$, where $x_1$ and $x_2$ have matching powers, $\sum_{\mathbf{r}} a_{r_2, r_2, r_3, \ldots, r_{d}} x_2^{r_2} x_3^{r_3} \cdots x_{d}^{r_{d}}$.}
% Note: this is defined in Pemantle and Wilson, Definition 2.4.9 on page 41:
% https://www2.math.upenn.edu/~pemantle/papers/ACSV.pdf
% I did not go with the phrasing there because it seemed more general than what we need.
% The \emph{elementary diagonal} of $F$ is the univariate GF $\sum_{n\geq 0} a_{n,n,\dots, n}t^n$.

\begin{pr}[\cite{Safo2000}, Lemma {2}]
\label{pr:saf1}
Suppose that $f$ is an algebraic power series given as a branch of
$P(f(\xx), \xx) = 0$, that $f$ is divisible by $x_1$ and that in some neighborhood of $\zero$, there is a factorization $P(Y, \xx) = (Y - f(\xx))^k u(Y, \xx)$ where $u(0,\zero) \neq 0$ and $k \geq 1$ is an integer.

Then $f$ is the elementary diagonal of the rational function $F$ given by
$$
F(Y, \xx) = 
\frac{Y^2 P_Y(Y,Yx_1, x_2, \dots, x_d)}{k P(Y,Yx_1, x_2, \dots, x_d)}.
$$
%where by $P_1$ we mean the partial derivative of $P$ with respect
%to the variable $Y$.
\end{pr}

\begin{eg}
\label{eg:narayana}
A bivariate refinement of the Catalan GF is the Narayana GF
$$
G(x,y):= \frac{1}{2x}{\left( 1 - x(y-1)
   - \sqrt{1 - 2x(y + 1) + x^2(y -1)^2} \right)},
$$
which enumerates noncrossing partitions by set size and number of blocks, rooted ordered trees by edges and leaves, Dyck paths by semilength and number of peaks, \textit{etc.} The minimal polynomial $P(Y,x,y) = xY^2 - Y(1-x(y-1)) + 1$ specializes to the Catalan case on setting $y=1$.

Now $G(x,y) - 1$ satisfies the hypotheses of \cref{pr:saf1} with $k=1$ (with respect to the variable $x$), and hence embeds into
$$
\frac{\left(1 - (2Y^2x + Yxy + Yx)\right)Y}{\left(1 - \left(Y^2x + Yxy + Yx + xy\right)\right)}.
$$
As expected, if we set $y = 1$, this GF specializes to $F_1$ in \cref{eg:catalan}. Similarly, if we instead multiply by $x$ before embedding, we obtain
$$
 \frac{Y \left(1 - 2Y - Yx(y-1)\right)}{1 - x - Y - Y x(y-1)},
$$
which specializes to $F_2$ in \cref{eg:catalan}.
\end{eg}

More generally, we must separate the branches of the algebraic function, which requires more work, undertaken for example in \cite{Safo2000}. We intend to consider this case in a companion paper. For now, we concentrate only on cases where the hypotheses of \cref{pr:saf1} are met, which turns out to be almost all of the examples in \cite{GrMW2021}. 
%We now move on describe the basic results needed to derive asymptotics after the embedding into rational GF has been completed.

\subsection{Basics of ACSV}
\label{ss:ACSV}
We give a very brief overview of this (by now standard) material, and refer to~\cite{Melc2021,PeWi2013} for full details.
Given a rational $d$-variate GF in the form $F = G/H$ with a power series expansion at the origin, we may often derive asymptotics as follows. First represent the coefficient of $\xx^\rr := x_1^{r_1} \cdots x_d^{r_d}$ via the Cauchy Integral Formula with domain of integration a small torus (product of circles) centered at the origin. We then expand this torus via a homothety until we reach a \emph{minimal critical point} (a type of point with algorithmically checkable properties) lying on the boundary of the domain of convergence. Replacing by a local residue integral we may evaluate this using stationary phase methods. In the case where the minimal critical point {$\mathbf{w}$} is a smooth point of the variety $H = 0$,  this leads directly to an asymptotic expansion {for $\mathbf{r} = n \cdot \widehat{\mathbf{r}}$ with $\widehat{\mathbf{r}} \in (0, \infty)^d$ fixed as $n \to \infty$}
$$
{\left[\mathbf{x}^{\mathbf{r}}\right] F(\mathbf{x}) \sim \mathbf{w}^{-\mathbf{r}}} \sum_{k\geq 0} a_k |\rr|^{(1-d)/2-k},
$$
where the coefficients can be determined algorithmically in terms of derivatives of $G$ and $H$, {and $\mathbf{w}$ and $a_k$ vary with $\widehat{\mathbf{r}}$}. The simplest explicit formula in terms of $G$ and $H$ is only for $k = 0$, but the rational GFs we obtain via the embedding procedures above always have $a_0 = 0$ \cite{RaWi2012b}. Computer algebra implementations computing coefficients $a_k$ are built into \SageMath~\cite{Raic}.

Another key observation is that if $1/H$ is \emph{combinatorial} (all its coefficients are nonnegative), then minimal singularities exist and for each minimal critical point $\ww$, the point $(|w_1|, \dots |w_d|)$ is also a minimal critical point. If the series is \emph{aperiodic} (the {subgroup} generated by the support is all of $\mathbb{Z}^d$) then there is a unique minimal critical point. In particular, if $H = 1 - K$ where $K$ is an aperiodic polynomial with nonnegative coefficients, which is the case in many of our examples below, for each direction there is a unique minimal critical point supplying asymptotics in that direction, and it is strictly minimal and lies in the positive orthant.

In the general noncombinatorial case, it can be hard to determine the contributing points.  Minimal points are still desirable because the contour shifting implicit in the above description is still guaranteed to work in the noncombinatorial case. Yet, minimal points need not exist, and algorithmically determining them is considerably harder. Much recent work has been done, using Morse theory, to deal with this case. In this article we discuss only {examples that can be manipulated until a combinatorial embedding is found}, leaving the asymptotic analysis for {noncombinatorial cases for} a future article.

\section{Worked examples}
\label{s:examples}
We categorize the examples in \cite{GrMW2021} according to the type of embedding obtained. We present a single illustrative example in each category in full detail, and give less detail in other cases. Full computations are given in the accompanying \SageMath~worksheet. 

\subsection{Notes on preprocessing}
\label{ss:preprocess}

Assuming that we have an algebraic power series $f$, there are two main hypotheses needed before we can embed using  \cref{pr:saf1}. They are: (H1) $f$ is divisible by some variable occurring in $f$ and (H2) $\partial P/\partial Y$ does not vanish at the origin.

If $f$ does not vanish at the origin, then H1 cannot apply. In the univariate case, we can remedy this by subtracting the constant term or multiplying by the variable, as we showed above for the Catalan example.  More generally, for the first approach we can subtract initial terms of the power series expansion of $f$. The following result gives a simple necessary condition for this to work.  {Let $\xx_j^\circ = (x_1, \ldots, x_{j - 1}, 0, x_{j + 1}, \ldots, x_d)$.}  


\begin{pr}
\label{pr:necessary}
{If $f - f_0$ satisfies H1 with respect to the variable {$x_j$}, for some polynomial $f_0$, then {$f(\xx_j^\circ)$} is a polynomial.}
\end{pr}
\begin{proof}
If we substitute {$x_j=0$}, then we need {$f(\xx_j^\circ) - f_0(\xx_j^\circ)$} to be identically zero.
\end{proof}

Note that if we already satisfy H1 but still apply such an \emph{additive substitution}, then the truth value of H2 will not change. To see this, write $\widetilde{f} = f - f_0$ and denote its minimal polynomial by $\widetilde{P}$. Then $\partial \widetilde{P}/\partial Y$ evaluated at the origin is equal to $\partial P/\partial Y$ evaluated at $\xx = 0, Y = f_0(\zero) = 0$. Thus in this case such a substitution is unnecessary if our goal is simply to embed. However as we see in \cref{eg:schroeder}, the nature of the rational function that we embed into may change, and this may be useful.

In all dimensions, the second method of \emph{multiplicative substitution} results in something satisfying H1. The Catalan example shows that we may also satisfy H2. However the situation seems quite tricky: 
%if we look at ternary trees instead of binary trees, we obtain 
the ternary tree analog of the shifted Catalan GF is defined by $Y^3 - xY + x^2 = 0$, and this does not satisfy H2. We do not pursue this approach further in the present article, for space reasons and because it seems less promising.

There is a third trick we can use. Assuming we already have $f(\zero) = 0$ but H1 is not satisfied, we can make a \emph{monomial substitution}. For example, in two variables we may have $(x,z) \mapsto (x,xz)$. This ensures that every term is now divisible by $x$, so H1 holds for the transformed GF $\widetilde{f}(x,z) = f(x,xz)$. Furthermore there is no change in the truth value of H2, since the minimal polynomial of $\widetilde{f}$ is $P(Y, x, xz)$ and this does not change the value of $\partial P /\partial Y$ evaluated at the origin. We do need to keep more careful track of the relation between the indices
in the original power series and the rational function.


%\subsection{Embedding is combinatorial after multiplying by a variable}

%The Catalan GF is one such example. Note that the Naryana example is not. \edit{whatever  to say about our standard examples?}

\subsection{Embedding is combinatorial after additive substitution}
\label{ss:additive}

In 6 of our 20 catalogued examples, we can immediately embed into a combinatorial GF once we remove the constant term, and in 4 examples a similar approach with more terms works. In addition to the examples shown below, the catalog examples \#8 (Eu; refinement of noncrossing partitions), \#9 (Do\v{s}lic \textit{et al.}; RNA secondary structures), \#13 (Flajolet and Sedgewick; patterns in trees), \#14 (the Narayana numbers), \#16 (new and old leaves), and \#19 (Bousquet-M\'{e}lou and Rechnitzer; bar graphs)  lie in this category. 

\subsubsection{A univariate algebraic family \cite[Example 4]{GrMW2021}}
\label{eg:callan}

% \edit{TG: I suggest not doing this one in full detail} 
As a warm-up we deal with a univariate problem.
In \cite{Call2007}, Callan studied the family
\[
G(x): = G_{a,b}(x) = \frac{1 - ax - \sqrt{1-2ax + (a^2 - 4b)x^2}}{2bx^2},
\]
for constants $a$ and $b$.  %This family includes functions for the Catalan numbers, Motzkin numbers, and little and big Schr\"{o}der numbers.  
Let $f(x) = G(x) - 1$, and observe that $f$ satisfies the minimal polynomial 
% \edit{tidy and collect}
\[
% P(x, Y) = Y^2x^2b + 2Yx^2b + Yxa + x^2b + xa - Y.
P({Y, x}) = x^2b Y^2 + (2bx^2 + ax - 1)Y + (x^2b + ax) .
\]
Since $P_Y(0, 0) \neq 0$, we can use \cref{pr:saf1} to embed $f$ in the GF
\[
F({Y, x}) = \frac{Y^2 P_Y({Y, xY})}{P({Y, xY})}
= \frac{{\left(1 - \left(2 \, Y^{3} b x^{2} + 2 \, Y^{2} b x^{2} + Y a x\right)\right)} Y}{1 - \left(Y^{3} b x^{2} + 2 \, Y^{2} b x^{2} + Y b x^{2} + Y a x + a x\right)}.
\]
We look at the coefficients of $F$ in the direction $\rr = [1, 1]$ since $[x^n] f(x) = [{Y^nx^n}] F({Y, x})$.  Let $H({Y, x})$ be the denominator of $F({Y, x})$.  Then, critical points satisfy the system of equations
$\left\{H = 0,\ \ xH_x - YH_Y = 0\right\}$.
When $b \neq a^2, a^2/4$, this system yields two points:
% \begin{align*}
\[
{(Y_1, x_1)} = \!\left(\frac{-\sqrt{b}}{(a - \sqrt{b})(a - 2\sqrt{b})}, -\frac{a \sqrt{b} - b}{b}\right)\hspace{-3pt},
{(Y_2, x_2)} = \!\left(\frac{\sqrt{b}}{(a + \sqrt{b})(a + 2\sqrt{b})}, \frac{a \sqrt{b} + b}{b}\right)\hspace{-3pt}.
\]
% \end{align*}

All critical points are smooth because the system of equations $\{H = 0,\ \ xH_x - YH_Y = 0, H_x = 0\}$ has no solutions.  
%When $b \neq 0, \sqrt{a}$, the critical point $(x_2, y_2)$ is strictly closer coordinate-wise to $(0, 0)$, and thus it is the only critical point that potentially contributes to asymptotics.
The coordinates of {$(Y_2, x_2)$} are always positive for any choice of $a, b > 0$, and this point is strictly minimal.
%Between this and the fact that $H$ is of the form $1 - v(x, y)$ for a polynomial $v$ with only positive coefficients, it is clear that $(x_2, y_2)$ must be a \emph{minimal} critical point, meaning that there is no point $(p, q)$ where $H(p, q) = 0$ and $|p| < x_2, |q| < y_2$.
%
%Moreover, $(x_2, y_2)$ must be \emph{strictly minimal}, meaning additionally that there is no point $(p, q) \neq (x_2, y_2)$ where $H(p, q) = 0$ and $|p| = x_2, |q| = y_2$.  In this case, strict minimality is easy to check: because $H = 1 - v(x, y)$ for a polynomial $v$ with only positive coordinates and because $(x_2, y_2)$ is minimal, the only way that $H(p, q) = 0$ would be if every term of $v(p, q)$ was positive.  Since $v(x, y)$ has the term $xa$ in it, this implies that $p > 0$.  Since it also has the term $yxa$, this implies that $q > 0$ too.  This means that $(p, q) = (x_2, y_2)$, proving that $(x_2, y_2)$ is strictly minimal.
%
We now use, for example, \cite[Theorem~5.2]{Melc2021} to find an asymptotic expansion for the coefficients of $F({Y, x})$.  %The Sage code accompanying Melcer's texbook \cite{Melc2021} automates this computation.
% Note that to drastically improve runtime in Sage by reducing the number of square roots involved in computations, we can temporarily make the substitution $a \to A^2, b \to B^2$.
We end up with 
\begin{equation} \label{eq:Example1-4-Asymptotics}
    [{Y^nx^n}] F({Y, x}) = \frac{b^{-3/4}}{2\sqrt{\pi}} n^{-3/2} (a + 2\sqrt{b})^{n + 3/2} + O(n^{-5/2}).
\end{equation}
Note that when $b = a^2$ or $b = a^2/4$, the non-dominant critical point is no longer relevant, but a similar analysis yields the same asymptotic formula.

We compare this to the asymptotic expansions derived using \cite[Corollary 2]{FlOd1990}.  The original GF $G(x)$ has a unique algebraic singularity at $x = \frac{1}{a + 2\sqrt{b}}$ for $a, b > 0$.  Additionally, if $\alpha_1 = \frac{1}{a + 2\sqrt{b}}$ and $\alpha_2 = \frac{1}{a - 2\sqrt{b}}$, then as $x \to \alpha_1$,
\[
\sqrt{1-2ax + (a^2 - 4b)x^2} \sim \sqrt{\alpha_1} \left(1 - \frac{x}{\alpha_1}\right)^{1/2} \sqrt{(\alpha_2 - \alpha_1)(a^2 - 4b)}.
\]
This implies that as $n \to \infty$
\[
[x^n] \sqrt{1-2ax + (a^2 - 4b)x^2} = -\frac{b^{1/4}}{\sqrt{\pi}}n^{-3/2} (a + 2\sqrt{b})^{n - 1/2} + O(n^{-5/2}).
\]
Plugging this expansion into the equation for $G(x)$ gives a matching asymptotic expression to Equation \eqref{eq:Example1-4-Asymptotics}.

% Keeping original version in case I mess something up:
% \subsubsection{A univariate algebraic family \cite[Example 4]{GrMW2021}} 
% \label{eg:callan}

% \edit{TG: I suggest not doing this one in full detail} 

% In \cite{Call2007}, Callan studied the family of generating functions,
% \[
% G(x) = \frac{1 - ax - \sqrt{1-2ax + (a^2 - 4b)x^2}}{2bx^2},
% \]
% for constants $a$ and $b$.  This family includes generating functions for the Catalan numbers, Motzkin numbers, and little and big Schr\"{o}der numbers.

% To apply  \cref{pr:furst}, we notice that if we subtract the constant term from the Taylor expansion of $G(x)$, then the variable $x$ divides each term.  With this in mind, let $f(x) = G(x) - 1$, and observe that $f$ satisfies the minimal polynomial \edit{tidy and collect}
% \[
% P(x, y) = y^2x^2b + 2yx^2b + yxa + x^2b + xa - y.
% \]
% Since $P_y(0, 0) \neq 0$, we can embed $f$ in the generating function,
% \[
% F(x, y) = \frac{y^2 P_y(xy, y)}{P(xy, y)}
% = \frac{{\left(1 - \left(2 \, y^{3} b x^{2} + 2 \, y^{2} b x^{2} + y a x\right)\right)} y}{1 - \left(y^{3} b x^{2} + 2 \, y^{2} b x^{2} + y b x^{2} + y a x + a x\right)}.
% \]
% This means that the coefficients of $f$ and $F$ are related by $[x^n] f(x) = [x^ny^n] F(x, y)$.  Thus, to find asymptotics for the coefficients of $f$, we look at the coefficients of $F$ in the direction $\rr = [1, 1]$.  Let $H(x, y)$ be the denominator of $F(x, y)$.  Searching for the critical points in this direction yields the system of equations
% $\left\{H = 0,\ \ xH_x - yH_y = 0\right\}$.
% When $b \neq a^2, a^2/4$, this system yields two points:
% % \begin{align*}
% % (x_1, y_1) &= \left(-\frac{3 \, a b + {\left(a^{2} + 2 \, b\right)} \sqrt{b}}{a^{4} - 5 \, a^{2} b + 4 \, b^{2}}, -\frac{a \sqrt{b} - b}{b}\right)\\
% % (x_2, y_2) &= \left(-\frac{3 \, a b - {\left(a^{2} + 2 \, b\right)} \sqrt{b}}{a^{4} - 5 \, a^{2} b + 4 \, b^{2}}, \frac{a \sqrt{b} + b}{b}\right)
% % \end{align*}

% \begin{align*}
% (x_1, y_1) &= \left(\frac{-\sqrt{b}}{(a - \sqrt{b})(a - 2\sqrt{b})}, -\frac{a \sqrt{b} - b}{b}\right)\\
% (x_2, y_2) &= \left(\frac{\sqrt{b}}{(a + \sqrt{b})(a + 2\sqrt{b})}, \frac{a \sqrt{b} + b}{b}\right)
% \end{align*}

% All critical points are smooth because the system of equations $\{H = 0,\ \ xH_x - yH_y = 0, H_x = 0\}$ has no solutions.  
% %When $b \neq 0, \sqrt{a}$, the critical point $(x_2, y_2)$ is strictly closer coordinate-wise to $(0, 0)$, and thus it is the only critical point that potentially contributes to asymptotics.
% The coordinates of $(x_2, y_2)$ are always positive for any choice of $a, b > 0$, and this point is strictly minimal.
% %Between this and the fact that $H$ is of the form $1 - v(x, y)$ for a polynomial $v$ with only positive coefficients, it is clear that $(x_2, y_2)$ must be a \emph{minimal} critical point, meaning that there is no point $(p, q)$ where $H(p, q) = 0$ and $|p| < x_2, |q| < y_2$.

% %Moreover, $(x_2, y_2)$ must be \emph{strictly minimal}, meaning additionally that there is no point $(p, q) \neq (x_2, y_2)$ where $H(p, q) = 0$ and $|p| = x_2, |q| = y_2$.  In this case, strict minimality is easy to check: because $H = 1 - v(x, y)$ for a polynomial $v$ with only positive coordinates and because $(x_2, y_2)$ is minimal, the only way that $H(p, q) = 0$ would be if every term of $v(p, q)$ was positive.  Since $v(x, y)$ has the term $xa$ in it, this implies that $p > 0$.  Since it also has the term $yxa$, this implies that $q > 0$ too.  This means that $(p, q) = (x_2, y_2)$, proving that $(x_2, y_2)$ is strictly minimal.

% We now use \cite[ Theorem 9.2.7]{PeWi2013} to find an asymptotic expansion for the coefficients of $F(x, y)$.  Additionally, this computation is automated in the Sage code accompanying Melczer's textbook \cite{Melc2021}.
% % Note that to drastically improve runtime in Sage by reducing the number of square roots involved in computations, we can temporarily make the substitution $a \to A^2, b \to B^2$.
% We end up with the expression,
% \begin{equation} \label{eq:Example1-4-Asymptotics}
%     [x^ny^n] F(x, y) = \frac{(a + 2\sqrt{b})^n}{\sqrt{n}} \cdot \left(\frac{(a + 2\sqrt{b})^{3/2}}{2\sqrt{\pi}b^{3/4}n} + O\left(\frac{1}{n^2}\right)\right).
% \end{equation}

% We can compare this to the asymptotic expansions from Corollary 2 of \cite{FlOd1990}.  Here, the original generating function $G(x)$ has a unique algebraic singularity at $x = \frac{1}{a + 2\sqrt{b}}$ for $a, b > 0$.  Additionally, if $\alpha_1 = \frac{1}{a + 2\sqrt{b}}$ and $\alpha_2 = \frac{1}{a - 2\sqrt{b}}$, then as $x \to \alpha_1$,
% \[
% \sqrt{1-2ax + (a^2 - 4b)x^2} \sim \sqrt{\alpha_1} \left(1 - \frac{x}{\alpha_1}\right)^{1/2} \sqrt{(\alpha_2 - \alpha_1)(a^2 - 4b)}.
% \]
% This implies that as $n \to \infty$,
% \[
% [x^n] \sqrt{1-2ax + (a^2 - 4b)x^2} = -\frac{b^{1/4}}{\sqrt{\pi}}n^{-3/2} (a + 2\sqrt{b})^{n - 1/2} + O(n^{-5/2}).
% \]
% Hence, by plugging this expansion into the equation for $G(x)$, we get a matching asymptotic expression to \eqref{eq:Example1-4-Asymptotics},
% \[
% [x^n] G(x) = \frac{b^{-3/4}}{2\sqrt{\pi}} n^{-3/2} (a + 2\sqrt{b})^{n + 3/2} + O(n^{-5/2}).
% \]
% \edit{I can go back to include the cases where $a = \pm 2\sqrt{b}$.}

\subsubsection{Dissections \texorpdfstring{\cite[Example 10]{GrMW2021}}{[14, Example 10]}}
\label{eg:dissections}
% Old Example 1.12
% \MW{A \emph{dissection} is a convex polygon split into fragments with a collection of non-crossing diagonals.}
Drmota \cite[page~376]{Drmo2009} enumerates dissections of polygons (where the polygons have a marked edge) using a bivariate GF $A(x,y)$, where $x$ counts the number of vertices in the polygon, and $y$ counts the total number of edges in the dissection.  %Drmota notes that dissections can also be viewed as $2$-connected outerplanar graphs with a rooted edge on their infinite face, and 
He gives the following minimal polynomial for $A$:
\[
A(x, y) = xy^2(1 + A(x, y))^2 + xy(1 + A(x, y)) \cdot A(x, y).
\]
Since $A$ is divisible by $x$, using \cref{pr:saf1} immediately we embed into 
$$F({Y, x, y}) = \frac{{\left(1 - \left(2 \, Y^{2} x y^{2} + 2 \, Y^{2} x y + 2 \, Y x y^{2} + Y x y\right) \right)} Y}{1 - \left(Y^{2} x y^{2} + Y^{2} x y + 2 \, Y x y^{2} + Y x y + x y^{2}\right)}.
$$
% \MW{Note that attaching $Y$ to $y$ also gives a combinatorial embedding, but where the denominator is of degree $3$ in $Y$.}
We note that $[x^{pn} y^{(1-p)n}]A(x, y) = [{Y^{pn}x^{pn}y^{(1-p)n}}] F({Y, x, y})$, and find that there is a single smooth critical point in this direction:
\[
{(Y, x, y)} = {\left(\frac{1 - 2 \, p}{p}, \frac{p(3p-1)^2}{(1-2p)^3}, \frac{(1-2p)^2}{(3p-1)(1-p)}\right)}.
\]
This critical point has positive coordinates when $1/3 < p < 1/2$.  This corresponds to the range of $p$-values where $A(x, y)$ has positive coefficients%
%\MW{: an $n$-gon can have between $0$ and $n - 2$ diagonals in its dissection, for a total of between $n$ and $2n - 2$ edges}
.   It is clear from the denominator of $F$ that in this case, the critical point is strictly minimal.  
Thus
% we obtain
for $1/3 < p < 1/2$:
\[
[x^{pn} y^{(1-p)n}]A(x, y) = \frac{\sqrt{1-p}}{2\pi p^2 \sqrt{3p - 1}} \cdot \frac{1}{n^2} \cdot \left(\frac{(1-p)^{1-p}}{(1-2p)^{2-4p}(3p-1)^{3p-1}}\right)^n + O\left(\frac{1}{n^3}\right).
\]

\if01
\subsubsection{Non-crossing partitions with $k$ visible blocks}
\label{eg:Eu}
% Old Example 1.8
Let $b_{n, k}$ be the number of circular non-singleton non-crossing partitions of $[n]$ with $k$ visible blocks. Eu presents \cite[Proposition~63, page~107]{Eu2002}:
\[
B(x, u) := \sum_{n, k \geq 0} b_{n, k} u^k x^n = \frac{1 + x - \sqrt{1 - 2x + x^2 - 4x^2u}}{2x(1 + xu)}.
\]
% Note that B(x, u) - 1 vanishes when $x=0$, and satisfies the minimal polynomial
% \[
% P(x, u, Y) = Y^{2} u x^{2} + 2 \, Y u x^{2} + Y^{2} x + u x^{2} + Y x - Y,
% \]
% and can thus be embedded in the trivariate generating function
% \[
% F(x, u, Y) = \frac{{\left(2 \, Y^{3} u x^{2} + 2 \, Y^{2} u x^{2} + 2 \, Y^{2} x + Y x - 1\right)} Y}{Y^{3} u x^{2} + 2 \, Y^{2} u x^{2} + Y u x^{2} + Y^{2} x + Y x - 1}.
% \]
Using \cref{pr:saf1}, $B(x, u) - 1$ can be embedded in a GF $F(x, u, Y)$ where $x$ is attached to $Y$.  We search for asymptotics of $[x^{np} u^{n(1-p)}] B(x, u)$.  For circular representations of partitions, every block is visible.  Thus, for a partition of $[n]$ with no singleton blocks, there are between $1$ and $\lfloor n/2\rfloor$ blocks.  This corresponds to $p \in (2/3, 1)$.
In the $(x, u, Y)$-direction  $\rr = (p, (1-p), p)$, there is a single smooth strictly minimal critical point with positive coordinates that leads to the asymptotic expansion
% 
% \[
% (x, u, Y) = \left(-\frac{6 \, p^{2} - 7 \, p + 2}{p^{2} - p}, \frac{p^{2} - 2 \, p + 1}{9 \, p^{2} - 12 \, p + 4}, -\frac{p - 1}{2 \, p - 1}\right).
% \]
% This leads to the asymptotic expansion
\[
[x^{np}u^{n(1-p)}] B(x, u) = \frac{\sqrt{p}}{2\pi (2p - 1)^2 \sqrt{3p - 2}} \cdot \frac{1}{n^2} \cdot \left(\frac{(p-1)^{2p - 2} p^p}{(3p-2)^{3p-2}} \right)^n + O\left(\frac{1}{n^3}\right).
\]

\fi


\subsubsection{Assembly trees \texorpdfstring{\cite[Example 15]{GrMW2021}}{[14, Example 15]}}
\label{eg:assembly}

% Old Example 1.21
B\'{o}na and Vince
\cite{BoVi2013} define the concept of \emph{assembly
tree} of a graph and show that the (exponential) GF for the number of
assembly trees of the complete bipartite graph $K_{rs}$ is 
% \MW{given by}
$$
f(x,y) = \sum_{rs}a_{rs}x^ry^s = 1 - \sqrt{(1-x)^2 + (1-y)^2 - 1}.
$$
Note that $f(0,y) = y$ and $f(x,0) = x$; indeed, the first order  Maclaurin expansion is $x+y$.
We replace $f$ by $\widetilde{f}:=f - x - y$, which obviously has no effect on asymptotics of coefficients, and we can embed $\widetilde{f}$ via \cref{pr:saf1} into
$$
F({Y, x, y}) = \frac{{\left(1 - \left(Y x + Y + y \right)\right)} Y}{1 - \left(Y x + x y + Y/2 + y\right)}.
$$
Here, we analyse the direction $\rr = [{p, p, (1-p)}]$ for variables $({Y, x, y})$ and $p \in (0, 1)$, and obtain a pair of smooth critical points, only one of which is strictly minimal with positive coordinates.
% \[
% (x, y, Y) = \left( \frac{2p - 1 + \sqrt{\xi}}{4(1-p)}, \frac{3}{2} - p - \frac{1}{2}\sqrt{\xi}, \sqrt{\xi} - 1\right).
% \]
Let $\xi := 1 + 4p - 4p^2$.  This leads to the asymptotic formula
% \begin{multline*}
% [x^{np} y^{n(1-p)}]f(x, y) = \frac{\sqrt{(2 + 4p - 4p^2)\sqrt{\xi} - 2\xi}\left(1 + \xi^{-1/2}\right)}{4\pi p(1-p)} \cdot \frac{1}{n^2} \cdot \\
% \left( \frac{(\sqrt{\xi} - 2p + 3)}{4(1-p)^2} \cdot \left( \frac{1 + (1-2p)\sqrt{\xi}}{4p^2}\right)^p \right)^n + O\left(\frac{1}{n^3}\right).
% \end{multline*}
\[
\frac{\sqrt{(1 + \xi)\sqrt{\xi} - 2\xi}\left(1 + \xi^{-1/2}\right)}{4\pi p(1-p)} \cdot \frac{1}{n^2} \cdot
\left( \frac{(\sqrt{\xi} - 2p + 3)}{4(1-p)^2} \cdot \left( \frac{1 + (1-2p)\sqrt{\xi}}{4p^2}\right)^p \right)^n + O\left(\frac{1}{n^3}\right).
\]


For example, when $p = 1/2$ we are looking at the diagonal case $K_{rr}$, and obtain
\[
[x^ny^n]f(x, y) = \frac{1}{\pi 2^{9/4}} \cdot \frac{1}{n^2} \cdot (6 + 4\sqrt{2})^n + O\left(\frac{1}{n^3}\right).
\]
This agrees with \cite[Theorem~4.11]{BoVi2013} in the exponential rate, but not in the constant --- ours is correct, as we confirmed by numerical checks.

\subsubsection{Schr\"{o}der trees by leaves and vertices \texorpdfstring{\cite[Example 17]{GrMW2021}}{[14, Example 17]}}
\label{eg:schroeder}
Recall this class from the introduction. Using \cref{pr:saf1} on the minimal polynomial for $V$ (with respect to the variable $y$) will yield a noncombinatorial embedding.  Instead, we use the embedding $F({Y, x, y})$ for $V(x, y) - xy$.
% and its corresponding minimal polynomial,
% \[
% P = -{x}^{2}{y}^{3}-2\,Yx{y}^{2}-y{Y}^{2}-Yxy-{Y}^{2}+Y.
% \]
% This yields a combinatorial embedding attaching $x$ to $Y$:
% \[
% F(x, y, Y) = \frac{{\left(2 \, Y x y^{2} + Y x y + 2 \, Y y + 2 \, Y - 1\right)} Y}{Y x^{2} y^{3} + 2 \, Y x y^{2} + Y x y + Y y + Y - 1}.
% \]
Checking in the $({Y, x, y})$ direction $\rr = ({p, p, (1-p)})$ for $p \in (1/3, 1/2)$ (corresponding to non-zero coefficients) yields a single strictly minimal critical point with positive coordinates.
% \[
% (x, y, Y) = \left(\frac{p(3p-1)(1-p)}{(1-2p)^3}, \frac{(1-2p)^2}{3p-1)(1-p)}, \frac{(3p-1)(1-2p)}{p(1-p)}\right).
% \]
Then, we obtain
\[
[x^{np}y^{n(1-p)}]V(x, y) = \frac{\sqrt{3p - 1}}{2\pi p^2\sqrt{1-p}} \cdot \frac{1}{n^2} \cdot \left(\frac{(1-2p)^{4p-2}}{(1-p)^{p-1}(3p-1)^{3p-1}} \right)^n + O\left(\frac{1}{n^3}\right).
\]



\subsection{Embedding is combinatorial after a monomial substitution}
\label{ss:melczer trick}

When the trick of subtracting a polynomial from $f$ does not work, we can move to another level.
In 2 of our 20 examples, a monomial substitution is effective.
\subsubsection{Bivariate generalization of Catalan numbers \texorpdfstring{\cite[Example 7]{GrMW2021}}{[14, Example 7]}}
\label{sss:Cossali}

The next example comes from \cite{Coss2003}. 
Let $$g(n, m) = \frac{(2n + m)!}{m!n!(n + 1)!}.$$  %Fragments of this array encode Catalan numbers, triangular numbers, and other sequences.  The GF is
with corresponding GF 
\[
L(x, z) := \sum_{q = 0}^\infty \sum_{m = 0}^\infty g(m, q)x^m z^q = \frac{(1 - z) - \sqrt{(1 - z)^2 - 4x}}{2x}.
\]

Then $L(0,0) \neq 0$ and \Cref{pr:necessary} rules out simple additive substitutions, since $L(x,0)$ is the Catalan GF and L'H\^{o}pital's rule shows that $L(0,z)$ is also not a polynomial. Instead we change variables by replacing $z$ by $xz$. Then $L(x, xz) - 1$ satisfies
\[
P = Y^{2} x + Y x z + 2 \, Y x + x z - Y + x,
\]
which leads to the embedding
\[
F({Y, x, z}) = \frac{1 - \left(2 Y^{2} x + Y x z + 2 Y x\right) Y}{1 - \left(Y^{2} x + Y x z + 2  Y x + x z + x\right)},
\]
where $[x^nz^k] L(x, z) = [{Y^{n + k}x^{n+k} z^n}] F({Y, x, z})$.  Rescaling so $n+k$ becomes $n$, we consider  $[x^{pn} z^{(1-p)n}] L(x, z)$ for a constant $p \in (0, 1)$  as $n \to \infty$.  This corresponds to analysing $[{Y^n x^n z^{(1-p)n}}]F({Y, x, z})$, giving us the direction $\rr = ({1, 1, (1-p)})$. 
% Let $H(x, z, Y) = Y^{2} x + Y x z + 2 \, Y x + x z + x - 1$ be the denominator of $F$.  Then, the smooth critical point equations are
% \[
% \left\{H = 0,\ \ (1-p)xH_x - zH_z,\ \ xH_x - YH_Y = 0\right\}.
% \]
% Using a Gr\"{o}bner basis, we get the single minimal smooth critical point,
% \[
% (x, z, Y) = \left(\frac{p^{3}}{p^{2} + 2 \, p + 1}, \frac{1 - p^{2}}{p^{2}}, \frac{1}{p}\right)
% \]
% It is again easy to verify that this point is strictly minimal because of the form of $H$.  Thus, we obtain
There is a single smooth strictly minimal critical point with positive coordinates in this direction, yielding
\[
[x^{pn} z^{(1-p)n}] L(x, z) = \frac{\sqrt{1 - p^2}}{2\pi (1-p)p^2} \cdot \frac{1}{n^2} \cdot \left( \frac{1 + p}{1-p} \cdot \frac{(1-p^2)^p}{p^{2p}}\right)^n + O\left(\frac{1}{n^3}\right).
\]


\subsubsection{Bicolored Motzkin Paths \texorpdfstring{\cite[Example 18]{GrMW2021}}{[14, Example 18]}}

In \cite[Lemma 2.1]{Eliz2021}, Elizalde derives the GF for bicolored Motzkin paths.  Here, such a path starts and ends at the $x$-axis, never passes below the $x$-axis, and takes steps $U = (1, 1), D = (1, -1)$, and two (colored) types of horizontal steps, $H_1 = (1, 0)$ and $H_2 = (1. 0)$.  Let $a_{m, n}$ be the number of such paths with $m$ total $U$ or $H_1$ steps and $n$ total $D$ or $H_2$ steps.  Then
\[
M(x, y) := \sum_{m, n = 0}^\infty a_{m, n} x^m y^n = \frac{1 - x - y - \sqrt{(1 - x- y)^2 - 4xy}}{2xy}.
\]
% Note that $M(x, xy) - 1$ satisfies the minimal polynomial
% \[
% P = {Y}^{2}{x}^{2}y+2\,Y{x}^{2}y+Yxy+{x}^{2}y+Yx+xy-Y+x
% \]
% and $M(x, xy) - 1$ can be embedded in the GF
% \[
% F(x, y, Y) = \frac{{\left(2 \, Y^{3} x^{2} y + 2 \, Y^{2} x^{2} y + Y x y + Y x - 1\right)} Y}{Y^{3} x^{2} y + 2 \, Y^{2} x^{2} y + Y x^{2} y + Y x y + Y x + x y + x - 1}.
% \]
% Then for $p \in (0, 1)$ and $(x, y, Y)$ in the direction $\rr = [1, (1-p), 1]$, there is a single smooth strictly minimal critical point with positive coordinates:
% \[
% (x, y, Y) = \left(\frac{(1-p)p^3}{p^2 - p + 1}, \frac{(1-p)^2}{p^2}, \frac{p^2 - p + 1}{p(1-p)} \right).
% \]
% This gives the asymptotic approximation
Using \cref{pr:saf1} on $M(x, xy) - 1$ gives the asymptotic formula
\[
[x^{pn} y^{(1-p)n}] M(x, y) = \frac{1}{2\pi (1-p)^2p^2} \cdot \frac{1}{n^2} \cdot \left( \frac{(1-p)^{2p - 2}}{p^{2p}}\right)^n + O\left(\frac{1}{n^3}\right).
\]



\if01
\subsubsection{General quadratic GFs}
Suppose that $F(\xx)$ is algebraic with minimal polynomial of the form $P(Y,\xx) = a(\xx) Y^2 + b(\xx)Y + c(\xx)$. A necessary condition for the hypotheses of 
\cref{pr:saf1} to hold is $b(\zero) \neq 0$.\edit{check}. 
\fi
\if01
\subsubsection{Leaves in trees}
Recall the Catalan and Narayana examples from the introduction. 
There is a further refinement \cite{ChDE2006} that considers different
types of leaves in a rooted ordered tree.  
Call a leaf of such a  tree \emph{old} if it is the leftmost
child of its parent, and \emph{young} otherwise.  They enumerate such trees
according to the number of old leaves, number of young leaves and number of
edges, finding the algebraic equation
$$
G(x,y,z) = 1 + \frac{z(G(x,y,z) - 1 + x)}{1 - z(G(x,y,z) - 1 + y)}.
$$
Thus $G$ is defined by the polynomial
$$
P(Y,x,y,z) = ***
$$
and we obtain the embedding 
$$
***
$$
\fi

\if01
\subsection{More difficult examples}

So far we have dealt with *** out of *** examples in \cite{GrMW2021}. Of the remaining ones in the catalog \cite{GrMW2021}, \cref{pr:saf1} applies for almost all \edit{how many}, but we have not yet found a combinatorial embedding in those examples. For example, bilateral Schr\"{o}der paths (see \url{https://oeis.org/A063007}) from $(0,0)$ to $(n,n)$ having $k$ North steps are enumerated by
$$G(t, z) = \frac{1}{\sqrt{1-2z-4tz+z^2}.}$$
The embedding $F({Y, t, z})$ found by using \cref{pr:saf1} and attaching $z$ to $Y$ yields no affine critical points in any relevant direction $\rr = [{(1-p), p, (1-p)}]$ for $p \in (0, 1)$.


For only *** of them does H2 fail to hold. Such cases can be treated by %the more powerful machinery of
Safonov's algorithm \cite{Safo2000}, which we intend to do in work currently in preparation. 
%The remaining cases yield, at this stage, noncombinatorial embeddings with affine critical points, and the difficulty is to prove that these points indeed contribute. 
%The recent work \cite{BMP2021} points the way.
\fi

\section{Further discussion}
\label{s:discuss}
We believe we have shown that our strategy for computing asymptotics of multivariate algebraic series is a good one. 
%Many cases occurring in applications work immediately using basic ACSV theory, and many others can be made to work with quite simple changes of variable. 
Further developments in ACSV theory, some already near completion, will allow analysis of noncombinatorial embeddings. We intend to take this up in a future work, and some cases will be challenging. For example, bilateral Schr\"{o}der paths 
% \MW{(see \url{https://oeis.org/A063007})}
from $(0,0)$ to $(n,n)$ having $k$ North steps are enumerated by
$$G(t, z) = \frac{1}{\sqrt{1-2z-4tz+z^2}.}$$
The embedding $F({Y, t, z})$ found by using \cref{pr:saf1} and attaching $z$ to $Y$ yields no affine critical points in any relevant direction.

% \MW{We note that sometimes all this machinery for algebraic functions is unnecessary. For example, every bivariate GF of the type $(1 - yv(x))^{-1}$ can be analysed via smooth point ACSV methods, with no need to consider the singularities of $v$, provided $v$ is analytic at the origin.} 

We note further that Furstenberg and Safonov are not the only relevant authors for embedding procedures. For example, Denef and Lipshitz~\cite{DeLi1987} give a somewhat more complicated method, which when applied to the example $x/\sqrt{1-x}$ yields, instead of the rather difficult to analyse embedding given by \cref{pr:furst}, the simple GF $2xY/(1-x-Y)$. This indicates a brighter future for the general program of computing multvariate asymptotics by reducing the 
algebraic to the rational case.



\acknowledgements{
This material is based upon work supported by the National Science Foundation under Grant Numbers 1641020 and 1916439, an NSERC Discovery Grant, an NSERC USRA and the American Mathematical Society Mathematics Research Community, Combinatorial Applications of Computational Geometry and Algebraic Topology.
}



\printbibliography



\end{document}
