Some Pairwise Balanced Designs

Malcolm Greig Greig Consulting 207-170 East Fifth St. North Vancouver BC, Canada, V7L 4L4

greig@sfu.ca

Submitted: Oct. 6, 1998; Accepted: Oct. 23, 1999.

Abstract

A pairwise balanced design, B(K; v), is a block design on v points, with block sizes taken from K, and with every pair of points occurring in a unique block; for a fixed K, B(K) is the set of all v for which a B(K; v) exists.

A set, S, is a PBD-basis for the set, T, if T = B(S). Let N_{a(m)} = {n : n ≡ a mod m}, and N_{≥m} = {n : n ≥ m}; with Q the corresponding restriction of N to prime powers.

This paper addresses the existence of three PBD-basis sets.

1. It is shown that Q_{1(8)} is a basis for N_{1(8)} \ E, where E is a set of 5 definite and 117 possible exceptions.

2. We construct a 78 element basis for N_{1(8)} with, at most, 64 inessential elements.

3. Bennett and Zhu have shown that Q_{≥8} is a basis for N_{≥8} \ E′, where E′ is a set of 43 definite and 606 possible exceptions. Their result is improved to 48 definite and 470 possible exceptions. (Constructions for 35 of these possible exceptions are known.)

Finally, we provide brief details of some improvements and corrections to the generating/exception sets published in The CRC Handbook of Combinatorial Designs. Key words and phrases: BIBD, Pairwise Balanced Design AMS subject classifications: Primary 05B05.

1 Introduction

A pairwise balanced design, B(K; v), is a block design on v points, with block sizes taken from K, and with every pair of points occurring in a unique block; for a fixed K, B(K) is the set of all v for which a B(K; v) exists.

A set, S, is a PBD-basis for the set, T, if T = B(S). Let N_{a(m)} = {n : n ≡ a mod m}, and N_{≥m} = {n : n ≥ m}; with Q the corresponding restriction of N to prime powers.

This paper addresses the existence of three PBD-basis sets. The opening sections deal with useful known results and more general constructions. In Section 5, we give constructions that are particularly useful for the first of our two problems, then in Section 6, we show that Q_{1(8)} is a basis for N_{1(8)} \ E, where E is a set of 5 definite and 117 possible exceptions; an application of this result is given in [5]. In Section 7, we construct a 78 element basis for N_{1(8)} with, at least, 14 essential elements. In Section 8, we look at what Q_{≥8} is a basis for. Bennett and Zhu have already tackled the last problem, and give some applications [9, 13]; they have shown that Q_{≥8} is a basis for N_{≥8} \ E′, where E′ is a set of 43 definite and 606 possible exceptions. Their result is improved to 48 definite and 470 possible exceptions. Results (without proofs) from this paper were incorporated into [12, Tables III.3.18–19].

Finally, in Section 9, we provide brief details of some improvements and corrections to the generating/exception sets published in The CRC Handbook of Combinatorial Designs, specifically [12, Tables III.3.17–19].

Although we sometimes give some non-existence results (phrased as definite exceptions and essential elements above) we will not establish these here; they require techniques quite different from the ones we are using here. We will merely note that most of them can be established by some results of Wilson’s [41]: the integrality conditions, and the bound on the size of a flat; these conditions are also given in [12, Lemma 3.2, Theorem 3.1.2].

Remark 1.1 Wilson’s integrality conditions imply that if S ⊂ N_{1(m)}, and if a B(S; v) exists, then it follows that v ∈ N_{1(m)}.

2 Notation

The notation we use is fairly straightforward. A K-GDD is a group divisible design with block sizes taken from K, and with a group size vector of {G_{1}, G_{2}, …, G_{n}}; we will usually write the group size vector in exponential notation. We will only be concerned with the λ = 1 case; i.e., a pair of elements from different groups occurs in one block of the design, whilst a pair of elements from the same group appears in no block.

A pairwise balanced block design is a GDD with a group size vector of 1^{v}; it is denoted by B(K; v). If the block size is uniform, with K = {k} then this block design is referred to as a balanced incomplete block design (a BIBD), and denoted by B(k; v).

If a B(k; v) exists, then the quantity r = (v − 1)/(k − 1) is called the replication number of the BIBD, and we say that r ∈ RN(k).

A transversal design, T D(k; t), is a {k}-GDD of group type t^{k}.

The set of all v for which a B(K; v) exists is denoted by B(K), and a similar definition is used for T D(k).

The notation B(K ∪ {k^{∗}}; v) indicates there is exactly one block of size k in the design in addition to those of sizes from K (further blocks of size k can occur only if k ∈ K).

Resolvable designs are designs that admit a partition of the block set into subsets of blocks that contain every point exactly once. These designs are denoted by the prefix R.

If a RB(k; v) exists, then we say that r ∈ RRN(k), where RRN(k) ⊂ RN(k).

Some notation that is specific to a section will be introduced in that section.

One final notational convention we have adopted should be mentioned. We have labelled several lemmas by a one or two letter code. This is summarized in the key in the appendix, which gives the symbolic parameters used in the lemma where the code is introduced, but numeric values are substituted in the table of constructions. This device allows considerable compression of the table, yet retains all the information needed to verify the constructions.

3 Direct Constructions

We start this section by summarizing some well-known results in the first lemma.

Lemma 3.1 If q is a prime or prime power, then

1. q^{2} ∈ RB(q), and

2. q^{2} + q + 1 ∈ B(q + 1), and

3. q^{3} + 1 ∈ RB(q + 1), and

4. q^{3} + q^{2} + q + 1 ∈ RB(q + 1).

Proof : All these are standard results. The first two amount to the existence of the affine and projective geometries, AG(2, q) and P G(2, q). The resolvability of the unital design was shown by Bose (see [15, 26]), and the resolvability of the last design can be found in Lorimer [33].

Lemma 3.2 Embedded in P G(2, 2^{N}) is a set of v(n) = 2^{n}(2^{n}−1)2^{N−n}+2^{n} points whose incidences with the lines of the plane are all either 0 or 2^{n}. Furthermore, if m < n, the set of v(n) points contains a subset of v(m) points whose incidence with the lines of the plane is either 0 or 2^{m}.

Proof : The first part of this result was shown by Denniston [19]. Denniston considers an irreducible second order curve, Q(x, y) = ax^{2} + bxy + cy^{2} over GF (2^{N}) in the nonhomogeneous coordinates (x, y) of the plane. Let G be any additive sub-group of order 2^{n} of the additive group GF (2^{N}). Then the set of points satisfying Q(x, y) ⊂ G forms a Denniston arc, {v(n); {0, 2^{n}}}, in P G(2, 2^{N}) with v(n) = 2^{N+n} − 2^{N} + 2^{n}; note if we consider a sub-group H of order 2^{m} and take H ⊂ G, this yields a {v(m); {0, 2^{m}}}-arc whose points are a subset of the v(n) points, so that Denniston arcs can be taken to be nested.

Corollary 3.3 If k is a power of 2, and n is a non-negative integer, then k(k−1)2^{n}+k ∈ RB(k).

Proof : The resolvability was demonstrated by Seiden in the case n = 1, (see [39]), and her proof carries over to Denniston’s arcs. The device used is to consider a line that has zero incidence with the arc; the incidence of its points with the non-zero lines of the arc identifies the resolution classes.

Corollary 3.4 The following designs exist:

1. B({9, 17^{∗}}; 120 + 17 = 137 = 8 ∗ 17 + 1);

2. B({9, 33^{∗}}; 232 + 33 = 265 = 8 ∗ 33 + 1);

3. B({9, 65^{∗}}; 456 + 65 = 521 = 8 ∗ 65 + 1);

4. B({17, 33^{∗}}; 496 + 33 = 529 = 8 ∗ 66 + 1);

5. B({9, 17}; 273 − 120 = 153 = 8 ∗ 19 + 1);

6. B({17, 33}; 1057 − 496 = 561 = 8 ∗ 70 + 1);

7. B({9, 17, 33^{∗}}; 496 − 232 + 33 = 297 = 8 ∗ 37 + 1).

Proof : The first four examples are formed by adding a complete external line to the appropriate Denniston arc in planes of order 16, 32, 64 and 32. The next two designs are formed by taking the complements of the Denniston arcs used in parts 1. and 4. above. The final result comes from taking the difference of the two arcs of parts 2. and 4., in the plane of order 32, again adding a complete external line.

Corollary 3.5 The following designs exist:

1. B({8, 9, 16, 17, 27^{∗}}; 291);

2. B({8, 9, 16, 17, 31^{∗}}; 295); Proof : Again we use the 264 point difference of two Denniston arcs that we used in Corollary 3.4.7, and now we add an incomplete external line.

If we have a projective plane, P G(2, q), then we may generate a T D(q+1; q) from it by deleting a point, and using the lines through that point to generate groups. Since all the Desarguesian planes have ovals, we may consider how these oval points are distributed amongst the groups. Recall that if q is odd, then there are q + 1 points in the oval; (if D is the Singer difference set, then −D is such an oval). If q is even, with D = 2D, then we may augment this set, −D, of q + 1 points by the point {0} to get a set of q + 2 hyperoval points, which we will also term an oval.

Lemma 3.6 If q = 2t + 1 is an odd prime power, then we may form a T D(q + 1; q) such that the distribution of the oval points amongst the groups is of type 0^{1}1^{q} or 0^{t}1^{2}2^{t} or 0^{t+1}2^{t+1}. If q = 2t is an even prime power, then we may form a T D(q + 1; q) such that the distribution of the oval points amongst the groups is of type 1^{q+1} or 0^{t}2^{t+1}.

Proof : To demonstrate this in the odd case, we either delete an oval point, or a non-oval tangent point, or a non-tangent point, and note the number of external lines, tangents and secants that the deleted point lay on. For the plane of even order, we delete an oval point, or a non-oval point; there are no tangents here.

Lemma 3.7 {81, 585} ⊂ RB(9), and {73, 433, 577} ⊂ B(9).

Proof : The first three values follow from Lemma 3.1 using q = 8 or q = 9. The values 433 and 577 result from constructions by Abel [1] and Buratti [17].

Lemma 3.8 If t ∈ {1, 6, 7} or t is a power of 2, then 56t + 8 ∈ RB(8).

Proof : This follows from Lemma 3.1 using q = 8 or q = 7, or from Corollary 3.3 using k = 8.

Lemma 3.9 If q is a prime or prime power, and q ≡ 1 mod 8, and q ∉ {25, 89} and q < 4096, then 7q + 1 ∈ RB(8).

Proof : The results for q ∈ {9, 17} are given above. The remaining constructions were given by Greig [20]. It can be shown that the restriction q < 4096 is unneccessary, although we do not need that improvement here.

Lemma 3.10 The {9}-RGDD of type 3^{33} exists.

Proof : This design was constructed by Mathon; see [28].

