# Linear functionals and $\Delta$\- coherent pairs of the second kind

Diego Dominici Research Institute for Symbolic Computation, Johannes Kepler
University Linz, Altenberger Straße 69, 4040 Linz, Austria. e-mail:
<EMAIL_ADDRESS>of Mathematics, State University of New
York at New Paltz, 1 Hawk Dr., New Paltz, NY 12561-2443, USA. Francisco
Marcellán Departamento de Matemáticas, Universidad Carlos III de Madrid,
Escuela Politécnica Superior, Av. Universidad 30, 28911 Leganés, Spain.
e-mail<EMAIL_ADDRESS>
###### Abstract

We classify all the _$\Delta$ -_coherent pairs of measures of the second kind
on the real line. We obtain $5$ cases, corresponding to all the families of
discrete semiclassical orthogonal polynomials of class $s\leq 1.$

_Keywords_ : Discrete orthogonal polynomials, discrete semiclassical
functionals, discrete Sobolev inner products, coherent pairs of discrete
measures, coherent pairs of second kind for discrete measures.

_2020 Mathematical Subject Classification_ : 42C05 (primary), 33C45, 46E39
(secondary).

##  1 Introduction

The aim of this contribution is to provide a characterization of all pairs of
discrete measures $\\{\rho_{0},\rho_{1}\\}$ supported on the real line such
that the corresponding sequences of _monic orthogonal polynomials_ (MOPs for
short) $\\{P_{n}(\rho_{0};x)\\}_{n\geq 0}$ and $\\{P_{n}(\rho_{1};x)\\}_{n\geq
0}$ satisfy

$P_{n}(\rho_{1};x)-\tau_{n}P_{n-1}(\rho_{1};x)=\frac{1}{n+1}\Delta
P_{n+1}(\rho_{0};x),\quad n\geq 1,$ (1)

where $\tau_{n}\neq 0$ for $n\geq 1$. We will solve this problem by dealing
with a more general problem concerning the characterization of pairs of quasi-
definite linear functionals (with complex moments) such that the corresponding
sequences of MOPs satisfy (1).

As we show in this contribution, we get special pairs of linear functionals
(in particular, positive definite linear functionals associated with positive
measures supported on infinite subsets of the real line) and the corresponding
associated sequences of orthogonal polynomials have interesting properties.
These pairs are _discrete semiclassical linear functionals_ of class at most
$s=1$ which have been studied in [8] and [9] in the framework of a
classification problem based on a hierarchy structure.

On the other hand, these sequences of orthogonal polynomials are related to
some problems in approximation theory. More precisely, the analysis of Fourier
expansions in terms of sequences of polynomials orthogonal with respect to the
Sobolev inner product

$\langle
f,g\rangle_{\mathfrak{S}}=\sum_{x=0}^{\infty}f(x)g(x)\rho_{0}(x)+\lambda\sum_{x=0}^{\infty}\Delta
f(x)\Delta g(x)\rho_{1}(x),$ (2)

defined by the pair of discrete measures $\\{\rho_{0},\rho_{1}\\}$ of class
$s\geq 1$. It turns out that the monic Sobolev orthogonal polynomials
$S_{n}(\rho_{0},\rho_{1};x)$ with respect to the inner product
$\langle\,,\,\rangle_{\mathfrak{S}}$ satisfy the connection formulas

$\begin{array}[c]{l}S_{n+1}(\rho_{0},\rho_{1};x)-\gamma_{n}S_{n}(\rho_{0},\rho_{1};x)=P_{n+1}(\rho_{0};x),\\\\[6.45831pt]
\Delta S_{n+1}(\rho_{0},\rho_{1};x)-\gamma_{n}\Delta
S_{n}(\rho_{0},\rho_{1};x)=(n+1)\left[P_{n}(\rho_{1};x)-\tau_{n}P_{n-1}(\rho_{1};x)\right],\end{array}\quad
n\geq 1,$ (3)

with $S_{1}(\rho_{0},\rho_{1};x)=P_{1}(\rho_{0};x)$. The above connection
formulas between $\\{S_{n}(\rho_{0},\rho_{1};x)\\}_{n\geq 0}$ and the
sequences of MOPs $\\{P_{n}(\rho_{0};x)\\}_{n\geq 0}$ and
$\\{P_{n}(\rho_{1};x)\\}_{n\geq 0}$ yield a nice approach to the study of
algebraic and analytic properties of the polynomials
$S_{n}(\rho_{0},\rho_{1};x)$.

Based on historical information given below we will refer to pairs of measures
$\\{\rho_{0},\rho_{1}\\}$ satisfying property (1) as _$\Delta$ -coherent pairs
of measures of the second kind on the real line_. The concept of coherence
between a pair of probability measures $\\{\nu_{0},\nu_{1}\\}$ supported on
the real line was introduced in [13]. Indeed, a pair of probability measures
supported on the real line is said to be a coherent pair if the corresponding
sequences of MOPs $\\{P_{n}(\nu_{0};x)\\}_{n\geq 0}$ and
$\\{P_{n}(\nu_{1};x)\\}_{n\geq 0}$, satisfy

$P_{n}(\nu_{1};x)=\frac{1}{n+1}\left[P_{n+1}^{\prime}(\nu_{0};x)-\rho_{n}P_{n}^{\prime}(\nu_{0};x)\right],\quad\rho_{n}\neq
0,\quad n\geq 1.$ (4)

It was shown in this case that the sequence of monic orthogonal polynomials
with respect to the inner product

$\langle f,g\rangle_{S}=\int f(x)g(x)d\nu_{0}+\lambda\int
f^{\prime}(x)g^{\prime}(x)d\nu_{1},$ (5)

satisfies the connection formulas

$\begin{array}[c]{l}S_{n+1}(\nu_{0},\nu_{1};x)-\gamma_{n}S_{n}(\nu_{0},\nu_{1};x)=P_{n+1}(\nu_{0};x)-\rho_{n}P_{n}(\nu_{0};x),\\\\[6.45831pt]
S_{n+1}^{\prime}(\nu_{0},\nu_{1};x)-\gamma_{n}S_{n}^{\prime}(\nu_{0},\nu_{1};x)=(n+1)P_{n}(\nu_{1};x),\end{array}\quad
n\geq 1.$ (6)

These formulas are very useful in the study of analytic properties of the
corresponding Sobolev orthogonal polynomials. For more information about
polynomials orthogonal with respect to Sobolev inner products see the updated
survey [19].

The motivation in [13] for introducing such pairs of measures was their
applications in the framework of Fourier expansions of functions with respect
to the Sobolev inner product $\langle\,,\,\rangle_{\mathfrak{S}}$. A
particular case of such Fourier series expansions based on Legendre-Sobolev
orthogonal polynomials had already been considered in [14], where some
numerical tests comparing these Legendre-Sobolev Fourier series expansions and
the ordinary Legendre Fourier series expansions are presented.

The pairs of probability measures supported on the real line with the property
that the corresponding sequences of MOPs satisfy (4) were completely
determined in 1997 by H. G. Meijer [20]. He showed that if $(\nu_{0},\nu_{1})$
is a coherent pair of measures on the real line, then one of the measures must
be classical (either Jacobi or Laguerre) and the other one a rational
perturbation of it. Note that the condition for classical linear functionals
to be part of a coherent pair was deduced in [17].

Thus, what was proved in [20] is more general than what is stated above. The
starting point of the classification in [20] are certain functional relations
established in [16] with respect to pairs of quasi-definite linear functionals
such that the corresponding sequences of MOPs satisfy a relation like (4).
Note that if the coherence property (4) holds, then you get the connection
formulas in (6). According to [20], (6) holds when one of the measures in
$\\{\nu_{0},\nu_{1}\\}$ is a classical one.

An extension of the concept of coherence, known in the literature as
$(1,1)$-coherence, is defined in terms of the corresponding MOPs as follows
(see [7])

$P_{n}(\nu_{1};x)-\tau_{n}P_{n-1}(\nu_{1};x)=\frac{1}{n+1}\left[P_{n+1}^{\prime}(\nu_{0};x)-\xi_{n}P_{n}^{\prime}(\nu_{0};x)\right],\quad\xi_{n},\tau_{n}\neq
0,\quad n\geq 1,\ \ $ (7)

In this case, the Sobolev orthogonal polynomials associated with the inner
product $\langle\,,\,\rangle_{\mathfrak{S}}$ in (5) satisfy the connection
formulas

$\begin{array}[c]{l}S_{n+1}(\nu_{0},\nu_{1};x)-\gamma_{n}S_{n}(\nu_{0},\nu_{1};x)=P_{n+1}(\nu_{0};x)-\xi_{n}P_{n}(\nu_{0};x),\\\\[6.45831pt]
S_{n+1}^{\prime}(\nu_{0},\nu_{1};x)-\gamma_{n}S_{n}^{\prime}(\nu_{0},\nu_{1};x)=(n+1)\left[P_{n}(\nu_{1};x)-\tau_{n}P_{n-1}(\nu_{1};x)\right],\end{array}\quad
n\geq 1.$ (8)

We would like to emphasize that the characterization of probability measures
satisfying the coherence property (7) is given in [7] assuming that
$\xi_{n},\tau_{n}\neq 0$ for $n\geq 1$. Therein you have semiclassical linear
functionals of class at most $1$. Its role in the study of the sequences of
orthogonal polynomials with respect to the Sobolev inner product defined by a
$(1,1)$ coherent pairs of measures has been emphasized in [12]. Notice that
when $\tau_{n}=0$ and $\xi_{n}\neq 0$ for $n\geq 1,$ we get the results on
coherent pairs presented in [20]. Thus, a natural question is to analyze the
case $\xi_{n}=0,$and $\tau_{n}\neq 0$ for $n\geq 0.$

In [24], the concept of _coherent pair of second kind_ is introduced. A pair
of probability measures $\\{\nu_{0},\nu_{1}\\}$ supported on the real line is
said to be a coherent pair of second kind if the corresponding sequences of
MOPs $\\{P_{n}(\nu_{0};x)\\}_{n\geq 0}$ and $\\{P_{n}(\nu_{1};x)\\}_{n\geq 0}$
satisfy

$\frac{1}{n+1}P_{n+1}^{\prime}(\nu_{0};x)=P_{n}(\nu_{1};x)-\tau_{n}P_{n-1}(\nu_{1};x)\quad
n\geq 1,$ (9)

where $\tau_{n}\neq 0$ for $n\geq 1$. The characterization of all pairs of
probability measures as well as the pairs of quasi-definite linear functionals
which are coherent pairs of second kind has been given in [24]. Some
illustrative examples were shown therein.

The concept of $\Delta$-coherent pair of linear functionals was introduced in
[1] as well as in [3]. Indeed, a pair of linear functionals
$\\{L_{0},L_{1}\\}$ it is said to be a $\Delta$-coherent pair if the
corresponding sequences of MOPs $\\{P_{n}^{(0)}(x)\\}_{n\geq 0}$ and
$\\{P_{n}^{(1)}(x)\\}_{n\geq 0}$ satisfy a discrete version of (4)

$P_{n}^{(1)}(x)=\frac{1}{n+1}\left[\Delta P_{n+1}^{(0)}(x)-\rho_{n}\Delta
P_{n}^{(0)}(x)\right],\quad\rho_{n}\neq 0,\quad n\geq 1.$ (10)

