Entropy of Generating Series for Nonlinear Input-Output Systems

Entropy of Generating Series for Nonlinear
Input-Output Systems and Their Interconnections††This paper is a contribution
to the Special Issue on Non-Commutative Algebra, Probability and Analysis in
Action. The full collection is available at
https://www.emis.de/journals/SIGMA/non-commutative-probability.html

W. Steven GRAY

W.S. Gray

Department of Electrical and Computer Engineering, Old Dominion University,
Norfolk, Virginia 23529, USA<EMAIL_ADDRESS>http://www.ece.odu.edu/~sgray/

Received February 22, 2022, in final form October 07, 2022; Published online
October 25, 2022

This paper has two main objectives. The first is to introduce a notion of
entropy that is well suited for the analysis of nonlinear input-output systems
that have a Chen–Fliess series representation. The latter is defined in terms
of its generating series over a noncommutative alphabet. The idea is to assign
an entropy to a generating series as an element of a graded vector space. The
second objective is to describe the entropy of generating series originating
from interconnected systems of Chen–Fliess series that arise in the context of
control theory. It is shown that one set of interconnections can never
increase entropy as defined here, while a second set has the potential to do
so. The paper concludes with a brief introduction to an entropy ultrametric
space and some open questions.

Chen–Fliess series; formal power series; entropy; nonlinear control theory

68R15; 94A17; 93C10; 16T30

##  1 Introduction

The concept of entropy in the context of dynamical systems has been defined in
a variety of ways [7, 56]. Each notion is viewed as a measurement of the rate
of increase in dynamical complexity as the system evolves over time. The idea
has been adapted and applied in control theory starting with the work of Zames
in the 1970s [57] in order to address engineering problems like controlled
invariance, estimation, model detection, and stabilization in a finite
precision environment due to sampling, quantization, finite bit rates, etc.
(see [36] for a more complete overview). More recently, the concept of entropy
has been employed in the analysis of networked control systems [32, 39, 45,
51]. The general goal there is to quantify the entropy of a network in terms
of the entropies of its subsystems in order to establish some fundamental
performance bounds given limited communication between the subsystems. In
[36], for example, an explicit bound on the topological entropy of a network
of autonomous, continuous-time, nonlinear state space systems is derived in
terms of similar upper bounds on its subsystems. The main result is then
applied to cascaded systems to produce an upper bound on the entropy of the
composite system.

This paper has two main objectives. The first is to introduce a notion of
entropy that is well suited for the analysis of input-output systems that have
a Chen–Fliess series representation [16, 17]. The latter is defined in terms
of its generating series, i.e., a noncommutative formal power series over a
finite alphabet. The idea is to assign an entropy to a formal power series as
an element of a graded vector space which measures how quickly in an
asymptotic sense the homogeneous components of the grading are being occupied
by the support of the series. The asymptotic behavior of the Hilbert–Poincaré
series for the vector space provides a direct basis for comparison [1, 2].
This idea is closely related to the concept of entropy appearing in formal
language theory using what is called a generating structure function [33, 34].
There the grading is always based on word length, and the two notions of
entropy coincide if the formal power series is taken to be the characteristic
series of the language. As the authors of these works explain, their
definition is in turn related to the classical information theoretic notion of
entropy introduced by Shannon in terms of channel capacity [47]. Other
distinct definitions for the entropy of a language exist. For example, the
concept introduced in [46] measures the complexity of a language in terms of
the exponential growth rate in the number of equivalence classes of the Nerode
congruence relation of the language as the word length increases. In this
setting, all rational languages and Dyck languages have zero entropy, which is
not the case here or in earlier work. The entropy of a formal power series as
defined here is also related in spirit to the concept of entropy appearing in
symbolic dynamics [37], namely, the entropy defined for a semigroup under
concatenation corresponding to the language of forbidden words in a shift
space. It is, however, distinct from this established definition in that there
is no underlying set of recurrence inequalities to provide additional
structure (see, for example, [37, Lemma 4.1.7]). The proposed entropy concept
also coincides in certain special cases (modulo a logarithm) with the notion
of entropy defined for graded algebras [40, 41]. But that connection does not
appear to be so important for the present work. Finally, it should be stated
that the entropy of a generating series can be used to develop notions of
entropy for its corresponding input-output map. One such example is system
identification entropy as defined in [20]. This quantity describes the growth
in the number of bits needed to specify the series coefficients in order to
approximate the input-output map as the desired accuracy increases.

The second objective of the paper is to describe the entropy of generating
series originating from interconnected systems of Chen–Fliess series found in
the context of control theory. Such interconnections have been studied
extensively by the author and others [12, 13, 16, 18, 21, 22, 23, 24, 25, 26,
27, 29, 50, 52, 53, 55]. It is known that in every case the composite system
always has a Chen–Fliess series representation whose generating series can be
computed in terms of an induced formal power series product applied to the
generating series of the component systems. The main products of interest are
addition, the shuffle product, the composition product and the feedback
product. The Cauchy product and Hadamard product play a supporting role in
this setting. The main question to be addressed here is which system
interconnections/formal power series products are capable of increasing
entropy and which ones are not. It will turn out that all linear systems have
generating series with zero entropy, so any interconnection that preserves
linearity will not increase entropy. Somewhat surprising, even
interconnections like the parallel product of two linear systems, which do not
preserve linearity, will still result in a new system having zero entropy.
Thus, this new concept of entropy is nontrivial only for nonlinear systems.
Finally, this work in many ways is the complement of previous work by the
author and others regarding the convergence of Chen–Fliess series and their
interconnections [25, 26, 28, 50, 52, 53, 54, 55]. The main focus there was on
the growth rate of the coefficients of a generating series and the specific
types of convergence that are guaranteed for the corresponding Chen–Fliess
series. In this paper, the nature of the coefficients is almost entirely
irrelevant aside from being either zero or nonzero, i.e., being in the support
of the generating series or not. Nevertheless, as shown in [20], the entropy
of a generating series can be used to refine the notion of radius of
convergence of a Chen–Fliess series as defined in [50].

The paper concludes with a brief introduction to an entropy ultrametric space.
Such constructions have appeared in other contexts, for example, [4]. As
feedback systems are often analyzed in an ultrametric space setting [12, 21,
25, 29], this framework could have immediate applications in control theory.
Some current open problems are posed in this setting.

The paper is organized as follows. In the next section, a few preliminaries
regarding formal power series, Chen–Fliess series, and system interconnections
are summarized. In Section 3, the definition of entropy of a generating series
is given along with a number of illustrative examples. The entropy of
interconnected systems is characterized in Section 4. The entropy ultrametric
is introduced in the subsequent section. The conclusions of the paper are
summarized in the final section.

##  2 Preliminaries

An alphabet $X=\\{x_{0},x_{1},\dots,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,
$\varnothing$, is taken to have length zero. For a given $x_{i}\in X$,
$|\eta|_{x_{i}}$ is the number of times $x_{i}$ appears in $\eta$. The
collection of all words having length $k$ is denoted by $X^{k}$. Define
$X^{+}=\bigcup_{k\geq 1}X^{k}$ and $X^{\ast}=\bigcup_{k\geq 0}X^{k}$, the
latter of which is a noncommutative monoid under concatenation. Any mapping
$c\colon X^{\ast}\rightarrow{\mathbb{R}}^{\ell}$ is called a formal power
series. It is often 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. 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$. As ${\mathbb{R}}\langle X\rangle$ is
dense in ${\mathbb{R}}\langle\langle X\rangle\rangle$ (under the ultrametric
topology [3]), ${\mathbb{R}}^{\ell}\langle\langle X\rangle\rangle$ can be
viewed as the completion of ${\mathbb{R}}^{\ell}\langle X\rangle$. Given any
language $L\subseteq X^{\ast}$, its characteristic series in
${\mathbb{R}}\langle\langle X\rangle\rangle$ is ${\rm char}(L)=\sum_{\eta\in
L}\eta$.

###  2.1 Entropy of graded vector spaces

Let ${\mathbb{N}}=\\{1,2,\dots\\}$ and
${\mathbb{N}}_{0}={\mathbb{N}}\cup\\{0\\}$. An ${\mathbb{R}}$-vector space $V$
is said to be ${\mathbb{N}}_{0}$-graded over ${\mathbb{R}}$ if
$V=\bigoplus_{n\in{\mathbb{N}}_{0}}V_{n}$, where each $V_{n}$ is an
${\mathbb{R}}$-vector subspace. Elements in $V_{n}$ are said to have degree
$n$. $V$ is connected if $V_{0}={\mathbb{R}}$ and locally finite if each
$V_{n}$ has finite dimension. The Hilbert–Poincaré series of a graded locally
finite vector space is defined to be the formal power series in indeterminate
$z$ [1, 2]

$V(z)=\sum_{n=0}^{\infty}{\rm dim}(V_{n})z^{n}.$

Often $V(z)$ is a rational function indicating some type of linear recursion
relates the sequence of dimensions $d_{n}:={\rm dim}(V_{n})$, $n\geq 0$. The
entropy of a graded vector space $V$ is taken to be

$H(V)=\limsup_{n\rightarrow\infty}\sqrt[n]{{\rm dim}(V_{n})},$

whenever the limit exists [41].

######  Example 2.1.

Consider ${\mathbb{R}}\langle\langle X\rangle\rangle$ with scalar
multiplication and addition defined in the usual way to form an
${\mathbb{R}}$-vector space. If ${\mathbb{R}}\langle\langle X\rangle\rangle$
is graded by word length, then it is connected and locally finite with
$V_{n}={\rm span}_{\mathbb{R}}\\{\eta\in X^{\ast}\colon|\eta|=n\\}$ and
$d_{n}={\rm dim}(V_{n})=(m+1)^{n}$ so that

$V(z)=\sum_{n=0}^{\infty}(m+1)^{n}z^{n}=\frac{1}{1-(m+1)z}.$

As the sequence of dimensions is a geometric sequence, clearly,
$d_{n+1}=(m+1)d_{n}$, $n\geq 0$ with $d_{0}=1$. The entropy is
$H(\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$})=m+1$.

Consider next an alternative grading of ${\mathbb{R}}\langle\langle
X\rangle\rangle$, where the letter $x_{0}$ has twice the degree of the other
letters and $\deg(\varnothing)=1$, that is,
$\deg(\eta)=2|\eta|_{x_{0}}+\sum_{i=1}^{m}|\eta|_{x_{i}}+1$ for all $\eta\in
X^{\ast}$ [18, 21]. Let $|A|$ denote the cardinality of set $A$. Define the
formal power series in commuting indeterminates $z_{0},z_{1},\dots z_{m}$

$\displaystyle W(z_{0},z_{1},\dots,z_{m})$
$\displaystyle=\sum_{k_{0},k_{1},\dots,k_{m}=0}^{\infty}|\\{\eta\in
X^{\ast}\colon|\eta|_{x_{j}}=k_{j},j=0,1,\dots,m\\}|z_{0}^{k_{0}}z_{1}^{k_{1}}\cdots
z_{m}^{k_{m}}$ $\displaystyle=\frac{1}{1-(z_{0}+z_{1}+\cdots+z_{m})}.$

In light of the assumed grading, it follows that

$\displaystyle
V(z)=1+mzW\big{(}z^{2},z,\dots,z\big{)}=\frac{1-z^{2}}{1-mz-z^{2}}$
$\displaystyle\hphantom{V(z)}{}=1+mz+m^{2}z^{2}+\big{(}m+m^{3}\big{)}z^{3}+\big{(}2m^{2}+m^{4}\big{)}z^{4}+\big{(}m+3m^{3}+m^{5}\big{)}z^{5}$
$\displaystyle\hphantom{V(z)=}{}+\big{(}3m^{2}+4m^{4}+m^{6}\big{)}z^{6}+\big{(}m+6m^{3}+5m^{5}+m^{7}\big{)}z^{7}+O\big{(}z^{8}\big{)}.$

In which case, $d_{0}=1$, $d_{1}=m$, $d_{2}=m^{2}$,

$d_{n+1}=md_{n}+d_{n-1},\qquad n\geq 2$

and

$d_{n}\sim\frac{m}{\sqrt{m^{2}+4}}\left(\frac{m+\sqrt{m^{2}+4}}{2}\right)^{n},\qquad
n\gg 1.$

If $m=1$, then $d_{n}$, $n\geq 1$ is the Fibonacci sequence, and
$d_{n}\sim\varphi^{n}/\sqrt{5}$ with $\varphi=\big{(}1+\sqrt{5}\big{)}/2$
being the golden ratio. The integer sequences for $m=2$ and $m=3$ are also
well studied (see A052542 and A052906, respectively, in [48]). Under this
alternative grading, the entropy is $H(\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$})=\big{(}m+\sqrt{m^{2}+4}\big{)}/2<m+1$.

###  2.2 Elementary products of formal power series

Suppose multiplication on ${\mathbb{R}}^{\ell}$ is defined componentwise. Then
there are three elementary products on ${\mathbb{R}}^{\ell}\langle\langle
X\rangle\rangle$ that render it an associative unital ${\mathbb{R}}$-algebra
[14, 16]. The first is the commutative Hadamard product defined as

$c\odot d=\sum_{\eta\in X^{\ast}}(c,\eta)(d,\eta)\eta.$

The second is the noncommutative Cauchy product

$cd=\sum_{\eta,\xi\in X^{\ast}}(c,\eta)(d,\xi)\,\eta\xi.$

Lastly, ${\mathbb{R}}^{\ell}\langle\langle X\rangle\rangle$ is a commutative
${\mathbb{R}}$-algebra under the bilinear shuffle product