The remaining basic designs we need are transversals. We will briefly summarize some well known results. the electronic journal of combinatorics 7 (2000), #R13 6

Lemma 3.11 If q is a prime or prime power, then q ∈ T D(q + 1). Lemma 3.12 If m ∈ T D(k + 1), then m ∈ T D(k). Lemma 3.13 If {m, n} ⊂ T D(k), then mn ∈ T D(k).

These last three lemmas can be combined to give a weaker version of MacNeish’s result [34]. Theorem 3.14 If m has no prime divisors less than k, then m ∈ T D(k + 1). Lemma 3.15 T D(k + 1) = RT D(k). Lemma 3.16 If t ≠ 3, then 8t ∈ T D(9), and if t ≠ 4, then 8t + 1 ∈ T D(9). Proof : See [3]; for Wojtas’ T D(9; 48) see [18].

Unless otherwise noted, all the TDs we need are from [3]. The remaining designs we need are incomplete transversal designs (ITDs). Loosely speaking, an ITD, written as T D(k; m) − T D(k; a), is a design that could be completed to a T D(k; m) by adding the blocks of a T D(k; a) to the ITD; we do not actually need to have a T D(k; a) to have an ITD. We have chosen to provide constructions for the ITDs we need, even though better values can sometimes be obtained from [4]. Lemma 3.17 If m ∈ T D(k), then the incomplete transversal T D(k; m) − T D(k; 1) exists. Proof : Delete one block of the TD to get the ITD.

The other two constructions of ITDs that we use are corollaries of Wilson’s basic construction [40]. Lemma 3.18 If m ∈ T D(10) and 0 ≤ n ≤ m, and {k, k + 1} ⊂ T D(9), then the incomplete transversal T D(9; km + n) − T D(9; n) exists. Lemma 3.19 If m ∈ T D(n) and 8 ≤ n, then the incomplete transversal T D(9; 8m + n − 8) − T D(9; n) exists.

4 General Constructions

Lemma 4.1 (Direct Product) If m ∈ T D(n), then mn ∈ B({m, n}). Proof : We just fill in the groups of the TD.

Theorem 4.2 Suppose we have a K-GDD with v points and a group size vector of {|G_{j}| : j = 1, …, g}, and, for the first g − 1 groups, we have a B(K ∪ {w^{∗}}; |G_{j}| + w) with 0 ≤ w, and, for the last group we have a B(K; |G_{g}| + w); then there exists a B(K; v + w).

Proof : This is a standard result; we add w infinite points, and when we fill the first g − 1 groups, we align the w block with the infinite points, and refrain from using it for these groups. Note that the resulting design does not contain a w block, unless, possibly, when w ∈ K.

Corollary 4.3 (Indirect Product) If (m − w) ∈ T D(n), and a B(K; m) containing a B(K; w) sub-design exists, (or a B(K; m) exists with w = 1), then n(m − w) + w ∈ B(K ∪ {n}).

Theorem 4.4 (Wilson’s Fundamental Construction) Suppose there is a “master” K −GDD with g groups and a group size vector of {|G_{j}| : j = 1, …, g}, and a weighting that assigns a positive weight of w(x) to each point x. Let W (B_{i}) be the weight vector of the i-th block. If, for every block B_{i}, we have a K′ − GDD with a group size vector of W (B_{i}), then there exists a K′ − GDD with a group size vector of {∑_{x∈G_{j}} w(x) : j = 1, …, g}.

Proof : See [41]. Also note that the blocks in the final design have cardinalities in K′, rather than K.

Theorem 4.5 If r ∈ RN(k), then a design with block size of k and a group vector of (k − 1)^{r} exists.

Proof : Deleting a point, and using its blocks as groups in a B(k; (k − 1)r + 1), gives the GDD; note that this construction can be reversed; (see [25]).

5 Specific Constructions

In this section, we start applying the results of the previous section to produce the tools for the second of the problems, that of constructing designs whose block sizes are in Q_{1(8)}, where Q_{1(8)} is the set of prime-powers congruent to 1 modulo 8. It will be convenient to define U_{1(8)} by:

t ∈ U_{1(8)} ⟺ 8t + 1 ∈ B(Q_{1(8)}).

Lemma 5.1 There exist {9}-GDDs of type 8^{9} and type 8^{10}.

Proof : Apply Theorem 4.5 to the 73 and 81 point designs of Lemma 3.7.

Lemma 5.2 If q = 8t + 1 ∈ RRN(8), then 56t + 8 ∈ RB(8), and 64t + 9 ∈ B({9, q^{∗}}), and there exists a {9}-GDD of type 8^{7t+1}(q − 1)^{1}, and there exists a {9, q^{∗}}-GDD of type 8^{q}.

Proof : Complete the RBIBD with q = 8t + 1 infinite points, and then delete either an infinite point, or a finite point, and use its lines to indicate the groups.

Theorem 5.3 If there exists a K-GDD on v points, with group sizes contained in M, and K ⊂ RN(9) ∪ (Q_{1(8)} \ {25, 89}), then M ⊂ U_{1(8)} implies v ∈ U_{1(8)}.

Proof : Give each point a weight of 8, and apply Wilson’s fundamental construction. The needed components come from Theorem 4.5 for RN(9), and Lemma 3.9 via Lemma 5.2 for the other block sizes. We fill in the groups with a point at infinity to obtain the required result.

Corollary 5.4 If there exists a {9, 10}-GDD on v points, with group sizes chosen from M, and M ⊂ U_{1(8)}, then v ∈ U_{1(8)}.

Lemma 5.5 (Code T) If m ∈ T D(10) and 0 ≤ n ≤ m and {m, n} ⊂ U_{1(8)}, then 9m + n ∈ U_{1(8)}.

Proof : Truncate one group of the transversal to size n, then use Corollary 5.4.

Concentrating on the points in the last block yields the “last spike” and “block deletion” constructions given below.

Lemma 5.6 (Code Ls) If m ∈ T D(n) and m ∈ U_{1(8)}, and n ≥ 9 and n ∈ Q_{1(8)} \ {25, 89}, then 9(m − 1) + n ∈ U_{1(8)}.

Proof : Remove m−1 points from n−9 groups of the transversal, retaining all the points of the last block, to give a {9, 10, n^{∗}}-GDD of type m^{9}1^{n−9}. Now use Theorem 5.3.

Lemma 5.7 (Code L) If m ∈ T D(n) and m ∈ Q_{1(8)} \ {25, 89}, and n ≥ 9 and n ∈ U_{1(8)}, then 9(m − 1) + n ∈ U_{1(8)}.

Proof : As in Lemma 5.7, we construct a {9, 10, n^{∗}}-GDD of type m^{9}1^{n−9}. Now fill in the groups and delete the big block to give a {9, 10, m}-GDD of type 1^{9m−9}n^{1}, and use Theorem 5.3.

Lemma 5.8 (Code BD) If m ∈ T D(10) and 9 ≤ n ≤ 10 and {m, m − 1} ⊂ U_{1(8)}, then 10m − n ∈ U_{1(8)}.

Proof : Remove n points from one block of the transversal, then use Corollary 5.4.

Remark 5.9 Note that if n = 10, then m ∈ U_{1(8)} is not needed.

Lemma 5.10 (Code R) If v ∈ RB(9) and 8n+1 ≤ v and n ∈ U_{1(8)}, then v+n ∈ U_{1(8)}.

Proof : Add n new points to the blocks of n resolution sets, then use Corollary 5.4.

Lemma 5.11 If m ∈ T D(k + 1), then:

1. there exists a {k + 1, m + 1}-GDD of type k^{m}m^{1};

2. there exists a {k + 1, m}-GDD of type k^{m}(m − 1)^{1}.

Proof : Take the transversal, and fill in groups with 1 or 0 points at infinity and then delete a finite point and use its blocks as groups to give the result.

Lemma 5.12 If k is a power of 2, then there exists a {k + 1, 2k + 1}-GDD on k(2k + 3) points, and this design has a group vector of k^{2k−1}(2k)^{2}.

Proof : In some ways, this lemma is a corollary of Lemma 3.2. The Seiden design can be embedded in P G(2, 2k). We now consider the non-Seiden points in P G(2, 2k), and delete one of these and use its blocks to define the groups.

Lemma 5.13 There exist {9, 17}-GDDs with group vectors of 8^{15}16^{1}, 8^{17}, 8^{16}16^{1}, 8^{17}16^{1} and 8^{15}16^{2}.

Proof : This follows from Lemma 5.2 with t = 2 (twice), from Lemma 5.11 with m = 16 and m = 17, and from Lemma 5.12.

Mullin et al. [38, Lemma 6.12], used a construction similar to Lemma 5.14. We could also adapt their Lemma 6.20, but this yields nothing new here, as we have a rich set of constructions in the next six lemmas, covering essentially the same ranges. Five of these constructions of these lemmas were used previously by Greig and Abel [22]; Lemma 5.16 (code B) is new.

Lemma 5.14 (Code A) If m ∈ T D(18) and 0 ≤ s ≤ t ≤ m and n = s + t, and {m, 2m, s, t} ⊂ U_{1(8)}, then 17m + n ∈ U_{1(8)}.

Proof : Truncate two groups to sizes s and t, and give the points of these truncated groups a weight of 8. Give the points of one other group weight 16 and give all the other points weight 8. The needed component group vectors are 8^{15}16^{1}, 8^{16}16^{1}, and 8^{17}16^{1}, and are obtained from Lemma 5.13, so we may apply Wilson’s fundamental construction to give a design with a group vector of (8m)^{15}(16m)^{1}(8s)^{1}(8t)^{1}. We fill these groups in with the aid of a point at infinity.

Remark 5.15 Note that, provided we took s = 0, we could relax the condition m ∈ T D(18) to m ∈ T D(17).

Lemma 5.16 (Code B) If m is a prime power with m ≥ 17, 0 ≤ t ≤ 17, n = 2t ≤ m + 1, and {m, m + 2} ⊂ U_{1(8)}, then 17m + n ∈ U_{1(8)}.

Proof : Using Lemma 3.6, we may construct a T D(17; m) with at least t groups containing a pair of oval points; give these t pairs of points a weight of 16, and give all the other points a weight of 8. The needed component group vectors are 8^{17}, 8^{16}16^{1}, and 8^{15}16^{2}, and are obtained from Lemma 5.13, so we may apply Wilson’s fundamental construction to give a design with a group vector of (8m)^{17−t}(8(m + 2))^{t}. We fill these groups in with the aid of a point at infinity.

Lemma 5.17 (Code C) If m ∈ T D(17) and 0 ≤ s ≤ t ≤ m and n = 2m + s + t, and {m, m + s, m + t} ⊂ U_{1(8)}, then 15m + n ∈ U_{1(8)}.

