logarithmic space complexity for performing this construction follows from the
fact that the construction of a new gate depends only on a constant number of
original or already constructed gates.

In the next lemma we iteratively apply Lemma B.11 to achieve closure under
$\Delta_{w}$ when reading an arbitrary word $w\in\Sigma^{*}$. The complexity
is exponential in the length of $w$. See 2.10

######  Proof B.13.

Let $C$ be an circuit of size $n$ containing gates $G_{a,i}$’s computing
polynomials $\Delta_{a}X_{i}\in\mathbb{Q}[N]$ for all $1\leq i\leq k$, and a
gate $D$ computing $\alpha$. An inductive application of Lemma B.11
immediately shows the following claim. For every word $w\in\Sigma^{*}$ we can
construct a circuit $C_{w}$ of size $\leq 4^{\left|w\right|}\cdot n$ s.t. for
every gate $G$ of $C$ there is a gate $G_{w}$ of $C_{w}$ computing

$\displaystyle\left\llbracket G_{w}\right\rrbracket=\Delta_{w}\left\llbracket
G\right\rrbracket.$

By the claim, $C_{w}$ contains in particular a gate $D_{w}$ computing
$\Delta_{w}\alpha$. Step $i+1$ of the construction can be done in space
logarithmic in the size $\leq 4^{i}\cdot n$ of the circuit obtained in the
previous step, and thus altogether polynomial in $\left|w\right|$ and
logarithmic in $n$.

####  B.2.2 Decidability

In this section we provide more details on the decidability of the WBPP
zeroness problem. This amounts to prove some important structural properties
of the ideal chain 6.

See 2.12

######  Proof B.14.

For the first point, let $p\in\Delta_{a}I_{n}$. Then $p=\Delta_{a}q$ for some
$q\in I_{n}$ of the form

$\displaystyle
q=\beta_{1}\cdot\Delta_{w_{1}}\alpha+\cdots+\beta_{m}\cdot\Delta_{w_{m}}\alpha,\quad\text{with
}w_{1},\dots,w_{m}\in\Sigma^{\leq n}.$

Applying $\Delta_{a}$ to both sides of the equation above and using the fact
that by 4 $\Delta_{a}(\alpha\cdot\beta)$ is a polynomial function of $\alpha$,
$\beta$, $\Delta_{a}\alpha$, and $\Delta_{a}\beta$, we easily deduce
$\Delta_{a}q\in I_{n+1}$.

Let us now consider the second point. The “$\supseteq$” inclusion follows
immediately from the definitions and the previous point. For the reverse
“$\subseteq$” inclusion, let $p\in I_{n+1}$. We can write

$\displaystyle
p=\beta_{1}\cdot\Delta_{w_{1}}\alpha+\cdots+\beta_{m}\cdot\Delta_{w_{m}}\alpha,\quad\text{with
}w_{1},\dots,w_{m}\in\Sigma^{\leq n+1}.$

It is now a matter of partitioning the $w_{i}$’s into two classes: In the
first class we put those words in $\Sigma^{\leq n}$ and in the second one
those in $\Sigma^{n+1}$. We re-index the $w_{i}$’s in order to have the words
from the first class appear first. Let $k$ be the size of the first class. We
can write

$\displaystyle
p=\underbrace{\beta_{1}\cdot\Delta_{w_{1}}\alpha+\cdots+\beta_{k}\cdot\Delta_{w_{k}}\alpha}_{\in
I_{n}\
\text{(a)}}+\underbrace{\beta_{k+1}\cdot\Delta_{w_{k+1}}\alpha+\cdots+\beta_{m}\cdot\Delta_{w_{m}}\alpha}_{\in\langle\bigcup_{a\in\Sigma}\Delta_{a}I_{n}\rangle\
\text{(b)}}.$

Point (a) follows directly from the definition of $I_{n}$. For point (b),
notice that $\Delta_{u}\alpha$ for $u$ of length $n+1$ can be written as
$\Delta_{v\cdot a}\alpha=\Delta_{a}\Delta_{v}\alpha$ for $v$ of length $n$,
and thus $\Delta_{u}\alpha\in\Delta_{a}I_{n}$.

The third point is an immediate consequence of the second point.

####  B.2.3 Complexity

In this section we provide the details necessary to establish the elementary
upper bound on the complexity of the WBPP zeroness problem, claimed in Theorem
1.1. In fact, all we need to do is to prove the ideal chain length bound
Theorem 2.16, which is the main technical contribution of the paper. In turn,
it suffices to prove Claim 1. This is done by generalising the argument of
Novikov and Yakovenko [62] from the case of one derivation to the case of a
finite number of derivations, possibly noncommuting. We recall two easy
properties of colon ideals:

  1. 1.

If $I$ is an ideal, then $I\subseteq I:J$.

  2. 2.

The colon operator is monotonic in its first argument and anti-monotonic in
its second argument: $I\subseteq I^{\prime}$ and $J^{\prime}\subseteq J$
implies $I\operatorname{\,:\,}J\subseteq
I^{\prime}\operatorname{\,:\,}J^{\prime}$.

We adapt the proof from [62, Sec. 4] from the setting of a single derivation
to the more general situation of multiple, possible noncommuting, derivations
$\Delta_{a}$, $a\in\Sigma$. We need to recall some definitions. An ideal $I$
is _prime_ if $p\cdot q\in I$ and $p\not\in I$ implies $q\in I$. The _radical_
$\sqrt{I}$ of an ideal $I$ is the set of elements $r$ s.t. $r^{m}\in I$ for
some $m\in\mathbb{N}$. Note that $\sqrt{I}$ is itself an ideal. A _radical
ideal_ is an ideal $I$ s.t. $I=\sqrt{I}$; in other words, $p^{m}\in I$ implies
$p\in I$. An ideal $I$ is _primary_ if $p\cdot q\in I$ and $p\not\in I$
implies $q\in\sqrt{I}$. The radical $\sqrt{I}$ of a primary ideal $I$ is prime
and it is called the _associated prime_ of $I$; in the same situation, we also
say that $I$ is _$\sqrt{I}$ -primary_. The colon operation preserves primary
ideals.

######  Claim 5.

If $I,J$ are ideals with $I$ primary, then $I\operatorname{\,:\,}J$ is also
primary.

######  Proof B.15 (Proof of the claim).

Let $p\cdot q\in I\operatorname{\,:\,}J$ and $p\not\in
I\operatorname{\,:\,}J$. There is $r\in J$ s.t. $p\cdot r\not\in I$. But
$(p\cdot q)\cdot r=(p\cdot r)\cdot q\in I$ and since $I$ is primary, there is
$m\in\mathbb{N}$ s.t. $q^{m}\in I\subseteq I\operatorname{\,:\,}J$.

The _dimension_ $\mathsf{dim}\,{I}$ of a polynomial ideal
$I\subseteq\mathbb{Q}[k]$ is the dimension of its associated variety
$V(I)=\left\\{x\in\mathbb{C}^{k}\;\middle|\;\forall p\in I.p(x)=0\right\\}$.
Since the operation of taking the variety of an ideal is inclusion-reversing,
ideal inclusion is dimension-reversing: $I\subseteq J$ implies
$\mathsf{dim}\,{I}\geq\mathsf{dim}\,{J}$. By Hilbert’s Nullstellensatz [27,
Chapter 4, §1, Theorem 2], an ideal $I$ and its radical $\sqrt{I}$ have the
same associated variety, and thus the dimension of an ideal $I$ its the same
as that of its radical, $\mathsf{dim}\,{I}=\mathsf{dim}\,{\sqrt{I}}$.

A _primary decomposition_ of an ideal $I$ is a collection of primary ideals
$\left\\{Q_{1},\dots,Q_{s}\right\\}$ s.t. $I=Q_{1}\cap\cdots\cap Q_{s}$. Such
a decomposition is _irredundant_ if

  1. 1.

no $Q_{i}$ can be omitted without changing the intersection, and

  2. 2.

the associated primes $\sqrt{Q_{i}}$’s are pairwise distinct.

By the Lasker-Noether theorem [27, Chapter 4, §8, Theorem 7] every polynomial
ideal $I$ has an irredundant primary decomposition. Let the _leading term_ of
an irredundant primary decomposition of $I$ be the intersection of all primary
components of maximal dimension. While irredundant primary decompositions of
an ideal are not unique in general, the leading terms of two irredundant
primary decompositions of the same ideal $I$ are in fact equal. Thus the
leading term, denoted $\mathsf{lt}\,{I}$, depends only on $I$.

Chains of equidimensional ideals induce chains of the respective leading
terms.

######  Claim 6 (variant of [62, Lemma 4]).

If two polynomial ideals $I\subseteq J$ have the same dimension
$\mathsf{dim}\,{I}=\mathsf{dim}\,{J}$, then
$\mathsf{lt}\,{I}\subseteq\mathsf{lt}\,{J}$.

######  Proof B.16 (Proof of the claim).

Write $\mathsf{lt}\,{I}=P_{1}\cap\cdots\cap P_{s}$ where the $P_{i}$’s are the
primary ideals of an irredundant decomposition of $I$ of maximal dimension,
and similarly $\mathsf{lt}\,{J}=Q_{1}\cap\cdots\cap Q_{t}$. Under the same
assumptions, [62, Lemma 4] shows that each component $Q_{i}$ of
$\mathsf{lt}\,{J}$ contains some component $P_{j}$ of $\mathsf{lt}\,{I}$, from
which $\mathsf{lt}\,{I}\subseteq\mathsf{lt}\,{J}$ follows immediately.

As a first stepping stone, we can already derive a bound on the length of
chains of ideals whose primary decomposition only involves associated primes
from a fixed set. We refer to [62, Sec. 4.1] and the discussion therein for
the notion of _multiplicity_ of a primary component.

######  Claim 7 ([62, Lemma 6]).

Consider a finite collection of pairwise distinct prime ideals $\mathcal{P}$
of the same dimension and a strictly ascending ideal chain

$\displaystyle J_{0}\subsetneq J_{1}\subsetneq\cdots\subsetneq J_{\ell}$

where each $J_{i}$’s has an irredundant primary ideal decomposition with
associated primes from $\mathcal{P}$. (Due to the dimensionality requirement
such a decomposition is unique.) Then, the length of the chain $\ell$ is at
most the number of primary components of $J_{0}$ (counted with
multiplicities).

The results recalled so far did not use convexity of the chain 6. In the next
claim we are generalising the analysis of [62] to multiple derivations. With
Claims 6 and 7 we obtain our second stepping stone, namely a chain length
bound when the ideal chain and the colon chain are equidimensional.

######  Claim 8 (generalising [62, Lemma 8]).

Consider a strictly ascending chain of convex ideals of the form 6 of length
$\ell$ where the colon ratios have the same dimension as the starting ideal
$I_{0}$:

$\displaystyle\mathsf{dim}\,{I_{0}}=\mathsf{dim}\,{(I_{0}\operatorname{\,:\,}I_{1})}=\mathsf{dim}\,{(I_{1}\operatorname{\,:\,}I_{2})}=\cdots=\mathsf{dim}\,{(I_{\ell-1}\operatorname{\,:\,}I_{\ell})}.$

(In particular, also the ideals $I_{n}$’s have the same dimension,

$\displaystyle\mathsf{dim}\,{I_{0}}=\mathsf{dim}\,{I_{1}}=\cdots=\mathsf{dim}\,{I_{\ell}}.)$

Then $\ell$ is at most the number of primary components of the leading term
$\mathsf{lt}\,{I_{0}}$ of the starting ideal (counted with multiplicities).

######  Proof B.17 (Proof of the claim.).

Let $m:=\mathsf{dim}\,{I_{0}}$ be the common dimension of the ideals and colon
ideals. Since the ideals $I_{n}$ have the same dimension $m$, by Claim 6 the
leading terms chain is ascending,
$\mathsf{lt}\,{I_{0}}\subseteq\mathsf{lt}\,{I_{1}}\subseteq\cdots\subseteq\mathsf{lt}\,{I_{\ell}}$.

In fact the latter chain is strictly ascending. If
$\mathsf{lt}\,{I_{n}}=\mathsf{lt}\,{I_{n+1}}$ for some $0\leq n\leq\ell-1$,
then we have

$\displaystyle\Delta_{w}\alpha\in
I_{n+1}\subseteq\mathsf{lt}\,{I_{n+1}}=\mathsf{lt}\,{I_{n}},\quad\text{for all
}w\in\Sigma^{n+1},$ (30)

and thus $\Delta_{w}\alpha$ belongs to all primary components of $I_{n}$ of
maximal dimension $m$. Write $I_{n}=\mathsf{lt}\,{I_{n}}\cap R_{n}$, where
$R_{n}$ is the intersection of primary components of dimension $<m$ and define

$\displaystyle\Delta_{n}\alpha:=\bigcup_{w\in\Sigma^{n}}\Delta_{w}\alpha$ (31)

for the set of polynomials which can be obtained from $\alpha$ by words of
length exactly $n$. By 30 we have
$\Delta_{n+1}\alpha\subseteq\mathsf{lt}\,{I_{n}}$ and thus

$\displaystyle\mathsf{lt}\,{I_{n}}\operatorname{\,:\,}\langle\Delta_{n+1}\alpha\rangle=\langle
1\rangle.$ (32)

We can now write

$\displaystyle I_{n}\operatorname{\,:\,}I_{n+1}$
$\displaystyle=I_{n}\operatorname{\,:\,}\langle\Delta_{n+1}\alpha\rangle=$
$\displaystyle=(\mathsf{lt}\,{I_{n}}\cap
R_{n})\operatorname{\,:\,}\langle\Delta_{n+1}\alpha\rangle=$
$\displaystyle=\left(\mathsf{lt}\,{I_{n}}\operatorname{\,:\,}\langle\Delta_{n+1}\alpha\rangle\right)\cap\left(R_{n}\operatorname{\,:\,}\langle\Delta_{n+1}\alpha\rangle\right)=$
(by 32) $\displaystyle=\langle
1\rangle\cap\left(R_{n}\operatorname{\,:\,}\langle\Delta_{n+1}\alpha\rangle\right)\supseteq
R_{n}.$

Passing to dimensions this means
$m=\mathsf{dim}\,{(I_{n}\operatorname{\,:\,}I_{n+1})}\leq\mathsf{dim}\,{R_{n}}<m$,
which is a contradiction. We have thus established that the leading terms
chain is strictly ascending:
$\mathsf{lt}\,{I_{0}}\subsetneq\mathsf{lt}\,{I_{1}}\subsetneq\cdots\subsetneq\mathsf{lt}\,{I_{\ell}}$.

Consider now the affine variety
$X_{n}:=V(\mathsf{lt}\,{I_{n}})\subseteq\mathbb{C}^{k}$ corresponding to the
leading term ideal $\mathsf{lt}\,{I_{n}}$. We have a non-increasing chain of
varieties $X_{0}\supseteq X_{1}\supseteq\cdots\supseteq X_{\ell}$, where the
next variety $X_{n+1}$ is obtained from the previous one $X_{n}$ by
intersecting with $V(\Delta_{n+1}\alpha)$,

$\displaystyle X_{n+1}=X_{n}\cap V(\Delta_{n+1}\alpha).$

