4 GENERALIZATIONS OF THE PERRON-FROBENIUS THEOREM
From Theorem 1.4, we see that
P ( n ) c P i ( n ) c P
2
( n ) c P
3
( n ) .
Thus P(n) provides a "lower bound" for Pi(n) for i = 1,2,3.
In Chapter 4, we shall prove a number of properties of P(n) and give a computer
program to compute P(n) explicitly.
To obtain an "upper bound" for P${n) we use the notion of admissible arrays
introduced by Nussbaum and Scheutzow [13].
DEFINITION
1.7. Suppose that (L, -) is a finite, totally ordered set and that
E is a finite set with n elements. Let Z denote the integers and for each i G L,
suppose that Oi : Z » E is a map. We shall say that {Oi : Z E | i G L} is an
admissible array on n symbols if the maps Oi satisfy the following conditions:
1. For each i G L, the map Oi : Z E is periodic of minimal period p*, where
1 Pi ft- Furthermore, for 1 j k pi we have Oi(j) ^ Oi(k).
2. If - denotes the ordering on L and rai - ra2 - - m
r +
i is any given
sequence of (r + 1) elements of L and if
"mi\Si)
=
" m ^ i ( n j
for 1 i r, then
r
^ ( t i
- Si) ^ 0 mod /,
where p = gcd({pmi | 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 [13] that if \L\ = m, we can assume that
L = {ieZ\li m} with the usual ordering and E = {j G Z | 1 j n}.
An admissible array {Oi : Z E | i G L} can be identified with a semi-infinite
matrix (a^), i G L, j G Z, where a^ = #i(j). For this reason, we shall sometimes
talk about the "ith row of an array" (which can be identified with Oi) or "the
period of the
ith
row" (which is the minimal period pi of Oi). We shall say that "an
admissible array has m rows" if \L\ m.
If {Oi : Z •— » E I i G I/} is an admissible array on n symbols, L\ C L and Li
inherits its ordering from that on L, then {^ \ i £ Li} is also an admissible array
and is called a subarray of {Oi \ i G L}.
If pi for i G L denote the periods of an admissible array {Oi : Z E | i G L},
we are interested in the integer lcm({pi | i G L}).
DEFINITION
1.8. Suppose that S = {qi \ 1 i m} is a set of positive integers
with 1 qi n for 1 i m and qi ^ qj for 1 i j m. We shall say that
5 is an array-admissible set for n if there exists a totally ordered set (L, -) with
\L\ = m, an admissible array on n symbols {Oi : Z » E | i G L} such that ^^ has
minimal period p^, and a one-to-one map aof{ieZ\li m} onto L such
that 2 i =Pa(i)-
DEFINITION 1.9. Q(n) = {lcm(5) | S is array-admissible for n}.
In earlier work Nussbaum and Scheutzow [13] showed that the connection be-
tween the sets Pi(n), i = 1, 2,3 and Q(n) can be derived from the structure of the
semilattice generated by a periodic orbit of a map in ^i(n), i = 1,2,3. For the sake
Previous Page Next Page