On the algebraicity of Puiseux series

Abstract

We deal with the algebraicity of a formal Puiseux series in terms of the properties of its coefficients. We show that the algebraicity of a Puiseux series for given bounded degrees is determined by a finite number of explicit universal polynomial formulas. Conversely, given a vanishing polynomial, there is a closed-form formula for the coefficients of the series in terms of the coefficients of the polynomial and of an initial part of the series.

1 Introduction

Let K be a field, $\overline{K}$ its algebraic closure, and x an indeterminate. We consider K[[x]], the domain of formal power series with coefficients in K, and its fraction field K((x)). We denote by $K((\hat{x})):= \bigcup \nolimits _{n=1}^{\infty }K((x^{1/n}))$ the field of formal Puiseux series (with coefficients in K). If K is of characteristic zero, by the Newton–Puiseux theorem (see e.g. [18, Theorem 3.1] and [13, p. 314, Proposition]), an algebraic closure of K((x)) is given by $\mathcal {P}_K:=\bigcup \nolimits _L L((\hat{x}))$ where L ranges over the finite extensions of K in $\overline{K}$. In particular, if $K=\overline{K}$, then $\mathcal {P}_K=K((\hat{x}))$. Among Puiseux series, we are interested in algebraic ones, say the Puiseux series which verify a polynomial equation $P(x,y)=0$ with coefficients which are themselves polynomials in x: $P(x,y)\in K[x][y]$. In fact, for the problems that we will investigate, it is sufficient to consider power series without fractional exponents (see Sect. 2). Therefore our article will mainly deal with algebraic power series.

Among the numerous works concerning algebraic Puiseux or power series [3, 9, 17], we deal with the following questions:

• Reconstruction of a vanishing polynomial for a given algebraic Puiseux series. Generically, a vanishing polynomial of a given algebraic power series can be computed as a Hermite-Padé approximant [1, Chap. 7]. In fact, the algebraicity of a Puiseux series can be encoded by the vanishing of certain determinants derived from the coefficients of the series. We extend this approach by showing how to reconstruct the coefficients of a vanishing polynomial by means of some minors of these determinants (see Sect. 3). More precisely, we show that, for given bounded degrees, there are finitely many universal polynomials allowing to check the algebraicity of a series and to perform this reconstruction (see Theorem 2). Note that this result holds for K of arbitrary characteristic.

• Description of the coefficients of an algebraic Puiseux series in terms of the coefficients of a vanishing polynomial. An approach consists in considering that the series coefficients verify a linear recurrence relation, which allows an asymptotic computation of the coefficients. This property follows classically from the fact that an algebraic Puiseux series is differentiably finite (D-finite), that is, it satisfies a linear differential equation with coefficients in K[x] [2, 4,5,6, 14,15,16]. Another approach consists in determining a closed-form expression in terms of the coefficients of a vanishing polynomial. In this direction, P. Flajolet and M. Soria (see the habilitation thesis of M. Soria (1990) and [8]) proposed a formula in the case of a series satisfying a reduced Henselian equation (see Definition 2 for this terminology) with complex coefficients. This formula extends to coefficients in an arbitrary field of characteristic zero K via a work of Henrici [12]. Here we complete this approach to the case of a Puiseux series which satisfies a general polynomial equation $P(x,y)=0$, by showing that the coefficients of such series can be computed applying Flajolet–Soria’s formula to a polynomial naturally derived from P (see Sect. 4). In this section, the field K is required to be of zero characteristic.

2 Preliminaries

Let us denote $\mathbb {N}:=\mathbb {Z}_{\ge 0}$ and $\mathbb {N}^*:=\mathbb {N}{\setminus }\{0\}=\mathbb {Z}_{>0}$. For any set $\mathcal {E}$, we will write $|\mathcal {E}|:=\mathrm {Card}(\mathcal {E})$. For any vector of natural numbers $L=(l_1,\ldots ,l_n)$, we set $L!:=\prod \nolimits _{i=1}^nl_i!$, $|L|:=\sum \nolimits _{i=1}^nl_i$ and $\Vert L\Vert :=\sum \nolimits _{i=1}^ni\,{l_i}$. The floor function will be written $\lfloor q \rfloor$ for $q\in \mathbb {Q}$. Let K be a (commutative) field.

We will need the following elementary lemma of linear algebra:

Lemma 1

Let $V_1,\ldots ,V_p$ be a family of infinite vectors, $V_j=(v_{i,j})_{i\in \mathbb {N}^*}\in K^{\mathbb {N}^*}$. Let M denote the matrix whose columns are the $V_j$’s. The rank of $V_1,\ldots ,V_p$ is less than p if and only if all the minors of order p of M vanish.

Proof

If M has rank less than p, then there is a nonzero vector $(a_j)_{j=1,\ldots ,p}\in K^p$ such that:

$$\begin{aligned} \sum _{j=1}^p a_jV_j=0. \end{aligned}$$

This implies that the same nontrivial linear combination vanishes for the columns of any submatrix of size $p\times p$ of M. Hence, the determinant of any of such matrix has to vanish.

Conversely, suppose that M has rank p. In particular, all the vectors $V_j$ are nonzero. Let us consider the first nonzero coefficient of $V_1$. Up to a permutation of the rows (which does not change the rank of M), we may assume for simplicity that $v_{1,1}\ne 0$. Then for any $j=2,{\ldots },p$, let us replace $V_j$ by $V_j-\frac{v_{1,j}}{v_{1,1}}V_1$, which does not change the rank of M either. We obtain a new matrix $M_1$ whose first row is the p-tuple $(v_{1,1},0,\ldots ,0)$, and whose columns are still all nonzero. The same process can be done with the next column, with nonzero coefficient taken without loss of generality at the second row etc. The process stops after p iterations and we obtain a matrix $M_p$ with the p first lines consisting of a lower triangular matrix with nonzero coefficients in the diagonal. The determinant of the latter—which is equal up to the sign to a minor of order p of M—is nonzero.

Let $\tilde{y}_0=\displaystyle \sum \limits _{n\ge n_0} \tilde{c}_nx^{n/p}\in K((\hat{x})),\ \tilde{c}_{n_0}\ne 0$, be a Puiseux series. We denote

$$\begin{aligned} \tilde{y}_0=x^{(n_0-1)/p}\sum _{n\ge 1} c_nx^{n/p}=x^{(n_0-1)/p}\tilde{z}_0\ \ \text {with}\ c_1\ne 0, \end{aligned}$$

where $c_n=\tilde{c}_{n-n_0+1}$ for $n\in \mathbb {N}^*$. The series $\tilde{y}_0$ is a root of a polynomial $\tilde{P}(x,y)=\sum \nolimits _{i,j} \tilde{a}_{i,j}x^iy^j\in K[x,y]$ of degree $d_y$ in y if and only if the series $y_0=\sum \nolimits _{n\ge 1} c_nx^n$ is a root of $x^m\tilde{P}(x^p,x^{n_0-1}y)$, the latter being a polynomial for $m=\max \{0;(1-n_0)d_y\}$. The existence of a polynomial $\tilde{P}$ cancelling $\tilde{y}_0$ is equivalent to the one of a polynomial $P(x,y)=\sum \nolimits _{i,j} a_{i,j}x^iy^j$ cancelling $y_0$, such that, for (i, j) belonging to the support of P, one has $i\equiv (n_0-1)j \mathrm { mod } p$ if $n_0-1\ge 0$, and $i\equiv (1-n_0)(d_y-j)\mathrm { mod }p$ otherwise. Thus the algebraicity of $\tilde{y}_0$ is equivalent to that of $y_0$ but with constraints on the support of P. This leads us to the following definition:

Definition 1

Let $\mathcal {F}$ and $\mathcal {G}$ be two strictly increasing finite sequences of ordered pairs $(i,j)\in \mathbb {N}^2$ ordered anti-lexicographically:

$$\begin{aligned} (i_1,j_1) \le (i_2,j_2)\Leftrightarrow j_1 < j_2\text { or } (j_1 = j_2\ \text {and}\ i_1 \le i_2). \end{aligned}$$

We suppose additionally that $\mathcal {F}\ge (0,1)>\mathcal {G}>(0,0)$ (thus the elements of $\mathcal {G}$ are ordered pairs of the form (i, 0), $i\in \mathbb {N}^*$, and those of $\mathcal {F}$ are of the form $(i,j),\ j\ge 1$). We say that a series $y_0=\sum \nolimits _{n\ge 1} c_nx^n\in K[[x]]$, $c_1\ne 0$, is algebraic relatively to $(\mathcal {F},\mathcal {G})$ if there exists a polynomial $P(x,y)=\sum \nolimits _{(i,j)\in \mathcal {F}\cup \mathcal {G}} a_{i,j}x^iy^j\in K[x,y]$ such that $P(x,y_0)=0$.

Flajolet and Soria (see the habilitation thesis of M. Soria (1990) and [8]) gave a closed-form expression to compute the coefficients of a formal solution of a reduced Henselian equation in the following sense:

Definition 2

We call reduced Henselian equation any equation of the following type:

$$\begin{aligned} y=Q(x,y)\ \text { with }\ Q(x,y)\in K[x,y], \end{aligned}$$

such that $Q(0,0)=\frac{\partial Q}{\partial y}(0,0)=0$ and $Q(x,0){\not \!\!{\equiv }}0$.

Theorem 1

(Flajolet–Soria’s formula) Let $y=Q(x,y)=\sum \nolimits _{i,j}a_{i,j}x^iy^j$ be a reduced Henselian equation. Then the coefficients of the unique solution $\sum \nolimits _{n\ge 1}c_nx^n$ are given by:

$$\begin{aligned} c_n=\sum _{m=1}^{2n-1}\frac{1}{m}\sum _{|\underline{k}|=m,\ ||\underline{k}||_1=n,\ ||\underline{k}||_2=m-1}\frac{m!}{\prod _{i,j}k_{i,j}!}\prod _{i,j}a_{i,j}^{k_{i,j}}, \end{aligned}$$

where $\underline{k}=(k_{i,j})_{i,j}$, $\ |\underline{k}|=\sum \nolimits _{i,j}k_{i,j}$, $\ ||\underline{k}||_1 = \sum \nolimits _{i,j}i\, k_{i,j}$ and $\ ||\underline{k}||_2 = \sum \nolimits _{i,j}j\, k_{i,j}$.

Remark 1

Let us consider the particular case where the coefficients of Q verify $a_{0,j}=0$ for all j. So, for any $\underline{k}$ such that $|\underline{k}|=m$ and $\prod \nolimits _{i,j}a_{i,j}^{k_{i,j}}\ne 0$, we must have $\Vert \underline{k}\Vert _1\ge m$. Thus, to have $\Vert \underline{k}\Vert _1=n$, one needs to have $m\le n$. Flajolet–Soria’s Formula can be written:

$$\begin{aligned} c_n=\sum _{m=1}^{n}\frac{1}{m}\sum _{|\underline{k}|=m,\ ||\underline{k}||_1=n,\ ||\underline{k}||_2=m-1}\frac{m!}{\prod _{i,j}k_{i,j}!}\prod _{i,j}a_{i,j}^{k_{i,j}}. \end{aligned}$$

3 Characterizing the algebraicity of a formal power series

Here we resume the remarks from [19]. The purpose of the following discussion is to translate the vanishing of a polynomial P at a formal series $y_0$ in terms of the vanishing of minors of an infinite matrix. Let us consider a series $Y_0=\sum \nolimits _{n\ge 1} C_nx^{n}\in K[(C_n)_{n\in \mathbb {N}^*}][[x]]$ where x and the $C_n$’s are variables. We denote the multinomial expansion of the jth power $Y_0^j$ of $Y_0$ by:

$$\begin{aligned} Y_0^j=\sum _{n\ge 1} C_n^{(j)}x^{n} \end{aligned}$$

where $C_n^{(j)}=C_n^{(j)}(C_1,\ldots ,C_{n-j+1})\in K[C_1,\ldots ,C_{n-j+1}]$. Of course, one has that $C_n^{(j)}\equiv 0$ for $n<j$ and $C_j^{(j)}=C_1^j$. For $j=0$, let $Y_0^0:=1$. We remark that for any n and any $j\le n$, $C_n^{(j)}$ is a homogeneous polynomial of degree j in the $C_m$’s for $m\le n-j+1$, with natural number coefficients (indeed, each monomial occurring in $C_n^{(j)}$ is of the form $C_{i_1}\ldots C_{i_j}$ with $i_k\ge 1$ and $i_1+\cdots +i_j=n$, so $i_k\le n-j+1$ for any k).

Now suppose we are given a series $y_0=\sum \nolimits _{n\ge 1} c_nx^{n}\in K[[x]]$ with $c_1\ne 0$. For any $j\in \mathbb {N}$, we denote the multinomial expansion of $y_0^j$ by:

$$\begin{aligned} y_0^j=\sum _{n\ge 1} c_n^{(j)}x^{n}. \end{aligned}$$

So, $c_n^{(j)}=C_n^{(j)}(c_1,\ldots ,c_{n-j+1})$.

Definition 3

• (i) Given an ordered pair $(i,j)\in \mathbb {N}\times \mathbb {N}$, we call Wilczynski vector $V_{i,j}$ the infinite vector with components:

  • if $j\ge 1$, a sequence of i zeros followed by the coefficients of the multinomial expansion $y_0^j$:

    $$\begin{aligned} V_{i,j}:=\left( 0,\ldots ,0,c_1^{(j)},c_2^{(j)},\ldots ,c_n^{(j)},\ldots \right) ; \end{aligned}$$

  • otherwise, 1 in the ith position and 0 for the other coefficients

    $$\begin{aligned} V_{i,0}:=(0,\ldots ,1,0,0,\ldots ,0,\ldots ). \end{aligned}$$

• (ii) Let $\mathcal {F}$ and $\mathcal {G}$ be two sequences as in Definition 1. We associate to $\mathcal {F}$ and $\mathcal {G}$ the (infinite) Wilczynski matrix whose columns are the corresponding vectors $V_{i,j}$:

  $$\begin{aligned} M_{\mathcal {F},\mathcal {G}}:=(V_{i,j})_{(i,j)\in \mathcal {F}\cup \mathcal {G}}\, , \end{aligned}$$

  $\mathcal {F}\cup \mathcal {G}$ being ordered anti-lexicographically. We define also the reduced Wilczynski matrix, $M_{\mathcal {F},\mathcal {G}}^{red}$: it is the matrix obtained from $M_{\mathcal {F},\mathcal {G}}$ by removing the columns indexed in $\mathcal {G}$, and also removing the corresponding rows (suppress the ith row for any $(i,0)\in \mathcal {G}$). This amounts exactly to remove the rows containing the coefficient 1 for some Wilczynski vector indexed in $\mathcal {G}$.

Lemma 2

(Wilczynski) The series $y_0$ is algebraic relatively to $(\mathcal {F},\mathcal {G})$ if and only if all the minors of order $|\mathcal {F}\cup \mathcal {G}|$ of the Wilczynski matrix $M_{\mathcal {F},\mathcal {G}}$ vanish, or also if and only if all the minors of order $|\mathcal {F}|$ of the reduced Wilczynski matrix $M_{\mathcal {F},\mathcal {G}}^{red}$ vanish.