$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=\sum_{\eta,\xi\in
X^{\ast}}(c,\eta)(d,\xi)\,\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 the shuffle product of two words $x_{i}\eta,x_{j}\xi\in X^{\ast}$ is
defined inductively by

$(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)$

with $x_{i},x_{j}\in X$ and
$\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}}}}}\,}\varnothing=\varnothing{\,{\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$. Each
product is locally finite. In addition,

$\displaystyle{\rm supp}(c+d)\subseteq{\rm supp}(c)\cup{\rm supp}(d),$
$\displaystyle{\rm supp}(c\odot d)={\rm supp}(c)\cap{\rm supp}(d),$
$\displaystyle{\rm supp}(cd)\subseteq{\rm supp}(c){\rm supp}(d).$

The relationship between the support of the shuffle product and that of its
arguments is much more complicated, see, for example, [38]. Enumerating the
number of distinct words from shuffle products was investigated in [49]. But
asymptotic results along these lines, which would be very useful here, appear
to be unknown at present.

###  2.3 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\colon[t_{0},t_{1}]\rightarrow{\mathbb{R}}^{m}$, define
$\left\|u\right\|_{\mathfrak{p}}=\max\\{\left\|u_{i}\right\|_{\mathfrak{p}}\colon
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}]\colon\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}\colon
L_{1}^{m}[t_{0},t_{1}]\rightarrow C[t_{0},t_{1}]$ by setting
$E_{\varnothing}[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})\,{\rm
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 [16]

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

To establish the convergence of this series, assume there exist real numbers
$K,M>0$ such that

$\displaystyle\left|(c,\eta)\right|\leq
KM^{|\eta|}|\eta|!,\qquad\forall\eta\in X^{\ast}.$ (2.2)

(Define $\left|z\right|:=\max_{i}\left|z_{i}\right|$ whenever
$z\in{\mathbb{R}}^{\ell}$.) It is shown in [28] that under such circumstances
the series (2.1) converges uniformly and absolutely so that $F_{c}$ describes
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$,
where $\mathfrak{p},\mathfrak{q}\in[1,\infty]$ satisfy
$1/\mathfrak{p}+1/\mathfrak{q}=1$. The operator $F_{c}$ is said to be locally
convergent and is called a Fliess operator. The collection of all generating
series $c$ satisfying the growth condition (2.2) is denoted by
${\mathbb{R}}^{\ell}_{LC}\langle\langle X\rangle\rangle$.

A special class of Chen–Fliess series consists of those having an input-output
map $y=F_{c}[u]$ with a smooth $n$ dimensional state space realization

$\dot{z}=g_{0}(z)+\sum_{i=1}^{m}g_{i}(z)u_{i},\qquad z(0)=z_{0},\qquad y=f(z)$

on some open set $W\subseteq{\mathbb{R}}^{n}$. In this case, the generating
series is computed by

$\displaystyle(c,\eta)=L_{\eta}f(z_{0}):=L_{g_{i_{1}}}\cdots
L_{g_{i_{k}}}f(z_{0})$ (2.3)

for any $\eta=x_{i_{k}}\cdots x_{i_{1}}\in X^{\ast}$, where
$z_{0}\in{\mathbb{R}}^{n}$, and $L_{g_{i}}f$ is the Lie derivative of the
smooth output function $f\colon W\rightarrow{\mathbb{R}}$ with respect to
vector field $g_{i}$ [16, 30]. The control Lie algebra, $\mathscr{C}(g)$, for
this realization is the smallest Lie algebra containing $g_{i}$,
$i=0,1,\dots,m$ which is closed under the Lie bracket operation

$[g_{i},g_{j}](z)=\frac{\partial g_{j}}{\partial z}g_{i}(z)-\frac{\partial
g_{i}}{\partial z}g_{j}(z).$

Identifying $g_{i}\sim x_{i}$ and letting
$[x_{i},x_{j}]=x_{j}x_{i}-x_{i}x_{j}$, ${\mathscr{C}}(g)$ is isomorphic to a
Lie subalgebra ${\mathscr{C}}(X)$ of the free Lie algebra over $X$.
${\mathscr{C}}(X)$ will be referred to as the control Lie algebra over $X$.

###  2.4 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 sum and parallel 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
[16]. When 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$}$ are
interconnected in a cascade fashion, the composite system $F_{c}\circ F_{d}$
has the Fliess operator representation $F_{c\circ d}$, where the composition
product of $c$ and $d$ is given by [12, 13]

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

Here $1$ denotes the monomial $1\varnothing$, and $\psi_{d}$ is the continuous
(in the ultrametric sense) algebra homomorphism from
${\mathbb{R}}\langle\langle X\rangle\rangle$ to the set ${\rm
End}(\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$})$ of vector space
endomorphisms on ${\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,\dots,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$}$). By
definition, $\psi_{d}(\varnothing)$ is the identity map on
${\mathbb{R}}\langle\langle X\rangle\rangle$. A generalized series $\delta$ is
defined as the unit for the composition product, that is, $\delta\circ
c=c\circ\delta=c$ for all $c\in\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}$, or, equivalently, $F_{\delta}$ is the identity map on the
input space so that $F_{\delta}[u]=u$ for all admissible inputs $u$.

Finally, consider the additive feedback connection with $F_{c}$ in the forward
path and $F_{d}$ in the feedback path. The generating series
$e\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ defines a closed-
loop system $y=F_{e}[u]$ when it satisfies the feedback equation
$F_{e}[u]=F_{c}[u+F_{d\circ e}[u]]$. It is known that there always exists such
an $e=c@d$, where the series $c@d$ is the feedback product of $c$ and $d$
[21]. This product has an explicit formula in terms of the antipode of a
graded connected Hopf algebra [18]. Its construction relies in part on the
shuffle algebra.

##  3 Entropy of generating series

Consider ${\mathbb{R}}\langle\langle X\rangle\rangle$ as a graded
${\mathbb{R}}$-vector space with finite dimensional homogeneous components
$V_{n}$ spanned by all the words of degree $n$, $X(n)$, so that ${\rm
dim}(V_{n})=|X(n)|$. Given a series $c\in\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}$ and $n\in{\mathbb{N}}_{0}$, let ${\rm supp}_{n}(c):={\rm
supp}(c)\bigcap X(n)$. Define the support sequence of $c$ to be
$S_{c}=\\{n_{k}\in{\mathbb{N}}_{0}\colon|{\rm supp}_{n_{k}}(c)|\neq
0,\;k\in{\mathbb{N}}_{0}\\}$. It is assumed that $|X(n)|\sim K\gamma^{n}$ for
some real numbers $K,\gamma>0$ when $n\gg 0$.

######  Definition 3.1.

The entropy of a series $c\in\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}/\mbox{${\mathbb{R}}\langle X\rangle$}$ with support sequence
$S_{c}$ is

$h(c)=\limsup_{k\rightarrow\infty}\frac{1}{n_{k}}\log_{\gamma}(|{\rm
supp}_{n_{k}}(c)|).$

If $c\in\mbox{${\mathbb{R}}\langle X\rangle$}$, then $h(c):=0$.

The entropy of a generating series is roughly a (normalized) measure of the
rate at which its support grows with increasing degree relative to the maximum
rate it could grow as determined by the grading.

######  Theorem 3.2.

For every $c\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$, $h(c)$ is
well defined with $0\leq h(c)\leq 1$.

###### Proof.

The only nontrivial case is when $c\in\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}/\mbox{${\mathbb{R}}\langle X\rangle$}$. Consider the
sequence of real numbers $a_{k}=\log_{\gamma}(|{\rm supp}_{n_{k}}(c)|)/n_{k}$,
$n_{k}\in S(c)$, $k\geq 0$. It is clearly bounded from below by zero. It is
also bounded from above by one since no series in ${\mathbb{R}}\langle\langle
X\rangle\rangle$ has a larger support than ${\rm char}(X^{\ast})=\sum_{\eta\in
X^{\ast}}\eta$, and ${\rm supp}_{k}({\rm char}(X^{\ast}))\sim K\gamma^{k}$,
$k\gg 0$. As the infinite sequence $a_{k}$, $k\geq 0$ in ${\mathbb{R}}$ is
bounded, it must have at least one cluster point. The largest cluster point
uniquely defines $h(c)$. ∎

If the sequence $a_{k}$, $k\geq 0$ defined above converges, then clearly
$h(c)$ is equivalent to this limit. In addition, it is evident that $h$ is not
homogeneous as $h(\alpha c)=h(c)$ for all nonzero $\alpha\in{\mathbb{R}}$.
Unless stated otherwise, the default assumption in most examples will be that
$X=\\{x_{0},x_{1}\\}$, ${\mathbb{R}}\langle\langle X\rangle\rangle$ is graded
by word length so that $K=1$, $\gamma=2$, and either $S(c)={\mathbb{N}}_{0}$
or $S(c)={\mathbb{N}}$.

######  Example 3.3.

A series (or polynomial) is called a repeated word series if the only words in
its support are powers of a single word $\xi\in X^{+}$. For example,
$c=x_{1}+x_{1}^{2}$ and $d=\sum_{n\geq 0}(x_{0}x_{1}x_{0})^{n}$ are repeated
word series. Clearly, $h(c)=0$. In the latter case, where
$\xi=x_{0}x_{1}x_{0}$, observe $S_{d}=\\{k|\xi|\colon k\geq 0\\}$ and ${\rm
supp}_{k|\xi|}(d)=1$, $k\geq 0$, so that $h(d)=0$. Therefore, all repeated
word series have zero entropy.

######  Example 3.4.

A series $c\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ is said to
be linear if $|\eta|_{x_{1}}=1$ for all $\eta\in{\rm supp}(c)$. For example,
$c=\sum_{n\geq r}x_{0}^{n-1}x_{1}$ is a linear series with relative degree
$r\geq 1$ [27]. When $r=1$, for example, the input-output map $F_{c}$ is
realized by the linear time-invariant system

$\dot{z}=z+u,\qquad z(0)=0,\qquad y=z.$

Observe ${\rm supp}_{k}(c)=1$, $k\geq r$ so that $h(c)=0$.

######  Example 3.5.

Consider the linear series $c=\sum_{n_{0},n_{1}\geq
0}x_{0}^{n_{0}}x_{1}x_{0}^{n_{1}}$. In this case, ${\rm supp}_{k}(c)=k+1$,
$k\geq 0$, and thus, $h(c)=\lim_{k\rightarrow\infty}\log_{2}(k+1)/k=0$. This
implies that the generating series for any linear operator $F_{c}$ has zero
entropy.

######  Example 3.6.

A series $c\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ is said to
be input-limited if for some fixed $N\in{\mathbb{N}}$, $|\eta|_{x_{1}}\leq N$
for all $\eta\in{\rm supp}(c)$. It is known in general that rationality is not
preserved under the composition product. However, $c\circ d$ is rational if
$c$ and $d$ are rational, and $c$ is input-limited [12, 13]. Consider, for
example, the input-limited series

$c_{N}:=\sum_{n_{0},n_{1},\dots,n_{N}=0}^{\infty}x_{0}^{n_{0}}x_{1}x_{0}^{n_{1}}x_{1}\cdots
x_{0}^{n_{N-1}}x_{1}x_{0}^{n_{N}}.$

The number of compositions (order partitions) of a nonnegative integer
$K=n_{0}+n_{1}+n_{2}+\cdots+n_{N}$ into $N+1$ parts where $n_{i}\geq 0$ is
${K+N\choose N}$. Therefore, ${\rm supp}_{k}(c)={k\choose N}$, $k\geq N$.
Hence,

$\displaystyle
h(c)=\lim_{k\rightarrow\infty}\frac{1}{k}\log_{2}\left(\frac{k(k-1)\cdots(k-N+1)}{N!}\right)\leq\lim_{k\rightarrow\infty}\frac{N}{k}\log_{2}(k)-\frac{1}{k}\log_{2}(N!)=0,$

so that $h(c)=0$. This is in fact the case for all input-limited series.

######  Example 3.7.

Given a word $\xi\in X^{\ast}$, let $\tilde{\xi}$ denote the word whose
letters are written in reverse order. For example, if $\xi=x_{0}x_{1}x_{1}$,
then $\tilde{\xi}=x_{1}x_{1}x_{0}$. Consider the set of all even palindromes

$P=\big{\\{}\xi\tilde{\xi}\colon\xi\in X^{\ast}\big{\\}}.$

Observe if $\eta\in P$ then $\tilde{\eta}\in P$. It can be directly checked
that $\big{|}P\bigcap X^{2n}\big{|}=2^{n}$, $n\geq 0$. Setting
$c=\sum_{\eta\in P}\eta$, it follows that $S_{c}=\\{2k\colon k\geq 0\\}$ and
${\rm supp}_{2k}(c)=2^{k}$, $k\geq 0$. In which case, $h(c)=1/2$.

######  Example 3.8.

A word power series has the form $c_{1/N}=\sum_{\eta\in X^{\ast}}\eta^{N}$,
where $\eta^{N}$ denotes the Cauchy product power and $N\in{\mathbb{N}}$ is
fixed. Analysis similar to that in the previous example gives $h(c)=1/N$.

######  Example 3.9.

The word power series ${\rm char}(X^{\ast})=\sum_{\eta\in X^{\ast}}\eta$
appearing in the proof of Theorem 3.2 has entropy one in light of the previous
example, as does the series $d=c-x_{0}^{\ast}$, where
$x_{0}^{\ast}:=\sum_{k\geq 0}x_{0}^{k}$.

######  Example 3.10.

Consider the bilinear state space realization

$\dot{z}=z+zu,\qquad z(0)=1,\qquad y=z.$