It was shown in this case that the sequence of monic polynomials $S_{n}(x)$
orthogonal with respect to the inner product

$\langle f,g\rangle_{\mathfrak{S}}=\langle L_{0},fg\rangle+\langle
L_{1},\Delta f\Delta g\rangle$

satisfies the connection formulas

$\begin{array}[c]{l}S_{n+1}(x)-\gamma_{n}S_{n}(x)=P_{n+1}^{(0)}(x)-\rho_{n}P_{n}^{(0)}(x),\\\\[6.45831pt]
\Delta S_{n+1}(x)-\gamma_{n}\Delta
S_{n}(x)=(n+1)P_{n}^{(1)}(x),\end{array}\quad n\geq 1.$ (11)

In [3], it was proved that one of them must be a $\Delta$-classical linear
functional. The corresponding companion linear functionals were described
therein. Notice that this inner product is a discretization of a Sobolev inner
product (5), i.e., $\nu_{0}$ and $\nu_{1}$ are discrete measures.

The paper is organized as follows. Section 2 summarizes the basic concepts
about linear functionals and orthogonal polynomials to be used in the sequel.
We emphasize a special family of linear functionals, the so called
$\Delta$_-semiclassical_ , which will play a central role along the
manuscript. In Section 3 we introduce the concept of $\Delta$-coherent pair of
the second kind for linear functionals and we give a characterization of them.
We must point out that both functionals in the pair turn out to be discrete
semiclassical functionals of class at most $1$. In Section 4 we classify all
the $\Delta$\- coherent pairs of the second kind. We show that the companions
of the discrete classical functionals (Charlier, Kravchuk, Meixner, and Hahn)
are discrete semiclassical of class $s=1$.

##  2 Preliminary material

Let $\mathbb{P}=\mathbb{C}\left[x\right]$ and $\mathbb{N}_{0}$ be the set of
nonnegative integers

$\mathbb{N}_{0}=\mathbb{N}\cup\left\\{0\right\\}=\left\\{0,1,2,\ldots\right\\}.$

We will denote by $\delta_{k,n}$ the _Kronecker delta_ , defined by

