\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\usepackage{tikz}
\usetikzlibrary{calc}
\def\tn{\textnormal}
\def\D{\mathcal{D}}
\def\P{\mathcal{P}}
\def\T{\mathcal{T}}
\newcommand{\set}[1]{\left\{#1\right\}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{notation}[theorem]{Notation}
\begin{center}
\vskip 1cm{\Large\bf
Connected Chord Diagrams and the \\
\vskip .1in
Combinatorics of Asymptotic Expansions
}
\vskip 1cm
Ali Assem Mahmoud\\
Department of Mathematics \\
Faculty of Science \\
Cairo University \\ Egypt\\
and\\
Department of Combinatorics and Optimization\\
University of Waterloo \\
Waterloo, ON N2L 3G1 \\
Canada\\
\href{mailto:ali.mahmoud@uwaterloo.ca}{\tt ali.mahmoud@uwaterloo.ca} \\
\ \\
Karen Yeats\\
Department of Combinatorics and Optimization\\
University of Waterloo \\
Waterloo, ON N2L 3G1 \\
Canada\\
\href{mailto:kayeats@uwaterloo.ca}{\tt kayeats@uwaterloo.ca}
\end{center}
\vskip .2 in
\begin{abstract}
In this article we study an asymptotic expansion for $C_n$, the
number of connected chord diagrams on $n$ chords. The expansion is
obtained in earlier work by means of alien derivatives applied to the
generating series of connected chord diagrams; we seek a combinatorial
interpretation. The main outcome presented here is a new combinatorial
interpretation for sequence \seqnum{A088221} of
the {\it On-Line Encyclopedia of Integer Sequences}. We
show that sequence \seqnum{A088221}
counts pairs of connected chord diagrams (allowing empty diagrams).
This gives a combinatorial interpretation for part of the closed form
of the asymptotic expansion of $C_n$.
\end{abstract}
\section{Introduction}\label{sec intro}
The concrete result of this paper is a bijection between ordered pairs of chord diagrams and certain rooted trees with a chord diagram structure at each vertex, giving a new combinatorial interpretation for entry \seqnum{A088221} of the
{\it On-Line Encyclopedia of Integer Sequences} (OEIS). However, this result is more than just an incidental bijection, but rather a preliminary step in a much bigger question about when we can obtain combinatorial understandings of asymptotic expansions and transseries.
We come at both the concrete result and the bigger question from two directions. On one side we come as pure combinatorialists following the classic path of seeing divergent series as formal power series first, looking to use different kinds of formal expansions for counting, and finding beautiful and insightful bijections between classes of combinatorial objects that explain identities between their counting sequences. On the other side we come more as mathematical physicists interested in working towards a better understanding of resurgence and instanton expansions in a way which is explicit and applicable in specific cases of interest in quantum field theory. However, our concrete work herein is purely combinatorial, and skipping this introduction and the concluding discussion, the paper can be read without any other background.
Transseries are a kind of formal expansion allowing many more expressions than powers of $x$ as monomials. Transseries are important both in analysis and in logic---a sign of their fundamental importance. For the application we investigate, it suffices to consider the special case of expansions of the form
\[
\sum_{n,m\geq 0} c_{n,m}x^{n}(e^{-1/2x}x^{-1/2})^m
\]
An important problem in quantum field theory is to understand how (and to what extent) non-perturbative effects can be recovered from perturbative approaches. In particular we may wish to start from the Hopf algebraic formulation of perturbative quantum field theory of Connes and Kreimer and recover non-perturbative information. This is one of the reasons one of us studies Dyson-Schwinger equations. Recently, resurgent analysis and the theory of transseries have been brought to bear on this question \cite{BMV, DunneUnsal, BellonClavier}. In the simple transseries form above, the $m=0$ part is the perturbative part, $m=1$ is the first instanton part, $m=2$, the second instanton part, and so on. The instantons are non-perturbative effects. In \cite{Geraldmichi} Borinsky and Dunne pursue a detailed case study of a particular Dyson-Schwinger equation in Yukawa theory which had been solved perturbatively and given an exact functional solution by Broadhurst and Kreimer \cite{bkerfc}. From the Dyson-Schwinger equation Borinsky and Dunne were able to give and understand the instanton expansion of this same problem to all orders and so reveal the non-perturbative structure.
However, this story is not just Hopf algebraic and analytic, but also combinatorial. The simple transseries form can be seen as a bivariate formal series, with the second variable $\xi = e^{-1/2x}x^{-1/2}$ suggestively named. The perturbative solution to the Dyson-Schwinger equation studied by Broadhurst and Kreimer is essentially the generating function for rooted connected chord diagrams, something which has been explored further in \cite{yu, terminal, con, Karenmarkushihn, michi}. The first instanton expansion, then, is just an appropriate normalization of the asymptotic expansion of number of rooted connected chord diagrams. The coefficients of this expansion are, after taking care of some straightforward signs and denominators, also a sequence of positive integers, and through Borinsky's theory of factorially divergent power series \cite{michi}, there is an expression for this expansion in terms of the generating function for rooted connected chord diagrams.
This situation calls out for a combinatorial interpretation. Though we are only able to give such an interpretation for part of the resulting function, just this part yields the highly non-trivial new bijection mentioned above. After presenting the background and details of this bijection, we conclude the paper by a discussion of the all orders transseries solution of Borinsky and Dunne, and what an as yet unknown combinatorial understanding of it should look like. Borinsky's theory of factorially divergent power series is also an important step towards a combinatorial interpretation, as it gives general tools for relating a formal series to the series of the asymptotic expansion of its coefficients entirely at the level of formal power series. However, these series manipulations do not in general maintain good combinatorial interpretations throughout the process, notably because of cancellations between parts with different signs.
\section{Chord diagrams}\label{chorddiagrams section}
(Connected) chord diagrams stand as a rich structure that becomes handy and informative in a variety of contexts, including bioinformatics \cite{bioinfo}, quantum field theory \cite{karenbook, michi1, michi}, and data structures \cite{datast}, as well as in pure combinatorics \cite{flajoletchords}.
\begin{definition}[Rooted chord diagrams]
A rooted chord diagram of size $n$ is a matching of the set $\{1,\ldots,2n\}$. Each pair in the matching is a \textit{chord}.
We visualize rooted chord diagrams by drawing $\{1,\ldots, 2n\}$ as vertices counterclockwise on a circle, or lined up from left to right, with the chords indicated by lines crossing the circle or arcs above the line. The vertex $1$ is the \textit{root vertex}, and the chord involving $1$ is the \textit{root chord}. With the root indicated, the labels $\{1,\ldots, 2n\}$ are unnecessary and so
are not drawn.
\end{definition}
Then the generating series for rooted chord diagrams is
\begin{equation}\label{rootedchorddiagsgen}
D(x):=\sum^\infty_{n=0}(2n-1)!!\; x^n
\end{equation}
Here $(2n-1)!!$ is the double factorial, defined by
$(2n-1)!! = 1\cdot 3\cdot \cdots (2n-3)(2n-1)$.
All chord diagrams considered here are rooted and so, when we say a chord diagram we tacitly mean a rooted one.
The representation of a chord diagram with vertices in a line and chords as arcs above the line is called the \textit{linear representation} of the chord diagram.
A chord in the diagram may be referred to as $c=\{a**0}$, and $\beta, c_k \in \mathbb{R}$, and
where $\Gamma(z)=\int_0^\infty x^{z-1}e^{-x}dx$ for $\text{Re}(z)>0$ is the gamma function.
When $a_n$ has such an asymptotic expansion, then the formal power series $f(x) = \sum_{n\geq 0}a_nx^n$ is, following Borinsky, said to be a \emph{factorially divergent power series} and the set of all such is written $\mathbb{R}[[x]]^\alpha_\beta$. For $\alpha>0$,the $\mathbb{R}[[x]]^\alpha_\beta$ are rings, and the coefficients $c_k$ as given above are well-defined, and so we write $c_k^f$ to emphasize the dependence on $f$ and define
\begin{definition}[\cite{michi1}]\label{map}
For $\alpha,\beta\in \mathbb{R}$, with $\alpha>0$, let $ \mathcal{A}_\beta^\alpha:\mathbb{R}[[x]]_\beta^\alpha\rightarrow\mathbb{R}[[x]]$ be the map that has the following action for every $f\in\mathbb{R}[[x]]_\beta^\alpha$
\[(\mathcal{A}_\beta^\alpha f)(x)=\overset{\infty}{\underset{k=0}{\sum}}c_k^fx^k.\]
\end{definition}
\noindent A map of this type is called an \textit{alien derivative (operator)} in the context of resurgence theory \cite{resurgence}.
Applying this specifically to the generating series $C(x)$ of rooted connected chord diagrams,
Borinsky \cite[\S 4.6.1]{michi} showed that
\begin{align}\label{A}
\Big(\mathcal{A}_{\frac{1}{2}}^2C\Big)(x)&=\displaystyle
\frac{1+C(x)-2xC'(x)}{\sqrt{2\pi}}\;e^{-\frac{1}{2x}(2C(x)+C(x)^2)}\\
&=\frac{x}{\sqrt{2\pi}C(x)}\;e^{-\frac{1}{2x}(2C(x)+C(x)^2)}, \tag{$\dagger$}
\end{align}
where the second equality is achieved by appealing to (iii) in Lemma \ref{cd}.
Obtaining such a computable formula for $\mathcal{A}_{\frac{1}{2}}^2C$ means that we have all the coefficients for the asymptotic expansion of $C(x)$. As provided in \cite{michi1}, the first coefficients are
\begin{equation}\label{calc}
\Big(\mathcal{A}_{\frac{1}{2}}^2C\Big)(x)=\frac{1}{e\;\sqrt{2\pi}}
\Bigg(1-\frac{5}{2}x-\frac{43}{8}x^2-\frac{579}{16}x^3-\frac{44477}{128}x^4-\frac{5326191}{1280}x^5\cdots\Bigg).
\end{equation}
Translating back to $C(x)$ itself, for large $n$ this implies
\[C_n= e^{-1}\Big((2n-1)!!-\frac{5}{2}(2n-3)!!-\frac{43}{8}(2n-5)!!-\frac{579}{16}(2n-7)!!
\cdots\Big).\]
This result by Borinsky provides a full generalization for the computations in the work of Kleitman \cite{kleit}, Stein and Everett \cite{steinandeveret} and Bender and Richmond \cite{benderandrichmond}, where only the first term in the expansion was known up to now. Finally, this also tells us that the probability for a diagram on $n$ chords to be connected is
$e^{-1}(1-\frac{5}{4n})+\mathcal{O}(1/n^2)$.
Now our goal is to give combinatorial interpretations for as much as possible of the expression
\begin{equation}\label{exxx}
\frac{x}{C(x)} \exp\Big(-\frac{1}{2x}(2C(x)+C(x)^2)\Big).
\end{equation}
By (iii) in Lemma \ref{cd} we can rewrite the expression inside the exponential as $-1$ times
\begin{equation}\label{eq part}
1+\frac{1}{2x} C(x) (4x\frac{d}{dx}-1)C(x).
\end{equation}
Ignoring the 1 and the 1/2, this can be interpreted as the generating function for rooted chord diagrams with at most two connected components, counted by one less than the number of chords. Indeed, a $2x\displaystyle\frac{d}{dx}$ means distinguishing an interval. Now, except for the last one, there are two ways of using an interval: we can just place the other $C(x)$ in the interval, or we can place it and pull its root chord to the very front to become the new root. The last interval can only be used in the first way. The coefficients of the expression in \eqref{eq part}, after ignoring the 1 and the 1/2, start as $3,10,63,558,6226,82836,\ldots$, which coincide with those of the sequence \seqnum{A088221} of the OEIS: $1,2,3,10,63,558,6226,82836,\ldots$. The only definition available for the latter is in terms of another sequence: \seqnum{A000698} which interestingly counts indecomposable chord diagrams. Namely, the definition tells that (in abuse of notation!) $[x^n](\seqnum{A088221})^n=[x^{n+1}] I(x)$.
So, there has to be some bridge between chord diagrams with at most two connected components and indecomposable chord diagrams, as we shall here prove.
As mentioned earlier, the problem of finding a better combinatorial interpretation for \seqnum{A088221} lies as a piece in a more general context. We would like to more generally give combinatorial interpretations for the action described by the map $\mathcal{A}_\beta^\alpha:\mathbb{R}[[x]]_\beta^\alpha\rightarrow\mathbb{R}[[x]]$, as it is applied in the case study of Borinsky and Dunne \cite{Geraldmichi} or more generally.
Throughout the paper we use the following notation:
\begin{enumerate}
\item $\mathcal{D}$ is the class of chord diagrams,
\item $\mathcal{C}$ is the class of connected chord diagrams,
\item $\mathcal{C}^*$ is the class of connected chord diagrams excluding the one chord diagram,
\item $\mathcal{D}_{\leq2}$ is the class of chord diagrams with at most two connected components,
\item $\mathcal{I}$ is the class indecomposable chord diagrams, and finally
\item $\mathcal{I}_2$ stands for indecomposable chord diagrams with exactly two components.
\end{enumerate}
\section{The main bijection}\label{mainhere}
In this section we derive a bijection described by a reversible algorithm to move
between the class of two lists of indecomposable chord diagrams (allowing empty lists) and the class of rooted trees, in which vertices are of special type, and where a $\mathcal{D}_{\leq2}$-structure is set over the children of every vertex. Our goal by proving this is to prove that \seqnum{A088221} counts pairs of connected chord diagrams. It may be possible to get the same result algebraically, but we are interested in the combinatorial argument represented mainly in the bijection displayed below.
First we recall the decomposition of a chord diagram by means of extracting the root component (Lemma \ref{cd}-(i))\;:
\[D(x)=1+C(xD(x)^2).\]
This decomposition will be of great help in the construction presented here,
and hence it may be wise to accompany it with a suitable notation.
\begin{notation}\label{notationdangling} The two diagrams that correspond to each chord in the root component is referred to as the \textit{right dangling} and the \textit{left dangling} diagrams. Given a chord diagram $D$, the root component is denoted $C_\bullet(D)$, while the dangling diagrams are $d_r$ and $d_l$. The symbols $d_r,d_l$ and $C_\bullet$ will often be used as operators.\end{notation}
\begin{example}\label{exampledangling}
Consider the following chord diagram.
\begin{center}
\raisebox{0cm}{\includegraphics[scale=0.68]{Figures/exampledanglingdiags.eps}}
\end{center}
Let us draw it in a non-standard way
\begin{center}
\raisebox{0cm}{\includegraphics[scale=0.68]{Figures/exampledanglingdiagsdone.eps}}
\end{center}
which clarifies the decomposition of the lemma. Note that the thick red diagram is the root component $C_\bullet$ of the original diagram. Also, notice that, for example, $d_l(c_1)=\varnothing$. The reason for the nomenclature is now hopefully justified.
\end{example}
\begin{lemma}\label{bij}There is a bijection $\Phi$ between the class $\mathcal{C}^*$ of rooted connected chord diagrams excluding the one chord diagram, and the class $\mathcal{I}_2$ of indecomposable chord diagrams with exactly two components. Thus, in terms of generating functions
$\mathcal{I}_2(x)=C(x)-x$.
\end{lemma}
\begin{proof}
The bijection $\Phi$ defined here works almost the same as what is known as the {\it{root share composition}}: Let $C$ be a rooted connected chord diagram. Removing the root chord shall generally leave us with a list of rooted connected components ordered in terms of intersections with the original root. The first of these components is denoted as $C_2$, while $C_1$ is obtained by removing $C_2$ from the original diagram $C$. Then $(k,C_1,C_2)$ where $1\leq k\leq 2|C_2|-1$, is the {\it{root share decomposition}} of $C$ (see \cite{yu}). $\Phi$ is a small variant on this. $\Phi$ places the whole $C_1$ at the interval of $C_2$ where the last end of the original root of $C$ would be if the non-root chords of $C_1$ are removed. Thus, the image $\Phi(C)$ is an indecomposable chord diagram with exactly two components. This definition is reversible. Indeed, given an indecomposable chord diagram with exactly two connected components, $C_2$ is the outer component and $C_1$ should be the inner one, and $C$ is obtained by just pulling out the first end of the root of $C_1$ to the leftmost position.
\end{proof}
\begin{example}
Under the map $\Phi$, the chord diagram
\begin{center}
\raisebox{-0.1cm}{\includegraphics[scale=0.5]{Figures/rootshare.eps}}
\;\;\text{is mapped to}\;\;
\raisebox{-0.1cm}{\includegraphics[scale=0.5]{Figures/rootsharemapped.eps}},
\end{center}
where, of course, the original root (black) is no longer the root for the resulting diagram.
\end{example}
\begin{notation}
In the next theorem, given a finite set $S$ and a class $\mathcal{G}$ of combinatorial objects, the term $\mathcal{G}$-structure on $S$ means an arrangement of the elements of $S$ into an object from $\mathcal{G}$. The operation $\ast$ stands for the usual ordered product for combinatorial classes. For example, if $\mathcal{T}$ is the class of trees and $\mathcal{K}_{or}$ is the class of oriented complete graphs, then an element from the class $\mathcal{T}\ast\mathcal{K}_{or}$ is an ordered pair $(T,K)$ where $T\in\mathcal{T}$ and $K\in\mathcal{K}_{or}$. Notice that, for such a product structure to be applied on a finite set there has to be a partition of the set.
Concretely, we only need to consider the labeled situation. That is, the underlying atoms of an object $a$ is labeled by $\{1,\ldots, |a|\}$, and an element of $\mathcal{A}\ast \mathcal{B}$ is an ordered pair $(a,b)$ but where the labels of $a$ and $b$ together run over $\{1,\ldots, |a|+|b|\}$, and so in particular given labeled objects $a$ and $b$, there are $\binom{|a|+|b|}{|a|}$ ways to combine $a$ and $b$ into an element of $\mathcal{A}\ast \mathcal{B}$. This is the usual labeled product and is the special case of the more general construction where the sets that the classes are applied on are always $\{1,\ldots, n\}$ with $n$ the size of the object. In this notation, $\mathcal{X}$ stands for the (class of) single object of size 1.
In this labeled context we work with exponential generating functions, that is if $\mathcal{A}$ is a class of labeled structures then the exponential generating function is $A(x) = \sum_{a\in \mathcal{A}} x^{|a|}/|a|!$.
The reader unfamiliar with this notation from enumerative combinatorics can refer to \cite{goulden}.
\end{notation}
Note that for any class of chord diagrams the (ordinary) generating function of the class of diagrams and the exponential generating function of the labeled diagrams obtained from all labelings of the elements of the original class is the same, since all $n!$ labelings of a chord diagram on $n$ chords are distinguishable. Because of this, we can move to labeled chord diagrams in the following theorem and algorithm without changing the formal series which we obtain. The class of rooted trees we consider $\mathcal{Z}$, on the other hand, is labeled and $Z(x)$ is its exponential generating function.
\begin{theorem}\label{mainth}Let $\mathcal{Z}$ be the class of rooted trees where vertices are nonempty ordered sets and where there is a $\mathcal{D}_{\leq2}$-structure over the children of every vertex. Then there is a bijection $\Theta$ between $\mathcal{Z}$ and the class $\mathcal{X\ast(D\ast D)}$, where $\mathcal{D}$ is the class of chord diagrams. Consequently, if $Z(x)$ is the generating series for $\mathcal{Z}$, then
\begin{equation}
Z=x\left(\frac{1}{1-I_0}\right)^2,
\end{equation} where $I_0$ is the generating series for nonempty indecomposable chord diagrams.\end{theorem}
We think of the nonempty ordered sets forming the vertices of the trees as little paths inside the vertex; see Figure~\ref{thetaofP}.
\begin{proof}
Begin with a labeled object $P$ from the class $\mathcal{X\ast(D\ast D)}$. In abuse of notation we shall write $d_r(P)$ and $d_l(P)$ for the two diagrams involved. Also \textit{the chord of} $P$ means the part of $P$ coming from $\mathcal{X}$ in the decomposition. Then the corresponding $\mathcal{Z}$-tree is obtained through the following algorithm (in all cases the label of a chord becomes the label of the vertex constructed from that chord):
\noindent\rule{\textwidth}{0.4pt}
\textbf{Algorithm 1\label{alg}: Make $\mathbf{\mathcal{Z}}$-Tree}\\
\noindent\rule{\textwidth}{0.4pt}
\texttt{Input:} $P\;$=\;\raisebox{0cm}{\includegraphics[scale=0.3]{Figures/onechord.eps}}
$(d_l,d_r) \;\;$
\texttt{initially} $Q_1=P$; \setlength{\parindent}{1.3cm}
\texttt{queue} $Q=(Q_1)$;
\texttt{integer} $L=\text{length}(Q)$ (automatically modified by any alteration of $Q$);
\texttt{vertex} $v=\odot$\;;
\texttt{label}($v$)\;=\;label given to the chord of $Q_1$;
\texttt{diagrams} $D_l=D_r=\varnothing$;
\texttt{tree} $Z=v$;\\
\setlength{\parindent}{1.5em}
Set $v$ as the root vertex of $Z$\\
While $Q\neq\varnothing$ \{\\\setlength{\parindent}{1.3cm}
\begin{enumerate}
\item Set $D_l=d_l(Q_1)$ and $D_r=d_r(Q_1)$;\\
\item If $D_l=\varnothing= D_r$ then:
-- push $Q_1$ out of $Q$ (i.e., for all $1\leq k**