Clearly, ${\rm dim}({\mathscr{C}}(X))=1$ since $g_{0}=g_{1}$ and
$[g_{0},g_{1}]=0$. As an algebra, ${\mathscr{C}}(X)$ has zero entropy [41].
But observe that $(c,\eta)=L_{\eta}f(z_{0})=1$ for all $\eta\in X^{\ast}$.
Thus, $c=\sum_{\eta\in X^{\ast}}\eta$ so that $h(c)=1$. That is, the
generating series of the input-output map has maximum entropy even though the
underlying state space realization has zero entropy in its control Lie
algebra. This is possible in light of (2.3) and the fact that
$L_{[g_{i},g_{j}]}h=L_{g_{i}}L_{g_{j}}h-L_{g_{j}}L_{g_{i}}h=0$ does not imply
that $L_{g_{i}}L_{g_{j}}h=L_{g_{j}}L_{g_{i}}h=0$. This will be clearer in the
next section when this example is revisited using the shuffle algebra, which
is playing a hidden role in this problem.

For any letter $x_{i}\in X$, let $x_{i}^{-1}$ denote the ${\mathbb{R}}$-linear
left-shift operator defined by $x_{i}^{-1}(\xi)=\xi^{\prime}$ when
$\xi=x_{i}\xi^{\prime}$ and zero otherwise. It is defined inductively for
higher order shifts via $(x_{i}\xi)^{-1}=\xi^{-1}x_{i}^{-1}$, where $\xi\in
X^{\ast}$. The left-shift operator acts as a derivation on the shuffle
product. The left-augmentation of $c\in\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}$ by $\xi\in X^{\ast}$ is simply the Cauchy product $\xi
c=\sum_{\eta\in X^{\ast}}(c,\eta)\xi\eta=\sum_{\eta\in X^{\ast}}(\xi
c,\eta)\eta$. Likewise, the right-augmentation of
$c\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ by $\xi\in X^{\ast}$
is $c\xi=\sum_{\eta\in X^{\ast}}(c,\eta)\eta\xi=\sum_{\eta\in
X^{\ast}}(c\xi,\eta)\eta$.

######  Theorem 3.11.

For any series $c\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ and
word $\xi\in X^{\ast}$, $h\big{(}\xi^{-1}(c)\big{)}\leq h(c)$ and $h(\xi
c)=h(c\xi)=h(c)$.

###### Proof.

The first claim is a consequence of the fact that ${\rm
supp}_{k}\big{(}\xi^{-1}(c)\big{)}\subseteq{\rm supp}_{k}(c)$, $k\geq 0$. The
equalities follow directly from the identities $|{\rm supp}_{k+\deg(\xi)}(\xi
c)|=|{\rm supp}_{k+\deg(\xi)}(c\xi)|=|{\rm supp}_{k}(c)|$, $k\geq 0$. ∎

In general, entropy is invariant only under augmentations.

######  Example 3.12.

Suppose $c=\sum_{\eta\in X^{\ast}}x_{0}\eta$. Then $h(c)=1$,
$h\big{(}x_{0}^{-1}(c)\big{)}=1$, and $h\big{(}x_{1}^{-1}(c)\big{)}=0$. On the
other hand, $h(x_{i}c)=h(cx_{i})=1$, $i=0,1$.

##  4 Entropy and interconnected nonlinear systems

######  Definition 4.1.

A magma $(\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$},\Box)$ with
entropy function $h$ is said to be entropy bounded if

$h(c\Box d)\leq\max(h(c),h(d)),\qquad\forall
c,d\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}.$

In essence, an entropy bounded product $\Box$ cannot create more entropy than
that which is already present in its arguments. The following is the first of
two main results in this section.

######  Theorem 4.2.

Addition, the Hadamard product, and the Cauchy product on
${\mathbb{R}}\langle\langle X\rangle\rangle$ are all entropy bounded.

###### Proof.

When necessary, it is sufficient to consider only the case where $c$ and $d$
are positively supported. That is, if $\eta\in{\rm supp}(c)$, then
$(c,\eta)>0$ and likewise for $d$. For the products under consideration, the
restriction to positively supported series will eliminate the possibility of
inter-term cancellations. Such cancellations can reduce the cardinality of the
support of the resulting series but never increase it. Without loss of
generality, it is assumed below that all the support sequences are equivalent
to ${\mathbb{N}}_{0}$.

Addition. A slightly stronger result is possible when $c$ and $d$ are
positively supported, namely, $h(c+d)=\max(h(c),h(d))$. Otherwise, the
possibility of cancellations makes the right-hand side only an upper bound.
Suppose $c$ and $d$ are positively supported. Observe then that ${\rm
supp}(c)\subseteq{\rm supp}(c+d)$, ${\rm supp}(d)\subseteq{\rm supp}(c+d)$,
and

${\rm supp}(c+d)={\rm supp}(c)\cup{\rm supp}(d).$

Therefore, $|{\rm supp}_{k}(c)|\leq|{\rm supp}_{k}(c+d)|$, $|{\rm
supp}_{k}(d)|\leq|{\rm supp}_{k}(c+d)|$, and

$\displaystyle|{\rm supp}_{k}(c+d)|\leq|{\rm supp}_{k}(c)|+|{\rm
supp}_{k}(d)|,\qquad\forall k\geq 0.$ (4.1)

Since $\log_{2}$ is an increasing function, the first two inequalities yield
$\max(h(c),h(d))\leq h(c+d)$. Consider a sequence
$a=\\{a_{k}\in{\mathbb{R}}\colon a_{k}\geq 1,\,k\in{\mathbb{N}}_{0}\\}$ such
that $\lambda(a):=\limsup_{k\rightarrow\infty}\log_{2}(a_{k})/k$ is a real
number. It can be verified for any two such sequences $a$ and $b$ that

$\lambda(a+b)=\max(\lambda(a),\lambda(b)).$ (4.2)

Hence, combining (4.1) and (4.2) gives $h(c+d)\leq\max(h(c),h(d))$, and the
claim is proved.

Hadamard product. If $\eta\in{\rm supp}_{k}(c\odot d)$, then $\eta\in{\rm
supp}_{k}(c)\cap{\rm supp}_{k}(d)$. But since ${\rm supp}_{k}(c)\cap{\rm
supp}_{k}(d)\subseteq{\rm supp}_{k}(c)$ and ${\rm supp}_{k}(c)\cap{\rm
supp}_{k}(d)\subseteq{\rm supp}_{k}(d)$, it follows that

$|{\rm supp}_{k}(c\odot d)|\leq\min(|{\rm supp}_{k}(c)|,|{\rm
supp}_{k}(d)|),\qquad\forall k\geq 0.$

Therefore, in general,

$h(c\odot d)\leq\min(h(c),h(d)).$

Cauchy product. Assume that $c,d\in\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}$ are positively supported. Then $\nu\in{\rm supp}_{k}(cd)$
if and only if

$(cd,\nu)=\sum_{\eta,\xi\in X^{\ast}\atop\nu=\eta\xi}(c,\eta)(d,\xi),$

where for at least one pair of words $(\eta,\xi)$ with $|\eta|+|\xi|=k$, the
product $(c,\eta)(d,\xi)\neq 0$. Therefore,

$|{\rm supp}_{k}(cd)|\leq\sum_{j=0}^{k}|{\rm supp}_{k-j}(c)||{\rm
supp}_{j}(d)|,\qquad\forall k\geq 0.$

Note that in general this upper bound is conservative since $\nu$ can be
constructed by concatenation of differently sized words, i.e.,
$\nu=x_{1}x_{0}x_{1}=(x_{1})(x_{0}x_{1})=(x_{1}x_{0})(x_{1})$. Now define the
sequences $a=\\{|{\rm supp}_{k}(c)|:k\geq 0\\}$ and $b=\\{|{\rm
supp}_{k}(d)|\colon k\geq 0\\}$. Observe for $k\geq 1$ that

$\displaystyle\log_{2}\left(\sum_{j=0}^{k}a_{k-j}b_{j}\right)\leq\max_{0\leq
j\leq k}\log_{2}(ka_{k-j}b_{j})=\log_{2}(k)+\max_{0\leq j\leq
k}\log_{2}(a_{k-j}b_{j}).$

Therefore,

$\displaystyle\limsup_{k\rightarrow\infty}\max_{0\leq j\leq
k}\frac{1}{k}\log_{2}(a_{k-j}b_{j})$
$\displaystyle=\limsup_{k\rightarrow\infty}\max_{0\leq j\leq
k}\frac{k-j}{k}\left(\frac{1}{k-j}\log_{2}(a_{k-j})\right)+\frac{j}{k}\left(\frac{1}{j}\log_{2}(b_{j})\right)$
$\displaystyle\leq\max(\lambda(a),\lambda(b))$

since $(k-j/k)+(j/k)=1$ and the terms $\log_{2}(a_{k-j})/(k-j)$ and
$\log_{2}(b_{j})/j$ are asymptotically bounded by $\lambda(a)$ and
$\lambda(b)$, respectively. Thus, $h(cd)\leq\max(h(c),h(d))$ as claimed. ∎

It is assumed in the following set of examples that $X=\\{x_{0},x_{1}\\}$.

######  Example 4.3.

Define $c_{0}$ to be the series in Example 3.3 when $\xi=x_{0}$. Let $c_{N}$
denote the series in Example 3.6 when $N\geq 1$. Theorem 4.2 implies that for
any integer $M\geq 0$, the input-limited series $d_{M}=\sum_{N=0}^{M}c_{N}$
has zero entropy. Note, however, that this property is not true in the limit
since $\lim_{M\rightarrow\infty}d_{M}={\rm char}(X^{\ast})$ and $h({\rm
char}(X^{\ast}))=1$. This indicates that
$h\colon\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}\rightarrow[0,1]$
is not continuous when convergence on ${\mathbb{R}}\langle\langle
X\rangle\rangle$ is defined in the ultrametric sense [3].

######  Example 4.4.

Reconsider the series of even palindromes $c=\sum_{\eta\in P}\eta$ in Example
3.7, where $h(c)=1/2$. Let $d=\sum_{k\geq 0}x_{0}^{k}$ so that $h(d)=0$. Then
$c\odot d=\sum_{k=0}^{\infty}x_{0}^{2k}$ so that $h(c\odot d)=0=\min(1/2,0)$
as expected.

######  Example 4.5.

All the series in Examples 3.3–3.6 can all be written as the Cauchy product of
repeated words series. For example, the series in Example 3.6 can be written
as $c_{N}=d_{0}^{\ast}x_{1}d_{1}^{\ast}x_{1}\cdots
d_{N-1}^{\ast}x_{1}d_{N}^{\ast}$, where $d_{i}^{\ast}=\sum_{k\geq
0}x_{0}^{k}$. Thus, by Theorem 4.2, every series in these examples must have
zero entropy as was demonstrated directly from the definition.

######  Example 4.6.

Reconsider the series of even palindromes $c=\sum_{\eta\in P}\eta$ in Example
3.7 where $h(c)=1/2$. The support of series $cc$ now contains elements that
are not palindromes, for example, $x_{0}^{2}x_{1}^{2}$. Nevertheless, Theorem
4.2 requires that $h(cc)\leq 1/2$. This can be verified by a direct
calculation. Note that every nonempty word in ${\rm supp}_{k}(cc)$ has the
form $\eta\tilde{\eta}\xi\tilde{\xi}$, where $2|\eta|+2|\xi|=k=2k^{\prime}$
with $k^{\prime}:=i+j$, $i:=|\eta|\geq 1$, and $j:=|\xi|\geq 1$. Observe that
$k^{\prime}:=i+j\geq 2$ has exactly ${k^{\prime}-1\choose 1}=k^{\prime}-1$
compositions with two parts $i$ and $j$. Thus, there are
$(k^{\prime}-1)2^{k^{\prime}}$ words in ${\rm supp}_{k}(cc)$. In which case,
$\log_{2}(|{\rm
supp}_{k}(cc)|)/k=\log_{2}((k^{\prime}-1)2^{k^{\prime}})/2k^{\prime}=1/2+\log_{2}(k^{\prime}-1)/2k^{\prime}$
so that in fact $h(cc)=1/2$.

The second main result of this section states that the remaining products of
interest on ${\mathbb{R}}\langle\langle X\rangle\rangle$ are not entropy
bounded. The claim is demonstrated via counterexamples presented subsequently.

######  Theorem 4.7.

The shuffle product, composition product, and feedback product on
${\mathbb{R}}\langle\langle X\rangle\rangle$ are not entropy bounded.

######  Example 4.8.

This example demonstrates that the shuffle product is not entropy bounded. If
$X=\\{x_{0},x_{1}\\}$, then $x_{i}^{\ast}=\sum_{k=0}^{\infty}x_{i}^{k}$ has
zero entropy. It is known that [8, 10]

${\rm char}\big{(}X^{k}\big{)}=\sum_{r_{0},r_{1}\geq 0\atop
r_{0}+r_{1}=k}x_{0}^{r_{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}}}}}\,}x_{1}^{r_{1}},\qquad
k\geq 0.$

Therefore,

$\displaystyle\sum_{\eta\in X^{\ast}}\eta={\rm
char}(X^{\ast})=\sum_{k=0}^{\infty}{\rm
char}\big{(}X^{k}\big{)}=\sum_{k=0}^{\infty}\sum_{r_{0},r_{1}\geq 0\atop
r_{0}+r_{1}=k}x_{0}^{r_{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}}}}}\,}x_{1}^{r_{1}}=x_{0}^{\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}}}}}\,}x_{1}^{\ast}.$

That is,

$h(x_{0}^{\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}}}}}\,}x_{1}^{\ast})=1>0=\max\\{h(x_{0}^{\ast}),h(x_{1}^{\ast})\\}.$

