THE ITERATION OF NONEXPANSIVE MAPS

Sjoerd M. Verduyn Lunel

Abstract For each n ≥ 1 we use the concept of “admissible arrays on n symbols” to define a set of positive integers Q(n) which is determined solely by number theoretical and combinatorial constraints. The set Q(n) is intimately connected to the set of periods of periodic points under iteration of nonexpansive maps. This paper provides a guide of recent joint work of the author with Roger Nussbaum and Michael Scheutzow.

1 Introduction

In this section we present a number of examples and some motivation to study the large time behaviour of discrete dynamical systems defined by iterating nonexpansive maps.

Let K^{n} denote the positive orthant in ℝ^{n}, M = (m_{ij}) be a nonnegative n × ncolumn stochastic matrix, i.e., ∑_{i=1}^{n} m_{ij} = 1 for 1 ≤ j ≤ n, m_{ij} ≥ 0. Consider the discrete dynamical system

x(k + 1) = Mx(k)  (1.1)

for k = 0, 1, 2, … with x(0) = x_{0}, where x : ℕ → ℝ and x_{0} ∈ K^{n} is given. The large time behaviour of the orbits of Eq. (1.1) follows from the Perron-Frobenius theory [7] for matrices with nonnegative entries. In fact, for every x_{0} ∈ K^{n}, there exists ξ = ξ(x_{0}) ∈ K^{n} and an integer p = p(x_{0}) such that M^{p}ξ = ξ, M^{j}ξ ≠ ξ, 1 ≤ j < p, and

lim_{j→∞} M^{jp}x_{0} = ξ.  (1.2)

In other words, all orbits of Eq. (1.1) approach periodic points. Furthermore, the possible minimal periods of the periodic points that can arise, are precisely the orders of the elements of the symmetric group on n letters. More general, if A is a nonnegative matrix with spectral radius equal to one, then all bounded orbits of x(k +1) = Ax(k), approach periodic points and the possible minimal periods of the periodic points that can arise are again precisely the orders of the elements of the symmetric group on n letters. This result, in particular, implies that the large time dynamics of bounded orbits of x(k + 1) = Ax(k) is as complex as iterating a permutation matrix. For references and a proof of these results we refer to Section 9 of [14].

Dynamical systems of type (1.1) arise often in applications. An element x ∈ K^{n} may be interpreted as the distribution of mass over finitely many containers C_{i}, i.e., for 1 ≤ i ≤ n, the i^{th}-coordinate of x denotes the mass in container C_{i}. The vector Mx is the distribution of mass over the containers after one time unit. Property (1.2) may now be interpreted as follows, starting with any initial distribution of mass over the containers, one will eventually approach a periodic procedure how to redistribute the mass over the containers. This linear model of diffusion of mass is rather special, for example, the mass sitting at the top of container C_{i} is moved in exactly the same way as the mass at the bottom of container C_{i}.

A simple nonlinear diffusion model that eliminates this special feature of linear models can be constructed as follows. Suppose that with each container C_{i}, 1 ≤ i ≤ n, we associate infinitely many containers C_{ik} of finite volume a_{ik} with ∑_{k=1}^{∞} a_{ik} = ∞. The rule of the movement of sand between the containers now consists of two steps. Pour the sand from container C_{i} into container C_{i1} until container C_{i1} is full or container C_{i} is empty. Next repeat the same procedure with C_{ik} for k > 1, until there is no more sand left in container C_{i}. If M_{ik}(x) denotes the volume of sand in container C_{ik}, then

M_{ik}(x) = min(max(x_{i} − ∑_{j=1}^{k−1} a_{ij}, 0), a_{ik}).  (1.3)

We carry out this procedure for each of the containers C_{i}, 1 ≤ i ≤ n. After the first step all containers C_{i} are empty. In the next step we redistribute the sand in the containers C_{ik} over the containers C_{i} according to a fixed rule

γ : {1, 2, …, n} × ℕ → {1, 2, …, n},  (1.4)

and the sand from container C_{ik} is poured into container C_{γ(i,k)}.

If y_{j} denotes the total amount of sand in C_{j} after these steps are completed, then

y_{j} = ∑_{γ(i,k)=j} M_{ik}(x).  (1.5)

Equations (1.3)–(1.5) define a map R_{γ} : K^{n} → K^{n}, where y_{j} is the j^{th}-coordinate of R_{γ}(x). It is easy to see that R_{γ} preserves total mass, i.e.,

∑_{j=1}^{n} R_{γ}(x)_{j} = ∑_{j=1}^{n} x_{j},

and is order preserving, i.e., x ≤ y implies R_{γ}(x) ≤ R_{γ}(y), where x ≤ y if and only if y − x ∈ K^{n}. The map R_{γ} defined by Eq. (1.3)–(1.5) is a special example of a nonlinear diffusion model studied in [1].