$\delta_{k,n}=\left\\{\begin{array}[c]{c}1,\quad k=n\\\ 0,\quad k\neq
n\end{array}\right.,\quad k,n\in\mathbb{N}_{0},$

and say that $\left\\{\Lambda_{n}\left(x\right)\right\\}_{n\geq
0}\subset\mathbb{P}$ is a _basis_ of $\mathbb{P}$ if
$\deg\left(\Lambda_{n}\right)=n.$

Suppose that $L:\mathbb{P}\rightarrow\mathbb{C}$ is a _linear functional,_
$\left\\{\Lambda_{n}\left(x\right)\right\\}_{n\geq 0}$ is a basis of
$\mathbb{P}$, and we choose a nonzero sequence $\left\\{h_{n}\right\\}_{n\geq
0}\subset\mathbb{C}$. If the system of linear equations

${\displaystyle\sum\limits_{i=0}^{n}}L\left[\Lambda_{k}\Lambda_{i}\right]c_{n,i}=h_{n}\delta_{k,n},\quad
0\leq k\leq n,$ (12)

has a unique solution $\left\\{c_{n,i}\right\\}_{0\leq i\leq n},$ then we can
define a polynomial $P_{n}\left(x\right)$ by

$P_{n}\left(x\right)={\displaystyle\sum\limits_{i=0}^{n}}c_{n,i}\Lambda_{i}\left(x\right),\quad
n\in\mathbb{N}_{0}.$

We say that $\left\\{P_{n}\left(x\right)\right\\}_{n\geq 0}$ is an _orthogonal
polynomial sequence_ with respect to the functional $L$. The system (12) can
be written as

$L\left[\Lambda_{k}P_{n}\right]=h_{n}\delta_{k,n},\quad 0\leq k\leq n,$

and using linearity we see that the sequence
$\left\\{P_{n}\left(x\right)\right\\}_{n\geq 0}$ satisfies the _orthogonality
conditions_

$L\left[P_{k}P_{n}\right]=h_{n}\delta_{k,n},\quad k,n\in\mathbb{N}_{0}.$ (13)

The linear functional $L$ is said to be _quasi-definite_ [6].

We define the multiplication of a linear functional by a polynomial $q(x)$ to
be the linear functional $qL$ such that

$\left(qL\right)\left[p\right]=L\left[qp\right],\quad p\in\mathbb{P},$ (14)

and the adjoint operator $\Delta^{\ast}$ of a linear functional by

$\left(\Delta^{\ast}L\right)\left[p\right]=-L\left[\Delta p\right],\quad
p\in\mathbb{P}.$ (15)

We say that $L$ is a _semiclassical functional_ with respect to the operator
$\Delta,$ ($\Delta-$semiclassical, in short) [18] if there exist polynomials
$\left(\phi,\psi\right)$ such that $L$ satisfies the _Pearson equation_

$\Delta^{\ast}\left(\phi L\right)+\psi L=0,$ (16)

where $\phi$ is monic and $\deg\left(\psi\right)\geq 1.$ Note that using (14)
and (15) we can rewrite the Pearson equation as

$L\left[\phi\Delta p\right]=L\left[\psi p\right],\quad p\in\mathbb{P}.\quad$
(17)

###### Lemma 1

If $f,g:\mathbb{Z}\rightarrow\mathbb{C},$ then we have the _summation by
parts_ formula

${\displaystyle\sum\limits_{x=a}^{b}}f\left(x\right)\Delta
g\left(x\right)=\left[f\left(x-1\right)g\left(x\right)\right]_{a}^{b+1}-{\displaystyle\sum\limits_{x=a}^{b}}g\left(x\right)\nabla
f\left(x\right),\quad a,b\in\mathbb{Z}.$ (18)

Proof. The formula follows from the telescoping sum

$\displaystyle{\displaystyle\sum\limits_{x=a}^{b}}\left[f\left(x\right)\Delta
g\left(x\right)+g\left(x\right)\nabla f\left(x\right)\right]$
$\displaystyle={\displaystyle\sum\limits_{x=a}^{b}}f\left(x\right)g\left(x+1\right)-g\left(x\right)f\left(x-1\right)$
$\displaystyle=f\left(b\right)g\left(b+1\right)-g\left(a\right)f\left(a-1\right).$

Using summation by parts, we can write an alternative form of the Pearson
equation (16).

###### Proposition 2

Let $L\in P^{\ast}$ be defined by

$L\left[p\right]={\displaystyle\sum\limits_{x=0}^{\infty}}p\left(x\right)\rho\left(x\right),\quad
p\in\mathbb{P},$

where $\rho\left(-1\right)=0$ and

$\underset{x\rightarrow\infty}{\lim}p\left(x\right)\rho\left(x\right)=0,\quad
p\in\mathbb{P}.$

Then, $L$ satisfies the Pearson equation (16) if and only if

$\nabla\left(\phi\rho\right)+\psi\rho=0.$ (19)

Proof. Since (16) is equivalent to (17), we can use (18) and conclude that $L$
satisfies (16) if and only if

${\displaystyle\sum\limits_{x=0}^{\infty}}\psi\left(x\right)p\left(x\right)\rho\left(x\right)=-{\displaystyle\sum\limits_{x=0}^{\infty}}p\left(x\right)\nabla\left(\phi\rho\right)\left(x\right),\quad
p\in\mathbb{P}.$

If the last equation holds for all $p\in\mathbb{P},$ then we must have

$\psi\rho=-\nabla\left(\phi\rho\right),$

and the result follows.

The _class_ of a discrete semiclassical linear functional $L$ is defined by

$s=\min\\{\max\left\\{\deg\left(\phi\right)-2,\
\deg\left(\psi\right)\\}-1\right\\},$ (20)

where the minimum is taken among all pairs of polynomials $\phi,\psi$ such
that the Pearson equation (16) holds for the linear functional $L.$
Functionals of class $s=0$ are called $\Delta$-classical (see [11], [15], and
[22] among others). $\Delta$-semiclassical linear functionals of class $s=1$
have been described in [8] and [9].

###### Remark 3

Let $\deg\left(\phi\right)=d_{1},$ $\deg\left(\psi\right)=d_{2}.$ If
$d_{1}=d_{2}+1=s+2,$ we will always assume the admissibility condition

$\psi_{d_{2}}\neq n-s,\quad n\in\mathbb{N}_{0},$ (21)

where $\psi_{d_{2}}$ is the leading coefficient of $\psi\left(x\right).$

We will denote by $\\{\varphi_{n}\left(x\right)\\}_{n\geq 0}$ the basis of
_falling factorial polynomials_ defined by $\varphi_{0}\left(x\right)=1$ and

$\varphi_{n}\left(x\right)={\displaystyle\prod\limits_{k=0}^{n-1}}\left(x-k\right),\quad
n\in\mathbb{N}.$ (22)

The polynomials $\varphi_{n}\left(x\right)$ satisfy the basic identities

$x\varphi_{n}\left(x\right)=\varphi_{n+1}\left(x\right)+n\varphi_{n}\left(x\right),\quad
n\in\mathbb{N}_{0},$ (23)

and

$\Delta\varphi_{n}=n\varphi_{n-1},\quad n\in\mathbb{N}_{0}.$ (24)

###### Lemma 4

We have the representation

$\varphi_{n}\left(x-1\right)={\displaystyle\sum\limits_{k=0}^{n}}\left(-1\right)^{k}\varphi_{k}\left(n\right)\varphi_{n-k}\left(x\right),\quad
n\in\mathbb{N}_{0}.$ (25)

Proof. We use induction. The identity is true for $n=0$ since
$\varphi_{0}\left(x\right)=1.$ Assuming (25) to be true for all $0\leq k\leq
n$ and using the recurrence (23), we have

$\displaystyle\varphi_{n+1}\left(x-1\right)$
$\displaystyle=\left(x-1-n\right)\varphi_{n}\left(x-1\right)={\displaystyle\sum\limits_{k=0}^{n}}\left(-1\right)^{k}\varphi_{k}\left(n\right)\left(x-1-n\right)\varphi_{n-k}\left(x\right)$
$\displaystyle={\displaystyle\sum\limits_{k=0}^{n}}\left(-1\right)^{k}\varphi_{k}\left(n\right)\left[\varphi_{n+1-k}\left(x\right)-\left(k+1\right)\varphi_{n-k}\left(x\right)\right].$

Since $\varphi_{n+1}\left(n\right)=0,$ we can rewrite the sum above as

$\varphi_{n+1}\left(x-1\right)={\displaystyle\sum\limits_{k=0}^{n+1}}\left(-1\right)^{k}\varphi_{k}\left(n\right)\varphi_{n+1-k}\left(x\right)+{\displaystyle\sum\limits_{k=0}^{n}}\left(-1\right)^{k+1}\left(k+1\right)\varphi_{k}\left(n\right)\varphi_{n-k}\left(x\right),$

or shifting the index in the second sum

$\varphi_{n+1}\left(x-1\right)={\displaystyle\sum\limits_{k=0}^{n+1}}\left(-1\right)^{k}\varphi_{k}\left(n\right)\varphi_{n+1-k}\left(x\right)+{\displaystyle\sum\limits_{k=1}^{n+1}}\left(-1\right)^{k}k\varphi_{k-1}\left(n\right)\varphi_{n+1-k}\left(x\right).$

But from (24) we see that

$\varphi_{k}\left(n+1\right)=\varphi_{k}\left(n\right)+k\varphi_{k-1}\left(n\right),$

and we conclude that

$\varphi_{n+1}\left(x-1\right)={\displaystyle\sum\limits_{k=0}^{n+1}}\left(-1\right)^{k}\varphi_{k}\left(n+1\right)\varphi_{n+1-k}\left(x\right).$

###### Proposition 5

Let $\\{p_{n}\left(x\right)\\}_{n\geq 0}$ be a sequence of polynomials
orthogonal with respect to a $\Delta-$semiclassical functional $L$ of class
$s.$ Then,

$L\left[\phi\Delta q\Delta p_{n}\right]=0,\quad
q\in\mathbb{P},\quad\deg\left(q\right)<n-s.$ (26)

Proof. The equation (26) is obviously true if $q=1,$ so we can assume that
$\deg\left(q\right)\geq 1.$ Using (25) with $k\geq 1,$ we have

$\Delta\varphi_{k}=-{\displaystyle\sum\limits_{j=1}^{k}}\left(-1\right)^{j}\varphi_{j}\left(k\right)\varphi_{k-j}\left(x+1\right),$

and multiplying by $\Delta p_{n}$ we get

$\Delta\varphi_{k}\Delta
p_{n}={\displaystyle\sum\limits_{j=1}^{k}}\left(-1\right)^{j}\varphi_{j}\left(k\right)\left[\Delta\varphi_{k-j}p_{n}-\Delta\left(\varphi_{k-j}p_{n}\right)\right],$

where we have used the identity

$\Delta\left(fg\right)=g\left(x+1\right)\Delta f+f\Delta g=g\Delta f+f\Delta
g+\Delta f\Delta g.$ (27)

Using the Pearson equation (16) and (24), we obtain

$\displaystyle L\left[\phi\Delta\varphi_{k}\Delta p_{n}\right]$
$\displaystyle={\displaystyle\sum\limits_{j=1}^{k}}\left(-1\right)^{j}\varphi_{j}\left(k\right)\left(L\left[\phi\Delta\varphi_{k-j}p_{n}\right]-L\left[\psi\varphi_{k-j}p_{n}\right]\right)$
$\displaystyle={\displaystyle\sum\limits_{j=1}^{k}}\left(-1\right)^{j}\varphi_{j}\left(k\right)\left\\{\left(k-j\right)L\left[\phi\varphi_{k-j-1}p_{n}\right]-L\left[\psi\varphi_{k-j}p_{n}\right]\right\\},$

and since the sequence of polynomials $\\{p_{n}(x)\\}_{n\geq 0}$ is orthogonal
with respect to $L$ we conclude that

$L\left[\phi\Delta\varphi_{k}\Delta p_{n}\right]=0,\quad
k<\min\left\\{n+2-\deg\left(\phi\right),\
n+1-\deg\left(\psi\right)\right\\}=n-s.$

Using the fact that $\left\\{\varphi_{k}\left(x\right)\right\\}_{k\geq 0}$ is
a polynomial basis, the result follows.

Using Proposition 5, we can prove the following characterization of discrete
semiclassical polynomials.

###### Theorem 6

Let $\\{p_{n}\left(x\right)\\}_{n\geq 0}$ be a sequence of monic polynomials
orthogonal with respect to a functional $L.$ The following statements are
equivalent:

###### Proposition 7

(i) $L$ is $\Delta-$semiclassical of class $s.$

(ii) There exists a monic polynomial $\phi\left(x\right)$ such that the
polynomials $p_{n}$ satisfy the _structure equation_

$\phi\left(x\right)\Delta
p_{n+1}={\displaystyle\sum\limits_{k=n-s}^{n+d_{1}}}\epsilon_{n,k}p_{k},\quad
n>s,\quad\epsilon_{n,n-s}\neq 0.$ (28)

Proof. (i) $\Rightarrow$ (ii) Since the sequence $\\{p_{n}\\}_{n\geq 0}$ is a
polynomial basis in the linear space of polynomials, we can write

$\phi\left(x\right)\Delta
p_{n+1}={\displaystyle\sum\limits_{k=0}^{n+d_{1}}}\epsilon_{n,k}p_{k}.$ (29)

Using the orthogonality relation (13) and (27), we have

$h_{k}\epsilon_{n,k}=L\left[\phi p_{k}\Delta
p_{n+1}\right]=L\left[\phi\Delta\left(p_{k}p_{n+1}\right)\right]-L\left[\phi\Delta
p_{k}p_{n+1}\right]-L\left[\phi\Delta p_{k}\Delta p_{n+1}\right].$

Using (17) and orthogonality, we get

$L\left[\phi\Delta\left(p_{k}p_{n+1}\right)\right]=L\left[\psi
p_{k}p_{n+1}\right]=0,\quad k<n+1-d_{2},$

and

$L\left[\phi\Delta\varphi_{k}p_{n+1}\right]=kL\left[\phi\varphi_{k-1}p_{n+1}\right]=0,\quad
k<n+2-d_{1},$

from which it follows that

$L\left[\phi\Delta\left(p_{k}p_{n+1}\right)\right]-L\left[\phi\Delta
p_{k}p_{n+1}\right]=0,\quad k<n-s.$

Using (26) we see that

$L\left[\phi\Delta p_{k}\Delta p_{n+1}\right]=0,\quad k<n+1-s,$

and therefore

$\epsilon_{n,k}=0,\quad k<n-s.$

For $k=n-s,$ we have

$\epsilon_{n,n-s}=h_{n+1}\left(\frac{\psi_{d_{2}}}{h_{n+1-d_{2}}}\delta_{d_{2},s+1}-\frac{n+2-d_{1}}{h_{n+2-d_{1}}}\delta_{d_{1},s+2}\right),$

and it follows that $\epsilon_{n,n-s}\neq 0$ as long as $d_{1}-2\neq d_{2}-1.$
If $d_{1}=d_{2}+1,$ we need the additional condition (21).

(ii) $\Rightarrow$ (i) Since $\left\\{\frac{p_{n}}{h_{n}}L\right\\}_{n\geq 0}$
is a basis of $\mathbb{P}^{\ast}$ satisfying

$\frac{p_{n}}{h_{n}}L\left[p_{k}\right]=\frac{1}{h_{n}}L\left[p_{k}p_{n}\right]=\delta_{k,n},$

we have the representation

$\Delta^{\ast}\left(\phi
L\right)={\displaystyle\sum\limits_{n=0}^{\infty}}c_{n}\frac{p_{n}}{h_{n}}L.$

Using the structure relation (28) and orthogonality, we get

$\displaystyle c_{n+1}$ $\displaystyle=\Delta^{\ast}\left(\phi
L\right)\left[p_{n+1}\right]=-L\left[\phi\Delta p_{n+1}\right]$
$\displaystyle=-{\displaystyle\sum\limits_{k=n-s}^{n+d_{1}}}\epsilon_{n,k}L\left[p_{k}\right]=\left\\{\begin{array}[c]{c}0,\quad
n>s\\\ -\mu_{0}\epsilon_{n,0},\quad n\leq s\end{array}\right.,$

where $\mu_{0}=L\left[1\right].$ Thus, $\Delta^{\ast}\left(\phi L\right)+\psi
L=0,$ with

$\psi\left(x\right)=\mu_{0}{\displaystyle\sum\limits_{n=1}^{s+1}}\frac{\epsilon_{n-1,0}}{h_{n}}p_{n}\left(x\right).$

Note that $\deg\left(\psi\right)-1\leq s,$ in agreement with (20).

For more information about this kind of structure relations for
$\Delta$-semiclassical linear functionals, check [18]. Notice that in the
$\Delta$-classical case $\left(s=0\right)$ two structure relations
characterizing such linear functionals are given in [11].

##  3 Coherent pairs

Let $\left\\{L_{0},L_{1}\right\\}$ be a pair of quasi-definite functionals and
$\left\\{P_{n}^{\left(0\right)}\left(x\right)\right\\}_{n\geq
0},\left\\{P_{n}^{\left(1\right)}\left(x\right)\right\\}_{n\geq 0}$ be the
corresponding sequences of monic orthogonal polynomials. We say that
$\left\\{L_{0},L_{1}\right\\}$ is a $\Delta-$_coherent pair of the second
kind_ (abbreviated $\Delta\mathrm{c}2)$ if there exists
$\left\\{\tau_{n}\right\\}_{n\geq
0}\subset\mathbb{C}\setminus\left\\{0\right\\}$ such that

$Q_{n}(x)=\frac{\Delta
P_{n+1}^{\left(0\right)}(x)}{n+1}=P_{n}^{\left(1\right)}(x)-\tau_{n}P_{n-1}^{\left(1\right)}(x),\quad
n\in\mathbb{N}_{0},$ (30)

where $P_{-1}^{\left(0\right)}(x)=P_{-1}^{\left(1\right)}(x)=0.$ The sequences
of polynomials $\left\\{P_{n}^{\left(i\right)}\left(x\right)\right\\}_{n\geqq
0},$ $i=0,1,$ satisfy the orthogonality conditions

$L_{i}\left[P_{k}^{\left(i\right)}P_{n}^{\left(i\right)}\right]=h_{n}^{\left(i\right)}\delta_{n,k},\quad
i=0,1,\quad n,k\in\mathbb{N}_{0}.$ (31)

###### Proposition 8

If $\left\\{L_{0},L_{1}\right\\}$ is a $\Delta\mathrm{c}2$ and the functionals
$\mathbf{v}_{n}^{\left(i\right)}$ are defined by

$\mathbf{v}_{n}^{\left(i\right)}=\frac{P_{n}^{\left(i\right)}}{h_{n}^{\left(i\right)}}L_{i},\quad
i=0,1,\quad n\in\mathbb{N}_{0},$ (32)

then

$\Delta^{\ast}\mathbf{v}_{n}^{\left(1\right)}=\tau_{n+1}\left(n+2\right)\mathbf{v}_{n+2}^{\left(0\right)}-\left(n+1\right)\mathbf{v}_{n+1}^{\left(0\right)},\quad
n\in\mathbb{N}_{0}.$ (33)

Proof. Using (31) and (32), we have

$\mathbf{v}_{n}^{\left(i\right)}\left[P_{k}^{\left(i\right)}\right]=\delta_{n,k},\quad
i=0,1,\quad n,k\in\mathbb{N}_{0}.$ (34)

Let $\mathbf{u}_{n}\in\mathbb{P}^{\ast}$ be defined by

$\mathbf{u}_{n}\left[Q_{k}\right]=\delta_{n,k},\quad n,k\in\mathbb{N}_{0}.$
(35)

Since the sequence of linear functionals $\\{\mathbf{u}_{n}\\}_{n\geq 0}$ is a
basis of $\mathbb{P}^{\ast},$ we can write

$\mathbf{v}_{n}^{\left(1\right)}={\displaystyle\sum\limits_{k=0}^{\infty}}a_{n,k}\mathbf{u}_{n}.$

Using (30) and (34), we get

$a_{n,k}=\mathbf{v}_{n}^{\left(1\right)}\left[Q_{k}\right]=\mathbf{v}_{n}^{\left(1\right)}\left[P_{k}^{\left(1\right)}-\tau_{k}P_{k-1}^{\left(1\right)}\right]=\delta_{n,k}-\tau_{k}\delta_{n,k-1},$

and therefore

$\mathbf{v}_{n}^{\left(1\right)}=\mathbf{u}_{n}-\tau_{n+1}\mathbf{u}_{n+1},\quad
n\in\mathbb{N}_{0}.$ (36)

If we write

$\Delta^{\ast}\mathbf{u}_{n}={\displaystyle\sum\limits_{k=0}^{\infty}}b_{n,k}\mathbf{v}_{k}^{\left(0\right)},$

then

$b_{n,k}=\Delta^{\ast}\mathbf{u}_{n}\left[P_{k}^{\left(0\right)}\right]=-\mathbf{v}_{n}^{\left(0\right)}\left[\Delta
P_{k}^{\left(0\right)}\right]=-k\mathbf{v}_{n}^{\left(0\right)}\left[Q_{k-1}\right]=-k\delta_{n,k-1},$

and, as a consequence,

$\Delta^{\ast}\mathbf{u}_{n}=-\left(n+1\right)\mathbf{v}_{n+1}^{\left(0\right)}.$
(37)

Using (37) in (36), we obtain (33).

With the help of Proposition 8, we can prove a characterization of
$\Delta-$coherent pairs of the second kind.

###### Theorem 9

The following are equivalent:

(1) $\left\\{L_{0},L_{1}\right\\}$ is a $\Delta\mathrm{c}2$.

(2) There exist $\Lambda_{2},\Lambda_{3}\in\mathbb{P}$ defined by

$\Lambda_{k}\left(x\right)={\displaystyle\sum\limits_{i=0}^{k}}\lambda_{i}^{\left(k\right)}x^{i},\quad
k=2,3,$ (38)

and satisfying

$\lambda_{2}^{\left(2\right)}+\left(n-1\right)\lambda_{3}^{\left(3\right)}\neq
0,\quad n\in\mathbb{N},$ (39)

such that

$\Delta^{\ast}L_{1}=\Lambda_{2}L_{0},\quad L_{1}=\Lambda_{3}L_{0}.$ (40)

Proof. (1) $\Rightarrow$ (2) Setting $n=0$ in (33), we have

$\frac{1}{h_{0}^{\left(1\right)}}\Delta^{\ast}L_{1}=2\tau_{1}\frac{P_{2}^{\left(0\right)}}{h_{2}^{\left(0\right)}}L_{0}-\frac{P_{1}^{\left(0\right)}}{h_{1}^{\left(0\right)}}L_{0},$

and defining

$\Lambda_{2}\left(x\right)=\frac{2\tau_{1}h_{0}^{\left(1\right)}}{h_{2}^{\left(0\right)}}P_{2}^{\left(0\right)}\left(x\right)-\frac{h_{0}^{\left(1\right)}}{h_{1}^{\left(0\right)}}P_{1}^{\left(0\right)}\left(x\right),$

we get $\Delta^{\ast}L_{1}=\Lambda_{2}L_{0}.$ Since $\tau_{1}\neq 0,$ we see
that $\deg\left(\Lambda_{2}\right)=2.$

Similarly, setting $n=1$ in (33) gives

$\frac{1}{h_{1}^{\left(1\right)}}\Delta^{\ast}\left(P_{1}^{\left(1\right)}L_{1}\right)=3\tau_{2}\frac{P_{3}^{\left(0\right)}}{h_{3}^{\left(0\right)}}L_{0}-2\frac{P_{2}^{\left(0\right)}}{h_{2}^{\left(0\right)}}L_{0}$

and using (27) we have

$\Delta^{\ast}P_{1}^{\left(1\right)}L_{1}+P_{1}^{\left(1\right)}\Delta^{\ast}L_{1}+\Delta^{\ast}P_{1}^{\left(1\right)}\Delta^{\ast}L_{1}=\left(\frac{3\tau_{2}h_{1}^{\left(1\right)}}{h_{3}^{\left(0\right)}}P_{3}^{\left(0\right)}-\frac{2h_{1}^{\left(1\right)}}{h_{2}^{\left(0\right)}}P_{2}^{\left(0\right)}\right)L_{0}.$

Since $\Delta^{\ast}P_{1}^{\left(1\right)}=1$ and
$\Delta^{\ast}L_{1}=\Lambda_{2}L_{0},$ we conclude that
$L_{1}=\Lambda_{3}L_{0}$ with

$\Lambda_{3}\left(x\right)=\frac{3\tau_{2}h_{1}^{\left(1\right)}}{h_{3}^{\left(0\right)}}P_{3}^{\left(0\right)}\left(x\right)-\frac{2h_{1}^{\left(1\right)}}{h_{2}^{\left(0\right)}}P_{2}^{\left(0\right)}\left(x\right)-\Lambda_{2}\left(x\right)\left[P_{1}^{\left(1\right)}\left(x\right)+1\right].$

Note that $\deg\left(\Lambda_{3}\right)\leq 3.$

(2) $\Rightarrow$ (1) Since the polynomial sequence
$\\{P_{n}^{\left(1\right)}\left(x\right)\\}_{n\geq 0}$ is a basis of
$\mathbb{P}$, we have

$Q_{n}(x)=P_{n}^{\left(1\right)}+{\displaystyle\sum\limits_{k=0}^{n-1}}c_{n,k}P_{k}^{\left(1\right)}(x).$

Using orthogonality and (27), we get

$\displaystyle\left(n+1\right)h_{k}^{\left(1\right)}c_{n,k}=\left(n+1\right)L_{1}\left[Q_{n}P_{k}^{\left(1\right)}\right]=L_{1}\left[\Delta
P_{n+1}^{\left(0\right)}P_{k}^{\left(1\right)}\right]$
$\displaystyle=L_{1}\left[\Delta\left(P_{n+1}^{\left(0\right)}P_{k}^{\left(1\right)}\right)\right]-L_{1}\left[P_{n+1}^{\left(0\right)}\Delta
P_{k}^{\left(1\right)}\right]-L_{1}\left[\Delta P_{n+1}^{\left(0\right)}\Delta
P_{k}^{\left(1\right)}\right]$
$\displaystyle=-L_{0}\left[\Lambda_{2}P_{n+1}^{\left(0\right)}P_{k}^{\left(1\right)}\right]-L_{0}\left[\Lambda_{3}P_{n+1}^{\left(0\right)}\Delta
P_{k}^{\left(1\right)}\right]-L_{0}\left[\Lambda_{3}\Delta
P_{n+1}^{\left(0\right)}\Delta P_{k}^{\left(1\right)}\right],$

and hence for all $0\leq k\leq n-1$

$\displaystyle
L_{0}\left[\Lambda_{2}P_{n+1}^{\left(0\right)}P_{k}^{\left(1\right)}\right]$
$\displaystyle=\lambda_{2}^{\left(2\right)}h_{n+1}^{\left(0\right)}\delta_{k,n-1},$
$\displaystyle L_{0}\left[\Lambda_{3}P_{n+1}^{\left(0\right)}\Delta
P_{k}^{\left(1\right)}\right]$
$\displaystyle=\left(n-1\right)\lambda_{3}^{\left(3\right)}h_{n+1}^{\left(0\right)}\delta_{k,n-1}.$

From (40) it follows that

$\Delta^{\ast}\left(\Lambda_{3}L_{0}\right)=\Lambda_{2}L_{0}.$

Therefore $L_{0}$ is $\Delta-$semiclassical of class at most $1.$ Using (26),
we conclude that

$L_{0}\left[\Lambda_{3}\Delta P_{n+1}^{\left(0\right)}\Delta
P_{k}^{\left(1\right)}\right]=0,\quad k<n.$

Thus, for all $0\leq k\leq n-1$

$\left(n+1\right)h_{k}^{\left(1\right)}c_{n,k}=-\left[\lambda_{2}^{\left(2\right)}+\left(n-1\right)\lambda_{3}^{\left(3\right)}\right]h_{n+1}^{\left(0\right)}\delta_{k,n-1},$

and we obtain

$Q_{n}(x)=P_{n}^{\left(1\right)}(x)-\tau_{n}P_{n-1}^{\left(1\right)}(x),$

where

$\tau_{n}=\frac{\lambda_{2}^{\left(2\right)}+\left(n-1\right)\lambda_{3}^{\left(3\right)}}{n+1}\frac{h_{n+1}^{\left(0\right)}}{h_{n-1}^{\left(1\right)}},\quad
n\in\mathbb{N}.$ (41)

Since the polynomials $\Lambda_{2},\Lambda_{3}$ satisfy (39), we see that
$\tau_{n}\neq 0.$

##  4 Classification

In this section, we will find all $\Delta-$coherent pairs of the second kind.
In view of Theorem 9, it is enough to consider discrete semiclassical
functionals of class $s\leq 1$ satisfying the Pearson equation

$\Delta^{\ast}\left(\Lambda_{3}L_{0}\right)=\Lambda_{2}L_{0},\quad\deg\left(\Lambda_{2}\right)=2,\quad\deg\left(\Lambda_{3}\right)\leq
3.$ (42)

In [8], we classified the discrete semiclassical functionals of class $s\leq
1$ satisfying (19), and obtained the following cases:

  1. 1.

Charlier (class $s=0)$

$\rho\left(x\right)=\frac{z^{x}}{x!},$ (43)
$\phi\left(x\right)=1,\quad\psi\left(x\right)=\frac{x}{z}-1.$ (44)

  2. 2.

Meixner (class $s=0)$

$\rho\left(x\right)=\left(a\right)_{x}\frac{z^{x}}{x!},$ (45)
$\phi\left(x\right)=x+a,\quad\psi\left(x\right)=\frac{x}{z}-\left(x+a\right).$
(46)

Subcase: Kravchuk polynomials

$\rho\left(x\right)=\left(-N\right)_{x}\frac{z^{x}}{x!},\quad N\in\mathbb{N},$
(47)
$\phi\left(x\right)=x-N,\quad\psi\left(x\right)=\frac{x}{z}-\left(x-N\right).$
(48)

  3. 3.

Hahn (class $s=0)$

$\rho\left(x\right)=\frac{\left(-N\right)_{x}\left(a\right)_{x}}{\left(b+1\right)_{x}}\frac{1}{x!},\quad
N\in\mathbb{N},$ (49)
$\phi\left(x\right)=\left(x-N\right)\left(x+a\right),\quad\psi\left(x\right)=\left(N-a+b\right)x+aN.$
(50)

  4. 4.

Generalized Charlier (class $s=1)$

$\rho\left(x\right)=\frac{1}{\left(b+1\right)_{x}}\frac{z^{x}}{x!},$ (51)
$\phi\left(x\right)=1,\quad\psi\left(x\right)=\frac{x\left(x+b\right)}{z}-1.$
(52)

  5. 5.

Generalized Meixner (class $s=1)$

$\rho\left(x\right)=\frac{\left(a\right)_{x}}{\left(b+1\right)_{x}}\frac{z^{x}}{x!},$
(53)
$\phi\left(x\right)=x+a,\quad\psi\left(x\right)=\frac{x\left(x+b\right)}{z}-\left(x+a\right).$
(54)

  6. 6.

Generalized Kravchuk (class $s=1)$

$\rho\left(x\right)=\left(-N\right)_{x}\left(a\right)_{x}\frac{z^{x}}{x!},\quad
N\in\mathbb{N},$ (55)
$\phi\left(x\right)=\left(x-N\right)\left(x+a\right),\quad\psi\left(x\right)=\frac{x}{z}-\left(x-N\right)\left(x+a\right).$
(56)

  7. 7.

Generalized Hahn of type I (class $s=1)$

$\rho\left(x\right)=\frac{\left(a_{1}\right)_{x}\left(a_{2}\right)_{x}}{\left(b+1\right)_{x}}\frac{z^{x}}{x!},$
(57)
$\phi\left(x\right)=\left(x+a_{1}\right)\left(x+a_{2}\right),\quad\psi\left(x\right)=\frac{x\left(x+b\right)}{z}-\left(x+a_{1}\right)\left(x+a_{2}\right).$
(58)

Note that if we set $z=1,a_{1}=a,a_{2}=-N,$ then we obtain the Hahn
polynomials.

  8. 8.

Generalized Hahn of type II (class $s=1)$

$\rho\left(x\right)=\frac{\left(-N\right)_{x}\left(a_{1}\right)_{x}\left(a_{2}\right)_{x}}{\left(b_{1}+1\right)_{x}\left(b_{2}+1\right)_{x}}\frac{1}{x!},\quad
N\in\mathbb{N},$ (59) $\displaystyle\phi\left(x\right)$
$\displaystyle=\left(x-N\right)\left(x+a_{1}\right)\left(x+a_{2}\right),$ (60)
$\displaystyle\psi\left(x\right)$
$\displaystyle=\left(N-a_{1}-a_{2}+b_{1}+b_{2}\right)x^{2}+\left(Na_{1}+Na_{2}-a_{1}a_{2}+b_{1}b_{2}\right)\allowbreak
x+Na_{1}a_{2}$

If we define $L_{0},L_{1}\in\mathbb{P}^{\ast}$ by

$L_{i}\left[p\right]={\displaystyle\sum\limits_{x=0}^{\infty}}p\left(x\right)\rho_{i}\left(x\right),\quad
i=0,1,\quad p\in\mathbb{P},$

with $\rho_{i}\left(-1\right)=0,$ $i=0,1,$ then we can use (2) and rewrite
(40) as

$\nabla\left(\Lambda_{3}\rho_{0}\right)+\Lambda_{2}\rho_{0}=0,\quad\rho_{1}=\Lambda_{3}\rho_{0}.$
(61)

###### Proposition 10

Let $q,\phi_{0},\psi_{0}\in\mathbb{P}.$ If $L_{0}\in\mathbb{P}^{\ast}$
satisfies

$\nabla\left(\phi_{0}\rho_{0}\right)+\psi_{0}\rho_{0}=0,$ (62)

and

$\Lambda_{2}=\left(q-\nabla q\right)\psi_{0}-\phi_{0}\nabla
q,\quad\Lambda_{3}=q\phi_{0},$ (63)

then

$\nabla\left(\Lambda_{3}\rho_{0}\right)+\Lambda_{2}\rho_{0}=0.$ (64)

Proof. If we use the identity

$\nabla\left(fg\right)=g\nabla f+f\nabla g-\nabla f\nabla g,$ (65)

and (63), we have

$\nabla\left(\Lambda_{3}\rho_{0}\right)=\left(\nabla
q\right)\phi_{0}\rho_{0}+\left(q-\nabla
q\right)\nabla\left(\phi_{0}\rho_{0}\right).$

Using (62), we get

$\nabla\left(\Lambda_{3}\rho_{0}\right)=\left(\nabla
q\right)\phi_{0}\rho_{0}-\left(q-\nabla
q\right)\psi_{0}\rho_{0}=-\Lambda_{2}\rho_{0},$

and (64) follows.

We will now find all $\Delta\mathrm{c}2$ pairs with
$\deg\left(\Lambda_{2}\right)=2.$

###  4.1 Case I: $\deg\left(\Lambda_{3}\right)=0$

If we take $\Lambda_{3}=1,$ we see from (61) that

$\nabla\rho_{0}+\Lambda_{2}\rho_{0}=0,\quad\rho_{1}=\rho_{0},$

and if $\rho_{0}\left(x\right)$ is the weight function corresponding to the
generalized Charlier polynomials (51), we see from (52) that

$\Lambda_{2}\left(x\right)=\frac{x\left(x+b\right)}{z}-1,\quad z\neq 0.$

Thus, the generalized Charlier polynomials are _self-coherent_ of the second
kind _._ Note that this was already observed in [10].

###  4.2 Case II (a): $\deg\left(\Lambda_{3}\right)=1$

If we take $\Lambda_{3}=x+\omega,$ $\omega\in\mathbb{C},$ then we see from
(61) that

$\nabla\left[\left(x+\omega\right)\rho_{0}\right]+\Lambda_{2}\rho_{0}=0,\quad\rho_{1}=\left(x+\omega\right)\rho.$

If $\rho_{0}\left(x\right)$ is the weight function corresponding to the
Charlier polynomials (43), we can use Proposition 10 with $q=x+\omega$ and
obtain

$\Lambda_{2}\left(x\right)=\frac{x}{z}\left(x+\omega-1\right)-\left(x+\omega\right),\quad
z\neq 0,$

where we have also used (44). The functional $L_{1}$ is a _Christoffel
transformation_ of $L_{0}$ satisfying

$\nabla\left[\left(x+\omega\right)\rho_{1}\right]+\Lambda_{2}\rho_{1}=0,$

and using (54) we see that $\rho_{1}\left(x\right)$ is the weight function
corresponding to the generalized Meixner polynomials (53) with

$a=\omega,\quad b=\omega-1.$

###  4.3 Case II (b): $\deg\left(\Lambda_{3}\right)=1$

If we take $\Lambda_{3}=x+\omega,$ $\omega\in\mathbb{C},$ then from (61) we
get that

$\nabla\left[\left(x+\omega\right)\rho_{0}\right]+\Lambda_{2}\rho_{0}=0,\quad\rho_{1}=\left(x+\omega\right)\rho.$

If $\rho_{0}\left(x\right)$ is the weight function corresponding to the
Kravchuk polynomials (47), we can use Proposition 10 with $q=x+\omega$ and
obtain

$\Lambda_{2}\left(x\right)=\frac{x}{z}\left(x+\omega-1\right)-\left(x+\omega\right)\left(x-N\right),\quad
z\neq 0,$

were we have also used (48). The functional $L_{1}$ is a Christoffel
transformation of $L_{0}$ satisfying

$\nabla\left[\left(x+\omega\right)\rho_{1}\right]+\Lambda_{2}\rho_{1}=0,$

and using (56) we see that $\rho_{1}\left(x\right)$ is the weight function
corresponding to the generalized Kravchuk polynomials (55) with

$a=\omega,\quad b=\omega-1.$

###  4.4 Case III: $\deg\left(\Lambda_{3}\right)=2$

If we take $\Lambda_{3}=\left(x+\omega\right)\left(x+a\right),$
$\omega\in\mathbb{C},$ then from (61) it follows

$\nabla\left[\left(x+\omega\right)\left(x+a\right)\rho_{0}\right]+\Lambda_{2}\rho_{0}=0,\quad\rho_{1}=\left(x+\omega\right)\left(x+a\right)\rho_{0}.$

If $\rho_{0}\left(x\right)$ is the weight function corresponding to the
Meixner polynomials (45), we can use Proposition 10 with $q=x+\omega$ and
obtain

$\Lambda_{2}\left(x\right)=\frac{x}{z}\left(x+\omega-1\right)-\left(x+\omega\right)\left(x+a\right),\quad
z\neq 0,$

were we have also used (46). The functional $L_{1}$ is a Christoffel
transformation of $L_{0}$ satisfying

$\nabla\left[\left(x+\omega\right)\left(x+a\right)\rho_{1}\right]+\Lambda_{2}\rho_{1}=0,$

and using (58) we see that $\rho_{1}\left(x\right)$ is the weight function
corresponding to the generalized Hahn polynomials of type I (57) with

$a_{1}=a,\quad a_{2}=\omega,\quad b=\omega-1.$

###  4.5 Case IV: $\deg\left(\Lambda_{3}\right)=3$

If we take
$\Lambda_{3}=\left(x+\omega\right)\left(x-N\right)\left(x+a\right),$
$\omega\in\mathbb{C},$ $N\in\mathbb{N},$ from (61) we deduce that

$\displaystyle\nabla\left[\left(x+\omega\right)\left(x-N\right)\left(x+a\right)\rho_{0}\right]+\Lambda_{2}\rho_{0}=0,$
$\displaystyle\rho_{1}=\left(x+\omega\right)\left(x-N\right)\left(x+a\right)\rho_{0}.$

If $\rho_{0}\left(x\right)$ is the weight function corresponding to the Hahn
polynomials (49), we can use Proposition 10 with $q=x+\omega$ and obtain

$\Lambda_{2}=\allowbreak\left(N-a+b-1\right)x^{2}+\allowbreak\left(N\omega+Na-a\omega+b\omega-b\right)x+Na\omega,$

were we have also used (50). The functional $L_{1}$ is a Christoffel
transformation of $L_{0}$ satisfying

$\nabla\left[\left(x+\omega\right)\left(x-N\right)\left(x+a\right)\rho_{1}\right]+\Lambda_{2}\rho_{1}=0,$

and using (60) we see that $\rho_{1}\left(x\right)$ is the weight function
corresponding to the generalized Hahn polynomials of type II (59) with

$a_{1}=a,\quad a_{2}=\omega,\quad b_{1}=b,\quad b_{2}=\omega-1.$

Note that Christoffel transforms of $\Delta$-classical linear functionals have
been analyzed in [23].

##  5 Conclusions and future directions

We have classified all $\Delta$-coherent pairs of the second kind
$\\{L_{0},L_{1}\\}$ and derived the following results:

$\begin{tabular}[c]{|l|l|}\hline\cr$L_{0}$&$L_{1}$\\\ \hline\cr generalized
Charlier&generalized Charlier\\\ \hline\cr Charlier&generalized Meixner\\\
\hline\cr Kravchuk&generalized Kravchuk\\\ \hline\cr Meixner&generalized Hahn
of type I\\\ \hline\cr Hahn&generalized Hahn of type II\\\
\hline\cr\end{tabular}.$

In all cases, the functional $L_{1}$ is a Christoffel transformation of
$L_{0},$ in agreement with the general results obtained by Meijer [20] for the
continuous case.

In a work in progress, we are dealing with analytic properties of discrete
Sobolev inner products associated with a pair of coherent pairs of the second
kind. We must point out that in [5] the authors deal with asymptotic
properties and the location of zeros of discrete polynomials associated with a
Sobolev inner product

$\langle p,q\rangle_{\mathfrak{S}}=\langle u_{0},pq\rangle+\lambda\langle
u_{1},\Delta p\Delta q\rangle,$

where $\lambda\geq 0$, $(u_{0},u_{1})$ is a $\Delta$-coherent pair of
positive-definite linear functionals, and $u_{1}$ is the Meixner linear
functional. A limit relation between these orthogonal polynomials and the
Laguerre-Sobolev orthogonal polynomials which is analogous to the one existing
between Meixner and Laguerre polynomials in the Askey scheme is deduced.
Notice that Meixner polynomials are $\Delta$ self-coherent, Thus, Mehler-Heine
type formulas and zeros of such polynomials when $u_{0}=u_{1}$ is the Meixner
functional have been studied in [21]. Outer relative asymptotics and
Plancherel-Rotach asymptotics as well as limit relations are analyzed in [4].
Algebraic properties of such polynomials as well as the behavior of their
zeros appear in [2].

##  6 Acknowledgements

Diego Dominici would like to thank the Isaac Newton Institute for Mathematical
Sciences, Cambridge, for support and hospitality during the programme
”Applicable resurgent asymptotics: towards a universal theory” (ARA2). The
work was supported by EPSRC grant no EP/R014604/1.

Francisco Marcellán has been supported by FEDER/Ministerio de Ciencia e
Innovación-Agencia Estatal de Investigación of Spain, grant
PID2021-122154NB-I00, and the Madrid Government (Comunidad de Madrid-Spain)
under the Multiannual Agreement with UC3M in the line of Excellence of
University Professors, grant EPUC3M23 in the context of the V PRICIT (Regional
Program of Research and Technological Innovation).

## References

  * [1] I. Area, E. Godoy, and F. Marcellán.  Classification of all $\Delta$-coherent pairs.  Integral Transform. Spec. Funct. 9(1), 1–18 (2000).
  * [2] I. Area, E. Godoy, and F. Marcellán.  Inner products involving differences: the Meixner-Sobolev polynomials.  J. Differ. Equations Appl. 6(1), 1–31 (2000).
  * [3] I. Area, E. Godoy, and F. Marcellán.  $\Delta$-coherent pairs and orthogonal polynomials of a discrete variable.  Integral Transforms Spec. Funct. 14(1), 31–57 (2003).
  * [4] I. Area, E. Godoy, F. Marcellán, and J. J. Moreno-Balcázar.  Ratio and Plancherel-Rotach asymptotics for Meixner-Sobolev orthogonal polynomials.  J. Comput. Appl. Math. 116(1), 63–75 (2000).
  * [5] I. Area, E. Godoy, F. Marcellán, and J. J. Moreno-Balcázar.  $\Delta$-Sobolev orthogonal polynomials of Meixner type: asymptotics and limit relation.  J. Comput. Appl. Math. 178(1-2), 21–36 (2005).
  * [6] T. S. Chihara.  “An introduction to orthogonal polynomials”.  Mathematics and its Applications, Vol. 13. Gordon and Breach Science Publishers, New York-London-Paris (1978).
  * [7] A. M. Delgado and F. Marcellán.  Companion linear functionals and Sobolev inner products: a case study.  Methods Appl. Anal. 11(2), 237–266 (2004).
  * [8] D. Dominici and F. Marcellán.  Discrete semiclassical orthogonal polynomials of class one.  Pacific J. Math. 268(2), 389–411 (2014).
  * [9] D. Dominici and F. Marcellán.  Discrete semiclassical orthogonal polynomials of class 2.  In “Orthogonal polynomials: current trends and applications”, vol. 22 of “SEMA SIMAI Springer Ser.”, pp. 103–169. Springer, Cham ([2021] ©2021).
  * [10] D. Dominici and J. J. Moreno-Balcázar.  Asymptotic analysis of a family of sobolev orthogonal polynomials related to the generalized charlier polynomials.  arXiv:2210.00082 (2022).
  * [11] A. G. García, F. Marcellán, and L. Salto.  A distributional study of discrete classical orthogonal polynomials.  In “Proceedings of the Fourth International Symposium on Orthogonal Polynomials and their Applications (Evian-Les-Bains, 1992)”, vol. 57, pp. 147–162 (1995).
  * [12] J. C. García-Ardila, F. Marcellán, and M. E. Marriaga.  From standard orthogonal polynomials to Sobolev orthogonal polynomials: the role of semiclassical linear functionals.  In “Orthogonal polynomials”, Tutor. Sch. Workshops Math. Sci., pp. 245–292. Birkhäuser/Springer, Cham ([2020] ©2020).
  * [13] A. Iserles, P. E. Koch, S. P. Nø rsett, and J. M. Sanz-Serna.  On polynomials orthogonal with respect to certain Sobolev inner products.  J. Approx. Theory 65(2), 151–175 (1991).
  * [14] A. Iserles, J. M. Sanz-Serna, P. E. Koch, and S. P. Nø rsett.  Orthogonality and approximation in a Sobolev space.  In “Algorithms for approximation, II (Shrivenham, 1988)”, pp. 117–124. Chapman and Hall, London (1990).
  * [15] R. Koekoek, P. A. Lesky, and R. F. Swarttouw.  “Hypergeometric orthogonal polynomials and their $q$-analogues”.  Springer Monographs in Mathematics. Springer-Verlag, Berlin (2010).  With a foreword by Tom H. Koornwinder.
  * [16] F. Marcellán, T. E. Pérez, and M. A. Piñar.  Orthogonal polynomials on weighted Sobolev spaces: the semiclassical case.  vol. 2, pp. 93–122. (1995).  Special functions (Torino, 1993).
  * [17] F. Marcellán and J. Petronilho.  Orthogonal polynomials and coherent pairs: the classical case.  Indag. Math. (N.S.) 6(3), 287–307 (1995).
  * [18] F. Marcellán and L. Salto.  Discrete semi-classical orthogonal polynomials.  J. Differ. Equations Appl. 4(5), 463–496 (1998).
  * [19] F. Marcellán and Y. Xu.  On Sobolev orthogonal polynomials.  Expo. Math. 33(3), 308–352 (2015).
  * [20] H. G. Meijer.  Determination of all coherent pairs.  J. Approx. Theory 89(3), 321–343 (1997).
  * [21] J. J. Moreno-Balcázar.  $\Delta$-Meixner-Sobolev orthogonal polynomials: Mehler-Heine type formula and zeros.  J. Comput. Appl. Math. 284, 228–234 (2015).
  * [22] A. F. Nikiforov, S. K. Suslov, and V. B. Uvarov.  “Classical orthogonal polynomials of a discrete variable”.  Springer Series in Computational Physics. Springer-Verlag, Berlin (1991).  Translated from the Russian.
  * [23] A. Ronveaux and L. Salto.  Discrete orthogonal polynomials—polynomial modification of a classical functional.  J. Differ. Equations Appl. 7(3), 323–344 (2001).
  * [24] M. H. Suni, G. A. Marcato, F. Marcellán, and A. Sri Ranga.  Coherent pairs of measures of the second kind and associated Sobolev orthogonal polynomials: a functional approach.  Submitted (2022).


NOTE 2019

A note on global optimization for max-plus linear systems

<EMAIL_ADDRESS>
Wang C and Tao Y

# A Note on Global Optimization for Max-Plus Linear Systems

Cailu WANG  Yuegang TAO  School of Automation, Beijing Institute of
Technology, Beijing 100081, China  School of Artificial Intelligence, Hebei
University of Technology, Tianjin 300130, China

###### Abstract

This note further addresses the global optimization problem for max-plus
linear systems considered in [Automatica 119 (2020) 109104]. Firstly, the
operations between $\pm\infty$ and real numbers involved in the formulas of
solving global optimization problems are explained explicitly. Secondly, the
formula of the greatest lower bound and the criterion of solvability of
globally optimal solutions are simplified. Thirdly, the criterion of
uniqueness of globally optimal solutions and the set of all globally optimal
solutions are presented.

###### keywords:

Max-plus linear system, global optimization, optimal solutions

##  1 Introduction

Max-plus linear systems can describe some nonlinear time-evolution systems
with synchronization but no concurrency, such as flexible manufacturing
systems, flow shop scheduling, traffic managements, communication networks
(see, e.g., [3, 2, 1]). Many progresses have been made in control and
optimization of max-plus linear systems (see, e.g., [10, 6, 8, 18, 16, 7, 15,
4, 19, 12, 11, 5, 13, 14, 17, 9]).

Global optimization is to find the global minimizer of a function or a set of
functions over a given set, which has been a basic tool in all areas of
engineering, medicine, economics, and other sciences. The global optimization
for max-plus linear systems has been considered in [20], whose objective
function is a max-plus function and constraint function is a real function.
This note is a further explanation and extension of the results in [20].

Some formulas for globally optimal solutions in
[20] involves the operations between some special elements in max-plus algebra
and real numbers. This note will explain these operations definitely and
simplify the formulas. In addition, reference [20] neglects to consider the
$0$ coefficients in the 1 constraint function when it discusses the uniqueness
of globally optimal solutions. This note will present a necessary and
sufficient condition for the uniqueness and construct the set of all globally
optimal solutions.

##  2 Preliminaries

Let us introduce some basic definitions and notations from the max-plus
algebra, which can be consulted for more details in [3, 2, 1].

Let $\mathbb{R}$ be the set of real numbers, $\mathbb{N}$ be the set of
natural numbers and $\mathbb{N}^{+}$ be the set of positive integers. For
$n\in\mathbb{N}^{+}$, denote by $\mathbb{N}_{n}$ the set $\\{1,2,\ldots,$
$n\\}$. Let $\mathbb{R}_{\max}$ be the set $\mathbb{R}\cup\\{-\infty\\}$ with
max and $\mathbb{+}$ as two binary operations $\oplus$ and $\otimes$,
respectively, i.e., for $a,b\in\mathbb{R}_{\max}$,

$a\oplus b=\max\\{a,b\\}\text{\ and\ }a\otimes b=a+b.$

$\left(\mathbb{R}_{\max},\oplus,\otimes\right)$ is called the max-plus
algebra, in whi- ch $-\infty$ is the zero element denoted by $\varepsilon$,
and 0 is the identity element denoted by $e$. For $a,b\in\mathbb{R}_{\max}$,
$a\leqslant b$ if $a\oplus b=b$.

Let $\mathbb{R}_{\max}^{n}$ and $\mathbb{R}_{\max}^{m\times n}$ be the set of
$n$-dimensional vectors and $m\times n$ matrices with entries in
$\mathbb{R}_{\mathrm{max}}$, respectively. The vectors and matrices are
represented by bold-type letters. The addition and multiplication can be
extended to the vector-matrix algebra over $\mathbb{R}_{\max}$ by the direct
analogy to the con- ventional linear algebra: For $\bm{A}=(a_{ij}),\
\bm{B}=(b_{ij})$ $\in\mathbb{R}_{\max}^{m\times n}$,
$(\bm{A}\oplus\bm{B})_{ij}=a_{ij}\oplus b_{ij};$ for $\bm{A}=(a_{ij})\in$
$\mathbb{R}_{\max}^{m\times p}$ and
$\bm{B}=(b_{ij})\in\mathbb{R}_{\max}^{p\times n}$,

$(\bm{A}\otimes\bm{B})_{ij}=\bigoplus_{k=1}^{p}a_{ik}\otimes b_{kj}.$

For $\bm{A},\bm{B}$ $\in\mathbb{R}_{\max}^{m\times n}$,
$\bm{A}\leqslant\bm{B}$ if $\bm{A}\oplus\bm{B}=\bm{B}$. For $\bm{A},$
$\bm{B}\in\mathbb{R}_{\max}^{m\times n}$ and
$\bm{x},\bm{y}\in\mathbb{R}_{\max}^{n}$, if $\bm{A}\leqslant\bm{B}$ and
$\bm{x}\leqslant\bm{y}$, then $\bm{A}\otimes\bm{x}$
$\leqslant\bm{B}\otimes\bm{y}.$

For $\bm{A}\in\mathbb{R}_{\max}^{m\times n}$ and
$\bm{x}\in\mathbb{R}_{\max}^{n}$, $F(\bm{x})=\bm{A}\otimes\bm{x}$ is called a
max-plus function of type $(n,m)$. Denoted by $F_{i}(\bm{x})$ the $i$th
component of $F(\bm{x})$. A max-plus linear system is a system that can be
described by using max-plus functions.

Given $\bm{A}=(a_{ij})\in\mathbb{R}_{\max}^{m\times n}$ and
$\bm{b}=(b_{i})\in\mathbb{R}_{\max}^{m}$, a system of max-plus linear
equations is defined as

$\bm{A}\otimes\bm{x}=\bm{b},$ (1)

where $\bm{x}=(x_{j})$ is considered in
$\accentset{{\cc@style\underline{\mskip
10.0mu}}}{\mathbb{R}}_{\max}(=\mathbb{R}_{\max}\cup\\{+\infty\\})$, rather
than in $\mathbb{R}_{\max}$. System (1) is said to be solvable if there exists
$\tilde{\bm{x}}\in$ $\accentset{{\cc@style\underline{\mskip
10.0mu}}}{\mathbb{R}}_{\max}^{n}$ such that
$\bm{A}\otimes\tilde{\bm{x}}=\bm{b}$, and $\tilde{\bm{x}}$ is called a
solution of system (1). For
$\tilde{\bm{x}}\in\accentset{{\cc@style\underline{\mskip
10.0mu}}}{\mathbb{R}}_{\max}^{n}$, $\tilde{\bm{x}}$ is called a subsolution of
system (1) if $\bm{A}\otimes\tilde{\bm{x}}\leqslant\bm{b}$.

######  Lemma 2.1.

[3] For system (1), let
$\bm{x}^{*}(\bm{A},\bm{b})\in\accentset{{\cc@style\underline{\mskip
10.0mu}}}{\mathbb{R}}_{\max}^{n}$ be defined by

$x_{j}^{*}(\bm{A},\bm{b})=\min\limits_{i\in\mathbb{N}_{m}}\\{b_{i}-a_{ij}\\},\
j\in\mathbb{N}_{n}.$ (2)

Then, $\bm{x}^{*}(\bm{A},\bm{b})$ is the greatest subsolution of system (1),
i.e.,

  1. 1)

$\bm{A}\otimes\bm{x}^{*}(\bm{A},\bm{b})\leqslant\bm{b}$;

  2. 2)

