A Mathematical Journal
Vol. 7, No 2, (81 - 85). August 2005.

A note on discrete monotonic dynamical
systems

Dongsheng Liu 1

Department of Applied Mathematics, Nanjing University of Science & Technology
Nanjing, 210094, Jiangsu, Peoples R China

d.liu@lancaster.ac.uk

ABSTRACT
We give a upper bound of Lebesgue measure V (S(f, h, Ω)) of the set S(f, h, Ω)

of points q ∈ Qdh for which the triple (h, q, Ω) is dynamically robust when f is
monotonic and satisfies certain condition on some compact subset Ω ∈ Rd.

RESUMEN
Damos una cota superior de la medida de Lebesgue V (S(f, h, Ω)) del conjunto

S(f, h, Ω) de puntos q ∈ Qdh para los cuales el tŕıo (h, q, Ω) es dinámicamente
robusto cuando f es monótona y satisface ciertas condiciones en algunos subcon-
juntos compactos Ω ∈ Rd.

Key words and phrases: Roundoff operator, dynamical robustness,
dynamical system.

Math. Subj. Class.: 37C70, 37C75

1 Introduction

A discrete dynamical system on the state space Rd is generated by the iteration of a
mapping f : Rd → Rd, that is xn+1 = f(xn),n = 0, 1, 2, · · · .

1Current address: Department of Physics, Lancaster University, Lancaster, LA1 4YB, UK.



82 Dongsheng Liu
7, 2(2005)

Let Qdh denote the h-cube in R
d centered at origin, that is

Qdh = {x = (x1,x2, · · · ,xd) ∈ Rd : −
h

2
< xi ≤

h

2
, i = 1, 2, · · · ,d}

and for each q ∈ Qdh, let Lh,q = {q + hz : z ∈ Zd} be the uniform h-lattice in Rd
centered at q.

For q ∈ Qdh, we define the roundoff operator [.]h,q from Rd into Lh,q by [x]h,q =
Lh,q ∩ (x + Qdh) for x ∈ Rd, or equivalently by

[x]h,q = ([x1 −q1]h + q1, · · · , [xd −qd]h + qd)
where x = (x1,x2, · · · .xd),q = (q1,q2, · · · ,qd) and [y]h is scalar roundoff operator
defined by

[y]h = kh if (k −
1
2
)h ≤ y < (k + 1

2
)h.

Let f be a dynamical system in Rd. The map fh,q : Lh,q → Lh,q defined by
fh,q(x) = [f(x)]h,q, x ∈ Lh,q

is called Lh,q-discretization of f.
Now we give the definition of dynamical robustness [2]:

Given h > 0, q ∈ Qdh, and a compact set Ω ⊂ Rd, we say the triple (h,q, Ω) is dy-
namically robust if the discretization fh,q has a single equilibrium xh,q = fh,q(xh,q) ∈
Ω ∩Lh,q and

lim
n→∞

|fnh,q(x) −xh,q| = 0 ∀x ∈ Lh,q ∩ Ω.
In [2] the following question was raised: given f and a compact set Ω ∈ Rd, what

is the Lebesgue measure V (S(f,h, Ω)) of the set S(f,h, Ω) of points q ∈ Qdh for which
the triple (h,q, Ω) is dynamically robust?

They answered this question partially: when Ω is a parallel-polyhedron in Rd,
f is monotonic on Ω and satisfies some condition, they give a lower bound for
V (S(f,h, Ω)). In this paper we give a upper bound of V (S(f,h, Ω)) for f is monotonic
and satisfies certain condition on some compact subset Ω ∈ Rd.

2 Main Results
We give the semi-ordering in Rd: for x,y ∈ Rd, we say x ≤ y if xi ≤ yi for

i = 1, 2, · · · ,d and x < y if xi < yi for i = 1, 2, · · · ,d. We shall say f is monotonically
increasing on a set S ∈ Rd if f(x) ≤ f(y) for all x,y ∈ S with x ≤ y.

In the following we restrict attention to monotonically increasing functions, noting
that the monotonic decreasing case is handled similarly.

By the definition of dynamically robust, we have

Proposition 1 Let f be monotonic on the compact set Ω ⊂ Rd and suppose that
(h,q, Ω) is a dynamically robust, xh,q is the single equilibrium. ∀x ∈ Lh,q ∩ Ω, if
x ≥ xh,q, fh,q(x) = xh,q; if x ≤ xh,q, there exists k ∈ N such that fkh,q(x) = xh,q.



7, 2(2005)
A note on discrete monotonic dynamical systems 83