On the other hand, there are specific instances where the entropy bounded
property holds, for example,
$x_{i}^{\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}}}}}\,}x_{i}^{\ast}=(2x_{i})^{\ast}$ so
that $h(x_{i}^{\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}}}}}\,}x_{i}^{\ast})=h((2x_{i})^{\ast})=0$
[19].

######  Example 4.9.

This example illustrates that the composition product is not entropy bounded.
Let $c=x_{1}^{\ast}$ so that $h(c)=0$. It is shown in [24] that

$\big{(}c\circ c,x_{0}^{k_{0}}x_{1}^{k_{1}}\cdots
x_{0}^{k_{l-1}}x_{1}^{k_{l}}\big{)}=(k_{0})^{k_{1}}(k_{0}+k_{2})^{k_{3}}\cdots(k_{0}+k_{2}+k_{4}+\cdots+k_{l-1})^{k_{l}}$

for all odd $l\geq 1$ and $k_{i}\geq 0$, $i=0,1,\dots,l$ (assume $0^{0}:=1$).
Therefore, ${\rm supp}(c\circ c)=X^{\ast}$ and $h(c\circ c)=1$.

######  Example 4.10.

It is shown in this example that the feedback product is not entropy bounded.
Assume $X=\\{x_{0},x_{1}\\}$, and let $c=\sum_{k\geq 0}k!\,x_{1}^{k}$ so that
$h(c)=0$. Let $d=\delta$, the composition unit. Formally, $\delta\cap
X^{\ast}$ is empty so that $h(\delta):=0$. Consider an additive unity feedback
interconnection with $F_{c}$ in the forward path and $F_{\delta}=I$ in the
feedback path. This defines a feedback product $e=c@\delta$. The generating
series $c@\delta$ was computed explicitly in [11] using Hopf algebra methods
described in [9, 21] and found to have the form $c@\delta=\sum_{n\geq
1}b_{n}$, where the polynomial sequence $b_{n}\in\mbox{${\mathbb{R}}\langle
X\rangle$}$, $n\geq 1$ satisfies the linear recursion

$\displaystyle b_{n}=(n-1)b_{n-1}x_{1}+(n-2)b_{n-2}x_{0},\qquad n\geq 2$ (4.3)

with $b_{0}=0$ and $b_{1}=1$. These are the Devlin polynomials that appear in
a combinatorial characterization of periodic solutions to the Abel equation in
the context of Hilbert’s 16th problem [5, 6]. The first few polynomials are:

$\displaystyle b_{1}=1,$ $\displaystyle b_{2}=x_{1},$ $\displaystyle
b_{3}=2x_{1}^{2}+x_{0},$ $\displaystyle
b_{4}=6x_{1}^{3}+3x_{0}x_{1}+2x_{1}x_{0},$ $\displaystyle
b_{5}=24x_{1}^{4}+12x_{0}x_{1}^{2}+8x_{1}x_{0}x_{1}+6x_{1}^{2}x_{0}+3x_{0}^{2},$
$\displaystyle
b_{6}=120x_{1}^{5}+60x_{0}x_{1}^{3}+40x_{1}x_{0}x_{1}^{2}+30x_{1}^{2}x_{0}x_{1}+24x_{1}^{3}x_{0}+15x_{0}^{2}x_{1}+12x_{0}x_{1}x_{0}+8x_{1}x_{0}^{2}.$

It is not hard to see from (4.3) that ${\rm supp}(c@\delta)=X^{\ast}$ so that
if ${\mathbb{R}}\langle\langle X\rangle\rangle$ is graded by word length then
$h(c@\delta)=1$. It is shown in [5, Theorem 4.1] that for $n\geq 1$

${\rm supp}(b_{n})=\\{\eta\in
X^{\ast}\colon\deg(\eta)=2|\eta|_{x_{0}}+|\eta|_{x_{1}}+1=n\\}.$

Therefore, under the alternative grading in Example 2.1, where
$|X(n)|\sim\big{(}1/\sqrt{5}\big{)}\varphi^{n}$ with
$\varphi=\big{(}1+\sqrt{5}\big{)}/2$ when $m=1$, it is evident that
$h(c@\delta)=1$. It is worth noting that this second grading is also the
grading for the polynomial algebra of coordinate functions that defines the
output feedback Hopf algebra used to compute the general feedback product
$c@d$ as discussed in Section 2.4.

The final two examples provide some applications of these results in the
context of nonlinear control theory.

######  Example 4.11.

Let $c$ and $d$ be generating series for two linear time-invariant systems as
described in Example 3.4. As linearity is preserved under the parallel sum,
composition, and feedback interconnections, the resulting generating series in
each case must have zero entropy. The parallel product connection does not
preserve linearity but nevertheless yields a zero entropy generating series.
To see this, observe that every word in the support of
$x_{0}^{i}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}}}}}\,}x_{0}^{j}x_{1}$ must
have the form $\xi x_{1}$ with $\xi\in X^{i+j-1}$ having the letter $x_{1}$ in
any position. While it is not true that
$x_{0}^{\ast}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}}}}}\,}x_{0}^{\ast}x_{1}=x_{0}^{\ast}x_{1}x_{0}^{\ast}x_{1}$,
it does hold that ${\rm
supp}((x_{0}^{\ast}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}}}}}\,}(x_{0}^{\ast}x_{1}))={\rm
supp}(x_{0}^{\ast}x_{1}x_{0}^{\ast}x_{1})$, and the latter series has zero
entropy as discussed in Example 4.5.

######  Example 4.12.

Reconsider the state space system in Example 3.10 after the coordinate
transformation $z=\exp(\bar{z})$ has been applied, namely,

$\dot{\bar{z}}=1+u,\qquad\bar{z}(0)=0,\qquad y=\exp(\bar{z}).$

The generating series is known to be invariant under a change of coordinates
[30]. Observe $\bar{z}=F_{x_{0}+x_{1}}[u]$ so that

$\displaystyle
y=\exp(F_{x_{0}+x_{1}}[u])=\sum_{n=0}^{\infty}(F_{x_{0}+x_{1}}[u])^{n}\frac{1}{n!}=\sum_{n=0}^{\infty}(F_{(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}}}}}\,}n}}[u])\frac{1}{n!},$

using the shuffle power identity
$F_{c}^{n}[u]=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}}}}}\,}n}}[u]$. Therefore,
$y=F_{c}[u]$, where

$c=\sum_{n=0}^{\infty}(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}}}}}\,}n}\frac{1}{n!}=\sum_{n=0}^{\infty}{\rm
char}(X^{n})=\sum_{\eta\in X^{\ast}}\eta,$

where the identity ${\rm char}(X^{n})=({\rm
char}(X))^{{\,{\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}}}}}\,}n}/n!$ has been used
above. What is clear in this coordinate system is that the output function is
largely responsible for the maximal growth in the entropy of the generating
series $c$ due to the appearance of the shuffle product. Observe the vector
fields in the state equation satisfy $\bar{g}_{0}=\bar{g}_{1}$ so that
$x_{0}\sim x_{1}$ and $[x_{0},x_{1}]=0$. Hence, the entropy of the control Lie
algebra is still zero as in the original coordinate system.

##  5 Entropy ultrametric space

Two series $c,d\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ are
said to be entropy equivalent, denoted by $c\sim_{h}d$, when $h(c-d)=0$. Using
this equivalence relation, let $A=\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}/{\sim_{h}}$ denote the quotient space. No notational
distinction between elements of ${\mathbb{R}}\langle\langle X\rangle\rangle$
and $A$ will be made except that $0$ will denote the equivalence class of zero
entropy series in $A$, and $c=d$ is understood to be $c\sim_{h}d$ when $c,d\in
A$.

######  Theorem 5.1.

The vector space $A=(A,{\rm dist}_{h})$ with ${\rm dist}_{h}(c,d):=h(c-d)$ for
$c,d\in A$ is a bounded ultrametric space.

###### Proof.

The only nontrivial property is the ultrametric inequality. Observe that for
any ${c{,}d{,}e\\!\in\\!A}$:

$\displaystyle{\rm dist}_{h}(c,d)=h(c-d)=h((c-e)+(e-d))$
$\displaystyle\hphantom{{\rm
dist}_{h}(c,d)}{}\leq\max(h(c-e),h(e-d))=\max({\rm dist}_{h}(c,e),{\rm
dist}_{h}(e,d)).$

The boundedness property is clear. ∎

Note that ${\rm dist}_{h}$ is not induced by a semi-norm as it is not
homogeneous, recall ${\rm dist}_{h}(\alpha c,\alpha d)={\rm dist}_{h}(c,d)$
for all nonzero $\alpha\in{\mathbb{R}}$.

######  Example 5.2.

In the present context, the series in Example 4.3 satisfy $d_{M}=\hbox{$0$}$,
$M\geq 0$. So as a sequence in $A$, it trivially converges to $0$ in $A$.

######  Example 5.3.

The sequence $c_{1/N}$, $N\geq 1$ in Example 3.8 defines a nontrivial sequence
in $A$. Since $\lim_{N\rightarrow\infty}{\rm
dist}_{h}(c_{1/N},1)=\lim_{N\rightarrow\infty}h\big{(}\sum_{\eta\in
X^{+}}\eta^{N}\big{)}=\lim_{N\rightarrow\infty}1/N=0$, this sequence also
converges to $0$ in $A$.

An immediate question is in what sense, if any, is $A$ complete? It is known
under various notions of completeness that contractions on ultrametric spaces
have a unique fixed point or some approximate fixed point [42, 43]. But at
present, this is an open problem.

Let $X$ and $Y$ be two arbitrary alphabets. Any ${\mathbb{R}}$-linear mapping
$\tau\colon\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}\rightarrow\mbox{${\mathbb{R}}\langle\langle
Y\rangle\rangle$}$ is called a transduction [15, 31, 35, 44]. It is completely
specified by

$\tau(\eta)=\sum\limits_{\xi\in Y^{*}}(\tau(\eta),\xi)\xi,\qquad\forall\eta\in
X^{*},$

if for each $c\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$, the sum
$\sum_{\eta\in X^{\ast}}(\tau(\eta),\xi)(c,\eta)$ is finite for all $\xi\in
Y^{\ast}$. Otherwise, it is only partially defined on
${\mathbb{R}}\langle\langle X\rangle\rangle$. One can canonically associate
with any transduction $\tau$ a series in ${\mathbb{R}}\langle\langle X\otimes
Y\rangle\rangle$, namely

$\hat{\tau}=\sum\limits_{\eta\in
X^{*}}\eta\otimes\tau(\eta)=\sum\limits_{\eta\in X^{*},\;\xi\in
Y^{*}}(\tau(\eta),\xi)\,\eta\otimes\xi.$

From $\hat{\tau}$ define a second transduction
$\tau^{\prime}\colon\mbox{${\mathbb{R}}\langle\langle
Y\rangle\rangle$}\rightarrow\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}$ via

$\tau^{\prime}(\xi)=\sum\limits_{\eta\in
X^{*}}(\tau(\eta),\xi)\eta,\qquad\forall\xi\in Y^{*}.$

$\tau^{\prime}$ is called the inverse of $\tau$. A transduction $\tau$ is
called rational if the series $\hat{\tau}$ is a rational series in
${\mathbb{R}}\langle\langle X\otimes Y\rangle\rangle$. In which case, every
rational series in ${\mathbb{R}}\langle\langle X\rangle\rangle$ is mapped to a
rational series in ${\mathbb{R}}\langle\langle Y\rangle\rangle$ (assuming it
is well-defined).

There are a number of interesting open problems regarding transductions and
entropy. Suppose ${\mathbb{R}}\langle\langle X\rangle\rangle$ and
${\mathbb{R}}\langle\langle Y\rangle\rangle$ are $N_{0}$-graded vector spaces.
Then $\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}\otimes\mbox{${\mathbb{R}}\langle\langle Y\rangle\rangle$}$
is also an $N_{0}$-graded vector space with

$(\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}\otimes\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$})_{n}=\bigoplus_{n=i+j}(\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$})_{i}\otimes(\mbox{${\mathbb{R}}\langle\langle
Y\rangle\rangle$})_{j}.$

If, as assumed in Section 3, $(\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$})_{i}$ and $(\mbox{${\mathbb{R}}\langle\langle
Y\rangle\rangle$})_{j}$ are spanned by all the words of degree $i$ and $j$,
respectively, then likewise for the element
$(\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$}\otimes\mbox{${\mathbb{R}}\langle\langle
X\rangle\rangle$})_{n}$. Therefore, a given $\hat{\tau}$ has a well defined
notion of entropy in terms of its formal power series representation as an
element in ${\mathbb{R}}\langle\langle X\otimes Y\rangle\rangle$. If
$c\in\mbox{${\mathbb{R}}\langle\langle X\rangle\rangle$}$ and
$d\in\mbox{${\mathbb{R}}\langle\langle Y\rangle\rangle$}$, then the first open
question is how are $h(c)$ and $h(\tau(c))$ related, and likewise for $h(d)$
and $h(\tau^{\prime}(d))$? (Here $h$ refers to the appropriate definition of
entropy based on its argument.) In the event that $X=Y$, there are
corresponding mappings $\tau_{A}\colon A\rightarrow A$ and
$\tau^{\prime}_{A}\colon A\rightarrow A$ between entropy equivalences classes.
Such a mapping is said to be strictly contracting if

${\rm dist}_{h}(\tau_{A}(c),\tau_{A}(d))<{\rm dist}_{h}(c,d),\qquad\forall
c\neq d\in A.$

A second open question is what notion of completeness is available for $A$
that would render a fixed point, i.e., $\tau_{A}(c)=c$ and/or
$\tau_{A}^{\prime}(d)=d$?