if $\tilde{\bm{x}}$ is a subsolution of system (1), then
$\tilde{\bm{x}}\leqslant\bm{x}^{*}(\bm{A},\bm{b})$. In particular, if
$\tilde{\bm{x}}$ is a solution, then
$\tilde{\bm{x}}\leqslant\bm{x}^{*}(\bm{A},\bm{b})$.

System (1) is solvable if and only if the greatest subsolution is a solution,
i.e., $\bm{A}\otimes\bm{x}^{*}(\bm{A},\bm{b})=\bm{b}$.

##  3 Global optimization

Consider the global optimization problem

$\min_{\bm{x}\in\mathcal{X}}F(\bm{x}),$ (3)

where the optimization variable is $\bm{x}=(x_{j})\in\mathbb{R}^{n}$; the
objective function is $F(\bm{x})=\bm{A}\otimes\bm{x}$, in which
$\bm{A}=(a_{ij})\in\mathbb{R}_{\max}^{m\times n}$; the constraint set is

$\mathcal{X}=\left\\{\bm{x}\,\Big{|}\displaystyle\sum\limits_{j=1}^{n}{k_{j}x_{j}}=c,\
k_{j}\geqslant 0,\ k_{j}\text{\,are not all 0}\right\\},$

in which $c\in\mathbb{R}$ is a constant.

