# Zeroing the Output of a Nonlinear System Without Relative Degree

W. Steven Gray<EMAIL_ADDRESS>Kurusch Ebrahimi-Fard  kurusch.ebrahimi-
<EMAIL_ADDRESS>Alexander Schmeding<EMAIL_ADDRESS>Department of
Electrical and Computer Engineering, Old Dominion University, Norfolk,
Virginia 23529, USA  Department of Mathematical Sciences, Norwegian University
of Science and Technology (NTNU), 7491 Trondheim, Norway  FLU, Nord University
Høgskoleveien 27, 7601 Levanger, Norway

###### Abstract

The goal of this paper is to establish some facts concerning the problem of
zeroing the output of an input-output system that does not have relative
degree. The approach taken is to work with systems that have a Chen-Fliess
series representation. The main result is that a class of generating series
called primely nullable series provides the building blocks for solving this
problem using the shuffle algebra. It is shown that the shuffle algebra on the
set of generating polynomials is a unique factorization domain so that any
polynomial can be uniquely factored modulo a permutation into its irreducible
elements for the purpose of identifying nullable factors. This is achieved
using the fact that this shuffle algebra is isomorphic to the symmetric
algebra over the vector space spanned by Lyndon words. A specific algorithm
for factoring generating polynomials into its irreducible factors is presented
based on the Chen-Fox-Lyndon factorization of words.

###### keywords:

nonlinear control systems, Chen-Fliess series, shuffle algebra

##  1 Introduction

Consider a smooth control-affine state space realization

$\displaystyle\dot{z}$ $\displaystyle=g_{0}(z)+g_{1}(z)u,\;\;z(0)=z_{0}$ (1a)
$\displaystyle y$ $\displaystyle=h(z),$ (1b)

where $g_{0}$, $g_{1}$, and $h$ are defined on $W\subseteq{\mathbb{R}}^{n}$.
If the realization has a well defined relative degree at $z_{0}\in W$, then it
is a classical result that the corresponding input-output map $F:u\mapsto y$
is left invertible [20, 26]. If the zero output is known to be in the range of
$F$ for some class of inputs $\cal U$, then there exists a unique input
$u^{\ast}\in\cal U$ satisfying $F(u^{\ast})=0$ which can be generated in real-
time using feedback [20, 26] or computed analytically using formal power
series methods [12]. This construction leads to the notion of zero dynamics
[14, 20, 21, 26]. When the system fails to have relative degree, however,
there appears to be little known about the problem of zeroing the output. Take
as a simple example the system

$\displaystyle\dot{z}_{1}$
$\displaystyle=1-u,\;\;\dot{z}_{2}=z_{3}-u,\;\;\dot{z}_{3}=1,\;\;z(0)=0$ (2a)
$\displaystyle y$ $\displaystyle=z_{1}z_{2}.$ (2b)

It is easily verified that this realization does not have relative degree at
the origin. Nevertheless, there are two inputs which give the zero output:
$u^{\ast}(t)=1$, $t\geq 0$ and $u^{\ast}(t)=t$, $t\geq 0$. The general goal of
this paper is to establish some facts concerning how to zero the output of a
system that does not have relative degree at some point of interest.

The approach taken here will be to work purely in the input-output setting
using Chen-Fliess series representations. One advantage to this point of view
is that the nonuniqueness of coordinate systems can be avoided. That is, the
generating series for the input-output map of a state space realization is
invariant under coordinate transformation. In addition, this framework is more
general as every analytic state space realization (1) has an input-output map
with a Chen-Fliess series representation but not conversely. In order to avoid
convergence issues associated with such series, the analysis will be done
using formal Fliess operators [17], that is, maps that take an infinite jet
representing a formal input function to an infinite jet representing a formal
output function. In this context, the problem of zeroing the output boils down
to a purely algebraic problem.

The concept of a nullable generating series is presented first. This is a
formal power series representing a formal Fliess operator having the property
that the zero output (jet) is in the range of the operator. A generating
series is called strongly nullable if there is a nonzero input that maps to
the zero output and primely nullable if this input is the only input with this
property. There are in some sense the building blocks for constructing other
nullable polynomials. A special class of primely series are those having
relative degree and one additional property. These will be called linearly
nullable. While there is no known direct test for general nullability,
linearly nullable series can be completely characterized, and in this case,
the nulling input can be directly computed. It is shown that the shuffle
product of two linearly nullable series is always strongly nullable but not
linearly nullable. The shuffle product corresponds to the parallel product
interconnection of two systems [8].

The focus then turns to an inverse problem, namely, factoring a polynomial
into its irreducible elements in the shuffle algebra. It is first established
that the shuffle algebra as a commutative polynomial ring over a finite set of
noncommuting indeterminates is a unique factorization domain. This is achieved
by assembling existing results from algebra [4] and algebraic combinatorics
[24]. Of particular importance is the fact that this shuffle algebra can be
viewed as the symmetric algebra over the ${\mathbb{R}}$-vector space spanned
by Lyndon words [24, 28]. Such factorizations can be used to identify any
nullable factors. What is unknown at present is whether every nullable series
can be written uniquely as the shuffle product of primely nullable series.
Finally, an algorithm is given to factor a polynomial into its irreducible
shuffle components. This is done by first mapping the polynomial to the
symmetric algebra using the Chen-Fox-Lyndon factorization of words [3, 19, 24,
28, 30]. The resulting polynomial is then factored using one of the many known
algorithms for factoring multivariate commutative polynomials [32]. Then each
factor is mapped back to the shuffle algebra.

The paper is organized as follows. In the next section, a brief summary is
given of the mathematical tools used to establish the main results of the
paper. In Section 3, the concept of nullable generating series is presented.
The subsequent section addresses the problem of factoring generating series in
the shuffle algebra. The final section provides the main conclusions of the
paper. It should be stated that a shorter preliminary version of this paper
was presented as a conference paper [15].

##  2 Preliminaries

An alphabet $X=\\{x_{0},x_{1},$ $\ldots,x_{m}\\}$ is any nonempty and finite
set of symbols referred to as letters. A word $\eta=x_{i_{1}}\cdots x_{i_{k}}$
is a finite sequence of letters from $X$. The number of letters in a word
$\eta$, written as $\left|\eta\right|$, is called its length. The empty word,
$\emptyset$, is taken to have length zero. The collection of all words having
length $k$ is denoted by $X^{k}$. Define $X^{\ast}=\bigcup_{k\geq 0}X^{k}$,
which is a monoid under the concatenation product. Any mapping
$c:X^{\ast}\rightarrow{\mathbb{R}}^{\ell}$ is called a formal power series.
Often $c$ is written as the formal sum $c=\sum_{\eta\in
X^{\ast}}(c,\eta)\eta$, where the coefficient $(c,\eta)\in{\mathbb{R}}^{\ell}$
is the image of $\eta\in X^{\ast}$ under $c$. The support of $c$, ${\rm
supp}(c)$, is the set of all words having nonzero coefficients. A series $c$
is called proper if $\emptyset{\not\in}{\rm supp}(c)$. The order of $c$, ${\rm
ord}(c)$, is the length of the shortest word in its support. By definition the
order of the zero series is $+\infty$. The set of all noncommutative formal
power series over the alphabet $X$ is denoted by
${\mathbb{R}}^{\ell}\langle\langle X\rangle\rangle$. The subset of series with
finite support, i.e., polynomials, is represented by
${\mathbb{R}}^{\ell}\langle X\rangle$. Each set is an associative
${\mathbb{R}}$-algebra under the concatenation product and an associative and
commutative ${\mathbb{R}}$-algebra under the shuffle product, that is, the
bilinear product uniquely specified by the shuffle product of two words

$(x_{i}\eta){\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}(x_{j}\xi)=x_{i}(\eta{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}(x_{j}\xi))+x_{j}((x_{i}\eta){\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}\xi),$

