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