######  Definition 3.1.

[20] Problem (3) is said to be solvable if there exists
$\tilde{\bm{x}}\in\mathcal{X}$ such that $F(\bm{x})\geqslant
F(\tilde{\bm{x}})$ for any $\bm{x}$ $\in\mathcal{X}$, and $\tilde{\bm{x}}$ is
called a globally optimal solution of problem (3). Otherwise, problem (3) is
said to be unsolvable.

Note that, for problem (3), an $\bm{\varepsilon}$ row in $\bm{A}$ has no
affect on globally optimal solutions. In addition, if the $j_{0}$th column of
$\bm{A}$ is $\bm{\varepsilon}$ and meanwhile $k_{j_{0}}=0$, then $x_{j_{0}}$
disappears from both the objective function and the constraint function of
problem (3). Consequently, problem (3) becomes into the optimization of
variables $\\{x_{j}\,|\,j\neq j_{0}\\}$. Without loss of generality, let us
make the following assumptions:

  1. 1)

$\bm{A}$ is row $\mathbb{R}$-astic, i.e., $\bm{A}$ has no $\bm{\varepsilon}$
row.

  2. 2)

$k_{j}$$\neq$0 if the $j$th column of $\bm{A}$ is $\bm{\varepsilon}$.

######  Theorem 3.2.