Let F : K^{n} → K^{n} be a nonlinear map which preserves total mass and is orderpreserving. From a result by Crandall and Tartar [2], it follows that F is l_{1}-norm nonexpansive, i.e., ∥F x − F y∥_{1} ≤ ∥x − y∥_{1}, where ∥x∥_{1} := ∑_{j=1}^{n} |x_{j}|. Akcoglu and Krengel [1] proved that if F is l_{1}-norm nonexpansive and has a bounded orbit (i.e., (∥F^{j}x_{0}∥)_{j=1}^{∞} is bounded for some x_{0} ∈ K^{n}), then all orbits under iteration of F converge to periodic orbits, that is, for every x_{0} ∈ K^{n} there exists ξ = ξ(x_{0}) and an integer p = p(x_{0}) such that F^{p}(ξ) = ξ, F^{j}(ξ) ≠ ξ, 1 ≤ j < p, and

lim_{j→∞} F^{jp}(x_{0}) = ξ.  (1.6)

Furthermore, the possible minimal periods p are a priori bounded by n!. This result suggests the importance of understanding the periodic points of l_{1}-norm nonexpansive maps and it marks the beginning of a large amount of work in this direction (see [10] and the references given there).

Define F_{3}(n) to be the collection of maps f : K^{n} → K^{n} which are nonexpansive in the l_{1}-norm and satisfy f(0) = 0. Scheutzow [16] showed that the minimal period p of a periodic point ξ of a map f ∈ F_{3}(n) is less than or equal to the least common multiple of the integers from 1 up to n, p ≤ lcm (1, 2, 3, …, n). Nussbaum [10] showed that this upper bound is in general not optimal and determined, for 1 ≤ n ≤ 32, the largest possible minimal period of a periodic point of a map f ∈ F_{3}(n).

In this paper we shall describe recent joint work with Roger Nussbaum and Michael Scheutzow [13, 14] building on earlier work in [12]. As a consequence of our main result we have the following remarkable fact. The possible periods of periodic points of a map f ∈ F_{3}(n) that can occur, can be realized in the map R_{γ} : K^{n} → K^{n} defined by Eq. (1.3)–(1.5) for an appropriate choice of the function γ. So the large time behaviour of bounded orbits of x(k + 1) = F (x(k)) is as complex as iterating a map R_{γ}.

This paper consists of four sections. In Section 2 we define some classes of maps and present our main result. In Section 3 we shall discuss and illustrate how to compute the possible periods of periodic points of maps f ∈ F_{3}(n) explicitly. In Section 4 we present some results from work in progress and discuss some open and related problems.

2 Definitions and the main result

The cone K^{n} = {x ∈ ℝ^{n} | x_{i} ≥ 0, 1 ≤ i ≤ n} induces a partial ordering by x ≤ y if and only if y − x ∈ K^{n}. A map f : D ⊂ ℝ^{n} → ℝ^{n} is order-preserving if f(x) ≤ f(y) for all x, y ∈ D with x ≤ y. If f_{j}(x) denotes the j^{th} coordinate of f(x), then f is called integral-preserving if

∑_{j=1}^{n} f_{j}(x) = ∑_{j=1}^{n} x_{j} for all x ∈ D.

We start to define some refinements of the class of maps F_{3}(n).

Definition 2.1 Define u = (1, 1, …, 1) ∈ ℝ^{n} and consider the following conditions on maps f : K^{n} → K^{n}:

(1) f(0) = 0,

(2) f is order-preserving,

(3) f is integral-preserving,

(4) f is nonexpansive with respect to the l_{1}-norm,

(5) f(λu) = λu for all λ > 0, We define sets of maps F_{j}(n), 1 ≤ j ≤ 3, by

F_{1}(n) = {f : K^{n} → K^{n} | f satisfies (1), (2), (3) and (5)},
F_{2}(n) = {f : K^{n} → K^{n} | f satisfies (1), (2) and (3)},
F_{3}(n) = {f : K^{n} → K^{n} | f satisfies (1) and (4)}.

A proposition of Crandall and Tartar [2] implies that if f : K^{n} → K^{n} is integralpreserving, then it is order-preserving if and only if it is l_{1}-norm nonexpansive. Thus we see that

F_{1}(n) ⊂ F_{2}(n) ⊂ F_{3}(n).

If f : K^{n} → K^{n} is integral-preserving and order-preserving, one can easily check that f satisfies (5) if and only if f is sup-norm-decreasing, i.e., ∥f(x)∥_{∞} ≤ ∥x∥_{∞} for all x ∈ D. Using this characterization of F_{1}(n) and a result of Lin and Krengel [3], we see that if f ∈ F_{1}(n) and y ∈ K^{n} is a periodic point of f, then there is a permutation σ, depending on f and y, such that

f(y) = (y_{σ(1)}, y_{σ(2)}, …, y_{σ(n)}).

Examples of maps belonging to F_{1}(n) can be constructed as follows. Let σ and τ be permutations of the set {1, 2, 3, …, n}. Define the map f : K^{n} → K^{n} by

f(x)_{j} = min{x_{σ(j)}, 1} + max{x_{τ(j)}, 1} − 1, j = 1, 2, …. , n,