Proof

Given a nontrivial polynomial $P(x,y)=\sum \nolimits _{(i,j) \in \mathcal {F}\cup \mathcal {G}}a_{i,j}x^iy^j$, we compute:

$$\begin{aligned} P(x,y_0)=\sum _{(i,j) \in \mathcal {F}}a_{i,j}x^i\left( \sum _{n\ge 1} c_n^{(j)}x^{n}\right) +\sum _{(i,0) \in \mathcal {G}}a_{i,0}x^i. \end{aligned}$$

The coefficients of the expansion of $P(x,y_0)$ with respect to the powers of x in increasing order are exactly the components of the infinite vector resulting from the following operation:

$$\begin{aligned} M_{\mathcal {F},\mathcal {G}}\cdot (a_{i,j})_{(i,j)\in \mathcal {F}\cup \mathcal {G}}. \end{aligned}$$

The series $y_0$ is a root of a nonzero polynomial with support included into $\mathcal {F}\cup \mathcal {G}$ if and only if there is a non zero solution $(a_{i,j})_{(i,j)\in \mathcal {F}\cup \mathcal {G}}$ of the following equation:

$$\begin{aligned} M_{\mathcal {F},\mathcal {G}}\cdot (a_{i,j})_{(i,j)\in \mathcal {F}\cup \mathcal {G}}=0. \end{aligned}$$

This means that the rank of $M_{\mathcal {F},\mathcal {G}}$ is less than $|\mathcal {F}\cup \mathcal {G}|$, the number of columns of $M_{\mathcal {F},\mathcal {G}}$. The latter condition is characterized as in finite dimension by the vanishing of all the minors of maximal order (see Lemma 1).

Let us now remark that, in the infinite vector $M_{\mathcal {F},\mathcal {G}}\cdot (a_{i,j})_{(i,j)\in \mathcal {F}\cup \mathcal {G}}$, if we remove the components of number i for $(i,0)\in \mathcal {G}$, then we get exactly the infinite vector $M_{\mathcal {F},\mathcal {G}}^{red}\cdot (a_{i,j})_{(i,j)\in \mathcal {F}}$. The vanishing of the latter means precisely that the rank of $M_{\mathcal {F},\mathcal {G}}^{red}$ is less than $|\mathcal {F}|$. Conversely, if the columns of $M_{\mathcal {F},\mathcal {G}}^{red}$ are dependent for certain $\mathcal {F}$ and $\mathcal {G}$, we denote by $(a_{i,j})_{(i,j)\in \mathcal {F}}$ a corresponding sequence of coefficients of a nontrivial vanishing linear combination of the column vectors. Then it suffices to note that the remaining coefficients $a_{k,0}$ for $(k,0)\in \mathcal {G}$ are each uniquely determined as follows:

$$\begin{aligned} a_{k,0}=-\sum _{(i,j)\in \mathcal {F}, i< k} a_{i,j}c_{k-i}^{(j)}\,. \end{aligned}$$

(1)

We deal with the implicitization problem for algebraic power series: for fixed bounded degrees in x and y, given the expression of an algebraic series, can we reconstruct a vanishing polynomial? if yes, how?

Definition 4

Let us consider the abstract version $\mathbf M _{\mathcal {F},\mathcal {G}}$ and $\mathbf M _{\mathcal {F},\mathcal {G}}^{red}$ associated to the abstract series $Y_0=\sum \nolimits _{n\ge 1} C_nx^{n}\in K[(C_n)_{n\in \mathbb {N}^*}][[x]]$ and to two sequences $\mathcal {F}$ and $\mathcal {G}$ of ordered pairs (i, j) as in Definition 1, of the Wilczynski matrices. We call Wilczynski polynomial any polynomial in the variables $C_n$ obtained as a minor of $\mathbf M _{\mathcal {F},\mathcal {G}}^{red}$. We denote such Wilczynski polynomial by $Q_{\underline{k},\underline{I}}$, where $\underline{I}:=((i_1,j_1),\ldots ,(i_l,j_l))$ is a subsequence of $\mathcal {F}$ indicating the l columns of $\mathbf M _{\mathcal {F},\mathcal {G}}^{red}$, and $\underline{k}:=(k_1,k_2,\ldots ,k_l)$ a strictly increasing sequence of natural numbers indicating the l rows of $\mathbf M _{\mathcal {F},\mathcal {G}}^{red}$ used to form the minor of $\mathbf M _{\mathcal {F},\mathcal {G}}^{red}$. One has that $l\in \mathbb {N}^*$, $l\le |\mathcal {F}|$, l being the order of that minor, that we will also call the order of the Wilczynski polynomial $Q_{\underline{k},\underline{I}}$. Note also that a Wilczynski polynomial $Q_{\underline{k},\underline{I}}$ is either homogeneous of degree equal to $\sum \nolimits _{(i,j)\in \underline{I}}j\$ or identically 0 (indeed, the multinomial coefficients $C_k^{(j)}$ in a column indexed by (i, j) of $\mathbf M _{\mathcal {F},\mathcal {G}}^{red}$ are either homogenous of degree j (case $k\ge j$) or identically 0 (case $k<j$)). By convention, we call Wilczynski polynomial of order 0 any nonzero constant polynomial.

By Lemma 2, the algebraicity of $y_0$ for certain $\mathcal {F}$ and $\mathcal {G}$ is equivalent to the vanishing of all the $Q_{\underline{k},\mathcal {F}}$ of order $l=|\mathcal {F}|$, at the specific values of the given coefficients $c_n$ of $y_0$.

Example 1

Let $y_0=\sum \nolimits _{n\ge 1} c_nx^{n}\in K[[x]]$ be a series with $c_1\ne 0$. We consider the conditions for $y_0$ to be a root of a polynomial of type:

$$\begin{aligned} P(x,y)=a_{2,0}x^2+a_{2,1}x^2y+(a_{0,2}+a_{2,2}x^2)y^2. \end{aligned}$$

Thus, $\mathcal {F}=\{(2,1),(0,2),(2,2)\}$ and $\mathcal {G}=\{(2,0)\}$. The corresponding Wilczynski matrix is:

$$\begin{aligned} M :=\left[ \begin{array}{c@{\quad }c@{\quad }c@{\quad }c}0 &{} 0 &{} 0 &{} 0 \\ 1 &{} 0 &{} \mathrm{c}_{1}^{2} &{} 0 \\ 0 &{} \mathrm{c}_{1} &{} 2\cdot c _{1}\cdot c _{2} &{} 0 \\ 0 &{} \mathrm{c}_{2} &{} c _{2}^{2}+2~c _{1}~c _{3} &{} \mathrm{c}_{1}^{2} \\ 0 &{} \mathrm{c}_{3} &{} 2~c _{1}~c _{ 4}+2~c _{2}~c _{3} &{} 2\cdot c _{1}\cdot c _{2} \\ 0 &{} \mathrm{c}_{4 } &{} 2~c _{2}~c _{4}+c _{3}^{2}+2~c _{1}~c _{5} &{} c _{2}^{2}+2~c _{1}~c _{3} \\ \vdots &{} \vdots &{} \vdots &{} \vdots \\ \end{array}\right] , \end{aligned}$$

and the reduced matrix is:

$$\begin{aligned} M ^{{ red} }:= \left[ \begin{array}{c@{\quad }c@{\quad }c}0 &{} 0 &{} 0 \\ c _{1} &{} 2\cdot c _{1}\cdot c _{2} &{} 0 \\ c _{2} &{} c _{2}^{2}+2~c _{1}~c _{3} &{} \mathrm{c}_{1}^{2} \\ c _{3} &{} 2~c _{1}~c _{4}+2~c _{2}~c _{3} &{} 2\cdot c _{1}\cdot c _{2} \\ c _{4} &{} 2~c _{2}~c _{4}+c _{3}^{2}+2~c _{1}~c _{5} &{} c _{2}^{2}+2~ c _{1}~c _{3} \\ \vdots &{} \vdots &{} \vdots \\ \end{array}\right] . \end{aligned}$$

We give the four first nontrivial Wilczynski polynomials of maximal order 3, which are equal to $3\times 3$ minors of $\mathbf M ^{red}$. So one has that $\underline{I}=\mathcal {F}$ as index for $Q_{\underline{k},\underline{I}}$:

$$\begin{aligned}&Q_{\underline{k},\mathcal {F}}:= -2\,{C_{{1}}}^{2} \left( {C_{{2}}}^{3}-2\,C_{{3}}C_{{1}}C_{{2}}+{C_{{1}}}^{2}C_{{4}} \right) \ \text { for }\underline{k}=(2,3,4), \\&Q_{\underline{k},\mathcal {F}}:= -C_{{1}} \left( {C_{{2}}}^{4}-3\,{C_{{1}}}^{2}{C_{{3}}}^{2}+2\,{C_{{1}}}^{3}C_{{5}} \right) \ \text { for }\underline{k}=(2,3,5), \\&Q_{\underline{k},\mathcal {F}}:= -2\,{C_{{1}}}^{2} \left( -C_{{4}}{C_{{2}}}^{2}-2\,C_{{1}}C_{{4}}C_{{3}}+C_{{2}}{C_{{3}}}^{2}+2\,C_{{1}}C_{{2}}C_{{5}} \right) \ \text { for }\underline{k}=(2,4,5), \\&Q_{\underline{k},\mathcal {F}}:= 8\,C_{{2}}{C_{{1}}}^{2}C_{{4}}C_{{3}}+{C_{{2}}}^{4}C_{{3}}-2\,{C_{{2}}}^{2}{C_{{3}}}^{2}C_{{1}}-4\,{C_{{1}}}^{2}{C_{{2}}}^{2}C_{{5}}\\&\qquad \quad \qquad -\,3\,{C_{{1}}}^{2}{C_{{3}}}^{3}+2\,C_{{3}}{C_{{1}}}^{3}C_{{5}} -2\,{C_{{1}}}^{3}{C_{{4}}}^{2}\ \ \ \text { for }\underline{k}=(3,4,5) . \end{aligned}$$

The series $y_0$ is a root of a polynomial P(x, y) as above if and only if all the Wilczynski polynomials of order 3 vanish at the $c_n$’s. This implies in particular that:

$$\begin{aligned} c_{{4}}=-{\frac{c_{{2}} \left( {c_{{2}}}^{2}-2\,c_{{1}}c_{{3}} \right) }{{c_{{1}}}^{2}}}\ \text { and }\ c_{{5}}=-\,{\frac{{c_{{2}}}^{4}-3\,{c_{{1}}}^{2}{c_{{3}}}^{2}}{{2\, c_ {{1}}}^{3}}}. \end{aligned}$$

Theorem 2

Let $\mathcal {F}$ and $\mathcal {G}$ be two finite sequences of ordered pairs as in Definition 1. We set $d_y:=\max \{j,\ (i,j)\in \mathcal {F}\}$, $d_x:=\max \{i,\ (i,j)\in \mathcal {F}\cup \mathcal {G}\}$ and $N:=2d_xd_y$. Then there exist a finite set $\varLambda$ and a finite number of homogeneous polynomials $a_{i,j}^{(\lambda )}\in \mathbb {Z}[C_1,\ldots ,C_N]$, $(i,j)\in \mathcal {F}\cup \mathcal {G}$, $\lambda \in \varLambda$, of total degree $\deg a_{i,j}^{(\lambda )}\le \frac{1}{2}d_y(d_y+1)(d_x+1)-1$ for $(i,j)\in \mathcal {F}$, and $\deg a_{i,0}^{(\lambda )}\le \frac{1}{2}d_y(d_y+1)(d_x+1)-1+i$ for $(i,0)\in \mathcal {G}$, such that, for any series $y_0=\sum \nolimits _{n\ge 1} c_nx^{n}\in K[[x]]$ with $c_1\ne 0$ algebraic relatively to $(\mathcal {F},\mathcal {G})$, there is $\lambda \in \varLambda$ such that the polynomial:

$$\begin{aligned} P^{(\lambda )}(x,y)=\sum _{(i,j) \in \mathcal {F}}a_{i,j}^{(\lambda )}(c_1,\ldots ,c_N)x^iy^j+\sum _{(i,0) \in \mathcal {G}}a_{i,0}^{(\lambda )}(c_1,\ldots ,c_N)x^i\ \in K[x,y] \end{aligned}$$

(2)

is nonzero and vanishes at $y_0$.

First, we give the reconstruction process. Then we will show its finiteness.

Proof

Let $y_0=\sum \nolimits _{n\ge 1} c_nx^{n}\in K[[x]]$ with $c_1\ne 0$ be algebraic relatively to $(\mathcal {F},\mathcal {G})$. We show how to reconstruct a nonzero vanishing polynomial P(x, y) of $y_0$.

We consider a minimal family $\mathcal {F}'\subseteq \mathcal {F}$ such that $y_0$ is algebraic relatively to $(\mathcal {F}',\mathcal {G})$. Let $Q(x,y)=\sum \nolimits _{(i,j) \in \mathcal {F}'}b_{i,j}x^iy^j+\sum \nolimits _{(i,0) \in \mathcal {G}}b_{i,0}x^i$ be a nonzero polynomial that vanishes at $y_0$. Let $m:=| \mathcal {F}'|$. If $m=1$, Q(x, y) is of the form:

$$\begin{aligned} Q(x,y)=b_{i,j}x^iy^j+\sum _{(i,0) \in \mathcal {G}}b_{i,0}x^i, \end{aligned}$$

with $b_{i,j}\ne 0$. So we must have $b_{n,0}=0$ for $n<i+j$, and the series $y_0$ verifies:

$$\begin{aligned} \sum _{(n,0) \in \mathcal {G}}b_{n,0}x^n=-b_{i,j}x^iy_0^j=\sum _{n>i} -b_{i,j}c_{n-i}^{(j)}x^{n}. \end{aligned}$$

By Lemma 2, the minors of order 1 of $M_{(i,j),\mathcal {G}}^{red}$, being equal to $c_{n-i}^{(j)}$ for $(n,0)\notin \mathcal {G}$, are all zero. We fix the coefficient $a_{i,j}$ arbitrarily in $\mathbb {Z}{\setminus } \{0\}$: it is a constant Wilczynski polynomial. Then the other coefficients are uniquely determined in accordance with Relation (1) by the equation:

$$\begin{aligned} a_{n,0}(c_1,c_2,\ldots ):=-a_{i,j}c_{n-i}^{(j)},\ \ (n,0)\in \mathcal {G}. \end{aligned}$$

Thus $a_{n,0}$ is a polynomial of degree j in the $C_k$, $k\le n-i-j+1$, which verifies indeed that $j\le d_y \le \frac{1}{2}d_y(d_y+1)(d_x+1)\le \frac{1}{2}d_y(d_y+1)(d_x+1)-1+n$.

Suppose now that $m=| \mathcal {F}'|\ge 2$. By Lemma 2, the minors of order m of $M_{\mathcal {F}',\mathcal {G}}^{red}$ all vanish, and, because $\mathcal {F}'$ is minimal, there exists a nonzero minor of order $m-1$ of this matrix, i.e. a Wilczynski polynomial evaluated at the $c_n$’s