[20] For problem (3), let $\bm{b}=(b_{i})\in\mathbb{R}_{\max}^{m}$ be defined
by

$b_{i}=\frac{\sum_{j=1}^{n}k_{j}a_{ij}+c}{\sum_{j=1}^{n}k_{j}},\
i\in{\mathbb{N}_{m}}.$ (4)

Then, $\bm{b}$ is the greatest lower bound of problem (3):

  1. 1)

$F(\bm{x})\geqslant\bm{b}$ for any $\bm{x}\in\mathcal{X}$;

  2. 2)

if $\bm{y}$ is a lower bound of problem (3), then $\bm{y}\leqslant\bm{b}$.

The calculation of (4) may refer to some opera- tions between elements
$\pm\infty$ in $\accentset{{\cc@style\underline{\mskip
10.0mu}}}{\mathbb{R}}_{\max}$ and real numbers in $\mathbb{R}$. To compute the
greatest lower bound by (4), one needs to make the following statements: For
$r,p\in\mathbb{R}$ and $p>0$,

$\max\\{r,-\infty\\}=r$, |  $\max\\{r,+\infty\\}=+\infty$,
---|---
$r+(-\infty)=-\infty$, |  $r+(+\infty)=+\infty$,
$r-(-\infty)=+\infty$, |  $r-(+\infty)=-\infty$,
$(-\infty)-r=-\infty$, |  $(+\infty)-r=+\infty$,
$p\times(-\infty)=-\infty$, |  $p\times(+\infty)=+\infty$,
$0\times(-\infty)=0$, |  $0\times(+\infty)=0$,
$(+\infty)+(-\infty)=-\infty$, |  $(-\infty)-(-\infty)=+\infty$.

