# On an algebraicity theorem of Kontsevich

Christophe Reutenauer and Marco Robado

Laboratoire de Combinatoire et d'Informatique Mathématique, Université du Québec à Montréal, Canada

**Abstract.** We give in a particular case a combinatorial proof of a recent algebraicity result of Kontsevich; the proof uses generalized one-sided and two-sided Dyck words, or equivalently, excursions and bridges. We indicate a non-commutative version of these notions, which could lead to a full proof. We show also a relation with pointed planar maps.

**Résumé.** Nous donnons, dans un cas particulier, une preuve combinatoire d'un résultat récent d'algébricité de Kontsevich; la preuve utilise des mots de Dyck généralisés d'un coté et deux cotés ou de façon équivalente, excursions et ponts. Nous indiquons une version non-commutative de ces notions, qui pourrait conduire à une preuve complète. Nous montrons aussi une relation avec des cartes planaires pointées.

**Keywords:** Algebraic series, Dyck words, noncommutative, planar maps.

## 1 Introduction: theorem of Kontsevich

Giving conditions for the algebraicity of formal power series is a classical problem in Mathematics. We may quote for example: Fürstenberg's theorem on the diagonal of a bivariate rational function; Grothendieck's p-curvature conjecture; the theorem of Chomsky and Schützenberger on the generating function of a context-free language. In this spirit, one has also the following result.

**Theorem 1 (Kontsevich [7])** Let $a \in \mathbb{C}[F(X)]$ be an element of the $\mathbb{C}$-algebra of the free group $F(X)$. Let $a_n$ be the constant term of $a^n$. Then the series

$$P_a = \exp\left(\sum_{n \ge 1} a_n \frac{t^n}{n}\right) \qquad (1)$$

is algebraic.

Note that Kontsevich actually defines the series $P_a$ as

$$P'_a = \exp\left(-\sum_{n \ge 1} a_n \frac{t^n}{n}\right) \qquad (2)$$

That is to say, $P_a = 1/P'_a$. Motivation of the definition in Eq. (2) comes evidently (as suggested by Kontsevich's notation, "Tr"($a$) = constant term of $a$) from the well-known identity giving the reciprocal of the characteristic polynomial of a square matrix $a$: $det(1 - ta) = \exp(\sum_{n \ge 1} tr(a^n)t^n/n)$.
The proof of Kontsevich uses a theorem of Chomsky-Schützenberger (to prove that $F_a = \sum_{n \ge 1} a_n t^n$ is algebraic, see also [8, 9, 5]), and a result of Chudnovsky-Chudnovsky which is a special case of a yet unsolved, 40 years old, conjecture of Grothendieck.

For the special case of the free group on one generator, Kontsevich states that the theorem follows easily from the residue formula. Note that it is also an easy consequence of theorem 1 of [1]. Both of these methods are analytic.

The first aim of this paper is to give a combinatorial proof of this special case. This is done quickly in Sections 2 and 3 by using a bijection between pointed bridges (that is, two-sided Dyck words where some minimum is pointed) and pointed excursions (that is, restricted Dyck words where some step is pointed); see Figure 1.

In Section 4, we show that one may generalize the construction of bridges and excursions as follows: one takes some free group with a total group ordering; then one defines bridges as the set of words in the generators and their inverses whose product in the free group is 1, which is a well-known unambiguous algebraic (or context-free) language, see [2]; then we define another language, which seems not to have been considered previously: the set of bridges such that each prefix, when evaluated in the free group, is positive (that is, > the neutral element); those words are the generalized excursions. The generalized bijection (see Lemma 2) then shows that if $a_n$ is the number of bridges of length $n$, then the generating series of excursions is the right-hand side of Eq.(1). Unfortunately, we are unable to prove that the language of generalized excursions is an algebraic language; actually, according to an unpublished manuscript of Mireille Bousquet-Melou and Gilles Schaeffer $^{(i)}$, this language is not algebraic, since its generating series is not $\mathbb{N}$-algebraic, at least for the free group on two generators (and likely for more generators): indeed, as shown in Section 5, the series in this case is the generating series of pointed planar maps (i.e. and edge is pointed), which is not $\mathbb{N}$ algebraic (loc. cit.).