Each maximal-dimensional irreducible component $C$ of $X_{n}$ gives rise to an
affine subvariety $C\cap V(\Delta_{n+1}\alpha)$ of $X_{n+1}$. There are two
options: Either all polynomials from $\Delta_{n+1}\alpha$ vanish on $C$ and in
this case $C=C\cap V(\Delta_{n+1}\alpha)$ is also a maximal-dimensional
irreducible component of $X_{n+1}$, or otherwise $C$ gives rise to an affine
(not necessarily irreducible) subvariety $C\cap
V(\Delta_{n+1}\alpha)\subsetneq C$ of $X_{n+1}$ of strictly smaller dimension
$<m$. It follows that the irreducible maximal-dimensional components of
$X_{n+1}$ include those of $X_{n}$.

Recall that the ideals of the irreducible components of maximal dimension of
$X_{n}$ are precisely the associated primes of $I_{n}$ of maximal dimension.
It follows that the set of associated primes of $\mathsf{lt}\,{I_{n+1}}$
(which are all of the same dimension $m$) includes those of
$\mathsf{lt}\,{I_{n}}$. In particular, the associated primes of
$\mathsf{lt}\,{I_{n}}$ include those of $\mathsf{lt}\,{I_{0}}$, and are all of
the same dimension $m$, call them $\mathcal{P}$.

Summarising, we have proved that the leading term chain is strictly increasing

$\displaystyle\mathsf{lt}\,{I_{0}}\subsetneq\mathsf{lt}\,{I_{1}}\subsetneq\cdots\subsetneq\mathsf{lt}\,{I_{\ell}}$

and the associated primes all come from a fixed set $\mathcal{P}$ of prime
ideals, all of the same dimension $m$. We can thus apply Claim 7 to this chain
and bound its length $\ell$ by the number of primary components of
$\mathsf{lt}\,{I_{0}}$ (counted with multiplicities).

We would like to relax the requirement from Claim 8 that the chain of colon
ideals has the same dimension as the first element $I_{0}$ of the ideal chain.
To this end, we show that the length of ideal chains as in Claim 8 in fact
provide an upper bound on the length of ideal chains without the additional
requirement.

######  Claim 9 (generalising [62, Lemma 9]).

Assume that the colon ideals $I_{n}\operatorname{\,:\,}I_{n+1}$ along a
strictly ascending chain 6 of length $\ell$ have all the same dimension $m$.
Consider any primary decomposition of the initial ideal $I_{0}$ and write it
as

$\displaystyle I_{0}=I_{0}^{\prime}\cap S$

where $I_{0}^{\prime}$ is the intersection of primary components of dimension
$\leq m$ and $S$ is the intersection of primary components of dimension $\geq
m+1$. Consider the new ideal chain started at $I_{0}^{\prime}$,

$\displaystyle I_{0}^{\prime}\subseteq I_{1}^{\prime}\subseteq\cdots\subseteq
I_{\ell}^{\prime},\quad\text{where
}I_{n+1}^{\prime}:=I_{n}^{\prime}+\langle\Delta_{n+1}\alpha\rangle.$ (33)

($\Delta_{n}$ is defined in 31.) Then, for all $0\leq n<\ell$,

  1. (1)

$\Delta_{n+1}\alpha\subseteq S$,

  2. (2)

$I_{n}=I_{n}^{\prime}\cap S$, and

  3. (3)

$I_{n}\operatorname{\,:\,}I_{n+1}=I_{n}^{\prime}\operatorname{\,:\,}I_{n+1}^{\prime}$.

Note that from condition (2) it follows that termination of the
$I_{n}^{\prime}$ chain implies the same for the $I_{n}$ chain.

######  Proof B.18 (Proof of the claim.).

Properties (1) and (2) are proved by simultaneous induction on $n$. Property
(3) will then follow at once.

(1) By way of contradiction, assume
$p:=\Delta_{w}\alpha\in\Delta_{n+1}\alpha\subseteq I_{n+1}$ is not in $S$ for
some word $w\in\Sigma^{n+1}$ of minimal length $n+1$. (In particular, (1)
holds for words of shorter length $n$ and thus below we can use (2) at $n$.)
Then $p$ does not belong to some primary component $Q$ of $S$ of dimension
$\geq m+1$. We argue that $\mathsf{dim}\,{(Q\operatorname{\,:\,}\langle
p\rangle)}=\mathsf{dim}\,{Q}$. In fact, we prove the stronger fact

$\displaystyle\sqrt{Q\operatorname{\,:\,}\langle p\rangle}=\sqrt{Q}.$

The “$\supseteq$” inclusion follows from the fact that the colon and radical
operations are monotone. For the “$\subseteq$” inclusion, let
$q\in\sqrt{Q\operatorname{\,:\,}\langle p\rangle}$. There is $m\in\mathbb{N}$
s.t. $q^{m}\in Q\operatorname{\,:\,}\langle p\rangle$. By definition of colon
ideal, $q^{m}\cdot p\in Q$. Since $Q$ is primary and $p\not\in Q$, we have
$q^{m\cdot h}\in Q$ for some $h\in\mathbb{N}$, which means $q\in\sqrt{Q}$.

By (2), we have $I_{n}\subseteq S\subseteq Q$. By monotonicity of colon
ideals, $I_{n}:I_{n+1}\subseteq I_{n}:\langle p\rangle$ (since $\langle
p\rangle\subseteq I_{n+1}$) and $I_{n}:\langle p\rangle\subseteq Q:\langle
p\rangle$ (since $I_{n}\subseteq Q$). Since the latter ideal
$\mathsf{dim}\,{(Q\operatorname{\,:\,}\langle p\rangle)}$ has dimension $\geq
m+1$, the same holds for the colon ideal $I_{n}:I_{n+1}$, which is a
contradiction. We conclude $p\in S$, as required.

(2) We proceed by induction. The base case $n=0$ holds by construction. For
the inductive step,

$\displaystyle I_{n+1}^{\prime}\cap S$
$\displaystyle=(I_{n}^{\prime}+\langle\Delta_{n+1}\alpha\rangle)\cap S=$
$\displaystyle=I_{n}^{\prime}\cap S+\langle\Delta_{n+1}\alpha\rangle\cap S=$
(by (1)) $\displaystyle=I_{n}^{\prime}\cap
S+\langle\Delta_{n+1}\alpha\rangle=$ (by (2))
$\displaystyle=I_{n}+\langle\Delta_{n+1}\alpha\rangle=I_{n+1}.$

(3) We have

$\displaystyle I_{n}\operatorname{\,:\,}I_{n+1}$
$\displaystyle=I_{n}\operatorname{\,:\,}\langle\Delta_{n+1}\alpha\rangle=$ (by
(2)) $\displaystyle=(I_{n}^{\prime}\cap
S)\operatorname{\,:\,}\langle\Delta_{n+1}\alpha\rangle=$ (by (1))
$\displaystyle=I_{n}^{\prime}\operatorname{\,:\,}\langle\Delta_{n+1}\alpha\rangle=I_{n}^{\prime}\operatorname{\,:\,}I_{n+1}^{\prime}.$

Thanks to Claim 9, we get rid of the assumption from Claim 8 that the chain of
colon ideals has the same dimension as the initial ideal, yielding our third,
and final, stepping stone. See 1

######  Proof B.19.

Consider an arbitrary primary component decomposition of $I_{0}$ and as in the
statement of Claim 9 write it as $I_{0}=I_{0}^{\prime}\cap S$, where
$I_{0}^{\prime}$ is the intersection of primary components of dimension $\leq
m$ and $S$ is the intersection of primary components of dimension $\geq m+1$.
Let $\ell^{\prime}$ be the length of the ideal chain 33. By construction, this
chain starts at an ideal $I_{0}^{\prime}$ of dimension $m$, and by Claim 9,
point (3), this dimension is the same for the corresponding chain of colon
ideals $I_{n}^{\prime}:I_{n+1}^{\prime}$. Clearly $\ell\leq\ell^{\prime}$: If
$I_{n}^{\prime}=I_{n+1}^{\prime}$, then by Claim 9, point (2),
$I_{n}=I_{n+1}$. Moreover, Claim 8 applies to the new ideal chain 33, since
the dimension of colon ratios of the new chain is $m$, the same dimension as
the new starting ideal $I_{0}^{\prime}$. Thus $\ell^{\prime}$ is at most the
number of primary components of $I_{0}^{\prime}$ of maximal dimension $=m$
(counted with multiplicities). In turn, this number is at most the number of
_all_ primary components of the given decomposition of the starting ideal
$I_{0}$ (counted with multiplicities).

Having established Claim 1, the proof of Theorem 2.16 is now completed.

##  Appendix C Additional material for § 3

In this section we provide additional details on the development of CDF power
series.

We recall a characterisation of CDF in the same spirit as for WBPP series in §
2.4. This characterisation will be put at work in the proofs of Lemmas 3.1,
3.4 and C.17.

######  Lemma C.1 ([8, Proposition 10]).

A power series is CDF if, and only if, it belongs to a finitely generated
differential subalgebra of $\mathbb{Q}[\\![x]\\!]$.

######  Remark C.2 (Simple CDF).

Let $f\in\mathbb{Q}[\\![x]\\!]$ be _simple CDF_ [7, Sec. 5, eq. (12)] if the
algebra $\mathbb{Q}[\partial_{x}^{n}f\mid n\in\mathbb{N}^{d}]$ generated by
all derivatives of $f$ is finitely generated. Since this algebra is closed
under derivation by definition, if $f$ is simple CDF then it is CDF. In [7,
Sec. 5] it is shown that $e^{x^{2}}$ is a CDF power series which is not
simple.

###  C.1 Basic closure properties

In order to be self-contained, we provide full proofs of the basic CDF closure
properties. This is also a nice playground for the characterisation of CDF
from Lemma C.1.

See 3.1

######  Proof C.3.

A quick argument for these basic closure properties can be obtained by virtue
of Lemma C.1. Thanks to Fact 3, in order to show that a finitely generated
algebra is closed under derivatives it suffices to show that this is the case
for its generators, which will be used several times below.

Let $f,g$ be CDF. By the characterisation given by Lemma C.1 there are
generators
$f^{(1)},\dots,f^{(k)},g^{(1)},\dots,g^{(m)}\in\mathbb{Q}[\\![x]\\!]$ s.t.

$\displaystyle f\in F:=\mathbb{Q}[f^{(1)},\dots,f^{(k)}]\quad\text{and}\quad
g\in G:=\mathbb{Q}[g^{(1)},\dots,g^{(m)}],$

and $F,G$ are closed under partial derivatives $\partial_{x_{j}}$’s. Closure
under scalar product is immediate since $c\cdot f\in F$ by definition.
Regarding closure under sum and product it is enough to take the union of the
generators:

$\displaystyle f+g,f\cdot g\in
R:=\mathbb{Q}[f^{(1)},\dots,f^{(k)},g^{(1)},\dots,g^{(m)}].$

The new ring $R$ is clearly closed for derivatives $\partial_{x_{j}}$. Closure
under derivation holds by definition since $\partial_{x_{j}}f\in F$ already.

We show closure under multiplicative inverse (when it exists). Let
$g:=f^{-1}$. By definition $f\cdot g=1$ and thus by the product rule
$\partial_{x_{j}}(f\cdot g)=\partial_{x_{j}}f\cdot
g+f\cdot\partial_{x_{j}}g=0$. We solve for $\partial_{x_{j}}g$ and write

$\displaystyle\partial_{x_{j}}g=-f^{-1}\cdot\partial_{x_{j}}f\cdot
g=-\partial_{x_{j}}f\cdot g^{2}.$ (34)

This suggests to add $g$ to the set of generators and consider the finitely
generated algebra

$\displaystyle g\in R:=\mathbb{Q}[f^{(1)},\dots,f^{(k)},g].$

The ring $R$ is closed under derivatives $\partial_{x_{j}}$’s by 34.

Finally, assume $\partial_{x_{1}}f,\dots,\partial_{x_{d}}f$ are CDF. By taking
the union of their generators, we can assume that they all lie in
$\mathbb{Q}[g^{(1)},\dots,g^{(m)}]$, closed under derivatives. We construct
the finitely generated algebra

$\displaystyle\mathbb{Q}[g^{(1)},\dots,g^{(m)},f]$

which clearly contains $f$ and is closed under derivatives.

Closure under strong composition requires some additional developments and it
will be proved in § C.2 (Lemma C.17).

###  C.2 Composition of CDF power series

In analogy for series, the _order_ $\mathsf{ord}(f)$ of a power series
$f\in\mathbb{Q}[\\![d]\\!]$ is the minimal total degree of a monomial in its
support. This endows the set of power series with a natural topology. Common
operations on power series are continuous for this topology (addition,
multiplication, partial derivative, composition $\\_\,\circ_{y}\,g$).

A family of power series
$\left\\{f_{0},f_{1},\dots\right\\}\subseteq\mathbb{Q}[\\![x]\\!]$ is
_summable_ if the following limit exists,

$\displaystyle\sum_{n=0}^{\infty}f_{n}:=\lim_{n\to\infty}\sum_{i=0}^{n}f_{i}\in\mathbb{Q}[\\![x]\\!].$

Spelling out the definition, this means that for every $n\in\mathbb{N}^{d}$
there are finitely many power series $f_{i}$ with nonzero coefficient
$[x^{n}]f_{i}$. This also gives formal meaning to the infinite sum
representation of power series
$f=\sum_{n\in\mathbb{N}^{d}}f_{n}\cdot\frac{x^{n}}{n!}$ since the family of
monomials $f_{n}\cdot\frac{x^{n}}{n!}$ is summable and its sum is $f$.

A linear and continuous function on power series
$F:\mathbb{Q}[\\![x]\\!]\to\mathbb{Q}[\\![x]\\!]$ commutes with sums of
families of summable functions, provided it preserves summability:

$\displaystyle
F\sum_{n=0}^{\infty}f_{n}=F\lim_{n\to\infty}\sum_{i=0}^{n}f_{i}=\lim_{n\to\infty}F\sum_{i=0}^{n}f_{i}=\lim_{n\to\infty}\sum_{i=0}^{n}Ff_{i}=\sum_{n=0}^{\infty}Ff_{n}.$

The operations of scalar product $c\cdot\\_$ ($c\in\mathbb{Q}$) and partial
derivation $\partial_{x_{j}}$ preserve summability. Moreover, if
$F,G:\mathbb{Q}[\\![x]\\!]\to\mathbb{Q}[\\![x]\\!]$ preserve summability, then
$F+G$ (defined as $(F+G)(f):=Ff+Gg$) and $F\cdot G$ (defined as $(F\cdot
G)(f):=Ff\cdot Gf$) also preserve summability.

######  Lemma C.4.

If $f\in\mathbb{Q}[\\![x,y]\\!],g\in\mathbb{Q}[\\![x]\\!]^{k}$ are
$y$-composable, then the same is true for $\partial_{x_{j}}f,g$ and
$\partial_{y_{i}}f,g$.

######  Proof C.5.

Let $I$ be the set of indices $i$ s.t. $g^{(i)}(0)\neq 0$. By definition of
$y$-composability, $f$ is locally polynomial w.r.t. $y_{I}$, that is
$f\in\mathbb{Q}[y_{I}][\\![x,y_{\setminus I}]\\!]$. Then it is clear that
$\partial_{x_{j}}f,\partial_{y_{i}}f$ belong to the same ring, and thus they
are $y$-composable with $g$.

The chain rule is a fundamental property connecting derivation and
composition. It is the main ingredient in proving closure under composition
for CDF series.

######  Lemma C.6 (Chain rule for power series).

