Description

I my work, I met fixed-point functional equations of a very specific form. Since I am not expert in the domain of functional equations, I have not pushed the study of these very far. Here is a description the objects.

Let $X := \lbrace x_1, \dots, x_k \rbrace$ be an alphabet of mutually commuting indeterminates and $F(x_1, \dots, x_k)$ be the formal power series \begin{equation} F(x_1, \dots, x_k) := \sum_{\alpha_1, \dots, \alpha_k} \lambda_{\alpha_1 \dots \alpha_k} \: x_1^{\alpha_1} \dots x_k^{\alpha_k}, \end{equation} where all coefficients $\lambda_{\alpha_1 \dots \alpha_k}$ are nonnegative integers.

The series $F(x,_1, \dots, x_k)$ is defined by the fixed-point functional equation \begin{equation} F(x_1, \dots, x_k) = x_1 + F(P_1(x_1, \dots, x_k), \dots, P_k(x_1, \dots, x_k)), \end{equation} where for any $i \in [k]$, $P_i(x_1, \dots, x_k)$ is a polynomial with nonnegative integer coefficients. Of course, there are some necessarily conditions to ensure that $F(x_1, \dots, x_k)$ is well-defined.

Here are two celebrated examples of fixed-points equations of this kind.

1. The series $S(x)$ defined by \begin{equation} S(x) = x + S(x^2 + x^3). \end{equation} This functional equation has been studied by A. M. Odlyzko (see [Odl82]). One can compute first coefficients of $S(x)$ by iteration: \begin{equation} S_1(x) = x, \end{equation} \begin{equation} S_2(x) = x + x^2 + x^3, \end{equation} \begin{equation} S_3(x) = x + x^2 + x^3 + x^4 + 2x^5 + 3x^7 + 3x^8 + x^9, \end{equation} and so on. This generating series is of the form \begin{equation} S(x) = x + x^2 + x^3 + x^4 + 2x^5 + 2x^6 + 3x^7 + 4x^8 + 5x^9 + 8x^{10} + 14x^{11} + 23x^{12} + \dots \end{equation} and its coefficients have a combinatorial interpretation: the coefficient of $x^n$ is the number of $2,3$-balanced trees (see [Odl82] and also A014535) with $n$ leaves.

2. The series $B(x, y)$ defined by \begin{equation} B(x, y) = x + B(x^2 + 2xy, x). \end{equation} By iteration, one founds \begin{equation} B_1(x, y) = x, \end{equation} \begin{equation} B_2(x, y) = x + 2xy + x^2, \end{equation} \begin{equation} B_3(x, y) = x + 2xy + x^2 + 4x^2y + 2x^3 + 4x^2y^2 + 4x^3y + x^4. \end{equation} The coefficient of $x^n$ is the specialization $B(x) := B(x, 0)$ is the number of balanced binary trees (see [BLL94] and also A006265) with $n$ leaves.

In my work, I encountered fixed-point functional equations rather more complicated: \begin{equation} F(x, y, z) = x + F(x^2 + xy + yz, x, xy), \end{equation} \begin{equation} G(x, y, z) = x + G(x^2 + 2xy + yz, x, x^2 + xy), \end{equation} \begin{equation} H(x, y, z, t) = x + H(x^2 + 2yt + yz, x, x^2 + xy, yt + yz). \end{equation} Coefficients of these count some tree-like structures.

It seems that the theory is fairly well-known when the generating series are univariate (for instance, A. M. Odlyzko [Odl82] gives asymptotic formulas and recurrence relations for the coefficients of $S(x)$). In the multivariate case, it seems that only few things are known and up to my knowledge, there are not other way to express the series $B(x)$ counting balanced binary trees.

Questions

(1) Have-you encountered other fixed-points functional equations of the described form?

Given a fixed-point functional equation for a series $F$ of the given form:

(2) What about an other method to extract coefficients of $F$ otherwise than iteration?

(3) What about obtaining a recurrence relation between the coefficients of $F$?

(4) What about asymptotic approximations for the coefficients of $F$?

(5) What about rationality, algebraicness, d-finiteness, or other of $F$?

References

[Odl82] A. M. Odlyzko. Periodic Oscillations of Coefficients of Power Series That Satisfy Functional Equations. Advances in Mathematics, 44:180–205, 1982

[BLL94] F. Bergeron, G. Labelle, and P. Leroux. Combinatorial Species and Tree-like Structures. Cambridge University Press, 1994.