$$\begin{aligned} Q_{\underline{k}_0,\underline{I}_0}(c_1,c_2,\ldots ) \ne 0. \end{aligned}$$

(3)

Let $(i_0,j_0)\in \mathcal {F}'$ be such that $\mathcal {F}'=\underline{I}_0\cup \{(i_0,j_0)\}$ and $p_0$ be the position of $(i_0,j_0)$ in $\mathcal {F}'$. Denote by $M_{\underline{k}_0,\underline{I}_0}$ the square matrix whose determinant is $Q_{\underline{k}_0,\underline{I}_0}(c_1,c_2,\ldots )$, and $W_{\underline{k}_0,(i_0,j_0)}$ the truncated $p_0$-th column that has been removed from $M_{\mathcal {F}',\mathcal {G}}^{red}$ to form this minor. We get a system of equations with a non-vanishing determinant and $b_{i_0,j_0}\ne 0$:

$$\begin{aligned} M_{\underline{k}_0,\underline{I}_0}\cdot (b_{i,j})_{(i,j)\ne (i_0,j_0)}=-b_{i_0,j_0}W_{\underline{k}_0,(i_0,j_0)}. \end{aligned}$$

(4)

Let us build polynomials $a_{i,j}$ verifying:

$$\begin{aligned} M_{\underline{k}_0,\underline{I}_0}\cdot (a_{i,j}(c_1,c_2,\ldots ))_{(i,j)\ne (i_0,j_0)}=-a_{i_0,j_0}(c_1,c_2,\ldots )W_{\underline{k}_0,(i_0,j_0)}, \end{aligned}$$

(5)