even for such simple looking examples it is not easy to determine the possible minimal periods of the periodic points of f.

In order to obtain more information about the possible periods, we define sets of positive integers P_{j}(n), 1 ≤ j ≤ 3, by

P_{j}(n) = {p ≥ 1 | ∃f ∈ F_{j}(n) and a periodic point of f

of minimal period p}.

Our theorems will describe the sets P_{2}(n) and P_{3}(n), precisely and provide considerable information about the set P_{1}(n).

Because F_{1}(n) ⊂ F_{2}(n) ⊂ F_{3}(n) we have, by definition,

P_{1}(n) ⊂ P_{2}(n) ⊂ P_{3}(n).  (2.7)

If S_{n} denotes the symmetric group on n symbols and σ an element of S_{n} then, by permutation of the coordinates, σ induces a linear map σ̂ that belongs to F_{1}(n) and it is easy to see that ξ = (1, 2, 3, …, n) ∈ K^{n} is a periodic point of minimal period p equal to the order of σ as an element of symmetric group S_{n}. Thus P_{1}(n) contains the set of all orders of elements of S_{n}. However, in general, is P_{1}(n) larger than the set of orders of elements of S_{n}.

By constructing special maps one can show (see [10] for P_{1}(n) and Section 8 of [14] for P_{2}(n)) that the sets P_{1}(n) and P_{2}(n) have the following properties Theorem 2.1 Let j = 1 or j = 2. If p_{1} ∈ P_{j}(n_{1}) and p_{2} ∈ P_{j}(n_{2}), then

lcm (p_{1}, p_{2}) ∈ P_{j}(n_{1} + n_{2}).

Furthermore, if p_{i} ∈ P_{j}(m) for 1 ≤ i ≤ r, then

rlcm (p_{1}, p_{2}, …, p_{r}) ∈ P_{j}(rm).

Claim (1) follows from concatenation of maps. If p_{i} ∈ P_{j}(n_{i}), i = 1, 2, there exist maps f_{i} ∈ F_{j}(n_{i}) with, respectively, periodic points ξ_{i} of minimal period p_{i}. The map F : K^{n_{1}+n_{2}} → K^{n_{1}+n_{2}} defined by F (x, y) = (f_{1}(x), f_{2}(y)) has a periodic point ξ = (ξ_{1}, ξ_{2}) of minimal period lcm (p_{1}, p_{2}). To prove the second claim, we use the following nontrivial observation. If there are maps f_{i} ∈ F_{j}(m) with, respectively, periodic points ξ_{i} of minimal period p_{i}, then there also exists a single map F ∈ F_{j}(m) with periodic points ξ̂_{i} of minimal period p_{i}, i = 1, 2, …, r, simultaneously. Assuming the existence of such a map F : K^{m} → K^{m} we can construct a map T : K^{rm} → K^{rm} as follows

T (x_{1}, x_{2}, …, x_{r}) = (F (x_{r}), x_{1}, …, x_{r−1})

that has a periodic point ξ = (ξ̂_{1}, …, ξ̂_{r}) of minimal period rlcm (p_{1}, p_{2}, …, p_{r}). For example, the map f : K^{4} → K^{4} given by

f(y_{1}, y_{2}, y_{3}, y_{4}) = (min{y_{3}, 1} + max{y_{4}, 1} − 1, y_{1}, y_{2}, max{y_{3}, 1} + min{y_{4}, 1} − 1)

belongs to F_{1}(4) and has periodic points (2, 1, 1, 1) and (1, 0, 0, 1) of minimal period, respectively, 4 and 3. Consequently, 2 × lcm {3, 4} = 24 ∈ P_{1}(8). Since 24 is not the order of an element of the symmetric group on eight symbols, a nonlinear map is needed to have a periodic point of minimal period 24 in K^{8}.

Also note that, since P_{j}(1) = {1}, one has that P_{j}(n) ⊂ P_{j}(n + 1) for all n ≥ 1 and if p ∈ P_{j}(n) and d|p, then d ∈ P_{j}(n) (j = 1, 2, 3).

To describe the set P_{3}(n) precisely, we use the notion of admissible arrays introduced by Nussbaum and Scheutzow [12].

Definition 2.2 Suppose that (L, ≺) is a finite, totally ordered set and that Σ is a finite set with n elements. Let ℤ denote the integers and for each i ∈ L, suppose that θ_{i} : ℤ → Σ is a map. We shall say that {θ_{i} : ℤ → Σ | i ∈ L} is an admissible array on n symbols if the maps θ_{i} satisfy the following conditions:

(i) For each i ∈ L, the map θ_{i} : ℤ → Σ is periodic of minimal period p_{i}, where 1 ≤ p_{i} ≤ n. Furthermore, for 1 ≤ j < k ≤ p_{i} we have θ_{i}(j) ≠ θ_{i}(k).

(ii) If ≺ denotes the ordering on L and m_{1} ≺ m_{2} ≺ ⋯ ≺ m_{r+1} is any given sequence of (r + 1) elements of L and if

θ_{m_{i}}(s_{i}) = θ_{m_{i+1}}(t_{i})