where $x_{i},x_{j}\in X$, $\eta,\xi\in X^{\ast}$ and with
$\eta{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}\emptyset=\emptyset{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}\eta=\eta$ [8]. For
any letter $x_{i}\in X$, let $x_{i}^{-1}$ denote the ${\mathbb{R}}$-linear
left-shift operator defined by $x_{i}^{-1}(\eta)=\eta^{\prime}$ when
$\eta=x_{i}\eta^{\prime}$ and zero otherwise. Higher order shifts are defined
inductively via $(x_{i}\xi)^{-1}(\cdot)=\xi^{-1}x_{i}^{-1}(\cdot)$, where
$\xi\in X^{\ast}$. It acts as a derivation on the shuffle product.

###  2.1 Chen-Fliess series

Given any $c\in\mbox{${\mathbb{R}}^{\ell}\langle\langle X\rangle\rangle$}$ one
can associate a causal $m$-input, $\ell$-output operator, $F_{c}$, in the
following manner. Let $\mathfrak{p}\geq 1$ and $t_{0}<t_{1}$ be given. For a
Lebesgue measurable function $u:[t_{0},t_{1}]\rightarrow{\mathbb{R}}^{m}$,
define
$\left\|u\right\|_{\mathfrak{p}}=\max\\{\left\|u_{i}\right\|_{\mathfrak{p}}:\
1\leq i\leq m\\}$, where $\left\|u_{i}\right\|_{\mathfrak{p}}$ is the usual
$L_{\mathfrak{p}}$-norm for a measurable real-valued function, $u_{i}$,
defined on $[t_{0},t_{1}]$. Let $L^{m}_{\mathfrak{p}}[t_{0},t_{1}]$ denote the
set of all measurable functions defined on $[t_{0},t_{1}]$ having a finite
$\left\|\cdot\right\|_{\mathfrak{p}}$ norm and
$B_{\mathfrak{p}}^{m}(R)[t_{0},t_{1}]:=\\{u\in
L_{\mathfrak{p}}^{m}[t_{0},t_{1}]:\left\|u\right\|_{\mathfrak{p}}\leq R\\}$.
Assume $C[t_{0},t_{1}]$ is the subset of continuous functions in
$L_{1}^{m}[t_{0},t_{1}]$. Define inductively for each word
$\eta=x_{i}\bar{\eta}\in X^{\ast}$ the map
$E_{\eta}:L_{1}^{m}[t_{0},t_{1}]\rightarrow C[t_{0},t_{1}]$ by setting
$E_{\emptyset}[u]=1$ and letting

$E_{x_{i}\bar{\eta}}[u](t,t_{0})=\int_{t_{0}}^{t}u_{i}(\tau)E_{\bar{\eta}}[u](\tau,t_{0})\,d\tau,$

where $x_{i}\in X$, $\bar{\eta}\in X^{\ast}$, and $u_{0}=1$. The Chen-Fliess
series corresponding to $c\in\mbox{${\mathbb{R}}^{\ell}\langle\langle
X\rangle\rangle$}$ is

$y(t)=F_{c}[u](t)=\sum_{\eta\in X^{\ast}}(c,\eta)\,E_{\eta}[u](t,t_{0})$

[8]. If there exist real numbers $K_{c},M_{c}>0$ such that

$\left|(c,\eta)\right|\leq K_{c}M_{c}^{|\eta|}|\eta|!,\;\;\forall\eta\in
X^{\ast},$ (3)

then $F_{c}$ constitutes a well defined mapping from
$B_{\mathfrak{p}}^{m}(R)[t_{0},$ $t_{0}+T]$ into
$B_{\mathfrak{q}}^{\ell}(S)[t_{0},\,t_{0}+T]$ for sufficiently small $R,T>0$
and some $S>0$, where the numbers $\mathfrak{p},\mathfrak{q}\in[1,\infty]$ are
conjugate exponents, i.e., $1/\mathfrak{p}+1/\mathfrak{q}=1$ [16]. (Here,
$\left|z\right|:=\max_{i}\left|z_{i}\right|$ when $z\in{\mathbb{R}}^{\ell}$.)
Any series $c$ satisfying (3) is called locally convergent, and $F_{c}$ is
called a Fliess operator. The subset of all locally convergent series is
denoted by ${\mathbb{R}}^{\ell}_{LC}\langle\langle X\rangle\rangle$.

A Fliess operator $F_{c}$ defined on $B^{m}_{\mathfrak{p}}(R)[t_{0},t_{0}+T]$
with $\ell=1$ is said to be realizable when there exists a state space
realization (1) with each $g_{i}$ being an analytic vector field expressed in
local coordinates on some neighborhood ${W}$ of $z_{0}\in{\mathbb{R}}^{n}$,
and the real-valued output function $h$ is an analytic function on ${W}$ such
that (1a) has a well defined solution $z(t)$, $t\in[t_{0},t_{0}+T]$ for any
given input $u\in B^{m}_{\mathfrak{p}}(R)[t_{0},t_{0}+T]$, and
$y(t)=F_{c}[u](t)=h(z(t))$, $t\in[t_{0},t_{0}+T]$. Denoting the Lie derivative
of $h$ with respect to $g_{i}$ by $L_{g_{i}}h$, it can be shown that for any
word $\eta=x_{i_{k}}\cdots x_{i_{1}}\in X^{\ast}$

$(c,\eta)=L_{g_{\eta}}h(z_{0}):=L_{g_{i_{1}}}\cdots L_{g_{i_{k}}}h(z_{0})$ (4)

[8, 20, 26].

###  2.2 System interconnections

Given Fliess operators $F_{c}$ and $F_{d}$, where
$c,d\in\mbox{${\mathbb{R}}^{\ell}_{LC}\langle\langle X\rangle\rangle$}$, the
parallel and product connections satisfy $F_{c}+F_{d}=F_{c+d}$ and
$F_{c}F_{d}=F_{c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d}$, respectively
[8]. It is also known that the composition of two Fliess operators $F_{c}$ and
$F_{d}$ with $c\in\mbox{${\mathbb{R}}^{\ell}_{LC}\langle\langle
X\rangle\rangle$}$ and $d\in\mbox{${\mathbb{R}}^{m}_{LC}\langle\langle
X\rangle\rangle$}$ always yields another Fliess operator with generating
series $c\circ d$, where the composition product is given by

$c\circ d=\sum_{\eta\in X^{\ast}}(c,\eta)\,\psi_{d}(\eta)(\mathbf{1})$ (5)

[7]. Here $\psi_{d}$ is the continuous (in the ultrametric sense) algebra
homomorphism from ${\mathbb{R}}\langle\langle X\rangle\rangle$ to the vector
space endomorphisms on ${\mathbb{R}}\langle\langle X\rangle\rangle$, ${\rm
End}(\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$})$, uniquely specified
by $\psi_{d}(x_{i}\eta)=\psi_{d}(x_{i})\circ\psi_{d}(\eta)$ with
$\psi_{d}(x_{i})(e)=x_{0}(d_{i}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}e),$ $i=0,1,\ldots,m$
for any $e\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$, and where
$d_{i}$ is the $i$-th component series of $d$
($d_{0}:=\hbox{$1$}:=1\emptyset$). By definition, $\psi_{d}(\emptyset)$ is the
identity map on ${\mathbb{R}}\langle\langle X\rangle\rangle$. It can be
verified directly that

$x_{j}^{-1}(c\circ
d)=\left\\{\\!\\!\\!\begin{array}[]{ccl}\displaystyle{x_{0}^{-1}(c)\circ
d+\sum_{i=1}^{m}\\!d_{i}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}(x_{i}^{-1}(c)\circ
d)}\\!\\!\\!\\!\\!&:&\\!\\!\\!\\!\\!j=0\\\
0\\!\\!\\!\\!\\!&:&\\!\\!\\!\\!\\!j\neq 0.\end{array}\right.$ (6)

If $c,d\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ with $m=\ell=1$
and $d$ non-proper, then one can define the quotient
$c/d=c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}-1}$ so that
$F_{c}/F_{d}=F_{c/d}$ with the shuffle inverse of $d$ defined as

