Connected Chord Diagrams and the Combinatorics of Asymptotic Expansions

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

                     ali.mahmoud@uwaterloo.ca

Karen Yeats Department of Combinatorics and Optimization University of Waterloo Waterloo, ON N2L 3G1 Canada

                       kayeats@uwaterloo.ca

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 \underline{A088221} of the On-Line Encyclopedia of Integer Sequences. We show that sequence \underline{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}.

1 Introduction

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 \underline{A088221} of the 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

∑_{n,m≥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 [17, 18, 20]. 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 [16] 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 [19]. 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 ξ = 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 [6, 5, 4, 7, 2]. 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 [2], 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.

2 Chord diagrams

(Connected) chord diagrams stand as a rich structure that becomes handy and informative in a variety of contexts, including bioinformatics [12], quantum field theory [8, 3, 2], and data structures [9], as well as in pure combinatorics [10].

Definition 1 (Rooted chord diagrams). A rooted chord diagram of size n is a matching of the set {1, …, 2n}. Each pair in the matching is a chord.

We visualize rooted chord diagrams by drawing {1, …, 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 root vertex, and the chord involving 1 is the root chord. With the root indicated, the labels {1, …, 2n} are unnecessary and so are not drawn.

Then the generating series for rooted chord diagrams is

D(x) := ∑_{n=0}^{∞}(2n − 1)!! x^{n}  (1)

Here (2n − 1)!! is the double factorial, defined by (2n − 1)!! = 1 · 3 ⋯ (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.

Figure 1: A rooted chord diagram and its linear representation.

The representation of a chord diagram with vertices in a line and chords as arcs above the line is called the linear representation of the chord diagram. A chord in the diagram may be referred to as c = {a < b}, where a and b are vertices.

Definition 2 (Intervals). In the linear representation of a rooted chord diagram, an interval is the space to the right of one of the nodes in the linear representation. Thus, a rooted diagram on n chords has 2n intervals.

Note the definition of interval includes the space to the right of the last node in the linear order.

As may be expected by now, the crossings in a chord diagram encode much of the structure and so we ought to give proper notation for them. Namely, in the linear order, two chords c_{1} = {v_{1} < v_{2}} and c_{2} = {w_{1} < w_{2}} are said to cross if v_{1} < w_{1} < v_{2} < w_{2} or w_{1} < v_{1} < w_{2} < v_{2}. Keeping track of all the crossings in the diagram leads to the following definition:

Definition 3 (The Intersection Graph). Given a (rooted) chord diagram D on n chords, consider the following graph G_{D}: the chords of the diagram serve as vertices for the new graph, and there is an edge between the two vertices c_{1} = {v_{1} < v_{2}} and c_{2} = {w_{1} < w_{2}} if v_{1} < w_{1} < v_{2} < w_{2} or w_{1} < v_{1} < w_{2} < v_{2}, i.e., if the chords cross each other. The graph so constructed is called the intersection graph of the given chord diagram.

Remark 4. A labeling for the intersection graph can be obtained as follows: give the label 1 to the root chord; order the components obtained if the root is removed according to the order of the first vertex of each of them in the linear representation, say the components are C_{1}, …, C_{n}; and then recursively label each of the components proceeding in that order. It is easily verified that a rooted chord diagram can be uniquely recovered from its labeled intersection graph.

Definition 5 (Connected Chord Diagrams). A (rooted) chord diagram is said to be connected if its intersection graph is connected in the graph-theoretic sense. A connected component of a diagram is a subset of chords which itself forms a connected chord diagram. The term root component refers to the connected component containing the root chord.

Example 6. The diagram D below is a connected chord diagram in linear representation, where the root node is drawn in black.

The generating function for connected chord diagrams (in the number of chords) is denoted by C(x). Thus C(x) = ∑_{n=0} C_{n}x^{n}, where C_{n} is the number of connected chord diagrams on n chords. The first terms of C(x) are found to be

C(x) = x + x^{2} + 4x^{3} + 27 x^{4} + 248 x^{5} + ⋯;

the reader may refer to OEIS sequence \underline{A000699} for more coefficients. The next lemma lists some classic decompositions for chord diagrams (see [10] for example), each of which can be used to obtain C(x).

Lemma 7. If D(x), C(x) are the generating series for chord diagrams and connected chord diagrams respectively, then

(i) D(x) = 1 + C(xD(x)^{2}),

(ii) D(x) = 1 + xD(x) + 2x^{2}D′(x), and

(iii) 2xC(x)C′(x) = C(x)(1 + C(x)) − x.

Proof. We sketch the underlying decompositions as follows:

(i) The ‘one’ term is for the empty chord diagram. Now, given a nonempty chord diagram, we see that for every chord in the root component there live two (potentially empty) chord diagrams to the right of its two ends. This gives the desired decomposition.

(ii) There are three situations for a root chord: it is either non-existent in the case of the empty diagram, or it is concatenated with a following diagram, or the root chord has its right end landing in one of the intervals of a diagram. These situations correspond respectively with the terms in (ii).

(iii) Can be derived from (i) and (ii). Nevertheless, it can be also shown as follows: if we remove the root chord what is left is a sequence of connected components, with each component having a special interval (through which the root used to pass) which cannot be the last interval (see the figure below). Thus each of these components is counted according to the generating function 2xC′(x) − C(x).

This decomposition gives that

C(x) = \frac{x}{1 − (2xC′(x) − C(x))},

and the result follows.

We end this section with the definition of an indecomposable chord diagram, these diagrams become a key ingredient later on.

Definition 8. A chord diagram is said to be indecomposable if, when represented linearly, it is not the concatenation of disjoint nonempty chord diagrams. The empty diagram is vacuously indecomposable by definition. The generating function for indecomposable chord diagrams is denoted here by I(x). We shall also use I_{0}(x) to denote the generating function for nonempty indecomposable chord diagrams (that is I(x) = 1 + I_{0}(x)).

Example 9. Consider the following two diagrams:

D_{1} = , and D_{2} =

Then D_{1} is indecomposable, whereas D_{2} is not since it is the concatenation of three indecomposable chord diagrams. Notice that an indecomposable chord diagram is not necessarily connected—D_{1} provides an example—but the converse is clearly true; namely, every connected diagram is indecomposable.

Sequence \underline{A000698} of the OEIS counts indecomposable chord diagrams, the first terms start as

I(x) = 1 + x + 2x^{2} + 10x^{3} + 74x^{4} + 706x^{5} + ⋯,

where I(x) is the generating series for indecomposable chord diagrams.

3 Asymptotics

We pursue a combinatorial interpretation for expressions that appear in the asymptotic expansion of C_{n}, the number of connected chord diagrams on n chords. This asymptotic expansion can be expressed as a rational function of C(x) times an exponential function in C(x). One of us, looking at initial terms, conjectured in 2018 that the part in the exponent is sequence \underline{A088221} of the OEIS. The main result presented in Section 4 proves this and gives a new combinatorial interpretation for entry \underline{A088221} of the OEIS. We show that \underline{A088221}, surprisingly, counts pairs of connected chord diagrams (allowing empty diagrams).

In [3], Borinsky studied the asymptotic behaviour of C_{n}, the number of connected chord diagrams on n chords, as an instance of his work on factorially divergent power series.

First we need a few definitions from from his work. In [2, 3], Borinsky studied sequences a_{n} whose asymptotic behaviour for large n follows a relation like

a_{n} = α^{n+β}Γ(n + β)(c_{0} + \frac{c_{1}}{α(n + β − 1)} + \frac{c_{2}}{α^{2}(n + β − 1)(n + β − 2)} + ⋯),  (2)

where α ∈ ℝ_{>0}, and β, c_{k} ∈ ℝ, and where Γ(z) = ∫_{0}^{∞} x^{z−1}e^{−x}dx for Re(z) > 0 is the gamma function.

When a_{n} has such an asymptotic expansion, then the formal power series f(x) = ∑_{n≥0} a_{n}x^{n} is, following Borinsky, said to be a factorially divergent power series and the set of all such is written ℝ[[x]]_{β}^{α}. For α > 0,the ℝ[[x]]_{β}^{α} 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

Definition 10 ([3]). For α, β ∈ ℝ, with α > 0, let A_{β}^{α} : ℝ[[x]]_{β}^{α} → ℝ[[x]] be the map that has the following action for every f ∈ ℝ[[x]]_{β}^{α}

(A_{β}^{α}f)(x) = ∞ ; ∑_{k=0}c_{k}^{f}x^{k}.

A map of this type is called an alien derivative (operator) in the context of resurgence theory [14].

Applying this specifically to the generating series C(x) of rooted connected chord diagrams, Borinsky [2, §4.6.1] showed that

(A2_{\frac{1}{2}} C)(x) = \frac{1 + C(x) − 2xC′(x)}{\sqrt{2π}} e^{− \frac{1}{2x} (2C(x)+C(x)^{2})}  (3)
= \frac{x}{\sqrt{2π}C(x)} e^{− \frac{1}{2x} (2C(x)+C(x)^{2})},  (†)

where the second equality is achieved by appealing to (iii) in Lemma 7. Obtaining such a computable formula for A2_{\frac{1}{2}} C means that we have all the coefficients for the asymptotic expansion of C(x). As provided in [3], the first coefficients are

(A2_{\frac{1}{2}} C)(x) = \frac{1}{e \sqrt{2π}} (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} ⋯). (4)

Translating back to C(x) itself, for large n this implies

C_{n} = e^{−1}((2n − 1)!! − \frac{5}{2}(2n − 3)!! − \frac{43}{8}(2n − 5)!! − \frac{579}{16}(2n − 7)!! ⋯).

This result by Borinsky provides a full generalization for the computations in the work of Kleitman [13], Stein and Everett [15] and Bender and Richmond [1], 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}) + O(1/n^{2}).