Proof. Because Ω is a compact subset of Rd, Lh,q ∩Ω is a finite set. For x ∈ Lh,q ∩Ω,
if x ≤ xh,q, let fh,q(x) = x(1), then x(1) = fh,q(x) ≤ fh,q(xh,q) = xh,q. If x(1) = xh,q
it is proved with k = 1. Otherwise we consider x(2) := fh,q(x(1)) ≤ fh,q(xh,q) = xh,q.
If x(2) = xh,q it is proved with k = 2. If x(2) 	= xh,q we can continue this process.
But Lh,q ∩Ω is finite set there exists a k ∈ N such that fkh,q(x) = fh,q(x(k−1)) = xh,q.
If x ≥ xh,q, and fh,q(x) 	= xh,q, by the monotonicty, fh,q(x) ≥ fh,q(xh,q) = xh,q. so
|fnh,q(x)−xh,q| ≥ |fh,q(x)−xh,q| > 0 for any n ∈ N, It is contradiction to the definition
of dynamically robust of (h,q, Ω). So we have fh,q(x) = xh,q.

In fact, ∀x ∈ Lh,q ∩ Ω there exists k ∈ N such that fkh,q(x) = xh,q.
Now we can estimate V (S(f,h, Ω)).

Theorem 1 Ω is a compact subset of Rd and satisfies: ∀q ∈ Qdh, there exist u1,q,u2,q ∈
Lh,q ∩Ω such that ∀x ∈ Lh,q ∩Ω, u1,q ≤ x ≤ u2,q. Let f be monotonic on the compact
set Ω ⊂ Rd and f(Ω) ⊂ Ω′ where Ω′ ⊂ Ω and satisfies ∀x = (x1, · · · ,xd) ∈ ∂Ω, the
boundary of Ω, and ∀x′ = (x′1, · · · ,x′d) ∈ Ω′, |xi −x′i| ≥ h2 , i = 1, 2, · · · ,d. we have

V (S(f,h, Ω)) ≤ L
L− 1h

d − 1
L− 1V ({x ∈ Ω : x−

h

2
≤ f(x) < x + h

2
})

where L = L1×L2×···×Ld and Li is determined by following: let li = |max{xi : x =
(x1, · · · ,xi, · · · ,xd) ∈ Ω}−min{xi : x = (x1, · · · ,xi, · · · ,xd) ∈ Ω}| and li = rh + p,
0 ≤ p < h then Li = r + 1.
Proof. The method of this proof is following that in [2]. Let F(h,q) = Lh,q ∩{x :
x− h

2
≤ f(x) < x+ h

2
} and k(h,q) = #{F(h,q)}. In order to carry on proof, we need

following

Lemma 1 [3].
∫

Qd
h

k(h,q)dq = V ({x : x− h
2
≤ f(x) < x + h

2
}).

We also need the following special case of the Birkhoff-Tarski Theorem

Lemma 2 [1]. Let g be a monotonic map of a finite set Γ ∈ Rd into itself. If g
satisfies g(x) ≥ x or g(x) ≤ x for x ∈ Γ, then the iterative sequence xn+1 = g(xn)
with x0 = x converge to the fixed point g(x∗) = x∗ ∈ Γ.
Remark :
(1). We can get the fixed point by following: take any x ∈ Γ with g(x) ≥ x or g(x) ≤ x
and iterate xn+1 = g(xn) with x0 = x, because Γ is finite, after a finite number of
steps we can get a fixed point.
(2). If fh,q has only one fixed point x∗, then x∗ = fkh,q(u1,q) and x

∗ = flh,q(u2,q) for
some k,l ∈ N. Since u1,q ≤ x ≤ u2,q it is easy to see fnh,q(x) = x∗, ∀x ∈ Lh,q ∩ Ω for
large n ∈ N.

The condition on f guarantees that fh,q is a mapping of Lh,q ∩ Ω into itself. The
elements of Fh,q are precisely the fixed points of fh,q. So it is easy to see k(h,q) ≥ 1



84 Dongsheng Liu
7, 2(2005)

from the lemma 2 because fh,q(u1,q) ≥ u1,q. By the definition of dynamically robust
and remark (2), we have q ∈ S(f,h, Ω) if and only if k(h,q) = 1. So V (S(f,h, Ω)) =
V ({q : k(h,q) = 1}). But

V ({q : k(h,q) = 1}) + V ({q : k(h,q) > 1}) = hd,
and k(h,q) at most equal to L = L1 ×···×Ld. By lemma 1, we have

V ({x : x− h
2
≤ f(x) < x + h

2
}) =

∫
Qd

h

k(h,q)dq

= V ({q : k(h,q) = 1}) +
L∑

i=2

i×V ({q : k(h,q) = i})

