3. MORE PROPERTIE S OF ADMISSIBLE ARRAYS 13
It follows from Theorem 3.1 that
j = l T3
j = 1
rJ
and this contradiction proves the corollary.
A weaker version of Corollary 3.3 plays an important role in the computer
program that we use to find the array admissible sets (see Chapter 6).
COROLLARY
3.4. Let S = {pi | 1 i ra +1} be a collection ofm + 1 distinct
positive integers pi with 1 pi n. Assume thatpi+pj n for 1 i j m + 1.
Assume that Sj C S, 1 j [i are pairwise disjoint sets with S = Uj=i &j-
F°r
each j , 1 j ii, assume that there is an integer rj 1 such that
gcd(p, q)\rj for all p G Sj and all q ^ p,q G S.
Let Sj = | Sj |. //
£?! (3-17)
then S is not an array admissible set for n.
PROOF .
Let S = { i G Z | l i r a + l} with the usual ordering and suppose
that E is a set with |E| n. Assume, by way of contradiction, that S is array-
admissible for n. Then there exists an admissible array { ^ : Z E | Z G S ' } and
a permutation a of S such that Oi has minimal period pi := pa(i)- If we define
Bi = {Oi(j) | j G Z}, the fact that pa^) + pa(j) n£oriijm + l implies
that Bi n Bj ^ 0 for 1 i j m + 1. We define Sj by
Sj = {a-1(i)\pieSj},
so \Sj\ = Sj, and observe that our hypotheses imply that if i G Sj then
gcd(pi-Upi)\rj a n d gcdG5i,j3i+i)|?
Theorem 3.1 now implies
3 = 1 T
which is a contradiction.
Corollary 3.4 motivates the following definition.
DEFINITION 3.5. A set S C {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:
1. gcd(a, /?) = 1 for all a G Q and /? G Q U i? with a ^ /?.
2. a + /3 n* := n - Y,^eQ 7
f o r a11 a,P
^ R
w i t n
« 7^ /?•
3. there exist pairwise disjoint sets Sj C R, 1 j // with Uj=1Sj = R and
such that for each j , 1 j /x, there is an integer rj 1 such that
gcd(p, q)\rj for all p G Sj and all q ^ p, # G i?.
4. E ^ = i ^ l , where Sj = \Sj\.
Previous Page Next Page