for 1 ≤ i ≤ r, then

∑_{i=1}^{r}(t_{i} − s_{i}) ≢ 0 mod ρ,

where ρ = gcd ({p_{m_{i}} | 1 ≤ i ≤ r + 1}).

The concept of an admissible array on n symbols depends on the ordering ≺ on L, but it has been observed in [12] that if |L| = m, we can assume that L = {i ∈ ℤ | 1 ≤ i ≤ m} with the usual ordering and Σ = {j ∈ ℤ | 1 ≤ j ≤ n}. An admissible array {θ_{i} : ℤ → Σ | i ∈ L} can be identified with a semi-infinite matrix (a_{ij}), i ∈ L, j ∈ ℤ, where a_{ij} = θ_{i}(j). For this reason, we shall sometimes talk about the “i^{th} row of an array”. We shall say that “an admissible array has m rows” if |L| = m.

The period of an admissible array {θ_{i} : ℤ → Σ | i ∈ L} is defined to be the least common multiple of the periods of the maps θ_{i}, i ∈ L.

Definition 2.3 Suppose that S = {q_{i} | 1 ≤ i ≤ m} is a set of positive integers with 1 ≤ q_{i} ≤ n for 1 ≤ i ≤ m and q_{i} ≠ q_{j} for 1 ≤ i < j ≤ m. We call S an array-admissible set for n if there exists an admissible array on n symbols {θ_{i} : ℤ → Σ | i ∈ L} such that θ_{i} has minimal period p_{i}, and a one-to-one map σ of {1, 2, …, m} onto L such that q_{i} = p_{σ(i)}.

Definition 2.4 Q(n) = {lcm (S) | S ⊂ {1, 2, …, n} is array-admissible for n}.

To become more familiar with admissible arrays and the set Q(n), we compute the sets Q(n) for 1 ≤ n ≤ 6 and refer to Section 3 for a systematic approach.

First observe that if p is a prime and p^{α} ∈ Q(n) for some α ≥ 0 and n ≥ 1, then p^{α} ≤ n. Furthermore, if q has the prime factorization q = p_{1}^{α_{1}} … p_{m}^{α_{m}} and ∑_{j=1}^{m} p_{j}^{α_{j}} ≤ n, then q ∈ Q(n) (the maps θ_{i} in the definition of an admissible array can be positioned in such a way that the ranges of the maps θ_{i} do not intersect and this implies that the second condition in the definition of an admissible array is void). This last observation implies that the orders of the elements of the symmetric group on n letters are contained in the set Q(n). These observations yield Q(1) = {1}, Q(2) = {1, 2} and Q(3) ⊂ {1, 2, 3, 6}. Can 6 ∈ Q(3)? For this we need an admissible array with two maps θ_{1} and θ_{2} with periods 2 and 3. Since n = 3 the intersection of ranges of θ_{1} and θ_{2} is nonempty. Hence there exist t_{1}, s_{1} such that θ_{1}(s_{1}) = θ_{2}(t_{1}) and the second condition in the definition of an admissible array yields t_{1} − s_{1} ≢ 0 mod 1. A contradiction. Thus Q(3) = {1, 2, 3}. Similarly Q(4) = {1, 2, 3, 4}, Q(5) = {1, 2, 3, 4, 5, 6} and Q(6) ⊂ {1, 2, 3, 4, 5, 6, 12}. Can 12 ∈ Q(6)? One cannot take an admissible array {θ_{1}, θ_{2}} with periods 3 and 4, but there exists an admissible array {θ_{1}, θ_{2}} with periods 4 and 6; define θ_{1}(j) = j mod 6 and θ_{2}(j) = j + 1 mod 4. So Q(6) = {1, 2, 3, 4, 5, 6, 12}

In earlier work Nussbaum and Scheutzow [12] showed that there is an intimate connection between the sets P_{i}(n), i = 1, 2, 3 and Q(n) which can be derived from the structure of the semilattice generated by a periodic orbit of a map in F_{i}(n), i = 1, 2, 3. To explain this connection we need some more definitions. If x, y ∈ ℝ^{n}, we define x ∧ y and x ∨ y in the standard way:

x ∧ y := z, z_{i} = min{x_{i}, y_{i}} for 1 ≤ i ≤ n
x ∨ y := w, w_{i} = max{x_{i}, y_{i}} for 1 ≤ i ≤ n.

If V ⊂ ℝ^{n}, V is called a lower semilattice if x ∧ y ∈ V whenever x ∈ V and y ∈ V. If A ⊂ ℝ^{n}, there is a minimal (in the sense of set inclusion) lower semilattice V ⊃ A, the lower semilattice generated by A. If |A| < ∞, it follows that |V | < ∞. If V is a lower semilattice, a map h : V → V is called a lower semilattice homomorphism of V if

h(x ∧ y) = h(x) ∧ h(y) for all x, y ∈ V.

If W ⊂ ℝ^{n} is a lower semilattice, h : W → W is a lower semilattice homomorphism of W and ξ ∈ W is a periodic point of minimal period p of h, we let V denote the finite lower semilattice generated by

