\documentclass[finalversion]{FPSAC2021}
\articlenumber{72}			%
											%
\usepackage{url}								%
\urlstyle{same}									%
											%									
\usepackage[backend=bibtex]{biblatex}				%
\addbibresource{72Scherer.bib}				%
											%
\usepackage{enumitem}							%
%\usepackage{lipsum}								%
\usepackage{color}								%
											%	
											%
\newtheorem{theorem}{Theorem}[section]					%
\newtheorem{lemma}[theorem]{Lemma}				%
\newtheorem{conjecture}[theorem]{Conjecture}			%
\newtheorem{prop}[theorem]{Proposition}				%
\newtheorem{corollary}[theorem]{Corollary}			%
\newcommand{\oh}[0]{\mathcal{O}}					%
\DeclareMathOperator{\Id}{Id}						%
											%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title[A criterion for sharpness in tree enumeration and a proof of a conjecture of Kuperberg]{A criterion for sharpness in tree enumeration and the asymptotic number of triangulations in Kuperberg's $G_2$ spider}

\author{Robert Scherer\thanks{\href{mailto:rescherer@math.ucdavis.edu}{rescherer@math.ucdavis.edu}.}\addressmark{1}}

\address{\addressmark{1}Department of Mathematics, University of California, Davis, One Shields Avenue, Davis, CA 95616, USA}

\received{\today}

\abstract{We prove a conjectured asymptotic formula of Kuperberg from the representation theory of the Lie algebra $G_2$. 
    Given a non-negative sequence $(a_n)_{n\geq 1}$, the identity $B(x)=A(xB(x))$ for generating functions $A(x)=1+\sum_{n\geq 1} a_n x^n$ and $B(x)=1+\sum_{n\geq 1} b_n x^n$ determines the number $b_n$ of rooted planar trees with $n$ vertices such that each vertex having $i$ children can have one of $a_i$ distinct colors. Kuperberg (\textit{J. Algebr. Combin.}, 1996) proved that this identity holds in the case that $b_n=\dim \text{Inv}_{G_2} (V(\lambda_1)^{\otimes n})$, where $V(\lambda_1)$ is the 7-dimensional fundamental representation of $G_2$, and $a_n$ is the number of triangulations of a regular $n$-gon such that each internal vertex has degree at least $6$. Moreover, he observed that $\limsup_{n\to\infty}\sqrt[n]{a_n}\leq 7/B(1/7)$. He conjectured that this estimate is sharp, or in terms of power series, that the radius of convergence of $A(x)$ is exactly $B(1/7)/7$. We prove this conjecture by introducing a new criterion for sharpness in the analogous estimate for general power series $A(x)$ and $B(x)$ satisfying $B(x)=A(xB(x))$. Moreover, by way of singularity analysis performed on a recently-discovered generating function for $B(x)$, we significantly refine the conjecture by deriving an asymptotic formula for the sequence $(a_n)$. 
}

%%%%%%%%%%%
%%%%%%%%%%%
\begin{document} %%
%%%%%%%%%%%
%%%%%%%%%%%

\maketitle

\section{Introduction}\label{Introduction} 
In this extended abstract, we prove a conjectured asymptotic estimate \cite[Conj. 8.2]{Kuperberg} for an integer sequence arising in the representation theory of the Lie algebra $G_2$.  The criterion we develop to prove this result applies to a wide class of generating functions satisfying a classic combinatorial identity from the theory of rooted planar trees. Furthermore, we significantly refine the conjectured estimate. A full-length article version of this paper is forthcoming, in which the proofs sketched in this version will be fully detailed. 

\subsection{Kuperberg's conjecture }

Let $a_0=1$, and for each positive integer $n$, let $a_n$ denote the number of triangulations of a regular $n$-gon, such that the minimum degree of each internal vertex is $6$. The sequence begins
\[
(a_n)_{n=0}^\infty =1, 0, 1, 1, 2, 5, 15, 50, 181, 697,\dots
\]
and is indexed in the On-Line Encyclopedia of Integer Sequences (OEIS, \cite{OEIS}) by A059710. 
Next, let $b_0=1$, and for each positive integer $n$ let $b_n$ denote the dimension of the vector subspace of invariant tensors in the $n$-th tensor power of the 7-dimensional fundamental representation of the exceptional simple Lie algebra $G_2. $ The sequence begins
\[
(b_n)_{n=0}^\infty=1, 0, 1, 1, 4, 10, 35, 120, 455, 1792,\dots
\]
and is indexed in OEIS as A059710.

The sequence $(b_n)$ is known to have a combinatorial interpretation as the number of lattice walks in the dominant Weyl chamber of the root system for $G_2$ that start and end at the origin, subject to certain constraints on the steps \cite{Westbury}. This type of model is not unique to $G_2$ or this particular representation; if $V$ is any irreducible representation of any complex semi-simple Lie algebra $L$, there is a similar lattice walk model for the dimension of the space of $L$-invariant $n$-tensors over $V$ (see e.g.\ \cite[Thm. 5]{Grabiner}). 

Now let $A(x)=1+\sum_{n=1}^\infty a_nx^n$ and $B(x)=1+\sum_{n=1}^\infty b_n x^n$ be the ordinary generating functions for $(a_n)_{n=0}^\infty$ and $(b_n)_{n=0}^\infty$, respectively. In \cite[Section 8]{Kuperberg}, Kuperberg proved the following remarkable identity of formal power series: 
\begin{equation}\label{eqn-functional_equation}
B(x)=A(xB(x)).
\end{equation}

Kuperberg also observed that $B(x)$ has radius of convergence $1/7$, that $B\left(1/7\right)<\infty$, and that by \eqref{eqn-functional_equation}, $A(x)$ has radius of convergence at least $(1/7)B\left(1/7\right)$, a constant whose numerical value he estimated to be approximately $6.811$. He conjectured that this bound is in fact an equality.
\begin{conjecture}[Kuperberg, 1996 \cite{Kuperberg}]
\label{conjecture}
\[
\limsup_{n\to\infty} \sqrt[n]{a_n}=7/B(1/7)\,.
\]
\end{conjecture}
The $\limsup$ is actually a limit (see Section \ref{proof}). We prove here that this conjecture is true and explicitly identify the value of the constant $7/B(1/7)$.   Moreover, we improve the exponential growth term to establish a true asymptotic formula for $(a_n)$, and we derive a full asymptotic expansion for $(b_n)$. The precise result is as follows.
\begin{theorem}\label{thm-conjecture}
Let $A(x)$ and $B(x)$ be as above. Define constants $\rho$, $K$, and $M$ by:
\begin{align}
\rho&=\frac{7}{B(1/7)}\\
K&=\frac{4117715\sqrt{3}}{864\pi}&\approx& \,2627.6\label{eqn-K}\\
M&=\frac{4\sqrt{3}}{421875\pi}\left(\frac{8575\pi-15552\sqrt{3}}{2592\sqrt{3}-1429\pi}\right)^7&\approx&\,1721.0 \label{eqn-M}\\ \nonumber
\end{align}
Then we have the following:
\begin{enumerate}[wide, labelwidth=!, labelindent=0pt, label=\normalfont]
\item[\normalfont(a)]
\textbf{Kuperberg's conjecture is true.} As $n\to\infty$,
\begin{equation} \label{eqn-first}
a_n=\rho^{n+o(n)}.
\end{equation}
\item[\normalfont(b)]
\textbf{Value of $\rho$.}
The constant $\rho$ has the explicit value
\begin{equation}\label{eqn-rho}
\rho=\frac{5\pi}{8575\pi - 15552\sqrt{3}}\,\approx \,6.8211.
\end{equation}
\item[\normalfont(c)]\textbf{Asymptotic expansion of $b_n$.}
As $n\to \infty$, the sequence $(b_n)$ grows asymptotically as 
\begin{equation}\label{eqn-b_asymptotic}
b_n= K\frac{7^n}{n^7}\left(1+\oh\left(\frac{1}{n}\right)\right)\,.
\end{equation}
Furthermore, there exists a computable sequence of rational numbers $(\kappa_i)_{i=7}^\infty$, with $\kappa_7=K\pi/\sqrt{3}$, such that as $n\to\infty$,
\begin{equation}\label{eqn-b_series}
b_n\sim \frac{7^n\sqrt{3}}{\pi} \sum_{i=7}^\infty \frac{\kappa_i}{n^i}\,.
\end{equation}
\item[\normalfont(d)]\textbf{Asymptotic formula for $a_n$.} 
Conjecture \ref{conjecture} admits the following refinement. As $n\to \infty$,
\begin{equation}\label{eqn-a_asym}
a_n= M\frac{\rho^n}{n^{7}}\left(1+\oh\left(\frac{\log n}{n}\right)\right)\,.
\end{equation}
\end{enumerate}
\end{theorem}
We also show the following, as a consequence of Theorem \ref{thm-conjecture}(b) and Lemma \ref{lemma-1} below. 
\begin{corollary}\label{cor-not_alg}
The generating functions A(x) and B(x) from Theorem \ref{thm-conjecture} are not algebraic. 
\end{corollary}
The sequences $(a_n)$ and $(b_n)$ have been studied by various authors since Kuperberg's conjecture; see for instance \cite{Westbury} and the recent \cite{Bostan}. 

\subsection{A criterion for sharpness} 
Our proof of Theorem \ref{thm-conjecture} will rely on several ideas that are far more general in their applicability than the case of the specific generating functions $A(x)$ and $B(x)$, and are of independent interest. Specifically, Conjecture \ref{conjecture} can be viewed as an asymptotic enumeration problem in the combinatorial theory of rooted trees, as \eqref{eqn-functional_equation} is a classic identity that encodes the recursive nature of these structures (see Section \ref{section_2}). 

In general, if $A(x)=1+\sum_{n\geq 1}a_nx^n$ and $B(x)=1+\sum_{n\geq 1}b_nx^n$ are ordinary generating functions having non-negative coefficients such that $a_n\geq 1$ eventually, and they satisfy \eqref{eqn-functional_equation}, then the inequality $rB(r)\leq R$ holds, where $R$ and $r$ are the radii of convergence of $A(x)$ and $B(x)$ respectively (see Lemma \ref{lemma-1}). It is natural then to ask when equality holds. We address this question in Section \ref{section_2} and eventually arrive at a criterion for equality in the estimate $rB(r)\leq R$. A simplified version of this criterion reads as follows. 
\begin{theorem}[Criterion for sharpness, simplified version]\label{thm-criterion-1}
With $A(x)$, $B(x)$, $R$, and $r$ as in the preceding paragraph, assume that $a_n\geq 0$ for all $n\geq 1$ and that $a_n \geq 1$ eventually. Then
\[
b_nr^n \neq \Theta(n^{-3/2}) \text{ as } n\to\infty \implies R=rB(r)\,.
\]
\end{theorem}
Conjecture \ref{conjecture} will follow from this criterion, since a formula from the character theory of Lie algebra representations will lead us to the preliminary estimate $b_n/7^n =\Theta (n^{-7})$ for the sequence $(b_n)$ in Conjecture \ref{conjecture} (see Section \ref{proof}). For the full criterion, including some technical details, see Theorem $\ref{thm-criterion}$ in Section \ref{section_2}.

Also of general interest is the ``singularity analysis'' discussed in Section \ref{sec-improved}, by which we study a new representation from \cite{Bostan} for the generating function $B(x)$ in Conjecture \ref{conjecture} and prove the remaining parts of Theorem \ref{thm-conjecture}. The fact that $rB(r)=R$ leads to subtle analysis in the application of known methods, namely the ``transfer theorems" of Flajolet and Odlyzko \cite{Odlyzko}, when compared to the typical case $rB(r)<R$. 

\acknowledgements{
The author would like to thank Dan Romik, Greg Kuperberg, Michael Drmota, Hamilton Santhakumar, and the FPSAC referees for helpful conversations and new ideas.  
}

\section{Simply generated trees} \label{section_2} 
\subsection{Basic definitions and analytic properties}
Let $A(x)=1+\sum_{n\geq 1} a_nx^n$ and $B(x)=1+\sum_{n\geq 1} b_nx^n$ be two power series satisfying \eqref{eqn-functional_equation}. 
It will be useful to set $y(x):=xB(x)$, whence the coefficient sequence $(y_n)_{n=1}^\infty$ of $y(x)=\sum_{n \geq 1}y_nx^n$ is given by $y_n=b_{n-1}$ for $n\geq 1$ and the identity \eqref{eqn-functional_equation} can be rewritten as
\begin{equation}
\label{eqn-functional_equation_2}
y(x)=xA(y(x)).
\end{equation}

This identity has a well-known interpretation in the theory of trees. A \textit{planar rooted tree} is an undirected acyclic graph, equipped with a distinguished node and an embedding in the plane, so that distinct subtrees dangling from the same node are ordered amongst themselves. If $A(x)=1+\sum_{n\geq 1} a_n x^n$, where the $a_n$'s are non-negative integers, and $y(x)=\sum_{n\geq 1} y_nx^n$ is related to $A(x)$ by \eqref{eqn-functional_equation_2}, then $y_n$ is the number of planar rooted trees with $n$ nodes, including the root, such that for each $i\geq 1$, an internal node with $i$ children can be colored with one of $a_i$ colors. In fact, given $(a_n)_{n\geq 1}$, the unique solution $(y_n)_{n\geq 1}$ to \eqref{eqn-functional_equation_2} is found by the Lagrange Inversion Formula \cite[Ch. 5.4]{Stanley}, which also implies that the $y_n$'s are non-negative if the $a_n$'s are, even if they are not integers. A family of trees is commonly called \emph{simply generated} (see \cite{Meir}, where this nomenclature appears to have been introduced) if the number of trees in the family is enumerated by a generating function $y(x)$ that satisfies \eqref{eqn-functional_equation_2} for some $A(x)$ of the above form. 

The article \cite{Drmota} contains several examples of \eqref{eqn-functional_equation_2} and a concise explanation of some fundamental asymptotic results, including that the Catalan numbers occur as the sequence $(y_n)_{n=1}^\infty$ when $A(x)={1}/{(1-x)}$, and in that case $y_n\sim \pi^{-\frac{1}{2}}4^{n-1}n^{-\frac{3}{2}}$ as $n\to\infty$. Generalizations of \eqref{eqn-functional_equation_2}  and statistical analysis of parameters associated to trees, such as the number of leaves, is also discussed. The text \cite[Sec. VI.7, VII.3, VII.4]{Flajolet} contains a broad treatment of the analytic framework for \eqref{eqn-functional_equation_2} as a functional equation, including asymptotic results by way of singularity analysis applied to several natural tree examples from the literature.

While the identity \eqref{eqn-functional_equation_2} is a priori just a relationship of formal power series, it will be abundantly fruitful to view it as a functional equation of analytic maps. We will call a sequence of real numbers $(a_n)_{n\geq 1}$ \textit{admissible} if $a_n\geq 0$ for all $n$, $a_n \geq 1$ eventually, and $\limsup_{n\to\infty} \sqrt[n]{a_n} <\infty$. Then it is relatively straightforward to verify the following facts.
\begin{lemma}\label{lemma-1} For admissible $(a_n)_{n\geq 1}$, let $y(x)=\sum_{n\geq1}y_nx^n$ be the unique solution to \eqref{eqn-functional_equation_2}, with radius of convergence $r$. Let $R$ be the radius of convergence of $A(x)$. Then the following are true:
\begin{enumerate}
\item The identity \eqref{eqn-functional_equation_2} holds on $\Omega=\{x: |x|<r\}$, as an identity of the analytic functions $A$ and $y$ defined by their respective power series.
\item $y$ extends continuously to the boundary $\partial\Omega$, and \eqref{eqn-functional_equation_2} remains valid there.
\item $0<r<y(r)\leq R\leq 1$\,.
\item $A$ does not vanish on $y(\Omega)\setminus{\{0\}}$.
\item The function
$\psi(z):=\frac{z}{A(z)}$
is analytic on $y(\Omega)$ and satisfies
\begin{equation}\label{eqn-derivative}
\psi'(z)=\frac{A(z)-zA'(z)}{A(z)^2}=\frac{1-\sum_{n=1}^\infty a_n(n-1)z^n}{A(z)^2}.
\end{equation}
\item $y:\Omega\to y(\Omega)$ is a biholomorphism, and $\psi(y(z))=z$ for $z\in\Omega$.
\end{enumerate}
\end{lemma}
The proof amounts to complex calculus, and all the details will be in the full-length article. There are more general conditions than ``admissible" to obtain similar analytic properties, but our choice simplifies the exposition and describes Kuperberg's triangulations as well as many natural combinatorial examples.

As a consequence of the lemma and \eqref{eqn-rho}, we obtain a simple proof of Corollary \ref{cor-not_alg}: 
\begin{proof}[Proof of Corollary \ref{cor-not_alg}]
Observe that $y(1/7)=1/\rho$. If $F(A(z),z)=0$ for $F$ a bivariate polynomial with integer coefficients, then $0=F(A(1/\rho), 1/\rho)=F(7/\rho, 1/\rho)=0$, by \eqref{eqn-functional_equation_2}.
This is absurd since $1/\rho$ is transcendental, which also implies directly that $B(x)$ is transcendental.
\end{proof}
\subsection{Full sharpness criterion and a proof of Theorem \ref{thm-criterion-1}}
The following new theorem provides a way to check that the radius of convergence of the function $A$ in \eqref{eqn-functional_equation_2} is as small as possible, namely equal to $y(r)$. 
\begin{theorem}\label{thm-main}
Suppose that $(a_n)_{n\geq 1}$ is admissible, and the generating functions $A(x)=1+\sum_{n=1}^\infty a_n x^n$ and $y(x)=\sum_{n=1}^\infty y_n x^n$ satisfy \eqref{eqn-functional_equation_2}. If $y(r)<R$, then $A(x)-xA'(x)$ vanishes at $x=y(r)$. 
\end{theorem}
\begin{proof} Assume that $y(r)<R$. Then $A$ is analytic on an open disk, which we call $E$, that is centered at $y(r)$ and contained in the disk $\{z:|z|<R\}$. By Lemma \ref{lemma-1}, $A(y(r))=y(r)/r >0$ (as mentioned above, Lagrange Inversion \cite[Ch. 5.4]{Stanley} implies that $y_n\geq 0$), so we may assume, by replacing $E$ with a smaller open disk if necessary, that $A$ does not vanish on $E$, and hence that $\psi$ is analytic on $y(\Omega)\cup E$. If we assume further, toward showing a contradiction, that $A(y(r))-y(r)A'(y(r))\neq 0$, then $\psi'(y(r))\neq 0$, by \eqref{eqn-derivative}.
It follows that $\psi$ is locally invertible at $y(r)$. That is, after possibly replacing $E$ with a smaller open disk centered at $y(r)$,
the map $\psi|_{E}: E\to \psi(E)$ is a homeomorphism, with an analytic inverse map $\psi|_{E}^{-1}$.
Since $r$ is a boundary point of $\Omega$, we see that $\emptyset\neq \psi(y(\Omega)\cap E)\subset \Omega \cap \psi(E)$. By the injectivity of $\psi|_E$, one sees that $y$ and $\psi|_{E}^{-1}$ agree on the open set $\psi(y(\Omega)\cap E)$, and hence on the larger set $\Omega \cap \psi(E)$ as well, by analytic continuation. Thus, the map $\psi|_{E}^{-1}$ serves as an analytic continuation of $y$ to $\psi(E)$. Since $r\in\psi(E)$, this contradicts a fact known as Pringsheim's Theorem \cite[Thm. 5.7.1]{Hille}, which asserts that an analytic function with non-negative real coefficients and a finite radius of convergence necessarily has a singularity at the point where the boundary of its disk of convergence intersects $[0,\infty)$. This is the contradiction we sought, and the proof is complete. 
\end{proof}

If we phrase the theorem in a slightly weaker form by replacing the consequent with the statement that $A(x)-xA'(x)=0$ for \emph{some} $x$ in $(0,R)$, then the converse  is well-known to be true, and it follows from Theorem \ref{thm-growth}(1) below. Theorem~\ref{thm-growth} contains even deeper asymptotic information than that, however, in particular regarding the \emph{subexponential} (i.e. polynomial) growth rate of $(y_n)$. This, it turns out, will be instrumental in proving Theorem \ref{thm-conjecture}, as it shows how information about the growth of $(y_n)$ can certify that $A(z)-zA'(z)$ does not vanish on $(0,R)$, and hence, by Theorem \ref{thm-main}, that $y(r)=R$.

\begin{theorem}[Meir, Moon, 1978 \cite{Meir}]\label{thm-growth}
Suppose that $A(x)=1+\sum_{n=1}^\infty a_nx^n$ and $y(x)=\sum_{n=1}^\infty y_n x^n$ (with radii of convergence $R$ and $r$, respectively) satisfy \eqref{eqn-functional_equation_2}, with $(a_n)$ admissible. If there exists $\tau\in(0,R)$, such that $A(\tau)-\tau A'(\tau)=0$, then the following are true.
\begin{enumerate}
\item[(1)] $y(x)$ has radius of convergence $r=\tau/A(\tau)$, and $y(r)=\tau<R$. 
\item[(2)] The coefficient sequence $(y_n)_{n=1}^\infty$ satisfies the following asymptotic estimate: 
\begin{align*}
y_n&=\frac{C}{r^nn^{3/2}}(1+\mathcal{O}(n^{-1}))=\frac{C\cdot A'(\tau)^n}{n^{3/2}}(1+\mathcal{O}(n^{-1})),
\end{align*}
as $n\to\infty$,
where $C =\sqrt{\frac{A(\tau)}{2\pi A''(\tau)}}$. 
\end{enumerate}
\end{theorem}

Combining Theorems \ref{thm-main} and \ref{thm-growth}, we obtain the following dichotomy. 
\begin{theorem}[Criterion for sharpness, full version]\label{thm-criterion}
Suppose that $A(x)=1+\sum_{n\geq1} a_nx^n$ and $y(x)=\sum_{n\geq 1}y_nx^n$ (with radii of convergence $R$ and $r$, respectively) satisfy \eqref{eqn-functional_equation_2}, with $(a_n)$ admissible. Then exactly one of the following is true: 
\begin{enumerate}
\item[(1)] $A(x)-xA'(x)$ is non-vanishing for $x\in(0,R)$, in which case $R=y(r)$.
\item[(2)] $R>y(r)=\tau$, where $\tau$ is the unique solution to $A(\tau)-\tau A'(\tau)=0$ on $(0,R)$, and $y_n=Cr^{-n}n^{-3/2}(1+o(1))$ as $n\to\infty$, for some constant  $C>0$. 
\end{enumerate}
\end{theorem}

In particular, the absence of the $n^{-3/2}$ factor in the asymptotic expansion of $y_n$ certifies that the inequality $y(r)\leq R$ is actually equality, so Theorem \ref{thm-criterion-1} is an immediate corollary.
\section{Proof of Conjecture \ref{conjecture}} 
\label{proof} 

Henceforth, let $A(x)=1+\sum_{n=1}^\infty a_nx^n$ and $B(x)=1+\sum_{n=1}^\infty b_nx^n$ be as in Theorem \ref{thm-conjecture}. Recall that $1/7$ is the radius of convergence of $B(x)$ and $y(x)$ and that $\rho:=7/B(1/7)=1/y(1/7)$, and let $R$ denote the radius of convergence of $A(x)$. It's not hard to show that $(a_n)_{n\geq 1}$ is an increasing sequence and that $R<\infty$, so that we may apply the criterion in Theorem \ref{thm-criterion-1} (or \ref{thm-criterion}). In order to do so, we must check that $b_n/7^{n}\neq \Theta(n^{-3/2})$. 
\begin{prop}\label{prop-asymptotics}
The sequence $(b_n)_{n=0}^\infty$ satisfies the following asymptotic equivalence: As $n\to\infty$,
\[
b_n\sim K\frac{7^n}{n^7},
\]
where
$
K=\frac{4117715\sqrt{3}}{864\pi}\approx 2627.6\,.
$
\end{prop}
In the introduction we described a lattice walk model in which the $b_n$'s denote the number of $n$-step excursions that start and end at the origin.
This is encoded in the following formula from character theory \cite[p.15]{Greg}: $b_n$ is given as the coefficient of $x^ny^n$ in the Laurent polynomial $WM^n$, where
\[
M(x,y)=1+x+y+xy+x^{2}y+xy^{2}+(xy)^{2},
\]
and
\begin{align*}
W(x,y)=x^{-2}y^{-3}(x^2y^3&-xy^3+x^{-1}y^2-x^{-2}y+x^{-3}y^{-1}-x^{-3}y^{-2}\\
&+x^{-2}y^{-3}-x^{-1}y^{-3}+xy^{-2}-x^2y^{-1}+x^3y-x^3y^2).
\end{align*}
Proposition \ref{prop-asymptotics} can be proved by approximating the value
\[
b_n=\frac{1}{(2\pi i)^2}\oint\oint \left[W(z_1,z_2)\cdot M(z_1,z_2)^n\cdot \frac{1}{(z_1z_2)^{n+1}}\right] \,dz_1\,dz_2
\]
in a standard manner, for contours passing through a ``saddle-point" of the integrand.

The proposition indicates by Theorem \ref{thm-criterion-1} that $R=1/\rho$, i.e. 
$
{\limsup_{n\to \infty} \sqrt[n]{a_n}}
=\rho\,.
$
It is not hard to show from the definition of $(a_n)$ that 
$
\log a_n +\log a_m \leq\log a_{n+m},
$
which implies by a lemma attributed to Fekete \cite{Fekete}
that
${
\lim_{n\to\infty}\sqrt[n]{a_n}}$$=\sup_{n\in\mathbb{N}} \sqrt[n]{a_n}.
$
This limit must be $\rho$, and \eqref{eqn-first} then follows directly. 

\section{Proof of Theorem \ref{thm-conjecture} (b)-(d)}
We record here a  ``transfer theorem" of Flajolet and Odlyzko \cite{Odlyzko}, which allows one to transfer asymptotic growth estimates of a function $f$ near a singularity to asymptotic growth estimates of the function's Taylor coefficients $(f_n)_{n\geq 0}$. The whole process is sometimes called ``singularity analysis."  Assume the following setup: $f$ is a function analytic at the origin, with radius of convergence $R>0$ and Taylor expansion $f(z)=\sum_{n=0}^\infty f_nz^n$, and $f$ can be continued analytically to a ``Delta-domain"
around the disk of convergence of $f$. Such a domain is denoted by $\Delta_R$ and defined to be any open set of the form
\[\{z:|z|<R+\epsilon, |\text{Arg}(z-R)|>\theta\},\] for some $\epsilon>0$ and some $\theta\in(0,\pi/2)$. 
The following statement combines Theorem 2 and Corollary 2 from \cite{Odlyzko}. Here and in the sequel, the principal branch of the logarithm is denoted by $\log$.
\begin{theorem}[Flajolet, Odlyzko, 1990]\label{thm-transfer}
Suppose $F(z)=g(z)+f(z)$, where $f$ and $g$ are analytic on {$\{z: |z|<R\}$}, and furthermore that $f(z)$ is analytic in a Delta-domain $\Delta_R$ and satisfies 
\[f(z)=\oh\big((1-z/R)^\alpha(\log(1-z/R))^\gamma\big),\] 
as $z\to R$ in $\Delta_R$, for $\alpha,\gamma\in\mathbb{R}$. Then as $n\to\infty$, the Taylor coefficients  $(F_n), (f_n),$ and $(g_n)$, of $F, f,$ and $g$, satisfy
\[
F_n=g_n+f_n=g_n+\oh\left(\frac{n^{-\alpha-1}(\log n)^\gamma}{R^n}\right).
\]
\end{theorem}
The theorem is most meaningful when $g_n$ is known explicitly and has asymptotically larger order than $f_n$. 
We apply it now to get asymptotic estimates for $(a_n)$ and $(b_n)$, with $\gamma=1$ in both cases. 

\label{sec-improved}
\subsection{Evaluation of $\rho$ and analytic continuation of $B$}\label{sub-ext}
In the recent paper \cite[p. 8]{Bostan} is given the following remarkable closed formula for the generating function $B$ in terms of hypergeometric series. 
\begin{theorem}[Bostan, Tirrell, Westbury, Zhang, 2019]\label{thm-Bostan}
\begin{equation}\label{eqn-formula}
B(z)=\frac{1}{30z^5}\left[ R_1(z)\cdot {_2F_1}\left(\frac{1}{3},\frac{2}{3};2;\phi(z)\right)+R_2(z)\cdot {_2F_1}\left(\frac{2}{3},\frac{4}{3};3;\phi(z) \right)+5P(z)\right],
\end{equation}
where 
\begin{align*}
R_1(z)&=(z+1)^2(214z^3+45z^2+60z+5)(z-1)^{-1},\\
R_2(z)&=6z^2(z+1)^2(101z^2+74z+5)(z-1)^{-2},\\
\phi(z)&=27(z+1)z^2(1-z)^{-3},\\
P(z)&=28z^4+66z^3+46z^2+15z+1.
\end{align*} 
\end{theorem}
Evaluating at $z=1/7$ and using standard identities for the ${_2F_1}$ hypergeometric function, one obtains \eqref{eqn-rho}.
In deriving formula \eqref{eqn-formula}, the authors of \cite{Bostan} demonstrate that $B$ is the solution of a linear differential equation of the form
$
B'''+a_2B''+a_1B'+a_0B=0,
$ where the coefficients $a_i$, $i=0,1,2$, are rational functions with poles at $0, -1/2, -1,$ and $1/7$.
\footnote{
As a consequence, they confirm a conjectured third-order linear recurrence relation (with quadratic coefficients in $n$) for $(b_n)$. 
}
From this fact, and since $B$ is expressed on $\Omega=\{z:|z|<1/7\}$ by a convergent power series and is analytic near $z=-1$ (by \eqref{eqn-formula} and $\phi(-1)=0$), the theory of differential equations implies that $B$ can be continued analytically and uniquely along any path avoiding the set $\{-1/2,1/7\}$ (see e.g.\ \cite[p.119]{Smith}). For example, $B$ has a unique analytic continuation to the simply-connected doubly slit plane 
\[
\tilde{\Omega}=\mathbb{C}\setminus{\big((\infty, -1/2]\cup [1/7, \infty)\big)}.
\]
In particular, $B$ extends to a Delta-domain around $\Omega$. In order to apply Theorem \ref{thm-transfer} to $(b_n)$, we must first determine the singular nature of $B$ near $1/7$. This is our next step. 
\subsection{Singular expansion of $B$ and asymptotics of $(b_n)$}
\begin{lemma}[\cite{Wolfram}]\label{lemma-expansion}
For constants $a,b\in\mathbb{R}^+$ and a variable $z$ satisfying $|1-z|<1$, we have
\begin{equation}\label{eqn-1}
_2F_1(a,b;a+b+1,z)=C_{a,b}+S_{a,b}(z)+\log(1-z)\cdot T_{a,b}(z),
\end{equation}
with the following definitions:
\[
C_{a,b}:=\frac{\Gamma(a+b+1)}{\Gamma(a+1)\Gamma(b+1)},
\]
\[
T_{a,b}(z):=\frac{\Gamma(a+b+1)}{\Gamma(a)\Gamma(b)}\cdot\left(\sum_{k=0}^\infty \left[\frac{(a+1)_k(b+1)_k}{k!(k+1)!}\cdot(1-z)^{k+1}\right]\right),
\]
and
\[
S_{a,b}(z):=\frac{\Gamma(a+b+1)}{\Gamma(a)\Gamma(b)}\cdot
\left(\sum_{k=0}^\infty \left[ \frac{(a+1)_k(b+1)_k}{k!(k+n)!}\cdot c_k\cdot (1-z)^{k+1}\right]\right),
\]
where
$c_k=\psi_0(a+k+1)+\psi_0(b+k+1)-\psi_0(k+1)-\psi_0(k+2)$, for the digamma function $\psi_0=\Gamma'/\Gamma$, and $(q)_k=q(q+1)\cdots (q+k-1)$ is the rising Pochhammer function.
\end{lemma}
Using the lemma we can expand the hypergeometric functions in \eqref{eqn-formula}, obtaining
\begin{equation}\label{B-expansion}
B(z)=f(z)+\log(1-\phi(z))g(z),
\end{equation}
for $|1-\phi(z)|<1$, 
where
\begin{align*}
f(z)=\frac{1}{30z^5}\left[R_1(z)\left(C_{\frac{1}{3},\frac{2}{3}}+S_{\frac{1}{3},\frac{2}{3}}(\phi(z))\right)+R_2(z)\left(C_{\frac{2}{3},\frac{4}{3}}+S_{\frac{2}{3},\frac{4}{3}}(\phi(z))\right)\right]+P(z),
\end{align*}
and
\[
g(z)=\frac{1}{30z^5}\left[R_1(z)\left(T_{\frac{1}{3},\frac{2}{3}}(\phi(z))\right)+R_2(z)\left(T_{\frac{2}{3},\frac{4}{3}}(\phi(z))\right)\right].
\]
Adopting the change of variable $Z=1-7z$ and expanding $f$ and $g$ in powers of $Z$, one can deduce the following singular expansion of $B$, with $K$ as defined in Theorem \ref{thm-conjecture}. 

\begin{prop}\label{prop-B_sing} As $z\to 1/7$ in $\tilde{\Omega}$, 
\begin{equation}\label{eqn-B_sing}
B(z)=p(Z)-\frac{K}{6!}Z^6\log Z+Z^7H_2(Z)+Z^7H_1(Z)\log Z\,,
\end{equation}
where $H_1(Z)$ and $H_2(Z)$ are power series with positive radii of convergence and non-zero constant terms, and $p(Z)$ is a degree-six polynomial with $p(0)=y(1/7)=1/\rho$. 
\end{prop}

Theorem \ref{thm-transfer} applies to \eqref{eqn-B_sing} with $F=B$, $g=p(Z)-\frac{K}{6!}Z^6\log Z$, $\gamma=1$, $\alpha=7$, $R=1/7$,
and $f=Z^7H_1(Z)\log Z+Z^7H_2(Z)=\mathcal{O}(Z^7\log Z)$. The Taylor coefficients of $g$ can be computed exactly by noting that for $n>7$, the $n$th Taylor coefficient of $(1-x)^6\log(1-x)$ is $-6!/[n\cdot (n-1)\cdots (n-6)]$. Then \eqref{eqn-b_asymptotic} follows, and by computing higher order coefficients of $B(z)$, the asymptotic series \eqref{eqn-b_series} can also be verified. Actually, Theorem \ref{thm-transfer} alone would give $\mathcal{O}(\log n/n)$ as the error term in \eqref{eqn-b_asymptotic}, but computing the very next term in the asymptotic series shows that the error is $\mathcal{O}(1/n)$.

\subsection{Singular expansions of $\psi$ and $A$ near $1/\rho$, and asymptotics of $(a_n)$}
To estimate the growth of $(a_n)$ by Theorem \ref{thm-transfer}, we must analyze $A$ near the singularity $y(1/7)=1/\rho$. Before that we will determine the singular nature of $\psi$, which was defined in Lemma~\ref{lemma-1}, where we also saw that $(y\circ \psi)|_{y(\Omega)}=\text{Id}|_{y(\Omega)}$. 
Defining $\Lambda:=\{z:|z|< 1/\rho\}$, which contains $y(\Omega)$, we start with the following extension lemma.  
\begin{lemma}\label{lemma-psi}
The function $\psi$ is analytically continuable to a Delta-domain $\Delta_{1/\rho}$ around $\Lambda$. Furthermore, 
\[
(y\circ \psi)|_{\Delta_{1/\rho}}=\Id|_{\Delta_{1/\rho}}.
\]
\end{lemma}
\begin{proof}[Proof sketch]
We outline the main ideas of the proof.
First, from the estimate $A(y(1/7))=7y(1/7)\approx 1.03$, one deduces that $\sum_{n\geq 1} a_nz$ <1 for $z\in\overline{\Lambda}$, so that $A$ is non-vanishing on $\overline{\Lambda}$, and $\psi$ extends analytically to $\Lambda$ and continuously to $\partial\Lambda$. 
A similar estimate using \eqref{eqn-derivative} shows that $\psi'$ extends continuously to $\overline{\Lambda}$ and  does not vanish there.

With these preliminary considerations in mind, one argues that $\psi(\Lambda)\subset\tilde{\Omega}$. This follows from the next two claims, which can be verified by standard complex calculus: (1) If $z\in \overline{\Lambda}\setminus{\mathbb{R}}$, then $\psi(z)\in \mathbb{R}$; and (2) $\psi$ maps $[-1/\rho, 1/\rho]$ bijectively onto $[\psi(-1/\rho), 1/7]\subset (-1/2, 1/7]$. 

Since $\psi(\Lambda)\subset \tilde{\Omega}$ we see that $y$ is analytic on $\psi(\Lambda)$. Moreover, by permanence of the identity $(y\circ \psi)|_{y(\Omega)}=\text{Id}|_{y(\Omega)}$, we have $(y\circ \psi)|_{\Lambda}=\text{Id}|_{\Lambda}$. To extend this identity to a Delta-domain $\Delta_{1/\rho}$ around $\Lambda$, it remains to show that $\psi$ is analytic there. 
Geometrically, the main idea is that since $y'(1/7)>0$ the map $y$ acts near $1/7$ approximately as a dilation, and hence is invertible near $1/7$ in $\tilde{\Omega}$, with a local inverse that extends $\psi$ to a region of the form $D_{\lambda,\delta}:=\{z:|z-y(1/7)|<\lambda, |\arg(z-y(1/7))| >\delta \}$, for some small $\lambda >0$ and some $\delta\in(0,\pi/2)$. To finish extending $\psi$ to $\Delta_{1/\rho}$, it suffices by compactness of the set $\partial \Lambda \setminus{D_{\lambda,\delta}}$ to provide analytic continuations of $\psi$ around all points in an arbitrary finite subcollection of $\partial \Delta\setminus{\{1/\rho\}}.$ To this end one can use the local inverse of $y$ about an arbitrary point in  $\psi(\partial{\Lambda})\setminus{\{1/7\}}$, as it is easy to check that $y'$ does not vanish there. Having extended $\psi$ to a Delta-domain $\Delta_{1/\rho}$ by patching together local inverses of $y$, we should check that $y$ is a global inverse to $\psi$ on $\Delta_{1/\rho}$. One need only observe that $\psi(\Delta_{1/\rho})\subset {\tilde{\Omega}}$, by construction. It follows that $y$ is analytic on $\psi(\Delta_{1/\rho})$, and $(y\circ \psi)|_{\Delta_{1/\rho}}=\text{Id}|_{\Delta_{1/\rho}}$, by the principle of permanence.
\end{proof}

As we have just seen, the fact that $y(r)=R$ in the notation of Theorem~\ref{thm-criterion} leads to rather subtle analysis when compared to the much more common situation of $y(r) < R$, in which case $A$ and $\psi$ are a priori analytic in a neighborhood of $y(r)$, which makes more transparent the analytic continuation of $y$. For a similar argument to ours in the sharp case $y(r)=R$, carried out in another context, see \cite{Felsner}, particularly Section 4.

Lemma \ref{lemma-psi} provides analytic preconditions to rigorously justify a ``bootstrapping procedure" (discussed in \cite[Ch. 2]{DeBruijn}) that locally inverts $y$ near $1/7$, up to an asymptotically negligible error term. The main thrust of the method can be shown by example: Consider the equation $y=x+x^2+x^2\log x$. Then $x\sim y$, as $x,y\to 0$, and $\log y=\log x+\log (1+x+x\log x)=\log x+\mathcal{O}(x\log x).$ It follows that $\log x=\log y+\mathcal{O}( y \log y)$. Since $x=y-x^2+x^2\log x$, we obtain $x^2=y^2+\mathcal{O}(y^3\log y)$. Plugging back into the original equation, this yields 
\[
x=y-y^2-y^2\log y+\mathcal{O}(y^3\log y).
\]The proof of the next proposition is similar, just more involved. Let $V=1-\rho z$. 

\begin{prop} $\psi(z)$ admits the following singular expansion: as $z\to y(1/7)$ in $\Delta_{1/\rho}$, \label{prop-psi_sing}
\begin{equation} \label{eqn-psi-sing}
\psi(z)=\gamma(V)+CV^6\log V+\oh(V^7 \log V), 
\end{equation}
where
$
C=M/(49\cdot 6!)
$
with $M$ as in \eqref{eqn-M},
and $\gamma(V)$ is a degree-six polynomial with $\gamma(0)=1/7$. 
Furthermore, the error term $\psi(z)-\gamma(V)-CV^6\log V$ is analytic in $\Delta_{1/\rho}$.
\end{prop}

We should turn this result into a statement about $A$. Since $\psi$ vanishes at $0$ and is injective on $\Delta_{1/\rho}$, by Lemma \ref{lemma-psi}, $\psi$ doesn't vanish on $\Delta_{1/\rho}\setminus{\{0\}}$. Thus, $A(z)=z/\psi(z)$ also extends analytically to $\Delta_{1/\rho}$. By manipulating \eqref{eqn-psi-sing} and justifying the steps analytically, the singular expansion of $A(z)$ near $1/\rho=y(1/7)$ is found to be the following. 
\begin{prop}\label{prop-A_sing} $A(z)$ admits the following singular expansion: as $z\to y(1/7)$ in $\Delta_{1/\rho}$,
\begin{equation}\label{eqn-A_sing}
A(z)=\eta(V)-\frac{49C}{\rho}V^6\log(V)+\oh(V^7\log V),
\end{equation}
where $\eta$ is a degree-seven polynomial.
The error term 
$A(z)+(49C/\rho)V^6\log V-\eta(V)$ is analytic in $\Delta_{1/\rho}$.
\end{prop}
By Theorem \ref{thm-transfer} and the Taylor expansion of $(1-x)^6\log(1-x)$ mentioned after Proposition~$\ref{prop-B_sing}$, we see that \eqref{eqn-A_sing} implies \eqref{eqn-a_asym}, which proves Theorem \ref{thm-conjecture}.
The complete proofs in this section are a bit technical, and they will be fully detailed in the full-length version. 

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

%The next line makes a manual change to the .cls file's definition of the field "url". This is to get the long url to break, otherwise it runs off the page. The "breaklinks=true" option in the hyperref package did not work, hence this adjusment. However, this line can be commented out (and the pdf will compile according to the original .cls file) if the editor should have a different way of addressing the long url in the bibliography. 

%\DeclareFieldFormat{url}{\textsc{url}: \url{#1}} 

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

\printbibliography
\end{document}