Now our goal is to give combinatorial interpretations for as much as possible of the expression

\frac{x}{C(x)} exp ( − \frac{1}{2x}(2C(x) + C(x)^{2})).  (5)

By (iii) in Lemma 7 we can rewrite the expression inside the exponential as −1 times

1 + \frac{1}{2x}C(x)(4x\frac{d}{dx} − 1)C(x).  (6)

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\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 (6), after ignoring the 1 and the 1/2, start as 3, 10, 63, 558, 6226, 82836, …, which coincide with those of the sequence \underline{A088221} of the OEIS: 1, 2, 3, 10, 63, 558, 6226, 82836, . . .. The only definition available for the latter is in terms of another sequence: \underline{A000698} which interestingly counts indecomposable chord diagrams. Namely, the definition tells that (in abuse of notation!) [x^{n}](\underline{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 \underline{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 A_{β}^{α} : ℝ[[x]]_{β}^{α} → ℝ[[x]], as it is applied in the case study of Borinsky and Dunne [16] or more generally.

Throughout the paper we use the following notation:

1. D is the class of chord diagrams,

2. C is the class of connected chord diagrams,

3. C^{∗} is the class of connected chord diagrams excluding the one chord diagram,

4. D_{≤2} is the class of chord diagrams with at most two connected components,

5. I is the class indecomposable chord diagrams, and finally

6. I_{2} stands for indecomposable chord diagrams with exactly two components.

4 The main bijection

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 D_{≤2}-structure is set over the children of every vertex. Our goal by proving this is to prove that \underline{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 7-(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. Notation 11. The two diagrams that correspond to each chord in the root component is referred to as the right dangling and the left dangling diagrams. Given a chord diagram D, the root component is denoted C_{•}(D), while the dangling diagrams are d_{r} and d_{l}. The symbols d_{r}, d_{l} and C_{•} will often be used as operators.

Example 12. Consider the following chord diagram.

Let us draw it in a non-standard way which clarifies the decomposition of the lemma. Note that the thick red diagram is the root component C_{•} of the original diagram. Also, notice that, for example, d_{l}(c_{1}) = ∅. The reason for the nomenclature is now hopefully justified.

Lemma 13. There is a bijection Φ between the class C^{∗} of rooted connected chord diagrams excluding the one chord diagram, and the class I_{2} of indecomposable chord diagrams with exactly two components. Thus, in terms of generating functions I_{2}(x) = C(x) − x.

Proof. The bijection Φ defined here works almost the same as what is known as the 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 ≤ k ≤ 2|C_{2}| − 1, is the root share decomposition of C (see [6]). Φ is a small variant on this. Φ 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 Φ(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.

Example 14. Under the map Φ, the chord diagram

is mapped to ,

where, of course, the original root (black) is no longer the root for the resulting diagram.

Notation 15. In the next theorem, given a finite set S and a class G of combinatorial objects, the term G-structure on S means an arrangement of the elements of S into an object from G. The operation ∗ stands for the usual ordered product for combinatorial classes. For example, if T is the class of trees and K_{or} is the class of oriented complete graphs, then an element from the class T ∗ K_{or} is an ordered pair (T, K) where T ∈ T and K ∈ 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, …, |a|}, and an element of A ∗ B is an ordered pair (a, b) but where the labels of a and b together run over {1, …, |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 A ∗ 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, …, n} with n the size of the object. In this notation, X stands for the (class of) single object of size 1.

In this labeled context we work with exponential generating functions, that is if A is a class of labeled structures then the exponential generating function is A(x) = ∑_{a∈A} x^{|a|}/|a|!.

The reader unfamiliar with this notation from enumerative combinatorics can refer to [11].

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 Z, on the other hand, is labeled and Z(x) is its exponential generating function.

Theorem 16. Let Z be the class of rooted trees where vertices are nonempty ordered sets and where there is a D_{≤2}-structure over the children of every vertex. Then there is a bijection Θ between Z and the class X ∗ (D ∗ D), where D is the class of chord diagrams. Consequently, if Z(x) is the generating series for Z, then

Z = x (\frac{1}{1 − I_{0}} )^{2} ,  (7)

where I_{0} is the generating series for nonempty indecomposable chord diagrams.

We think of the nonempty ordered sets forming the vertices of the trees as little paths inside the vertex; see Figure 2.

Proof. Begin with a labeled object P from the class X ∗ (D ∗ D). In abuse of notation we shall write d_{r}(P) and d_{l}(P) for the two diagrams involved. Also the chord of P means the part of P coming from X in the decomposition. Then the corresponding 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):

Algorithm 1: Make Z-Tree

Input: P = (d_{l}, d_{r})

   initially Q_{1} = P;

queue Q = (Q_{1});

integer L = length(Q) (automatically modified by any alteration of Q);

      vertex v = ⊙ ;

label(v) = label given to the chord of Q_{1};

      diagrams D_{l} = D_{r} = ∅;
      tree Z = v;

Set v as the root vertex of Z While Q ≠ ∅ {

1. Set D_{l} = d_{l}(Q_{1}) and D_{r} = d_{r}(Q_{1}); 2. If D_{l} = ∅ = D_{r} then:

– push Q_{1} out of Q (i.e., for all 1 ≤ k < L, Q_{k} ← Q_{k+1} );

– Go to step (1) again.

3. If D_{l} = ∅ and D_{r} ≠ ∅ then: – Create |C_{•}(D_{r})| children attached to v, and set their labels to be the same as the chords in C_{•}(D_{r}). Namely, let {w_{1}, …, w_{|C_{•}(D_{r})|}} be the children and set label(w_{i})=label(i^{th} chord) in the obvious meaning;

– For each i ∈ {1, …, |C_{•}(D_{r})|} add Q_{L+i} to the queue Q, where Q_{L+i}:= (d_{l}(i^{th} chord), d_{r}(i^{th} chord)), where the single chord stands for the i^{th} chord in C_{•}(D_{r}) and the d_{l}, d_{r} are the dangling diagrams of this chord in D_{r};

– Set C_{•}(D_{r}) as the D_{≤2}-structure over the children of v;

– Push Q_{1} out of Q;

– Set v = vertex for the chord of Q_{1} (where Q_{1} has been updated);

– Go to step (1);

4. If D_{l} ≠ ∅ and D_{r} ≠ ∅ then: – Create |C_{•}(D_{l})| + |C_{•}(D_{r})| children attached to v, and set their labels to be the same as the corresponding chords, as before;

– For each i ∈ {1, …, |C_{•}(D_{l})| + |C_{•}(D_{r})|} add Q_{L+i} to the queue Q, where Q_{L+i}:= (d_{l}(i^{th} chord), d_{r}(i^{th} chord)), where the single chord stands for the i^{th} chord in C_{•}(D_{l}) if 1 ≤ i ≤ |C_{•}(D_{l})| and for the (i − |C_{•}(D_{l})|)^{th} chord in C_{•}(D_{r}) otherwise;

– Set the concatenation C_{•}(D_{l})C_{•}(D_{r}) as the D_{≤2}-structure over the children of v;

– Push Q_{1} out of Q;

– Set v = vertex for the chord of Q_{1};

– Go to step (1);

5. If D_{l} ≠ ∅ and D_{r} = ∅ then:

(a) In case C_{•}(D_{l}) is a single chord c then: – vertex v absorbs another node with the label given to c. It is appropriate to think of a vertex here as some sort of stack comprising labeled nodes:

– Add Q_{L+1} to Q, where Q_{L+1} consists of c and its dangling diagrams, i.e., d_{l}(Q_{L+1}) = d_{l}(c) and d_{r}(Q_{L+1}) = d_{r}(c);

– Push Q_{1} out of Q;

– Set v = vertex for the chord of Q_{1};

– Go to step (1);

(b) Otherwise if C_{•}(D_{l}) is not a single chord then: – Create |C_{•}(D_{l})| children attached to v, and set their labels to be the same as the corresponding chords, as before;

– For each i ∈ {1, …, |C_{•}(D_{l})|} add Q_{L+i} to the queue Q, where Q_{L+i}:= (d_{l}(i^{th} chord), d_{r}(i^{th} chord)), where the single chord stands for the i^{th} chord in C_{•}(D_{l});

– Set Φ(C_{•}(D_{l})) as the D_{≤2}-structure over the children of v;

– Push Q_{1} out of Q;

– Set v = vertex for the chord of Q_{1};

– Go to step (1); }

Output: Θ(P) = Z.

This algorithm uniquely generates the corresponding tree. Indeed, to see this it shall be enough to see that every branching from a vertex is uniquely translated into chord diagrams:

1. If the D_{≤2}-structure over the children is the concatenation of two connected components, then we know simply that there were nonempty right and left dangling diagrams for the chord corresponding to the vertex. Further, the two connected components are, respectively, the root components of the dangling diagrams. The order of components in the (rooted) D_{≤2}-structure dictates which component is for the left or right dangling diagram.

2. If the D_{≤2}-structure is just a connected chord diagram, then for the chord corresponding to the vertex only the right dangling diagram was nonempty. In particular, this connected structure is the root component for the right dangling diagram.

3. If the D_{≤2}-structure is an indecomposable chord diagram with exactly two connected components, then we learn that for the corresponding chord only the left dangling diagram was nonempty. The root component of which is determined by applying Φ^{−1} to the D_{≤2}-structure. This process is well-defined by virtue of Φ being a bijection.

4. The only remaining case is when the vertex itself is a stack. This marks that, as in the previous case, only the left dangling diagram was nonempty for the chord corresponding to the vertex, and that, further, the root component for this dangling diagram was a single chord with the label given next in the stack. Uniqueness in this case is clear as the information is encoded into the tree in a way that does not interfere with the previous cases, hence no ambiguity arises.

This outlines that the above algorithm is reversible, and hence establishes the desired bijection. To prove the second part of the theorem notice that any rooted chord diagram can be viewed as a (possibly empty) list of nonempty indecomposable chord diagrams.

Example 17. Let P ∈ X ∗ (D ∗ D) be given by P = (d_{l}(P), d_{r}(P)), where

d_{r}(P) = and

d_{l}(P) = .

The first iterations in the algorithm are as follows:

[1] Initially: Q_{1} = P, Q = (Q_{1}), L = 1,

Z = .

[2] D_{l} ≠ ∅ and D_{r} ≠ ∅, so we attach the children as of

Z =  with the D_{≤2}-structure  . The

updated queue becomes (after including the new entries and pushing the old Q_{1} out of Q):

Q = (Q_{1} =  ,  ,  ,  ,  )

and then the vertex v is set to be 11.

[3] In this iteration we find that D_{l} ≠ ∅, whereas D_{r} = ∅; moreover, C_{•}(D_{l}) is the single chord labeled ‘20’. Thus, following the algorithm, one more node is appended to the vertex v which, before this moment, only contained the node labeled 11. Thus, vertex v is now

given by . Then we add the entry Q_{6} =  (  , ∅) to the queue Q (from

the end); update Q by pushing out Q_{1}; and set the vertex v to be at chord ‘1’, since it is the chord of the new Q_{1}.

Following the algorithm to the end we generate the tree Θ(P) to be as in Figure 2 below, where the right column displays the D_{≤2}-structures pertinent to the children of each vertex (recall that vertices here are generally stacks of nodes). For clarity, structures are displayed level-wise.

Corollary 18. Let I_{0}(x) be the generating series for nonempty indecomposable chord diagrams as before, and set B(x) = D_{≤2}(x) + x, where D_{≤2}(x) is the generating function for the class D_{≤2}. Then

I_{0}(x) = \frac{x}{1 − xB′(Z)},

where Z is the generating series for the class Z as before.

Before proving Corollary 18 we give a decomposition of indecomposable diagrams:

Lemma 19. The generating series I_{0} for nonempty indecomposable chord diagrams satisfies the relation

I_{0}(x) = x + \frac{2x^{2}I′_{0}(x)}{1 − I_{0}(x)} .

Proof. Given a nonempty indecomposable chord diagram we can argue as follows. If the diagram is not a single chord, then removing the root chord generally leaves us with a list of nonempty indecomposable chord diagrams. Moreover, the last diagram in this list carries all the information about the removed root chord, encoded as a marked interval that used to carry the right end of the root chord. Recall that the intervals are the spaces to the right of every chord end in the linear representation, including the last space to the right of the diagram. Thus we have 2m intervals in a diagram with m chords. The relation in the lemma is exactly the translation of this decomposition into the world of generating series.

Figure 2: Θ(P), with D_{≤2}-structures displayed by level on the right.

Example 20. In the following diagram, the diagram is decomposed into: the root, D_{1}, D_{2}, and (D_{3}, interval 4), where, among the 8 intervals in D_{3}, the root originally landed in interval 4 (marked by a red dotted line).

Proof of Corollary 18: First of all, notice that by the definition of the class Z, the generating series Z satisfies the recursion

Z(x) = xD_{≤2}(Z) + xZ = xB(Z),

where B(t) = D_{≤2}(t) + t. Thus Z′(x) = B(Z) + xB′(Z)Z′ = \frac{Z}{x} + xB′(Z)Z′, and hence

Z = xZ′(1 − xB′(Z)).

By Theorem 16, we have that Z = x(\frac{1}{1 − I_{0}} )^{2}. Taking the logarithmic derivative of both

sides and making use of the above identities we get

1 + 2x\frac{d}{dx} log (\frac{1}{1 − I_{0}} ) = x\frac{d}{dx} log Z = x\frac{Z′}{Z} = \frac{1}{1 − xB′(Z)},

and hence

\frac{1}{1 − xB′(Z)} = 1 + \frac{2xI′_{0}}{(1 − I_{0})} .

Multiplying by x we get that, by Lemma 19, \frac{x}{1 − xB′(Z)} = x + \frac{2x^{2}I′_{0}}{(1 − I_{0})} = I_{0}, which

completes the proof.

Corollary 21. Let A(X) be the generating series for the sequence \underline{A088221}. Then

A(x) = D_{≤2}(x) + x.

Proof. By Lagrange inversion^{1}, we know that

[x^{n}]\frac{1}{1 − xB′(Z)} = [x^{n}]B^{n}(x).

Now, by the definition of the sequence \underline{A088221}, we know that it is the sequence for which [x^{n}]A^{n}(x) = [x^{n+1}]I_{0}(x), where A(x) is assumed to be the generating series for the sequence \underline{A088221}. This gives

[x^{n}]A^{n}(x) = [x^{n+1}]I_{0}(x) = [x^{n+1}]\frac{x}{1 − xB′(Z)} = [x^{n}]\frac{1}{1 − xB′(Z)} = [x^{n}]B^{n}(x),

and so A(x) = B(x) = D_{≤2}(x) + x.

1Lagrange inversion, also known as the Lagrange implicit function theorem, can be found in many standard enumeration references. See for example [11]. Briefly, in the form that we will use it, Lagrange inversion says that if Z(x) = xB(Z(x)) then [x^{n}]Z(x) = \frac{1}{n}[x^{n−1}]B(x)^{n}.

Proposition 22. The n^{th}entry in the sequence \underline{A088221} counts the number of pairs (C_{1}, C_{2}) of connected chord diagrams (allowing empty diagrams) with total number of chords being n.

Proof. Indeed, any chord diagram with at most two connected components is either: (1) empty, (2) connected, (3) concatenation of two connected diagrams, (4) or is indecomposable with exactly two connected components. By using Lemma 13 for the last case we thus get

A(x) = D_{≤2}(x) + x = 1 + C(x) + C^{2}(x) + C(x) − x + x = (C(x) + 1)^{2},

and the result is established.

5 Discussion

The bijections above are interesting in their own right, but for us, they are most interesting as a small first step towards giving a combinatorial interpretation of the analysis of Borinsky and Dunne [16], and ultimately more generally of such resurgence setups. To this end, let us further discuss the situation of Borinsky and Dunne.

They work with the transseries Ansatz [16, Eq. (20)]

C(x) = ∑_{k=0}^{∞} σ^{k}C^{(k)}(x),

where σ is an instanton parameter (as it turns out, it comes along with the same power of e^{−1/2x}/\sqrt{x}, giving a transseries in the simplified form mentioned in the introduction). In the expansion of Borinsky and Dunne, C^{(0)}(x) is what we have called C(x) in this paper, the generating series for connected chord diagrams. C^{(0)}(x) is also a scaled version of the perturbative solution to the Dyson-Schwinger equation in Yukawa theory that Broadhurst and Kreimer solved in [19]. The C(x) of Borinsky and Dunne is required to satisfy the same differential equation as the generating series for the connected chord diagrams, namely Lemma 7 (iii). Taking the coefficient of σ^{0} we see that C^{(0)}(x) must satisfy the same differential equation and so must be exactly the generating series for connected chord diagrams.

They next derive, using the differential equation, the expression for C^{(1)} whose exponential part we have been studying in this paper.

C^{(1)}(x) = (\frac{e^{−1/2x}}{\sqrt{x}} ) (A2_{\frac{1}{2}} C^{(0)}) (x)

= (\frac{e^{−1/2x}}{\sqrt{x}} ) (\frac{x}{\sqrt{2π}C^{(0)}(x)}) e^{− \frac{(C^{(0)}(x)(C^{(0)}(x)+2)}{2x}}

= ξ \frac{1}{e \sqrt{2π}} (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} − ⋯),

where ξ = e^{−1/2x}/\sqrt{x}.

In fact, their methods make it possible to give expressions for all the C^{(j)}(x) in terms of C^{(0)}(x) and derivatives of an explicit bivariate function they call f(x, y) (see [16, Eq. (38)]). Expanding the first few of these expressions one obtains

C^{(2)}(x) = ξ^{2} \frac{1}{2πe^{2}} (−\frac{1}{x} + 5 + \frac{11}{2}x + \frac{97}{2}x^{2} + \frac{4173}{8}x^{3} + \frac{268051}{40}x^{4} + ⋯)
C^{(3)}(x) = ξ^{3} \frac{1}{(2π)^{3/2}e^{3}} (\frac{3}{2x^{2}} − \frac{47}{4x} + \frac{67}{16} − \frac{2157}{32}x − \frac{211199}{256}x^{2} − \frac{29245909}{2560}x^{3} + ⋯) .

Borinsky and Dunne also consider expanding C(x) = ∑_{k=0}^{∞} σ^{k}C^{(k)}(x) in terms of x with the coefficients series in σξ. They write [16, Eq. (39)]

C(x) = x ∑_{n=0}^{∞} x^{n}F_{n}(ρ),

where ρ = σξ/x. Then they find that the same differential equation gives that F_{0}(ρ) = 1 + W (ρ) where W is the Lambert W function. The Lambert W function is defined by the identity W (ρ)e^{W (ρ)} = ρ. From an enumerative perspective it is a standard fact that the Lambert W function gives the exponential generating series for nonempty labeled rooted trees. Specifically letting R(z) be the exponential generating series of labeled rooted trees we have R(z) = ze^{R(z)} since a nonempty rooted tree is a root and a forest of subtrees. Rearranging we have R(z)e^{−R(z)} = z and so R(z) = −W (−z). This means that F_{0} is the exponential generating series of labeled rooted trees, allowing an empty tree, and with a sign of (−1)^{|t|−1} for a tree t with |t| vertices. That is, F_{0}(ρ) = 1 − R(−ρ).

Borinsky and Dunne were well aware of this connection to rooted trees [21]. It makes the question of an overall combinatorial interpretation all the more tantalizing, for what we have is a square

F_{0}(ρ) F_{1}(ρ) F_{2}(ρ) F_{3}(ρ) ⋯
C^{(0)}(x) \frac{1}{x}  1  1  4  27 ⋯
C^{(1)}(x) \frac{e\sqrt{2π}}{ξ}  1  −\frac{5}{2} −\frac{43}{8} −\frac{579}{16} ⋯
C^{(2)}(x) \frac{xe^{2}2π}{ξ^{2}}  −1  5  \frac{11}{2}  \frac{97}{2} ⋯
C^{(3)}(x) \frac{x^{2}e^{3}(2π)^{3/2}}{ξ^{2}}  \frac{3}{2}  −\frac{47}{4}  \frac{67}{16} −\frac{2157}{32} ⋯
⋮  ⋮  ⋮  ⋮  ⋮ ...

where the first row and first column both have classical combinatorial interpretations: the ordinary generating series of rooted connected chord diagrams and the exponential generating series of labeled rooted trees, respectively. For the second row, we have taken a small step, giving a combinatorial interpretation for part of what goes into that series.

We would like to understand this whole square combinatorially, namely to find some combinatorial objects counted with respect to two parameters, where setting one parameter to 0 gives rooted trees and setting the other parameter to 0 gives connected chord diagrams, and a bivariate count gives the square above. One reason to doubt the possibility of this is the signs, which do not follow an obvious pattern. The principal difficulty we encountered also comes from signs, though in this case from internal signs. Borinsky and Dunne found equations for all these series in terms of C^{(0)} and the Lambert W. If these equations involved only positive coefficients then by standard methods all the operations would immediately be interpretable combinatorially and the problem would be trivial. However, the expressions do involve signs, and so giving an interpretation becomes a challenging task of giving sufficiently nice interpretations of the pieces that cancellations coming from sign differences can be understood as explicit set subtractions. In general there is no reason to expect this to be possible, but we remain hopeful that in structured circumstances like this one, with sufficient cleverness, a fully combinatorial explanation will be possible.

6 Acknowledgments

KY and AM would like to thank Gerald Dunne, Michi Borinsky, and Dirk Kreimer for useful discussions. KY is supported by an NSERC Discovery grant and by the Canada Research Chair program. During some of this work KY was supported by a Humboldt fellowship and thanks Dirk Kreimer for hosting her Humboldt visit to Berlin. AM would like to thank KY for initiating the research in this problem and for her continuous support.

References

[1] E. Bender and L. Richmond, An asymptotic expansion for the coefficients of some power series II: Lagrange inversion, Discrete Math. 50 (1984), 135–141.

[2] M. Borinsky, Graphs in perturbation theory: Algebraic structure and asymptotics, arXiv preprint arXiv:1807.02046, 2018. Available at https://arxiv.org/abs/1807.

    02046.

[3] M. Borinsky, Generating asymptotics for factorially divergent sequences, Electron. J. Combin. 25 (2018), #P4.1.

[4] J. Courtiel, K. Yeats, and N. Zeilberger, Connected chord diagrams and bridgeless maps, Electron. J. Combin. 26 (2019), #P4.37.

[5] J. Courtiel and K. Yeats, Terminal Chords in Connected Chord Diagrams, Ann. Inst. Henri Poincaré Comb. Phys. Interact. 4 (2017), 417–452.

[6] N. Marie and K. Yeats, A chord diagram expansion coming from some Dyson-Schwinger equations, Commun. Number Theory Phys. 7 (2013), 251–291.

[7] M. Hihn and K. Yeats, Generalized chord diagram expansions of Dyson-Schwinger equations, Ann. Inst. Henri Poincaré Comb. Phys. Interact. 6 (2019), 573–605.

[8] K. Yeats, A Combinatorial Perspective on Quantum Field Theory, Springer, 2017.

[9] P. Flajolet, J. Françon, and J. Vuillemin, Sequence of operations analysis for dynamic data structures, J. Algorithms 1 (1980), 111–141.

[10] P. Flajolet and M. Noy, Analytic combinatorics of chord diagrams, in Formal Power Series and Algebraic Combinatorics, 12th International Conference, FPSAC’00, Springer, 2000, pp. 191–201.

[11] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley & Sons, 1983.

[12] I. Hofacker, P. Schuster, and P. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math. 88 (1998), 207–237.

[13] D. Kleitman, Proportions of irreducible diagrams, Stud. Appl. Math. 49 (1970), 297– 299.

[14] C. Mitschi and D. Sauzin, Divergent Series, Summability and Resurgence I, Springer, 2016.

[15] P. Stein and C. Everett, On a class of linked diagrams II. Asymptotics, Discrete Math. 21 (1978), 309–318.

[16] M. Borinsky and G. V. Dunne, Non-perturbative completion of Hopf-algebraic Dyson-Schwinger equations, Nuclear Phys. B 957 (2020), 115096.

[17] J. Bersini, A. Maiezza, and J. Carlos Vasquez, Resurgence of the renormalization group equation, Ann. Physics 415 (2020), 168126.

[18] G. V. Dunne and M. Unsal, New nonperturbative methods in quantum field theory: From large-N orbifold equivalence to bions and resurgence, Ann. Rev. Nucl. Part. Sci. 66 (2016), 245–272.

[19] D. J. Broadhurst and D. Kreimer, Exact solutions of Dyson-Schwinger equations for iterated one-loop integrals and propagator-coupling duality, Nucl. Phys. B 600 (2001), 403–422.

[20] M. Bellon and P. Clavier, Alien calculus and a Schwinger-Dyson equation: two-point function with a nonperturbative mass scale, Lett. Math. Phys. 108 (2018), 391–412.

[21] M. Borinsky and G. Dunne, Personal communication, (2018).

2020 Mathematics Subject Classification: Primary 05A19; Secondary 05A15, 05A16, 81T99. Keywords: chord diagram, connected chord diagram, asymptotic expansion.

(Concerned with sequences \underline{A000698}, \underline{A000699}, and \underline{A088221}.)

Received April 3 2021; revised versions received August 23 2022; September 13 2022. Published in Journal of Integer Sequences, September 15 2022.

Return to Journal of Integer Sequences home page.