A = {h^{j}(ξ) | 0 ≤ j < p}.

From the definitions it follows that h(V) ⊂ V and h^{p}(x) = x for all x ∈ V. In particular, h|V is a lower semilattice homomorphism, h|V is one-to-one, onto and

(h|V)^{−1} = h^{p−1}|V

is also a semilattice homomorphism of V.

The relevance of these ideas in our situation is indicated by the following theorem due to Scheutzow [16].

Theorem 2.2 Suppose that f ∈ F_{3}(n) and that ξ ∈ K^{n} is a periodic point of f of minimal period p. Let A = {f^{j}(ξ) | 0 ≤ j < p}. If V denotes the finite lower semilattice generated by A, then f(V) ⊂ V, f|V is a lower semilattice homomorphism of V, f^{p}(x) = x for all x ∈ V and (f|V)^{−1} = f^{p−1}|V is a lower semilattice homomorphism of V.

Definition 2.5 If f : D ⊂ ℝ^{n} → ℝ^{n}, we shall write f ∈ G_{1}(n) if and only if D is a lower semilattice f(D) ⊂ D and f is a lower semilattice homomorphism of D. We shall write p ∈ Q_{1}(n) if and only if there exists a map f ∈ G_{1}(n) and a periodic point ξ ∈ K^{n} of f of minimal period p.

From Theorem 2.2 it follows that P_{3}(n) ⊂ Q_{1}(n). Our main theorem [13] describes the situation precisely.

Theorem 2.3 For every positive integer n

P_{2}(n) = P_{3}(n) = Q_{1}(n) = Q(n).

The inclusion Q_{1}(n) ⊂ Q(n) follows from [12] and the inclusion Q(n) ⊂ P_{2}(n) is proved in [13] by explicitly constructing a map R_{γ} defined by Eq. (1.3)–(1.5) with a periodic point of minimal period q from a given admissible array {θ_{j}|j ∈ L} with period q.

A nontrivial consequence of the theorem is the observation that if q ∈ Q(n) and p divides q, then p ∈ Q(n). This allows us to define maximal elements, a p ∈ Q(n) is called maximal if there does not exist a q ∈ Q(n), q ≠ p and p divides q. For example, if we list only the maximal elements, then Q(6) consists of the elements 5 and 12. This observation is crucial in any attempt to compute the set Q(n) explicitly.

3 Computation of Q(n)

From our main result it follows that the set of positive integers Q(n) which is determined solely by number theoretical and combinatorial constraints is a central object of study. Its explicit computation turns out to be a highly nontrivial problem. In this section we shall describe some results from [14] which, in particular, allow the computation of Q(n) for n ≤ 50. We begin with a general definition.

Definition 3.1 We define inductively, for each n ≥ 1, a collection of positive integers P (n) by P (1) = {1} and, for n > 1, p ∈ P (n) if and only if either

(A) p = lcm (p_{1}, p_{2}), where p_{1} ∈ P (n_{1}), p_{2} ∈ P (n_{2}) and n_{1} and n_{2} are positive integers with n = n_{1} + n_{2} or

(B) n = rm for integers r > 1 and m ≥ 1 and p = rlcm (p_{1}, p_{2}, …, p_{r}), where p_{i} ∈ P (m) for 1 ≤ i ≤ r.

From Theorem 2.1, we obtain that

P (n) ⊂ P_{1}(n) ⊂ P_{2}(n).

Since from our main result, P_{2}(n) = Q(n), it follows that the set P (n) provides a “lower bound” for Q(n).

The set P (n) can easily be computed and in order to compute Q(n) it suffices to study the complement of P (n) in Q(n). In other words it suffices to compute the set

{lcm (S)|S ⊂ {1, 2, …, n} is array-admissible for n and lcm (S) ∉ P (n)}.

Since it seems rather difficult to compute Q(n) directly, we followed this approach in [14] to compute Q(n) explicitly for 1 ≤ n ≤ 50.

The following result is a corollary of Theorem 3.1 of [14] and plays a crucial role in this approach.

Theorem 3.1 Let S = {p_{i} | 1 ≤ i ≤ m + 1} be a collection of m + 1 distinct positive integers p_{i} with 1 ≤ p_{i} ≤ n. Assume that p_{i} + p_{j} > n for 1 ≤ i < j ≤ m + 1. Assume that S_{j} ⊂ S, 1 ≤ j ≤ μ are pairwise disjoint sets with S = ∪_{j=1}^{μ}S_{j}. For each j, 1 ≤ j ≤ μ, assume that there is an integer r_{j} > 1 such that

gcd (p, q)|r_{j} for all p ∈ S_{j} and all q ≠ p, q ∈ S.

Let s_{j} = |S_{j}|. If

∑_{j=1}^{μ} \frac{s_{j}}{r_{j}} > 1,

then S is not an array-admissible set for n.

This theorem motivates the following definition.