by taking $a_{i_0,j_0}(c_1,c_2,\ldots ):=(-1)^{p_0}Q_{\underline{k}_0,\underline{I}_0}(c_1,c_2,\ldots )\ne 0$ and by computing the other $a_{i,j}(c_1,c_2,\ldots )$ by Cramer’s rule. Thus the $a_{i,j}(c_1,c_2,\ldots )$ are all minors of order $m-1$ of $M_{\mathcal {F}',\mathcal {G}}^{red}$, and so, up to the sign, evaluations at the $c_n$’s of Wilczynski polynomials $Q_{\underline{k}_0,\underline{I}}$ of order $m-1$. If $\underline{k}_0=(k_{0,1},\ldots ,k_{0,m-1})$, we set:

$$\begin{aligned} N_{y_0}:=k_{0,m-1}. \end{aligned}$$

(6)

The $a_{i,j}$ are homogeneous polynomials of $\mathbb {Z}[C_1,\ldots ,C_{N_{y_0}}]$. The degree of a Wilczynski polynomial $Q_{\underline{k}_0,\underline{I}}$ verifies:

$$\begin{aligned} \deg Q_{\underline{k}_0,\underline{I}}= & {} \sum _{(i,j)\in \underline{I},\ c_k^{(j)}{\not \!\!{\equiv }}0}j\\\le & {} -1+\sum _{(i,j)\in \mathcal {F}' }j\\\le & {} -1+(d_x+1)\sum _{j=1}^{d_y}j\\= & {} \frac{1}{2}d_y(d_y+1)(d_x+1)-1. \end{aligned}$$

The coefficients $a_{n,0}(c_1,c_2,\ldots )$ for $(n,0)\in \mathcal {G}$ are obtained via relations (1):

$$\begin{aligned} a_{n,0}(c_1,c_2,\ldots )=-\displaystyle \sum _{(i,j)\in \mathcal {F}', n>i} a_{i,j}(c_1,c_2,\ldots )c_{n-i}^{(j)}. \end{aligned}$$

(7)

Note that the coefficients $b_{n,0}$ for $(n,0)\in \mathcal {G}$ of Q also satisfy:

$$\begin{aligned} b_{n,0}=-\displaystyle \sum _{(i,j)\in \mathcal {F}', n>i} b_{i,j}c_{n-i}^{(j)}. \end{aligned}$$

(8)

Let us set $a_{i,j}:=0$ for $(i,j)\in \mathcal {F}{\setminus }\mathcal {F}'$. Knowing that $C_{n-i}^{(j)}{\not \!\!{\equiv }}0 \Rightarrow n-i\ge j$, and in this case $\deg C_{n-i}^{(j)}=j$, we deduce that $\deg a_{n,0}\le n+\max _{(i,j)\in \mathcal {F}}(\deg a_{i,j})$ as desired. As the right-hand sides of Systems (4) and (5) are proportional, there is $\mu :=\displaystyle \frac{a_{i_0,j_0}(c_1,c_2,\ldots )}{b_{i_0,j_0}}\in K{\setminus }\{0\}$ such that $a_{i,j}(c_1,c_2,\ldots )=\mu b_{i,j}$ for any $(i,j)\in \mathcal {F}'$. By Systems (7) and (8), one has also $a_{n,0}(c_1,c_2,\ldots )=\mu b_{n,0}$ for $(n,0)\in \mathcal {G}$. The polynomial

$$\begin{aligned} P(x,y)=\displaystyle \sum _{(i,j)\in \mathcal {F}'\cup \mathcal {G}}a_{i,j}(c_1,c_2,\ldots )x^iy^j \end{aligned}$$

is proportional to Q (i.e. $P=\mu Q$), so it is nonzero and vanishes at $y_0$.

To obtain Theorem 2, it suffices now to show that there exists a uniform bound $N_{d_x,d_y}$ for the depth in $M_{\mathcal {F},\mathcal {G}}^{red}$ to which we get the reconstruction process, that is, the depth at which we find a first nonzero minor. We reach this in the two following lemmas.

Lemma 3

Let $d_x,\, d_y\in \mathbb {N}^*$. For any series $y_0=\sum \nolimits _{n\ge 1} c_nx^{n}\in K[[x]]$ with $c_1\ne 0$, verifying an equation $P(x,y_0)=0$ where $P(x,y)\in K[x,y]{\setminus } \{0\}$, $\deg _xP\le d_x,\ \deg _yP\le d_y$, and for any polynomial $Q(x,y)\in K[x,y],\ \deg _xQ\le d_x,\ \deg _yQ\le d_y$, such that $Q(x,y_0)\ne 0$, one has that $\mathrm {ord}_xQ(x,y_0)\le 2d_xd_y$.

Proof

Let $y_0$ be a series as in the statement of Lemma 3. We consider the ideal $I_0:=\{R(x,y)\in K[x,y]\ |\ R(x,y_0)=0\}$. By assumption, it is a nontrivial prime ideal, so its height is one or two. If it were equal to 2, then it would be a maximal ideal. But $I_0$ is included into the ideal $\{R(x,y)\in K[x,y]\ |\ R(0,0)=0\}$, so:

$$\begin{aligned} I_0=\{R(x,y)\in K[x,y]\ |\ R(0,0)=0\}=(x,y) \end{aligned}$$

which is absurd because $x\notin I_0$. So, $I_0$ is a height one prime ideal of the factorial ring K[x, y]. It is generated by an irreducible polynomial $P_0(x,y)\in K[x,y]$. We set $d_{0,x}:=\deg _x P_0$ and $d_{0,y}:=\deg _y P_0$. Note also that, by factoriality of K[x, y], $P_0$ is also irreducible as an element of K(x)[y].

Let P be as in the statement of Lemma 3. One has that $P=SP_0$ for some $S\in K[x,y]$. Hence $d_{0,x}\le d_x$ and $d_{0,y}\le d_y$. Let $Q\in K[x,y]$ be such that $Q(x,y_0)\ne 0$ with $\deg _x Q\le d_x$, $\deg _yQ\le d_y$. So $P_0$ and Q are coprime in K(x)[y]. Their resultant r(x) is nonzero. One has the following Bézout relation in K[x][y]:

$$\begin{aligned} A(x,y)P_0(x,y)+B(x,y)Q(x,y)=r(x). \end{aligned}$$

We evaluate at $y=y_0$:

$$\begin{aligned} 0+B(x,y_0)Q(x,y_0)=r(x). \end{aligned}$$

So $\mathrm {ord}_x Q(x,y_0)\le \deg _x r(x)$. But, the resultant is a determinant of order at most $d_y+d_{0,y}\le 2\,d_y$ whose entries are polynomials in K[x] of degree at most $\max \{d_x,d_{0,x}\}= d_x$. So, $\deg _x r(x)\le 2\,d_xd_y$. Hence, one has that: $\mathrm {ord}_x Q(x,y_0)\le 2\,d_xd_y$.

Lemma 4

Let $\mathcal {F}''\subsetneq \mathcal {F}$. If $y_0$ is not algebraic relatively to $(\mathcal {F}'',\mathcal {G})$, we denote $l:=|\mathcal {F}''|$ and $q:=\min \left\{ k_l\ |\ Q_{\underline{k},\mathcal {F}''}(c_1,c_2,\ldots )\ne 0,\ \underline{k}=(k_1,\ldots ,k_l)\right\}$. We denote by p the index in $M_{\mathcal {F}'',\mathcal {G}}$ of the $q^{th}$ row of $M_{\mathcal {F}'',\mathcal {G}}^{red}$. Then, for any polynomial

$$\begin{aligned} Q(x,y)=\displaystyle \sum _{(i,j)\in \mathcal {F}''\cup \mathcal {G}}b_{i,j}x^iy^j \end{aligned}$$

with $b_{i,j}\ne 0$ for some $(i,j)\in \mathcal {F}''$, we have:

$$\begin{aligned} \mathrm {ord}_xQ(x,y_0)\le p\le 2\,d_xd_y, \end{aligned}$$

and the value p is reached for a certain polynomial $Q_0$ of this type.

Proof

By the definition of q, for any $\underline{k}=(k_1,\ldots ,k_l)$ with $k_l<q$, we have $Q_{\underline{k},\mathcal {F}''}(c_1,c_2,\ldots )=0$. This means that the rank of the column vectors $V_{i,j,q-1}$ that are the restrictions of those of $M_{\mathcal {F}'',\mathcal {G}}^{red}$ up to the row $q-1$, is less than $l=|\mathcal {F}''|$. There are coefficients $(a_{i,j})_{(i,j)\in \mathcal {F}''}$ not all zero such that $\sum \nolimits _{(i,j)\in \mathcal {F}''}a_{i,j}V_{i,j,q-1}=0$. By computing the coefficients $a_{n,0}$ for $(n,0)\in \mathcal {G}$ via relations (1):

$$\begin{aligned} a_{n,0}=-\displaystyle \sum _{(i,j)\in \mathcal {F}'', n>i} a_{i,j}c_{n-i}^{(j)}, \end{aligned}$$

(9)

we obtain the vanishing of the $p-1$ first terms of $Q_0(x,y_0):=\sum \nolimits _{(i,j)\in \mathcal {F}''\cup \mathcal {G}}a_{i,j}x^i(y_0)^j$. Thus, $\mathrm {ord}_xQ_0(x,y_0)\ge p$, and so $p\le 2\,d_xd_y$. On the other hand, again by the definition of q, the column vectors $V_{i,j,q}$, $(i,j)\in \mathcal {F}''$, up to the row q are, in turn, of rank $l=|\mathcal {F}''|$. This means that the rank of the matrix $M_{\mathcal {F}'',\mathcal {G},q}^{red}$ consisting of the q first rows of $M_{\mathcal {F}'',\mathcal {G}}^{red}$ is l. Thus, for any nonzero vector $(b_{i,j})_{(i,j)\in \mathcal {F}''}$, we have:

$$\begin{aligned} M_{\mathcal {F}'',\mathcal {G},q}^{red}\,\cdot \, (b_{i,j})_{(i,j)\in \mathcal {F}''}\ne 0. \end{aligned}$$

But the components of this nonzero vector, up to a change of indexes, are exactly the coefficients $e_k$, $(k,0)\notin \mathcal {G}$ and $k\le p$, of the expansion of $\sum \nolimits _{(i,j)\in \mathcal {F}''}b_{i,j}\,x^i\,(y_0)^j$. Now, these terms of the latter series do not overlap with the terms of $\sum \nolimits _{(i,0)\in \mathcal {G}}b_{i,0}\,x^i$. Therefore, for a given polynomial $Q(x,y)=\sum \nolimits _{(i,j)\in \mathcal {F}''\cup \mathcal {G}}b_{i,j}x^iy^j$ with $b_{i,j}\ne 0$ for some $(i,j)\in \mathcal {F}''$, the series $Q(x,y_0)$ has a nonzero term $e_k$ with $k\le p$, $(k,0)\notin \mathcal {G}$. Hence, $\mathrm {ord}_xQ(x,y_0)\le p$.

We achieve the proof of Theorem 2 via Lemmas 3 and 4 by considering for a given algebraic series $y_0$ a family $\mathcal {F}'\subset \mathcal {F}$ minimal among the families such that $y_0$ is algebraic relatively to $(\mathcal {F}',\mathcal {G})$. We consider an associated nonzero Wilczynski polynomial $Q_{\underline{k}_0,\underline{I}_0}$ as in (3) with $N_{y_0}$ as defined in Formula (6) minimal. Taking $\mathcal {F}''=\underline{I}_0$, Lemma 4 applies and $N_{y_0}=q$. So $N_{y_0}\le p\le N=2\,d_xd_y$.

Recall that the coefficients $a_{i,j}$ constructed in the first part of the proof are homogenous polynomials in $\mathbb {Z}[C_1,\ldots ,C_{N_{y_0}}]\subseteq \mathbb {Z}[C_1,\ldots ,C_{N}]$. To complete the proof of Theorem 2, let us describe a finite set $\varLambda$ which enumerates all possible reconstruction formulas. Let $M_N$ be the matrix obtained from $M_{\mathcal {F},\mathcal {G}}^{red}$ by taking its first $N=2d_xd_y$ rows. So $M_N$ is a $N\times |\mathcal {F}|$-matrix. Let $\nu$ be the number of minors of order less or equal to $\min \{N;|\mathcal {F}|-1\}$ of $M_N$. We fix a finite set $\varLambda$ of cardinality $|\mathcal {F}|+\nu$. Its first $|\mathcal {F}|$ elements are the indexes of reconstruction formulas (2) as built in the first part of the proof of Theorem 2 (case $m=|\mathcal {F}'|=1$). The other $\nu$ elements are used to enumerate reconstruction formulas (2) in the case described in the second part of the proof (case $m=|\mathcal {F}'|\ge 2$).

Construction of the coefficients $a_{i,j}^{(\lambda )}(c_1,c_2,\ldots )$ for a given $y_0$.

Let $y_0$ be algebraic relatively to $(\mathcal {F},\mathcal {G})$ as in Definition 1. Let $N=2\,d_xd_y$ as in Theorem 2. Recall that $M_N$ denotes the matrix consisting in the N first rows of $M_{\mathcal {F},\mathcal {G}}^{red}$. Let r be the rank of $M_N$, and $m:=r+1$. The minors of $M_N$ of order m are all zero and there exists a minor of order $m-1=r$ which is nonzero. There are two cases. If $r=0$, we choose $(i,j)\in \mathcal {F}$ and we fix the coefficients $a_{i,j}:=1$ and $a_{l,m}=0$ for $(l,m)\in \mathcal {F}$, $(l,m)\ne (i,j)$. Then we derive the coefficients $a_{i,0}(c_1,c_2,\ldots )$ for $(i,0)\in \mathcal {G}$ from Relations (1). The polynomials P thus obtained are all annihilators of $y_0$. If $r\ge 1$, we consider all the Wilczynski polynomials $Q_{\underline{k},\underline{I}}$ of order r that do not vanish when evaluated at $c_1,\ldots ,c_N$. Each of them allows to reconstruct coefficients $a_{i,j}^{(\lambda )}(c_1,c_2,\ldots )$, $(i,j)\in \mathcal {F}$, and subsequently coefficients $a_{i,0}(c_1,c_2,\ldots )$, $(i,0)\in \mathcal {G}$, via Relations (1). The corresponding polynomials $P^{(\lambda )}$ are annihilators of $y_0$ if and only if $\mathrm {ord}_x P^{(\lambda )}\left( x,\, \sum \nolimits _{k=1}^{N}c_kx^k\right) >N$.

Remark 2

With the hypothesis and notations of Theorem 2 and its proof, let us denote $f:=|\mathcal {F}|\le (d_x+1)d_y$ and $g:=\min \{N,f-1\}$. Then $|\varLambda |$ is bounded by $f+\sum \nolimits _{t=1}^g{{f}\atopwithdelims (){t}} {{N}\atopwithdelims (){t}}$, which is itself roughly bounded by $f+(2^f-1)(2^N-1)$.

Example 2

We resume Example 1, and note that, for $\underline{I}=((2,1),(2,2))$ and $\underline{k}=(2,3)$, we have that:

$$\begin{aligned} Q_{\underline{k},\underline{I}}= \left| \begin{array}{c@{\quad }c}C _{1} &{} 0 \\ C _{2} &{} \mathrm{C}_{1}^{2} \\ \end{array}\right| =C_1^3\ne 0. \end{aligned}$$

which does not vanish at $c_1\ne 0$. So we set $a_{0,2}:=(-1)^2C_1^3=C_1^3$ and, applying Cramer’s rule:

$$\begin{aligned} \left\{ \begin{array}{lll} a_{2,1}&{}:=&{}(-1)^1 \left| \begin{array}{c@{\quad }c}2\cdot C _{1}\cdot C _{2} &{} 0 \\ C _{2}^{2}+2~C _{1}~C _{3} &{} C_{1}^{2} \\ \end{array}\right| =-2C_1^3C_2 \\ a_{2,2}&{}:=&{}(-1)^3 \left| \begin{array}{c@{\quad }c} C _{1} &{} 2\cdot C _{1}\cdot C _{2}\\ C _{2} &{} C _{2}^{2}+2~C _{1}~C _{3} \\ \end{array}\right| =C_1\left( C_2^2-2C_1C_3\right) . \end{array} \right. \end{aligned}$$

We deduce from formulas (1) that:

$$\begin{aligned} a_{2,0}=-a_{2,1}\cdot 0-a_{0,2}\cdot C_1^2-a_{2,2}\cdot 0=-C_1^5. \end{aligned}$$

A vanishing polynomial of a series $y_0=\sum \nolimits _{n\ge 1} c_nx^{n}\in K[[x]]$, $c_1\ne 0$, algebraic relatively to $\mathcal {F}=\left( (2,1),(0,2),(2,2)\right)$ and $\mathcal {G}=(2,0)$ is:

$$\begin{aligned} P(x,y)= & {} -c_1^5x^2-2c_1^3c_2\,x^2y+c_1^3\,y^2+c_1\left( c_2^2-2c_1c_3\right) x^2y^2\\= & {} c_1\left[ -c_1^4x^2-2c_1^2c_2\,x^2y+c_1^2\,y^2+\left( c_2^2-2c_1c_3\right) x^2y^2\right] .\\ \end{aligned}$$

Remark 3

• (i) Let $y_0$ be an algebraic series with vanishing polynomial of degree $d_x$ in x and $d_y$ in y. According to [1, Chap. 7], the method of reconstruction of equation based on Hermite-Padé approximants provides a priori only polynomials $P(x,y)=\sum \nolimits _{i\le d_x,\ j\le d_y} a_{i,j}x^iy^j$ such that $P(x,y_0)\equiv 0\, [x^\sigma ]$ with $\sigma =(d_x+1)(d_y+1)-1$. Subsequently, one has to check whether $P(x,y_0)=0$ actually. By our Lemma 3, one can always certify that $P(x,y_0)=0$ just by verifying that $P(x,y_0)\equiv 0\, [x^\tau ]$ with $\tau =2d_xd_y$. Hence this reconstruction method as implemented in the GFUN package in Maple software holds for any equation of degree less than $d_x$ in x and $d_y$ in y, not for only irreducible ones as in [1, Theorem 8, p. 110].

• (ii) Theorem 2 provides an alternative to the Hermite-Padé reconstruction process. However, its algorithmic interest may be limited by the a priori big size of the finite set $\varLambda$. But, for a given $(\mathcal {F},\mathcal {G})$, generically, any minor of $M_N$ of order $\min \{|\mathcal {F}|-1,2d_xd_y\}$ is nonzero. So any reconstruction formula (2) corresponding to such nonzero minor holds true.

• (iii) Let us consider the case where $y_0$ is a rational fraction:

  $$\begin{aligned} y_0= & {} \displaystyle \frac{-a_0(x)}{a_1(x)}=\displaystyle \frac{-a_{1,0}x-\cdots -a_{d_0,0}x^{d_0}}{1+a_{1,1}x+\cdots +a_{d_1,1}x^{d_1}}\\= & {} \displaystyle \sum _{n\ge 1}c_n x^n\ \text { with }\ c_1\ne 0. \end{aligned}$$

  Thus, $y_0$ is algebraic relatively to $\mathcal {F}=\left\{ (0,1),\ldots ,(d_1,1)\right\}$ and $\mathcal {G}=\left\{ (1,0),\ldots ,\right.$ $\left. (d_0,0)\right\}$. The Wilczynski polynomials of order $|\mathcal {F}|=d_1+1$ evaluated at the $c_n$’s are all zero. The evaluation of the Wilczynski polynomial $Q_{\underline{k}_0,\underline{I}_0}$ of order $d_1$ with $\underline{I}_0=((1,1),\ldots ,(d_1,1))$ and $\underline{k}_0=(1,\ldots ,d_1)$ is equal, up to the sign, to the resultant of $a_0(x)$ and $a_1(x)$, by [11, Chap. 12 (1.15), p. 401].

• (iv) In the present section, the field K can be of any characteristic.

4 Closed-form expression of an algebraic series

Let us assume from now on that K has characteristic zero. Our purpose is to determine the coefficients of an algebraic series in terms of the coefficients of a vanishing polynomial. We consider the following polynomial of degrees bounded by $d_x$ in x and $d_y$ in y:

$$\begin{aligned} P(x,y)= & {} \displaystyle \sum _{i=0}^{d_x}\displaystyle \sum _{j=0}^{d_y}a_{i,j}x^iy^j ,\ \text { with } P(x,y)\in K[x,y]\\= & {} \displaystyle \sum _{i=0}^{d_x}\pi ^P_{i}(y)x^i\\= & {} \displaystyle \sum _{j=0}^{d_y}a_{j}(x)y^j, \end{aligned}$$

and a formal power series:

$$\begin{aligned} y_0=\displaystyle \sum _{n\ge 1}c_nx^n, \text { with } y_0\in K[[x]],\ c_1\ne 0. \end{aligned}$$

The field K((x)) is endowed with the x-adic valuation $\text {ord}_x$.

Notation 1

For any $k\in \mathbb {N}$ and for $Q(x,y)=\sum \nolimits _{j=0}^da_j(x)y^j\in K((x))[y]$, we denote:

• $\mathrm {ord}_xQ:=\min \{\mathrm {ord}_x a_j(x),\ j=0,{\ldots },d\}$;

• $z_0:=0$ and for $k\ge 1$, $z_k:=\sum \nolimits _{n=1}^{k}c_nx^n$;

• $y_k:=y_0-z_k=\sum \nolimits _{n\ge k+1}c_nx^n$;

• $Q_k(x,y):=Q(x,z_k+x^{k+1}y)=\sum \nolimits _{i=i_k}^{d_k}\pi ^Q_{k,i}(y)x^i$ where $i_k=\mathrm {ord}_x Q_k$ and $d_k:=\deg _xQ_k$. Note that the sequence $(i_k)_{k\in \mathbb {N}}$ is nondecreasing since $Q_{k+1}(x,y)=Q_k(x,c_{k+1}+xy)$.

Classically (e.g. [18]), reducing to the case where $y_0$ is a simple root, the resolution of $P=0$ with the Newton–Puiseux method is algorithmic, with two stages:

• (i) a first stage of separation of the branches solutions, which illustrates the following fact: $y_0$ may share a principal part with other roots of P. This is equivalent to the fact that this principal part is also the principal part of a root of $\partial P/\partial y$.

• (ii) a second stage of unique “automatic” resolution: once the branches are separated, the remaining part of $y_0$ is a root of an equation called Henselian in the formal valued context ($y_0$ seen as an algebraic formal power series), and called of implicit function type in the context of differentiable functions ($y_0$ seen as the convergent Taylor’s expansion of an algebraic function).

We give here a version of the algebraic content of this algorithmic resolution.

Lemma 5

• (i) The series $y_0$ is a root of P(x, y) if and only if the sequence $(i_k)_{k\in \mathbb {N}^*}$ is strictly increasing where $i_k=\mathrm {ord}_x P_k$.

• (ii) The series $y_0$ is a simple root of P(x, y) if and only if the sequence $(i_k)_{k\in \mathbb {N}^*}$ is strictly increasing and there exists a lowest index $k_0$ such that $i_{k_0+1}=i_{k_0}+1$. In that case, one has that $i_{k+1}=i_k+1$ for any $k\ge k_0$.

Proof

(i) Note that for any k, $i_k\le \text {ord}_xP_k(x,0)=\text {ord}_xP(x,z_k)$. Hence, if the sequence $(i_k)_{k\in \mathbb {N}^*}$ is strictly increasing, it tends to $+\infty$, and so does $\text {ord}_xP(x,z_k)$. The series $y_0$ is indeed a root of P(x, y). Reciprocally, suppose that there exist $1\le k<l$ such that $i_k\ge i_l$. Since the sequence $(i_n)_{n\in \mathbb {N}}$ is nondecreasing, one has that $i_l\ge i_k$, so $i_l=i_k$. We apply Taylor’s formula to $P_j(x,y)$ for $j>k$:

$$\begin{aligned} P_j(x,y)= & {} P_k(x,c_{k+1}+c_{k+2}x+\cdots +x^{j-k}y)\nonumber \\= & {} \pi ^P_{k,i_k}(c_{k+1})x^{i_k}+\left[ (\pi ^P_{k,i_k})'(c_{k+1})c_{k+2}+\pi ^P_{k,i_k+1}(c_{k+1})\right] x^{i_k+1}+\cdots .\nonumber \\ \end{aligned}$$

(10)

For $j=l$, we deduce that $\pi ^P_{k,i_k}(c_{k+1})\ne 0$. This implies for any $j>k$, that $i_j=i_k$ and $\text {ord}_xP_j(x,0)=\text {ord}_xP(x,z_j)=i_k$. Hence $\text {ord}_xP(x,y_0)=i_k\ne +\infty$.

(ii) The series $y_0$ is a double root of P if and only if it is a root of P and $\partial P/\partial y$. We apply Taylor’s formula for certain $k\in \mathbb {N}^*$:

$$\begin{aligned} P_{k+1}(x,y)= & {} P_k(x,c_{k+1}+xy)\nonumber \\= & {} \pi ^P_{k,i_k}(c_{k+1})x^{i_k}+\left[ (\pi ^P_{k,i_k})'(c_{k+1})y+\pi ^P_{k,i_k+1}(c_{k+1})\right] x^{i_k+1}\nonumber \\&+\left[ \displaystyle \frac{(\pi ^P_{k,i_{k}})''(c_{k+1})}{2}y^2+(\pi ^P_{k,i_{k}+1})'(c_{k+1})\,y+\pi ^P_{k,i_{k}+2}(c_{k+1})\right] x^{i_k+2}\nonumber \\&+\cdots .\end{aligned}$$

(11)

Note that:

$$\begin{aligned} \displaystyle \frac{\partial P_k}{\partial y}(x,y)=x^{k+1}\left( \displaystyle \frac{\partial P}{\partial y}\right) _k(x,y)=\displaystyle \sum _{i=i_k}^{d_k}(\pi ^P_{k,i})'(y)x^i \end{aligned}$$

One has that $\pi ^P_{k,i_k}{\not \!\!{\equiv }}0$ and $\pi ^P_{k,i_k}(c_{k+1})=0$ (see the point (i) above), so $(\pi ^P_{k,i_k})'(y){\not \!\!{\equiv }}0$. Thus $\mathrm {ord}_x\left( \frac{\partial P}{\partial y}\right) _k=i_k-k-1$. We perform the Taylor’s expansion of $\left( \frac{\partial P}{\partial y}\right) _{k+1}=\left( \displaystyle \frac{\partial P}{\partial y}\right) _k(x,c_{k+1}+x\,y)$:

$$\begin{aligned} \left( \displaystyle \frac{\partial P}{\partial y}\right) _{k+1}(x,y)= & {} (\pi ^P_{k,i_k})'(c_{k+1})x^{i_k-k-1}\\&\quad +\left[ (\pi ^P_{k,i_k})''(c_{k+1})y+(\pi ^P_{k,i_k+1})' (c_{k+1})\right] x^{i_k-k}+\cdots . \end{aligned}$$

By the point (i) applied to $\displaystyle \frac{\partial P}{\partial y}$, if $y_0$ is a double root of P, we must have $(\pi ^P_{k,i_k})'(c_{k+1})=0$. Moreover, if $\pi ^P_{k,i_k+1}(c_{k+1})\ne 0$, by formula (11) we would have $i_{k+1}=i_k+1$ and even $i_{k+j}=i_k+1$ for every j according to formula (10): $y_0$ could not be a root of P. So, $\pi ^P_{k,i_k+1}(c_{k+1})= 0$, and, accordingly, $i_{k+1}\ge i_k+2$.

If $y_0$ is a simple root of P, from the point (i) and its proof applied to $\displaystyle \frac{\partial P}{\partial y}$, there exists a lowest natural number $k_0$ such that the sequence $(i_k-k-1)_{k\in \mathbb {N}^*}$ is no longer strictly increasing, or equivalently $i_{k+1}=i_k+1$, that is, such that $(\pi ^P_{k_0,i_{k_0}})'(c_{k_0+1})\ne 0$. For any $k\ge k_0$, we consider the Taylor’s expansion of $\left( \frac{\partial P}{\partial y}\right) _{k+1}(x,y)=\left( \frac{\partial P}{\partial y}\right) _{k_0}(x,c_{k_0+1}+\cdots +x^{k-k_0+1}y)$:

$$\begin{aligned} \left( \displaystyle \frac{\partial P}{\partial y}\right) _{k+1}(x,y)= & {} (\pi ^P_{k_0,i_{k_0}})'(c_{k_0+1})x^{i_{k_0}-k_0-1}\nonumber \\&+\left[ (\pi ^P_{k_0,i_{k_0}})''(c_{k_0+1})c_{k_0+2}\right. \nonumber \\&\left. +\,(\pi ^P_{k_0,i_{k_0}+1})' (c_{k_0+1})\right] x^{i_{k_0}-k_0}+\cdot \cdot \end{aligned}$$

(12)

and we get that:

$$\begin{aligned} \mathrm {ord}_x\displaystyle \frac{\partial P}{\partial y}(x,z_{k+1})=\mathrm {ord}_x\left( \displaystyle \frac{\partial P}{\partial y}\right) _{k+1}(x,0)=\mathrm {ord}_x\left( \displaystyle \frac{\partial P}{\partial y}\right) _{k+1}=i_{k_0}-k_0-1. \end{aligned}$$

(13)

As $(\pi ^P_{k+1,i_{k+1}})'(y){\not \!\!{\equiv }}0$, we obtain that $i_{k+1}=\mathrm {ord}_xP_{k+1}=\mathrm {ord}_x\left( \frac{\partial P_{k+1}}{\partial y}\right) =k+2+\mathrm {ord}_x\left( \frac{\partial P}{\partial y}\right) _{k+1}=i_{k_0}+k-k_0+1$. Hence, the sequence $(i_k)_{k\ge k_0}$ increases one by one.

Resuming the notations of Lemma 5, the natural number $k_0$ represents the length of the principal part in the stage of separation of the branches. In the following lemma, we bound it using Lemma 3 or the discriminant $\varDelta _P$ of P.

Lemma 6

Let $y_0=\sum \nolimits _{n\ge 1}c_nx^n,\ c_1\ne 0$, be a simple root of a polynomial P(x, y) with $\deg _x (P)\le d_x$ and $\deg _y(P)\le d_y$. The natural number $k_0$ of Lemma 5 verifies that:

$$\begin{aligned} k_0\le 2d_x d_y. \end{aligned}$$

In particular, if P has only simple roots:

$$\begin{aligned} k_0\le d_x(2\,d_y-1). \end{aligned}$$

Proof

By Lemma 3, since $P(x,y_0)=0$ and $\displaystyle \frac{\partial P}{\partial y}(x,y_0)\ne 0$, one has that:

$$\begin{aligned} \mathrm {ord}_x \displaystyle \frac{\partial P}{\partial y}(x,y_0)\le 2d_xd_y. \end{aligned}$$

But, by definition of $k_0$ and by formula (13), we obtain:

$$\begin{aligned} \mathrm {ord}_x \displaystyle \frac{\partial P}{\partial y}(x,z_{k+1}) =\mathrm {ord}_x\displaystyle \frac{\partial P}{\partial y}(x,z_{k_0+1}) =i_{k_0}-k_0-1 \end{aligned}$$

for any $k\ge k_0$. So, $\mathrm {ord}_x \displaystyle \frac{\partial P}{\partial y}(x,y_0)=\mathrm {ord}_x\displaystyle \frac{\partial P}{\partial y}(x,z_{k_0+1})$. Moreover, by minimality of $k_0$, the sequence $(i_k-k-1)_k$ is strictly increasing up to $k_0$, so:

$$\begin{aligned} \mathrm {ord}_x \displaystyle \frac{\partial P}{\partial y}(x,y_0)= & {} \mathrm {ord}_x\displaystyle \frac{\partial P}{\partial y}(x,z_{k_0+1})\\= & {} \mathrm {ord}_x\left( \displaystyle \frac{\partial P}{\partial y}\right) _{k_0+1}(x,0)\ge \mathrm {ord}_x\left( \displaystyle \frac{\partial P}{\partial y}\right) _{k_0+1}\ge k_0. \end{aligned}$$

Hence we obtain as desired that:

$$\begin{aligned} k_0\le 2d_x d_y. \end{aligned}$$

In the case where P has only simple roots, as in the proof of Lemma 3, $\mathrm {ord}_x \displaystyle \frac{\partial P}{\partial y}(x,y_0)$ is bounded by the degree of the resultant of P and $\displaystyle \frac{\partial P}{\partial y}$, say the discriminant $\varDelta _P$ of P, which is bounded by $d_x(2\,d_y-1)$.

Notation 2

Resuming Notation 1 and the content of Lemma 5, we set:

$$\begin{aligned} \omega _0:=(\pi ^P_{k_0,i_{k_0}})'(c_{k_0+1}). \end{aligned}$$

By formula (12), we note that:

$$\begin{aligned} \left( \displaystyle \frac{\partial P}{\partial y}\right) (x,y_0)=\omega _0x^{i_{k_0}-k_0-1}+\cdots . \end{aligned}$$

Thus, $\omega _0$ is the initial coefficient of $\left( \frac{\partial P}{\partial y}\right) (x,y_0)$, hence $\omega _0\ne 0$.

Theorem 3

Consider the following polynomial in K[x, y] of given degrees $d_x$ in x and $d_y$ in y:

$$\begin{aligned} P(x,y)=\displaystyle \sum _{i=0}^{d_x}\displaystyle \sum _{j=0}^{d_y}a_{i,j}x^iy^j = \displaystyle \sum _{i=0}^{d_x}\pi ^P_{i}(y)x^i, \end{aligned}$$

and a formal power series which is a simple root:

$$\begin{aligned} y_0=\displaystyle \sum _{n\ge 1}c_nx^n\ \in K[[x]],\ c_1\ne 0. \end{aligned}$$

Resuming Notations 1 and 2, and the content of Lemma 5, we recall that

$\omega _0:=(\pi ^P_{k_0,i_{k_0}})'(c_{k_0+1})\ne 0$. Then, for any $k>k_0$:

• either the polynomial $z_{k+1}=\sum \nolimits _{n=1}^{k+1}c_nx^n$ is a solution of $P(x,y)=0$;

• or the polynomial $_k R(x,y):=\frac{P_k(x,y+c_{k+1})}{-\omega _0x^{i_k}}=-y\ +\ _kQ(x,y)$ defines a reduced Henselian equation:

  $$\begin{aligned} y\ =\ _kQ(x,y) \end{aligned}$$

  with $_kQ(0,y)\equiv 0$ and satisfied by:

  $$\begin{aligned} t_{k+1}:=\frac{y_0-z_{k+1}}{x^{k+1}}=c_{k+2}x+c_{k+3}x^2+\cdots . \end{aligned}$$

Proof

We show by induction on $k>k_0$ that $_kR(x,y)=-y+x\, _kT(x,y)$ with $_kT(x,y)\in K[x,y]$. The initial step of the induction is for $k=k_0+1$. Let us apply Formula (11) with parameter $k=k_0$. Since $i_{k_0+1}=i_{k_0}+1$, we have that $\pi ^P_{k_0,i_{k_0}}(c_{k_0+1})=0$ and accordingly:

$$\begin{aligned} P_{k_0+1}(x,y)=\left[ \omega _0\,y+\pi ^P_{k_0,i_{k_0}+1}(c_{k_0+1})\right] x^{i_{k_0}+1}+\cdots . \end{aligned}$$

Since $i_{k_0+2}=i_{k_0}+2$, $\pi ^P_{k_0+1,i_{k_0}+1}(y)=\omega _0\,y+\pi ^P_{k_0,i_{k_0}+1}(c_{k_0+1})$ vanishes at $c_{k_0+2}$, which implies that $c_{k_0+2}=\displaystyle \frac{-\pi ^P_{k_0,i_{k_0}+1}(c_{k_0+1})}{\omega _0}$. Computing $_{k_0+1}R(x,y):=\displaystyle \frac{P_{k_0+1}(x,y+c_{k_0+2})}{-\omega _0x^{i_k}}$, it follows that:

$$\begin{aligned} _{k_0+1}R(x,y)=-y+\, _{k_0+1}Q(x,y) , \end{aligned}$$

with $_{k_0+1}Q(x,y)$ being equal to:

$$\begin{aligned}&\displaystyle \frac{x}{-\omega _0}\left[ \displaystyle \frac{(\pi ^P_{k,i_{k_0}})''(c_{k_0+1})}{2}(y+c_{k_0+2})^2\right. \\&\quad \left. +\,(\pi ^P_{k_0,i_{k_0}+1})'(c_{k_0+1})\,(y+c_{k_0+2})+\pi ^P_{k_0,i_{k_0}+2}(c_{k_0+1})\right] +\displaystyle \frac{x^2}{-\omega _0}[\cdots ]. \end{aligned}$$

So $_{k_0+1}Q(0,y)\equiv 0$.

Suppose that the property holds true at a rank $k\ge k_0+1$, which means that $_kR(x,y):=\displaystyle \frac{P_k(x,y+c_{k+1})}{-\omega _0x^{i_k}}=-y+x\, _kT(x,y)$. Therefore, for $_k\tilde{T}:=-\omega _0\, _kT(x,y-c_{k+1})\in K[x,y]$, we can write:

$$\begin{aligned} P_k(x,y)= & {} \omega _0(y-c_{k+1})x^{i_k}+x^{i_k+1}\, _k\tilde{T}(x,y)\\= & {} \pi ^P_{k,i_k}(y)x^{i_k}+\pi ^P_{k,i_k+1}(y)x^{i_k+1}+ \cdots . \end{aligned}$$

In particular, $\pi ^P_{k,i_k}(y)=\omega _0(y-c_{k+1})$. Since $P_{k+1}(x,y)=P_k(x,c_{k+1}+xy)$, we have:

$$\begin{aligned} P_{k+1}(x,y)=\left[ \omega _0\,y+\pi ^P_{k,i_k+1}(c_{k+1})\right] x^{i_k+1}+\pi ^P_{k+1,i_k+2}(y)x^{i_k+2}+\cdots . \end{aligned}$$

Now, $\pi ^P_{k+1,i_k+1}(y)=\omega _0\,y+\pi ^P_{k,i_k+1}(c_{k+1})$. But $i_k+2=i_{k+2}>i_{k+1}=i_k+1$. So we must have $\pi ^P_{k+1,i_k+1}(c_{k+2})=0$. So, $c_{k+2}=\displaystyle \frac{-\pi ^P_{k,i_k+1}(c_{k+1})}{\omega _0}$. It follows that:

$$\begin{aligned} P_{k+1}(x,y)=\omega _0(y-c_{k+2})x^{i_k+1}+\pi ^P_{k+1,i_k+2}(y)x^{i_k+2}+\cdots . \end{aligned}$$

Hence:

$$\begin{aligned} _{k+1}R(x,y):= & {} \displaystyle \frac{P_{k+1}(x,y+c_{k+2})}{-\omega _0x^{i_{k+1}}}\\= & {} -y-x\displaystyle \frac{\pi ^P_{k+1,i_k+2}(y+c_{k+2})}{\omega _0}+x^2[\cdots ]+\cdots \\= & {} -y+x\cdot \ _{k+1}T(x,y),\ \ \ \ _{k+1}T\in K[x,y], \end{aligned}$$

as desired.

In particular, $_{k}Q(0,0)=\displaystyle \frac{\partial \, _{k}Q}{\partial y}(0,0)=0$. So the equation $y =\, _kQ(x,y)$ is reduced Henselian if and only if $_kQ(x,0){\not \!\!{\equiv }}0$, which is equivalent to $z_{k+1}$ not being a root of P.

We will need the following lemma:

Lemma 7

Let $y_0$ be a simple root of a nonzero polynomial P(x, y) of degrees $\deg _x(P)\le d_x$ and $\deg _y(P)\le d_y$. For $y_1\ne y_0$ any other root of P, one has that:

$$\begin{aligned} \mathrm {ord}_x(y_0-y_1)\le 2\,d_xd_y. \end{aligned}$$

Proof

Note that the hypothesis imply that $d_y\ge 2$. Let us write $y_1-y_0=x^k\,\delta _{1,0}$ where $k:=\mathrm {ord}_x(y_1-y_0)$ and $\delta _{1,0}\in K[[x]]{\setminus }\{0\}$. By Taylor’s Formula, we have:

$$\begin{aligned} P(x,y_0+x^k\delta _{1,0})= & {} 0\\= & {} P(x,y_0)+\displaystyle \frac{\partial P}{\partial y}(x,y_0)x^k\delta _{1,0}+\cdots +\displaystyle \frac{1}{d_y!}\displaystyle \frac{\partial ^{d_y} P}{\partial y^{d_y}}(x,y_0)x^{kd_y}\delta _{1,0}^{d_y}\\= & {} x^k\delta _{1,0}\left( \displaystyle \frac{\partial P}{\partial y}(x,y_0)+\cdots +\displaystyle \frac{1}{d_y!}\displaystyle \frac{\partial ^{d_y} P}{\partial y^{d_y}}(x,y_0)x^{k(d_y-1)}\delta _{1,0}^{d_y-1}\right) . \end{aligned}$$

Since $x^k\delta _{1,0}\ne 0$ and $\displaystyle \frac{\partial P}{\partial y}(x,y_0)\ne 0$, one has that:

$$\begin{aligned} \displaystyle \frac{\partial P}{\partial y}(x,y_0)=-x^k\delta _{1,0}\left( \displaystyle \frac{1}{2}\displaystyle \frac{\partial ^2 P}{\partial y^2}(x,y_0)+\cdots +\displaystyle \frac{1}{d_y!}\displaystyle \frac{\partial ^{d_y} P}{\partial y^{d_y}}(x,y_0)x^{k(d_y-2)}\delta _{1,0}^{d_y-2}\right) \end{aligned}$$

The order of the right hand side being at least k, we obtain that:

$$\begin{aligned} \mathrm {ord}_x\left( \displaystyle \frac{\partial P}{\partial y}(x,y_0)\right) \ge k. \end{aligned}$$

But, by Lemma 3, we must have $\mathrm {ord}_x\left( \displaystyle \frac{\partial P}{\partial y}(x,y_0)\right) \le 2d_xd_y$. So $k\le 2d_xd_y$.

For the courageous reader, in the case where $y_0$ is a series which is not a polynomial, we deduce from Theorem 3 and from Flajolet–Soria’s Formula 1 a closed-form expression for the coefficients of $y_0$ in terms of the coefficients $a_{i,j}$ of P and of the coefficients of an initial part $z_k$ of $y_0$ sufficiently large. For any $k\ge 2d_xd_y+1$, recall that $i_k=\mathrm {ord}_x P_k$.

Corollary 1

For any $k\ge 2d_xd_y+1$, for any $p\ge 1$, one has that:

$$\begin{aligned} c_{k+1+p}=\displaystyle \sum _{q=1}^p\displaystyle \frac{1}{q}\left( \displaystyle \frac{-1}{\omega _0}\right) ^q\displaystyle \sum _{|S|=q,\ \Vert S\Vert _2\ge q-1}A^S\left( \displaystyle \mathop {\mathop {\sum }\limits _{|T_S|=\Vert S\Vert _2-q+1}}\limits _{\Vert T_S\Vert =p+qi_k-(q-1)(k+1)-\Vert S\Vert _1}e_{T_S}C^{T_S}\right) , \end{aligned}$$

where $S=(s_{i,j})$, $A^S={\mathop {\mathop {\prod }\limits _{i=0,\ldots ,d_x , j=0,\ldots ,d_y}}}a_{i,j}^{s_{i,j}}$, $T_S=(t_{S,i})$, $C^{T_S}=\prod \nolimits _{i=1}^{k+1}c_i^{t_{S,i}}$, and $e_{T_S}\in \mathbb {N}$ is of the form:

$$\begin{aligned}&e_{T_S}=\displaystyle \sum _{\left( n^{l,m}_{i,j,L}\right) }\left( \displaystyle \frac{q!}{\displaystyle {\mathop {\mathop {\prod }\limits _{l=1,\ldots ,(k+1)d_y+d_x-i_k}}\limits _{m=0,\ldots ,m_l}} \displaystyle {\mathop {\mathop {\prod }\limits _{i=0,\ldots ,d_x}}\limits _{j=m,\ldots ,d_y}}\displaystyle {\mathop {\mathop {\prod }\limits _{|L|=j-m }}\limits _{\Vert L\Vert =l+i_k-m(k+1)-i}}n^{l,m}_{i,j,L}!}\right. \nonumber \\&\left. \quad \displaystyle {\mathop {\mathop {\prod }\limits _{l=1,\ldots ,(k+1)d_y+d_x-i_k}}\limits _{m=0,\ldots ,m_l}}\displaystyle {\mathop {\mathop {\prod }\limits _{i=0,\ldots ,d_x}}\limits _{j=m,\ldots ,d_y}}\displaystyle {\mathop {\mathop {\prod }\limits _{|L|=j-m }}\limits _{\Vert L\Vert =l+i_k-m(k+1)-i}}\left( \displaystyle \frac{j!}{m!\,L!}\right) ^{n^{l,m}_{i,j,L}}\right) , \end{aligned}$$

where $m_l:=\min \left\{ \left\lfloor \frac{l+i_k}{k+1}\right\rfloor ,d_y\right\}$, $L=L_{i,j}^{l,m}=\left( l_{i,j,1}^{l,m},\ldots ,l_{i,j,k+1}^{l,m}\right)$, and where the sum is taken over the set of sequences $\mathop {\left( n^{l,m}_{i,j,L}\right) }\nolimits _{\begin{array}{c} l=1,\ldots ,(k+1)d_y+d_x-i_k,\ m=0,\ldots ,m_l \\ i=0,\ldots ,d_x,\ j=m,\ldots ,d_y,\ |L|=j-m,\ \Vert L\Vert =l+i_k-m(k+1)-i \end{array}}$ such that:

$$\begin{aligned} \displaystyle \sum _{l,m}\displaystyle \sum _{L}n^{l,m}_{i,j,L}=s_{i,j}, \ \ \displaystyle \sum _{l,m}\displaystyle \sum _{i,j}\displaystyle \sum _{L}n^{l,m}_{i,j,L}=q\ \ \ and \ \ \ \displaystyle \sum _{l,m}\displaystyle \sum _{i,j}\displaystyle \sum _{L}n^{l,m}_{i,j,L}L=T_S. \end{aligned}$$

Remark 4

Note that the coefficients $e_{T_S}$ are indeed natural numbers, since they are sums of products of multinomial coefficients because $\sum \nolimits _{l,m}\sum \nolimits _{i,j}\sum \nolimits _{L}n^{l,m}_{i,j,L}=q$ and $m+|L|=j$.

Proof

We get started by computing the coefficients of $\omega _0x^{i_k}\, _kR$, in order to get those of $_kQ$:

$$\begin{aligned} -\omega _0x^{i_k}\, _kR= & {} P_k(x,\,y+c_{k+1})\\= & {} P(x,z_{k+1}+x^{k+1}y)\\= & {} \displaystyle \sum _{i=0,\ldots ,d_x\, ,\ j=0,\ldots ,d_y}a_{i,j}x^i\left( z_{k+1}+x^{k+1}y\right) ^{j}\\= & {} \displaystyle \sum _{i=0,\ldots ,d_x\, ,\ j=0,\ldots ,d_y}a_{i,j}x^i\displaystyle \sum _{m=0}^{j}\displaystyle \frac{j!}{m!\,(j-m)!}z_{k+1}^{j-m}x^{m(k+1)}y^m. \end{aligned}$$

For $L=(l_1,\ldots ,l_{k+1})$, we denote $C^L:=c_1^{l_1}\cdots c_{k+1}^{l_{k+1}}$. One has that:

$$\begin{aligned} z_{k+1}^{j-m}=\displaystyle \sum _{|L|=j-m}\displaystyle \frac{(j-m)!}{L!}C^Lx^{\Vert L\Vert }. \end{aligned}$$

So:

$$\begin{aligned} -\omega _0x^{i_k}\, _kR=\displaystyle \sum _{m=0}^{d_y} \displaystyle {\mathop {\mathop {\sum }\limits _{i=0,\ldots ,d_x}}\limits _{ j=m,\ldots ,d_y}} a_{i,j}\displaystyle \sum _{|L|=j-m}\displaystyle \frac{j!}{m!\,L!}C^Lx^{\Vert L\Vert +m(k+1)+i}y^m. \end{aligned}$$

We set $\hat{l}=\Vert L\Vert +m(k+1)+i$, which ranges between $m(k+1)$ and $(k+1)(d_y-m)+m(k+1)+d_x=(k+1)d_y+d_x$. Thus:

$$\begin{aligned} -\omega _0x^{i_k}\, _kR=\displaystyle {\mathop {\mathop {\sum }\limits _{m=0,\ldots ,d_y}}\limits _{\hat{l}=m(k+1),\ldots ,(k+1)d_y+d_x}} \displaystyle {\mathop {\mathop {\sum }\limits _{i=0,\ldots ,d_x }}\limits _{j=m,\ldots ,d_y}a_{i,j}}\displaystyle {\mathop {\mathop {\sum }\limits _{{|L|=j-m}}}\limits _{\Vert L\Vert =\hat{l}-m(k+1)-i}}\displaystyle \frac{j!}{m!\,L!}C^Lx^{\hat{l}}y^m. \end{aligned}$$

Since $_kR(x,y)=-y+\, _kQ(x,y)$ with $_kQ(0,y)\equiv 0$, the coefficients of $_kQ$ are obtained for $\hat{l}=i_k+1,\ldots ,(k+1)d_y+d_x$. We set $l:=\hat{l}-i_k$, $m_l:=\min \left\{ \left\lfloor \frac{l+i_k}{k+1}\right\rfloor ,d_y\right\}$ and we obtain:

$$\begin{aligned} _kQ(x,y)=\displaystyle {\mathop {\mathop {\sum }\limits _{l=1,\ldots ,(k+1)d_y+d_x-i_k}}\limits _{m=0,\ldots ,m_l}}b_{l,m}x^ly^m, \end{aligned}$$

with:

$$\begin{aligned} b_{l,m}=\displaystyle \frac{-1}{\omega _0}\displaystyle {\mathop {\mathop {\sum }\limits _{i=0,\ldots ,d_x}}\limits _{j=m,\ldots ,d_y}}a_{i,j}\displaystyle {\mathop {\mathop {\sum }\limits _{|L|=j-m}}\limits _{\Vert L\Vert =l+i_k-m(k+1)-i}}\displaystyle \frac{j!}{m!\,L!}C^L. \end{aligned}$$

According to Lemmas 6, 7 and Theorem 3, we are in position to apply the version in Remark 1 of Flajolet–Soria’s Formula in order to compute the coefficients of $t_{k+1}=c_{k+2}x+c_{k+3}x^2+\cdots$. Thus, denoting $B:=(b_{l,m})$, $Q:=(q_{l,m})$ and $B^Q:=\prod \nolimits _{l,m} b_{l,m}^{q_{l,m}}$ for $l=1,\ldots ,(k+1)d_y+d_x-i_k$ and $m=0,\ldots ,m_l$, we obtain:

$$\begin{aligned} c_{k+1+p}=\displaystyle \sum _{q=1}^p\displaystyle \frac{1}{q}\displaystyle \sum _{|Q|=q,\, \Vert Q\Vert _1=p,\,\Vert Q\Vert _2=q-1}\displaystyle \frac{q!}{Q!}B^Q. \end{aligned}$$

Let us compute:

$$\begin{aligned} b_{l,m}^{q_{l,m}}= & {} \left( \displaystyle \frac{-1}{\omega _0}\right) ^{q_{l,m}}\left( \displaystyle {\mathop {\mathop {\sum }\limits _{i=0,\ldots ,d_x}}\limits _{j=m,\ldots ,d_y}}a_{i,j}\displaystyle {\mathop {\mathop {\sum }\limits _{|L|=j-m }}\limits _{\Vert L\Vert =l+i_k-m(k+1)-i}}\displaystyle \frac{j!}{m!\,L!}C^L\right) ^{q_{l,m}}\nonumber \\= & {} \left( \displaystyle \frac{-1}{\omega _0}\right) ^{q_{l,m}}\displaystyle \sum _{|M_{l,m}|=q_{l,m}}\left( \displaystyle \frac{q_{l,m}!}{M_{l,m}!} A^{M_{l,m}}\displaystyle \right. \nonumber \\&\quad \left. {\mathop {\mathop {\prod }\limits _{i=0,\ldots ,d_x }}\limits _{j=m,\ldots ,d_y}}\left( \displaystyle {\mathop {\mathop {\sum }\limits _{|L|=j-m}}\limits _{\Vert L\Vert =l+i_k-m(k+1)-i}}\displaystyle \frac{j!}{m!\,L!}C^L\right) ^{m^{l,m}_{i,j}}\right) \nonumber \\&\text { where } M_{l,m}=(m^{l,m}_{i,j})\text { for } i=0,\ldots ,d_x,\ j=0,\ldots ,d_y\text { and }\nonumber \\&\quad&m^{l,m}_{i,j}=0\text { for }j<m. \end{aligned}$$

(14)

Let us expand the expression $\mathop {\prod }\nolimits _{\begin{array}{c} i=0,\ldots ,d_x\\ j=m,\ldots ,d_y \end{array}} \left( \mathop {\sum }\nolimits _{\begin{array}{c} |L|=j-m\\ \Vert L\Vert =l+i_k-m(k+1)-i \end{array}}\frac{j!}{m!\,L!}C^L\right) ^{m^{l,m}_{i,j}}$. For each (l, m, i, j), we enumerate the terms $\displaystyle \frac{j!}{m!\,L!}C^L$ with $u=1,\ldots ,\alpha _{i,j}^{l,m}$. Subsequently:

$$\begin{aligned} \left( \displaystyle {\mathop {\mathop {\sum }\limits _{|L|=j-m}}\limits _{l+i_k-m(k+1)-i}} \displaystyle \frac{j!}{m!\,L!}C^L\right) ^{m^{l,m}_{i,j}}= & {} \left( \displaystyle \sum _{u=1}^{\alpha _{i,j}^{l,m}}\displaystyle \frac{j!}{m!\,L_{i,j,u}^{l,m}!}C^{L_{i,j,u}^{l,m}}\right) ^{m^{l,m}_{i,j}}\\= & {} \displaystyle \sum _{|N^{l,m}_{i,j}|=m^{l,m}_{i,j}}\left( \displaystyle \frac{m^{l,m}_{i,j}!}{N^{l,m}_{i,j}!}\left( \displaystyle \prod _{u=1}^{\alpha _{i,j}^{l,m}}\left( \displaystyle \frac{j!}{m!\,L_{i,j,u}^{l,m}!}\right) ^{n^{l,m}_{i,j,u}}\right) \right. \\&\quad \left. C^{\sum _{u=1}^{\alpha ^{l,m}_{i,j}}n^{l,m}_{i,j,u} L_{i,j,u}^{l,m}}\right) , \end{aligned}$$

where $N^{l,m}_{i,j}=\left( n^{l,m}_{i,j,u}\right) _{u=1,\ldots ,\alpha _{i,j}^{l,m}}$, $N^{l,m}_{i,j}!=\prod \nolimits _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}!$. Denoting $U_{l,m}:=\mathop {\sum }\nolimits _{\begin{array}{c} i=0,\ldots ,d_x\\ j=m,\ldots ,d_y \end{array}}\sum \nolimits _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}L_{i,j,u}^{l,m}$, one computes:

$$\begin{aligned} |U_{l,m}|= & {} \displaystyle {\mathop {\mathop {\sum }\limits _{i=0,\ldots ,d_x}}\limits _{j=m,\ldots ,d_y}} \displaystyle \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}|L_{i,j,u}^{l,m}|\nonumber \\= & {} \displaystyle {\mathop {\mathop {\sum }\limits _{i=0,\ldots ,d_x}}\nolimits _{j=m,\ldots ,d_y}}\left( \displaystyle \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}\right) (j-m)\nonumber \\= & {} \displaystyle {\mathop {\mathop {\sum }\limits _{i=0,\ldots ,d_x}}\nolimits _{j=m,\ldots ,d_y}}m^{l,m}_{i,j}(j-m)\nonumber \\= & {} \Vert M_{l,m}\Vert _2-m\,q_{l,m}. \end{aligned}$$

(15)

Likewise, one computes:

$$\begin{aligned} \Vert U_{l,m}\Vert= & {} \displaystyle {\mathop {\mathop {\sum }\limits _{i=0,\ldots ,d_x}}\limits _{j=m,\ldots ,d_y}}\displaystyle \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}\Vert L_{i,j,u}^{l,m}\Vert \nonumber \\= & {} \displaystyle {\mathop {\mathop {\sum }\limits _{i=0,\ldots ,d_x}}\limits _{j=m,\ldots ,d_y}}\left( \displaystyle \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}\right) (l+i_k-m(k+1)-i)\nonumber \\= & {} \displaystyle {\mathop {\mathop {\sum }\limits _{i=0,\ldots ,d_x}}\limits _{j=m,\ldots ,d_y}}m^{l,m}_{i,j}(l+i_k-m(k+1)-i)\nonumber \\= & {} q_{l,m}[l+i_k-m(k+1)]-\Vert M_{l,m}\Vert _1. \end{aligned}$$