≤ V ({q : k(h,q) = 1}) + L×V ({q : k(h,q) > 1})
= V ({q : k(h,q) = 1}) + Lhd −L×V ({q : k(h,q) = 1})
= Lhd − (L− 1)V ({q : k(h,q) = 1})
= Lhd − (L− 1)V (S(f,h, Ω)).

So,

V (S(f,h, Ω)) ≤ L
L− 1h

d − 1
L− 1V ({x ∈ Ω,x−

h

2
≤ f(x) < x + h

2
}).

Under the condition of Theorem 2, the result of Theorem 1 in [2] still holds.
Combining with the Theorem 1 in [2], we get

Corollary 1 Under the condition of Theorem 2 below we have
Max{0, 2hd −V ({x ∈ Ω : x− h

2
≤ f(x) < x + h

2
})}≤ V (S(f,h, Ω))

≤ L
L−1h

d − 1
L−1V ({x ∈ Ω,x− h2 ≤ f(x) < x + h2}).

Remark : It is easy to see hd ≤ V ({x ∈ Ω : x− h
2
≤ f(x) < x + h

2
}) ≤ Lhd.

If f is not monotonic, the situation is complex. Following we give a special exam-
ple.

For g is a map from Ω into itself, we say x is a periodic point of g, if there exist
n ∈ N such that gn(x) = x. The least n which satisfies gn(x) = x is called period of
g at x.

Now we give the example.

Theorem 2 Let f be a map from a compact set Ω into Ω′. where Ω′ ⊂ Ω and
satisfies ∀x = (x1, · · · ,xd) ∈ ∂Ω, the boundary of Ω, and ∀x′ = (x′1, · · · ,x′d) ∈ Ω′,
|xi −x′i| ≥ h2 , i = 1, 2, · · · ,d. If ∀q ∈ Qdh, fh,q has no periodic point with period more
than 1, then

V (S(f,h, Ω)) ≤ L
L− 1h

d − 1
L− 1V ({x ∈ Ω : x−

h

2
≤ f(x) < x + h

2
})

where L = L1×L2×···×Ld and Li is determined by following: let li = |max{xi : x =
(x1, · · · ,xi, · · · ,xd) ∈ Ω}−min{xi : x = (x1, · · · ,xi, · · · ,xd) ∈ Ω}| and li = rh + p,
0 ≤ p < h then Li = r + 1.



7, 2(2005)
A note on discrete monotonic dynamical systems 85

Proof. We note

V ({q : k(h,q) = 0}) + V ({q : k(h,q) = 1}) + V ({q : k(h,q) > 1}) = hd,
so

V ({q : k(h,q) > 1}) ≤ hd −V ({q : k(h,q) = 1}).

Now we only need to prove following.

Lemma 3
q ∈ S(f,h, Ω) if and only if k(h,q) = 1.

Proof. Let q ∈ S(f,h, Ω), but k(h,q) 	= 1. Then k(h,q) = 0 or k(h,q) > 1. That
means dynamical system fh,q has no equilibrium or has at least two distinct equilibria,
it is contradition to q ∈ S(f,h, Ω).

If k(h,q) = 1, let xh,q is the unique fixed point of fh,q in Lh,q ∩Ω. ∀x1 ∈ Lh,q ∩Ω,
the condition of f guarantee fh,q(x1) ∈ Lh,q ∩ Ω. Let Fh,q(x1) := x2, if x2 	= x1, we
consider fh,q(x2) := x3. If x3 	= x2 then x3 	= x1 since fh,q has no periodic point with
period more than 1. We continue this process and get x1,x2, · · · ,∈ Lh,q ∩ Ω, which
are pairwise distinct. But Lh,q ∩ Ω is finite, so after finite number of steps, say N
steps, we have fNh,q(x1) = fh,q(xN ) = xN . But xh,q is the unique fixed point, we get
xN = xh,q and fNh,q(x1) = xh,q. So f

m
h,q(x1) = xh,q for any m ≥ N, that is

lim
n→∞

fnh,q(x) = xh,q, ∀x ∈ Lh,q ∩ Ω.

i.e., q ∈ S(f,h, Ω).
The next step of the proof is the same as that in Theorem 2.

Received: June 2004. Revised: August 2004.

References

[1] G. BIRKHOFF, Lattice Theory, AMS. Colloq. Publ. Vol 25, Amer.Math.
Soc., Providence (1967).

[2] P. DIAMOND, P. KLOEDEN, V. KOZYAKIN, AND A. POKROVSKII,
Monotonic Dynamicl Systems Under Spatial Discretization, Proc. of Amer.
Math. Soc, 126(7) (1998), 2169-2174.

[3] M. G. KENDALL AND P. A. P. MORAN, Geometrical Probability, C. Grif-
fin, London (1963).