Definition 3.2 A set S ⊂ {1, 2, …, n} satisfies the generalized condition C for the integer n if S does not contain disjoint subsets Q and R with the following properties:

(i) gcd (α, β) = 1 for all α ∈ Q and β ∈ Q ∪ R with α ≠ β.

(ii) α + β > n^{∗} := n − ∑_{γ∈Q} γ for all α, β ∈ R with α ≠ β.

(iii) there exist pairwise disjoint sets S_{j} ⊂ R, 1 ≤ j ≤ μ with ∪_{j=1}^{μ}S_{j} = R and such that for each j, 1 ≤ j ≤ μ, there is an integer r_{j} > 1 such that

gcd (p, q)|r_{j} for all p ∈ S_{j} and all q ≠ p, q ∈ R.

(iv) ∑_{j=1}^{μ} \frac{s_{j}}{r_{j}} > 1, where s_{j} = |S_{j}|.

So any set S ⊂ {1, 2, …, n} which does not satisfy generalized condition C is not array-admissible for n, and this condition can be effectively used to study the complement of P (n) in Q(n).

We mention two other necessary conditions for array-admissible sets that follow from Theorem 3.1 of [14].

Definition 3.3 A set S ⊂ {1, 2, …, n} satisfies condition D for the integer n if S does not contain a set R with the following properties:

(i) |R| = m + r − 1, where m ≥ 2 and r ≥ 2, and gcd (α, β)|r for all α, β ∈ R with α ≠ β.

(ii) there exist disjoint subsets R_{1} and R_{2} of R with R_{1} ∪ R_{2} = R, |R_{1}| = m and |R_{2}| = r − 1, ∑_{α∈R_{1}} α > n, and α + β > n for all α ∈ R and β ∈ R_{2}.

An example of a set that does not satisfy condition D for n = 21 is the set S = {9, 15, 16, 21}. In this case take R = {9, 15, 16, 21}, m = 2 and r = 3. Thus S = {9, 15, 16, 21} is not array-admissible for n = 21.

Definition 3.4 A set S ⊂ {1, 2, …, n} satisfies condition E for the integer n if S does not contain disjoint subsets Q and R with the following properties:

(i) gcd (α, β) = 1 for all α ∈ Q and β ∈ Q ∪ R with α ≠ β.

(ii) there is an integer r ≥ 1 such that gcd (α, β)|r for all α, β ∈ R with α ≠ β and

(iii) ∑_{β∈R} β > rn^{∗}, where n^{∗} := n − ∑_{α∈Q} α.

An example of a set that does not satisfy condition E for n equal to 24 is S = {4, 10, 14, 22} and this set is not array-admissible for n = 24.

An example of a set S that satisfies D and E but fails generalized condition C for n equal to 45 is given by

S = {24, 30, 33, 36, 39, 42}.

For if p_{1} = 24, p_{2} = 30, p_{3} = 33, p_{4} = 36, p_{5} = 39 and p_{6} = 42 then p_{i} + p_{j} > 45 for 1 ≤ i < j ≤ 6. If

S_{1} = {33, 39}, S_{2} = {30, 42}, S_{3} = {24, 36}

then s_{1} = |S_{1}| = 2, s_{2} = |S_{2}| = 2, s_{3} = |S_{3}| = 2 and

gcd (p, α)|3  for p ∈ S_{1} and all α ∈ S,
gcd (p, α)|6  for p ∈ S_{2} and all α ∈ S,
gcd (p, α)|12  for p ∈ S_{3} and all α ∈ S.

If we set r_{1} = 3, r_{2} = 6 and r_{3} = 12, then

∑_{j=1}^{2} \frac{s_{j}}{r_{j}} = \frac{2}{3} + \frac{2}{6} + \frac{2}{12} > 1.

Thus the set R = S_{1} ∪ S_{2} ∪ S_{3} satisfies the conditions (1)–(4) of Definition 3.2 with Q = ∅ and this shows that the generalized condition C fails for {24, 30, 33, 36, 39, 42} with n = 45 and the set S is not array-admissible for n = 45.

From the results in [14], it actually follows that

Theorem 3.2 For n ≤ 33 a set S ⊂ {1, 2, …, n} is array-admissible for n if and only if S satisfies the conditions generalized C, D and E given in Definition 3.2–3.4 for n.

This theorem presents a relatively simple procedure to explicitly compute Q(n) for 1 ≤ n ≤ 33. If n = 34 the set S = {12, 14, 16, 20, 34} satisfies generalized condition C, condition D and E, but it turns out that S is not array-admissible for n = 34. So further conditions are needed to describe the array-admissible sets.

With the aid of these ideas and some further results along the same lines, the following theorems were obtained in [14].

Theorem 3.3 If S ⊂ {1, 2, …, n} is a set such that lcm (S) has at most three prime factors, then lcm (S) ∈ Q(n) if and only if lcm (S) ∈ P (n). If S ⊂ {1, 2, …, n} is a set such that lcm (S) has four prime factors and gcd (S) > 1, then lcm (S) ∈ Q(n) if and only if lcm (S) ∈ P (n).

