14
GENERALIZATIONS OF THE PERRON-FROBENIUS THEOREM
Corollary 3.4 and the fact that Bq D Bp = 0 whenever p ^ q and gcd(p, q) = 1
imply that any set S C {1, 2,.. . , n} which does not satisfy the generalized condition
C is not array-admissible for n.
An example of a set S that satisfies condition A, B, C, D and E but fails the
generalized condition C for n equal to 45 is given by
S = {24,30,33,36,39,42}.
For if pi = 24, p2 = 30, p
3
= 33, p4 = 36, p5 = 39and p6 = 42 then pi + pj 45
for1 i j 6. If
Si = {33,39}, S2 = {24,30,36,42},
then si = \Si\ = 2, s2 = \S2\ = 4 and
gcd(p, a) 13 for p G Si and all a G 5,
gcd(p, a) 16 for p e S2 and all a G &
If we set ri = 3 and r2 = 6,
E s? 2 4 . ,
J7 = l ^
Thus the set R = SiUS2 satisfies the conditions (l)-(4) of Definition 3.5 with Q 0
and this shows that the generalized condition C fails for {24,30,33,36,39,42} with
n = 45.
Another type of example is given by the set {24,32,40,44,46}. This set also
satisfies condition A, B, C, D and E but fails the generalized condition C for n
equal to 47. If
S1 = {46}, S2 = {44}, S3 = {24,32,40} and n = 2, r2 = 4, r3 - 8,
then R S\U S2U Ss satisfies the conditions (l)-(4) of Definition 3.5 with Q = 0
and this shows that the generalized condition C fails for {24,32,40,44,46} with
n = 47.
It is easy to verify that the conditions A, B and C (see Definitions 2.1-2.3) are
contained in the generalized condition C, and actually, relatively straightforward
arguments also show that conditions D and E of Chapter 2 follow from Theorem
3.1.
To summarize, we state the following result:
THEOREM
3.6. If a set S C {1,2,... ,n} is array-admissible for n, then S
satisfies the generalized condition C and conditions D and E for n.
The generalized condition C requires the existence of pairwise disjoint sets Sj,
1 J' H with the property that there exist integers Tj 1 such that
gcd(p, q)\rj for all p G Sj and q G U^=1Sj, p ^ q.
For a set S C £ there exists a standard construction for a useful family of such
subsets.
For a given subset T of 5, define r(T) by
r{T) = min (lcm{gcd(p, q) \qeS,q^p}). (3.18)
Previous Page Next Page