Proof : Give s points from one group a weight of 16, give t points from another group a weight of 16, and give all the other points a weight of 8. The needed component group vectors are 8^{17}, 8^{16}16^{1}, and 8^{15}16^{2}, and are obtained from Lemma 5.13, so we may apply Wilson’s fundamental construction to give a design with a group vector of (8m)^{15}(8m + 8s)^{1}(8m + 8t)^{1}. We fill these groups in with the aid of a point at infinity.

Lemma 5.18 (Code D) If m ∈ T D(17), 0 ≤ s+t ≤ m, n = s+2t, and {m, 2m, n} ⊂ U_{1(8)}, then 17m + n ∈ U_{1(8)}.

Proof : Give s points from one group a weight of 8, give t points from the same group a weight of 16, give the points of another group a weight of 16, and give the points of all the other 15 groups a weight of 8. The needed component group vectors are 8^{15}16^{1}, 8^{16}16^{1}, and 8^{15}16^{2}, and are obtained from Lemma 5.13, so we may apply Wilson’s fundamental construction to give a design with a group vector of (8m)^{15}(16m)^{1}(8s + 16t)^{1}. We fill these groups in with the aid of a point at infinity.

Lemma 5.19 (Code E) If m ∈ T D(17) and 1 ≤ s ≤ m and 1 ≤ t ≤ m and 15(s−1)+ t ≤ m and n = m+t, and {m+1, m+s, m+t} ⊂ U_{1(8)}, then 16(m+1)+(s−1)+n ∈ U_{1(8)}.

Proof : Give the points from the last block a weight of 16, give s − 1 other points from the first group a weight of 16, give t − 1 other points from the second group a weight of 16, and give all the other points a weight of 8. There are 15(s − 1) lines containing a pair of points with weight 16, one from group 1 and the other from groups 3 through 17; when assigning the extra t − 1 weight 16 points in the second group, we must avoid these lines; this is possible by hypothesis. The needed component group vectors are 8^{17}, 8^{16}16^{1}, 8^{15}16^{2}, and 16^{17}, and are obtained from Lemma 5.13, or from Lemma 3.8 with q = 16, so we may apply Wilson’s fundamental construction to give a design with a group vector of (8m + 8)^{15}(8m + 8s)^{1}(8m + 8t)^{1}. We fill these groups in with the aid of a point at infinity.

Remark 5.20 In all instances, we will take s = 1.

Lemma 5.21 (Code F) If m ∈ T D(18), 0 ≤ n < m, and {m − 1, 2m, n} ⊂ U_{1(8)}, then 18m − 16 + n ∈ U_{1(8)}.

Proof : Give the points from the last block a weight of 0, except for the first group, where all points get a weight of 16; also give m − n − 1 other points from the last group a weight of 0; and give all the other points a weight of 8. The needed component group vectors are 8^{15}16^{1}, 8^{16}16^{1}, and 8^{17}16^{1}, and are obtained from Lemma 5.13, so we may apply Wilson’s fundamental construction to give a design with a group vector of (8m − 8)^{16}(16m)^{1}(8n)^{1}. We fill these groups in with the aid of a point at infinity.

Remark 5.22 In all instances of the preceeding six lemmas, rather than filling the groups with the aid of a single infinite point, we could use w > 1 infinite points, as allowed by Theorem 4.2; we shall have occassion to do this.

The Singular Indirect Product construction was introduced in [36]. The following is a particular instance.

Lemma 5.23 (Code Ir) If 56m + 8 ∈ RB(8), and t ≤ 8m + 1, and m + t = n ∈ U_{1(8)}, and the incomplete transversal T D(9; 56m + 8 + t) − T D(9; t) exists, then 63m + 9 + n ∈ U_{1(8)}.

Proof : Since 56m + 8 ∈ RB(8), we may adjoin 8m + 1 points to the resolution sets to produce a B({9, 8m + 1^{∗}}), We use this design to fill in the groups of the incomplete transversal design with aid of 8m + 1 − t points at infinity, with the points of the design labelled so that the single filling block of size 8m + 1, (which is omitted), coincides with the missing subgroup and the infinite points. Filling in the infinite points and the missing subgroups with a single block of size 8(m + t) + 1 = 8n + 1 completes the construction.

Remark 5.24 For application in Appendix Table A.1, we will obtain the ITDs we need from Lemma 3.19, using m = 37, or m = 107.

6 The Spectrum

The objective of this section is to establish Theorem 6.1.

Theorem 6.1 If m is not one of the values listed in Table 6.1, then m ∈ U_{1(8)}, and 8m + 1 ∈ B(Q_{1(8)}).

Table 6.1.

Values of m for which m ∈ U_{1(8)} is unknown.

4 7 8 13 16 20 22 23 25 26
27 31 33 37 38 40 43 47 48 52
58 59 60 61 62 63 67 68 69 70
76 79 85 88 89 92 93 94 98 103
106 112 114 115 118 123 124 125 130 132
133 134 139 140 142 143 148 151 157 160
166 175 178 184 187 191 192 195 196 197
199 202 203 204 205 208 209 211 213 214
218 220 221 223 224 226 227 229 232 238
247 250 256 259 265 268 364 367 368 373
376 382 385 391 400 424 427 438 463 607
623 628 637 643 646 670 823 832 1024 1039
1048 1084

We give, in appendix Table A.1, our constructions for values up to 288 together with further constructions covering portions of the range up to 1648. We begin this section by concentrating on the first 288 values, and in exhibiting subdesigns for this range.

Lemma 6.2 (Code RB) If m ∈ E, then 8m + 1 ∈ B(Q_{1(8)}) with E given by: E = {9, 17, 41, 49, 97, 113, 121, 169, 193, 233, 241} ∪ {361, 409, 1033}.

Proof : This lemma is essentially a corollary of Lemma 5.2.

Lemma 6.3 (Code ZZ) If m ∈ {111, 198, 805, 814, 826}, then m ∈ U_{1(8)}.

Proof : For 111; take Mathon’s design of Lemma 3.10, and add 12 infinite points, to give a {10}-GDD of type 3^{33}12^{1}; apply Lemma 5.3. For 198; take Mathon’s design of Lemma 3.10, and give each point a weight of 16, and apply Wilson’s Fundamental Construction of Theorem 4.4, using a T D(9; 16). For 805; take a T D(10; 81) and truncate one block to size 5; note that the short block only contains points from the full groups; fill the full groups, and remove the short block to give a {9, 10, 81}-GDD with group sizes from {1, 80, 5^{∗}}, and thence a {9, 10}-GDD with group sizes from {1, 80, 5^{∗}}; the needed designs for Wilson’s FC come from Lemmas 5.1. For {814, 826}; truncate one group of a T D(18; 23) to size 16 or 22, and give each point a weight of 16, and apply Wilson’s FC; we may obtain {17}-GDDs of types 16^{17} and 16^{18} for this application by using Theorem 4.5 with k = 17 on Lemma 3.1 with q = 16 or 17.

We next summarize some of the smaller designs constructions.

Table 6.2.

m 8m + 1  Authority Remarks
9 73 = P G(2, 8)  Lemma 3.1
10 81 = AG(2, 9)  Lemma 3.1
17 137 = 17 + RB(8; 120)  Lemma 6.2
18 145 = 9 ∗ (17 − 1) + 1  Lemma 4.3
19 153 = 9 ∗ 17  Lemma 4.1
28 225 = 9 ∗ 25  Lemma 4.1
34 273 = P G(2, 16)  Lemma 3.1
36 289 = AG(2, 17)  Lemma 3.1
45 361 = 9 ∗ (41 − 1) + 1  Lemma 4.3 [3] for T D(9; 40)
46 369 = 9 ∗ 41  Lemma 4.1
53 425 = 17 ∗ 25  Lemma 4.1
54 433 = B(9; 433)  Lemma 3.7
55 441 = 9 ∗ 49  Lemma 4.1
64 513 = RB(9; 513)  Lemma 3.1
73 585 = 9 ∗ (73 − 9) + 9  Lemma 4.3
74 593 = 9 ∗ (73 − 9) + 17  Lemma 5.23 ITD(9;65)-(9;1)
78 625 = AG(2, 25)  Lemma 3.1
91 729 = 9 ∗ 81  Lemma 4.1
127 1017 = 9 ∗ 113  Lemma 4.1
128 1025 = 25 ∗ 41  Lemma 4.1
135 1081 = 9 ∗ (121 − 1) + 1  Lemma 4.3
136 1089 = 9 ∗ 121  Lemma 4.1
137 1097 = 9 ∗ (137 − 17) + 17 Lemma 4.3
138 1105 = 9 ∗ (137 − 17) + 25 Lemma 5.23 ITD(9;121)-(9;1)
145 1161 = 9 ∗ (137 − 9) + 9  Lemma 4.3
146 1169 = 9 ∗ (145 − 17) + 17 Lemma 4.3
201 1609 = 25 ∗ (73 − 9) + 9  Lemma 4.3
206 1649 = 17 ∗ 97  Lemma 4.1
210 1681 = AG(2, 41)  Lemma 3.1
216 1729 = 9 ∗ (193 − 1) + 1  Lemma 4.3
217 1737 = 9 ∗ 193  Lemma 4.1
228 1825 = 25 ∗ 73  Lemma 4.1
240 1921 = 17 ∗ 113  Lemma 4.1
251 2009 = 41 ∗ 49  Lemma 4.1

We next turn to the range 289–3439; constructions A and C, as detailed below in Tables 6.3 and 6.4 and Remark 6.4, cover large portions of this range. In both Tables 6.3 and 6.4, we get valid constructions for the range 17m through 19m with the exception of the noted failures.

Table 6.3.

m Invalid n  17m 19m Failures
17 33  289 323 322
32 55,63  544 608 599,607
41 79,81  697 779 776,778
64 116,122–127 1088 1216 1204,1210–1215
73 133–4,140–1 1241 1387 1374–5,1381–2
81  1377 1539
97 189  1649 1843 1838
121  2057 2299
127 250,251  2159 2413 2409,2410
137 269  2329 2603 2598
149 297  2533 2831 2830
163  2771 3097
167 333  2839 3173 3172
181  3077 3439

Remark 6.4 Using the overlapping ranges, or applying construction C of Lemma 5.17 with the same value of m to the exceptions in Table 6.3, we are able to remove all of them except 322, 607 and 1211.

Table 6.4 presents some cases of construction C. Again, apart from the noted failures, the inclusive range 17m through 19m has a valid construction available.

Table 6.4.

m Invalid n  15m 17m 19m Failures
19 39,41,44,46,  285 323 361 324,326,329,331,
73–76  358–361
29 115,116  435 493 551 550,551
49 189,195,196  735 833 931 924,930,931
53 115,116,211,212  795 901 1007 910,911,1006,1007
71 280,281,283,284  1065 1207 1349 None thru 1344
83 331,332  1245 1411 1577 1576,1577
101 392,397,403,404  1515 1717 1919 None thru 1911
107 409,415,421,423, etc. 1605 1819 2033 None thru 2013
113 227–8,231,443, etc.  1695 1921 2147 None in 1927–2137