(16)

So, according to formula (14) and the new way of writing the expression

$\mathop {\prod }\nolimits _{\begin{array}{c} i=0,\ldots ,d_x\\ j=m,\ldots ,d_y \end{array}}\left( \mathop {\sum }\nolimits _{\begin{array}{c} |L|=j-m\\ \Vert L\Vert =l+i_k-m(k+1)-i \end{array}} \frac{j!}{m!\,L!}C^L\right) ^{m^{l,m}_{i,j}}$, we obtain:

$$\begin{aligned} b_{l,m}^{q_{l,m}}= & {} \left( \displaystyle \frac{-1}{\omega _0}\right) ^{q_{l,m}}\displaystyle \sum _{|M_{l,m}|=q_{l,m}}A^{M_{l,m}}\displaystyle {\mathop {\mathop {\sum }\limits _{|U_{l,m}|=\Vert M_{l,m}\Vert _2-m\,q_{l,m}}}\limits _{\Vert U_{l,m}\Vert =q_{l,m}[l+i_k-m(k+1)]-\Vert M_{l,m}\Vert _1}}d_{U_{l,m}}C^{U_{l,m}}\\&\text { with }d_{U_{l,m}}:=\displaystyle \sum _{\left( N^{l,m}_{i,j}\right) }\displaystyle \frac{q_{l,m}!}{\displaystyle {\mathop {\mathop {\prod }\limits _{i=0,\ldots ,d_x}}\limits _{j=m,\ldots ,d_y}}N^{l,m}_{i,j}!}\displaystyle {\mathop {\mathop {\prod }\limits _{i=0,\ldots ,d_x}}\limits _{j=m,\ldots ,d_y}}\displaystyle \prod _{u=1}^{\alpha _{i,j}^{l,m}}\left( \displaystyle \frac{j!}{m!\,L_{i,j,u}^{l,m}!}\right) ^{n^{l,m}_{i,j,u}}, \end{aligned}$$