However, the construction shows that the generating series of generalized excursions on the free group does not depend on the chosen group ordering, a result which seems not immediately evident, and that it is algebraic; of course, for the latter result, we use Kontsevich's theorem, which is just the contrary of our initial motivation. It remains to find an argument to prove directly its algebraicity, which would give another proof of Kontsevich's theorem.

Another open question is to find a natural bijection between pointed planar maps with $n$ edges and generalized excursions of length $2n$ on the free group with 2 generators. Equivalently, to prove bijectively that the logarithmic derivative of the generating series (with the variable squared) of pointed planar maps, multiplied by the variable, is equal to the generating series of the bridges in the free group with two generators (two-sided Dyck words on two letters and their inverses); see Eq.(4). These bijections surely exist, since the corresponding generating series are equal, see Section 5 on pointed planar maps.

**Acknowledgments** The authors gratefully thank Guillaume Chapuy for indicating to them Proposition 1, which is the combinatorial key to proving that the logarithmic derivative (multiplied by the variable) of the enumerating series of excursions is the enumerating series of bridges.

<footnote>(i) Singularities of $\mathbb{R}_+$-algebraic series, 2006</footnote>
## 2 Bridges and excursions

A finite sequence of integers, $m = (m_1, \dots, m_n)$, is viewed as a *path* in the discrete plane $\mathbb{Z} \times \mathbb{Z}$ considering the sequence of points

$$((0,0), (1, m_1), (2, m_1 + m_2), \dots, (n, \sum_{i=1}^{n} m_i)).$$

The values $m_i$ are then called the *steps* of the path $m$ and $n$ is its *length*. The *height* of a path is the sum of its steps and the height of the empty path is defined to be 0. Also, given two paths, $m, m'$ define their concatenation in the obvious way, by concatenating them as words.

A path is said to be a *bridge* if its height is 0. A *minimum* of a bridge is one of its *proper prefixes* of minimal height. A bridge of length $n$ has then at most $n$ minima as the bridge itself is never considered a minimum. The set of all bridges of length $n$ with $k$ minimum is denoted by $B_{n,k}$ and the set of all bridges of length $n$ simply $B_n$. A *pointed bridge* is a bridge with one distinguished minima. Note that there are $k|B_{n,k}|$ pointed bridges of length $n$ with $k$ minimum.

A bridge is called an *excursion* if the height of any of its minima is non-negative. The set of excursions of length $n$ with $k$ minima is written $\mathcal{E}_{n,k}$. A *pointed excursion* is an excursion with a distinguished proper prefix. Notice that there are $n|\mathcal{E}_{n,k}|$ pointed excursions of length $n$ and $k$ minima.

The following result seems to be well-known.

**Proposition 1** Let $n, k \in \mathbb{N}$ be two integers. There is a bijection between pointed bridges and pointed excursions of length $n$ with $k$ minima.

**Proof:** See Figure 1 for an example of the bijection. $\square$

<figure><img src="image_1.png" /><figcaption>Fig. 1: Bijection between a pointed excursion (on top) and a pointed bridge.</figcaption></figure>
## 3 Power series

Let {$x_i$ | $i \in \mathbb{Z}$} be a set of commuting variables. The weight of a path $m = (m_1, \dots, m_n)$ is the monomial $w(m) = x_{m_1} \cdots x_{m_n}$. For integers $n, k \in \mathbb{N}$, define the following elements in $\mathbb{C}[x_i | i \in \mathbb{Z}]$:

$$b_{n,k} = \sum_{b \in \mathcal{B}_{n,k}} w(b), \quad b_n = \sum_k b_{n,k}$$

$$e_{n,k} = \sum_{e \in \mathcal{E}_{n,k}} w(e), \quad e_n = \sum_k e_{n,k}.$$

The following identity follows easily by noticing that the bijection of Proposition 1 preserves weights.

**Corollary 1** Let $n, k \in \mathbb{N}$ be two integers. Then,

$$ne_{n,k} = kb_{n,k}.$$

□