Lemma 6.5 If 289 ≤ t ≤ 3439, and t ∉ E, then t ∈ U_{1(8)}, where E is given by:

{322, 324, 326, 329, 331} ∪ N_{358}^{492} ∪ {607} ∪ N_{609}^{696} ∪ N_{780}^{832} ∪ N_{1006}^{1087} ∪ N_{1576}^{1648}.

Proof : This follows by the application of constructions A and C as detailed in Tables 6.3 and 6.4, noting Remark 6.4.

Most of the exception set E of Lemma 6.5 can be dealt with by applying our constructions exactly as given. However, for some constructions we will use Theorem 4.2 with more than one infinite point.

Lemma 6.6 A B(Q_{1(8)} ∪ {8w + 1^{∗}}; 8(m + w) + 1) exists when (m, w) is one of the following pairs:

\begin{matrix}(8, 1) & (16, 1) & (16, 2) & (17, 1) & (25, 3) & (27, 1) & (32, 2) \\ (43, 6) & (50, 3) & (54, 1) & (81, 6) & (83, 1) & (89, 1) \end{matrix}

Proof : For m = 43, this follows from Lemma 5.2; for other m < 81, this follows from Table 6.2; for m ≥ 81, this follows from Lemma 5.5, truncating a T D(10, 9).

We use these subdesigns in the constructions given in Table 6.5.

Table 6.5.

Code m w Needed  Result  n range  Successes

subdesigns

T  16 1 (16,1)  144 + n  1 ≤ n ≤ 17  Several
T  25 3 (25,3)  225 + n  3 ≤ n ≤ 28  Several
T  27 1 (27,1)  243 + n  1 ≤ n ≤ 28  Several
A  16 2 (16,2) (32,2) 272 + n  2 ≤ n ≤ 18  274,277,
(0,2)  281,283,286
T  32 2 (32,2)  288 + n  2 ≤ n ≤ 34  322
A  17 1 (17,1)  289 + n n = 2m + w = 35 324
T  43 6 (43,6)  387 + n  6 ≤ n ≤ 49  Several
D  25 3 (25,3) (50,3) 425 + n  3 ≤ n ≤ 53  454,457
A  27 1 (27,1) (54,1) 467 + n  1 ≤ n ≤ 28  472

(8,1)

C  43 6 (43,6) (81,6) 726 + n 49 ≤ n ≤ 92 808,817
T  83 1 (83,1)  747 + n  1 ≤ n ≤ 84  831
C  89 1 (89,1)  1424 + n 90 ≤ n ≤ 189 1582

Lemma 6.7 If t ≤ 3439, and t ∉ T, then t ∈ U_{1(8)}, where T is the list of unconstructed cases given in Table 6.1.

Proof : Appendix Table A.1, in conjunction with Table 6.2, covers the values through 288 and most of the exception set E.

To deal with the values exceeding 3439, we need three preliminary lemmas.

Lemma 6.8 Any sequence of 10 consecutive integers contains at least one value from T D(10).

Proof : Consider only the 5 odd numbers of the sequence, and note that at most two are divisible by 3, and at most one by 5 or 7. Hence there is (at least) one value with no factors less than 11; the result then follows by Theorem 3.14.

Lemma 6.9 Let E′ = {367, 373, 391, 463, 607, 643, 823, 1039}. If m ∉ U_{1(8)}, and 288 ≤ m ≤ 3439 and m ∉ E′, then m is divisible by 2 or 7.

Proof : This is simply a matter of checking Table 6.1.

Lemma 6.10 G ⊂ U_{1(8)} ∩ T D(10), where G = {331, 337, 343, 349, 353, 359, 361, 369, 379, 389, 397, 461, 467, 601, 611, 641, 647, 821, 827, 1033, 1040}.

Proof : For G ⊂ U_{1(8)}, we check Table 6.1. For G ⊂ T D(10), we note that all the numbers given are prime powers, except 369 = 9 ∗ 41, 611 = 13 ∗ 47, and 1040 = 16 ∗ 64 + 16.

Lemma 6.11 If m > 3439, then m ∈ U_{1(8)}.

Proof : Note that U_{1(8)} contains an unbroken sequence of values from 269 through 363; the range 269 through 331 contains 63 > 6 ∗ 9 values. We may use the truncated transversal construction of Lemma 5.5, with 331 ≤ m ≤ 361 to construct the range 3248 = 9∗331+ 269 through 3610, with m being chosen from the set G of Lemma 6.10; note that the m values used do not differ by more than 6. Next, note the range 269 through 361 contains 93 > 10 ∗ 9 values. Again we use the truncated transversal construction of Lemma 5.5. By Lemma 6.8, we are assured that we may find a sequence of m ∈ T D(10) close enough together that the ranges of the successive constructions overlap. The only problem is that some of the needed m may not be in U_{1(8)}. The set E′ of Lemma 6.9 gives the only possible problem values in the values that Lemma 6.8 is providing. These problem values can be overcome by use of values from the set G of Lemma 6.10; the remaining values of G (i.e., those exceeding 361), were all chosen to straddle values in E′, with the straddling values differing by at most 10.

Theorem 6.12 If v is not in Table 6.6, and v ≡ 1 mod 8, then v ∈ B(Q_{1(8)}).

Proof : This is really a restatement of Theorem 6.1.

Table 6.6.

Values of v for which v ∈ B(Q_{1(8)}) is unknown.

33 57 65 105 129 161 177 185 201 209
217 249 265 297 305 321 345 377 385 417
465 473 481 489 497 505 537 545 553 561
609 633 681 705 713 737 745 753 785 825
849 897 913 921 945 985 993 1001 1041 1057

1065 1073 1113 1121 1137 1145 1185 1209 1257 1281
1329 1401 1425 1473 1497 1529 1537 1561 1569 1577
1593 1617 1625 1633 1641 1665 1673 1689 1705 1713
1745 1761 1769 1785 1793 1809 1817 1833 1857 1905
1977 2001 2049 2073 2121 2145 2913 2937 2945 2985
3009 3057 3081 3129 3201 3393 3417 3505 3705 4857
4985 5025 5097 5145 5169 5361 6585 6657 8193 8313
8385 8673

7 The Basis for 1 mod 8

Since we already have the machinery and most of the results already in place, we will take the opportunity to treat the PBD basis for the 1 mod 8 case. Let N_{1(m)} = {v : v ≡ 1 mod m}; we wish to find a set H_{1(m)} containing as few elements as possible, such that N_{1(m)} = B(H_{1(m)}). This problem was considered by Wilson for 2 ≤ m ≤ 4, and subsequently by Mullin for 5 ≤ m ≤ 7, and by Greig [41, 35, 21].

Lemma 7.1 Let a be a positive integer, and suppose that there exists a positive integer u such that u ≡ 1 mod a, and that there exists both a T D(a+1; u−1) and a T D(a+1; u). If there exists a T D(u + 1; m), then m(u − 1)(a + 1) + at + 1 is inessential in H_{1(a)} for 0 ≤ t ≤ m.

Proof : See [35, Lemma 2.2]; we truncate one group of the T D(u + 1; m), and apply Wilson’s FC, with group types found from the first two TDs, and then fill with an infinite point.

Let P_{k} = {q : q ≤ k, q prime}; we define U(P_{k}) to be the smallest integer δ such that, for any positive n, we can always find some s satisfying n ≤ s < n + δ with the property that s is relatively prime to every element of P_{k}. The main consequence of this, via MacNeish [34], is the following lemma.

Lemma 7.2 Let k be a positive integer. Then given any positive integer n, there exists an integer s such that n ≤ s < n + U(P_{k}) and there exists a T D(k + 2; s).

Proof : See [35, Lemma 2.1].

Let V (a, b) = {v : a + 1 ≤ v ≤ b, v ≡ 1 mod a}.

Lemma 7.3 Let a be a positive integer, and let u be an integer such that u ≡ 1 mod a and there exists a T D(a + 1; u − 1) and a T D(a + 1; u). Let δ = U(P_{k}) and let w be an integer such that there exists a T D(u + 1; w) and w ≥ δ(u − 1)(a + 1)/a − 1. Then the set V (a, w(u − 1)(a + 1) − a + 1) is a finite basis for N_{1(a)}.

Proof : See [35, Theorem 2.3]; we give a slightly improved version, with the improvement resulting from the observation that consecutive intervals need only abut each other, not overlap; the hypothesized bound on w is decreased by unity.

Corollary 7.4 V (8, 6401) is a basis for N_{1(8)}.

Proof : Take a = 8, u = 9, 10 = δ = U(P_{9}) = U(P_{7}), and w = 89. It follows from Lemma 6.8 that we can take δ = 10.

Actually, since the prime powers below 89 are within 6 of each other, there is more overlap of consecutive intervals than is provided for in Lemma 7.3, with its allowed gap of 10, so the result of Corollary 7.4 can be improved on considerably.

Lemma 7.5 Let S = N_{1}^{80} ∪ N_{91}^{98} ∪ N_{111}^{116} ∪ N_{131}^{143} ∪ N_{191}^{206}. If m ∉ S ∪ N_{321}^{332}, then 8m + 1 is inessential in H_{1(8)}.

Proof : In Lemma 7.1, take a = 8, u = 9, and let m range through the prime powers from 9 through 83.

Lemma 7.6 If m ∈ N_{321}^{332}, then 8m + 1 is inessential in H_{1(8)}.

Proof : In Lemma 5.14, take m = 17 or m = 19.

Lemma 7.7 If E = {9, 17, 41, 49, 97, 113, 193} ∪ {33, 57, 65}, then 8q + 1, with q ∈ E, is inessential in H_{1(8)}.

Proof : This lemma is essentially a corollary of Lemma 5.2, and Lemma 3.8.

Lemma 7.8 We have 125 ∈ B({5^{∗}, 9, 11, 13}), and also the incomplete transversal design T D(9; 125) − T D(9; 5) exists.

Proof : The PBD was constructed in [21] from an RT D(10; 13) in P G(2, 13) and parallels the construction of the 158 point PBD in Lemma 8.2. The ITD result follows from this PBD.

Table 7.1.

m 8m + 1  Authority  Remarks
63  505 = 9 ∗ (57 − 1) + 1  Lemma 4.3 K = {9, 57}
68  545 = 17 ∗ (33 − 1) + 1  Lemma 4.3 K = {17, 33}
72  577 = 9 ∗ (65 − 1) + 1  Lemma 4.3 K = {9, 65}
132  1057 = P G(2, 32)  Lemma 3.1 K = {33}
142  1137 = 9 ∗ (137 − 17) + 57 Lemma 5.23 K = {9, 57}
Lemma 7.8 ITD(9;125)-(9;5)
199  1593 = 9 ∗ 177  Lemma 4.1 K = {9, 177}
200  1601 = 25 ∗ (65 − 1) + 1  Lemma 4.3 K = {25, 65}
202  1617 = 33 ∗ 49  Lemma 4.1 K = {33, 49}