where the sum is taken over

$$\begin{aligned} \left\{ {\mathop {\mathop {\left( N^{l,m}_{i,j}\right) }\limits _{i=0,\ldots ,d_x}}\limits _{ j=m,\ldots ,d_y}}\text { such that }|N^{l,m}_{i,j}|=m^{l,m}_{i,j}\text { and }\displaystyle {\mathop {\mathop {\sum }\limits _{i=0,\ldots ,d_x}}\limits _{ j=m,\ldots ,d_y}}\sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}L_{i,j,u}^{l,m}=U_{l,m}\right\} . \end{aligned}$$

(Note that, if the latter set is empty, then $d_{U_{l,m}}=0$.)

We deduce that:

$$\begin{aligned} B^{Q}= & {} \prod _{l=1,\ldots ,(k+1)d_y+d_x-i_k,\, m=0,\ldots ,m_l}b_{l,m}^{q_{l,m}}\\= & {} \left( \displaystyle \frac{-1}{\omega _0}\right) ^{q}\displaystyle \prod _{l,m}\left[ \sum _{|M_{l,m}|=q_{l,m}}A^{M_{l,m}}{\mathop {\mathop {\sum }\limits _{U_{l,m}|=\Vert M_{l,m}\Vert _2-m\,q_{l,m}}}\limits _{\Vert U_{l,m}\Vert =q_{l,m}[l+i_k-m(k+1)]-\Vert M_{l,m}\Vert _1}}d_{U_{l,m}}C^{U_{l,m}}\right] . \end{aligned}$$