##  6 Conclusions

A definition of entropy was introduced for the generating series of a
Chen–Fliess series. The concept is most closely related to the notion that
appears in formal language theory. It was shown to be trivial in the case of
linear systems, i.e., all linear systems have zero entropy. Formal power
series products induced or related to system interconnections were then
classified in terms of their ability to increase entropy relative to their
arguments. In particular, the shuffle product and all the products that
utilize it in their definition can increase entropy. This result will likely
have applications in future work regarding networks of Chen–Fliess series.
Finally, the paper concluded by introducing an entropy ultrametric space as a
possible context for the future analysis of feedback systems.

### Acknowledgement

The author would like to thank the referees for suggesting some significant
clarifications and improvements to this paper.

## References

  * [1] Anick D.J., Non-commutative graded algebras and their Hilbert series, J. Algebra 78 (1982), 120–140.
  * [2] Atiyah M.F., MacDonald I.G., Introduction to commutative algebra, Addison–Wesley Publishing Co., Reading, Mass. – London – Don Mills, Ont., 1969\.
  * [3] Berstel J., Reutenauer C., Rational series and their languages, EATCS Monogr. Theoret. Comput. Sci., Vol. 12, Springer-Verlag, Berlin, 1988.
  * [4] Caracciolo S., Radicati L.A., Entropy ultrametric for dynamical and disordered systems, J. Physique 50 (1989), 2919–2930.
  * [5] Devlin J., Word problems related to periodic solutions of a nonautonomous system, Math. Proc. Cambridge Philos. Soc. 108 (1990), 127–151.
  * [6] Devlin J., Word problems related to derivatives of the displacement map, Math. Proc. Cambridge Philos. Soc. 110 (1991), 569–579.
  * [7] Downarowicz T., Entropy in dynamical systems, New Math. Monogr., Vol. 18, Cambridge University Press, Cambridge, 2011.
  * [8] Duffaut Espinosa L.A., Interconnections of nonlinear systems driven by $L_{2}$-Itô stochastic process, Ph.D. Thesis, Old Dominion University, 2009, https://doi.org/10.25777/cngz-5y11.
  * [9] Duffaut Espinosa L.A., Ebrahimi-Fard K., Gray W.S., A combinatorial Hopf algebra for nonlinear output feedback control systems, J. Algebra 453 (2016), 609–643, arXiv:1406.5396.
  * [10] Duffaut Espinosa L.A., Gray W.S., González O.R., On Fliess operators driven by $L_{2}$-Itô random processes, in Proc. 48th IEEE Conf. on Decision and Control, IEEE, Shanghai, China, 2009, 7478–7484.
  * [11] Ebrahimi-Fard K., Gray W.S., Center problem, Abel equation and the Faà di Bruno Hopf algebra for output feedback, Int. Math. Res. Not. 2017 (2017), 5415–5450, arXiv:1507.06939.
  * [12] Ferfera A., Combinatoire du monoïde libre appliquée à la composition et aux variations de certaines fonctionnelles issues de la théorie des systèmes, Ph.D. Thesis, University of Bordeaux I, 1979.
  * [13] Ferfera A., Combinatoire du monoïde libre et composition de certains systèmes non linéaires, Astérisque 75–76 (1980), 87–93, available at http://www.numdam.org/item/AST_1980__75-76__87_0.
  * [14] Fliess M., Sur divers produits de séries formelles, Bull. Soc. Math. France 102 (1974), 181–191.
  * [15] Fliess M., Transductions de séries formelles, Discrete Math. 10 (1974), 57–74.
  * [16] Fliess M., Fonctionnelles causales non linéaires et indéterminées non commutatives, Bull. Soc. Math. France 109 (1981), 3–40.
  * [17] Fliess M., Réalisation locale des systèmes non linéaires, algèbres de Lie filtrées transitives et séries génératrices non commutatives, Invent. Math. 71 (1983), 521–537.
  * [18] Foissy L., The Hopf algebra of Fliess operators and its dual pre-Lie algebra, Comm. Algebra 43 (2015), 4528–4552, arXiv:1304.1726.
  * [19] Gray W.S., Formal power series methods in nonlinear control theory, unpublished, 1.2 ed., 2022, available at http://www.ece.odu.edu/~sgray/fps-book.
  * [20] Gray W.S., System identification entropy for Chen–Fliess series and their interconnections, in Proc. 2022 Allerton Conf. on Communication, Control, & Computing, Allerton Park, Illinois, to appear.
  * [21] Gray W.S., Duffaut Espinosa L.A., Ebrahimi-Fard K., Faà di Bruno Hopf algebra of the output feedback group for multivariable Fliess operators, Systems Control Lett. 74 (2014), 64–73, arXiv:1406.5378.
  * [22] Gray W.S., Ebrahimi-Fard K., SISO output affine feedback transformation group and its Faà di Bruno Hopf algebra, SIAM J. Control Optim. 55 (2017), 885–912, arXiv:1411.0222.
  * [23] Gray W.S., Ebrahimi-Fard K., Generating series for networks of Chen–Fliess series, Systems Control Lett. 147 (2021), 104827, 8 pages, arXiv:2007.00743.
  * [24] Gray W.S., Herencia-Zapana H., Duffaut Espinosa L.A., González O.R., Bilinear system interconnections and generating series of weighted Petri nets, Systems Control Lett. 58 (2009), 841–848.
  * [25] Gray W.S., Li Y., Generating series for interconnected analytic nonlinear systems, SIAM J. Control Optim. 44 (2005), 646–672.
  * [26] Gray W.S., Thitsa M., A unified approach to generating series for mixed cascades of analytic nonlinear input-output systems, Internat. J. Control 85 (2012), 1737–1754.
  * [27] Gray W.S., Venkatesh G.S., Relative degree of interconnected SISO nonlinear control systems, Systems Control Lett. 124 (2019), 99–105.
  * [28] Gray W.S., Wang Y., Fliess operators on $L_{p}$ spaces: convergence and continuity, Systems Control Lett. 46 (2002), 67–74.
  * [29] Gray W.S., Wang Y., Formal Fliess operators with applications to feedback interconnections, in Proc. 18th Inter. Symp. on the Mathematical Theory of Networks and Systems, Blacksburg, Virginia, 2008, 12 pages.
  * [30] Isidori A., Nonlinear control systems, 3rd ed., Comm. Control Engrg. Ser., Springer-Verlag, Berlin, 1995.
  * [31] Jacob G., Sur un théorème de Shamir, Inf. Control 27 (1975), 218–261.
  * [32] Kawan C., Delvenne J.-C., Network entropy and data rates required for networked control, IEEE Trans. Control Netw. Syst. 3 (2016), 57–66, arXiv:1409.6037.
  * [33] Kuich W., On the entropy of context-free languages, Inf. Control 16 (1970), 173–200.
  * [34] Kuich W., Maurer H., The structure generating function and entropy of tuple languages, Inf. Control 19 (1971), 195–203.
  * [35] Kuich W., Salomaa A., Semirings, automata, languages, EATCS Monogr. Theoret. Comput. Sci., Vol. 5, Springer-Verlag, Berlin, 1986.
  * [36] Liberzon D., On topological entropy of interconnected nonlinear systems, IEEE Control Syst. Lett. 5 (2021), 2210–2214.
  * [37] Lind D., Marcus B., An introduction to symbolic dynamics and coding, 2nd ed., Cambridge Math. Lib., Cambridge University Press, Cambridge, 2021.
  * [38] Lothaire M., Combinatorics on words, 2nd ed., Cambridge Math. Lib., Cambridge University Press, Cambridge, 1997.
  * [39] Matveev A.S., Proskurnikov A.V., Pogromsky A., Fridman E., Comprehending complexity: data-rate constraints in large-scale networks, IEEE Trans. Automat. Control 64 (2019), 4252–4259.
  * [40] McLachlan R.I., Ryland B., The algebraic entropy of classical mechanics, J. Math. Phys. 44 (2003), 3071–3087, arXiv:math-ph/0210030.
  * [41] Newman M.F., Schneider C., Shalev A., The entropy of graded algebras, J. Algebra 223 (2000), 85–100.
  * [42] Priess-Crampe S., Ribenboim P., Ultrametric dynamics, Illinois J. Math. 55 (2011), 287–303.
  * [43] Priess-Crampe S., Ribenboim P., The approximation to a fixed point, J. Fixed Point Theory Appl. 14 (2013), 41–53, arXiv:1307.6431.
  * [44] Salomaa A., Soittola M., Automata-theoretic aspects of formal power series, Monogr. Comput. Sci., Springer-Verlag, New York – Heidelberg, 1978.
  * [45] Savkin A.V., Analysis and synthesis of networked control systems: topological entropy, observability, robustness and optimal control, Automatica 42 (2006), 51–62.
  * [46] Schneider F.M., Borchmann D., Topological entropy of formal languages, Semigroup Forum 94 (2017), 556–581, arXiv:1507.03393.
  * [47] Shannon C.E., A mathematical theory of communication, Bell System Tech. J. 27 (1948), 379–423.
  * [48] Sloane N.J.A., The on-line encyclopedia of integer sequences, available at https://oeis.org.
  * [49] Smith C., Enumeration of the distinct shuffles of permutations, Ph.D. Thesis, Harvard University, 2009, available at https://www.proquest.com/docview/304890446.
  * [50] Thitsa M., Gray W.S., On the radius of convergence of interconnected analytic nonlinear input-output systems, SIAM J. Control Optim. 50 (2012), 2786–2813.
  * [51] Tomar M.S., Zamani M., Compositional quantification of invariance feedback entropy for networks of uncertain control systems, IEEE Control Syst. Lett. 4 (2020), 827–832.
  * [52] Venkatesh G.S., Wiener–Fliess composition of formal power series: additive static feedback and shuffle rational series, Ph.D. Thesis, Old Dominion University, 2021, https://doi.org/10.25777/t2b1-dx91.
  * [53] Venkatesh G.S., Gray W.S., Formal power series approach to nonlinear systems with static output feedback, Internat. J. Control, to appear, arXiv:2110.10034.
  * [54] Wang Y., Algebraic differential equations and nonlinear control systems, Ph.D. Thesis, Rutgers University, 1990, available at https://www.proquest.com/docview/303872790.
  * [55] Winter-Arboleda I.M., Gray W.S., Duffaut Espinosa L.A., Fractional Fliess operators: two approaches, in Proc. 49th Conf. on Information Sciences and Systems, IEEE, Baltimore, Maryland, 2015, 6 pages.
  * [56] Young L.-S., Entropy in dynamical systems, in Entropy, Princeton Ser. Appl. Math., Princeton University Press, Princeton, New Jersey, 2003, 313–327.
  * [57] Zames G., On the metric complexity of causal linear systems: $\varepsilon$-entropy and $\varepsilon$-dimension for continuous time, IEEE Trans. Automat. Control 24 (1979), 222–230.


# On disjoint sets

Jin-Hui Fang  Department of Mathematics, Nanjing University of Information
Science $\&$ Technology, Nanjing 210044, PR China<EMAIL_ADDRESS>and
Csaba Sándor  Department of Stochastics, Institute of Mathematics, Budapest
University of Technology and Economics, Műegyetem rkp. 3., H-1111, Budapest,
Hungary; Department of Computer Science and Information Theory, Budapest
University of Technology and Economics, Műegyetem rkp. 3., H-1111 Budapest,
Hungary; MTA-BME Lendület Arithmetic Combinatorics Research Group, ELKH,
Műegyetem rkp. 3., H-1111 Budapest, Hungary<EMAIL_ADDRESS>
###### Abstract.

Two sets of nonnegative integers $A=\\{a_{1}<a_{2}<\cdots\\}$ and
$B=\\{b_{1}<b_{2}<\cdots\\}$ are defined as _disjoint_ , if
$\\{A-A\\}\bigcap\\{B-B\\}=\\{0\\}$, namely, the equation
$a_{i}+b_{t}=a_{j}+b_{k}$ has only trivial solution. In 1984, Erdős and Freud
[J. Number Theory 18 (1984), 99-109.] constructed disjoint sets $A,B$ with
$A(x)>\varepsilon\sqrt{x}$ and $B(x)>\varepsilon\sqrt{x}$ for some
$\varepsilon>0$, which answered a problem posed by Erdős and Graham. In this
paper, following Erdős and Freud’s work, we explore further properties for
disjoint sets. As a main result, we prove that, for disjoint sets $A$ and $B$,
assume that $\\{x_{1}<x_{2}<\cdots\\}$ is a set of positive integers such that
$\frac{A(x_{n})B(x_{n})}{x_{n}}\rightarrow 2$ as $x_{n}\to\infty$, then, (i)
for any $0<c_{1}<c_{2}<1,$ $c_{1}x_{n}\leqslant y\leqslant c_{2}x_{n}$, we
have $\frac{A(y)B(y)}{y}\rightarrow 1$ as $n\rightarrow\infty$; (ii) for any
$1<c_{3}<c_{4}<2,$ $c_{3}x_{n}\leqslant y\leqslant c_{4}x_{n}$, we have
$A(y)B(y)=(2+o(1))x_{n}$ as $n\rightarrow\infty$.

###### Key words and phrases:

Disjoint sets, Sidon, difference

###### 2020 Mathematics Subject Classification:

Primary 11B13, Secondary 11B34

* Corresponding author.

The first author is supported by the National Natural Science Foundation of
China, Grant No. 12171246 and the Natural Science Foundation of Jiangsu
Province, Grant No. BK20211282. The second author is supported by the NKFIH
Grants No. K129335.

##  1\. Introduction