Theorem 7.9 If m is not listed in Table 7.2, then 8m + 1 is inessential in H_{1(8)}.

Proof : We only have to deal with elements of S from Lemma 7.5. We use Corollary 3.4 to remove m ∈ {19, 37, 66, 70}; we use Lemma 7.7 to remove m ∈ {9, 17, 33, 41, 49, 57, 65, 97, 113, 193}; we use Lemma 3.7 to remove m ∈ {10, 54, 73}; we use Lemma 6.3 to remove m ∈ {111, 198}; the remaining constructions are to be found in Table 6.2, or Table 7.1.

Table 7.2.

Values of m for which 8m + 1 ∈ B(H_{1(8)} \ {8m + 1}) is unknown.
1 2 3 4 5 6 7 8 11 12
13 14 15 16 20 21 22 23 24 25
26 27 29 30 31 32 35 38 39 40
42 43 44 47 48 50 51 52 56 58
59 60 61 62 67 69 71 75 76 77
79 80 92 93 94 95 96 98 112 114
115 116 131 133 134 139 140 141 143 191
192 194 195 196 197 203 204 205

Theorem 7.10 If v is not listed in Table 7.3, then v is inessential in H_{1(8)}.

Proof : This is just another version of Theorem 7.9. The first 14 values are essential.

Table 7.3.

Values of v for which v ∈ B(H_{1(8)} \ {v}) is unknown.
9 17 25 33 41 49 57 65 89 97
105 113 121 129 161 169 177 185 193 201
209 217 233 241 249 257 281 305 313 321
337 345 353 377 385 401 409 417 449 465
473 481 489 497 537 553 569 601 609 617
633 641 737 745 753 761 769 785 897 913
921 929 1049 1065 1073 1113 1121 1129 1145 1529
1537 1553 1561 1569 1577 1625 1633 1641

8 Prime Powers Exceeding Seven

The main aim of this section is to improve the spectrum of B(Q_{≥8}), where Q_{≥8} is the set of all prime powers exceeding 7. This problem was introduced by Bennett [9] and further discussed in [13]. Direct constructions for the values 123, 156, 158, 254, 316, and 1262 are given in [21], and for 291 and 295 were given in Corollary 3.5. The 123 point design takes the 120 point Denniston arc used in Corollary 3.4.1 and adds three extra points on an 8-line. The 158 point design uses the q − x construction from [21] (with q = 16 and x = 6): start with P G(2, q), and remove a point and x+1 lines through it to produce a RT D(q − x; q) and then take a (q − x)-line (in the plane) and flip the status of its q + 1 points, now deleting q − x and restoring x + 1, and finally add a non-planar point to the (x + 1)-line and the q − x (q − 1)-groups. The remaining constructions are based on Brouwer [16], who considers the cyclic difference set for P G(2, q), and looks at the points belonging to a residue set modulo w, for w a divisor of q^{2} + q + 1. Here however, we take more than one residue set; we take twelve modulo 21 sets in P G(2, 16), two modulo 3 sets in P G(2, 19), four modulo 7 sets in P G(2, 23), or two modulo 3 sets in P G(2, 43) to get our designs; if w = 3, it doesn’t matter which sets we pick; in the other two cases we used the eleven used sets plus 0, and the four least used sets, considering the use in the difference set given by Baumert [8].

Theorem 8.1 {123, 291, 295, 316, 574, 814, 1262} ⊂ B(Q_{≥8}).

Proof : See [21] or Corollary 3.4, or apply the q − x construction with q = 32 and x = 14 or 6.

We high-light two particularly useful values:

Lemma 8.2 156 ∈ B({8, 9, 11, 17}) and 158 ∈ B({8^{∗}, 9, 11, 16}).

Corollary 8.3 158 ∈ T D(9).

Lemma 8.4 1. If T D(k; m) exists, then km ∈ B({k, m}), and all block sizes occur.

2. If T D(k + 1; m) exists, and 0 < t < m, then km + t ∈ B({k, k + 1, m, t}), and all block sizes occur.

Proof : See Bennett [9, Lemma 2.8].

Lemma 8.5 If T D(t; m) exists, and k + 1 ≤ t, then km + t − k ∈ B({k, k + 1, m, t}), and all block sizes occur.

Proof : See Bennett [9, Lemma 2.11].

Using the notation T D^{∗}(k; m) to denote a T D(k; m) with at least one parallel class of k-lines, we have the following lemma which was exploited by Bennett and Zhu [13].

Lemma 8.6 If a T D(k; p) exists, and a T D^{∗}(p; q) exists, and a T D^{∗}(k; q) exists, then a {k, p, q}-GDD of type (kp)^{q} exists.

Proof : Filling in the groups of the third TD, and removing a parallel class produces a {k, q}-GDD of type k^{q}. Now a similar construction with the second TD shows we have a {p, q}-GDD of type p^{q}. Applying Wilson’s FC with weight of p for all points in our first constructed design, using the second constructed design to give the ingredients for the blocks of size q, and using the first hypothesized design to give the ingredients for the blocks of size k, shows the required result.

Lemma 8.7 If m ≠ 4, then 8m + 1 ∈ B(Q_{≥8}).

Proof : See Bennett [9, Theorem 4.1].

Lemma 8.8 1. If m ∉ {3, 5, 6, 7}, then 8m ∈ B(Q_{≥8});

2. If m ≥ 8 and m ≠ 22, then 8m ∈ B(Q_{≥8} ∪ {8^{∗}});

Proof : For the first part, see Bennett [9, Theorem 4.2]. Actually a careful analysis of Bennett’s proof establishes most of the second part. It n ≥ 8 is odd and n ∉ E_{9}, where E_{9} is a set of 30 numbers, then a T D(9; n) is known to exist, and Bennett also shows that n ∈ B(Q_{≥8}), [9, Theorem 4.1]. Hence, if n ∉ E_{9}, then we have the result for m = n by Lemma 8.4.1, and for m = n + 1 by Lemma 8.4.2 with t = 8. Lemma 8.4.1 also deals with the case that m ≥ 8 is a power of 2. Lemma 8.4.2 with t = 16, 32 also gives the cases m = n + 2 and m = n + 4 if n is not too small. Lemma 8.5 with t = 32 gives the cases m = n + 3 for n ≥ 31, and with t = 72 gives m = 78. We can use Lemma 8.4.2 with k = 16, t = 8 to deal with m = 35, 95. We also note that an RB(8; v) exists for v = 120, 288, 680; (the latter deals with m = 94). This abbreviated proof establishes the second part of the lemma; Bennett’s result now follows by noting that the missing smaller m are all powers of 2, and 8 ∗ 22 = 11 ∗ 16, and we can again apply Lemma 8.4.1.

Lemma 8.9 (Bennett [10])

1. If n = 10 or 12 ≤ n ≤ 19, then 8n + 12 ∈ B(Q_{≥8} ∪ {w^{∗}}) for 8 ≤ w ≤ 12;

2. If n = 12 or 14 ≤ n ≤ 19, then 8n + 14 ∈ B(Q_{≥8} ∪ {w^{∗}}) for 8 ≤ w ≤ 14;

3. If n ∈ {11, 13, 19} or 15 ≤ n ≤ 17, then 8n + w ∈ B(Q_{≥8} ∪ {w^{∗}}) for w ≤ 11.

Proof : If w ≤ n, we can truncate one group of a T D(9; n) to size w whenever n is a prime power, and if n = 15, we can add w points to a RB(8; 120). If w ≤ n+2 and n+1 is a prime power, we can apply Lemma 8.5 to a T D(w; n + 1). Finally, for n = 14, the RB(8; 120) is embedded as a {120; {0, 8}}-arc in P G(2, 16); we can extend an 8-secant to size w.

Lemma 8.10 (Bennett [10])

1. If m = 136 or 138 ≤ m ≤ 146 or m ∈ {148, 149}, then 8m + 156 ∈ B(Q_{≥8});

2. If m = 138 or 140 ≤ m ≤ 146 or m ∈ {148, 149}, then 8m + 158 ∈ B(Q_{≥8}); Proof : Let u ∈ {156, 158}; for m ≤ 144, set w = u − 144 and truncate one group of a T D(9; 144); now add w infinite points, and fill the groups using Lemma 8.9 for all but the last group (on 144+w points) which we fill with a B(Q_{≥8}; u) design from Lemma 8.2. For m = 145, set w = u − 144 and remove 8 collinear points from a T D(9; 19), and use this as the master design in Wilson’s Fundamental Construction of Theorem 4.4, giving all points weight 8, to get a {8, 9}-GDD of type 144^{8}152^{1}; now add w infinite points, and fill the groups using Lemma 8.9 for all but the last group (on 144 + w points) which we fill with a B(Q_{≥8}; u) design from Lemma 8.2. For m > 145, set w = u − 152 and truncate one group of a T D(9; 152); now add w infinite points, and fill the groups using Lemma 8.9 for all but the last group (on 152 + w points) which we fill with a B(Q_{≥8}; u) design from Lemma 8.2.

Lemma 8.11 If T D(k; v − u) exists, and v ∈ B(Q_{≥8} ∪ {u}^{∗}), and v ∈ B(Q_{≥8}), then k(v − u) + u ∈ B(Q_{≥8}).

Proof : See Bennett [9, Lemma 2.12].

Theorem 8.12 Let 0 ≤ y ≤ u − x and 0 ≤ a − y ≤ v − (u − x) and suppose:

1. {k, k + 1} ⊂ B(Q_{≥8}),

2. the incomplete transversal T D(k + 1; v) − T D(k + 1; a) exists,

3. v + x ∈ B(Q_{≥8} ∪ {a + x}^{∗}).

Further suppose either (A):

4. u ∈ B(Q_{≥8}),

5. ka + x + y ∈ B(Q_{≥8} ∪ {x + y}^{∗});

or else (B):

4′. u ∈ B(Q_{≥8} ∪ {x + y}^{∗}),

5′. ka + x + y ∈ B(Q_{≥8});

then kv + u ∈ B(Q_{≥8}).

Proof : This is a variation of the usual singular indirect product construction. We add x infinite points to the design, then truncate one of the groups of the ITD, leaving u − x points with y of them in the missing part. The initial conditions on x and y ensure that we actually remove a non-negative number from both the missing and non-missing parts of the groups of the ITD, and also leave a non-negative number of points in each part of the group. We then use D_{3} to fill the k untruncated groups, omitting the flat which we align with the infinite points and the hole. For version B, we then use D_{4′} to fill the last, truncated, group, and finally use D_{5′} to fill the holes and infinite points. For version A, we reverse this order, and use D_{5} first, then D_{4}.