$d^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}-1}=((d,\emptyset)(1-d^{\prime}))^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}-1}=(d,\emptyset)^{-1}(d^{\prime})^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}\ast},$

where $d^{\prime}=\hbox{$1$}-(d/(d,\emptyset))$ is proper and
$(d^{\prime})^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}\ast}:=\sum_{k\geq
0}(d^{\prime})^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}k}$ [12]. The
following lemma will be useful.

###### Lemma 2.1

For any $c,d,e\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ with $d$
non-proper, the following identity holds

$(c/d)\circ e=(c\circ e)/(d\circ e).$

Proof: It can be shown directly from the definition of the composition product
that if $d$ is non-proper then so is $d\circ e$. In fact, $(d\circ
e,\emptyset)=(d,\emptyset)\neq 0$. Thus, both sides of the equality in
question are at least well defined formal power series. In light of the known
identity

$(c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d)\circ e=(c\circ
e){\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}(d\circ e)$ (7)

for any $c,d,e\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ [9], it
is sufficient to show that

$d^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}-1}\circ e=(d\circ
e)^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}-1}.$ (8)

It is clear via induction that for any $k\in{\mathbb{N}}$,

$d^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}k}\circ e=(d\circ
e)^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}k}.$

Therefore, since $d$ is non-proper, it follows that

$\displaystyle d^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}-1}\circ e$
$\displaystyle=(d,\emptyset)^{-1}\lim_{n\rightarrow\infty}\sum_{k=0}^{n}(d^{\prime})^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}k}\circ e$
$\displaystyle=(d\circ
e,\emptyset)^{-1}\lim_{n\rightarrow\infty}\sum_{k=0}^{n}(d^{\prime}\circ
e)^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}k}$
$\displaystyle=(d\circ
e)^{{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}-1}.$

As $d^{\prime}$ and $d^{\prime}\circ e$ are both proper, all the limits above
(in the ultrametric sense) exist, and thus, the claim is verified.

###  2.3 Formal Fliess operators

Suppose $X=\\{x_{0},x_{1}\\}$ and define $X_{0}=\\{x_{0}\\}$. Then every
series $c_{u}\in\mbox{${\mathbb{R}}[[X_{0}]]$}$ can be identified with an
infinite jet $j^{\infty}_{t_{0}}(u)$ for any fixed $t_{0}\in{\mathbb{R}}$. By
Borel’s Lemma, there is a real-valued function $u\in C^{\infty}(t_{0})$ whose
Taylor series corresponds to $j^{\infty}_{t_{0}}(u)$. In the event that the
coefficients of $c_{u}$ satisfy the growth bound (3), then $u$ is real-
analytic. In which case, for any $c\in\mbox{${\mathbb{R}}_{LC}\langle\langle
X\rangle\rangle$}$, $F_{c_{y}}[v]=y=F_{c}[u]=F_{c}[F_{c_{u}}[v]]=F_{c\circ
c_{u}}[v]$, where $v$ is just a placeholder in this chain of equalities. If
the Taylor series for $u$ does not converge, it is viewed as a formal
function. Nevertheless, the mapping
$c\,\circ:\mbox{${\mathbb{R}}[[X_{0}]]$}\rightarrow\mbox{${\mathbb{R}}[[X_{0}]]$}:c_{u}\mapsto
c_{y}=c\circ c_{u}$ is still well defined and takes the input infinite jet to
the output infinite jet. This is called a formal Fliess operator [17]. The
advantage of working with these formal objects is that their algebraic
properties can be characterized independently of their analytic nature. This
will be the approach taken below.

###  2.4 Relative degree of a generating series

Observe that $c\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ can
always be decomposed into its natural and forced components, that is,
$c=c_{N}+c_{F}$, where $c_{N}:=\sum_{k\geq 0}(c,x_{0}^{k})x_{0}^{k}$ and
$c_{F}:=c-c_{N}$.

###### Definition 2.1

[12] Given $c\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ with
$X=\\{x_{0},x_{1}\\}$, let $r\geq 1$ be the largest integer such that ${\rm
supp}(c_{F})\subseteq x_{0}^{r-1}X^{\ast}$. Then $c$ has relative degree $r$
if the linear word $x_{0}^{r-1}x_{1}\in{\rm supp}(c)$, otherwise it is not
well defined.

It is immediate that $c$ has relative degree $r$ if and only if there exists
some $e\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ with ${\rm
supp}(e)\subseteq X^{\ast}/\\{X_{0}^{\ast},x_{1}\\}$ such that

$c=c_{N}+c_{F}=c_{N}+Kx_{0}^{r-1}x_{1}+x_{0}^{r-1}e$ (9)

and $K\neq 0$. This notion of relative degree coincides with the usual
definition given in a state space setting [13].

##  3 Nullable Generating Series

It is assumed for the remainder of the paper that all systems are single-
input, single-output, i.e., $m=\ell=1$ so that $X=\\{x_{0},x_{1}\\}$ and all
series coefficients are real-valued. Consider the following classes of
generating series.

###### Definition 3.1

A series $c\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ is said to
be nullable if the zero series is in the range of the mapping
$c\,\circ:\mbox{${\mathbb{R}}[[X_{0}]]$}\rightarrow\mbox{${\mathbb{R}}[[X_{0}]]$},c_{u}\mapsto
c\circ c_{u}$. That is, there exists a nulling series
$c_{u^{\ast}}\in\mbox{${\mathbb{R}}[[X_{0}]]$}$ such that $c\circ
c_{u^{\ast}}=0$. The series is strongly nullable if it has a nonzero nulling
series. A strongly nullable series is primely nullable if its nulling series
is unique.

Observe that from (5) it follows that $(c\circ c_{u},\emptyset)=(c,\emptyset)$
for all $c_{u}\in\mbox{${\mathbb{R}}[[X_{0}]]$}$. Thus, if $c$ is nullable,
then necessarily $c$ must be proper. Also, every series $c=c_{F}$ satisfies
$c\circ 0=0$. Thus, it is nullable. If $c=c_{N}+c_{F}$ with $c_{N}\neq 0$,
then $c\circ 0=c_{N}$. Therefore, if $c$ is nullable, it must be strongly
nullable.

###### Example 3.1

Observe that $c=x_{0}^{2}-x_{1}x_{0}$ is primely nullable since
$c\circ\hbox{$1$}=x_{0}^{2}-x_{0}^{2}=0$, and $c_{u^{\ast}}=\hbox{$1$}$ is the
only series with this property.

###### Example 3.2

The polynomial $c=x_{0}+x_{0}x_{1}$ is not nullable since $c\circ
c_{u}=x_{0}+x_{0}^{2}c_{u}\neq 0$ for all
$c_{u}\in\mbox{${\mathbb{R}}[[X_{0}]]$}$.

A sufficient condition for a series to be primely nullable is given in the
following theorem.

###### Theorem 3.1

If $c\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ has relative
degree $r$, and ${\rm supp}(c_{N})\subseteq x_{0}^{r}X_{0}^{\ast}$ is
nonempty, then $c$ is primely nullable.

Proof: Since $c_{N}\neq 0$ by assumption, any nulling series must be nonzero.
The claim is that $c$ has a unique nonzero nulling series. Applying (6) to
$c_{y}=c\circ c_{u}$ with $m=1$ (let $d_{1}=d$) under the assumption that $c$
has relative degree $r$ gives

$\displaystyle c_{y}$ $\displaystyle=c\circ c_{u}$ $\displaystyle
x_{0}^{-1}(c_{y})$ $\displaystyle=x_{0}^{-1}(c)\circ c_{u}$
$\displaystyle\hskip 5.78172pt\vdots$ $\displaystyle x_{0}^{-r+1}(c_{y})$
$\displaystyle=x_{0}^{-r+1}(c)\circ c_{u}$ $\displaystyle x_{0}^{-r}(c_{y})$
$\displaystyle=x_{0}^{-r}(c)\circ
c_{u}+c_{u}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}((x_{0}^{r-1}x_{1})^{-1}(c)\circ
c_{u}).$