As a classic topic, Sidon’s problems attracts much interest in combinatorial
number theory, where a set $A=\\{a_{k}\\}_{k=1}^{\infty}$ of positive integers
is called _Sidon_ if the differences $a_{i}-a_{j}(i\neq j)$ are all distinct.
For a positive real number $x$, denote $A(x)$ by the number of elements $a\in
A$ with $a\leqslant x$. In [2], Erdős and Graham posed an interesting problem
as follows:

Erdős-Graham Problem. Let $A=\\{a_{1}<a_{2}<\cdots\\}$ and
$B=\\{b_{1}<b_{2}<\cdots\\}$ be sequences of integers satisfying
$A(x)>\varepsilon\sqrt{x}$ and $B(x)>\varepsilon\sqrt{x}$ for some
$\varepsilon>0$. Is it true that $a_{i}-a_{j}=b_{k}-b_{t}$ has infinitely many
solutions?

In 1984, Erdős and Freud [1] provided a negative answer by choosing $A$ as
nonnegative integers consisting only even powers of two and $B$ as nonnegative
integers consisting only odd powers of two, since every integer can be
uniquely written as the sum of different powers of two and

$\displaystyle\liminf_{x\rightarrow\infty}\frac{\min\\{A(x)B(x)\\}}{\sqrt{x}}=\frac{1}{\sqrt{2}}.$

In [1], Erdős and Freud also introduced the notations $SP$ and $IN$ as
follows:

$\displaystyle SP=\limsup_{x\rightarrow\infty}\frac{A(x)B(x)}{x},\hskip
11.38109ptIN=\liminf_{x\rightarrow\infty}\frac{\min\\{A(x),B(x)\\}}{\sqrt{x}}.$

Two sets of nonnegative integers $A=\\{a_{1}<a_{2}<\cdots\\}$ and
$B=\\{b_{1}<b_{2}<\cdots\\}$ are defined as _disjoint_ , if
$\\{A-A\\}\bigcap\\{B-B\\}=\\{0\\}$, namely, the equation
$a_{i}+b_{t}=a_{j}+b_{k}$ has only trivial solution. Erdős and Freud [1]
proved the following nice results for disjoint sets $A$ and $B$:

Theorem A. ([2, Theorem 1]) The largest possible value of $SP$ is 2, moreover
the following more precise estimations hold:

1.1. To any function $H(x)$ with $\limsup_{x\rightarrow\infty}H(x)=\infty$, we
can construct sets $A,B$ such that

$\displaystyle A(x)B(x)\geqslant 2x-H(x)$

is valid for infinitely many (integer) values of $x$.

1.2. The previous result is best possible: for any $A$ and $B$,
$A(x)B(x)-2x\rightarrow-\infty$ ($x\rightarrow\infty$).

Theorem B. ([2, Theorem 3.3]) If $SP=2$, then $IN=0$.

In this paper, we further consider the properties of disjoint sets and prove
that:

######  Theorem 1.1.

For disjoint sets $A$ and $B$, assume that $\\{x_{1}<x_{2}<\cdots\\}$ is a set
of positive integers such that

$\displaystyle\lim_{n\rightarrow\infty}\frac{A(x_{n})B(x_{n})}{x_{n}}=2,\hskip
8.53581pt\mbox{namely,}\hskip 8.53581ptSP=2.$

(i) For any $0<c_{1}<c_{2}<1,$ $c_{1}x_{n}\leqslant y\leqslant c_{2}x_{n}$, we
have

$\displaystyle\frac{A(y)B(y)}{y}\rightarrow 1\hskip 8.53581pt\mbox{as}\hskip
8.53581ptn\rightarrow\infty.$

(ii) For any $1<c_{3}<c_{4}<2,$ $c_{3}x_{n}\leqslant y\leqslant c_{4}x_{n}$,
we have

$\displaystyle A(y)B(y)=(2+o(1))x_{n}\hskip 8.53581pt\mbox{as}\hskip
8.53581ptn\rightarrow\infty.$

(iii)

$\displaystyle\limsup_{n\rightarrow\infty}\frac{A(2x_{n})B(2x_{n})}{2x_{n}}\leqslant\frac{3}{2}.$

Furthermore, the constant $\frac{3}{2}$ is best possible.

We characterize the set $\\{x_{1}<x_{2}<\cdots\\}$ such that
$\frac{A(x_{n})B(x_{n})}{x_{n}}\rightarrow 2$ for disjoint sets $A$ and $B$.

######  Theorem 1.2.

(i) For disjoint sets $A$ and $B$, if $\\{x_{1}<x_{2}<\cdots\\}$ is a set of
positive integers with $x_{i+1}\geqslant 2x_{i}$ for all large $i$ such that

(1.1)
$\displaystyle\lim_{n\rightarrow\infty}\frac{A(x_{n})B(x_{n})}{x_{n}}=2,$

then

(1.2) $\displaystyle\frac{x_{n+1}}{x_{n}}\rightarrow\infty\hskip
11.38109pt\mbox{as}\hskip 11.38109ptn\rightarrow\infty.$

(ii) Let $\\{x_{1}<x_{2}<\cdots\\}$ be a set of positive integers satisfying
(1.2). Then there exist disjoint sets $A$ and $B$ such that

$\displaystyle\lim_{n\rightarrow\infty}\frac{A(x_{n})B(x_{n})}{x_{n}}=2.$

Furthermore, we generalize the above Theorem B, that is:

######  Theorem 1.3.

For disjoint sets $A$ and $B$, if $IN\geqslant 0$, then

(1.3) $\displaystyle\frac{IN^{6}}{IN^{2}+8}\leqslant 64(2-SP).$

For disjoint sets $A$ and $B$, we have
$\binom{A(x)}{2}+\binom{B(x)}{2}\leqslant x$. Hence $IN\leqslant 1$. The
following corollary is obtained.

######  Corollary 1.4.

For disjoint sets $A$ and $B$, we have $IN\leqslant
2\sqrt[3]{3}\sqrt[6]{2-SP}$.

For a given positive integer $k\geqslant 2$, write

$\displaystyle
A=\\{\epsilon_{0}+\epsilon_{2}k^{2}+\cdots+\epsilon_{2s-2}k^{2s-2},\epsilon_{2i}=0,1,\cdots,k-1\\},$
$\displaystyle
B=\\{\epsilon_{1}k+\epsilon_{3}k^{3}+\cdots+\epsilon_{2s-1}k^{2s-1},\epsilon_{2i-1}=0,1,\cdots,k-1\\},$

Obviously, $A$ and $B$ are disjoint sets. Erdős and Freud obtained in [1] that

$\displaystyle SP=\frac{2(k+1)}{k+2}\hskip 8.53581pt\mbox{and}\hskip
8.53581ptIN=\frac{1}{\sqrt{k}}.$

Based on the above result, we naturally posed a problem:

######  Problem 1.5.

For disjoint sets $A$ and $B$, is there some positive constant $C$ such that

$IN\leqslant C\sqrt{2-SP}?$

##  2\. Proof of Main Results

During the proof of Theorems 1.1-1.2, we will employ the following fact many
times.

Proposition 1. Let $A$ and $B$ be disjoint sets with $SP=2$, namely,

$\displaystyle\lim_{n\rightarrow\infty}\frac{A(x_{n})B(x_{n})}{x_{n}}=2.$

Then, with the exception of at most $o(x_{n})$ numbers, all numbers in
$[0,2x_{n}]$ can be written as $a_{i}+b_{j}$ with $a_{i}\leqslant
x_{n},b_{j}\leqslant x_{n}$.

Proof of Theorem 1.1. Before the proof of Theorem 1.1, we first prove the
following proposition.

Proposition 2. There exist functions $y_{n}<z_{n}<x_{n}$, $y_{n}\to\infty$
such that $y_{n}=o(x_{n})$, $z_{n}=x_{n}-y_{n}$ and one of the following
conclusion holds:

(i)

$\displaystyle A(y_{n})=(0.5+o(1))A(x_{n}),\hskip
5.69054ptA(z_{n})-A(y_{n})=o(x_{n}),\hskip
5.69054ptA(x_{n})-A(z_{n})=(0.5+o(1))A(x_{n}),$

and

$\displaystyle B(y)=(\frac{y}{x_{n}}+o(1))B(x_{n})\hskip
8.53581pt\mbox{for}\hskip 8.53581pty_{n}<y<z_{n};$

(ii)

$\displaystyle B(y_{n})=(0.5+o(1))B(x_{n}),\hskip
5.69054ptB(z_{n})-B(y_{n})=o(x_{n}),\hskip
5.69054ptB(x_{n})-B(z_{n})=(0.5+o(1))B(x_{n})$

and

$\displaystyle A(y)=(\frac{y}{x_{n}}+o(1))A(x_{n})\hskip
8.53581pt\mbox{for}\hskip 8.53581pty_{n}<y<z_{n};$

###### Proof.

For any positive number $c^{\prime}$ and any $y_{n}$ with
$c^{\prime}x_{n}\leqslant y_{n}\leqslant\frac{1}{2}x_{n}$, we can only use
$a_{i}\leqslant y_{n}$ and $b_{i}\leqslant y_{n}$ for the numbers in
$[0,y_{n}]$. Similarly, we can only use $z_{n}\leqslant a_{i}\leqslant x_{n}$
and $z_{n}\leqslant b_{i}\leqslant x_{n}$ for the numbers in $[u_{n},2x_{n}]$.
It infers from Proposition 1 that

(2.1) $\displaystyle A(y_{n})B(y_{n})>y_{n}-o(x_{n}),\hskip
8.53581pt(A(x_{n})-A(z_{n})(B(x_{n})-B(z_{n}))>y_{n}-o(x_{n}).$

On the other hand, by considering the difference, we have

$A(y_{n})B(y_{n})+(A(x_{n})-A(z_{n}))(B(x_{n})-B(z_{n}))\leqslant 2y_{n}.$

It follows from (2.1) that

(2.2) $\displaystyle A(y_{n})B(y_{n})=y_{n}+o(x_{n})$

and

(2.3) $\displaystyle(A(x_{n})-A(z_{n}))(B(x_{n})-B(z_{n}))=y_{n}+o(x_{n})$

Let $\delta_{1}>0$ and let $\delta_{1}x_{n}\leqslant
y_{n}\leqslant\frac{1}{3}x_{n}$. Then the sets $A\cap[0,y_{n}]$,
$A\cap]y_{n},2y_{n}]$ and $A\cap]z_{n},x_{n}]$ are distinct. By considering
the differences we have

$A(y_{n})B(y_{n})+(A(2y_{n})-A(y_{n}))(B(2y_{n})-B(y_{n}))+(A(x_{n})-A(z_{n}))(B(x_{n})-B(z_{n}))\leqslant
2y_{n}.$

It follows from (2.2) and (2.3) that

(2.4) $\displaystyle(A(2y_{n})-A(y_{n}))(B(2y_{n})-B(y_{n}))=o(x_{n}).$

Since $y_{n}\geqslant\delta_{1}x_{n}$, it follows from (2.2) that
$A(y_{n})B(y_{n})\geqslant\delta_{1}x_{n}+o(x_{n})$. It infers from (2.4) that

(2.5) $\displaystyle A(2y_{n})-A(y_{n})=o(A(y_{n}))\hskip
8.53581pt\mbox{or}\hskip 8.53581ptB(2y_{n})-B(y_{n})=o(B(y_{n})).$

Similarly, by considering the sets $A\cap[0,y_{n}]$,
$A\cap]z_{n},x_{n}-2y_{n}]$ and $A\cap]z_{n},x_{n}]$ we get

(2.6) $\displaystyle\hskip
17.07164ptA(z_{n})-A(x_{n}-2y_{n})=o(A(x_{n})-A(z_{n}))$
$\displaystyle\mbox{or}\hskip
8.53581ptB(z_{n})-B(x_{n}-2y_{n})=o(B(x_{n})-B(z_{n})).$

It follows from (2.2), (2.3) and the fact $A(x_{n})B(x_{n})=2x_{n}+o(x_{n})$
that

$\displaystyle A(x_{n})B(y_{n})+A(y_{n})B(x_{n})=2x_{n}+o(x_{n}).$

Then,

$\displaystyle\frac{A(x_{n})B(y_{n})+A(y_{n})B(x_{n})}{A(x_{n})B(x_{n})}=\frac{B(y_{n})}{B(x_{n})}+\frac{A(y_{n})}{A(x_{n})}=1+o(1).$

Take $y_{n}=\frac{x_{n}}{2}$. Let
$\alpha_{n}=\frac{A(\frac{x_{n}}{2})}{A(x_{n})}$ and
$\beta_{n}=\frac{B(\frac{x_{n}}{2})}{B(x_{n})}$. Clearly,
$\alpha_{n}\beta_{n}=0.25+o(1)$ and $\alpha_{n}+\beta_{n}=1+o(1)$, that is
$\alpha_{n}=0.5+o(1)$ and $\beta_{n}=0.5+o(1)$. Hence

(2.7) $\displaystyle A(\frac{x_{n}}{2})=(0.5+o(1))A(x_{n})\hskip
8.53581pt\mbox{and}\hskip 8.53581ptB(\frac{x_{n}}{2})=(0.5+o(1))B(x_{n}).$

Let us suppose that

(2.8) $\displaystyle
A(\frac{x_{n}}{2})-A(\frac{x_{n}}{4})=o(A(\frac{x_{n}}{2})).$

We will prove by induction on $k$ that

(2.9) $\displaystyle
A(\frac{x_{n}}{2})-A(\frac{x_{n}}{2^{k}+1})=o(A(\frac{x_{n}}{2})).$

for every positive integer $k$.

It follows from (2.8) that
$A(\frac{x_{n}}{2})-A(\frac{x_{n}}{3})=o(A(\frac{x_{n}}{2}))$, thus (2.9)
holds for $k=1$. Suppose that