Corollary 8.13 If 160 ≤ m ≤ 170, or 192 ≤ m ≤ 279, and u ∈ {156, 158}, then 8m + u ∈ B(Q_{≥8}).

Proof : We will apply version A of Theorem 8.12, with k = 8 and x = 0. Express m as m = v = 8q + a with q taken from 19, 23, 25, 27, 29, 31, and with 8 ≤ a ≤ q; this form provides us with the ITD, and also with D_{3} since x = 0. Take y = 8 for q = 19 or a = 22, and y = 0 otherwise. Lemma 8.2 gives us D_{4}; and since ka + x + y is a multiple of 8, Lemma 8.8 gives us D_{5} for both values of y, noting in the case y = 0 the subdesign is trivial.

Corollary 8.14 Let 144 ≤ m ≤ 159, or 180 ≤ m ≤ 187.

1. If m ≠ 146, then 8m + 156 ∈ B(Q_{≥8}).

2. If m ∉ {145, 147, 148, 149}, then 8m + 158 ∈ B(Q_{≥8}).

Proof : We will apply version B of Theorem 8.12, with k = 8. For 144 ≤ m ≤ 159, let m = v = 144 + a and y = a; the ITD follows from Wilson’s MOLS construction [40] and v = 16 ∗ 9 + a for a ≤ 9, or from v = 8 ∗ 19 + (a − 8) and for 8 < a ≤ 15. For u = 156, let x = 17 − a, and for u = 158, let x = 16 − a; D_{3} follows from v + x = 8 ∗ 19 + (x + a − 8) and Lemma 8.5, and D_{4′} follows from Lemma 8.2, and D_{5′} is on 8a + 17 or 8a + 16 points, which is alright by Lemma 8.7, unless a = 2 for u = 156, or else is alright by Lemma 8.8, unless a ∈ {1, 3, 4, 5} for u = 158.

For u ∈ {156, 158}, if 180 ≤ m ≤ 187, let m = v = 176 + a, let x = 11 − a, and y = a − 2; the ITD follows from v = 16 ∗ 11 + a, and D_{3} follows from v + x = 11 ∗ 17 and Lemma 8.4.1, and D_{4′} follows from Lemma 8.2, and D_{5′} is on 8a + 9 points, which is alright, by Lemma 8.7, for 4 ≤ a ≤ 11.

Lemma 8.15 If 171 ≤ m ≤ 191, and m ∉ {174, 175, 188}, then 8m + u ∈ B(Q_{≥8}) for u ∈ {156, 158}.

Proof : For the odd values not covered by Corollary 8.14, and for 176, we may apply Lemma 8.4.2 with t = u and k = 8. For the remaining m, we note that m + 1 is a prime, and apply Lemma 8.5 with t = u and k = 8.

Lemma 8.16 If a T D(14; m) exists, 0 ≤ s, t, w, x, y, z ≤ m and x + y + z ≤ m, then there is a Q_{≥8}-GDD of type (8m)^{10}(8x + 9y + 10z)^{1}(8s)^{1}(8t)^{1}(8w)^{1}.

Proof : See Bennett [9, Lemma 3.11].

Corollary 8.17 1558 ∈ B(Q_{≥8})

Proof : Apply Lemma 8.16 with m = 17, s = x = 1, t = 4, z = 15 and w = y = 0 to give a GDD of type 136^{10}158^{1}8^{1}32^{1}.

Theorem 8.18 If 138 ≤ m ≤ 279, then 8m + 156 ∈ B(Q_{≥8}).

Proof : Combining the preceeding corollaries and lemmas, we only have to deal with the three exceptions of Lemma 8.15, and these are covered by Lemma 8.4 with k=31, using the prime powers 49 and 53.

Theorem 8.19 If 140 ≤ m ≤ 279, then 8m + 158 ∈ B(Q_{≥8}).

Proof : The proof is essentially the same as for Theorem 8.18. The use of Lemma 8.4 with k = 31 and the prime powers 43, 49, 53, resolves m = 147, and two of the three exceptions of Lemma 8.15, and Corollary 8.17 resolves the third exception.

We turn now to the construction of some miscellaneous values. In addition to the values mentioned in the beginning of this section, we also have:

Theorem 8.20 1102 ∈ B(Q_{≥8}).

Proof : Apply Lemma 8.6 with k = 9, p = q = 11 to give a {9, 11}-GDD of type 99^{11}, and fill with 13 infinite points using a B({8, 9, 13}; 112 = 99 + 13) provided by 112 = 8 ∗ 13 + 8.

Remark 8.21 A construction similar to this one was used by Bennett and Zhu to remove this and two other values in [13]. In the introduction to this section, we mentioned the construction of adding t − 8 extra points from an 8-line through a 120 point Denniston arc in P G(2, 16); if we use the lines through a further point on this line to generate the groups, we have a {8, 9}-GDD of type 8^{14}t^{1} for 8 ≤ t ≤ 16 (and in particular t = 15); taking this in conjunction with the method used in the proof of [9, Lemma 3.9] and with 254 ∈ B(Q_{≥8}) accounts for the other constructions in [13]. Actually, This particular GDD, in conjunction with Bennett [9, Lemma 3.8], enables us to extend Lemma 8.16 to allow six further groups receiving weights of some mix of 0 and 8, if we wish, Provided, of course we were weighting a T D(20; m)).

Theorem 8.22 {1182, 1220, 1222, 1244, 1260, 1268, 1946} ⊂ B(Q_{≥8}).

Proof : For 1182, use Brouwer’s stacking Baer sub-planes construction of [16] to give 7 P G(2, 4)s in P G(2, 16), i.e., a B({7, 11}; 147), and to this add 6 infinite points for the resolutions on the short blocks to give a B({8, 11, 6^{∗}}; 153); use this design to fill 7 groups of a T D(8; 147) with 6 infinite points, and then a B({9, 17}; 153) from 153 = 9∗17 to fill the last group. For the next two values, let u ∈ {156, 158} and let a = u − 152; now use u = 8 ∗ 19 + a ∈ B({8, 9, 19, a^{∗}}) to fill in all but the last group of a T D(8; 152) with a added infinite points, and use Lemma 8.2 for the last group. The next two values are the two smallest values given by Lemma 8.10. For the last two values, we use Lemma 8.11, noting that 1268 = 9 ∗ (156 − 17) + 17 and 1946 = 13 ∗ (158 − 9) + 9.

Remark 8.23 For the applications discussed in [9, 13], the following equations are worth noting:

1. 1578 = 11 ∗ (158 − 16) + 16, and

2. 1626 = 11 ∗ (156 − 9) + 9.

We may summarize the main results of this section:

Theorem 8.24 If v has the value 4 or 6 modulo 8, and v ≥ 1276, then v ∈ B(Q_{≥8}).

Proof : Given in Theorems 8.18 and 8.19.

Remark 8.25 We have now substantiated the majority of the improvements made in [12, Table 3.18] over the results in [9]. We have no construction for 1578 or 1626, the two values noted in Remark 8.23; it would appear that these were erroneously omitted from [12, Table 3.18]. In addition, we have noted constructions for the values 316, 574, 814, 1244, 1260 and 1318 which further improve [12, Table 3.18].

9 Update

In this final section, we wish to provide some updates and corrections to the three tables of generating/exception sets given in [12, Tables III.3.17–19].

9.1 Table III.3.17

Most of the changes here involve designs with 4 ∈ K, and result from improvements to [37] during its later drafts. That paper has a couple of weak entries in the summary table [37, pp. 74–75]: (55 ∈ B({4, 6, 8, 9}), 30 ∉ B({4, 7, 8, 9})). It is known that 44, 45, 47 ∉ B({4, 7, 8}) and also that 48 ∉ B({4, 7, 9}). The remaining improvements with 4 ∈ K from [37] are in constructing designs; another results from Ling [29, p. 57] who gives a B({4, 5}; 104) with 21 parallel classes of 4-blocks, so adding 11 points gives a B({4, 5, 11^{∗}}; 115). For 4 ∈ K, we have chosen to list the current possible exceptions for all such listed K, several of which seem close to solution.

K  Possible exceptions
4, 6  33, 34, 39, 45, 46, 51, 75, 87
4, 8  48, 53, 60, 65, 69, 77, 89, 101, 161, 164, 173
4, 9  60, 69, 84, 93, 96, 192
4, 5, 7  30, 39, 42, 51, 54
4, 5, 11  38, 42, 43, 46, 50, 54, 58, 62, 66, 67, 70, 74

78, 82, 90, 94, 98, 102, 106, 114, 118, 126

4, 6, 7  33, 45, 87
4, 6, 8  33, 34, 35, 39, 41, 47, 50, 51, 53, 59, 62, 65,

71, 75, 77, 87, 89, 95, 101, 110, 131, 161, 170

4, 6, 9  34, 75, 87
4, 7, 8  48, 51, 54, 59, 62, 65, 66, 69, 74, 75, 77, 78, 83, 87,

89, 90, 101, 102, 110, 111, 114, 123, 126, 131, 135, 143, 150, 159, 161, 162, 164, 167, 170, 173, 174, 186, 195

4, 7, 9  51, 54, 60, 66, 69, 75, 78, 84, 87, 93, 96, 102,

111, 114, 138, 147, 150, 159, 174, 183, 186, 195, 210

4, 8, 9  48, 53, 60, 69, 77, 101, 161, 164, 173
4, 5, 7, 8  30, 42, 51
4, 5, 7, 9  30, 51, 54
4, 5, 7, 11  30, 42, 54
4, 6, 7, 8  33, 35, 41, 65, 77, 131
4, 6, 8, 9  34, 35, 41, 47, 50, 53, 59, 62, 71,

75, 77, 87, 95, 101, 131, 161, 170

4, 7, 8, 9  35, 38, 39, 41, 42, 44, 47, 48, 51, 54, 59, 62,

110, 143, 150, 159, 161, 164, 167, 173, 174

4, 5, 7, 8, 9  30, 51
4, 6, 7, 8, 9  35, 41
4, 5, 7, 9, 10, 11 30
4, 5, 9, 11, 19, 31 38, 42, 43, 46, 50, 54, 62, 66, 74, 78, 90, 98, 102, 114, 126

There were three changes involving designs with 5 ∈ K resulting from improvements to [11] during its final draft. The remaining improvements to [12, Table III.3.17] come from other results in the table or from three designs: Bierbrauer [14] exhibits a pentario in P G(2, 8) (i.e., a set of 3 quintuples, any pair of which form a hyperoval), and the pentario forms a {15; {0, 2, 3}}-arc in the plane, so deleting the pentario and an external line gives a B({5, 6, 8}; 49); there are over 10^{6} such configurations, and using the Singer difference set given by powers of 2 in Z_{73}, an example set of deleted points is:

{1, 2, 11, 27, 60}{0, 9, 29, 45, 58}{7, 30, 38, 46, 71}{3, 4, 6, 10, 18, 34, 39, 57, 66}