Now, in order to expand the latter product of sums, we consider the corresponding sets:

$$\begin{aligned} \mathcal {S}_Q:=\left\{ \sum _{l,m}M_{l,m}\ \ / \ \ \forall l,m,\ |M_{l,m}|=q_{l,m}\text { and }\ m^{l,m}_{i,j}=0\text { for }j<m\right\} \end{aligned}$$

and, for any $S\in \mathcal {S}_Q$,

$$\begin{aligned} \mathcal {U}_{Q,S}{:=}&\left\{ \left( U_{l,m}\right) \ \ / \ \ \exists (M_{l,m})\ \mathrm {s.t.}\ |M_{l,m}|=q_{l,m}\text { and } \ m^{l,m}_{i,j}=0\right. \\&\left. \text { for }j<m,\ \sum _{l,m}M_{l,m}=S, |U_{l,m}|=\Vert M_{l,m}\Vert _2-m\,q_{l,m} \text { and }\Vert U_{l,m}\Vert \right. \\&\left. =q_{l,m}[l+i_k-m(k+1)]-\Vert M_{l,m}\Vert _1 \displaystyle \frac{}{}\right\} \end{aligned}$$

and

$$\begin{aligned} \mathcal {T}_{Q,S}:=\left\{ \displaystyle \sum _{l,m}U_{l,m} \ \ / \ \ \left( U_{l,m}\right) \in \mathcal {U}_{Q,S} \right\} . \end{aligned}$$

We have:

$$\begin{aligned} B^Q= & {} \left( \displaystyle \frac{-1}{\omega _0}\right) ^{q}\displaystyle \sum _{S\in \mathcal {S}_Q}A^{S}\displaystyle \sum _{T_S\in \mathcal {T}_{Q,S}} \left( \displaystyle \sum _{\begin{aligned}&\left( U_{l,m}\right) \in \mathcal {U}_{Q,S},\\&\Sigma _{l,m}U_{l,m}=T_S\end{aligned}}\displaystyle \prod _{l,m}d_{U_{l,m}}\right) \mathcal {C}^{T_S}\nonumber \\= & {} \left( \displaystyle \frac{-1}{\omega _0}\right) ^{q}\displaystyle \sum _{S\in \mathcal {S}_Q}A^{S}\displaystyle \sum _{T_S\in \mathcal {T}_{Q,S}}e_{Q,T_S}C^{T_S}. \end{aligned}$$

(17)

where:

$$\begin{aligned} e_{Q,T_S}:=\displaystyle \sum _{\left( N^{l,m}_{i,j}\right) }\displaystyle \frac{\displaystyle \prod _{l,m}q_{l,m}!}{\displaystyle \prod _{l,m}\displaystyle \prod _{i,j}N^{l,m}_{i,j}!}\displaystyle \prod _{l,m} \displaystyle \prod _{i,j}\displaystyle \prod _{u}\left( \displaystyle \frac{j!}{m!\,L_{i,j,u}^{l,m}!}\right) ^{n^{l,m}_{i,j,u}} \end{aligned}$$

and where the previous sum is taken over:

$$\begin{aligned} \mathcal {E}_{Q,T_S}{:=}&\left\{ {\mathop {\mathop { \left( N^{l,m}_{i,j}\right) }\limits _{ l=1,\ldots ,(k+1)d_y+d_x-i_k,\, m=0,\ldots ,m_l }}\limits _{ i=0,\ldots ,d_x,\ j=m,\ldots ,d_y}}\ \ /\ \right. \\&\quad \left. \displaystyle \sum _{l,m}\sum _{u=1}^{\alpha _{i,j}^{l,m}} n^{l,m}_{i,j,u}=s_{i,j},\ \forall l,m,\ \displaystyle \sum _{i,j}|N^{l,m}_{i,j}|=q_{l,m},\right. \\&\left. \text { and } \displaystyle \sum _{l,m} \displaystyle \sum _{i,j} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}L_{i,j,u}^{l,m} =T_S \ \right\} . \end{aligned}$$

where $S=(s_{i,j})$.

Note that, for any Q and for any $S\in \mathcal {S}_Q$, $|S|=\sum \nolimits _{l,m}q_{l,m}=q$ and $\Vert S\Vert _2\ge \sum \nolimits _{l,m}mq_{l,m}=\Vert Q\Vert _2=q-1$. Moreover, for any $T_S\in \mathcal {T}_{Q,S}$:

$$\begin{aligned} |T_S|= & {} \displaystyle \sum _{l,m} \Vert M_{l,m}\Vert _2-m\,q_{l,m}\\= & {} \Vert S\Vert _2-\Vert Q\Vert _2\\= & {} \Vert S\Vert _2-q+1 \end{aligned}$$

and:

$$\begin{aligned} \Vert T_S\Vert= & {} \displaystyle \sum _{l,m}q_{l,m}[l+i_k-m(k+1)]-\Vert M_{l,m}\Vert _1\\= & {} \Vert Q\Vert _1+|Q|i_k-\Vert Q\Vert _2(k+1)-\Vert S\Vert _1\\= & {} p+qi_k-(q-1)(k+1)-\Vert S\Vert _1. \end{aligned}$$

Now, let us show that:

$$\begin{aligned}&\displaystyle \sum _{|Q|=q,\, \Vert Q\Vert _1=p,\,\Vert Q\Vert _2=q-1}\displaystyle \frac{q!}{Q!}B^{Q}= \left( \displaystyle \frac{-1}{\omega _0}\right) ^{q}\left( \displaystyle \sum _{|S|=q,\, \Vert S\Vert _2\ge q-1}A^{S}\right. \nonumber \\&\quad \displaystyle \left. {\mathop {\mathop {\sum }\limits _{|T_S|=\Vert S\Vert _2-q+1}}\limits _{\Vert T_S\Vert =p+qi_k-(q-1)(k+1)-\Vert S\Vert _1}}e_{T_S}C^{T_S}\right) , \end{aligned}$$

(18)

where $e_{T_S}:=\sum \nolimits _{\left( N^{l,m}_{i,j}\right) }\frac{q!}{\displaystyle \prod \nolimits _{l,m}\prod \nolimits _{i,j}N^{l,m}_{i,j}!}\prod \nolimits _{l,m} \prod \nolimits _{i,j}\prod \nolimits _{u}\left( \frac{j!}{m!\,L_{i,j,u}^{l,m}!}\right) ^{n^{l,m}_{i,j,u}}$ and where the sum is taken over

$$\begin{aligned} \mathcal {E}_{T_S}:=\left\{ {\mathop {\mathop {\left( N^{l,m}_{i,j}\right) }\limits _{l=1,\ldots ,(k+1)d_y+d_x-i_k,\, m=0,\ldots ,m_l }}\limits _{i=0,\ldots ,d_x,\ j=m,\ldots ,d_y}}\ \ /\ \ \displaystyle \sum _{l,m}\sum _{u=1}^{\alpha _{i,j}^{l,m}} n^{l,m}_{i,j,u}=s_{i,j},\ \displaystyle \sum _{l,m}\displaystyle \sum _{i,j}|N^{l,m}_{i,j}|=q\right. \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left. \text { and } \displaystyle \sum _{l,m}\displaystyle \sum _{i,j} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}L_{i,j,u}^{l,m}=T_S\right\} . \end{aligned}$$

(Note that, if the latter set is empty, then $e_{T_S}=0$.)

Recall that $N^{l,m}_{i,j}!=\prod \nolimits _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}!$ and that the $L^{l,m}_{i,j,u}$’s enumerate the L’s such that $|L|=j-m$ and $\Vert L\Vert =l+i_k-m(k+1)-i$ for given l, m, i, j.

Let us consider S and $T_S$ such that $|S|=q,\, \Vert S\Vert _2\ge q-1$, $|T_S|=\Vert S\Vert _2-q+1,\ \Vert T_S\Vert =p+qi_k-(q-1)(k+1)-\Vert S\Vert _1$ and such that $\mathcal {E}_{T_S}\ne \emptyset$. Take an element $( n^{l,m}_{i,j,u})\in \mathcal {E}_{T_S}$. Define $m^{l,m}_{i,j}:=\sum \nolimits _{u=1}^{\alpha _{i,j}^{l,m}} n^{l,m}_{i,j,u}$ for each $i,\,j,\,l,\,m$ with $j\ge m$, and $m^{l,m}_{i,j}:=0$ if $j<m$. Set $M_{l,m}:=(m^{l,m}_{i,j})_{i,j}$ for each $l,\,m$. So, $\sum \nolimits _{l,m}m^{l,m}_{i,j}=\sum \nolimits _{l,m}\sum \nolimits _{u=1}^{\alpha _{i,j}^{l,m}} n^{l,m}_{i,j,u}=s_{i,j}$, and $S=\sum \nolimits _{l,m}M_{l,m}$. Define $q_{l,m}:=\sum \nolimits _{i,j}m^{l,m}_{i,j}=|M_{l,m}|$ for each $l,\,m$, and $Q:=(q_{l,m})$. Let us show that $|Q|=q$, $\Vert Q\Vert _1=p$ and $\Vert Q\Vert _2=q-1$. By definition of $\mathcal {E}_{T_S}$,

$$\begin{aligned} |Q|:=\displaystyle \sum _{l,m}q_{l,m}= \displaystyle \sum _{l,m}\displaystyle \sum _{i,j} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}=q.\end{aligned}$$

Recall that $\Vert Q\Vert _2:=\sum \nolimits _{l,m}mq_{l,m}$. We have:

$$\begin{aligned}&|T_S|= \left| \displaystyle \sum _{l,m}\displaystyle \sum _{i,j} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}L_{i,j,u}^{l,m}\right| =\Vert S\Vert _2 -q+1\\ \Leftrightarrow&\displaystyle \sum _{l,m}\displaystyle \sum _{i,j} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}|L_{i,j,u}^{l,m}|=\displaystyle \sum _{i,j}js_{i,j}-q+1\\ \Leftrightarrow&\displaystyle \sum _{l,m}\displaystyle \sum _{i,j} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}(j-m)=\displaystyle \sum _{i,j}js_{i,j}-q+1\\ \Leftrightarrow&\displaystyle \sum _{i,j} j\displaystyle \sum _{l,m} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}-\displaystyle \sum _{l,m}m\displaystyle \sum _{i,j} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}=\displaystyle \sum _{i,j}js_{i,j}-q+1\\ \Leftrightarrow&\displaystyle \sum _{i,j} js_{i,j}-\displaystyle \sum _{l,m}mq_{l,m} =\displaystyle \sum _{i,j}js_{i,j}-q+1\\ \Leftrightarrow&\Vert Q\Vert _2=q-1. \end{aligned}$$

Recall that $\Vert Q\Vert _1:=\sum \nolimits _{l,m}lq_{l,m}$. We have:

$$\begin{aligned} \Vert T_S\Vert= & {} \left\| \displaystyle \sum _{l,m}\displaystyle \sum _{i,j} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}L_{i,j,u}^{l,m}\right\| =p+qi_k -(q-1)(k+1) -\Vert S\Vert _1\\\Leftrightarrow & {} \displaystyle \sum _{l,m}\displaystyle \sum _{i,j} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}\Vert L_{i,j,u}^{l,m}\Vert =p+qi_k -(q-1)(k+1) -\Vert S\Vert _1\\\Leftrightarrow & {} \displaystyle \sum _{l,m}\displaystyle \sum _{i,j} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}(l+i_k -m(k+1) -i)\\&\quad =p+qi_k -(q-1)(k+1) -\Vert S\Vert _1\\\Leftrightarrow & {} \displaystyle \sum _{l,m}l\displaystyle \sum _{i,j} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}+ i_k \displaystyle \sum _{l,m}\displaystyle \sum _{i,j} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}\\&\quad -(k+1) \displaystyle \sum _{l,m}m\displaystyle \sum _{i,j} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u} -\displaystyle \sum _{i,j}i \displaystyle \sum _{l,m} \sum _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u} \\&\quad =p+qi_k -(q-1)(k+1) -\Vert S\Vert _1 \\\Leftrightarrow & {} \displaystyle \sum _{l,m}lq_{l,m}+i_k\cdot q\\&\quad -(k+1)\displaystyle \sum _{l,m}mq_{l,m}-\displaystyle \sum _{i,j} is_{i,j}=p+qi_k -(q-1)(k+1) -\Vert S\Vert _1 \\\Leftrightarrow & {} \Vert Q\Vert _1+qi_k-\Vert Q\Vert _2(k+1)-\Vert S\Vert _1=p+qi_k -(q-1)(k+1) -\Vert S\Vert _1. \end{aligned}$$

Since $\Vert Q\Vert _2=q-1$, we deduce that $\Vert Q\Vert _1=p$ as desired. So, $S\in \mathcal {S}_Q$ for Q as in the left-hand side of (18).