$\displaystyle
A(\frac{x_{n}}{2})-A(\frac{x_{n}}{2^{k}+1})=o(A(\frac{x_{n}}{2})).$

Then

$\displaystyle A(\frac{x_{n}}{2^{k}+1})=(1+o(1))A(\frac{x_{n}}{2}).$

Since

$\displaystyle[0,\frac{x_{n}}{2^{k}+1}]\subseteq[0,2\frac{x_{n}}{2^{k+1}+1}]\subseteq[0,\frac{x_{n}}{2}],$

we have

(2.10) $\displaystyle A(2\frac{x_{n}}{2^{k+1}+1})=(1+o(1))A(\frac{x_{n}}{2}).$

Thus,

(2.11) $\displaystyle
A(2\frac{x_{n}}{2^{k+1}+1})=(1+o(1))A(\frac{x_{n}}{2^{k}+1}).$

Take $y_{n}=\frac{x_{n}}{2^{k+1}+1}$ in (2.5), then

(2.12) $\displaystyle\hskip
17.07164ptA(2\frac{x_{n}}{2^{k+1}+1})-A(\frac{x_{n}}{2^{k+1}+1})=o(A(\frac{x_{n}}{2^{k+1}+1}))$
$\displaystyle\mbox{or}\hskip
5.69054ptB(2\frac{x_{n}}{2^{k+1}+1})-B(\frac{x_{n}}{2^{k+1}+1})=o(B(\frac{x_{n}}{2^{k+1}+1})).$

Assume that
$B(2\frac{x_{n}}{2^{k+1}+1})-B(\frac{x_{n}}{2^{k+1}+1})=o(B(\frac{x_{n}}{2^{k+1}+1}))$.
Then

$\displaystyle
B(2\frac{x_{n}}{2^{k+1}+1})-B(\frac{x_{n}}{2^{k}+1})=o(B(\frac{x_{n}}{2^{k}+1}))\hskip
8.53581pt\mbox{namely,}\hskip
8.53581ptB(2\frac{x_{n}}{2^{k+1}+1})=(1+o(1))B(\frac{x_{n}}{2^{k}+1}).$

It follows from (2.2) and (2.11) that

$(1+o(1))2\frac{x_{n}}{2^{k+1}+1}=A(2\frac{x_{n}}{2^{k+1}+1})B(2\frac{x_{n}}{2^{k+1}+1})=(1+o(1))A(\frac{x_{n}}{2^{k}+1})B(\frac{x_{n}}{2^{k}+1})=(1+o(1))\frac{x_{n}}{2^{k}+1},$

a contradiction. Then we could deduce from (2.12) that

$\displaystyle
A(2\frac{x_{n}}{2^{k+1}+1})-A(\frac{x_{n}}{2^{k+1}+1})=o(A(\frac{x_{n}}{2^{k+1}+1})).$

It follows from (2.10) that

$A(\frac{x_{n}}{2})-A(\frac{x_{n}}{2^{k+1}+1})=o(A(\frac{x_{n}}{2})),$

which completes the induction. Thus, (2.9) follows.

If (2.9) holds, then $A(\delta x_{n})=(1+o(1))A(\frac{x_{n}}{2})$ for every
$0<\delta\leqslant\frac{1}{2}$. We will show that: if
$A(\delta_{2}x_{n})=(1+o(1))A(\frac{x_{n}}{2})$ for every
$0<\delta_{2}\leqslant\frac{1}{2}$ and $A(Cx_{n})=(1+o(1))A(\frac{x_{n}}{2})$
for some $C$ with $0<C<1$, then $B(cx_{n})=(c+o(1))B(x_{n})$ for every
$0<c\leqslant C$. Let $0<\delta<c$. Clearly, by (2.1) we know that

$A(cx_{n})B(cx_{n})\geqslant cx_{n}-o(x_{n}).$

On the other hand,

$\displaystyle A(cx_{n})B(cx_{n})$ $\displaystyle=$
$\displaystyle(A(cx_{n})-A(\delta x_{n}))B(cx_{n})+A(\delta x_{n})B(cx_{n})$
$\displaystyle=$ $\displaystyle
o(A(\frac{x_{n}}{2}))B(cx_{n})+|\\{m:m=a+b,a\leqslant\delta x_{n},a\in
A,b\leqslant cx_{n},b\in B\\}|$ $\displaystyle\leqslant$
$\displaystyle(c+\delta+o(1))x_{n}.$

Since $\delta$ can be arbitrary small, we have
$A(cx_{n})B(cx_{n})=(c+o(1))x_{n}$. Then we could deduce from (2.2) (choosing
$y=\frac{x_{n}}{2}$) and (2.7) that

$A(cx_{n})B(cx_{n})=(c+o(1))x_{n}=(2c+o(1))A(\frac{x_{n}}{2})B(\frac{x_{n}}{2})=(c+o(1))A(cx_{n})B(x_{n}).$

It follows that $B(cx_{n})=(c+o(1))B(x_{n})$ for any $c$ with $0<c\leqslant
C$. Since $A(\frac{x_{n}}{2})=(1+o(1))A(\frac{x_{n}}{2})$, we have
$B(cx_{n})=(c+o(1))B(x_{n})$ for any $c$ with $0<c\leqslant 0.5$.

Next, we will prove that

(2.13) $\displaystyle
A(x_{n}-\frac{x_{n}}{2^{k}+1})=(1+o(1))A(\frac{x_{n}}{2}).$

We argue by induction on $k$. Taking $y=\frac{x_{n}}{3}$ in (2.6) we get

(2.14) $\displaystyle\hskip
17.07164ptA(x_{n}-\frac{x_{n}}{3})-A(x_{n}-2\frac{x_{n}}{3})=o(A(x_{n})-A(\frac{2x_{n}}{3}))$
$\displaystyle\mbox{or}\hskip
5.69054ptB(x_{n}-\frac{x_{n}}{3})-B(x_{n}-2\frac{x_{n}}{3})=o(B(x_{n})-B(\frac{2x_{n}}{3})).$

If $B(\frac{2x_{n}}{3})-B(\frac{x_{n}}{3})=o(B(x_{n})-B(\frac{2x_{n}}{3}))$,
then

$\displaystyle
B(\frac{x_{n}}{2})-B(\frac{x_{n}}{3})=o(B(x_{n}))=o(B(\frac{x_{n}}{2})).$

Hence $B(\frac{x_{n}}{3})=(1+o(1))B(\frac{x_{n}}{2})$. But
$B(\frac{x_{n}}{3})=(\frac{1}{3}+o(1))B(x_{n})$ and
$B(\frac{x_{n}}{2})=(\frac{1}{2}+o(1))B(x_{n})$, a contradiction. Then we
could deduce from (2.14) that

$\displaystyle
A(\frac{2x_{n}}{3})-A(\frac{x_{n}}{3})=o(A(x_{n})-A(\frac{2x_{n}}{3}))=o(A(\frac{x_{n}}{2})).$

It follows that $A(\frac{2x_{n}}{3})=(1+o(1))A(\frac{x_{n}}{2})$, thus (2.13)
holds for $k=1$. Suppose that

(2.15) $\displaystyle
A(x_{n}-\frac{x_{n}}{2^{k}+1})=(1+o(1))A(\frac{x_{n}}{2}).$

Noting that

$\displaystyle\frac{x_{n}}{2}<x_{n}-2\frac{x_{n}}{2^{k+1}+1}<x_{n}-\frac{x_{n}}{2^{k}+1},$

we know that $A(x_{n}-2\frac{x_{n}}{2^{k+1}+1})=(1+o(1))A(\frac{x_{n}}{2})$.
Taking $y=\frac{x_{n}}{2^{k+1}+1}$ in (2.6) we get

(2.16) $\displaystyle\hskip
17.07164ptA(x_{n}-\frac{x_{n}}{2^{k+1}+1})-A(x_{n}-2\frac{x_{n}}{2^{k+1}+1})=o(A(x_{n})-A(x_{n}-\frac{x_{n}}{2^{k+1}+1}))$
$\displaystyle\mbox{or}\hskip
5.69054ptB(x_{n}-\frac{x_{n}}{2^{k+1}+1})-B(x_{n}-2\frac{x_{n}}{2^{k+1}})=o(B(x_{n})-B(\frac{x_{n}}{2^{k+1}+1})).$

If
$B(x_{n}-\frac{x_{n}}{2^{k+1}+1})-B(x_{n}-2\frac{x_{n}}{2^{k+1}+1}))=o(B(x_{n})-B(x_{n}-\frac{x_{n}}{2^{k+1}+1}))$,
then

$\displaystyle
B(x_{n}-\frac{x_{n}}{2^{k}+1})-B(x_{n}-2\frac{x_{n}}{2^{k+1}+1})=o(B(x_{n})).$

Hence

$\displaystyle(\frac{1}{2(2^{k}+1)(2^{k+1}+1)}+o(1))x_{n}$
$\displaystyle\leqslant$ $\displaystyle|\\{m:m=a+b,a\in A,b\in
B,x_{n}-\frac{x_{n}}{2^{k}+1}+\frac{1}{2(2^{k}+1)(2^{k+1}+1)}x_{n}\leqslant
m\leqslant x_{n}-2\frac{x_{n}}{2^{k+1}+1}\\}|$ $\displaystyle\leqslant$
$\displaystyle|\\{m:m=a+b,a\in
A,a\leqslant\frac{x_{n}}{2(2^{k}+1)(2^{k+1}+1)},$ $\displaystyle
x_{n}-\frac{x_{n}}{2^{k}+1}+\frac{x_{n}}{2(2^{k}+1)(2^{k+1}+1)}\leqslant
m\leqslant x_{n}-2\frac{x_{n}}{2^{k}+1}\\}|$ $\displaystyle+|\\{m:m=a+b,a\in
A,a>\frac{x_{n}}{2(2^{k}+1)(2^{k+1}+1)},$ $\displaystyle
x_{n}-\frac{x_{n}}{2^{k}+1}+\frac{1}{2(2^{k}+1)(2^{k+1}+1)}x_{n}\leqslant
m\leqslant x_{n}-2\frac{x_{n}}{2^{k}+1}\\}|$ $\displaystyle\leqslant$
$\displaystyle
A(\frac{x_{n}}{2(2^{k}+1)(2^{k+1}+1)})(B(x_{n}-\frac{x_{n}}{2^{k}+1})-B(x_{n}-2\frac{x_{n}}{2^{k+1}+1}))$
$\displaystyle+(A(x_{n}-\frac{x_{n}}{2^{k}+1})-A(\frac{x_{n}}{2(2^{k}+1)(2^{k+1}+1)}))B(x_{n})$
$\displaystyle\leqslant$ $\displaystyle
A(\frac{x_{n}}{2}))o(B(x_{n}))+o(A(\frac{x_{n}}{2}))B(x_{n})=o(x_{n}),$

a contradiction. Then we could deduce from (2.16) that

$\displaystyle
A(x_{n}-\frac{x_{n}}{2^{k+1}+1})-A(x_{n}-2\frac{x_{n}}{2^{k+1}+1})=o(A(x_{n})-A(x_{n}-\frac{x_{n}}{2^{k+1}+1}))=o(A(x_{n}))=o(A(\frac{x_{n}}{2})).$

It follows that

$\displaystyle
A(x_{n}-\frac{x_{n}}{2^{k+1}+1})-A(x_{n}-\frac{x_{n}}{2^{k}+1})=o(A(\frac{x_{n}}{2})).$

Hence by (2.15) we have

$A(x_{n}-\frac{x_{n}}{2^{k+1}+1})=(1+o(1))A(\frac{x_{n}}{2}).$

Since $A((1-\delta)x_{n})=(1+o(1))A(\frac{x_{n}}{2})$ for any $0<\delta<0.5$
we have $B(cx_{n})=(c+o(1))B(x_{n})$ for every $0<c<1$.∎

We will return to the proof of Theorem 1.1 (i). By Proposition 2, we know
that, in any case,

$\displaystyle\frac{A(y)B(y)}{y}\rightarrow 1\hskip 8.53581pt\mbox{as}\hskip
8.53581ptn\rightarrow\infty.$

Theorem 1.2 (i) follows.

Now we will prove Theorem 1.2 (ii). We know that
$A(x_{n})B(x_{n})=(2+o(1))x_{n}$ and

$|\\{m:x_{n}\leqslant m\leqslant 2x_{n},m=a+b,a\in A,b\in B,a>x_{n}\hskip
8.53581pt\mbox{or}\hskip 8.53581ptb>x_{n}\\}|=o(x_{n}).$

Assume the contrary, for some $c_{3}x_{n}\leqslant v_{n}\leqslant c_{4}x_{n}$,
we have $A(v_{n})B(v_{n})>(2+\varepsilon)x_{n}$ with $\varepsilon>0$ for
infinitely many $n$. Then, $A(v_{n})>(1+\varepsilon^{\prime})A(x_{n})$ or
$B(v_{n})>(1+\varepsilon^{\prime})x_{n}$ for some $\varepsilon^{\prime}>0$.
Let us suppose that $A(v_{n})>(1+\varepsilon^{\prime})A(x_{n})$, that is
$A(v_{n})-A(x_{n})\geqslant\varepsilon A(x_{n})$. We proved in (i) that
$B((2-c_{4})x_{n})=(0.5+o(1))B(x_{n})$ or
$B((2-c_{4})x_{n})=(2-c_{4}+o(1))B(x_{n})$. It follows that
$B((2-c_{4})x_{n})\gg B(x_{n})$. Hence