For tuples of commuting variables $x=\left(x_{1},\dots,x_{d}\right)$,
$y=\left(y_{1},\dots,y_{k}\right)$, and $y$-composable power series
$f\in\mathbb{Q}[\\![x,y]\\!]$, $g\in\mathbb{Q}[\\![x]\\!]^{k}$ we have, for
every $1\leq j\leq d$,

$\displaystyle\partial_{x_{j}}(f\,\circ_{y}\,g)$
$\displaystyle=\partial_{x_{j}}f\,\circ_{y}\,g+\sum_{i=1}^{k}\partial_{x_{j}}g^{(i)}\cdot(\partial_{y_{i}}f\,\circ_{y}\,g),$
(35)

This is a general result on power series; in particular, there is no
assumption on whether the involved power series are CDF.

######  Proof C.7.

Fix an index $j$ and a tuple of power series $g$ as in the statement of the
lemma. First note that the r.h.s. of 35 is well-defined since
$\partial_{x_{j}}f,g$ and $\partial_{y_{i}}f,g$ are $y$-composable by Lemma
C.4.

Rewrite 35 as

$\displaystyle F(f)=G(f),$ (36)

where we have used the abbreviations

$\displaystyle F(f)$
$\displaystyle:=\partial_{x_{j}}(f\,\circ_{y}\,g),\text{and}$ $\displaystyle
G(f)$
$\displaystyle:=\partial_{x_{j}}f\,\circ_{y}\,g+\sum_{i=1}^{k}\partial_{x_{j}}g^{(i)}\cdot(\partial_{y_{i}}f\,\circ_{y}\,g).$

Since partial differentiation $\partial_{x_{j}}$ and composition
$\\_\,\circ_{y}\,g$ are linear and continuous, the same is true for $F$ and
$G$. This implies that 36 is inductive over scalar multiplication, summable
families of power series, and products. We show this in the following claims.

If 36 holds for $f$, then it holds for $c\cdot f$, for every $c\in\mathbb{Q}$,

######  Proof C.8 (Proof of the claim).

$\displaystyle F(c\cdot f)=c\cdot F(f)=c\cdot G(f)=G(c\cdot f).\quad$

Assume $\left\\{f_{0},f_{1},\dots\right\\}\subseteq\mathbb{Q}[\\![x]\\!]$ is a
summable family s.t. 1) $\left\\{F(f_{0}),F(f_{1}),\dots\right\\}$ and
$\left\\{G(f_{0}),G(f_{1}),\dots\right\\}$ are also summable and 2) for every
$f_{i}$ the chain rule 36 holds. Then, it also holds for
$\sum_{n=0}^{\infty}f_{n}$.

######  Proof C.9 (Proof of the claim).

$\displaystyle
F(\sum_{n=0}^{\infty}f_{n})=\sum_{n=0}^{\infty}F(f_{n})=\sum_{n=0}^{\infty}G(f_{n})=G(\sum_{n=0}^{\infty}f_{n}).\quad$

If 36 holds for $f_{1},f_{2}$, then it holds for $f_{1}\cdot f_{2}$.

######  Proof C.10 (Proof of the claim).

Both $F$ and $G$ satisfy a property akin to Leibniz rule:

$\displaystyle F(f_{1}\cdot f_{2})$
$\displaystyle=F(f_{1})\cdot(f_{2}\,\circ_{y}\,g)+(f_{1}\,\circ_{y}\,g)\cdot
F(f_{2}),$ (37) $\displaystyle G(f_{1}\cdot f_{2})$
$\displaystyle=G(f_{1})\cdot(f_{2}\,\circ_{y}\,g)+(f_{1}\,\circ_{y}\,g)\cdot
G(f_{2}).$ (38)

Indeed, regarding $F$ we have

$\displaystyle F(f_{1}\cdot f_{2})$
$\displaystyle=\partial_{x_{j}}((f_{1}\cdot f_{2})\,\circ_{y}\,g)=$
$\displaystyle=\partial_{x_{j}}((f_{1}\,\circ_{y}\,g)\cdot(f_{2}\,\circ_{y}\,g))=$
$\displaystyle=\partial_{x_{j}}(f_{1}\,\circ_{y}\,g)\cdot(f_{2}\,\circ_{y}\,g)+(f_{1}\,\circ_{y}\,g)\cdot\partial_{x_{j}}(f_{2}\,\circ_{y}\,g)=$
$\displaystyle=F(f_{1})\cdot(f_{2}\,\circ_{y}\,g)+(f_{1}\,\circ_{y}\,g)\cdot
F(f_{2}),$

Regarding $G$, write $G_{0}(f):=\partial_{x_{j}}f\,\circ_{y}\,g$ and
$G_{i}(f):=\partial_{y_{i}}f\,\circ_{y}\,g$ for $1\leq i\leq k$. We notice
that 38 holds for $G_{0},\dots,G_{k}$:

$\displaystyle G_{0}(f_{1}\cdot f_{2})$
$\displaystyle=\partial_{x_{j}}(f_{1}\cdot f_{2})\,\circ_{y}\,g$
$\displaystyle=(\partial_{x_{j}}f_{1}\cdot
f_{2}+f_{1}\cdot\partial_{x_{j}}f_{2})\,\circ_{y}\,g=$
$\displaystyle=(\partial_{x_{j}}f_{1}\,\circ_{y}\,g)\cdot(f_{2}\,\circ_{y}\,g)+(f_{1}\,\circ_{y}\,g)\cdot(\partial_{x_{j}}f_{2}\,\circ_{y}\,g)=$
$\displaystyle=G_{0}(f_{1})\cdot(f_{2}\,\circ_{y}\,g)+(f_{1}\,\circ_{y}\,g)\cdot
G_{0}(f_{2}).$

The proof for $G_{1},\dots,G_{k}$ is analogous. Since $G$ is a linear
combination of $G_{0},\dots,G_{k}$, property 38 follows for $G$ as well.

Having established the product rules 37 and 38, we show that 36 is inductive
over products of power series, completing the proof of the claim. Indeed,
assume that 36 holds for $f_{1},f_{2}$. We can then write

$\displaystyle F(f_{1}\cdot f_{2})$
$\displaystyle=F(f_{1})\cdot(f_{2}\,\circ_{y}\,g)+(f_{1}\,\circ_{y}\,g)\cdot
F(f_{2})=$
$\displaystyle=G(f_{1})\cdot(f_{2}\,\circ_{y}\,g)+(f_{1}\,\circ_{y}\,g)\cdot
G(f_{2})=$ $\displaystyle=G(f_{1}\cdot f_{2}).\quad$

In the last claim we establish the chain rule for single variables. 36 holds
for single variables $f=x_{\ell}$ and $f=y_{\ell}$.

######  Proof C.11 (Proof of the claim).

If $f=x_{\ell}$ then we have $\partial_{y_{i}}f=0$, and thus

$\displaystyle F(f)$
$\displaystyle=\partial_{x_{j}}(x_{\ell}\,\circ_{y}\,g)=\partial_{x_{j}}x_{\ell},\text{and}$
$\displaystyle G(f)$
$\displaystyle=\partial_{x_{j}}x_{\ell}\,\circ_{y}\,g=\partial_{x_{j}}x_{\ell}.$

If $f=y_{\ell}$ then $f\,\circ_{y}\,g=g^{(\ell)}$ and
$\partial_{x_{j}}f=\partial_{y_{i}}f=0$ for all $i\neq\ell$, implying that the
r.h.s. of 36 is just $\partial_{x_{j}}g^{(\ell)}$, as required.

We now prove 36 by bringing all claims together. Write the power series $f$ as
the sum

$\displaystyle f=\sum_{m\in\mathbb{N}^{d},n\in\mathbb{N}^{k}}f_{m,n}\cdot
x^{m}y^{n}$

of the summable family of monomials $\left\\{f_{m,n}\cdot
x^{m}y^{n}\;\middle|\;m\in\mathbb{N}^{d},n\in\mathbb{N}^{k}\right\\}$. Since
$f,\partial_{x_{j}}f,\partial_{y_{i}}f$ are all $y$-composable with $g$, the
families

$\displaystyle\left\\{F(f_{m,n}\cdot
x^{m}y^{n})\;\middle|\;m\in\mathbb{N}^{d},n\in\mathbb{N}^{k}\right\\}\text{
and }$ $\displaystyle\left\\{G(f_{m,n}\cdot
x^{m}y^{n})\;\middle|\;m\in\mathbb{N}^{d},n\in\mathbb{N}^{k}\right\\}$

are also summable. Since $F(h)=G(h)$ for $h$ a single variable $h=x_{\ell}$ or
$h=y_{\ell}$ by the last claim, we have $F(x^{m}y^{n})=G(x^{m}y^{n})$ by
multiple applications of the claim for products, but then we also have
$F(f_{m,n}\cdot x^{m}y^{n})=G(f_{m,n}\cdot x^{m}y^{n})$ by the claim for
scalar multiplication, and finally

$\displaystyle F(f)$
$\displaystyle=F(\sum_{m\in\mathbb{N}^{d},n\in\mathbb{N}^{k}}f_{m,n}\cdot
x^{m}y^{n})=$
$\displaystyle=\sum_{m\in\mathbb{N}^{d},n\in\mathbb{N}^{k}}F(f_{m,n}\cdot
x^{m}y^{n})=$
$\displaystyle=\sum_{m\in\mathbb{N}^{d},n\in\mathbb{N}^{k}}G(f_{m,n}\cdot
x^{m}y^{n})=$
$\displaystyle=G(\sum_{m\in\mathbb{N}^{d},n\in\mathbb{N}^{k}}f_{m,n}\cdot
x^{m}y^{n})=G(f)$

by the claim for summable families.

The following lemma shows that if a CDF series is polynomial in a set of
variables, then the generators can be chosen with the same property. This will
be used in the proof of closure under strong composition for CDF power series
(Lemma C.17).

######  Lemma C.12.

Let $f$ belong to a finitely generated differential subalgebra of
$\mathbb{Q}[\\![x]\\!]$. If $f$ is a polynomial in
$Z\subseteq\left\\{x_{1},\dots,x_{d}\right\\}$, then the generators can be
chosen to be polynomial in $Z$.

We leave it open whether the lemma holds by replacing “polynomial” with
“locally polynomial”. Were this the case, we could prove the generalisation of
Lemma C.17 stating that CDF power series are closed under composition.

######  Proof C.13.

We show the lemma for $Z=\left\\{x_{1}\right\\}$. Since the construction
preserves polynomiality of the generators, iterated application proves the
general statement.

Assume that $f$ is a polynomial in $x_{1}$ of degree $E\in\mathbb{N}$ and that
it belongs to the finitely generated differential algebra

$\displaystyle
R:=\mathbb{Q}[f^{(1)},\dots,f^{(m)}]\subseteq\mathbb{Q}[\\![x]\\!].$

For a power series $g\in\mathbb{Q}[\\![x]\\!]$ and $e\in\mathbb{N}$, write

$\displaystyle
g_{e}:=[x_{1}^{e}]g\cdot\frac{x_{1}^{e}}{e!},\quad[x_{1}^{e}]g\in\mathbb{Q}[\\![x_{2},\dots,x_{d}]\\!],$

so that any power series $g$ can be written as $g=g_{0}+g_{1}+\cdots$, where
the family $\left\\{g_{0},g_{1},\dots\right\\}$ is summable. For instance,
since $f$ is polynomial in $x_{1}$ of degree $E$ we can write

$\displaystyle f=f_{0}+f_{1}+\cdots+f_{E}.$ (39)

The operation $(\\_)_{e}$ is linear, continuous, and preserves summability,
for every $e\in\mathbb{N}$. We will use the following sum and product rules.
For every power series $g,h\in\mathbb{Q}[\\![x]\\!]$ and $e\in\mathbb{N}$,

$\displaystyle(g+h)_{e}=g_{e}+h_{e}\quad\text{and}\quad(g\cdot
h)_{e}=\sum_{a+b=e}g_{a}\cdot h_{b}.$ (40)

######  Proof C.14 (Proof of the claim.).

The sum rule follows immediately by linearity. For the product rule, we have

$\displaystyle(g\cdot h)_{e}$
$\displaystyle=\left(\sum_{a\in\mathbb{N}}g_{a}\cdot\sum_{b\in\mathbb{N}}h_{b}\right)_{e}=\left(\sum_{a,b\in\mathbb{N}}g_{a}\cdot
h_{b}\right)_{e}=\sum_{a,b\in\mathbb{N}}\left(g_{a}\cdot h_{b}\right)_{e}=$
$\displaystyle=\sum_{a,b\in\mathbb{N}}\left([x_{1}^{a}]g\cdot\frac{x_{1}^{a}}{a!}\cdot[x_{1}^{b}]h\cdot\frac{x_{1}^{b}}{b!}\right)_{e}=$
$\displaystyle=\sum_{a,b\in\mathbb{N}}[x_{1}^{e}]\left([x_{1}^{a}]g\cdot\frac{x_{1}^{a}}{a!}\cdot[x_{1}^{b}]h\cdot\frac{x_{1}^{b}}{b!}\right)\cdot\frac{x_{1}^{e}}{e!}=$
$\displaystyle=\sum_{a,b\in\mathbb{N}}[x_{1}^{e}]\left([x_{1}^{a}]g\cdot[x_{1}^{b}]h\cdot\frac{x_{1}^{a+b}}{a!b!}\right)\cdot\frac{x_{1}^{e}}{e!}=$
$\displaystyle=\sum_{a+b=e}[x_{1}^{a}]g\cdot[x_{1}^{b}]h\cdot\frac{x_{1}^{a+b}}{a!b!}=$
$\displaystyle=\sum_{a+b=e}[x_{1}^{a}]g\cdot\frac{x_{1}^{a}}{a!}\cdot[x_{1}^{b}]h\cdot\frac{x_{1}^{b}}{b!}=\sum_{a+b=e}g_{a}\cdot
h_{b}.$

Consider the finitely generated algebra

$\displaystyle\widetilde{R}:=\mathbb{Q}[f^{(\ell)}_{e}\mid 0\leq e\leq
E,1\leq\ell\leq m],$

Two observations are in order. First, the $f^{(\ell)}_{e}$’s are polynomial in
$x_{1}$ by construction. Second, if $f^{(\ell)}$ is polynomial in $x_{j}$, for
any $1\leq j\leq d$, then the same is true for $f^{(\ell)}_{e}$, guaranteeing
repeatability of the argument. The proof is concluded by the following two
claims. $f\in\widetilde{R}$.

######  Proof C.15 (Proof of the claim.).

Since $f\in R$, the power series $f$ can be written as a polynomial function
$f=p(f^{(1)},\dots,f^{(m)})$ of the original generators $f^{(\ell)}$’s, for
some $p\in\mathbb{Q}[m]$. By the sum and product rules 40, the term containing
$x_{1}^{e}$ in $f$ depends only on the terms containing $x_{1}^{\leq e}$ in
$f^{(1)},\dots,f^{(m)}$. Thus, we can write

$\displaystyle f_{e}=q\left(\left(f^{(\ell)}_{a}\right)_{0\leq a\leq
e,1\leq\ell\leq m}\right)$

for some polynomial $q\in\mathbb{Q}[m\cdot(e+1)]$. Therefore
$f_{e}\in\widetilde{R}$, and we conclude $f\in\widetilde{R}$ since $f$ admits
the representation 39.

The ring $\widetilde{R}$ is closed under partial derivatives
$\partial_{x_{j}}$’s.

######  Proof C.16 (Proof of the claim.).