Considering that $0$ coefficients in the constraint function have no function
in calculating the greatest lower bound, formula (4) can equivalently be
simplified as

$b_{i}=\frac{\sum_{j\in\mathcal{J}}k_{j}a_{ij}+c}{\sum_{j\in\mathcal{J}}k_{j}},\
i\in{\mathbb{N}_{m}},$ (5)

where $\mathcal{J}=\\{j\in\mathbb{N}_{n}\,|\,k_{j}>0\\}.$ The formula above
avoids the multiplication $\times$ between $0$ and infinity elements in
$\accentset{{\cc@style\underline{\mskip 10.0mu}}}{\mathbb{R}}_{\max}$.

##  4 Optimal solutions

Let us provide two necessary conditions for the existence of globally optimal
solutions.

######  Lemma 4.1.

If problem (3) is solvable, then

  1. 1)

the greatest lower bound $\bm{b}$ given in (5) is finite;

  2. 2)

$\bm{x}^{*}(\bm{A},\bm{b})$ is finite.

Proof. 1) Suppose that there exists $i_{0}\in\mathbb{N}_{m}$ such that
$b_{i_{0}}=\varepsilon$. Since $\bm{A}$ is row $\mathbb{R}$-astic, there
exists $j_{0}\in$ $\mathbb{N}_{n}$ such that $a_{i_{0}j_{0}}\neq\varepsilon$.
Let $\tilde{\bm{x}}=(\tilde{x}_{j})$ be a globally optimal solution of problem
(3). Then,

$\varepsilon=b_{i_{0}}=F_{i_{0}}(\tilde{\bm{x}})=\max_{j\in\mathbb{N}_{n}}\\{a_{i_{0}j}+\tilde{x}_{j}\\}\geqslant
a_{i_{0}j_{0}}+\tilde{x}_{j_{0}}.$

This implies that $\tilde{x}_{j_{0}}=\varepsilon$, and hence
$\tilde{\bm{x}}\notin\mathcal{X}$. This contradiction indicates that $\bm{b}$
is finite.

2) Since $\bm{b}$ is finite, ${x}_{j}^{*}(\bm{A},\bm{b})\neq\varepsilon$ for
any $j\in\mathbb{N}_{n}$. Suppose that there exists $j_{0}\in\mathbb{N}_{n}$
such that

${x}_{j_{0}}^{*}(\bm{A},\bm{b})=\min\limits_{i\in\mathbb{N}_{m}}\\{b_{i}-a_{ij_{0}}\\}=+\infty.$

This implies that $a_{ij_{0}}=\varepsilon$ for any $i\in\mathbb{N}_{m}$.
Assum- ption 2) ensures that $k_{j_{0}}>0$, i.e, $j_{0}\in\mathcal{J}$.
According to (5), $\bm{b}=\bm{\varepsilon}$, and hence problem (3) is
unsolvable. This contradiction indicates that $\bm{x}^{*}(\bm{A},\bm{b})$ is
finite. $\Square$

It can be inferred from the lemma above that if

$\sum_{j\in\mathcal{J}}k_{j}x_{j}^{*}(\bm{A},\bm{b})\big{(}=\sum_{j=1}^{n}k_{j}x_{j}^{*}(\bm{A},\bm{b})\big{)}=c,$
(6)

then $\bm{x}^{*}(\bm{A},\bm{b})$ is finite and
$\bm{x}^{*}(\bm{A},\bm{b})\in\mathcal{X}$. The cri-
teria of solvability given in [20] can be then represented as follows.

######  Theorem 4.2.

[20] For problem (3), the following statements are equivalent:

  1. 1)

Problem (3) is solvable.

  2. 2)

Equation (6) holds.

  3. 3)

$\bm{x}^{*}(\bm{A},\bm{b})$ is a globally optimal solution.

Let us see a numerical example of global optimization problem that contains
$\varepsilon$ coefficients in the objective function and $0$ coefficients in
the constraint function.

######  Example 4.3.

Consider the global optimization
problem

$\min_{\bm{x}\in\mathcal{X}}F(\bm{x}),$ (7)

where the objective function is $F(\bm{x})=\bm{A}\otimes\bm{x}$,