Now, set $U_{l,m}:=\sum \nolimits _{i,j} \sum \nolimits _{u=1}^{\alpha _{i,j}^{l,m}}n^{l,m}_{i,j,u}L_{i,j,u}^{l,m}$, so $\sum \nolimits _{l,m}U_{l,m}=T_S$. Let us show that $(U_{l,m})\in \mathcal {U}_{Q,S}$, which implies that $T_S\in \mathcal {T}_{Q,S}$ as desired. The existence of $(M_{l,m})$ such that $|M_{l,m}|=q_{l,m}\text { and } \ m^{l,m}_{i,j}=0\text { for }j<m$ and $\sum \nolimits _{l,m}M_{l,m}=S$ follows by construction. Conditions $|U_{l,m}|=\Vert M_{l,m}\Vert _2-m\,q_{l,m} \text { and }\Vert U_{l,m}\Vert =q_{l,m}[l+i_k-m(k+1)]-\Vert M_{l,m}\Vert _1$ are obtained exactly as in (15) and (16). This shows that $(n^{l,m}_{i,j,u}) \in \mathcal {E}_{Q,T_S}$, so:

The reverse inclusion holds trivially since $|Q|=q$, so:

We deduce that:

$$\begin{aligned} e_{T_S}=\displaystyle \sum _{|Q|=q,\, \Vert Q\Vert _1=p,\,\Vert Q\Vert _2=q-1}\displaystyle \frac{q!}{Q!} e_{Q,T_S}. \end{aligned}$$

We conclude that any term occuring in the right-hand side of (18) comes from a term from the left-hand side.

Conversely, for any Q as in the left-hand side of Formula (18), $S\in \mathcal {S}_Q$ and $T_S \in \mathcal {T}_{Q,S}$ verify the following conditions:

$$\begin{aligned} |S|= & {} q,\ \ \Vert S\Vert _2\ge q-1,\ \ |T_S|=\Vert S\Vert _2-q+1 ,\ \\&\Vert T_S\Vert =p+qi_k-(q-1)(k+1)-\Vert S\Vert _1 \end{aligned}$$

and

Hence, any term occuring in the expansion of $B^Q$ contributes to the right hand side of formula (18).

Thus we obtain formula (18) from which the statement of Corollary 1 follows.

Remark 5

We have seen in Theorem 3 and its proof (see Formula (11) with $k=k_0$) that $\omega _0=(\pi ^P_{k_0,i_{k_0}})'(c_{k_0+1})$ is the coefficient of the monomial $x^{i_{k_0}+1}y$ in the expansion of $P_{k_0+1}(x,y)=P(x,c_1x+\cdots +c_{k_0+1}x^{k_0+1}+x^{k_0+2}y)$, and that $c_{k_0+2}=\displaystyle \frac{-\pi ^P_{k_0,i_{k_0}+1}(c_{k_0+1})}{\omega _0}$ where $\pi ^P_{k_0,i_{k_0}+1}(c_{k_0+1})$ is the coefficient of $x^{i_{k_0}+1}$ in the expansion of $P_{k_0+1}(x,y)$. Expanding $P_{k_0+1}(x,y)$, having done the whole computations, we deduce that:

$$\begin{aligned}\left\{ \begin{array}{lll} \omega _0&{}=&{}\displaystyle \sum _{i=0,{\ldots },d_x,\ j=1,{\ldots },d_y}\ \ \displaystyle \sum _{|L|=j-1,\ \Vert L\Vert =i_{k_0}-i-k_0-1}\displaystyle \frac{j!}{L!}a_{i,j}C^L\ ;\\ c_{k_0+2}&{}=&{} \displaystyle \frac{-1}{\omega _0}\displaystyle \sum _{i=0,{\ldots },d_x,\ j=0,{\ldots },d_y}\ \ \displaystyle \sum _{|L|=j,\ \Vert L\Vert =i_{k_0}-i+1}\ \ \displaystyle \frac{j!}{L!}a_{i,j}C^L. \end{array}\right. \end{aligned}$$

Example 3

In order to illustrate Corollary 1 and its proof, we resume the polynomial of Example 1 with $a_{0,2}\ne 0$:

$$\begin{aligned} P(x,y)= & {} a_{0,2}y^2+\left( a_{2,0} +a_{2,1}y+a_{2,2}y^2\right) x^2\\ P_0(x,y)= & {} \left( a_{2,0}+a_{0,2}y^2\right) x^2+a_{2,1}yx^3+a_{2,2}y^2x^4\\ P_1(x,y)= & {} \left( 2a_{0,2}c_1y+a_{2,1}c_1\right) x^3+\left( a_{0,2}y^2+a_{2,1}y+a_{2,2}c_1^2\right) x^4 \\&+\,2a_{2,2}c_1yx^5+a_{2,2}y^2x^6\\&\text {with }a_{2,0}+a_{0,2}c_1^2=0\,\Leftrightarrow \, c_1=\pm \sqrt{\displaystyle \frac{-a_{2,0}}{a_{0,2}}}. \end{aligned}$$

Thus, $i_0=2$, $i_1=3=i_0+1$, so $k_0=0$, $\omega _0=2\,a_{0,2}\,c_1$. The coefficient $c_2$ must verify $2a_{0,2}c_1c_2+a_{2,1}c_1=0\, \Leftrightarrow \, c_2=\displaystyle \frac{-a_{2,1}}{2a_{0,2}}$. We obtain that:

$$\begin{aligned} -\omega _0\, _1R= & {} \displaystyle \frac{P_1(x,y+c_2)}{x^3}\\= & {} \omega _0y+ \left( a_{{2,2}}{c_{{1}}}^{2}+ a_{{2,1}}c_{{2}}+a_{{0,2}}{c_{{2 }}}^{2}+\left( a_{{2,1}}+2\,a_{{0,2}}c_{{2}}\right) y+a_{{0,2}}{y}^{2} \right) {x}\\&+ \left( 2\,a_{{2,2}}c_{{1}}c_{{2}}+2\,a_{{2,2}}c_{{1} }y \right) {x}^{2}+ \left( a_{{2,2}}{c_{{2}}}^{2}+2\,a_{{2,2}}c_{{2}}y+a_{{2,2}}{y}^{2} \right) {x}^{3}. \end{aligned}$$

So the coefficients of the corresponding reduced Henselian equation $y=\, _1Q(x,y)$ are:

$$\begin{aligned} \begin{array}{lll} b_{1,0}=-\left( a_{{2,2}}{c_{{1}}}^{2}+ a_{{2,1}}c_{{2}}+a_{{0,2}}{c_{{2 }}}^{2}\right) /\omega _0,&b_{1,1}=-\left( a_{{2,1}}+2\,a_{{0,2}}c_{{2}}\right) /\omega _0=0, \end{array}\\ \begin{array}{lll} b_{1,2}=-a_{{0,2}}/\omega _0,&{} b_{2,0}= -2\,a_{{2,2}}c_{{1}}c_{{2}}/\omega _0,&{} b_{2,1}=-2\,a_{{2,2}}c_{{1}}/\omega _0,\\ b_{3,0}=-a_{{2,2}}{c_{{2}}}^{2}/\omega _0, &{}b_{3,1}=-2\,a_{{2,2}}c_{{2}}/\omega _0, &{}b_{3,2}=-a_{{2,2}}/\omega _0, \end{array} \end{aligned}$$

But, by version 1 of Flajolet–Soria’s Formula 1, one has that:

$$\begin{aligned} c_3= & {} b_{1,0}=\displaystyle \frac{- a_{{2,2}}{c_{{1}}}^{2}- a_{{2,1}}c_{{2}}-a_{{0,2}}{c_{{2 }}}^{2} }{2\,a_{0,2}\,c_1};\\ c_4= & {} b_{2,0}+b_{1,0}b_{1,1}=b_{2,0}=\displaystyle \frac{-2\,a_{{2,2}}c_{{1}}c_{{2}}}{2\,a_{0,2}\,c_1};\\ c_5= & {} b_{3,0}+b_{1,0}b_{2,1}+b_{1,0}^2b_{1,2}+b_{1,0}b_{1,1}^2+b_{2,0}b_{1,1}=b_{3,0}+b_{1,0}b_{2,1} +b_{1,0}^2b_{1,2}\\= & {} \displaystyle \frac{-a_{2,2}\,{c_2}^2}{2\,a_{0,2}\,c_1}+ \displaystyle \frac{2\,a_{{2,1}}a_{{2,2}}c_{{1}}c_{{2}}+2\,a_{{0,2}}a_{{2,2}}c_{{1}}{c_{{2 }}}^{2}+2\,{a_{{2,2}}}^{2}{c_{{1}}}^{3} }{\left( 2\,a_{0,2}\,c_1\right) ^2}\,-\\&\displaystyle \frac{a_{{0,2}}{a_{{2,1}}}^{2}{c_{{2}}}^{2}+2\,{a_{{0,2}}}^{2}a_{{2,1}}{c_{{2}}}^{3}+2\,a_{{0,2}}a_{{2,1}}a_{{2,2}}{c_{{1}}}^{2}c_{{2}}+{a_{{0,2}} }^{3}{c_{{2}}}^{4} }{\left( 2\,a_{0,2}\,c_1\right) ^3}\\&-\displaystyle \frac{2\,{a_{{0,2}}}^{2}a_{{2,2}}{c_{{1}}}^{2}{c_{{2}}}^{ 2}+a_{{0,2}}{a_{{2,2}}}^{2}{c_{{1}}}^{4} }{\left( 2\,a_{0,2}\,c_1\right) ^3};\\ \ \ \ \vdots \end{aligned}$$

Remark 6

Classically, a series $y_0=\sum \nolimits _{n\ge 0} c_nx^n\in K[[x]]$ is algebraic if and only if its coefficients $c_n$ are the diagonal coefficients of the power series expansion of a bivariate rational fraction [7, 10]. In particular, in the reduced Henselian case $y=Q(x,y)$ (see Definition 2), the rational fraction can be written:

$$\begin{aligned}y_0=\mathrm {Diag}\left( \displaystyle \frac{y^2-y^2\displaystyle \frac{\partial Q}{\partial y}(xy,y)}{y-Q(xy,y)}\right) .\end{aligned}$$

With the computations in the proof of Corollary 1, we can deduce in the general case $P(x,y)=0$ a formula for the rational fraction having the $c_n$ as diagonal coefficients of its expansion.

As a consequence of Theorem 2 and Corollary 1, we get the following result. Let $d_x$, $d_y$ be some fixed degrees, and an integer $n>2d_xd_y+2$. There is a finite number of universal polynomial formulas which compute the coefficient $c_n$ of any algebraic series $y_0$ of degrees at most $d_x$, $d_y$. These formulas are evaluated at the first $2d_xd_y+2$ first coefficients of $y_0$, and their number is independent of n. More precisely:

Corollary 2

Let $d_x,d_y\in \mathbb {N}^*$. We set $M:=\displaystyle \frac{1}{2}d_y(d_y+1)(d_x+1)+d_y-2$ and $\mu :=N+2=2d_xd_y+2$. There exists a finite set $\varLambda$ and for any $\lambda \in \varLambda$, there exist a polynomial $\varOmega ^{(\lambda )}(C_1,\ldots ,C_\mu )\in \mathbb {Z}[C_1,\ldots ,C_\mu ]$, $\deg \varOmega ^{(\lambda )}\le M$, and for every $p\in \mathbb {N}^*$, a polynomial $\varPsi ^{(\lambda )}_p(C_1,\ldots ,C_{\mu +1})\in \mathbb {Z}[C_1,\ldots ,C_{\mu +1}]$, $\deg \varPsi ^{(\lambda )}_p\le p(M+d_x)+1$, such that for every $y_0=\sum \nolimits _{n\ge 1}c_nx^n$, $c_1\ne 0$, algebraic with vanishing polynomial of degrees bounded by $d_x$ in x and $d_y$ in y, there exists $\lambda \in \varLambda$ such that for every $p\in \mathbb {N}^*$:

$$\begin{aligned} c_{\mu +1+p}=\displaystyle \frac{\varPsi ^{(\lambda )}_p(c_1,\ldots ,c_{\mu +1})}{\varOmega ^{(\lambda )}(c_1,\ldots ,c_\mu )^p}.\end{aligned}$$

Proof

Let $y_0=\sum \nolimits _{n\ge 1}c_nx^n$, $c_1\ne 0$, be algebraic with vanishing polynomial of degree bounded by $d_x$ in x and $d_y$ in y. According to Theorem 2, there is a finite set $\varLambda$ and for every $\lambda \in \varLambda$, polynomials $a^{(\lambda )}_{i,j}(C_1,\ldots ,C_N)\in \mathbb {Z}[C_1,\ldots ,C_N]$ such that:

$$\begin{aligned}P^{(\lambda )}=\displaystyle \sum _{i\le d_x,j\le d_y}a_{i,j}^{(\lambda )}(c_1,\ldots ,c_N)x^iy^j\end{aligned}$$

is a vanishing polynomial for $y_0$ for a certain $\lambda \in \varLambda$. Enlarging the finite set $\varLambda$ by indices corresponding to the various $\displaystyle \frac{\partial ^k P^{(\lambda )}}{\partial y^k}$, $k=1,\ldots ,d_y-1$, we can assume that there is $\lambda$ such that $y_0$ is a simple root of $P^{(\lambda )}$. So the coefficients of $y_0$ can be computed as in Corollary 1. More precisely, for any $p\in \mathbb {N}^*$:

$$\begin{aligned} c_{\mu +1+p}= \sum _{q=1}^p \sum _{S\in I_q} \sum _{T_S\in J_S}\frac{m_{S,T_S}}{\omega _0^p} \omega _0^{p-q}A^S C^{T_S} \end{aligned}$$

(19)

where $I_q=\left\{ (s_{i,j})\ |\ |S|=q,\ \Vert S\Vert _2\ge q-1\right\}$,

$$\begin{aligned} J_S=\left\{ (t_{S,i})\ |\ |T_S|=\Vert S\Vert _2-q+1,\ \Vert T_S\Vert =p+qi_\mu - (q-1)(\mu +1)-\Vert S\Vert _1\right\} \end{aligned}$$

and $m_{S,T_S}\in \mathbb {Z}$. Note that $C=(c_1,\ldots ,c_{\mu +1})$ and $A=(a_{i,j}(c_1,\ldots ,c_N))$. It suffices to bound the degrees of the numerator and denominator in the terms of formula (19). By Theorem 2, $\deg a_{i,j}^{(\lambda )}\le M+d_x+1-d_y$. So by Remark 5 and Theorem 2, we deduce that $\omega _0$ is the evaluation of a polynomial $\varOmega ^{(\lambda )}(C_1,\ldots ,C_\mu )$ such that $\deg \varOmega ^{(\lambda )}\le M$. The degree $d_{q,S}$ corresponding to a term $\omega _0^{p-q}A^S C^{T_S}$ is bounded by:

$$\begin{aligned}&(p-q)M+|S|(M+d_x+1-d_y)+|T_S|\\&\quad =(p-q)M+q(M+d_x+1-d_y)+\Vert S\Vert _2-q+1. \end{aligned}$$

But, $\Vert S\Vert _2\le qd_y$ and $1\le q\le p$. So we get that:

$$\begin{aligned} d_{q,S}\le (p-q)M+q(M+d_x+1-d_y)+qd_y-q+1\le p(M+d_x)+1 \end{aligned}$$