It suffices to show $\partial_{x_{j}}f^{(\ell)}_{e}\in\widetilde{R}$. If $e=0$
and $j=1$, we have $\partial_{x_{j}}f^{(\ell)}_{e}=0$ and we are done. Now
assume $e\geq 1$ or $j\neq 1$. We have the following commuting rule

$\displaystyle\partial_{x_{j}}f^{(\ell)}_{e}=\left\\{\begin{array}[]{ll}(\partial_{x_{j}}f^{(\ell)})_{e-1}&\text{
if }j=1,\\\ (\partial_{x_{j}}f^{(\ell)})_{e}&\text{
otherwise.}\end{array}\right.$ (43)

Indeed, for $j=1$ (thus $e\geq 1$ by assumption) we have

$\displaystyle\partial_{x_{1}}f^{(\ell)}_{e}$
$\displaystyle=\partial_{x_{1}}([x_{1}^{e}]f^{(\ell)}\cdot\frac{x_{1}^{e}}{e!})=[x_{1}^{e}]f^{(\ell)}\cdot\partial_{x_{1}}(\frac{x_{1}^{e}}{e!})=$
$\displaystyle=[x_{1}^{e}]f^{(\ell)}\cdot\frac{x_{1}^{e-1}}{(e-1)!}=[x_{1}^{e-1}](\partial_{x_{1}}f^{(\ell)})\cdot\frac{x_{1}^{e-1}}{(e-1)!}=$
$\displaystyle=(\partial_{x_{1}}f^{(\ell)})_{e-1},$

and for $j\neq 1$ we have

$\displaystyle\partial_{x_{j}}f^{(\ell)}_{e}$
$\displaystyle=\partial_{x_{j}}([x_{1}^{e}]f^{(\ell)}\cdot\frac{x_{1}^{e}}{e!})=\partial_{x_{j}}([x_{1}^{e}]f^{(\ell)})\cdot\frac{x_{1}^{e}}{e!}=$
$\displaystyle=[x_{1}^{e}](\partial_{x_{j}}f^{(\ell)})\cdot\frac{x_{1}^{e}}{e!}=(\partial_{x_{j}}f^{(\ell)})_{e}.$

Since $R$ is closed under partial derivatives, $\partial_{x_{j}}f^{(\ell)}$
can be written as a polynomial combination of the original generators
$f^{(1)},\dots,f^{(m)}$. Reasoning as in the previous claim,
$(\partial_{x_{j}}f^{(\ell)})_{e}$ can be written as a polynomial combination
of new generators $f^{(\ell)}_{a}$ for $0\leq a\leq e$ and $1\leq\ell\leq m$.
The same clearly applies to $(\partial_{x_{j}}f^{(\ell)})_{e-1}$.
Consequently, $(\partial_{x_{j}}f^{(\ell)})_{e}$ and
$(\partial_{x_{j}}f^{(\ell)})_{e-1}$ are in $\widetilde{R}$, and thanks to 43
we have $\partial_{x_{j}}f^{(\ell)}_{e}\in\widetilde{R}$ as well, as required.

The two claims conclude the proof.

We can finally show closure for CDF power series under strong composition.

######  Lemma C.17 (Closure under strong composition).

Consider commuting variables $x=\left(x_{1},\dots,x_{d}\right)$,
$y=\left(y_{1},\dots,y_{k}\right)$, and strongly $y$-composable power series
$f\in\mathbb{Q}[\\![x,y]\\!]$, $g\in\mathbb{Q}[\\![x]\\!]^{k}$. If $f,g$ are
CDF, then $f\,\circ_{y}\,g$ is CDF.

######  Proof C.18.

This is a consequence of the chain rule (Lemma C.6). Since $f$ is CDF, by
Lemma C.1 it belongs to a finitely generated algebra

$\displaystyle f\in R:=\mathbb{Q}[f^{(1)},\dots,f^{(m)}],\quad\text{for some
}f^{(1)},\dots,f^{(m)}\in\mathbb{Q}[\\![x,y]\\!],$

closed under $\partial_{x_{j}}$’s and $\partial_{y_{i}}$’s. The tuple of power
series $g=(g^{(1)},\dots,g^{(k)})$ is also CDF, and we assume w.l.o.g. that

$S:=\mathbb{Q}[g^{(1)},\dots,g^{(k)}]$

is already closed under $\partial_{x_{j}}$’s. (Were this not the case, we
could increase $k$ and add dummy variables $y_{i}$’s to accommodate additional
generators). We now apply Lemma C.6 to $f,g$ and write

$\displaystyle\partial_{x_{j}}(f\,\circ_{y}\,g)=\partial_{x_{j}}f\,\circ_{y}\,g+\sum_{i=1}^{k}\partial_{x_{j}}g^{(i)}\cdot(\partial_{y_{i}}f\,\circ_{y}\,g).$

This suggests to consider the finitely generated algebra

$\displaystyle
T:=\mathbb{Q}[f^{(1)}\,\circ_{y}\,g,\dots,f^{(m)}\,\circ_{y}\,g,g^{(1)},\dots,g^{(k)}]\subseteq\mathbb{Q}[\\![x]\\!].$

First of all, we need to ensure that the generators of $T$ are well defined.
We can choose the generators $f^{(\ell)}$’s s.t. $f^{(\ell)},g$ are strongly
$y$-composable. (Incidentally, this is the problematic step for showing
closure under composable CDF power series: It is not clear how to ensure that
the generators $f^{(\ell)}$’s of $f$ can be chosen so that if $f$ is locally
polynomial in $y_{I}$, then $f^{(1)},\dots,f^{(m)}$ are also locally
polynomial in $y_{I}$.)

######  Proof C.19 (Proof of the claim.).

Let $I\subseteq\left\\{1,\dots,k\right\\}$ be the set of indices $i$ s.t.
$g^{(i)}(0)\neq 0$. Since $f,g$ are strongly $y$-composable, $f$ is polynomial
w.r.t. $y_{I}$, i.e., $f\in\mathbb{Q}[\\![x,y_{\setminus I}]\\!][y_{I}]$. We
conclude by Lemma C.12.

Next, we show that the composition of $f$ and $g$ is indeed in $T$.
$f\,\circ_{y}\,g\in T$.

######  Proof C.20 (Proof of the claim.).

Since $f\in R$ and $R$ is closed under $\partial_{x_{j}}$’s and
$\partial_{y_{i}}$’s, we have $\partial_{x_{j}}f,\partial_{y_{i}}f\in R$ as
well. Consequently,

$\displaystyle\partial_{x_{j}}f\,\circ_{y}\,g,\partial_{y_{i}}f\,\circ_{y}\,g\in
T^{\prime}:=\mathbb{Q}[f^{(1)}\,\circ_{y}\,g,\dots,f^{(m)}\,\circ_{y}\,g].$

By the same argument, $\partial_{x_{j}}g^{(i)}\in S$. We conclude by noticing
that the generators of $T$ are obtained by taking the union of those of
$T^{\prime}$ and $S$.

Finally, we show that $T$ is closed under partial derivatives. $T$ is closed
under $\partial_{x_{j}}$’s.

######  Proof C.21 (Proof of the claim.).

By the product rule for power series Leibniz rule, it suffices to show that
$\partial_{x_{j}}$ applied to the generators of $T$ yields> a power series in
$T$. The argument showing $\partial_{x_{j}}g^{(i)}\in T$ is immediate since
$\partial_{x_{j}}g^{(i)}\in S$ and $S\subseteq T$. We conclude by showing
$\partial_{x_{j}}(f^{(\ell)}\,\circ_{y}\,g)\in T$. This is another consequence
of the chain rule (Lemma C.6), this time applied to $f^{(\ell)},g$:

$\displaystyle\partial_{x_{j}}(f^{(\ell)}\,\circ_{y}\,g)=\underbrace{\partial_{x_{j}}f^{(\ell)}\,\circ_{y}\,g}_{\in
T^{\prime}\subseteq T}+\sum_{i=1}^{k}\underbrace{\partial_{x_{j}}g^{(i)}}_{\in
S\subseteq T}\cdot(\underbrace{\partial_{y_{i}}f^{(\ell)}\,\circ_{y}\,g}_{\in
T^{\prime}\subseteq T}).$

Since $\partial_{x_{j}}f^{(\ell)}\in R$, we have
$\partial_{x_{j}}f^{(\ell)}\,\circ_{y}\,g\in T^{\prime}\subseteq T$.
Similarly, $\partial_{y_{i}}f^{(\ell)}\,\circ_{y}\,g\in T$. Also,
$\partial_{x_{j}}g^{(i)}\in S\subseteq T$. This suffices to show that
$\partial_{x_{j}}(f^{(\ell)}\,\circ_{y}\,g)\in T$, as required.

By the claims, we have shown that $f\,\circ_{y}\,g$ belongs to a finitely
generated algebra $T\subseteq\mathbb{Q}[\\![x]\\!]$ closed under
$\partial_{x_{j}}$’s. We conclude that $f\,\circ_{y}\,g$ is CDF by Lemma C.1.

###  C.3 Regular support restrictions

We present below the formal semantics of constraint expressions introduced in
§ 3.2:

$\displaystyle\left\llbracket z_{j}=n\right\rrbracket$
$\displaystyle=\left\\{\left(a_{1},\dots,a_{d}\right)\in\mathbb{N}^{d}\;\middle|\;a_{j}=n\right\\}$
$\displaystyle\left\llbracket{z_{j}}\equiv{n}\;(\mathsf{mod}\
m)\right\rrbracket$
$\displaystyle=\left\\{\left(a_{1},\dots,a_{d}\right)\in\mathbb{N}^{d}\;\middle|\;{a_{j}}\equiv{n}\;(\mathsf{mod}\
m)\right\\}$ $\displaystyle\left\llbracket\varphi\lor\psi\right\rrbracket$
$\displaystyle=\left\llbracket\varphi\right\rrbracket\cup\left\llbracket\psi\right\rrbracket$
$\displaystyle\left\llbracket\varphi\land\psi\right\rrbracket$
$\displaystyle=\left\llbracket\varphi\right\rrbracket\cap\left\llbracket\psi\right\rrbracket$
$\displaystyle\left\llbracket\neg\varphi\right\rrbracket$
$\displaystyle=\mathbb{N}^{d}\setminus\left\llbracket\varphi\right\rrbracket.$

While constraint expressions are convenient to describe subsets of
$\mathbb{N}^{d}$, we now introduce an algebraic formalism which is more
suitable in proofs. A set $S\subseteq\mathbb{N}^{d}$ is _recognisable_ if
there is a finite commutative monoid $\left(M,+,0\right)$, with a
distinguished subset $F\subseteq M$, and a homomorphism $h:\mathbb{N}^{d}\to
M$ s.t. $S=h^{-1}F$. Recognisable subsets of $\mathbb{N}^{d}$ are in bijective
correspondence with commutative regular languages and form a strict subset of
semilinear sets. For instance, the semilinear set
$\left(1,1,1\right)^{*}\subseteq\mathbb{N}^{3}$ is not recognisable.

######  Lemma C.22.

For every set $S\subseteq\mathbb{N}^{d}$, if $S$ is regular then $S$ is
recognisable.

In fact, the converse holds as well and thus regular and recognisable subsets
of $\mathbb{N}^{d}$ coincide, however we will not need the other direction in
the sequel.

######  Proof C.23.

Assume $S\subseteq\mathbb{N}^{d}$ is regular. There exists an expression
$\varphi$ of dimension $d$ s.t. $S=\left\llbracket\varphi\right\rrbracket$. We
show that $\left\llbracket\varphi\right\rrbracket$ is recognisable by
structural induction on $\varphi$.

In the first base case, we have $\varphi\equiv x_{j}=n$. We construct a monoid
with elements $0,1,\dots,n,\infty$ where element $i$ for $0\leq i\leq n$
intuitively means “coordinate $j$ equals $i$”, and $\infty$ means “coordinate
$j$ is $\geq n+1$”. The monoid operation is ordinary sum in $\mathbb{N}$ when
the result is $\leq n$, and it is $\infty$ otherwise. The monoid homomorphism
$h:\mathbb{N}^{d}\to M$ maps a vector $x\in\mathbb{N}^{d}$ to its $j$-th
coordinate $x_{j}$ if $x_{j}\leq n$, and $\infty$ otherwise. The accepting set
is $F=\left\\{n\right\\}$.

In the second base case, we have
$\varphi\equiv({x_{j}}\equiv{n}\;(\mathsf{mod}\ m))$. We assume w.l.o.g.
$0\leq n\leq m-1$. The construction is similar as in the previous case. We
construct a monoid with elements $0,\dots,m-1$, representing equivalence
classes modulo $m$. Addition in the monoid $a+_{M}b$ is $(a+b)\mod m$, the
homomorphism is $h(x)=(x_{j}\mod m)$ and the accepting set is
$F=\left\\{n\right\\}$.

In the first inductive case, the constraint is of the form $\varphi\land\psi$.
By inductive assumption, $\left\llbracket\varphi\right\rrbracket$ is
recognised by $M_{\varphi},h_{\varphi},F_{\varphi}$ and
$\left\llbracket\psi\right\rrbracket$ by $M_{\psi},h_{\psi},F_{\psi}$. We
construct a product monoid $M:=M_{\varphi}\times M_{\psi}$ where all data is
defined component-wise: addition is
$(a_{0},b_{0})+_{M}(a_{1},b_{1}):=(a_{0}+_{M_{\varphi}}a_{1},b_{0}+_{M_{\psi}}b_{1})$,
the neutral element is $0_{M}:=\left(0_{M_{\varphi}},0_{M_{\psi}}\right)$, the
accepting set is $F:=F_{\varphi}\times F_{\psi}$, and the homomorphism is
$h(x):=\left(h_{\varphi}(x),h_{\psi}(x)\right)$. We then have
$h^{-1}F=h^{-1}(F_{\varphi}\times F_{\psi})=h_{\varphi}^{-1}F_{\varphi}\cap
h_{\psi}^{-1}F_{\psi}$.

In the second inductive case, the constraint is of the form $\neg\varphi$. If
$M,h,F$ recognises $\left\llbracket\varphi\right\rrbracket$, then its
complement $\mathbb{N}^{d}\setminus\left\llbracket\varphi\right\rrbracket$ is
recognised by $M,h,M\setminus F$.

In the last inductive case, the constraint is of the form $\varphi\lor\psi$.
We can just reduce to the previous two cases by double negation, since
$\left\llbracket\varphi\lor\psi\right\rrbracket=\left\llbracket\neg(\neg\varphi\land\neg\psi)\right\rrbracket$.

See 3.4

######  Proof C.24.

Let $f^{(1)}\in\mathbb{Q}[\\![x]\\!]$ be a CDF power series, and thus by Lemma
C.1 $f^{(1)}$ belongs to a finitely generated algebra

$\displaystyle R:=\mathbb{Q}[f^{(1)},\dots,f^{(k)}]$

closed under $\partial_{x_{j}}$’s. Let $S$ be a regular subset of
$\mathbb{N}^{d}$, which is thus recognisable by virtue of Lemma C.22. There
exist a finite commutative monoid $M$ and a surjective homomorphism
$h:\mathbb{N}^{d}\to M$ s.t. $S=h^{-1}F$ for some $F\subseteq M$. Notice that
$\left\\{h^{-1}m\;\middle|\;m\in M\right\\}$ is a partition of
$\mathbb{N}^{d}$.

For every $m\in M$ and $1\leq i\leq k$, let $f^{(i)}|_{m}$ be the restriction
of $f^{(i)}$ to $S_{m}:=h^{-1}m\subseteq\mathbb{N}^{d}$, i.e.,

$\displaystyle f^{(i)}|_{m}:=f^{(i)}|_{S_{m}}=\sum_{n\in
h^{-1}m}[x^{n}]f^{(i)}\cdot\frac{x^{n}}{n!}.$

By the partition property, every power series $f\in\mathbb{Q}[\\![x]\\!]$ can
be written as a finite sum of restrictions

$\displaystyle f=\sum_{m\in M}f|_{m}.$ (44)

First of all, restriction is a linear operation. For two power series
$f,g\in\mathbb{Q}[\\![x]\\!]$ and $m\in M$, we have

$\displaystyle\left.(f+g)\right|_{m}=\left.f\right|_{m}+\left.g\right|_{m}.$
(45)

######  Proof C.25 (Proof of the claim).

We have

$\displaystyle\left.(f+g)\right|_{m}$
$\displaystyle=\left.\left(\sum_{n\in\mathbb{N}^{d}}[x^{n}]f\cdot\frac{x^{n}}{n!}+\sum_{n\in\mathbb{N}^{d}}[x^{n}]g\cdot\frac{x^{n}}{n!}\right)\right|_{m}=$
$\displaystyle=\left.\left(\sum_{n\in\mathbb{N}^{d}}([x^{n}]f+[x^{n}]g)\cdot\frac{x^{n}}{n!}\right)\right|_{m}=$
$\displaystyle=\sum_{n\in h^{-1}m}([x^{n}]f+[x^{n}]g)\cdot\frac{x^{n}}{n!}=$
$\displaystyle=\sum_{n\in h^{-1}m}[x^{n}]f\cdot\frac{x^{n}}{n!}+\sum_{n\in
h^{-1}m}[x^{n}]g\cdot\frac{x^{n}}{n!}=$
$\displaystyle=\left.f\right|_{m}+\left.g\right|_{m}.\quad$

The following claim shows that restrictions can be pushed through products.
For two power series $f,g\in\mathbb{Q}[\\![x]\\!]$, we have the following
product rule for the restriction operation:

$\displaystyle(f\cdot g)|_{m}=\sum_{a+b=m}f|_{a}\cdot g|_{b},\quad\text{for
all }m\in M.$ (46)

######  Proof C.26 (Proof of the claim.).

By 44 applied to $f$ and to $g$ we have

$\displaystyle(f\cdot g)|_{m}$ $\displaystyle=\left.\left(\left(\sum_{a\in
M}f|_{a}\right)\cdot\left(\sum_{b\in M}g|_{b}\right)\right)\right|_{m}=$
$\displaystyle=\left.\left(\sum_{a,b\in M}f|_{a}\cdot
g|_{b}\right)\right|_{m}=$ $\displaystyle=\sum_{a,b\in M}\left.(f|_{a}\cdot
g|_{b})\right|_{m}=$ $\displaystyle=\sum_{a,b\in
M}\left.\left(\sum_{h(d)=a}f_{d}\cdot x^{d}\cdot\sum_{h(e)=b}g_{e}\cdot
x^{e}\right)\right|_{m}=$ $\displaystyle=\sum_{a,b\in
M}\left.\left(\sum_{h(d)=a,h(e)=b}f_{d}g_{e}\cdot x^{e+d}\right)\right|_{m}=$
$\displaystyle=\sum_{a,b\in M}\sum_{h(d)=a,h(e)=b,h(e+d)=m}f_{d}g_{e}\cdot
x^{e+d}=$ $\displaystyle=\sum_{a+b=m}\sum_{h(d)=a,h(e)=b}f_{d}g_{e}\cdot
x^{e+d}=$ $\displaystyle=\sum_{a+b=m}\sum_{h(d)=a}f_{d}\cdot
x^{d}\cdot\sum_{h(e)=b}g_{e}\cdot x^{e}=$
$\displaystyle=\sum_{a+b=m}f|_{a}\cdot g|_{b}.$

Restrictions compose trivially: For all $a,b\in M$ with $a\neq b$,

$\displaystyle\left.(f|_{a})\right|_{a}=f|_{a}\quad\text{and}\quad\left.(f|_{a})\right|_{b}=0.$
(47)

######  Proof C.27 (Proof of the claim.).

The first equality is trivial, and the second one follows from the partition
property (distinct monoid elements recognise disjoint subsets of
$\mathbb{N}^{d}$).

Consider the new finitely generated algebra

$\displaystyle\widetilde{R}:=\mathbb{Q}[f^{(i)}|_{m}\mid m\in M,1\leq i\leq
k].$

$f^{(1)}|_{S}=\sum_{m\in F}f^{(1)}|_{m}$, thus in $\widetilde{R}$. It remains
to argue that $\widetilde{R}$ is closed under $\partial_{x_{j}}$’s. In fact,
it suffices to show this for an arbitrary generator $f^{(i)}|_{m}$. We begin
by an observation. We have the following exchange property

$\displaystyle\partial_{x_{j}}(f^{(i)}|_{m})=\sum_{m^{\prime}\in
M_{j}}(\partial_{x_{j}}f^{(i)})|_{m^{\prime}},$ (48)

where $M_{j}:=\left\\{m^{\prime}\in
M\;\middle|\;m^{\prime}+h(e_{j})=m\right\\}$ and $e_{j}$ is the $j$-th unit
vector.

######  Proof C.28 (Proof of the claim).

Justification:

$\displaystyle\partial_{x_{j}}(f^{(i)}|_{m})$
$\displaystyle=\partial_{x_{j}}\sum_{n\in
h^{-1}m}[x^{n}]f^{(i)}\cdot\frac{x^{n}}{n!}$ $\displaystyle=\sum_{n\in
h^{-1}m}[x^{n}]f^{(i)}\cdot\partial_{x_{j}}\frac{x^{n}}{n!}$
$\displaystyle=\sum_{n\in h^{-1}m,n_{j}\geq
1}[x^{n}]f^{(i)}\cdot\frac{x^{n-e_{j}}}{(n-e_{j})!}$
$\displaystyle=\sum_{(n+e_{j})\in
h^{-1}m}[x^{n+e_{j}}]f^{(i)}\cdot\frac{x^{n}}{n!}$
$\displaystyle=\sum_{(n+e_{j})\in
h^{-1}m}[x^{n}]\partial_{x_{j}}f^{(i)}\cdot\frac{x^{n}}{n!}$
$\displaystyle=\sum_{h(n+e_{j})=h(n)+h(e_{j})=m}[x^{n}]\partial_{x_{j}}f^{(i)}\cdot\frac{x^{n}}{n!}$
$\displaystyle=\sum_{m^{\prime}\in M_{j}}\sum_{n\in
h^{-1}m^{\prime}}[x^{n}]\partial_{x_{j}}f^{(i)}\cdot\frac{x^{n}}{n!}$
$\displaystyle=\sum_{m^{\prime}\in
M_{j}}(\partial_{x_{j}}f^{(i)})|_{m^{\prime}}.$

The exchange property from 48 shows that $\partial_{x_{j}}(f^{(i)}|_{m})$ is a
linear combination of restrictions of $\partial_{x_{j}}f^{(i)}$. Since
$\partial_{x_{j}}f^{(i)}\in R$, the latter can written as a polynomial
combination of the generators $f^{(1)},\dots,f^{(k)}$. Since
$f^{(1)},\dots,f^{(k)}\in\widetilde{R}$ by the partition property 44, we also
have $\partial_{x_{j}}f^{(i)}\in\widetilde{R}$. The proof is concluded by
showing that $\widetilde{R}$ is closed under restrictions. If
$f\in\widetilde{R}$ then $\left.f\right|_{m}\in\widetilde{R}$ for all $m\in
M$.

######  Proof C.29 (Proof of the claim.).

This is shown by induction on the structure of witnesses of membership of $f$
in $\widetilde{R}$. The base case for a generator $f^{(i)}|_{m}$ holds since
restrictions compose by 47. The inductive step follows by the sum 45 and
product 46 rules.

This concludes the proof of closure under regular support restrictions.

###  C.4 Implicit power series theorems

The purpose of this section is to provide a proof of Lemma 3.3 regarding
solutions of constructible systems of CDF equations. We will obtain this as a
consequence of the study of more general systems of equations, which we now
introduce.

The next result shows that the class CDF does not change if we allow CDF
kernels in the definition of CDF power series (cf. [8, Proposition 12]).

######  Lemma C.30 (CDF differentially constructible power series theorem).

Consider a matrix of power series $M\in\mathbb{Q}[\\![x,y]\\!]^{k\times d}$
and a tuple of power series $f\in\mathbb{Q}[\\![x]\\!]^{k}$ s.t. $M,f$ are
$y$-composable and satisfy a constructible system of partial differential
equations

$\displaystyle\partial_{x}f=M\,\circ_{y}\,f.$ (49)

If $M$ is CDF, then $f$ is CDF.

For instance, the unique univariate power series $f$ with $f(0)=0$ satisfying
$\partial_{x}f=x\cdot e^{f}$ is CDF. The next closure property is a simple
application of Lemma C.30, albeit a very useful one since many power series
can be shown to be CDF thanks to it.

######  Lemma C.31 (CDF implicit power series theorem).

Consider $y$-composable tuples of power series
$f\in\mathbb{Q}[\\![x,y]\\!]^{k},g\in\mathbb{Q}[\\![x]\\!]^{k}$ s.t.

$\displaystyle f\,\circ_{y}\,g=0.$ (50)

Assume that the Jacobian matrix
$\partial_{y}f\in\mathbb{Q}[\\![x,y]\\!]^{k\times k}$ is invertible in the
ring of power series matrices
$(\partial_{y}f)^{-1}\in\mathbb{Q}[\\![x,y]\\!]^{k\times k}$, and moreover
$(\partial_{y}f)^{-1}$ is $y$-composable with $g$. If $f$ is CDF, then $g$ is
CDF.

######  Remark C.32.

We do not know whether the composability assumption on
$(\partial_{y}f)^{-1},g$ can be dropped. In applications, this is often
guaranteed by $g(0)=0$. Under this condition, $f(0,g(0))=f(0,0)=0$ and in this
case $g$ is the unique power series solution of 50. This is a consequence of
the _implicit power series theorem_ (cf. [63, Theorem 4],[51, Theorem 16.5]),
a variation of the _implicit function theorem_ well-known from analysis (cf.
[10, Theorem 9 on pg. 39],[71, Theorem 9.28]); cf. also [15, Theorem 2], where
a univariate _implicit stream theorem_ , in the special case where $f$ is a
polynomial, is presented in the context of the _stream calculus_ [72].

######  Example C.33.

To illustrate Lemma C.31, let $d=k=1$ and consider $y\cdot f-1=0$ for some CDF
$f\in\mathbb{Q}[\\![x]\\!]$. The Jacobian matrix is $\partial_{y}(y\cdot
f-1)=f$ and the invertibility assumption means $f(0)\neq 0$. Thus
$f^{-1}\in\mathbb{Q}[\\![x]\\!]$ exists and solves the equation. Since $f$ is
trivially $y$-composable with $f^{-1}$, by Lemma C.31 $f^{-1}$ is CDF.

We now prove Lemma C.30.

######  Proof C.34 (Proof of Lemma C.30).

Let $M=\left(M_{ij}\right)\in\mathbb{Q}[\\![x,y]\\!]^{k\times d}$ be a matrix
of CDF power series. Write

$\displaystyle\partial_{x_{j}}f_{i}=g_{ij},\ \text{with
}g_{ij}:=M_{ij}\,\circ_{y}\,f\in\mathbb{Q}[\\![x]\\!],\ \forall 1\leq i\leq
k,1\leq j\leq d.$

It suffices to show that the $g_{ij}$’s are CDF. We assume w.l.o.g. that
$M_{ij}$ satisfies equations of the form

$\displaystyle\partial_{x_{h}}M_{ij}$
$\displaystyle=p_{ijh}\,\circ_{z}\,M\quad\forall 1\leq h\leq d,\text{ and }$
$\displaystyle\partial_{y_{\ell}}M_{ij}$
$\displaystyle=q_{ij\ell}\,\circ_{z}\,M,\quad\forall 1\leq\ell\leq k,$

for some polynomials $p_{ijh},q_{ij\ell}\in\mathbb{Q}[x,y,z]$ and fresh
commuting variables $z=\left(z_{ij}\right)$ with $1\leq i\leq k$ and $1\leq
j\leq d$. (This can be guaranteed since 1) $M_{ij}$ is CDF and 2) we can add
auxiliary CDF power series to $M$ if necessary.) We apply the chain rule from
Lemma C.6,