The two other designs are 7-GDDs of types 7^{25} and 7^{37} constructed by Janko and Tonchev [27] and by Abel [2], and modifying these designs give the remaining new PBDs.

\begin{matrix}K & Change \\ 5, 7 & 259, 709 ∈ B(K) \\ 5, 6, 8 & 49, 307 ∈ B(K) \\ 5, 6, 8, 9 & 174 ∈ B(K) \\ 5, 7, 8, 9 & 163, 243 ∈ B(K) \\ 6, 7, 8 & 170, 174, 175, 176 ∈ B(K) \\ 6, 7, 8, 9 & 137, 170, 174, 175, 176 ∈ B(K) \\ 7, 8, 9 & 175, 176, 259, 260 ∈ B(K) \end{matrix}

Finally, we note that [29, p. 21] contains an arithmetic error; this affects part of [30, Lemma 4.7], for (94, 95). More specifically, Ling gives a (lower) bound up to which we safely can add points to a certain configuration in a projective plane, although he mis-evaluated the bound here; using essentially Ling’s plan, one can exceed this bound with carefully chosen points, and this was demonstrated in [7, Lemma 4.18], correcting the lacuna.

9.2 Table III.3.18

First, we note the errors in this table. For K = Q_{≥4} clearly the prime powers 11, 19, 23, 27 are not exceptions, nor is 51 a possible exception (truncate one group of a T D(5; 11) to size 7); incidentally, the exception set can be deduced from the K = {4, 5, 7, 8, 9} exception set. Earlier, we commented on the other possible errors in this table for K = Q_{≥8} in Remark 8.25, (1578, 1626 omitted), as well as the improvements of constructions for 316, 574, 814, 1244, 1260, 1318; Bennett [10] has also obtained constructions for 1196, 1198, 1212, 1214, 1236, 1238, 1246, 1254, 1270, 1706, 1770, 1778, 1794 and all values ≥ 1810.

In [6], it is shown that:

{161, 231, 266, 276, 296, 376, 561, 741, 946} ⊂ B(Q_{1 mod 5} ∪ {6}).

The Janko-Tonchev and Abel designs [27, 2] also show

{175, 176, 259, 260} ⊂ B(Q_{0,1 mod 7}).

9.3 Table III.3.19

There is one error: clearly 15 is an essential element of H_{0,1(5)}.

In [6], for H_{1(5)}, it is shown that the following are inessential:

{131, 146, 166, 196, 221, 226, 231, 251, 261, 266, 296, 316, 326, 351, 356}.

9.4 Updated References

Finally we note that the references in [37, 11] are more accurate than those in [12, Table III.3.19], and give the following updates to the reference section of [12].

Citation in [12] Citation in this paper
[4]  [11]
[12]  This paper itself
[13]  [21]
[14]  [24]
[15]  [23]
[19]  [30]
[20]  [31]
[21]  [32]
[25]  [37]

Acknowledgement

I would like to acknowledge the help and advice of Frank Bennett, and his hospitality during a visit to Mount Saint Vincent University, where some of this research was done. I would also like to thank Frank for his help in providing some of the constructions that went into generating [12, Table 3.18], and to Julian Abel, who also provided help with the update section.

The problem of Section 8 was one of the first combinatorial problems I tackled, and in these last ten years, I have had discussions and preprints which have helped me with the problems in this paper, and (especially for this paper) help with references, and for all of this, I would like to thank Julian Abel, Frank Bennett, Juergen Bierbrauer, Charlie Colbourn, Dieter Gronau, Martin Gruettmueller, Alan Ling, Ron Mullin, Paul Schellenberg and Vladimir Tonchev.

References

[1] R. J. R. Abel, Difference families, in: CRC Handbook of Combinatorial Designs, (C. J. Colbourn and J. H. Dinitz, eds.), CRC Press, Boca Raton FL, (1996), 270– 287.

[2] R. J. R. Abel, Some new BIBDs with block size 7. J. Combin. Des. (to appear).

[3] R. J. R. Abel, A. E. Brouwer, C. J. Colbourn and J. H. Dinitz, Mutually Orthogonal Latin Squares (MOLS), in: CRC Handbook of Combinatorial Designs, (C. J. Colbourn and J. H. Dinitz, eds.), CRC Press, Boca Raton FL, (1996), 111–142.

[4] R. J. R. Abel, C. J. Colbourn and J. H. Dinitz, Incomplete MOLS, in: The CRC Handbook of Combinatorial Designs, (C. J. Colbourn and J. H. Dinitz, eds.), CRC Press, Boca Raton FL, (1996), 142–172.

[5] R. J. R. Abel, N. J. Finizio, M. Greig and S. J. Lewis, Pitch tournament designs and other BIBDs – existence results for the case v = 8n + 1, (1999), preprint; (Congr. Numer., to appear).

[6] R. J. R. Abel and M. Greig, Some new (v, 5, 1) RBIBDs and PBDs with block sizes ≡ 1 mod 5, Australasian J. Combinat. 15 (1997), 177–202.

[7] R. J. R. Abel, M. Greig, Y. Miao and L. Zhu, Resolvable BIBDs with block size 7 and index 6, (preprint).

[8] L. D. Baumert, Cyclic Difference Sets, Lecture Notes in Math. 182 (1971).

[9] F. E. Bennett, Pairwise balanced designs with prime power block sizes exceeding 7, Ann. Discrete Math. 34 (1987), 43–64.

[10] F. E. Bennett, Personal communications, (Oct./Nov., 1999).

[11] F. E. Bennett, C. J. Colbourn and R. C. Mullin, Quintessential pairwise balanced designs, J. Statist. Plann. Inference 72 (1998), 15–66.

[12] F. E. Bennett, H.-D. O. F. Gronau, A. C. H. Ling and R. C. Mullin, PBD-Closure, in: The CRC Handbook of Combinatorial Designs, (C. J. Colbourn and J. H. Dinitz, eds.), CRC Press, Boca Raton FL, (1996), 203–213.

[13] F. E. Bennett and L. Zhu, Conjugate-orthogonal latin squares and related structures, in: Contemporary Design Theory: A Collection of Surveys, (J. H. Dinitz and D. R. Stinson, eds.), John Wiley, New York, (1992), 41–96.

[14] J. Bierbrauer, The maximal size of a 3-arc in P G(2, 8), (preprint).

[15] R. C. Bose, On the application of finite projective geometry for deriving a certain series of balanced Kirkman arrangements, Cal. Math. Soc. Golden Jubilee Commemoration Volume, Part II (1958–1959), 341–356.

[16] A. E. Brouwer, A series of seperable designs with application to pairwise orthogonal latin squares, European J. Combin. 1 (1980), 39–41.

[17] M. Buratti, A powerful method of constructing difference families and optical orthogonal codes, Des. Codes Cryptogr. 5 (1995), 13–25.

[18] C. J. Colbourn and J. H. Dinitz, Home page for The CRC Handbook of Combinatorial Designs, URL: http://www.emba.uvm.edu/∼dinitz/hcd.html

[19] R. H. F. Denniston, Some maximal arcs in finite projective planes, J. Combin. Theory 6 (1969), 317–319.

[20] M. Greig, Some group divisible design constructions, J. Combin. Math. Combin. Comput. 27 (1998), 33–52.

[21] M. Greig, Designs from projective planes, and PBD bases, J. Combin. Des. 7 (1999), 341–374.

[22] M. Greig and R. J. R. Abel, Resolvable balanced incomplete block designs with a block size of 8, Des. Codes Cryptogr. 11 (1997), 123–140.

[23] H.-D. O. F. Gronau, V. Leck, R. C. Mullin and P. J. Schellenberg, On orthogonal covers of K⃗_{n}, (preprint).

[24] H.-D. O. F. Gronau, R. C. Mullin and C. Pietsch, The closure of all subsets of {3, 4, …, 10} which include 3, Ars Combin. 41 (1995), 129–161.

[25] H. Hanani, Balanced incomplete block designs and related designs, Discrete Math. 11 (1975), 255–369.

[26] D. R. Hughes and F. C. Piper, Design Theory, Cambridge University Press, Cambridge UK, (1985).

[27] Z. Janko and V. D. Tonchev, New designs with block size 7, J. Combin. Theory Ser. A 83 (1998), 152–157.

[28] E. Lamken, The existence of 3 orthogonal partitioned incomplete latin squares of type t^{n}, Discrete Math. 89 (1991), 231–251.

[29] A. C. H. Ling, Pairwise Balanced Designs and Related Codes, Ph. D. Thesis, University of Waterloo, Canada, 1997.

[30] A. C. H. Ling and C. J. Colbourn, Pairwise balanced designs with block sizes 8, 9 and 10, J. Combin. Theory Ser. A 77 (1997), 228–245.

[31] A. C. H. Ling and C. J. Colbourn, Concerning the generating set of Z_{≥n}, Congr. Numer. 114 (1996), 65–72.

[32] A. C. H. Ling, X. J. Zhu, C. J. Colbourn and R. C. Mullin, Pairwise balanced designs with consecutive block sizes, Des. Codes Cryptogr. 10 (1997), 203–222.

[33] P. Lorimer, A class of block designs having the same parameters as the design of points and lines in a projective 3-space, Lecture Notes in Math. 403 (1974), 73–78.

[34] R. C. MacNeish, Euler squares, Ann. of Math. 23 (1922), 221–227.

[35] R. C. Mullin, Finite bases for some PBD-closed sets, Discrete Math. 77 (1989), 217–236.

[36] R. C. Mullin, D. G. Hoffman and C. C. Lindner, A few more BIBD’s with k = 6 and λ = 1, Ann. Discrete Math. 34 (1987), 379–384.

[37] R. C. Mullin, A. C. H. Ling, R. J. R. Abel and F. E. Bennett, On the closure of subsets of {4, 5, …, 9} which contain 4, Ars Combin. 45 (1997), 33–76.

the electronic journal of combinatorics 7 (2000), #R13 31

[38] R. C. Mullin, P. J. Schellenberg, S. A. Vanstone and W. D. Wallis, On the existence of frames, Discrete Math. 37 (1981), 79–104.

[39] E. Seiden, A method of construction of resolvable BIBD, Sankhy a Ser. A 25 (1963), 393–394.

[40] R. M. Wilson, Concerning the number of mutually orthogonal latin squares, Discrete Math. 9 (1974), 181–198.

[41] R. M. Wilson, Constructions and uses of pairwise balanced designs, Math. Centre Tracts 55, Mathematisch Centrum, Amsterdam, 1974, 18–41.

A Appendix

The object of this appendix is to provide the constructions for the first 288 values of B(Q_{1(8)}) plus portions of the range for the first 1648 values, as annonunced in Section 6.

Key to Table A.1.