Since $(x_{0}^{r-1}x_{1})^{-1}(c)$ is non-proper (specifically,
$((x_{0}^{r-1}x_{1})^{-1}(c),\emptyset)=K\neq 0$ in (9)) it can be shown that
$(x_{0}^{r-1}x_{1})^{-1}(c)\circ c_{u}$ is also non-proper and thus has a
shuffle inverse. Setting $x_{0}^{-r}(c_{y})=0$ and dividing by
$(x_{0}^{r-1}x_{1})^{-1}(c)\circ c_{u}$ gives

$0=(x_{0}^{-r}(c)\circ c_{u})/((x_{0}^{r-1}x_{1})^{-1}(c)\circ c_{u})+c_{u}.$

Next, applying Lemma 2.1 yields

$0=(x_{0}^{-r}(c)/(x_{0}^{r-1}x_{1})^{-1}(c))\circ c_{u}+c_{u}.$

Define a generalized series $\delta$ with the defining property that
$F_{\delta}[u]=u$ for all admissible inputs $u$. Then it must have the unital
property $\delta\circ c=c\circ\delta=c$ on the semigroup
$(\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$},\circ)$. The previous
equation can be written as

$0=\underbrace{(\delta+(x_{0}^{-r}(c)/(x_{0}^{r-1}x_{1})^{-1}(c)))}_{:=d_{\delta}}\circ
c_{u}.$

It is known that the set of series $\delta+\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}$ forms a group under the induced composition product [11].
Therefore, one can solve for $c_{u}$ directly via left inversion to give
$c_{u}=d_{\delta}^{\circ-1}\circ 0.$ In which case, there exists a unique
$c_{u}$ that will zero out all the coefficients of $c_{y}$ with the exception
of the first $r$ coefficients. These initial coefficients are completely
determined by $c$ since

$\displaystyle(c_{y},x_{0}^{k})$
$\displaystyle=(x_{0}^{-k}(c_{y}),\emptyset)=(x_{0}^{-k}(c)\circ
c_{u},\emptyset)$
$\displaystyle=(x_{0}^{-k}(c),\emptyset)=(c,x_{0}^{k}),\;\;k=0,1,\ldots,r-1.$

By assumption ${\rm supp}(c_{N})\subseteq x_{0}^{r}X_{0}^{\ast}$. Hence, all
the coefficients above must be zero so that $c_{y}=0$ as desired.

It is worth noting that $(\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$},\circ,\delta)$ described above as well as
$(\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$},{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,},\hbox{$1$})$ both
include the monoids of characters over their respective graded connected
bialgebras of coordinate functions. Identity (7), which is central in this
work, can then be viewed in terms of the concept of two bialgebras in
cointeraction [10]. I n this respect, equation (8) is equivalent to stating
that the right action of the character monoid
$(\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$},\circ,\delta)$ on the
group of unital non-proper series
$(\hbox{$1$}+\mbox{${\mathbb{R}}_{np}\langle\langle
X\rangle\rangle$},{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,},\hbox{$1$})\subset(\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$},{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,},\hbox{$1$})$ is
compatible with the antipode of its Hopf algebra of coordinate functions.

Series satisfying the condition in Theorem 3.1 will be referred to as linearly
nullable since the linear word $x_{0}^{r-1}x_{1}$ in its support plays a key
role in computing the nulling series. In light of (9), every such series has
the form

$c=x_{0}^{r}e_{0}+Kx_{0}^{r-1}x_{1}+x_{0}^{r-1}e_{1},$

where $r\in{\mathbb{N}}$, $K\neq 0$,
$e_{0}\in\mbox{${\mathbb{R}}[[X_{0}]]$}/\\{0\\}$, and ${\rm
supp}(e_{1})\subseteq X^{\ast}/\\{X_{0}^{\ast},x_{1}\\}$. From the general
identity $(x_{0}^{k}c)\circ d=x_{0}^{k}(c\circ d)$ and the fact that the
composition product is left linear, it follows that

$\displaystyle c\circ c_{u^{\ast}}$
$\displaystyle=(x_{0}^{r}e_{0}+Kx_{0}^{r-1}x_{1}+x_{0}^{r-1}e_{1})\circ
c_{u^{\ast}}$ $\displaystyle=x_{0}^{r-1}((x_{0}e_{0}+Kx_{1}+e_{1})\circ
c_{u^{\ast}})$ $\displaystyle=0.$

That is, $c_{u^{\ast}}$ is a solution to

$(x_{0}e_{0}+Kx_{1}+e_{1})\circ
c_{u^{\ast}}=x_{0}(e_{0}+Kc_{u^{\ast}})+e_{1}\circ c_{u^{\ast}}=0.$

Central to the proof of Theorem 3.1 is the observation that mapping $c\circ$
under the condition that $c$ has relative degree is injective since it is left
invertible. The following corollary, which also follows directly from this
proof, states that $c\circ$ is never surjective on ${\mathbb{R}}[[X_{0}]]$
under this condition.

###### Corollary 3.1

Suppose $c$ has relative degree $r$. Define
$c_{N}^{r-1}=(c,\emptyset)+(c,x_{0})x_{0}+\cdots+(c,x_{0}^{r-1})x_{0}^{r-1}$.
Then the range of the mapping $c_{u}\mapsto c\circ c_{u}$ is the affine
subspace of the ${\mathbb{R}}$-vector space ${\mathbb{R}}[[X_{0}]]$

$R_{c}:=\\{c_{y}=c_{N}^{r-1}+x_{0}^{r}e:e\in\mbox{${\mathbb{R}}[[X_{0}]]$}\\}.$

Therefore, $c$ is nullable in this case only if $c^{r-1}_{N}=0$.

###### Example 3.3

The polynomial $c=x_{0}+x_{1}$ has relative degree 1 and $c_{N}=x_{0}\in
x_{0}X_{0}^{\ast}$. Therefore, it is linearly nullable. Specifically,
$c_{u^{\ast}}=-\hbox{$1$}$ is the only series that yields $c\circ
c_{u^{\ast}}=0$.

###### Example 3.4

The polynomial $c=x_{0}^{2}-x_{1}x_{0}$ in Example 3.1 does not have relative
degree. So it is primely nullable but not linearly nullable.

###### Example 3.5

The polynomial $c=x_{0}+x_{0}x_{1}$ in Example 3.2 has relative degree 2 and
was shown not to be nullable. Observe $c_{N}=x_{0}\not\in
x_{0}^{2}X_{0}^{\ast}$, which is consistent with Theorem 3.1.

###### Example 3.6

Consider the series $c=\sum_{\eta\in X^{+}}|\eta|!\,\eta$, where
$X^{+}:=X^{\ast}/\\{\emptyset\\}$. The series has relative degree 1 and is
linearly nullable. In this instance, the corresponding Chen-Fliess series has
the closed-form expression

$F_{c}[u]=\frac{F_{x_{0}+x_{1}}[u]}{1-F_{x_{0}+x_{1}}[u]}.$

Therefore, the unique nulling series for $c$ is $c_{u^{\ast}}=-\hbox{$1$}$.

Let $c\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ be nullable.
Define the (two-sided) principal ideal

$I_{c}=(c):=\\{c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d:d\in\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}\\}$

in the shuffle algebra on ${\mathbb{R}}\langle\langle X\rangle\rangle$.

###### Lemma 3.1

Every series in $I_{c}$ is nullable. If $c$ is strongly nullable, then every
series in $I_{c}$ is strongly nullable.

Proof: Applying (7) it follows that
$(c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d)\circ
c_{u^{\ast}}=(c\circ
c_{u^{\ast}}){\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}(d\circ
c_{u^{\ast}})=0$ if $c_{u^{\ast}}$ is selected so that $c\circ
c_{u^{\ast}}=0$, which is always possible since $c$ is nullable by assumption.
The second claim is now obvious.

The first theorem below is obvious given the definition of primely nullable.
The second theorem is less trivial.

###### Theorem 3.2