$\displaystyle\partial_{x_{h}}g_{ij}$
$\displaystyle=\partial_{x_{h}}(M_{ij}\,\circ_{y}\,f)=$
$\displaystyle=\partial_{x_{h}}M_{ij}\,\circ_{y}\,f+\sum_{\ell=1}^{k}\left(\partial_{y_{\ell}}M_{ij}\,\circ_{y}\,f\right)\cdot\partial_{x_{h}}f_{\ell}=$
$\displaystyle=(p_{ijh}\,\circ_{z}\,M)\,\circ_{y}\,f+\sum_{\ell=1}^{k}\left((q_{ij\ell}\,\circ_{z}\,M)\,\circ_{y}\,f\right)\cdot
g_{\ell h}=$
$\displaystyle=(p_{ijh}\,\circ_{y}\,f)\,\circ_{z}\,(M\,\circ_{y}\,f)+\sum_{\ell=1}^{k}\left((q_{ij\ell}\,\circ_{y}\,f)\,\circ_{z}\,(M\,\circ_{y}\,f)\right)\cdot
g_{\ell h}=$
$\displaystyle=(p_{ijh}\,\circ_{y}\,f)\,\circ_{z}\,g+\sum_{\ell=1}^{k}\left((q_{ij\ell}\,\circ_{y}\,f)\,\circ_{z}\,g\right)\cdot
g_{\ell h}=$
$\displaystyle=p_{ijh}\,\circ_{y,z}\,\left(f,g\right)+\sum_{\ell=1}^{k}\left(q_{ij\ell}\,\circ_{y,z}\,\left(f,g\right)\right)\cdot
g_{\ell h}.$

Notice that $\partial_{x_{h}}M_{ij},f$ and $\partial_{y_{\ell}}M_{ij},f$ are
still $y$-composable by Lemma C.4. Moreover, since $p_{ijh}$ is a polynomial
and $f$ does not contain $z$, $p_{ijh}\,\circ_{y}\,f$ is a polynomial in $z$,
and thus $p_{ijh}\,\circ_{y}\,f,M\,\circ_{y}\,f$ are $z$-composable. Similarly
for $(q_{ij\ell}\,\circ_{y}\,f),(M\,\circ_{y}\,f)$. The last equation follows
from the fact that $f$ does not contain $z$. We have shown that
$\partial_{x_{h}}g_{ij}$ is a polynomial function of $x$, $f$, and $g$, as
required for $g$ to be CDF.

Thanks to Lemma C.30 we can now prove Lemma C.31.

######  Proof C.35 (Proof of Lemma C.31).

Let $g$ be a solution of 50. The composability assumption means that each
entry $f^{(i)}$ of $f=(f^{(1)},\dots,f^{(k)})$ is $y$-composable with $g$,
implying that $f^{(i)}\,\circ_{y}\,g$ is defined. By deriving
$f\,\circ_{y}\,g$ w.r.t. $x$ and applying the chain rule (Lemma C.6) in matrix
form we obtain