An excursion is said to be simple if it has exactly one minimum. The set of simple excursions of length $n$ noted $S_n$ is then equal to $\mathcal{E}_{n,1}$. Notice that the set of excursions forms a monoid (for concatenation) which is free over the set of simple excursions. The length of an excursion in this monoid is then its number of minima.

Define the formal power series

$$S(t) = \sum_{n \ge 0} s_n t^n, \quad E(t) = \sum_{n \ge 0} e_n t^n \quad \in \mathbb{C}[x_i | i \in \mathbb{Z}][[t]]$$

where $s_n = \sum_{s \in S_n} w(s)$. For a fixed number of minima, $k \in \mathbb{N}$, we have the following identity:

$$\sum_{n \ge 0} e_{n,k} t^n = S(t)^k, \qquad (3)$$

it follows that

$$\sum_n \sum_k e_{n,k} t^n = \sum_{k \ge 0} S(t)^k = \frac{1}{1 - S(t)}.$$

The following identity is pivotal to proving the main theorem:

**Lemma 1**

$$\frac{t(E(t))'}{E(t)} = \sum_{n \ge 1} b_n t^n$$

**Proof:** From corollary 1, it follows that

$$\sum_{k \ge 1} \frac{1}{k} \sum_{n \ge 1} e_{n,k} t^n = \sum_{n \ge 1} b_n \frac{t^n}{n}.$$

Using (3), we get

$$\sum_{k \ge 1} \frac{S(t)^k}{k} = \sum_{n \ge 1} b_n \frac{t^n}{n}.$$
And then,

$$t \frac{d}{dt} \left( \sum_{k \ge 1} \frac{S(t)^k}{k} \right) = t \frac{d}{dt} \left( \sum_{n \ge 1} b_n \frac{t^n}{n} \right) = \sum_{n \ge 1} b_n t^n.$$

Moreover, the equality

$$t \frac{d}{dt} \left( \sum_{k \ge 1} \frac{S(t)^k}{k} \right) = \frac{t(E(t))'}{E(t)}$$

is easily checked.

□

**Proof:** (Kontsevich's theorem $n = 1$)

Let $a \in \mathbb{C}[x, x^{-1}]$ be a Laurent polynomial and let $a_n$ be the constant term of $a^n$. Consider the series

$$P_a = \exp\left(\sum_{n \ge 1} a_n \frac{t^n}{n}\right) = \sum_{n \ge 0} p_n t^n, \quad Q_a = \sum_{n \ge 1} a_n t^n.$$

It is well known that the series $P_a$ is uniquely determined by the the equation

$$t \frac{P_a'}{P_a} = Q_a.$$

In particular, if $Q_a = \sum_{n \ge 1} b_n t^n$, then $P_a = E(t)$. Moreover, the set of all excursions forms a language which is algebraic (context-free) and deterministic; indeed, it is recognised by a deterministic 1-counter stack automaton. Hence it is unambiguous and therefore, by a theorem of Chomsky and Schützenberger [3], the series $E(t)$ is algebraic (see also [8] and [9]).

Now, it can be seen that the constant term of $a^n$ is the polynomial $b_n$ with the coefficient of $x^i$ in $a$ substituted for $x_i$. We then have that $P_a = E(t)$, hence it is algebraic. □

# 4 The case $a = x_1 + \cdots + x_k + x_1^{-1} + \cdots + x_k^{-1}$

Let $X = \{x_1, \dots, x_n\}$ be an alphabet and let $\bar{X} = \{\bar{x}_1, \dots, \bar{x}_n\}$ be disjoint from $X$. Define a morphism of monoids from the free monoid $(X \cup \bar{X})^*$ to the free group $F(X)$, $\pi: (X \cup \bar{X})^* \to F(X)$, by $\pi(x_i) = x_i$ and $\pi(\bar{x}_i) = \bar{x}_i^{-1}$. A word $w \in (X \cup \bar{X})^*$ is called a (generalized) *bridge* if $\pi(w) = 1$. The set of bridges, noted $B$, is then equal to $\pi^{-1}(1)$.

Let $a = x_1 + \cdots + x_k + x_1^{-1} + \cdots + x_k^{-1} \in \mathbb{C}[F(X)]$. As before, write $a_n$ for the constant term of $a^n$. As in the previous case, it can be seen that $a_n$ is the number of bridges of length $n$.

Let $\le$ be a total order on the free group $F(X)$ compatible with its product. That is, $g_1 \le g_2$ implies $hg_1 \le hg_2$ and $g_1h \le g_2h$ for every $h, g_1, g_2 \in F(X)$. It is known, although not obvious, that such orders exist. The most standard one is obtained by embedding the free group into the group of invertible elements of the ring of noncommutative power series (Magnus embedding $x \mapsto 1+x$), and to give a total ring order to the latter; see for example [4, p.76].

By analogy with the previous case, we say that the *height* of a word $w \in (X \cup \bar{X})^*$ is $\pi(w) \in F(X)$. We can then compare words by their heights. We say that the height of a word is positive if it is greater or equal to $1 \in F(X)$. Note that in the case $X = \{x\}$, the free group on one generator is isomorphic to
($\mathbb{Z}$, $+$) and we can take the natural ordering of the integers. In this case, the height function is just the one defined in the previous section.

With this order, we can now say that a proper prefix $u$ of a bridge $w \in \mathcal{B}$ is a minimum of $w$ if $u$ has minimal height among the proper prefixes of $w$. In other words, $\pi(u) \le \pi(v)$ for every proper prefix $v$ of $w$. A bridge $w \in (X \cup \bar{X})^*$ is then called an (generalized) excursion if every one of it prefixes has positive height. The set of excursions is defined as

$$ \mathcal{E} = \{w \in \mathcal{B} \mid \pi(u) \ge 1, w = uv\}. $$

A pointed bridge is a triple $(w, u, v)$, where $w = uv$ is a bridge and $u$ is a minimum of $w$. Similarly, a pointed excursion is a triple $(w, u, v)$, where $w = uv$ is an excursion and $u$ is any proper prefix of $w$. We write $e_{n,k}$ (resp. $b_{n,k}$) for the number of pointed excursions (resp. bridges) of length $n$ with $k$ minima. The preceding bijection between pointed bridges and pointed excursion holds in this more general context.

**Lemma 2** The function

$$ f: \mathcal{E}^{\bullet} \to \mathcal{B}^{\bullet} \\ (uv, u, v) \mapsto (vu, v, u) $$

is a bijection between pointed excursions and pointed bridges.

**Proof:** Let $(uv, u, v) \in \mathcal{E}^{\bullet}$ be a pointed excursion. We first have to show that $(vu, v, u)$ is a pointed bridge. It is clear that $\pi(vu) = 1$ since $\pi(uv) = 1$ and $\pi(vu) = \pi(u)^{-1}\pi(uv)\pi(u) = 1$. So $vu$ is a bridge. Now, let $v_1$ be a prefix of $v$. So $vu = v_1v_2u$. Then, because $uv$ is an excursion,

$$ \begin{align*} \pi(uv_1) &\ge 1 = \pi(uv) \\ \iff \pi(1) &\ge \pi(v_2) \\ \iff \pi(v_1) &\ge \pi(v_1v_2) = \pi(v). \end{align*} $$

Similarly, if $u_1$ is a prefix of $u$, $\pi(u_1) \ge \pi(v)$ so $v$ is of minimal height among prefixes of $vu$ and $(vu, v, u)$ is a pointed bridge. Now, the map is clearly injective and it is also surjective since for a pointed bridge $(uv, u, v)$, $(vu, v, u)$ is clearly a pointed excursion. This completes the proof. □ As previously, this bijection gives us the equality $ne_{n,k} = kb_{n,k}$. If we let

$$ E(t) = \sum e_n t^n, \quad B(t) = \sum b_n t^n, $$

by the same proof as for lemma 1, we get the relation

$$ \frac{t(E(t))'}{E(t)} = \sum_{n \ge 1} b_n t^n. $$

Which says that the series $P_a$ for $a = x_1 + \cdots + x_k + x_1^{-1} + \cdots + x_k^{-1}$ is equal to the series $E(t)$ of generalized excursions.

Unfortunately, we were unable to prove that the language of generalized excursions is an algebraic language. So the algebraicity of the series $P_a$ does not follow from this argument.
# 5 Planar maps

The second example of Kontsevich, for $n = 2$, gives an interesting connection with planar maps. Indeed, for $a = x_1 + x_2 + x_1^{-1} + x_2^{-1}$, the series $P_a$ is by [7] equal to

$$P_a = \frac{\frac{2f+1}{3}}{\left(\frac{f+1}{2}\right)^2},$$

where $f = f(t) = \sqrt{1 - 12t^2}$. The first few terms of this series are

$$1 + 2t^2 + 9t^4 + 54t^6 + 378t^8 + 2916t^{10} + O(t^{12})$$

A quick look at Sloane's Online Encyclopedia of Integer Sequences suggests that the coefficient of $t^{2n}$ is the number of pointed planar maps with $n$ edges.

This is easily proved by comparing the generating function of pointed planar maps counted by number of edges and the series $P_a$. Indeed, the generating function for pointed planar maps is (see [6] chapter 7 section 8.2)

$$g(z) = \frac{-1}{54z^2}(1 - 18z - (1 - 12z)^{3/2}).$$

And a simple calculation shows that the series $g(t^2)$ is equal to $P_a$.

This raises the question of finding a bijection between pointed planar maps with $n$ edges and generalized excursions on two letters as defined in the previous section.

Another question is to prove combinatorially the equation

$$t \frac{d}{dt} g(t^2) = F_a(t) \qquad (4)$$

where $F_a(t)$ is the generating function of two-sided Dyck language on two letters (these are the generalized bridges in the case $n = 2$).
References

[1] Cyril Banderier and Philippe Flajolet. Basic analytic combinatorics of directed lattice paths. *Theoret. Comput. Sci.*, 281(1-2):37–80, 2002. ISSN 0304-3975. doi: 10.1016/S0304-3975(02)00007-5. URL http://dx.doi.org/10.1016/S0304-3975(02)00007-5. Selected papers in honour of Maurice Nivat.

[2] Jean Berstel. *Transductions and context-free languages*, volume 38 of *Leitfäden der Angewandten Mathematik und Mechanik [Guides to Applied Mathematics and Mechanics]*. B. G. Teubner, Stuttgart, 1979. ISBN 3-519-02340-7.

[3] N. Chomsky and M. P. Schützenberger. The algebraic theory of context-free languages. In *Computer programming and formal systems*, pages 118–161. North-Holland, Amsterdam, 1963.

[4] P. M. Cohn. *Skew fields*, volume 57 of *Encyclopedia of Mathematics and its Applications*. Cambridge University Press, Cambridge, 1995. ISBN 0-521-43217-0. Theory of general division rings.

[5] Philippe Duchon. On the enumeration and generation of generalized Dyck words. *Discrete Math.*, 225(1-3):121–135, 2000. ISSN 0012-365X. doi: 10.1016/S0012-365X(00)00150-3. URL http://dx.doi.org/10.1016/S0012-365X(00)00150-3. Formal power series and algebraic combinatorics (Toronto, ON, 1998).

[6] Philippe Flajolet and Robert Sedgewick. *Analytic combinatorics*. Cambridge University Press, Cambridge, 2009. ISBN 978-0-521-89806-5.

[7] Maxim Kontsevich. Noncommutative identities, September 2011. URL http://arxiv.org/abs/1109.2469v1.

[8] Jacques Labelle and Yeong Nan Yeh. Dyck paths of knight moves. *Discrete Appl. Math.*, 24(1-3): 213–221, 1989. ISSN 0166-218X. doi: 10.1016/0166-218X(92)90286-J. URL http://dx.doi.org/10.1016/0166-218X(92)90286-J. First Montreal Conference on Combinatorics and Computer Science, 1987.

[9] Jacques Labelle and Yeong Nan Yeh. Generalized Dyck paths. *Discrete Math.*, 82(1):1–6, 1990. ISSN 0012-365X. doi: 10.1016/0012-365X(90)90039-K. URL http://dx.doi.org/10.1016/0012-365X(90)90039-K.