If $c,d\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ are primely
nullable with $c_{u^{\ast}}\neq d_{u^{\ast}}$, then
$c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d$ is strongly
nullable but not primely nullable.

###### Theorem 3.3

If $c,d\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ are linearly
nullable, then $c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d$ is strongly
nullable but not linearly nullable.

Proof: The strong nullability property follows directly from the lemma above.
Regarding the second assertion, if
$c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d$ is linearly
nullable, then necessarily
$c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d$ must have relative
degree, say $s$, and
$(c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d)_{N}\in
x_{0}^{s}X_{0}^{\ast}$. Observe that

$\displaystyle c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d$
$\displaystyle=(x_{0}^{r_{c}}e_{0}+K_{c}x_{0}^{r_{c}-1}x_{1}+x_{0}^{r_{c}-1}e_{1}){\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}$
$\displaystyle\hskip
14.45377pt(x_{0}^{r_{d}}f_{0}+K_{d}x_{0}^{r_{d}-1}x_{1}+x_{0}^{r_{d}-1}f_{1})$

has the property that
$(c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d)_{N}\in
x_{0}^{r_{c}+r_{d}}X_{0}^{\ast}$. But the assertion is that
$c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d$ cannot have
relative degree $r_{c}+r_{d}$. This would require that the shortest linear
word in ${\rm supp}(c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d)_{F}$ be
$x_{0}^{r_{c}+r_{d}-1}x_{1}$ and all other words in ${\rm
supp}((c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d)_{F})$ must have
the prefix $x_{0}^{r_{c}+r_{d}-1}$. This linear word will only be present if

$K_{c}(f_{0},\emptyset)+K_{d}(e_{0},\emptyset)\neq 0.$ (10)

This means that at least one of the constant terms $(e_{0},\emptyset)$ or
$(f_{0},\emptyset)$ must be nonzero. In addition, note that every word in the
support of

$\displaystyle(e_{0},\emptyset)x_{0}^{r_{c}}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}K_{d}x_{0}^{r_{d}-1}x_{1}+(f_{0},\emptyset)x_{0}^{r_{d}}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}K_{c}x_{0}^{r_{c}-1}x_{1}$
$\displaystyle=K_{d}(e_{0},\emptyset)(x_{0}^{r_{c}}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}x_{0}^{r_{d}-1}x_{1})+K_{c}(f_{0},\emptyset)(x_{0}^{r_{d}}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}x_{0}^{r_{c}-1}x_{1})$

has length $r_{c}+r_{d}$, and these words must have the required prefix
$x_{0}^{r_{c}+r_{d}-1}$ since no other words in the larger shuffle product are
short enough to cancel these words. But the only way to remove an illegal word
would violate (10). For example, if $r_{c}=r_{d}=1$, then

$\displaystyle(e_{0},\emptyset)x_{0}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}K_{d}x_{1}+(f_{0},\emptyset)x_{0}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}K_{c}x_{1}$
$\displaystyle=K_{d}(e_{0},\emptyset)(x_{0}x_{1}+x_{1}x_{0})+K_{c}(f_{0},\emptyset)(x_{0}x_{1}+x_{1}x_{0}).$

The illegal word $x_{1}x_{0}$ cannot be canceled without removing the required
linear word $x_{0}x_{1}$. Thus,
$c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d$ cannot be linearly
nullable.

###### Example 3.7

Suppose $c=x_{0}-x_{1}$ and $d=x_{0}^{2}-x_{1}$. Both series are linearly
nullable with relative degree 1. The nulling series for $c$ is
$c_{u^{\ast}}=\hbox{$1$}$, and the nulling series for $d$ is
$d_{u^{\ast}}=x_{0}$. Observe

$c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d=-x_{0}x_{1}-x_{1}x_{0}+2x_{1}^{2}+3x_{0}^{3}-x_{0}^{2}x_{1}-x_{0}x_{1}x_{0}-x_{1}x_{0}^{2}$

does not have relative degree. Therefore
$c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d$ is strongly
nullable, but not linearly nullable and not primely nullable. In fact, if the
coefficients for the realization (2) are computed from (4), one will find
directly that the generating series is the polynomial given above. This is the
origin of the example given in the introduction.

###### Example 3.8

Suppose $c=x_{0}+x_{1}$ and $d=\hbox{$1$}+x_{1}$. In this case, $c$ is
linearly nullable with relative degree 1, and $d$ also has relative degree 1
but is not nullable as it is not proper. Observe

$c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d=x_{0}+x_{1}+x_{0}x_{1}+x_{1}x_{0}+2x_{1}^{2}$

is also linearly nullable with relative degree 1. That is, Theorem 3.3 does
not preclude the possibility that primely nullable series can have shuffle
factors that are not nullable.

###### Example 3.9

Suppose $c=d=x_{0}-x_{1}$ so that both series are linearly nullable with
relative degree 1. As expected,

$c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d=2x_{0}^{2}-2x_{0}x_{1}-2x_{1}x_{0}-2x_{1}^{2}$

is not linearly nullable as it does not have relative degree, but it is
primely nullable since $c_{u^{\ast}}=d_{u^{\ast}}=\hbox{$1$}$ is the only
nulling series for $c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d$ as the shuffle
product is an integral domain. That is, in general
$(c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d)\circ
e_{u}=(c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}e_{u}){\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}(d\circ e_{u})=0$ if
and only if at least one argument in the second shuffle product is the zero
series.

In summary, if ${\mathbb{R}}_{p}\langle\langle X\rangle\rangle$ is the set of
all proper series in ${\mathbb{R}}\langle\langle X\rangle\rangle$, then the
following inclusions hold:

${\mathbb{R}}_{p}\langle\langle X\rangle\rangle$ $\supset$ nullable series
$\supset$ strongly nullable series $\supset$ primely nullable series $\supset$
linearly nullable series.

In light of Theorems 3.2 and 3.3, only the set of nullable series and strongly
nullable series are closed under the shuffle product.

The final example provides an application of nullable series.

###### Example 3.10

In optimal control problems, it is often necessary to determine critical
points of quadratic objective functions. From the calculus of variations, this
is accomplished by computing the critical points of a variational derivative.
For a system described only in terms of a Chen-Fliess series, this would
involve determining the critical points of a variational derivative of a Chen-
Fliess series. The Fréchet derivative of $F_{c}$, for example, can be computed
by introducing a variational alphabet associated with $X=\\{x_{0},x_{1}\\}$,
say $\delta X=\\{\delta x_{0},\delta x_{1}\\}$. Define the mapping
$\delta:X\rightarrow\delta X$ by $\delta(x_{0})=\delta x_{0}=0$ and
$\delta(x_{1})=\delta x_{1}$. Extend the definition of $\delta$ to $X^{\ast}$
by letting it act as a derivation with respect to concatenation. Further
extend the definition to ${\mathbb{R}}\langle\langle X\rangle\rangle$ by
linearity. In which case, the Fréchet derivative of $F_{c}$ at $u$ is the
linear functional $DF_{c}[u][h]=F_{\delta(c)}[u,h]$ [5]. Consider the simple
example where $c=x_{0}x_{1}+x_{1}x_{0}+x_{1}^{2}$ so that
$\delta(c)=(x_{0}+x_{1}){\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}\delta x_{1}$.
Identifying $u$ with $x_{1}$ and $h$ with $\delta x_{1}$ from some admissible
set of functions ${\cal U}$, it follows that

$DF_{c}[u][h]=F_{x_{0}+x_{1}}[u]E_{\delta x_{1}}[h],$

where $DF_{c}[u][\cdot]$ is clearly linear. Critical points in this context
are the inputs $u^{\ast}\in\cal U$ such that $DF_{c}[u^{\ast}][h]=0$ for all
$h\in\cal U$. Here it is evident since $x_{0}+x_{1}$ is linearly nullable that
$u^{\ast}(t)=-1$, $t\geq 0$.

##  4 Factorizations in the Shuffle Algebra

The shuffle product on ${\mathbb{R}}\langle X\rangle$ forms a commutative
ring. Such structures appear in the following chain of class inclusions:

commutative rings $\supset$ integral domains $\supset$ integrally closed
domains $\supset$ GCD domains $\supset$ unique factorization domains $\supset$
principal ideal domains $\supset$ Euclidean domains $\supset$ fields

[1, 23]. The integral domain property of the shuffle algebra was proved in
[29, Theorem 3.2]. The following theorem identifies the strongest structure
available on this ring.

###### Theorem 4.1

The shuffle algebra on ${\mathbb{R}}\langle X\rangle$ is a unique
factorization domain but not a principal ideal domain.

Proof: The claim that the shuffle algebra on ${\mathbb{R}}\langle X\rangle$ is
a unique factorization domain follows from existing results. It is known from
[28] (see also [18, Section 6] and [24, Chapter 5]) that the shuffle algebra
on ${\mathbb{R}}\langle X\rangle$ is isomorphic to the symmetric algebra on
the ${\mathbb{R}}$-vector space $V$ having basis $L=\\{l_{i}\\}_{i\geq 0}$,
the set of Lyndon words. The symmetric algebra $S(V)$ is in turn canonically
isomorphic to the free polynomial algebra ${\mathbb{R}}[L]$. Thus, there
exists an ${\mathbb{R}}$-linear map ${\mathscr{L}}:\mbox{${\mathbb{R}}\langle
X\rangle$}\rightarrow{\mathbb{R}}[L]$ such that

${\mathscr{L}}(\eta_{1}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}\eta_{2})={\mathscr{L}}(\eta_{1}){\mathscr{L}}(\eta_{2}),\;\;\forall\eta_{i}\in
X^{\ast}$ (11)

with ${\mathscr{L}}(\mathbf{1})=\mathbf{1}$, and, in particular,
${\mathscr{L}}(l_{i})=l_{i}$. Put another way, the shuffle algebra on
${\mathbb{R}}\langle X\rangle$ is freely generated by the set of all Lyndon
words [30, Theorem 6.1]. It is shown in [4, Section 4, Corollary 1] that any
such polynomial ring is a unique factorization domain (see also [2]).

To be a principal ideal domain, it is necessary that every ideal in
${\mathbb{R}}\langle X\rangle$ be generated by a single element. The classical
argument that this is not the case in the present context goes as follows
(e.g., see [25, p. 153]). The assertion is that the set of all proper
polynomials in ${\mathbb{R}}\langle X\rangle$, ${\mathbb{R}}_{p}\langle
X\rangle$, is an ideal which is not principal. It is clear that
${\mathbb{R}}_{p}\langle X\rangle$ is an ideal. Now suppose
${\mathbb{R}}_{p}\langle X\rangle$ has a single generator $p$ in the shuffle
algebra, i.e., $\mbox{${\mathbb{R}}_{p}\langle
X\rangle$}=(p):=\\{p{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}q:q\in\mbox{${\mathbb{R}}\langle
X\rangle$}\\}$. Since $x_{0},x_{1}\in\mbox{${\mathbb{R}}_{p}\langle
X\rangle$}$, there must exist $q_{0},q_{1}\in\mbox{${\mathbb{R}}\langle
X\rangle$}$ such that
$x_{0}=p{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}q_{0}$ and
$x_{1}=p{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}q_{1}$. In light of
the degrees of $x_{0}$ and $x_{1}$, this would require a generator of the form
$p=\alpha_{0}x_{0}+\alpha_{1}x_{1}$, $\alpha_{i}\in{\mathbb{R}}$. If
$\alpha_{0}=0$, then $p$ will generate $x_{1}$ but not $x_{0}$. Likewise, if
$\alpha_{1}=0$ then $p$ will generate $x_{0}$ but not $x_{1}$. Thus, the ideal
${\mathbb{R}}_{p}\langle X\rangle$ has two basis elements, that is,
$\mbox{${\mathbb{R}}_{p}\langle
X\rangle$}=(x_{0},x_{1}):=\\{x_{0}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}q_{0}+x_{1}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}q_{1}:q_{0},q_{1}\in\mbox{${\mathbb{R}}\langle
X\rangle$}\\}$, and thus is not principal.

The main theorem of this section is presented next.

###### Theorem 4.2

Let $c\in\mbox{${\mathbb{R}}\langle X\rangle$}$ with $c_{N}\neq 0$ and unique
factorization $c=c_{1}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}c_{2}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}\cdots{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}c_{n}$ (modulo a
permutation), where each $c_{i}$ is irreducible as a polynomial in the shuffle
algebra. Then $c_{u^{\ast}}\neq 0$ is a nulling series for $c$ if and only if
it is a nulling series for at least one of the factors $c_{i}$.

Proof: If $c_{u^{\ast}}\neq 0$ is a nulling series for $c_{i}$, then directly
from Lemma 3.1 it is a nulling series for $c$. Conversely, if

$c\circ c_{u^{\ast}}=(c_{1}\circ
c_{u^{\ast}}){\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}(c_{2}\circ
c_{u^{\ast}}){\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}\cdots{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}(c_{n}\circ
c_{u^{\ast}})=0$

for some $c_{u^{\ast}}\neq 0$, then since the shuffle algebra is an integral
domain, at least one series $c_{i}\circ c_{u^{\ast}}$ must be the zero series,
and the theorem is proved.

It is important to point out what the theorem above is not saying, namely,
that every nullable series can be factored into a shuffle product of primely
nullable series. While it is easy to demonstrate that a primely nullable
series need not be irreducible (Examples 3.8 and 4.3), it is unknown at
present whether a nullable and irreducible series is always primely nullable.
This is a much deeper problem.

Next, an algorithm is given to shuffle factorize any polynomial
$c\in\mbox{${\mathbb{R}}\langle X\rangle$}$ into its irreducible components.
This result follows from combining the proof of the previous theorem and
various known properties of Lyndon words. Suppose $X=\\{x_{0},x_{1}\\}$ is
ordered with $x_{0}<x_{1}$ so as to induce a corresponding lexicographical
ordering on $X^{+}$. Recall that a word $\eta\in X^{+}$ is called a Lyndon
word if all factorizations $\eta=\xi\nu$ with $\xi,\nu\in X^{+}$ have the
property that $\eta<\nu\xi$. In this case, the first few Lyndon words are
$L=\\{l_{i}\\}_{i\geq
0}=\\{x_{0},x_{1},x_{0}x_{1},x_{0}^{2}x_{1},x_{0}x_{1}^{2},x_{0}^{3}x_{1},x_{0}^{2}x_{1}^{2},x_{0}x_{1}^{3},\ldots\\}$,
where here the ordering is by increasing word length and then
lexicographically among words of the same length.111This ordering is only for
convenience in displaying results and does not play any mathematical role in
this presentation. The Chen-Fox-Lyndon factorization of a word $\eta\in X^{+}$
is a unique non-increasing product of Lyndon words so that

$\eta=l_{i_{1}}l_{i_{2}}\cdots l_{i_{n}},\;\;l_{i_{1}}\geq
l_{i_{2}}\geq\cdots\geq l_{i_{n}}$

[3, 19, 24, 30]. A consequence of this factorization is that

$l_{i_{1}}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}l_{i_{2}}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}\cdots{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}l_{i_{n}}=a\eta+R,$
(12)

where $a$ is a nonzero element in the set of rational numbers, $Q$, and all
the words in the remainder $R$ are lexicographically smaller than $\eta$ [19,
Theorem 5.6]. Applying (11) to both sides of (12) provides the recursive
formula

$\mathscr{L}(l_{i_{1}}l_{i_{2}}\cdots
l_{i_{n}})=\frac{1}{a}(l_{i_{1}}l_{i_{2}}\cdots l_{i_{n}}-\mathscr{L}(R)).$
(13)

The recursion will terminate when all the remainders are zero.

###### Example 4.1