$\displaystyle\underbrace{\partial_{x}(f\,\circ_{y}\,g)}_{k\times
d}=\underbrace{\partial_{x}f}_{k\times
d}\,\circ_{y}\,g+(\underbrace{\partial_{y}f}_{k\times
k}\,\circ_{y}\,g)\cdot\underbrace{\partial_{x}g}_{k\times d}=0.$

First of all we show that the r.h.s. is well-defined. $\partial_{x}f,g$ and
$\partial_{y}f,g$ are $y$-composable.

######  Proof C.36 (Proof of the claim.).

We need to show that $\partial_{x_{j}}f^{(i)},g$ are $y$-composable. By
assumption $f^{(i)},g$ are $y$-composable and we can apply Lemma C.4. The
argument showing composability of $\partial_{y_{\ell}}f^{(i)},g$ is analogous.

Since by assumption the Jacobian matrix $\partial_{y}f$ is invertible as a
power series matrix, we can write

$\displaystyle\partial_{x}g=P\,\circ_{y}\,g,\ \text{where
}P:=-\underbrace{(\partial_{y}f)^{-1}}_{\mathbb{Q}[\\![x,y]\\!]^{k\times
k}}\cdot\underbrace{\partial_{x}f}_{\mathbb{Q}[\\![x,y]\\!]^{k\times
d}}\in\mathbb{Q}[\\![x,y]\\!]^{k\times d}.$

Notice that $P,g$ are $y$-composable since $(\partial_{y}f)^{-1},g$ are
$y$-composable by assumption and $\partial_{x}f,g$ are $y$-composable by the
claim. By Cramer’s rule, the entries of $(\partial_{y}f)^{-1}$ are rational
functions of the entries of $\partial_{y}f$. Since $f$ is CDF, by Lemma 3.1
$\partial_{x}f$, $\partial_{y}f$, and thus $(\partial_{y}f)^{-1}$ are CDF.
Thus $P$ is a matrix of CDF power series and we conclude by Lemma C.30.

The proof of Lemma 3.3 relies on two simple facts about matrices, which we
recall below in Lemmas C.37 and C.39. The following lemma provides a simple
condition guaranteeing that $\partial_{y}f$ is invertible as a power series
matrix.

######  Lemma C.37.

A power series matrix $M\in\mathbb{Q}[\\![z]\\!]^{k\times k}$ has a power
series matrix inverse $M^{-1}\in\mathbb{Q}[\\![z]\\!]^{k\times k}$ iff $M$
evaluated at the origin $M(0)\in\mathbb{Q}^{k\times k}$ is invertible (in
$\mathbb{Q}^{k\times k}$).

######  Proof C.38.

The crucial observation is that determinant and evaluation commute:

$\displaystyle(\det M)(0)=\det(M(0)).$

We now have a chain of equivalences: $M(0)$ is invertible iff $\det(M(0))\neq
0$ iff $(\det M)(0)\neq 0$ (the constant term of $\det
M\in\mathbb{Q}[\\![z]\\!]$ is nonzero) iff $\det M$ is invertible in
$\mathbb{Q}[\\![z]\\!]$ iff $M$ is invertible in
$\mathbb{Q}[\\![z]\\!]^{k\times k}$.

######  Lemma C.39.

Consider a rational matrix $M\in\mathbb{Q}^{k\times k}$. If $M$ is nilpotent,
then $I-M$ is invertible.

######  Proof C.40.

Since $M$ is nilpotent, there is $m\in\mathbb{N}$ s.t. $M^{m}=0$. Since the
matrix series $M^{*}:=\sum_{\ell=0}^{\infty}M^{\ell}$ exists (in fact it
equals $M^{0}+M^{1}+M^{2}+\cdots+M^{m-1}$), and $(I-M)\cdot M^{*}=M^{*}-M\cdot
M^{*}=I$, we conclude that $M^{*}$ is the inverse of $I-M$, and thus the
latter is invertible.

See 3.3

######  Proof C.41.

Let $g\in\mathbb{Q}[\\![x]\\!]^{k}$ be a solution of a constructible system
$y=f(x,y)$. The Jacobian of $\widetilde{f}:=y-f$ is
$\partial_{y}\widetilde{f}=I-\partial_{y}f$, where $I$ is the $k\times k$
identity matrix. By the well-posedness assumption, $\partial_{y}f$ evaluated
at the origin is nilpotent. By Lemma C.39, $\partial_{y}\widetilde{f}$
evaluated at the origin is invertible. By Lemma C.37,
$\partial_{y}\widetilde{f}$ has a power series matrix inverse
$(\partial_{y}\widetilde{f})^{-1}$. The condition $g(0)=0$ guarantees
$y$-composability of $g$ with $(\partial_{y}\widetilde{f})^{-1}$. We conclude
by Lemma C.31 applied to $\widetilde{f},g$.

Existence and uniqueness of canonical solutions is classic (cf., e.g., [47,
Theorem 6]). We can also obtain uniqueness from the previous construction,
since the CDF system for $g$ has a unique solution for every fixed initial
condition $g(0)$.

###  C.5 Lie derivatives and exchange rule

The purpose of this section is to show a formula for the computation of the
coefficients of a CDF power series (Lemma C.42). This will be used in § C.8 to
obtain algorithms for computing coefficients and deciding zeroness of CDF
power series, and analyse their complexity. In order to do this, we recall the
notion of Lie derivative.

For every $1\leq j\leq d$, define the _$j$ -th Lie derivative_ of an
autonomous CDF system of equations 9 as

$\displaystyle
L_{j}:=\sum_{h=1}^{k}P_{hj}\cdot\partial_{y_{h}}:\mathbb{Q}[y]\to\mathbb{Q}[y].$

Since $L_{j}$ is a linear combination of derivations $\partial_{y_{h}}$’s, it
is itself a derivation. Extend $L$ to sequences of indices as
$L_{\varepsilon}=1$ (the identity operator) and $L_{j\cdot w}=L_{w}L_{j}$
(operator composition), for every $w\in\left\\{1,\dots,d\right\\}^{*}$.

We show a formula to express coefficients of $p\,\circ_{y}\,f$ as a function
of the initial condition $f(0)$. This will be useful in the zeroness algorithm
(§ 3.4).

######  Lemma C.42.

For any solution $f$ of 9, $w\in\left\\{1,\dots,d\right\\}^{*}$,
$p\in\mathbb{Q}[y]$:

$\displaystyle\partial_{x}^{\\#({w})}(p\,\circ_{y}\,f)=L_{w}p\,\circ_{y}\,f\text{
and }[x^{\\#({w})}](p\,\circ_{y}\,f)=L_{w}p\,\circ_{y}\,f(0).$

######  Proof C.43.

The first equality is proved by induction. The base case $w=\varepsilon$ is
clear, since both $\partial_{x}^{0}$ and $L_{\varepsilon}$ are the identity.
For the inductive step,

$\displaystyle\partial_{x}^{\\#({j\cdot w})}(p\,\circ_{y}\,f)$
$\displaystyle=\partial_{x}^{\\#({w})}\partial_{x_{j}}(p\,\circ_{y}\,f)=\partial_{x}^{\\#({w})}(L_{j}p\,\circ_{y}\,f)=$
$\displaystyle=L_{w}L_{j}p\,\circ_{y}\,f=L_{j\cdot w}p\,\circ_{y}\,f.$

For the second equality, we compute:

$\displaystyle[x^{\\#({w})}](p\,\circ_{y}\,f)$ (by 8)
$\displaystyle=[x^{0}](\partial_{x}^{\\#({w})}(p\,\circ_{y}\,f))=$ (by the
first equality) $\displaystyle=[x^{0}](L_{w}p\,\circ_{y}\,f)=$ ($[x^{0}]$
homomorphism) $\displaystyle=L_{w}p\,\circ_{y}\,[x^{0}]f=$
$\displaystyle=L_{w}p\,\circ_{y}\,f(0).$

###  C.6 CDF and commutative WBPP

In this section we provide a proof of the fact that CDF power series coincide
with WBPP series which are commutative.

See 3.5

######  Proof C.44.

For the first direction, let
$f\in\mathbb{Q}\langle\\!\langle\Sigma\rangle\\!\rangle$ be a commutative
shuffle-finite series. Thanks to Lemma B.7, we have

$\displaystyle f=f^{(1)}\in\mathbb{Q}[f^{(1)},\dots,f^{(k)}],$

where the latter ring is closed under $\delta_{a_{j}}$, for every $1\leq j\leq
d$. Let
$g^{(i)}:=\mathsf{s2p}\left(f^{(i)}\right)=\sum_{n\in\mathbb{N}^{d}}f^{(i)}_{w_{n}}\cdot\frac{x^{n}}{n!}$
be the corresponding commutative series, for every $1\leq i\leq k$. Here, for
every $n\in\mathbb{N}^{d}$, we have fixed a word $w_{n}\in\Sigma^{*}$ s.t.
$\\#({w_{n}})=n$. Consider the power series ring

$\displaystyle R:=\mathbb{Q}[g^{(1)},\dots,g^{(k)}].$

Clearly $\mathsf{s2p}\left(f^{(1)}\right)\in R$. It remains to show that $R$
is closed under $\partial_{x_{j}}$, for every $1\leq j\leq d$.

We begin with a combinatorial equality which will be useful in the rest of the
proof. For every $x,y\in\mathbb{N}^{d}$, we have

$\displaystyle\sum_{\\#({u})=x,\\#({v})=y}(u\operatorname{\oldshuffle}v)=\sum_{\\#({w})=x+y}{\\#({w})\choose
x,y}\cdot w,$ (51)

where the l.h.s. sum is over $u,v\in\Sigma^{*}$ and the r.h.s. sum is over
$w\in\Sigma^{*}$.

######  Proof C.45 (Proof of the claim.).

Since the shuffle product enjoys bilinearity, associativity, commutativity,
and distributivity over sum, we have

$\displaystyle\sum_{\\#({u})=x,\\#({v})=y}(u\operatorname{\oldshuffle}v)=$
$\displaystyle=\left(\sum_{\\#({u})=x}u\right)\operatorname{\oldshuffle}\left(\sum_{\\#({v})=y}v\right)=$
$\displaystyle=\left(a_{1}^{x_{1}}\operatorname{\oldshuffle}\cdots\operatorname{\oldshuffle}a_{d}^{x_{d}}\right)\operatorname{\oldshuffle}\left(a_{1}^{y_{1}}\operatorname{\oldshuffle}\cdots\operatorname{\oldshuffle}a_{d}^{y_{d}}\right)=$
$\displaystyle=(a_{1}^{x_{1}}\operatorname{\oldshuffle}a_{1}^{y_{1}})\operatorname{\oldshuffle}\cdots\operatorname{\oldshuffle}(a_{d}^{x_{d}}\operatorname{\oldshuffle}a_{d}^{y_{d}})=$
$\displaystyle=\left({x_{1}+y_{1}\choose
x_{1},y_{1}}a_{1}^{x_{1}+y_{1}}\right)\operatorname{\oldshuffle}\cdots\operatorname{\oldshuffle}\left({x_{d}+y_{d}\choose
x_{d},y_{d}}a_{d}^{x_{d}+y_{d}}\right)=$ $\displaystyle={x_{1}+y_{1}\choose
x_{1},y_{1}}\cdots{x_{d}+y_{d}\choose
x_{d},y_{d}}\cdot\left(a_{1}^{x_{1}+y_{1}}\operatorname{\oldshuffle}\cdots\operatorname{\oldshuffle}a_{d}^{x_{d}+y_{d}}\right)=$
$\displaystyle={x+y\choose
x,y}\cdot\left(a_{1}^{x_{1}+y_{1}}\operatorname{\oldshuffle}\cdots\operatorname{\oldshuffle}a_{d}^{x_{d}+y_{d}}\right)=$
$\displaystyle={x+y\choose x,y}\cdot\sum_{\\#({w})=x+y}w=$
$\displaystyle=\sum_{\\#({w})=x+y}{\\#({w})\choose x,y}\cdot w.$

In the next claim we show a commutation rule for partial derivative
$\partial_{x_{j}}$ w.r.t. $\mathsf{s2p}\left(\\_\right)$ and shift
$\delta_{a_{j}}$. For every commutative series
$f\in\mathbb{Q}\langle\\!\langle\Sigma\rangle\\!\rangle$ and $1\leq j\leq d$,

$\displaystyle\partial_{x_{j}}(\mathsf{s2p}\left(f\right))=\mathsf{s2p}\left(\delta_{a_{j}}f\right).$
(52)

######  Proof C.46 (Proof of the claim).

$\displaystyle\partial_{x_{j}}(\mathsf{s2p}\left(f\right))$
$\displaystyle=\partial_{x_{j}}\sum_{n\in\mathbb{N}^{d}}f_{w_{n}}\cdot\frac{x^{n}}{n!}=$
$\displaystyle=\sum_{n\in\mathbb{N}^{d}}f_{w_{n}}\cdot\partial_{x_{j}}\frac{x^{n}}{n!}=$
$\displaystyle=\sum_{n\in\mathbb{N}^{d},n_{j}\geq
1}f_{w_{n}}\cdot\frac{x^{n-e_{j}}}{(n-e_{j})!}=$
$\displaystyle=\sum_{n\in\mathbb{N}^{d}}f_{w_{n+e_{j}}}\cdot\frac{x^{n}}{n!}=(*)$
$\displaystyle=\sum_{n\in\mathbb{N}^{d}}f_{a_{j}\cdot
w_{n}}\cdot\frac{x^{n}}{n!}=$
$\displaystyle=\sum_{n\in\mathbb{N}^{d}}(\delta_{a_{j}}f)_{w_{n}}\cdot\frac{x^{n}}{n!}=$
$\displaystyle=\mathsf{s2p}\left(\delta_{a_{j}}f\right).$

The crucial equality is $(*)$ where we have used commutativity to deduce
$f_{w_{n+e_{j}}}=f_{a_{j}\cdot w_{n}}$.

In the next claim we show that $\mathsf{s2p}\left(\\_\right)$ is a
homomorphism from the ring of commutative shuffle series to the ring of power
series. For every commutative series
$f,g\in\mathbb{Q}\langle\\!\langle\Sigma\rangle\\!\rangle$,

$\displaystyle\mathsf{s2p}\left(f+g\right)=\mathsf{s2p}\left(f\right)+\mathsf{s2p}\left(g\right),$
(53)
$\displaystyle\mathsf{s2p}\left(f\operatorname{\oldshuffle}g\right)=\mathsf{s2p}\left(f\right)\cdot\mathsf{s2p}\left(g\right).$
(54)

######  Proof C.47 (Proof of the claim).

Additivity follows immediately from the definitions. We now show 54. For every
word $w\in\Sigma^{*}$, write $f_{\\#({w})}:=f_{w}$ and $g_{\\#({w})}:=g_{w}$,
which is well defined since $f,g$ are commutative.

$\displaystyle\mathsf{s2p}\left(f\operatorname{\oldshuffle}g\right)$
$\displaystyle=\mathsf{s2p}\left(\left(\sum_{u\in\Sigma^{*}}f_{u}\cdot
u\right)\operatorname{\oldshuffle}\left(\sum_{v\in\Sigma^{*}}g_{v}\cdot
v\right)\right)=$
$\displaystyle=\mathsf{s2p}\left(\left(\sum_{a\in\mathbb{N}^{d}}f_{a}\cdot\sum_{\\#({u})=a}u\right)\operatorname{\oldshuffle}\left(\sum_{b\in\mathbb{N}^{d}}g_{b}\cdot\sum_{\\#({v})=b}v\right)\right)=$
$\displaystyle=\mathsf{s2p}\left(\sum_{a,b\in\mathbb{N}^{d}}f_{a}f_{b}\cdot\sum_{\\#({u})=a,\\#({v})=b}u\operatorname{\oldshuffle}v\right)=\text{(by\leavevmode\nobreak\
\lx@cref{creftype~refnum}{eq:shuffle combinatorial identity})}$
$\displaystyle=\mathsf{s2p}\left(\sum_{a,b\in\mathbb{N}^{d}}f_{a}f_{b}\cdot\sum_{\\#({w})=a+b}{a+b\choose
a,b}\cdot w\right)=$
$\displaystyle=\mathsf{s2p}\left(\sum_{a,b\in\mathbb{N}^{d}}f_{a}f_{b}\cdot{a+b\choose
a,b}\cdot\sum_{\\#({w})=a+b}w\right)=$
$\displaystyle=\sum_{a,b\in\mathbb{N}^{d}}f_{a}f_{b}\cdot{a+b\choose
a,b}\cdot\frac{x^{a+b}}{(a+b)!}=$
$\displaystyle=\left(\sum_{a\in\mathbb{N}^{d}}f_{a}\cdot\frac{x^{a}}{a!}\right)\cdot\left(\sum_{b\in\mathbb{N}^{d}}f_{b}\cdot\frac{x^{b}}{b!}\right)=$
$\displaystyle=\mathsf{s2p}\left(f\right)\cdot\mathsf{s2p}\left(g\right).$

We can now apply the previous two claims and compute

$\displaystyle\partial_{x_{j}}g^{(i)}$
$\displaystyle=\partial_{x_{j}}(\mathsf{s2p}\left(f^{(i)}\right))=$ (by 52)
$\displaystyle=\mathsf{s2p}\left(\delta_{a_{j}}f^{(i)}\right)=$
$\displaystyle=\mathsf{s2p}\left(p_{j}^{(i)}\,\circ_{y}\,\left(f^{(1)},\dots,f^{(k)}\right)\right)=$
(by 53 and 54)
$\displaystyle=p_{j}^{(i)}(\mathsf{s2p}\left(f^{(1)}\right),\dots,\mathsf{s2p}\left(f^{(k)}\right))=$
$\displaystyle=p_{j}^{(i)}(g^{(1)},\dots,g^{(k)})\in\mathbb{Q}[g^{(1)},\dots,g^{(k)}].$

This shows that $\partial_{x_{j}}g^{(i)}$ belongs to
$\mathbb{Q}[g^{(1)},\dots,g^{(k)}]$, as required.

For the other direction, let $f\in\mathbb{Q}[\\![x]\\!]$ be a CDF power
series. Thanks to Lemma C.1, we have

$\displaystyle f=f^{(1)}\in\mathbb{Q}[f^{(1)},\dots,f^{(k)}],$

where the latter ring is closed under $\partial_{x_{j}}$, for every $1\leq
j\leq d$. Write
$f^{(i)}=\sum_{n\in\mathbb{N}^{d}}f^{(i)}_{n}\cdot\frac{x^{n}}{n!}$ and let
$g^{(i)}:=\mathsf{p2s}\left(f^{(i)}\right)=\sum_{w\in\Sigma^{*}}f^{(i)}_{\\#({w})}\cdot
w$ be the corresponding commutative series, for every $1\leq i\leq k$. We
claim that

$\displaystyle\mathbb{Q}[g^{(1)},\dots,g^{(k)}]$

is closed under $\delta_{a_{j}}$, for every $1\leq j\leq d$. It suffices to
show this for the generators.

The following two claims show that $\mathsf{p2s}\left(\\_\right)$ is a
homomorphism from the power series to the series ring which respects their
differential structure. For every power series $f\in\mathbb{Q}[\\![x]\\!]$ and
$1\leq j\leq d$, we have

$\displaystyle\delta_{a_{j}}(\mathsf{p2s}\left(f\right))=\mathsf{p2s}\left(\partial_{x_{j}}f\right).$
(55)

######  Proof C.48 (Proof of the claim.).

We compute:

$\displaystyle\delta_{a_{j}}(\mathsf{p2s}\left(f\right))$
$\displaystyle=\delta_{a_{j}}\sum_{w\in\Sigma^{*}}f_{\\#({w})}\cdot w=$
$\displaystyle=\sum_{w\in\Sigma^{*}}f_{\\#({w})}\cdot\delta_{a_{j}}w=$
$\displaystyle=\sum_{w\in\Sigma^{*}}f_{\\#({a_{j}\cdot
w})}\cdot\delta_{a_{j}}(a_{j}\cdot w)=$
$\displaystyle=\sum_{w\in\Sigma^{*}}f_{\\#({w})+e_{j}}\cdot w=$
$\displaystyle=\sum_{w\in\Sigma^{*}}(\partial_{x_{j}}f)_{\\#({w})}\cdot w=$
$\displaystyle=\mathsf{p2s}\left(\partial_{x_{j}}f\right).$

For every two power series $f,g\in\mathbb{Q}[\\![x]\\!]$, we have

$\displaystyle\mathsf{p2s}\left(f+g\right)=\mathsf{p2s}\left(f\right)+\mathsf{p2s}\left(g\right),$
(56) $\displaystyle\mathsf{p2s}\left(f\cdot
g\right)=\mathsf{p2s}\left(f\right)\operatorname{\oldshuffle}\mathsf{p2s}\left(g\right).$
(57)

######  Proof C.49 (Proof of the claim.).

Additivity follows immediately from the definitions. Regarding 57, we have

$\displaystyle\mathsf{p2s}\left(f\right)\operatorname{\oldshuffle}\mathsf{p2s}\left(g\right)$
$\displaystyle=\left(\sum_{u\in\Sigma^{*}}f_{\\#({u})}\cdot
u\right)\operatorname{\oldshuffle}\left(\sum_{v\in\Sigma^{*}}g_{\\#({v})}\cdot
v\right)=$
$\displaystyle=\sum_{u,v\in\Sigma^{*}}f_{\\#({u})}g_{\\#({v})}\cdot(u\operatorname{\oldshuffle}v)=$
$\displaystyle=\sum_{x,y\in\mathbb{N}^{d}}f_{x}g_{y}\sum_{\\#({u})=x,\\#({v})=y}(u\operatorname{\oldshuffle}v)=\text{(by\leavevmode\nobreak\
\lx@cref{creftype~refnum}{eq:shuffle combinatorial identity})}$
$\displaystyle=\sum_{x,y\in\mathbb{N}^{d}}f_{x}g_{y}\sum_{\\#({w})=x+y}{\\#({w})\choose
x,y}\cdot w=$
$\displaystyle=\sum_{w\in\Sigma^{*}}\sum_{x+y=\\#({w})}{\\#({w})\choose
x,y}f_{x}g_{y}\cdot w=$
$\displaystyle=\mathsf{p2s}\left(\sum_{n\in\mathbb{N}^{d}}\sum_{x+y=n}{n\choose
x,y}f_{x}g_{y}\cdot x^{n}\right)=$ $\displaystyle=\mathsf{p2s}\left(f\cdot
g\right).$

Thanks to the last two claims we have

$\displaystyle\delta_{a_{j}}g^{(i)}=$
$\displaystyle=\delta_{a_{j}}(\mathsf{p2s}\left(f^{(i)}\right))=$ (by 55)
$\displaystyle=\mathsf{p2s}\left(\partial_{x_{j}}f^{(i)}\right)=$
$\displaystyle=\mathsf{p2s}\left(p_{j}^{(i)}(f^{(1)},\dots,f^{(k)})\right)=$
(by 56 and 57)
$\displaystyle=p_{j}^{(i)}\,\circ_{y}\,\left(\mathsf{p2s}\left(f^{(1)}\right),\dots,\mathsf{p2s}\left(f^{(k)}\right)\right)=$
$\displaystyle=p_{j}^{(i)}\,\circ_{y}\,\left(g^{(1)},\dots,g^{(k)}\right)\in\mathbb{Q}[g^{(1)},\dots,g^{(k)}].$

This shows that $\delta_{a_{j}}g^{(i)}$ is in the ring
$\mathbb{Q}[g^{(1)},\dots,g^{(k)}]$, as required.

###  C.7 Number sequences and binomial convolution

In this short section we recall a classical connection between power series
and numeric sequences. Let the set of number sequences
$\mathbb{N}^{d}\to\mathbb{Q}$ be denoted for brevity by
$\mathbb{Q}[\\![\mathbb{N}^{d}]\\!]$. Consider two number sequences
$f,g\in\mathbb{Q}[\\![\mathbb{N}^{d}]\\!]$. Their sum $f+g$ is the sequence
obtained by pointwise sum, and the sequence $c\cdot f$ for a scalar
$c\in\mathbb{Q}$ is obtained by multiplying by $c$ the value of $f$. This
endows the set of number sequences with the structure of a vector space. The
_binomial convolution_ of two sequences $f,g$ is the number sequence
$f\operatorname{\ast}g$ s.t. for every $n\in\mathbb{N}^{d}$,

$\displaystyle(f\operatorname{\ast}g)_{n}:=\sum_{m\leq
n}\binom{n}{m}f_{m}g_{m-n},\ \text{with
}\binom{n}{m}:=\binom{n_{1}}{m_{1}}\cdots\binom{n_{d}}{m_{d}}.$ (58)

Binomial convolution is associative, commutative, with identity the sequence
$f$ s.t. $f_{0}=1$ and zero everywhere else. In this way we have endowed
number sequences with the structure of a commutative ring. Since binomial
convolution is bilinear, it also endows number sequences with the structure of
an algebra over $\mathbb{Q}$.

The _$j$ -th shift_ of a sequence $f\in\mathbb{Q}[\\![\mathbb{N}^{d}]\\!]$ is
the sequence $\sigma_{j}f$ which maps $n$ to $f_{n+e_{j}}$, where $n+e_{j}$ is
obtained from $n$ by increasing the $j$-th coordinate by $1$. The shifts
$\sigma_{j}$’s are pairwise commutative and endow the sequences ring / algebra
with a differential structure since they obey Leibniz rule

$\displaystyle\sigma_{j}(f\operatorname{\ast}g)=\sigma_{j}f\operatorname{\ast}g+f\operatorname{\ast}\sigma_{j}g.$
(59)

######  Definition C.50.

A sequence $f\in\mathbb{Q}[\\![\mathbb{N}^{d}]\\!]$ is _binomial-convolution
finite_ if it belongs to a finitely generated subalgebra of
$\left(\mathbb{Q}[\\![\mathbb{N}^{d}]\\!];{+},{\operatorname{\ast}}\right)$
closed under shifts $\sigma_{j}$’s for every $1\leq j\leq d$.

In analogy with other composition operators, define the composition of a
polynomial $p\in\mathbb{Q}[k]$ and a tuple of number sequences
$f\in\mathbb{Q}[\\![\mathbb{N}^{d}]\\!]^{k}$ as the number sequence
$p\operatorname{\circ\,}f$ obtained by replacing the $i$-th variable in $p$ by
$f^{(i)}$ and interpreting polynomial multiplication by binomial convolution.
The following is our working definition of binomial-convolution finite
sequences.

######  Lemma C.51.

A number sequence $f^{(1)}\in\mathbb{Q}[\\![\mathbb{N}^{d}]\\!]$ is binomial-
convolution finite iff there exist number sequences
$f^{(2)},\dots,f^{(k)}\in\mathbb{Q}[\\![\mathbb{N}^{d}]\\!]$, and polynomials
$p_{j}^{(i)}\in\mathbb{Q}[k]$ for every $1\leq j\leq d$ and $1\leq i\leq k$,
s.t. for every $1\leq j\leq d$:

$\displaystyle\left\\{\begin{array}[]{rcl}\sigma_{j}f^{(1)}&=&p^{(1)}_{j}\operatorname{\circ\,}\left(f^{(1)},\dots,f^{(k)}\right),\\\
&\vdots&\\\
\sigma_{j}f^{(k)}&=&p^{(k)}_{j}\operatorname{\circ\,}\left(f^{(1)},\dots,f^{(k)}\right).\end{array}\right.$
(63)

####  C.7.1 Connection with CDF power series

At this point, the analogy between binomial-convolution finite sequences and
CDF power series should be evident. The _exponential generating power series_
of a number sequence $f\in\mathbb{Q}[\\![\mathbb{N}^{d}]\\!]$ is the power
series

$\displaystyle\mathsf{EGS}[f]:=\sum_{n\in\mathbb{N}}f_{n}\cdot\frac{x^{n}}{n!}.$

In the other direction, we can transform a power series
$f\in\mathbb{Q}[\\![d]\\!]$ to a number sequence
$g\in\mathbb{Q}[\\![\mathbb{N}^{d}]\\!]$ with the coefficient extraction
operation $g_{n}:=[x^{n}]f$. Clearly, these two operations are one the inverse
of the other. There are a number of notable identities connecting the
$\mathsf{EGS}[\\_]$ transform and operations on number sequences.

$\mathbb{Q}[\\![\mathbb{N}^{d}]\\!]$ | $\mathbb{Q}[\\![d]\\!]$
---|---
$f$ | $\mathsf{EGS}[f]$
$c\cdot f$ | $c\cdot\mathsf{EGS}[f]$
$f+g$ | $\mathsf{EGS}[f]+\mathsf{EGS}[g]$
$f\operatorname{\ast}g$ | $\mathsf{EGS}[f]\cdot\mathsf{EGS}[g]$
$\sigma_{j}f$ | $\partial_{x_{j}}\mathsf{EGS}[f]$
$p\operatorname{\circ\,}\left(f^{(1)},\dots,f^{(k)}\right)$ | $p\operatorname{\circ\,}\left(\mathsf{EGS}[f^{(1)}],\dots,\mathsf{EGS}[f^{(k)}]\right)$

The connection between binomial-convolution finite sequences and CDF power
series stated below follows immediately from the identities above.

######  Lemma C.52.

A number sequence $f\in\mathbb{Q}[\\![\mathbb{N}^{d}]\\!]$ is binomial-
convolution finite iff its exponential power series
$\mathsf{EGS}[f]\in\mathbb{Q}[\\![x]\\!]$ is CDF.

This interpretation will be useful when computing CDF power series
coefficients in § C.8.

###  C.8 Computing coefficients of CDF power series

In this section we provide more details on the complexity of computing CDF
power series coefficients.

####  C.8.1 Coefficient growth

We show that coefficients and denominators of a CDF power series do not grow
too fast. We being with a bound on the growth of coefficients.

######  Lemma C.53.

Let $f\in\mathbb{Q}[\\![d]\\!]^{k}$ be a tuple of CDF power series satisfying
a CDF system of degree $\leq D$, order $\leq k$, height $\leq H$, and with
initial value $\left|f(0)\right|_{\infty}\leq H$. For every
$n\in\mathbb{N}^{d}$,

$\displaystyle\left|[x^{n}]f\right|_{\infty}\leq(\left|n\right|_{1}D+k)^{O\left(\left|n\right|_{1}\cdot
k\right)}\cdot H^{O\left(\left|n\right|_{1}\cdot D\right)}.$

######  Remark C.54.

For univariate power series $f$ solving an algebraic differential equation, a
bound $\left|[x^{n}]f/n!\right|\leq(n!)^{O\left(1\right)}$ was previously
known [55, Theorem 16]. For univariate CDF power series, [7, Theorem 3] shows
the more precise bound $\left|[x^{n}]f\right|\leq\alpha^{n}\cdot n!$, later
generalised to the multivariate case [8, Theorem 11]. None of these bounds
provide details on the precise dependency of the exponent on the parameters of
the system, such as degree $D$, height $H$, and order $k$, which we need in
our complexity analysis.

######  Proof C.55.

By Lemma C.42, the coefficient of $x^{n}$ of component $f^{(i)}$ of a solution
$f$ of 9 can be expressed as
$[x^{n}]f^{i}=[x^{n}](y_{i}\,\circ_{y}\,f)=L_{w}y_{i}(f(0))$, for any
$w\in\Sigma^{*}$ s.t. $\\#({w})=n$. The bound follows as a corollary of 22 in
Lemma A.6 regarding the complexity of $L_{w}y_{i}$.

We now state a bound on the growth of denominators of CDF power series
coefficients. The following bound has appeared in [7, Theorem 3(iii)] in the
univariate context, later generalised to the multivariate context in [8,
Theorem 14(iii)]. Since no proof appeared in the multivariate context, we
provide one for completeness.

######  Lemma C.56.

Let $f\in\mathbb{Q}[\\![d]\\!]^{k}$ with $f_{0}=0$ be a tuple of CDF power
series solving 9. Let $q\in\mathbb{N}$ be a common denominator of all rational
constants appearing in the kernel $P_{ij}\in\mathbb{Q}[y]$. We have

$\displaystyle
q^{\left|n\right|_{1}}\cdot[x^{n}]f\in\mathbb{Z}^{k},\quad\forall
n\in\mathbb{N}^{d}.$ (64)

######  Proof C.57.

There are integer polynomials $Q_{ij}\in\mathbb{Z}[y]$ s.t.
$P_{ij}=q^{-1}\cdot Q_{ij}$. By extracting the coefficient of $x^{n}$ on both
sides of 9 and using 8, we have

$\displaystyle[x^{n+e_{j}}]f^{(i)}=q^{-1}\cdot[x^{n}](Q_{ij}\,\circ_{y}\,f).$
(65)

We show 64 by induction on $\left|n\right|_{1}$. The base case
$\left|n\right|_{1}=0$ holds by the assumption $f_{0}=0\in\mathbb{N}$. For the
inductive step, consider a coordinate $1\leq j\leq d$ and write

$\displaystyle q^{\left|n+e_{j}\right|_{1}}\cdot[x^{n+e_{j}}]f^{(i)}$
$\displaystyle=q^{\left|n\right|_{1}+1}\cdot
q^{-1}\cdot[x^{n}](Q_{ij}\,\circ_{y}\,f)=$
$\displaystyle=q^{\left|n\right|_{1}}\cdot[x^{n}](Q_{ij}\,\circ_{y}\,f).$

By the correspondence between power series product and binomial convolution of
number sequences, $[x^{n}](Q_{ij}\,\circ_{y}\,f)$ is a sum with integer
coefficients of products of the form
$[x^{n_{1}}]f^{(i_{1})}\cdots[x^{n_{\ell}}]f^{(i_{\ell})}$ where
$n_{1}+\cdots+n_{\ell}=n$. By inductive assumption, for each factor we have

$\displaystyle
q^{\left|n_{1}\right|_{1}}\cdot[x^{n_{1}}]f^{(i_{1})},\dots,q^{\left|n_{\ell}\right|_{1}}\cdot[x^{n_{\ell}}]f^{(i_{\ell})}\in\mathbb{Z},$

and thus for their product

$\displaystyle
q^{\left|n\right|_{1}}\cdot[x^{n_{1}}]f^{(i_{1})}\cdots[x^{n_{\ell}}]f^{(i_{\ell})}\in\mathbb{Z}$

as well.

####  C.8.2 Complexity of computing CDF coefficients

We now provide complexity bounds on computing coefficients of CDF power series
satisfying systems of CDF equations with integer coefficients.

See 3.6

######  Proof C.58.

By the stars and bars argument in combinatorics the number of $d$-variate
monomials of total degree equal to $N$ is $\binom{N+d-1}{d-1}$. The number of
$d$-variate monomials of total degree $\leq N$ can be counted by adding an
extra variable and count the number of monomials of total degree equal to $N$,
which consequently is $\binom{N+d}{d}$.

We build a table of size $\leq k\cdot\binom{N+d}{d}$ where we store all values
$f_{n}:=[x^{n}]f\in\mathbb{Z}^{k}$ required during the computation, for all
$\left|n\right|_{1}\leq N$. Indeed, for each sequence $f^{(i)}$ (with $1\leq
i\leq k$) the number of coefficients $f^{(i)}_{n}=[x^{n}]f^{(i)}$ with
$\left|n\right|_{1}\leq N$ equals the number of $d$-variate monomials of total
degree $\leq N$. Generalising 58, we can compute a specific entry
$n\in\mathbb{N}^{d}$ of a convolution product
$g:=g^{(1)}\operatorname{\ast}\cdots\operatorname{\ast}g^{(e)}$ with the
formula

$\displaystyle
g_{n}=\sum_{m^{(1)}+\cdots+m^{(e)}=n}\binom{n}{m^{(1)},\dots,m^{(e)}}g^{(1)}_{m^{(1)}}\cdots
g^{(e)}_{m^{(e)}},$ (66)

where the vectorial multinomial coefficient is defined as

$\displaystyle\binom{n}{m^{(1)},\dots,m^{(e)}}:=\frac{n!}{m^{(1)}!\cdots
m^{(e)}!}\in\mathbb{N}.$ (67)

The multinomial coefficient 67 can be computed with $O\left(N\right)$
arithmetic operations.

######  Proof C.59.

We expand the vectorial notation in 67 by writing
$n=\left(n_{1},\dots,n_{d}\right),m^{(\ell)}=\left(m^{(\ell)}_{1},\dots,m^{(\ell)}_{d}\right)\in\mathbb{N}^{d}$
and we have

$\displaystyle\binom{n}{m^{(1)},\dots,m^{(e)}}=\frac{n_{1}!}{m^{(1)}_{1}!\cdots
m^{(e)}_{1}!}\cdots\frac{n_{d}!}{m^{(1)}_{d}!\cdots m^{(e)}_{d}!}$

where, for every $1\leq j\leq d$, we have the balancing condition
$m^{(1)}_{j}+\cdots+m^{(e)}_{j}=n_{j}$. Computing the numerator requires
$n_{1}+\cdots+n_{d}=\left|n\right|_{1}$ products, and the same is true for the
denominator, thanks to the balancing condition. Thus
$2\cdot\left|n\right|_{1}$ products suffice and at the end we perform one
integer division.

For every $n\in\mathbb{N}^{d}$ and $e\in\mathbb{N}$ with
$\left|n\right|_{1}\leq N$ and $e\leq D$, we can compute 66 with
$O\left((N+D)\cdot\binom{N+d\cdot D-1}{d\cdot D-1}\right)$ arithmetic
operations.

######  Proof C.60 (Proof of the claim).

Each summand of 66 requires $e-1\leq D-1$ binary products to compute
$g^{(1)}_{m^{(1)}}\cdots g^{(e)}_{m^{(e)}}$ and $O\left(N\right)$ arithmetic
operations for the multinomial coefficient (by the previous claim). We now
estimate the number of summands of 66. Every tuple of vectors
$(m^{(1)},\dots,m^{(e)})\in(\mathbb{N}^{d})^{e}$ corresponds to a monomial in
$d\cdot e$ variables. Since these vectors sum up to $n\in\mathbb{N}^{d}$, the
total degree of the monomial is $\left|n\right|_{1}$. It follows that there
are $\leq\binom{\left|n\right|_{1}+d\cdot e-1}{d\cdot e-1}$ such summands. The
latter quantity is monotone in $\left|n\right|_{1}$ and $e$, and thus it is
bounded by $\leq\binom{N+d\cdot D-1}{d\cdot D-1}$.

Suppose a certain portion of the table has already been filled in, and
consider an index $n\in\mathbb{N}^{d}$ s.t. $\left|n\right|_{1}<N$,
$f_{m}\in\mathbb{Z}^{k}$ is already in the table for every $m\leq n$, but
$f^{(i)}_{n+e_{j}}$ is not in the table for some $1\leq j\leq d$ and $1\leq
i\leq k$. Extract the term $n\in\mathbb{N}^{d}$ on both sides of 63:

$\displaystyle
f^{(i)}_{n+e_{j}}=\left(p^{(i)}_{j}\operatorname{\circ\,}\left(f^{(1)},\dots,f^{(k)}\right)\right)_{n},\quad\forall
1\leq i\leq k,1\leq j\leq d.$ (68)

This means that $f^{(i)}_{n+e_{j}}$ is a polynomial function of previous
values $f^{(h)}_{m}$’s with $1\leq h\leq k$ and $m\leq n$. Polynomial
$p^{(i)}_{j}\in\mathbb{Z}[k]$ has total degree $\leq D$ and it is $k$-variate,
therefore it contains at most $\binom{D+k}{k}$ monomials. Thanks to the
previous claim, entry $n\in\mathbb{N}^{d}$ in the convolution product arising
from each such monomial can be computed with

$O\left((N+D)\cdot\binom{N+d\cdot D-1}{d\cdot D-1}\right)$

arithmetic operations. Combining these two facts yields the next claim. We can
compute entry $f^{(i)}_{n}\in\mathbb{Z}$ of the table with a number of
arithmetic operations at most

$\displaystyle O\left(\binom{D+k}{k}\cdot(N+D)\cdot\binom{N+d\cdot D-1}{d\cdot
D-1}\right).$

By the previous claim and the fact that the table has $\leq
k\cdot\binom{N+d}{d}$ entries, we can compute the whole table with a number of
arithmetic operations bounded by

$\displaystyle\leq
O\left(k\cdot\binom{N+d}{d}\cdot\binom{D+k}{k}\cdot(N+D)\cdot\binom{N+d\cdot
D-1}{d\cdot D-1}\right)\leq$ $\displaystyle\leq
O\left(k\cdot(N+d)^{d}(D+k)^{k}\cdot(N+D)\cdot(N+d\cdot D-1)^{d\cdot
D-1}\right)\leq$ $\displaystyle\leq(N+d\cdot D+k)^{O\left(d\cdot D+k\right)}.$

By Lemma C.53, numbers in the table are exponentially bounded in $N$, $k$, and
$D$, and in fact each of them can be stored with a number of bits bounded by

$\displaystyle O\left(N\cdot k\cdot\log(N\cdot D+k)+N\cdot D\cdot\log
H\right).$

Since an arithmetic operation (sum or multiplication) on two $b$-bits integer
numbers can be performed in $O\left(b^{2}\right)$ deterministic time, the
total time necessary to build the table is

$\displaystyle(N+d\cdot D+k)^{O\left(d\cdot D+k\right)}\cdot(N\cdot
k\cdot\log(N\cdot D+k)+N\cdot D\cdot\log H)^{O\left(1\right)}$
$\displaystyle\leq(N+d\cdot D+k)^{O\left(d\cdot D+k\right)}\cdot(\log
H)^{O\left(1\right)}.$

####  C.8.3 Complexity of the CDF zeroness problem

In the next lemma we argue that a CDF power series is zero iff just a few
initial coefficients are zero.

See 3.8

######  Proof C.61.

We construct the ideal chain 6 as in the case of WBPP, where $\Delta_{w}$ is
replaced by $L_{w}$, and $\alpha$ by $p$. Let $M\in\mathbb{N}$ be the index
when this chain stabilises, $I_{M}=I_{M+1}=I_{M+2}=\cdots$. Consider now an
arbitrary word $w\in\Sigma^{*}$. Since $L_{w}p\in I_{M}$, we can write

$\displaystyle L_{w}p=q_{1}\cdot L_{w_{1}}p+\cdots+q_{m}\cdot L_{w_{m}}p,$

for some short words $w_{1},\dots,w_{m}\in\Sigma^{\leq M}$ and polynomial
multipliers $q_{1},\dots,q_{m}\in\mathbb{Q}[y]$. We now compose with $f$ on
the right and by Lemma C.42 we have

$\displaystyle\partial_{x}^{\\#({w})}g$
$\displaystyle=L_{w}p\operatorname{\circ\,}f=$
$\displaystyle=\underbrace{(q_{1}\operatorname{\circ\,}f)}_{=:\;g_{1}}\cdot(L_{w_{1}}p\operatorname{\circ\,}f)+\cdots+\underbrace{(q_{m}\operatorname{\circ\,}f)}_{=:\;g_{m}}\cdot(L_{w_{m}}p\operatorname{\circ\,}f)=$
$\displaystyle=g_{1}\cdot\partial_{x}^{\\#({w_{1}})}g+\cdots+g_{m}\cdot\partial_{x}^{\\#({w_{m}})}g.$

We now extract the constant term on both sides. This is a homomorphic
operation $[x^{0}]\\_$, and thus we have

$\displaystyle[x^{0}](\partial_{x}^{\\#({w})}g)=[x^{0}]g_{1}\cdot[x^{0}](\partial_{x}^{\\#({w_{1}})}g)+\cdots+[x^{0}]g_{m}\cdot[x^{0}](\partial_{x}^{\\#({w_{m}})}g).$

By the commutation rule 8,

$\displaystyle[x^{\\#({w})}]g=[x^{0}]g_{1}\cdot[x^{\\#({w_{1}})}]g+\cdots+[x^{0}]g_{m}\cdot[x^{\\#({w_{m}})}]g.$

We have shown that the coefficient $[x^{{\\#({w})}}]g$ is a homogeneous linear
combination of the coefficients $[x^{n}]g$’s of total degree
$\left|n\right|_{1}\leq M$. Since $w$ was arbitrary, if all those coefficients
$[x^{n}]g$’s are zero, then $g$ is zero. We now invoke the upper bound on $M$
from Theorem 2.16.

See 1.3

######  Proof C.62.

Without loss of generality the problem reduces to checking zeroness of the
first component $g:=f^{(1)}$ of a tuple of CDF power series
$f\in\mathbb{Q}[\\![x]\\!]^{k}$. Moreover, we can assume that
$f\in\mathbb{Z}[\\![x]\\!]^{k}$ and that the corresponding CDF system of
equations 9 contains only integer polynomials $P_{ij}\in\mathbb{Z}[y]$. (Were
this not the case, a simple scaling by multiplying each $P_{ij}$ with a common
denominator of all rational constants of the system provides a new integral
system where the answer to the zeroness problem is the same.) By Lemma 3.8, it
suffices to check $[x^{n}]f^{(1)}=0$ for all monomials $x^{n}$ of degree
$\left|n\right|_{1}\leq N:=D^{k^{O\left(k^{2}\right)}}$. By Lemma 3.6 we can
compute a table containing all those integer coefficients in time

$\displaystyle(N+d\cdot D+k)^{O\left(d\cdot D+k\right)}\cdot(\log
H)^{O\left(1\right)}.$

By the definition of $N$, this gives a zeroness algorithm running in
deterministic time

$\displaystyle(D^{k^{O\left(k^{2}\right)}}+d\cdot D+k)^{O\left(d\cdot
D+k\right)}\cdot(\log H)^{O\left(1\right)}$ $\displaystyle\leq(d\cdot
D)^{d\cdot D\cdot k^{O\left(k^{2}\right)}}\cdot(\log H)^{O\left(1\right)},$

which amounts to a 2-EXPTIME zeroness algorithm.