$\displaystyle o(x_{n})$ $\displaystyle=$ $\displaystyle|\\{m:x_{n}\leqslant
m\leqslant 2x_{n},m=a+b,a\in A,b\in B,a>x_{n}\hskip 8.53581pt\mbox{or}\hskip
8.53581ptb>x_{n}\\}|$ $\displaystyle\geqslant$
$\displaystyle(B(2-c_{4})x_{n})(A(v_{n})-A(x_{n}))\gg
A(x_{n})B(x_{n})=(2+o(1))x_{n},$

a contradiction. Theorem 1.2 (ii) follows.

Finally we will prove Theorem 1.2 (iii). By Proposition 1, with the exception
of at most $\varepsilon x_{n}$ numbers, all numbers in $[0,2x_{n}]$ can be
written as $a_{i}+b_{j}$ with $a_{i}\leqslant x_{n},b_{j}\leqslant x_{n}$. For
$i=1,2,3,4$, denote the number of elements of $A$ and $B$ in the intervals
$(\frac{(i-1)x_{n}}{2},\frac{ix_{n}}{2}]$ by $A_{i}$ and $B_{i}$,
respectively. Clearly,

$\displaystyle A_{1}B_{1}+A_{1}B_{2}+A_{2}B_{1}+A_{2}B_{2}\leqslant 2x_{n}.$

Noting that the sum in
$A_{1}B_{3}+A_{1}B_{4}+A_{2}B_{3}+A_{2}B_{4}+A_{3}B_{1}+A_{3}B_{2}+A_{3}B_{3}+A_{4}B_{1}+A_{4}B_{2}$
belongs to $[x_{n},3x_{n}]$, we know that

$\displaystyle
A_{1}B_{3}+A_{1}B_{4}+A_{2}B_{3}+A_{2}B_{4}+A_{3}B_{1}+A_{3}B_{2}+A_{3}B_{3}+A_{4}B_{1}+A_{4}B_{2}\leqslant
x_{n}+\varepsilon x_{n}.$

Considering the difference, also by the definition of _disjoint set_ , with
the exception of at most $\varepsilon x_{n}$ numbers, all numbers in
$[-x_{n},x_{n}]$ can be written as $a_{i}-b_{j}$ with $a_{i}\leqslant
x_{n},b_{j}\leqslant x_{n}$. Thus,

$\displaystyle A_{3}B_{4}+A_{4}B_{3}+A_{4}B_{4}\leqslant\varepsilon x_{n}.$

Hence

$\displaystyle
A(2x_{n})B(2x_{n})=(A_{1}+A_{2}+A_{3}+A_{4})(B_{1}+B_{3}+B_{3}+B_{4})\leqslant
3x_{n}+2\varepsilon x_{n}.$

It follows that

$\displaystyle\limsup_{k\rightarrow\infty}\frac{A(2x_{n})B(2x_{n})}{2x_{n}}\leqslant\frac{3}{2}.$

On the other hand, let

(2.17) $\displaystyle
A=\\{\epsilon_{0}+\epsilon_{2}m_{1}m_{2}+\cdots+\epsilon_{2k-2}m_{1}\cdots
m_{2k-2},\epsilon_{2i}=0,1,\cdots,m_{2i+1}-1\\},$ $\displaystyle
B=\\{\epsilon_{1}m_{1}+\epsilon_{3}m_{1}m_{2}m_{3}+\cdots+\epsilon_{2k-1}m_{1}\cdots
m_{2k-1},\epsilon_{2i-1}=0,1,\cdots,m_{2i}-1\\},$

where $m_{1},m_{2},\cdots$ are integers no less than two. Then $A,B$ are
disjoint sets. Let

$\displaystyle
y_{k}=(m_{1}-1)+(m_{3}-1)m_{1}m_{2}+\cdots+(m_{2k-1}-1)m_{1}\cdots
m_{2k-2}+m_{1}m_{2}\cdots m_{2k}.$

Then we have $A(y_{n})=2m_{1}m_{3}\cdots m_{2n-1}$ and
$B(y_{n})=m_{2}m_{4}\cdots m_{2n}$. Let $m_{i+1}\geqslant im_{i}$ for every
positive integer $i$. Then

$\displaystyle\lim_{k\rightarrow\infty}\frac{A(y_{k})B(y_{k})}{y_{k}}=2.$

Also, $A(2y_{n})=3m_{1}m_{3}\cdots m_{2n-1}$, $B(2y_{n})=m_{2}m_{4}\cdots
m_{2n}$ and then

$\displaystyle\lim_{k\rightarrow\infty}\frac{A(2y_{n})B(2y_{n})}{2y_{n}}=\frac{3}{2}.$

Theorem 1.3 (iii) follows.

This completes the proof of Theorem 1.1. $\Box$

Proof of Theorem 1.2. We will firstly prove Theorem 1.2 (i). Assume the
contrary, (1.2) does not hold. Then there exists a positive constant $c$ such
that $\frac{x_{n+1}}{x_{n}}\leqslant c$ for infinitely many positive integers
$n$. Since $x_{i+1}\geqslant 2x_{i}$ for all $i$, there exist infinitely many
positive integers $n$ such that

$\displaystyle\frac{1}{c}x_{n+1}\leqslant
x_{n}\leqslant\frac{1}{2}x_{n+1},\hskip 11.38109pt\mbox{namely},\hskip
11.38109pt\frac{2}{c}x_{n+1}\leqslant 2x_{n}\leqslant x_{n+1}.$

It infers from

$\displaystyle\lim_{n\rightarrow\infty}\frac{A(x_{n+1})B(x_{n+1})}{x_{n+1}}=2$

and Theorem 1.1 (i) that

$\displaystyle\lim_{n\rightarrow\infty}\frac{A(x_{n})B(x_{n})}{x_{n}}=1,$

a contradiction with (1.1).

Now we will prove Theorem 1.2 (ii). We introduce the following proposition.

Proposition 3. Define disjoint sets $A$ and $B$ as in (2.17). Write

$\displaystyle
N_{k}=(m_{1}-1)+(m_{3}-1)m_{1}m_{2}+\cdots+(m_{2k-1}-1)m_{1}\cdots m_{2k-2}.$

Then, for $x$ with $N_{k}+m_{1}m_{2}\cdots m_{2k}\leqslant x\leqslant
2m_{1}m_{2}\cdots m_{2k-1}+m_{1}m_{2}\cdots m_{2k}$, we have

$\displaystyle\frac{A(x)B(x)}{x}\geqslant\frac{2}{1+\frac{2}{m_{2k}}}.$

We now return to the proof of Theorem 1.2 (ii). Suppose we have already found
$m_{1},m_{2},\cdots,m_{2k-2}$ such that

$\displaystyle N_{k-1}+m_{1}m_{2}\cdots m_{2k-2}\leqslant x_{i}\leqslant
2m_{1}m_{2}\cdots m_{2k-3}+m_{1}m_{2}\cdots m_{2k-2}.$

Now, for $x_{i+1}$, we need to find $m_{2k-1}$ and $m_{2k}$ such that

$\displaystyle N_{k}+m_{1}m_{2}\cdots m_{2k}\leqslant x_{i+1}\leqslant
2m_{1}m_{2}\cdots m_{2k-1}+m_{1}m_{2}\cdots m_{2k}.$

Let $m_{2k-1}=2$. Since the length of the interval
$[\frac{x_{i+1}-2m_{1}m_{2}\cdots m_{2k-1}}{m_{1}m_{2}\cdots
m_{2k-1}},\frac{x_{i+1}-N_{k}}{m_{1}m_{2}\cdots m_{2k-1}}]$ is larger than 1,
there exists an integer (write it as $m_{2k}$) such that

(2.18) $\displaystyle\frac{x_{i+1}-2m_{1}m_{2}\cdots
m_{2k-1}}{m_{1}m_{2}\cdots m_{2k-1}}\leqslant
m_{2k}\leqslant\frac{x_{i+1}-N_{k}}{m_{1}m_{2}\cdots m_{2k-1}}.$

Namely,

$\displaystyle N_{k}+m_{1}m_{2}\cdots m_{2k}\leqslant x_{i+1}\leqslant
2m_{1}m_{2}\cdots m_{2k-1}+m_{1}m_{2}\cdots m_{2k}.$

It infers from Proposition 3 that

$\displaystyle\frac{A(x_{i+1})B(x_{i+1})}{x_{i+1}}\geqslant\frac{2}{1+\frac{2}{m_{2k}}}.$

By (1.2) and (2.18) we know that $m_{2k}\rightarrow\infty$. Thus,

$\displaystyle\lim_{n\rightarrow\infty}\frac{A(x_{n})B(x_{n})}{x_{n}}=2.$

This completes the proof of Theorem 1.2. $\Box$

The main idea in the proof of Theorem 1.3 is from [2, Theorem 3.3]. We give
the details for the sake of completeness.

Proof of Theorem 1.3. If $IN=0$, then (1.3) follows from the fact that
$SP\leqslant 2$. Now we only need to consider the case $IN>0$. For any $\eta$
with $0<\eta<IN$, we have $A(x)\geqslant(IN-\eta)\sqrt{x}$ and
$B(x)\geqslant(IN-\eta)\sqrt{x}$ for large enough $x$. It follows from
$A(x)B(x)\leqslant 2x$ that

(2.19) $\displaystyle B(x)\leqslant\frac{2}{IN-\eta}\sqrt{x}\hskip
8.53581pt\mbox{and}\hskip
8.53581ptA(x)\leqslant\frac{2}{IN-\eta}\sqrt{x}\hskip 8.53581pt\mbox{for
large}\hskip 8.53581ptx.$

Let $\varepsilon$ be small enough. Take an $x$ such that

$\displaystyle A(2x)B(2x)\geqslant(2SP-\varepsilon)x.$

Thus, with the exception of at most $(4-2SP+\varepsilon)x$ numbers, all
numbers in $[0,4x]$ can be written as $a_{i}+b_{j}$ with $a_{i}\leqslant
2x,b_{j}\leqslant 2x$. Let

$A_{1}=|A\cap[0,x]|,A_{2}=|A\cap(x,2x]|,B_{1}=|B\cap[0,x]|,B_{2}=|B\cap(x,2x]|.$

Hence

(2.20) $\displaystyle A_{1}B_{1}+A_{2}B_{2}\geqslant(2SP-2-\varepsilon)x$

and also

$\displaystyle A_{1}B_{1}\geqslant(2SP-3-\varepsilon)x,\hskip
8.53581ptA_{2}B_{2}\geqslant(2SP-3-\varepsilon)x.$

It follows from $A_{1}B_{1}+A_{2}B_{2}\leqslant 2x$ that

$\displaystyle A_{1}B_{1}\leqslant(5-2SP+\varepsilon)x,\hskip
8.53581ptA_{2}B_{2}\leqslant(5-2SP+\varepsilon)x.$

Take

$d=\frac{(IN-\eta)^{4}}{16}.$

Then $0<d<1$. Let

$A^{\prime}=|A\cap[dx,x]|,A^{*}=|A\cap(x,(1+d)x]|,B^{\prime}=|B\cap[dx,x]|,B^{*}=|B\cap(x,(1+d)x]|.$

Considering the difference, by (2.20) we know that at most
$(4-2SP+\varepsilon)x$ other pairs satisfy $|a_{i}-b_{j}|\leqslant x$. Thus,

(2.21) $\displaystyle
A^{\prime}B^{*}+A^{*}B^{\prime}\leqslant(4-2SP+\varepsilon)x.$

By (2.19) we have

$A^{\prime}=A(x)-A(dx)\geqslant(IN-\eta)\sqrt{x}-\frac{2}{IN-\eta}\sqrt{dx}=\frac{IN-\eta}{2}\sqrt{x},$

(similarly, $B^{\prime}>\frac{IN-\eta}{2}\sqrt{x}$.) It infers from (2.21)
that

$A^{*}+B^{*}\leqslant\frac{2(4-2SP+\varepsilon)}{IN-\eta}\sqrt{x}.$

Write $M=\max\\{A^{*},B^{*}\\}$. Then

$M\leqslant\frac{2(4-2SP+\varepsilon)}{IN-\eta}\sqrt{x}.$

By (2),

$A((1+d)x)B((1+d)x)\geqslant(1+d)x-(4-2SP+\varepsilon)x=(2SP+d-3-\varepsilon)x$

and

$A((1+d)x)B((1+d)x)=(A_{1}+A^{*})(B_{1}+B^{*}),$

we have

$A_{1}B^{*}+A^{*}B_{1}+A^{*}B^{*}>(4SP+d-8-2\varepsilon)x.$

On the other hand,

$A_{1}B^{*}+A^{*}B_{1}+A^{*}B^{*}\leqslant
M(A_{1}+B_{1})+M^{2}<\frac{8\sqrt{x}}{IN-\eta}M\leqslant\frac{8}{IN-\eta}\frac{2(4-2SP+\varepsilon)}{IN-\eta}x.$

Thus,

$4SP+d-8-2\varepsilon\leqslant\frac{16(4-2SP+\varepsilon)}{(IN-\eta)^{2}}.$

As $\eta\rightarrow 0$ and $\varepsilon\rightarrow 0$, we have

$\frac{IN^{6}}{IN^{2}+8}\leqslant 64(2-SP).$

(1.3) follows.

This completes the proof of Theorem 1.3. $\Box$

##  3\. Acknowledgments

The first author sincerely thanks Prof. Yong-Gao Chen for his kind help and
concern all the time.

## References

  * [1] P. Erdős, R. Freud, On disjoint sets of differences, J. Number Theory 18 (1984), 99-109.
  * [2] P. Erdős, R.L. Graham, Old and new problems and results in combinatorial number theory, Monographies No. 28, de L’Enseignement Mathématique, Geneva, 1980.