3. MORE PROPERTIE S O F ADMISSIBLE ARRAYS 15
For j 1, define sets Sj and integers Tj by
Tj
=r(S\ JU1 Si), where SQ = 0, (3.19)
and
Sj = {peS\ 'u 1 Si | gcd(p, q)\rj for all q G 5, q ^ p}. (3.20)
By construction the sets Sj are pairwise disjoint, Tj r^ for j k and there exists
an integer \i so that S = U^=1 Sj. One can verify
Sj =
{p€S\JUQSi\r({p})=rj}
and use this fact to verify that rj\s for all s Sj.
For example, if S = {24,32,40,44,46}, then n = 2 and Si = {46}, r2 = 4 and
S2 = {44}, r3=S and S3 = {24,32,40}.
To apply the generalized condition C we set, if r\ = 1, Q = Si and R = U^=2Sj
and if 1, Q = 0 and R = U^=15j. It is easy to see that condition (1) and
(3) of Definition 3.4 are satisfied and to test the generalized condition C, with this
collection of subsets, it remains to verify conditions (2) and (4) of Definition 3.5. In
the computer program (see Appendix A) that verifies the generalized condition C
for a set S we shall make use of this standard construction for the sets Sj. Another
application is the following theorem.
THEOREM
3.7. Let S C E be array-admissible for n and assume {in the nota-
tion of Remark 3.2) that BpC\Bq ^ 0 for all p,q e S. Write S = U^=1Sj according
to the standard decomposition, where Sj is given by (3.20) and Tj by (3.19). Set
ro = 1. //
rj-i\rj forl JV,
then lcm(S) e P(n).
PROOF .
First note that from the properties of admissible arrays it follows that
gcd(S) 1. Therefore Tj 1 for 1 j /i and we can set Q = 0 and R = \jf=1Sj.
Define integers lj by Tj = IjTj-i, 1 j \±. Since BPD Bq j^ $ for all p, q G S it
follows from Corollary 3.4 that
Y^ 1 where
Sj
= \Sj\. (3.21)
i = i rj
We claim that there exists a sequence of nonnegative integers ij, 1 j /J with
7o = 1 such that
Sj = lj-ilj - 7j, for 1 3 V- (3-22)
If j = 1, inequality (3.21) implies s\ r\ l\ and so we can choose 71 0 such
that si = 70Z1 —71- By induction, assume that there exist nonnegative integers jj
Previous Page Next Page