Theorem 3.4 For every positive integer n less than or equal to 50 we have

Q(n) = P (n).

The proof of this theorem is computer-assisted. Subsets S of the integers from 1 up to n are considered. If lcm (S) ∉ P (n), the conditions in Definitions 3.2–3.4 (and further generalizations) are tested. After this sieving procedure one is left with what are called “candidate exceptional sets” which might occur as the periods of an admissible array on n symbols. One then uses subtle arguments that none of these exceptional sets is actually array-admissible. The number 50 in the theorem has no particular meaning. Up to this integer, the number of candidate exceptional sets is quite small.

However, as the following result shows, in general, P (n) ≠ Q(n).

Theorem 3.5 There exist integers n and sets S such that lcm (S) ∈ Q(n) while lcm (S) ∉ P (n). In particular, q = 2^{3} × 7^{2} × 11 × 13 ∈ Q(78) and q ∈ P (79) but q ∉ P (78).

At present we do not know the smallest integer n such that P (n) ≠ Q(n). We also do not know whether P_{1}(n) = Q(n) in general. Until now all examples of integers q for which q ∈ Q(n) but q ∉ P (n) have the property that q ∈ P_{1}(n).

We conclude this section with the maximal elements of Q(n) for 1 ≤ n ≤ 27 and refer to [14] for the complete list and further information about the computation.

n  maximal elements of Q(n)
1  [1]
2  [2]
3  [2, 3]
4  [3, 4]
5  [4, 5, 6]
6  [5, 12]
7  [7, 10, 12]
8  [7, 10, 15, 24]
9  [14, 15, 18, 20, 24]
10  [14, 18, 21, 24, 40, 60]
11  [11, 18, 21, 24, 28, 40, 60]
12  [11, 28, 35, 36, 42, 120]
13  [13, 22, 35, 36, 84, 120]
14  [13, 22, 33, 36, 90, 120, 140, 168]
15  [26, 33, 44, 105, 120, 140, 168, 180]
16  [26, 39, 44, 55, 66, 126, 140, 180, 210, 240, 336]
17  [17, 39, 52, 55, 72, 126, 132, 180, 240, 280, 336, 420]
18  [17, 52, 65, 77, 78, 110, 132, 144, 240, 252, 280, 336, 360, 420]
19  [19, 34, 65, 77, 110, 144, 156, 165, 240, 252, 264, 336, 360, 840]
20  [19, 34, 51, 91, 130, 154, 156, 165, 198, 220, 252, 264, 720, 1680]
21  [38, 51, 68, 91, 130, 154, 195, 198, 231, 264, 312, 440, 660, 720, 1260, 1680]
22  [38, 57, 68, 85, 102, 182, 195, 234, 260, 312, 396, 462, 504, 528, 616, 720,
880, 1260, 1320, 1680]
23  [23, 57, 76, 85, 182, 204, 234, 273, 312, 385, 396, 462, 504, 520, 528, 616,
720, 780, 880, 1260, 1320, 1680]
24  [23, 76, 95, 114, 119, 143, 170, 204, 234, 273, 312, 364, 520, 616, 720, 770,
780, 792, 924, 1680, 2520, 2640]
25  [46, 95, 119, 143, 170, 228, 255, 300, 364, 408, 455, 468, 546, 720, 792, 990,
1008, 1540, 1560, 1680, 1848, 2520, 2640]
26  [46, 69, 133, 190, 228, 238, 255, 300, 306, 340, 408, 572, 720, 792, 910, 936,
1008, 1155, 1540, 1680, 1848, 1980, 2184, 2520, 2640, 3120]
27  [69, 92, 133, 190, 238, 285, 300, 306, 357, 408, 429, 456, 572, 680, 792, 936,
1020, 1080, 1170, 1386, 1512, 1820, 1980, 2184, 2310, 2640, 3080, 3120,
3696, 3780, 5040]

4 Conclusions

Even though the set P (n) is described explicitly, it is highly irregular as is the set of orders of the symmetric group on n letters. From recent work [15], it follows that on a log scale the largest elements of P (n) and Q(n) have the same asymptotics as the largest element of the set of orders of the symmetric group on n letters, i.e., if γ(n) denotes the largest element of Q(n) then

log γ(n) ∼ \sqrt{n log n}.

It would be interesting to study whether P (n), in some sense, can serve as a good approximation of Q(n) for general n.

Instead of considering l_{1}-norm nonexpansive maps f : K^{n} → K^{n} with f(0) = 0 and defining the set of minimal periods P_{3}(n) of all periodic points of such maps, we can consider l_{1}-norm nonexpansive maps f : ℝ^{n} → ℝ^{n} and define R(n), as the analogue of P_{3}(n), to be the set of all minimal periods of the periodic points of such maps that can arise. From Example 1.3 of [10] (see also [17]) it follows that

R(n) ⊂ Q(2n).

From work in progress by Bas Lemmens, it follows that R(n) ≠ Q(2n) in general. For example, if n = 3, we have seen 12 ∈ Q(6) but one can show that 12 ∉ R(3) and