Code  Result  Authority  Code  Result Authority
A/a m.n 17m + n  Lemma 5.14  P  Prime
B m.n 17m + n  Lemma 5.16  PP  Prime power
BD m.n 10m − n  Lemma 5.8  R  v.n v + n Lemma 5.10
C/c m.n 15m + n  Lemma 5.17  RB  m m  Lemma 6.2
D/d m.n 17m + n  Lemma 5.18  T/t m.n 9m + n Lemma 5.5
E m.n 16m + 16 + n Lemma 5.19  Table  Table 6.2
F  m.n 18m − 16 + n Lemma 5.21  X  Tables 6.3, 6.4
Ir m.n 63m + 9 + n Lemma 5.23  ZZ  Lemma 6.3
L  m.n 9m + n − 9  Lemma 5.7
Ls m.n 9m + n − 9  Lemma 5.6  ** n ** Unconstructed

Lower case versions of construction codes (and their m and n) are from Table 6.5.

Table A.1.

Table of Constructions for U_{1(8)}.

0  1  2  3  4  5  6  7  8
0 0  PP  P  PP ***4**  P  PP ***7** ***8**
9 1  P  PP  P  P **13**  P  PP **16**  P
18 2  Table Table **20**  PP **22** **23**  P **25** **26**
27 3 **27** Table  P  P **31**  P **33** Table  P
36 4  PP **37** **38**  P **40** RB 41  P **43**  P
45 5  PP Table **47** **48** RB 49  P  P **52** Table
54 6  P Table  P  P **58** **59** **60** **61** **62**
63 7 **63** Table  P  PP **67** **68** **69** **70**  P
72 8  P Table  P  P **76**  P  PP **79**  P
81 9  T 9.0 T 9.1 T 9.2  P **85** T 9.5  T 9.6 **88** **89**
90 10  T 9.9  PP **92** **93** **94**  P  P RB 97 **98**
99 11 T 11.0 T 11.1  P T 11.3 *103** T 11.5  PP *106**  P
108 12 T 11.9 T 11.10  P  ZZ *112** RB 113 *114** *115**  P
117 13  P *118**  P  PP RB 121  P *123** *124** *125**

126 14  P Table Table  P *130**  P *132** *133** *134**
135 15  Table Table  P Table *139** *140**  P *142** *143**
144 16  P t 16.1 t 16.2 t 16.3 *148**  P  P *151**  P
153 17 T 17.0 T 17.1 T 17.2  P *157** T 17.5 T 17.6 *160**  P
162 18  P T 17.10 T 17.11  P *166** T 17.14 T 17.15 RB 169  P
171 19  PP T 19.1 T 19.2 T 19.3 *175**  P T 19.6 *178**  P
180 20 T 19.9 T 19.10 T 19.11 T 19.12 *184**  P  P *187** T 19.17
189 21 T 19.18 T 19.19 *191** *192** RB 193  P *195** *196** *197**
198 22  ZZ *199**  P  P *202** *203** *204** *205** Table
207 23  P *208** *209**  PP *211**  P *213** *214**  P
216 24  Table Table *218**  P *220** *221**  P *223** *224**
225 25  P *226** *227** t 25.3 *229** t 25.5  PP *232** RB 233
234 26  P t 25.10  P t 25.12 *238**  P t 25.15 RB 241 t 25.17
243 27 t 25.18 t 27.1 t 27.2 t 27.3 *247** t 27.5  P *250** Table
252 28  P t 27.10 t 27.11 t 27.12 *256** t 27.14 t 27.15 *259**  P
261 29  P T 29.1 T 29.2  P *265**  P  P *268**  P
270 30  P T 29.10 T 29.11 T 29.12 a 16.2 T 29.14  PP a 16.5 T 29.17
279 31 T 29.18 T 29.19 a 16.9 T 29.21 a 16.11  P  P a 16.14  P
288 32 T 32.0  X  X  X  X  X  X  X  X

For 289 – 321; use construction A with m = 17.

315 35  X  X  X  X  X  X  X t 32.34  X
324 36 a 17.35  X  P  X  X B 19.6  X B 19.8  X

For 323 – 357 (with gaps); use construction C with m = 19.

351 39 X X X X X X X Ir 5.34 Ir 5.35
360 40 Ir 5.36 RB 361  P Ir 5.39 *364** Ir 5.41 Ir 5.42 *367** *368**
369 41 T 41.0 T 41.1 T 41.2 T 41.3 *373** T 41.5 T 41.6 *376** L 41.17
378 42 T 41.9 T 41.10 T 41.11 T 41.12 *382** T 41.14 T 41.15 *385** T 41.17
387 43 T 41.18 T 41.19 L 41.29 T 41.21 *391** L 41.32 T 41.24 L 41.34 L 41.35
396 44  t 43.9 T 41.28 T 41.29 T 41.30 *400** T 41.32 t 43.15 T 41.34 T 41.35
405 45 T 41.36 t 43.19  P T 41.39 RB 409 T 41.41 t 43.24 E 23.28 E 23.29
414 46 E 23.30 t 43.28 t 43.29 t 43.30 E 23.34 t 43.32 E 23.36 t 43.34 t 43.35
423 47 t 43.36 *424** E 23.41 t 43.39 *427** t 43.41 t 43.42 E 23.46 t 43.44
432 48 t 43.45 t 43.46 F 25.0 F 25.1 t 43.49 F 25.3 *438** F 25.5 F 25.6
441 49 T 49.0 T 49.1 T 49.2 T 49.3 F 25.11 T 49.5 T 49.6 F 25.14 F 25.15
450 50 T 49.9 T 49.10 T 49.11 T 49.12 d 25.29 T 49.14 T 49.15 d 25.32 T 49.17
459 51 T 49.18 T 49.19 L 49.29 T 49.21 *463** L 49.32 T 49.24 L 49.34 L 49.35
468 52 L 49.36 T 49.28 T 49.29 T 49.30 a 27.5 T 49.32 L 49.42 T 49.34 T 49.35
477 53 T 53.0 T 53.1 T 53.2 T 53.3 L 49.49 T 53.5 T 53.6 E 27.36 T 49.44
486 54 T 53.9 T 53.10 T 53.11 T 53.12 T 49.49 T 53.14 T 53.15 X X

For 493 – 606, 608; use constructions A, C with m = 29, 32.

603 67 X X X X *607** X R585.24 T 64.34 T 64.35
612 68 T 64.36 R585.28 R585.29 T 64.39 Ls64.49 T 64.41 T 64.42 R585.34 T 64.44
621 69 T 64.45 T 64.46 *623** R585.39 T 64.49 T 64.50 T 64.51 *628** T 64.53
630 70 T 64.54 T 64.55 T 64.56 T 64.57 R585.49 R585.50 R585.51 *637** R585.53
639 71 T 71.0 T 71.1 T 71.2 T 71.3 *643** T 71.5 T 71.6 *646** Ls71.17
648 72 T 71.9 T 71.10 T 71.11 T 71.12 F 37.2 T 71.14 T 71.15 F 37.5 T 71.17
657 73 T 71.18 T 71.19 T 73.2 T 71.21 F 37.11 T 73.5 T 71.24 F 37.14 F 37.15
666 74 T 73.9 T 71.28 T 71.29 T 71.30 *670** T 71.32 T 73.15 T 71.34 T 71.35
675 75 T 71.36 T 73.19 L 73.29 T 71.39 F 37.29 T 71.41 T 71.42 F 37.32 T 71.44
684 76 T 71.45 T 71.46 T 73.29 T 73.30 T 71.49 T 71.50 T 71.51 T 73.34 T 71.53

693 77 T 71.54 T 71.55 T 71.56 T 71.57  X  X  X  X  X

For 697 – 779; use constructions A, C with m = 41.

774 86 X X X X X X T 81.51 T 83.34 T 82.44
783 87 T 81.54 T 81.55 T 81.56 T 81.57 T 82.49 T 82.50 T 82.51 F 43.32 T 83.44
792 88 T 82.54 T 81.64 T 81.65 T 81.66 T 83.49 T 83.50 T 83.51 F 43.41 T 81.71
801 89 T 81.72 T 81.73 T 81.74 T 81.75  ZZ T 81.77 T 81.78 c 43.82 T 81.80
810 90 T 81.81 T 82.73 T 82.74 T 82.75  ZZ T 82.77 T 82.78 c 43.91 T 82.80
819 91 T 82.81 T 82.82 T 83.74 T 83.75 *823** T 83.77 T 83.78  ZZ T 83.80
828 92 T 83.81 T 83.82 T 83.83 t 83.84 *832** X X X X

For 833 – 1006; use construction C with m = 49, 53.

999 111 X X X X X X X T101.97 T107.44
1008 112 T107.45 T107.46 T109.29 T109.30 T107.49 T107.50 T107.51 T109.34 T109.35
1017 113 T 113.0 T 113.1 T 113.2 T109.39 Ls109.49 T 113.5 T 113.6 *1024* T109.44
1026 114 T 113.9 T113.10 T107.65 T113.12 T109.49 T113.14 T113.15 RB 1033 T113.17
1035 115 T113.18 T113.19 T109.56 T113.21 *1039* T107.77 T113.24 L113.34 T107.80
1044 116 T107.81 T109.64 T113.29 T113.30 *1048* T113.32 T107.87 T113.34 T113.35
1053 117 T113.36 T109.73 T109.74 T113.39 L113.49 T113.41 T113.42 T107.97 T113.44
1062 118 T113.45 T113.46 T109.83 T109.84 T113.49 T113.50 T113.51 Ls109.97 T113.53
1071 119 T113.54 T113.55 T113.56 T113.57 Ir15.121 T109.95 T109.96 T109.97 L113.71
1080 120 T109.99 T113.64 T113.65 T113.66 *1084* T117.32 T109.105 T117.34  X

For 1088 – 1575; use constructions A, C with m = 64, 71, 73, 81, 83.

1575 175  X T173.19 T169.56 T173.21 Ls163.121 T171.41 T173.24 c89.158 T171.44
1584 176 T 176.0 T 176.1 T 176.2 T 176.3 T171.49 T 176.5 T 176.6 T173.34 T173.35
1593 177 T 177.0 T 177.1 T 177.2 T 177.3 Ls173.49 T 177.5 T 177.6 T167.97 T176.17
1602 178 T 177.9 T177.10 T177.11 T177.12 T173.49 T177.14 T177.15 L169.97 T177.17
1611 179 T 179.0 T 179.1 T 179.2 T 179.3 Ls167.121 T 179.5 T 179.6 T176.34 T176.35
1620 180 T 179.9 T179.10 T179.11 T179.12 T167.121 T179.14 T179.15 T177.34 T179.17
1629 181 T 181.0 T 181.1 T 181.2 T 181.3 T176.49 T 181.5 T 181.6 T171.97 T177.44
1638 182 T 181.9 T181.10 T181.11 T181.12 T177.49 T181.14 T181.15 T179.34 T181.17
1647 183 T181.18 T181.19  X  X  X  X  X  X  X
0  1  2  3  4  5  6  7  8