Let $\eta_{1}=x_{0}x_{1}x_{0}$, $\eta_{2}=x_{0}^{2}x_{1}x_{0}$,
$\eta_{3}=x_{0}x_{1}x_{0}^{2}$. Their Chen-Fox-Lyndon factorizations are,
respectively, $\eta_{1}=(x_{0}x_{1})x_{0}=l_{2}l_{0}$,
$\eta_{2}=(x_{0}^{2}x_{1})(x_{0})=l_{3}l_{0}$, and
$\eta_{3}=(x_{0}x_{1})(x_{0})(x_{0})=l_{2}l_{0}^{2}$. Observe, for example,
that

$l_{2}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}l_{0}=x_{0}x_{1}x_{0}+2x_{0}^{2}x_{1}=\eta_{1}+R,$

where $R=2l_{3}$. Therefore, from (13)

$\mathscr{L}(\eta_{1})=l_{0}l_{2}-2l_{3}.$

Likewise,

$\displaystyle\mathscr{L}(\eta_{2})$ $\displaystyle=l_{0}l_{3}-3l_{5}$
$\displaystyle\mathscr{L}(\eta_{3})$
$\displaystyle=\frac{1}{2}l_{0}^{2}l_{2}-2l_{0}l_{3}+3l_{5}.$

To illustrate the isomorphism between the shuffle algebra on
${\mathbb{R}}\langle X\rangle$ and the free algebra $R[L]$, observe that

$\eta_{1}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}x_{0}=2\eta_{2}+2\eta_{3},$

so that as expected from (11)

$\displaystyle\mathscr{L}(\eta_{1}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}x_{0})$
$\displaystyle=2\mathscr{L}(\eta_{2})+2\mathscr{L}(\eta_{3})$
$\displaystyle=(l_{0}l_{2}-2l_{3})l_{0}$
$\displaystyle=\mathscr{L}(\eta_{1})\mathscr{L}(x_{0}).$

The proposed algorithm for shuffle factoring a proper polynomial $c$ is
summarized below:

  * 1.

Compute $c_{L}={\mathscr{L}}(c)$ using (12)-(13).

  * 2.

Factor $c_{L}$ using Mathematica’s Factor command [33].

  * 3.

Apply the map $\mathscr{L}^{-1}$ to each factor in $R[L]$ from the previous
step. In particular, ${\mathscr{L}}^{-1}(l_{i_{1}}l_{i_{2}}\cdots
l_{i_{k}})=l_{i_{1}}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}l_{i_{2}}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}\cdots{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}l_{i_{k}}$.

An efficient algorithm for the Chen-Fox-Lyndon factorizations in step 1 is
given in [6] (see also [31]). Mathematica’s implementation notes for Factor
provide a description of the specific algorithms used to factor multivariate
polynomials. For a more general treatment of the subject see [32].

###### Example 4.2

Consider the polynomial

$\displaystyle c$
$\displaystyle=2x_{0}^{2}-2x_{1}^{2}+\underline{2x_{0}^{2}x_{1}x_{0}+2x_{0}x_{1}x_{0}^{2}}-2x_{0}x_{1}^{2}x_{0}$
$\displaystyle\hskip
11.56346pt+2x_{1}x_{0}^{2}x_{1}+2x_{1}x_{0}x_{1}^{2}+2x_{1}^{2}x_{0}x_{1}+2x_{0}x_{1}x_{0}x_{1}x_{0}x_{1}$
$\displaystyle\hskip
11.56346pt+2x_{0}x_{1}x_{0}x_{1}^{2}x_{0}+4x_{0}x_{1}^{2}x_{0}^{2}x_{1}+2x_{0}x_{1}^{2}x_{0}x_{1}x_{0}$
$\displaystyle\hskip
11.56346pt+2x_{1}x_{0}^{2}x_{1}x_{0}x_{1}+4x_{1}x_{0}^{2}x_{1}^{2}x_{0}+2x_{1}x_{0}x_{1}x_{0}^{2}x_{1}$
$\displaystyle\hskip 11.56346pt+2x_{1}x_{0}x_{1}x_{0}x_{1}x_{0},$

which does not have relative degree since it has no linear words of the form
$x_{0}^{r-1}x_{1}$ in its support. The algorithm above is applied to $c$ with
the help of the Mathematica NCFPS package [27]. The underlined terms
correspond to Example 4.1 which is embedded in this example.

Step 1: Observe

$\displaystyle c_{L}$
$\displaystyle={\mathscr{L}(c)}=l_{0}^{2}-l_{1}^{2}+\underline{l_{0}^{2}l_{2}}+l_{1}^{2}l_{2}+l_{0}l_{1}l_{2}^{2}-\underline{2l_{0}l_{3}}$
$\displaystyle\hskip
10.84006pt+2l_{1}l_{3}-2l_{1}l_{2}l_{3}-2l_{0}l_{4}-2l_{1}l_{4}-2l_{0}l_{2}l_{4}+4l_{3}l_{4}.$

Step 2: Using the $\tt Factor$ command in Mathematica gives

$c_{L}=(l_{0}+l_{1}+\underline{l_{0}l_{2}-2l_{3}})(\underline{l_{0}}-l_{1}+l_{1}l_{2}-2l_{4}).$

Step 3: Mapping each factor of $c_{L}$ back to ${\mathbb{R}}_{p}\langle
X\rangle$ yields

$c=c_{1}{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}c_{2}=(x_{0}+x_{1}+\underline{x_{0}x_{1}x_{0}}){\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}(\underline{x_{0}}-x_{1}+x_{1}x_{0}x_{1}).$

Observe that the two factors of $c$ are distinct and linearly nullable with
relative degree $r=1$. Hence, there exist two distinct nulling inputs
$c_{u^{\ast}_{1}}$ and $c_{u^{\ast}_{2}}$ for this polynomial. Each input can
be computed via the algorithm in [12] or by solving an initial value problem
which follows from setting $F_{c_{i}}[u]=0$ and then repeatedly
differentiating with respect to time. For $c_{1}$ the latter approach yields

$u\ddot{u}-2\dot{u}^{2}-u^{4}=0,\;\;u(0)=-1,\;\;\dot{u}(0)=0$

so that

$c_{u^{\ast}_{1}}=\hbox{$1$}+x_{0}^{2}+7x_{0}^{4}+127x_{0}^{6}+4369x_{0}^{8}+\cdots.$

Similarly, for $c_{2}$ the corresponding initial value problem is

$\dot{u}+tu=0,\;\;u(0)=-1,$

which gives

$c_{u^{\ast}_{2}}=-\hbox{$1$}+x_{0}^{2}-3x_{0}^{4}+15x_{0}^{6}-105x_{0}^{8}+\cdots.$

To empirically verify that $c\circ c_{u^{\ast}_{i}}=0$, it is necessary to
truncate $c_{u^{\ast}_{i}}$. This means that $c\circ c_{u^{\ast}_{i}}$ will
not be exactly zero, but instead zero up to some word length depending on the
number of terms retained in $c_{u^{\ast}_{i}}$. For example, truncating both
$c_{u^{\ast}_{i}}$ to words of maximum length six gives

$\displaystyle c\circ c_{u^{\ast}_{1}}$
$\displaystyle=87380x_{0}^{10}+2946560x_{0}^{12}+153856528x_{0}^{14}+O(x_{0}^{16})$
$\displaystyle c\circ c_{u^{\ast}_{2}}$
$\displaystyle=2100x_{0}^{10}-840840x_{0}^{14}+57657600x_{0}^{16}-O(x_{0}^{18}).$

###### Example 4.3

Reconsider Example 3.8 where $c_{L}=l_{0}+l_{1}$ and $d_{L}=\hbox{$1$}+l_{1}$.
As observed earlier, $c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d$ is primely
nullable but not linearly nullable. Clearly
$(c{\,{\mathchoice{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip 3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
3.5pt\vrule height=5.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
3.5pt\vrule
height=5.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule
height=3.0pt,width=0.0pt\vrule}\hrule}}}}{\mathbin{\hbox{\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt}\hrule}\vbox{\hbox{\vrule\hskip
2.6pt\vrule height=3.0pt,width=0.0pt\vrule}\hrule}}}}}\,}d)_{L}=c_{L}d_{L}$ is
reducible with one linearly nullable factor $c_{L}$.