R(3) = {1, 2, 3, 4, 5, 6}.

One can ask a question which is superficially related but actually very different. Consider maps f : D_{f} → D_{f} ⊂ ℝ^{n} such that f is l_{1}-norm nonexpansive. It is known, even if D_{f} is infinite, that such a map may not have an l_{1}-norm nonexpansive extension F : ℝ^{n} → ℝ^{n}. Define R̃(n) to be the set of positive integers p such that there exists an l_{1}-norm nonexpansive map f : D_{f} → D_{f} which has a periodic point of minimal period p. For n ≥ 3 one expects R̃(n) to be strictly larger than R(n). From recent work [4], it actually follows that 8 and 12 belong to R̃(3) while the elements of R(3) are less than or equal to 6. Can one characterize R̃(n) precisely by number theoretical and combinatorial constraints? An upper bound of n!2^{2^{n}} for elements of R̃(n) has been obtained by Misiurewicz [8], but this estimate is probably far from sharp (see [4] for further details).

Finally, it should be mentioned that the l_{1}-norm is not essential as a starting point for these results. In fact, for any polyhedral norm on a finite dimensional vector space V and any nonexpansive map F : V → V with a bounded orbit, it follows that all orbits under iteration of F converge to periodic orbits. Furthermore, the set of possible minimal periods is a finite set. In particular, the sup-norm has attracted a lot of attention. See [1, 5, 6, 9, 18] and the references given there, for more information and results.

References

[1] Akcoglu, M.A. and U. Krengel, Nonlinear models of diffusion on a finite space, Prob. Th. Rel. Fields 76 (1987), 411–420.

[2] Crandall, M.G. and L. Tartar, Some relations between nonexpansive and order preserving mappings, Proc. Amer. Math. Soc. 78 (1980), 385–391.

[3] Krengel, U. and M. Lin, Order preserving nonexpansive operators in L_{1}, Israel J. Mathematics 58 (1987), 170–192.

[4] Lemmens, B., R.D. Nussbaum and S.M. Verduyn Lunel, Lower and upper bounds for ω-limit sets of nonexpansive maps, Preprint, Vrije Universiteit, Amsterdam.

[5] Lyons, R. and R.D. Nussbaum, On transitive and commutative finite groups of isometries, pp. 189–228 in Fixed Point Theory and Applications, (K.-K. Tan, ed.), World Scientific, Singapore, 1992.

[6] Martus, P., Asymptotic properties of nonstationary operator sequences in the nonlinear case, Ph.D. dissertation, Friedrich-Alexander Univ, Erlangen-Nürnberg, 1989.

[7] Minc, H. Nonnegative Matrices, John Wiley and Sons, New York, 1988.

[8] Misiurewicz, M., Rigid sets in finite dimensional l_{1}-spaces, Report, Mathematica Göttingensis Schriftenreihe des Sonderforschungsbereichs Geometrie und Analysis, Heft 45, 1987.

[9] Nussbaum, R.D., Omega limit sets of nonexpansive maps: finiteness and cardinality estimates, Diff. Integral Equations 3 (1990), 523–540.

[10] Nussbaum, R.D., Estimates of the periods of periodic points of nonexpansive operators, Israel J. Math. 76 (1991), 345–380.

[11] Nussbaum, R.D., A nonlinear generalization of Perron-Frobenius theory and periodic points of nonexpansive maps, pp. 183–198 in Recent developments in optimization theory and nonlinear analysis, (Y. Censor and S. Reich, ed.), Contemporary Mathematics, vol. 204, American Math. Society, Providence, R.I., 1997.

[12] Nussbaum, R.D. and M. Scheutzow, Admissible arrays and periodic points of nonexpansive maps, Journal of the London Math. Soc. 58 (1998), 526–544.

[13] Nussbaum, R.D., M. Scheutzow and S.M. Verduyn Lunel, Periodic points of nonexpansive maps and nonlinear generalizations of the Perron-Frobenius theory, Selecta Math. (N.S.) 4 (1998), 1–41.

[14] Nussbaum, R.D. and S.M. Verduyn Lunel, Generalizations of the Perron-Frobenius theorem for nonlinear maps, Memoirs of the American Mathematical Society 138 (1999), number 659, 1–98.

[15] Nussbaum, R.D. and S.M. Verduyn Lunel, Asymptotic estimates for periods of nonexpansive maps, In preparation.

[16] Scheutzow, M., Periods of nonexpansive operators on finite l_{1}-spaces, European J. Combinatorics 9 (1988), 73–81.

[17] Scheutzow, M., Corrections to periods of nonexpansive operators on finite l_{1}- spaces, European J. Combinatorics 12 (1991), 183.

[18] Weller, D., Hilbert’s metric, part metric and self mappings of a cone, Ph.D. dissertation, Univ. of Bremen, Germany, 1987.

Faculteit der Exacte Wetenschappen Vrije Universiteit Amsterdam and Mathematisch Instituut Universiteit Leiden e-mail: verduyn@math.leidenuniv.nl