$\bm{A}=\begin{pmatrix}1&2&-2\\\ -1&e&\varepsilon\\\ e&1&3\end{pmatrix},$

and the constraint set is $\mathcal{X}=\\{\bm{x}\,|\,2x_{1}+x_{2}=2\\}.$ By
(5), $\bm{b}=(2\ \,e\ \,1)^{\intercal}.$ By (2),
$\bm{x}^{*}(\bm{A},\bm{b})=(1\ \,e\ -2)^{\intercal}.$ Then,
$2x_{1}^{*}(\bm{A},\bm{b})+x_{2}^{*}(\bm{A},\bm{b})=2=c.$ It follows from
Theorem 4.2 that problem (7) is solvable, and $(1\ \,e$ $-2)^{\intercal}$ is a
globally optimal solution.

If the constraint set of problem (7) is replaced by
$\accentset{{\cc@style\underline{\mskip
10.0mu}}}{\mathcal{X}}=\\{\bm{x}\,|\,2x_{1}+x_{2}+x_{3}=2\\}$, then
$b_{2}=\varepsilon$. It can be obtained from Lemma 4.1 that such a problem has
no globally optimal solution.

Note that, the globally optimal solution introduced in Definition 3.1 may be
not unique. According to [20, Theorem 3], if problem (3) is solvable, then
$k_{j}>0$ for any $j\in\mathbb{N}_{n}$ is a sufficient condition for the
uniqueness of globally optimal solutions. In fact, such a condition is also
necessary.

######  Theorem 4.4.

Let problem (3) be solvable. Problem (3) has a unique globally optimal
solution if and only if $k_{j}>0$ for any $j\in\mathbb{N}_{n}$.

Proof. The sufficiency can be obtained from the proof of [20, Theorem 3]. Let
us now prove the ne-
cessity. Since problem (3) is solvable, equation (6) holds. Suppose that there
exists $j_{0}\in\mathbb{N}_{n}$ such that
$k_{j_{0}}=0$, i.e., $j_{0}\notin{\mathcal{J}}$. Let $\tilde{\bm{x}}$
$=(\tilde{x}_{j})\in\mathbb{R}_{\max}^{n}$ be defined by

$\tilde{x}_{j}=\left\\{\begin{array}[]{ll}\varepsilon,&j=j_{0};\\\
x^{*}_{j}(\bm{A},\bm{b}),&j\neq j_{0}.\end{array}\right.$ (8)

It can be known from Lemma 4.1 that $\bm{x}^{*}(\bm{A},\bm{b})$ is finite.
Then, $\tilde{\bm{x}}<\bm{x}^{*}(\bm{A},\bm{b})$ and

$\displaystyle\sum_{j\in\mathcal{J}}k_{j}\tilde{x}_{j}$
$\displaystyle=\sum_{j\in\mathcal{J}}k_{j}x^{*}_{j}(\bm{A},\bm{b})=c,$

i.e., $\tilde{\bm{x}}\in\mathcal{X}$. By Theorem 3.2,
$F(\tilde{\bm{x}})\geqslant\bm{b}$. In addition,

$\displaystyle F(\tilde{\bm{x}})$ $\displaystyle\leqslant
F(\bm{x}^{*}(\bm{A},\bm{b}))=\bm{A}\otimes\bm{x}^{*}(\bm{A},\bm{b})\leqslant\bm{b}.$

Hence, $F(\tilde{\bm{x}})=\bm{b}$. This implies that $\tilde{\bm{x}}$ is also
a globally optimal solution, which contradicts with the uniqueness. Hence,
$k_{j}>0$ for any $j\in\mathbb{N}_{n}$. $\Square$

The proof of Theorem 4.4 is constructive and formula (8) can be extended to
find all globally optimal solutions as follows.

######  Theorem 4.5.

If problem (3) is solvable, then the set of all globally optimal solutions is

$\displaystyle\mathcal{S}=\left\\{\tilde{\bm{x}}\
\Bigg{|}\begin{array}[]{l}\tilde{x}_{j}\leqslant
x^{*}_{j}(\bm{A},\bm{b})\text{\ if\ }k_{j}=0;\\\
\tilde{x}_{j}=x^{*}_{j}(\bm{A},\bm{b})\text{\ if\
}k_{j}>0.\end{array}\right\\}.$

Proof. Since problem (3) is solvable, equation (6) holds. On the one hand, for
any $\tilde{\bm{x}}\in\mathcal{S}$,

$\displaystyle\sum_{j\in\mathcal{J}}k_{j}\tilde{x}_{j}$
$\displaystyle=\sum_{j\in\mathcal{J}}k_{j}x^{*}_{j}(\bm{A},\bm{b})=c,$

i.e., $\tilde{\bm{x}}\in\mathcal{X}$. By Theorem 3.2,
$F(\tilde{\bm{x}})\geqslant\bm{b}$. In addition,

$\displaystyle F(\tilde{\bm{x}})$ $\displaystyle\leqslant
F(\bm{x}^{*}(\bm{A},\bm{b}))=\bm{A}\otimes\bm{x}^{*}(\bm{A},\bm{b})\leqslant\bm{b}.$

Hence, $F(\tilde{\bm{x}})=\bm{b}$. This implies that $\tilde{\bm{x}}$ is a
globally optimal solution. On the other hand, let $\tilde{\bm{x}}$ be a
globally optimal solution. Then, $\tilde{\bm{x}}\in\mathcal{X}$ and
$F(\tilde{\bm{x}})$ $=\bm{A}\otimes\tilde{\bm{x}}=\bm{b}.$ By Lemma 2.1,
$\tilde{\bm{x}}\leqslant\bm{x}^{*}(\bm{A},\bm{b})$. Suppose that there exists
$j_{0}\in{\mathcal{J}}$ such that
$\tilde{x}_{j_{0}}<x^{*}_{j_{0}}(\bm{A},\bm{b})$. Then,

$\displaystyle c$
$\displaystyle=\sum_{j\in\mathcal{J}\setminus\\{j_{0}\\}}k_{j}\tilde{x}_{j}+k_{j_{0}}\tilde{x}_{j_{0}}$
$\displaystyle<\sum_{j\in\mathcal{J}\setminus\\{j_{0}\\}}k_{j}x^{*}_{j}(\bm{A},\bm{b})+k_{j_{0}}x^{*}_{j_{0}}(\bm{A},\bm{b})$
$\displaystyle=\sum_{j\in\mathcal{J}}k_{j}x^{*}_{j}(\bm{A},\bm{b})=c.$

This contradiction implies that $\tilde{x}_{j}=x^{*}_{j}(\bm{A},\bm{b})$ for
any $j$ $\in{\mathcal{J}}$, and so $\tilde{\bm{x}}\in\mathcal{S}$. Hence,
$\mathcal{S}$ is the set of all globally optimal solutions. $\Square$

Owing to the theorem above, $\bm{x}^{*}(\bm{A},\bm{b})$ is referred to as the
greatest globally optimal solution of problem (3) if equation (6) holds.

######  Example 4.6.

Find all globally optimal solutions of problem (7). It has been calculated in
Example 4.3 that $\bm{x}^{*}(\bm{A},\bm{b})=(1\ \,e\ -2)^{\intercal}.$ By
Theorem 4.5, the set of all globally optimal solutions is

$\mathcal{S}=\left\\{\,\left(1\ \ 0\ \
a\right)^{\intercal}\Big{|}\,a\leqslant-2\right\\}.$

The authors would like to thank the peer experts for their valuable comments
and sugges- tions.

## References

  * [1] F. Baccelli, G. Cohen, G. J. Olsder, and J. P. Quadrat.  Synchronization and Linearity: An Algebra for Discrete Event Systems.  John Wiley and Sons, New York, 1992.
  * [2] B. Heidergott, G. J. Olsder, and J. van der Woude. Max-Plus at Work: Modeling and Analysis of Synch- ronized Systems. Princeton University Press, New Jersey, 2006.
  * [3] P. Butkovi$\check{\text{c}}$. Max-Linear Systems: Theory and Algorithms. Springer-Verlag, Berlin, 2010.
  * [4] G. Cohen, D. Dubois, J. P. Quadrat, and M. Viot. A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing. IEEE Transactions on Automatic Control, 30: 210–220, 1985\.
  * [5] B. De Schutter and T. van den Boom. Model predictive control for max-plus-linear discrete event systems. Automatica, 37(7): 1049–1056, 2001.
  * [6] S. Gaubert, R. D. Katz, and S. Sergeev. Tropical linear-fractional programming and parametric mean payoff games. Journal of Symbolic Computation, 47: 1447–1478, 2012\.
  * [7] Y. Shang, L. Hardouin, M. Lhommeau, and C. A. Maia. An integrated control strategy to solve the disturbance decoupling problem for max-plus linear systems with applications to a high throughput screening system. Automatica, 63: 338–348, 2016.
  * [8] J. Xu, T. van den Boom, and B. De Schutter. Optimistic optimization for model predictive control of max-plus linear systems. Automatica, 74: 16–22, 2016.
  * [9] S. E. Z. Soudjani, D. Adzkiya, and A. Abate. Formal verification of stochastic max-plus-linear systems. IEEE Transactions on Automatic Control, 61(10): 2861–2876, 2016.
  * [10] S. S. Farahani, T. van den Boom, and B. De Schutter. On optimization of stochastic max-min-plus-scaling systems: An approximation approach. Automatica, 83: 20–27, 2017.
  * [11] B. Cottenceau, L. Hardouin, and J. Trunk.  Weight-balanced timed event graphs to model periodic phenomena in manufacturing systems.  IEEE Transactions on Automation Science and Engineering, 14: 1731–1742, 2017.
  * [12] R. M. F. Candido, L. Hardouin, M. Lhommeau, R. S. Mendes. Conditional reachability of uncertain max plus linear systems. Automatica, 94: 426–435, 2018.
  * [13] K. Ioannis, P. Maragos, and G. Papavassilopoulos. Stochastic stability in max-product and max-plus systems with markovian jumps. Automatica, 92: 123–132, 2018.
  * [14] S. Kubo and K. Nishinari. Applications of max-plus algebra to flow shop scheduling problems. Discrete Applied Mathematics, 247: 278–293, 2018.
  * [15] C. Wang, Y. Tao, and H. Yan.  Optimal input design for uncertain max-plus linear systems.  International Journal of Robust and Nonlinear Control, 28: 4816–4830, 2018.
  * [16] V. M. Goncalves, C. A. Maia, and L. Hardouin. On max-plus linear dynamical system theory: The observation problem. Automatica, 107: 103–111, 2019.
  * [17] R. S. Mendes, L. Hardouin, and M. Lhommeau. Stochastic filtering of max-plus linear systems with bounded disturbances. IEEE Transactions on Automatic Control, 64(9): 3706–3715, 2019.
  * [18] H. Myšková and J. Plavka. Interval robustness of (interval) max-plus matrices. _Discrete Applied Mathematics_ , 284: 8–19, 2020.
  * [19] E. Berthier and F. Bach.  Max-plus linear approximations for deterministic continuous-state markov decision processes.  IEEE Control Systems Letters, 4: 767– 772, 2020.
  * [20] Y. Tao and C. Wang. Global optimization for max-plus linear systems and applications in distributed systems. Automatica, 119: 109104, 2020.