###### Example 4.4

Recall that for polynomials in one variable, the class of irreducible
polynomials depends on the base field. For example, over the real field, the
irreducible polynomials are either of degree $1$ or degree $2$ (e.g.,
$x_{0}^{2}+1$). Over the complex field, there are only degree $1$ irreducibles
[22, Chapter IV.1]. However, in every multivariate polynomial ring there are
irreducible elements of higher degree. Consider the polynomial
$c=6x_{1}^{3}-2x_{1}x_{0}^{2}-2x_{0}x_{1}x_{0}-2x_{0}^{2}x_{1}-24x_{0}^{4}\in\mbox{${\mathbb{R}}_{p}\langle
X\rangle$}$. It does not have relative degree, and thus, it is not linearly
nullable. There is at present no direct test for any other form of
nullability. In the Lyndon basis, it follows that
$c_{L}=l_{1}^{3}-l_{0}^{2}l_{1}-l_{0}^{4}\in{\mathbb{R}}[L]$. Now if $c_{L}$
is reducible, one could write

$c_{L}=(l_{1}-p_{1}(l_{0}))(l_{1}^{2}+p_{2}(l_{0})l_{1}+p_{3}(l_{0}))$ (14)

for some polynomials $p_{i}(l_{0})$. Since
$l_{0}^{4}=p_{1}(l_{0})p_{3}(l_{0})$, necessarily $p_{1}(l_{0})=al_{0}^{n}$
and $p_{3}(l_{0})=bl_{0}^{4-n}$ for some $n\in\\{0,1,2,3,4\\}$ and
$a,b\in{\mathbb{R}}$ with $ab=1$. Substituting these forms into (14) shows
directly that there are no values of $n$ that can yield $c_{L}$. Thus, $c_{L}$
is an irreducible multivariate polynomial of degree $4$ as an element in
${\mathbb{R}}[L]$.

##  5 Conclusions

Working entirely in a Chen-Fliess series setting, it was shown that a class of
generating series called primely nullable series provides building blocks in
the shuffle algebra for the problem of zeroing the output. Next, it was shown
that the shuffle algebra on ${\mathbb{R}}\langle X\rangle$ is a unique
factorization domain so that any polynomial can be uniquely factored into its
irreducible elements for the purpose of identifying nullable factors. This
factorization is done by viewing this shuffle algebra as the symmetric algebra
over the vector space spanned by Lyndon words. A specific polynomial
factorization algorithm was given based on the Chen-Fox-Lyndon factorization
of words.

## Acknowledgments

KEF and AS were supported by the Research Council of Norway through project
302831 Computational Dynamics and Stochastics on Manifolds (CODYSMA).

## References

  * [1] M. Artin, Algebra, 2nd Ed., Prentice Hall, Boston, MA, 2011.
  * [2] J. Berstel and L. Boasson, Shuffle factorization is unique, Theoret. Comput. Sci., 273 (2002) 47–67.
  * [3] K.-T. Chen, R. H. Fox, and R. C. Lyndon, Free differential calculus, IV, Ann. Math., 68 (1958) 81–95.
  * [4] P. M. Cohn, Unique factorization domains, Amer. Math. Monthly, 80 (1973) 1–18.
  * [5] L. A. Duffaut Espinosa, W. S. Gray, and I. Perez Avellaneda, Derivatives of Chen-Fliess series with applications to optimal control, Proc. 62nd IEEE Conf. on Decision and Control, Singapore, under review.
  * [6] J.-P. Duval, Factorizing words over an ordered alphabet, J. of Algorithms, 4 (1983) 363–381.
  * [7] A. Ferfera, Combinatoire du monoïde libre et composition de certains systèmes non linéaires, Astérisque, 75-76 (1980) 87–93.
  * [8] M. Fliess, Fonctionnelles causales non linéaires et indéterminées non commutatives, Bull. Soc. Math. France, 109 (1981) 3–40.
  * [9] L. Foissy, The Hopf algebra of Fliess operators and its dual pre-Lie algebra, Comm. Algebra, 43 (2015) 4528–4552.
  * [10] L. Foissy, Bialgebras in cointeraction, the antipode and the eulerian idempotent, arXiv:2201.11974, 2022.
  * [11] W. S. Gray, L. A. Duffaut Espinosa, and K. Ebrahimi-Fard, Faá di Bruno Hopf algebra of the output feedback group for multivariable Fliess operators, Systems Control Lett., 74 (2014) 64–73.
  * [12] W. S. Gray, L. A. Duffaut Espinosa, and M. Thitsa, Left inversion of analytic nonlinear SISO systems via formal power series methods, Automatica, 50 (2014) 2381–2388.
  * [13] W. S. Gray and K. Ebrahimi-Fard, SISO output affine feedback transformation group and its Faà di Bruno Hopf algebra, SIAM J. Control Optim., 55 (2017) 885–912.
  * [14] W. S. Gray, K. Ebrahimi-Fard, and A. Schmeding, Universal zero dynamics: SISO case, Proc. 55th Conf. on Information Sciences and Systems, Baltimore, MD, 2021, 6 pages.
  * [15] W. S. Gray, K. Ebrahimi-Fard, and A. Schmeding, Zeroing the output of nonlinear systems without relative degree, Proc. 57th Conf. on Information Sciences and Systems, Baltimore, MD, 2021, 6 pages.
  * [16] W. S. Gray and Y. Wang, Fliess operators on $L_{p}$ spaces: Convergence and continuity, Systems Control Lett., 46 (2002) 67–74.
  * [17] W. S. Gray and Y. Wang, Formal Fliess operators with applications to feedback interconnections, Proc. 18th Inter. Symp. on the Mathematical Theory of Networks and Systems, Blacksburg, VA, 2008, 12 pages.
  * [18] D. Grinberg and V. Reiner, Hopf algebras in combinatorics, arXiv:1409.8356, 2020.
  * [19] M. Hazewinkel, The algebra of quasi-symmetric functions is free over the integers, Adv. Math., 164 (2001) 283–300.
  * [20] A. Isidori, Nonlinear Control Systems, 3rd Ed., Springer, London, 1995.
  * [21] A. Isidori, The zero dynamics of a nonlinear system: From the origin to the latest progresses of a long successful story, European J. Control, 19 (2013) 369–378.
  * [22] S. Lang, Algebra, 3rd Ed., Springer, New York, 2002.
  * [23] H. Lombardi and C. Quitté, Commutative Algebra: Constructive Methods, Springer, Dordrecht, 2015.
  * [24] M. Lothaire, Combinatorics on Words, Cambridge Univesity Press, Cambridge, United Kingdom, 1983.
  * [25] S. MacLane and G. Birkhoff, Algebra, Macmillan Co., New York, 1967.
  * [26] H. Nijmeijer and A. J. van der Schaft, Nonlinear Dynamical Control Systems, Springer, New York, 1990.
  * [27] NonCommutative Formal Power Series (NCFPS), Mathematica package available at: https://github.com/LBerlin/NCFPS-MMA, 2023.
  * [28] D. E. Radford, A natural ring basis for the shuffle algebra and an application to group schemes, J. Algebra, 58 (1979) 432–454.
  * [29] R. Ree, Lie elements and an algebra associated with shuffles, Ann. of Math. (2), 68 (1958) 210–220.
  * [30] C. Reutenauer, Free Lie Algebras, Oxford University Press, New York, 1993.
  * [31] A. C. J. Scholtens, On the graded dual of the non-commutative universal Leibniz Hopf algebra $\cal Z$, Faculty of Mathematics and Computer Science, series no. 419, Free University, Amsterdam, 1994.
  * [32] J. von zur Gathen, Irreducibility of multivariate polynomials, J. Comput. System Sci., 31 (1985) 225–264.
  * [33] Wolfram Research, Factor, Wolfram Language function, https: //reference.wolfram.com/language/ref/Factor.html, 2007.