From order one catalytic decompositions to context-free specifications: the rewiring bijection

Enrica Duchi, Gilles Schaeffer · 2024

Read From order one catalytic decompositions to context-free specifications: the rewiring bijection by Enrica Duchi, Gilles Schaeffer (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-20628.txt.

Description

Abstract . A celebrated result of Bousquet-Mélou and Jehanne states that the bivariate power series solutions of so-called discrete differential equations , also known as polynomial equations with one catalytic variable , or simply catalytic equations , are algebraic series.

Catalog record

CREATOREnrica Duchi, Gilles Schaeffer
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-20628

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

From order one catalytic decompositions to context-free specifications: the rewiring bijection Thanks: [email protected] . ED was partially supported by ANR Projects IsOMa (Grant number ANR-21-CE48-0007) and CartesEtPlus (Grant number ANR-23-CE48-0018). Thanks: [email protected] . GS was partially supported by ANR Project 3DMaps (Grant number ANR-20-CE48-0018), LambdaComb (Grant number ANR-21-CE48-0017) and CartesEtPlus (Grant number ANR-23-CE48-0018). Enrica Duchi, Gilles Schaeffer Abstract . A celebrated result of Bousquet-Mélou and Jehanne states that the bivariate power series solutions of so-called discrete differential equations , also known as polynomial equations with one catalytic variable , or simply catalytic equations , are algebraic series. We give a purely combinatorial derivation of this result in the case of order one catalytic equations , involving only one univariate unknown series. In particular, our approach provides a tool to produce context-free specifications or bijections with simple multi-type families of trees for the derivation trees of combinatorial structures that are directly governed by an order one catalytic decomposition. This provides a simple unified framework to deal with various combinatorial interpretation problems that were solved or raised over the last 50 years since the first such catalytic equation was written by W. T. Tutte in the late 60’s to enumerate rooted planar maps. 1. Introduction 1.1. Order one catalytic equations. We are interested in a family of functional equations that have surfaced in various places in the mathematical literature since the 60s: an order one catalytic equation is an equation of the form (1) F(t,u)=t\cdot Q\left(F(t,u),\frac{1}{u}(F(t,u)-F(t,0)),u\right), with Q(v,w,u) a given series in the ring of formal power series \mathbb{Q}[[v,w,u]] and F(t,u) an unknown formal power series in \mathbb{Q}[[t,u]] . Equation ( 1 ) is a special instance of the more general family of equations with one catalytic variable thoroughly discussed in [ 4 ] , and also known as discrete differential equations as they are often written as above in terms of iterates of a divided difference operator \Delta F=\frac{1}{u}(F(t,u)-F(t,0)) in the so-called catalytic variable u . These equations have gained over the years the status of standard ingredients in enumerative combinatorics, as discussed for instance in [ 2 , 3 , 4 , 15 , 25 ] . The formal power series solutions of order one catalytic equations are particularly well understood: as discussed in [ 27 ] , it easily follows from the celebrated approach of Bousquet-Mélou and Jehanne [ 4 ] that the univariate part f\equiv f(t)=F(t,0) of the solution of Equation ( 1 ) admits generically the following simple univariate parametrization: (2) \displaystyle f\;=\;C_{\scriptstyle\square}-C_{{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}}\cdot C_{{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}},\quad\textrm{ or }\quad{\textstyle\frac{d}{dt}}f \displaystyle=(1+C_{\textstyle\bullet})\cdot Q(C_{\scriptstyle\square},C_{{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}},C_{{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}}), where C_{\scriptstyle\square}\equiv C_{\scriptstyle\square}(t) , C_{\textstyle\bullet}\equiv C_{\textstyle\bullet}(t) , C_{{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}}\equiv C_{{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}}(t) and C_{{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}}\equiv C_{{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}}(t) are the unique formal power series that satisfy the companion system \displaystyle\left\{\begin{array}[]{rclcl}{C}_{\scriptstyle\square}&=&t\cdot Q({C}_{\scriptstyle\square},{C}_{{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}},{C}_{{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}}),\\ {C}_{\textstyle\bullet}&=&t\cdot(1+{C}_{\textstyle\bullet})\cdot{Q}^{\prime}_{v}({C}_{\scriptstyle\square},{C}_{{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}},{C}_{{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}}),\\ {C}_{{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}}&=&t\cdot(1+{C}_{\textstyle\bullet})\cdot{Q}^{\prime}_{w}({C}_{\scriptstyle\square},{C}_{{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}},{C}_{{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}}),\\ {C}_{{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}}&=&t\cdot(1+{C}_{\textstyle\bullet})\cdot{Q}^{\prime}_{u}({C}_{\scriptstyle\square},{C}_{{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}},{C}_{{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}}).\end{array}\right. When Q is a polynomial, this parametrization immediately implies that f is an algebraic series: the fact that solutions of polynomial equations with one catalytic variable are algebraic series follows in fact from earlier general algebraic results ( [ 26 ] , see the discussion in [ 1 , Sec. 5.3] ), but the explicit dependency of Parametrization ( 1.1 ) in Q is remarkably appealing from a combinatorial point of view. In particular, when Q is a polynomial with non-negative integer coefficients, this parametrization shows that the series \frac{d}{dt}f is \mathbb{N} -algebraic in the sense of [ 3 ] , and since the first occurrences of catalytic equations in the literature, this fact has called for combinatorial interpretations. Elegant interpretations in terms of trees were indeed given for several special instances of these equations (see [ 18 ] and references therein, as well as the conclusion of the present article), based on remarkable ad-hoc constructions building on specific properties of the underlying combinatorial structures. The purpose of this article, as presented in the next section, is instead to give a generic combinatorial interpretation and derivation of Equations ( 2 ) and ( 1.1 ) directly starting from Equation ( 1 ). On the one hand this approach provides new insights on algebraic combinatorial generating functions as discussed by Bousquet-Mélou in [ 3 ] , and on the other hand it yields a systematic approach to build bijections with simple families of trees for combinatorial structures with order one catalytic specification. 1.2. Two combinatorial interpretations and a bijective derivation When Q(v,w,u) is a polynomial with non-negative integer coefficients, it is not difficult to give combinatorial interpretations to Equation ( 1 ) in terms of labeled trees with non-negativity conditions on labels. This was done for instance in [ 14 ] for a closely related family of equations, in terms of some description trees , or more recently in [ 8 ] for a special case of Equation ( 1 ) in terms of some fully parked trees . Under the same hypotheses on Q(v,w,u) , System ( 1.1 ) is a so-called \mathbb{N} -algebraic system , and the power series C_{\scriptstyle\square} , C_{\textstyle\bullet} , C_{{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}} and C_{{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}} admit natural interpretations as generating functions (gf) of simple varieties of multi-type trees with a context-free specification , as discussed in [ 3 ] , or [ 19 , Chapter I, ex. I.53, p82] . However there is a priori no clear relations between these first and second types of interpretations. Figure 1. From order one catalytic specifications to context-free specifications, via rewiring non-negative \mathcal{Q} -trees into \mathcal{Q} -companion trees. Our main contribution is instead to introduce two families of plane trees with vertices and edges decorated with pearls ( {\scriptstyle\square} , {{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}} , {\textstyle\bullet} , {{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}} ), that give two such interpretations that can easily be related one to the other, as illustrated by Figure 1 . The trees of the first family, called non-negative \mathcal{Q} -trees , have two types of edges ( {\textstyle\bullet}\!{\color[rgb]{0,0,0}\rule[1.5pt]{10.0pt}{1.7pt}}\!{\scriptstyle\square} edges and {\color[rgb]{1,0,0}{{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}}\!\rule[1.5pt]{10.0pt}{1.7pt}}\!{\scriptstyle\square} edges) and some free {{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}} -pearls, and they obey a non-negativity condition on the difference between the number of {{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}} -pearls and the number of {{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}} -pearls in their subtrees: as stated in Proposition 1 , these trees provide a generic interpretation of Equation ( 1 ). The trees of the second family, called rooted \mathcal{Q} -companion trees , have instead edges of type {\textstyle\bullet}\!{\color[rgb]{0,0,0}\rule[1.5pt]{10.0pt}{1.7pt}}\!{\scriptstyle\square} and {{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}}\!{\color[rgb]{0,0,1}\rule[1.5pt]{10.0pt}{1.7pt}}\!{{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}} and admit, as stated in Theorem 3 , a context-free specification that interprets System 1.1 . The relation between the two is given a simple transformation, called rewiring , that simply consists in replacing each {\color[rgb]{1,0,0}{{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}}\!\rule[1.5pt]{10.0pt}{1.7pt}}\!{\scriptstyle\square} edge by a well chosen {{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}}\!{\color[rgb]{0,0,1}\rule[1.5pt]{10.0pt}{1.7pt}}\!{{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}} edge. More precisely, as stated in Theorem 1 , rewiring yields a one-to-one mapping between non-negative \mathcal{Q} -trees and a certain subset of balanced \mathcal{Q} -companion trees. An analysis of the balance condition, summarized in Theorem 2 , shows that these balanced \mathcal{Q} -companion trees are in one-to-one correspondence with unrooted \mathcal{Q} -companion trees, while unbalanced \mathcal{Q} -companion trees can be decomposed into pairs of {{\color[rgb]{1,0,0}\scriptstyle\blacklozenge}} - and {{\color[rgb]{0,0,1}\scriptstyle\blacktriangle}} -rooted \mathcal{Q} -companion trees. In particular the latter decomposition allows us to give in Corollary 1 an interpretation of the first formula in ( 2 ). Upon marking a vertex, balanced \mathcal{Q} -companion trees can instead be decomposed into pairs of {\textstyle\bullet} - and {\scriptstyle\square} -rooted \mathcal{Q} -companion trees, and, as discussed in Corollary 2 , this yields a direct interpretation of the second Formula in (

Read the complete text