SOME NEW STEINER 2-DESIGNS S(2, 4, 37)

VEDRAN KRČADINAC

Abstract. Automorphisms of Steiner 2-designs S(2, 4, 37) are studied and used to find many new examples. Some of the constructed designs have S(2, 3, 9) subdesigns, closing the last gap in the embedding spectrum of S(2, 3, 9) designs into S(2, 4, v) designs.

1. Introduction

A balanced incomplete block design (BIBD) with parameters (v, k, λ) is an incidence structure consisting of v points and a number of blocks, with k points on every block and λ blocks through every pair of distinct points. The number of blocks through an arbitrary point can be expressed as r = \frac{λ(v−1)}{k−1}, and the total number of blocks as b = \frac{λv(v−1)}{k(k−1)}. Necessary conditions for the existence of (v, k, λ) BIBDs are integrality of r and b and Fisher’s inequality, v ≤ b. Steiner 2-designs are BIBDs with λ = 1. In this case it is customary to write parameters in the form S(2, k, v) and to talk about lines instead of blocks.

The Handbook of Combinatorial Designs [9] gives 3 as the number of known S(2, 4, 37) designs. Another example was constructed by F. Franek et al. [3], as part of the search for 2-chromatic S(2, 4, v)s. An S(2, 4, 37) with an automorphism of order 2 keeping the maximum number of points fixed was found by D.L. Kreher, D.R. Stinson and L. Zhu [7]. More examples were found by M. Meszka and A. Rosa [10].

Although it appears that there are many S(2, 4, 37) designs, an easy way to generate them is lacking. Steiner triple systems S(2, 3, v) can be generated efficiently by hill-climbing (see [15]). There are similar randomized search techniques for general BIBDs (e.g. [8], [1] and [6]), but they perform poorly when λ = 1 and k > 3. Not a single S(2, 4, 37) was found by the tabu-search algorithm [6] even after a considerable amount of CPU time. The best approach in this particular case seem to be the classic one, i.e. to look for designs with prescribed automorphisms.

In this article all S(2, 4, 37) designs with automorphisms of order 11 and many more with automorphisms of order 2 and 3 are constructed. The search is not exhaustive in the latter two cases, but interesting connections with (12, 3, 2) and (12, 4, 3) BIBDs are discovered. The construction involving (12, 3, 2) BIBDs proved particularly prolific, enabling fast generation of millions of S(2, 4, 37) designs. About 50000 nonisomorphic examples are explicitly constructed and analyzed. Some of them contain S(2, 3, 9) subdesigns, providing examples for the last open case of the embedding spectrum E(9) in [10].

2000 Mathematics Subject Classification. 05B05 (51E10).

Key words and phrases. Steiner 2-design, automorphism, subdesign.

2. The construction method and known results

An automorphism of a BIBD is an incidence-preserving permutation of points and lines. The set of all automorphisms forms a group under composition, the full automorphism group. Provided it is nontrivial, the full automorphism group must contain automorphisms of prime order. Our first task is to determine the prime numbers p which are candidates for automorphism orders of S(2, 4, 37) designs. The following lemma was proved in [5].

Lemma 2.1. Let α be an automorphism of prime order p of a S(2, k, v) design with v < k(k^{2} − 2k + 2). If p ≥ k − 1, then α either has no fixed points, or has a single fixed point, or keeps fixed k points on a line.

For S(2, 4, 37) designs this means that any p ≥ 3 must necessarily divide v = 37, v − 1 = 36 or v − k = 33. Thus, we can conclude:

Proposition 2.2. If a S(2, 4, 37) design possesses an automorphism of prime order p, then p ∈ {2, 3, 11, 37}.

The automorphism order is not sufficient for the construction of designs; more detailed information on how it acts on the points and lines is required. Automorphisms of prime order p act in orbits of length 1 and p. Hence, the action is completely determined by the number of fixed points and lines. Once the orbit sizes are known, construction of the designs proceeds in three steps.

(1) Construction of orbit matrices (also called tactical decompositions). The entries of these matrices are incidence counts for pairs of pointline orbits.

(2) Indexing; the orbit matrices are expanded in a systematic fashion to obtain incidence matrices of the designs.

(3) Screening of the designs for isomorphism.

In the first step we use an orderly algorithm that generates orbit matrices in canonical form. In the second step limited isomorph rejection is performed directly, and B.D. McKay’s nauty [11] is used in the third step for complete isomorph rejection. A paper where this method is applied to Steiner triple systems is [2]. Further references and more details about the computer programs that were used can be found in [5].

Automorphisms of order 37 act fixed point and fixed line free on S(2, 4, 37) designs. There are two designs with such automorphisms. These cyclic designs are two of the three examples in [9].

The S(2, 4, 37) designs with automorphisms of order 11 were determined by M. Meszka and A. Rosa, but no further details are given in [10]. Therefore we repeat the classification here. As a consequence of Lemma 2.1 automorphisms of order 11 have four collinear fixed points. The corresponding line is obviously fixed, and no further fixed lines are possible because they would have to be fixed pointwise.

Proposition 2.3. There are exactly 284 designs S(2, 4, 37) with automorphisms of order 11.

Proof. The action of an automorphism of order 11 induces four point orbits of size 1 and three of size 11, as well as a single line orbit of size 1 and ten of size 11. The orbit matrix is unique up to rearrangements of rows and columns:

[ \begin{matrix}1 & 11 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 11 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 11 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 11 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 3 & 1 & 0 & 0 & 2 & 2 \\ 0 & 1 & 1 & 1 & 1 & 0 & 3 & 1 & 2 & 0 & 2 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 3 & 2 & 2 & 0 \end{matrix} ]

Here the first four rows and the first column correspond to the fixed points and the fixed line. This orbit matrix can be indexed in many ways, giving rise to a total of 284 nonisomorphic incidence matrices of S(2, 4, 37) designs.

□

3. Automorphisms of order 3

There are several possible sets of points and lines kept fixed by automorphisms of order 3.

Proposition 3.1. Let α be an automorphism of order 3 of a S(2, 4, 37) design. The set of points and lines kept fixed by α is one of the following:

(a) one point and g lines through it, where g = 0, 3, 6, 9 or 12;

(b) four points on a line and two more lines through each of the points;

(c) four points on a line, five more lines through one of the points and two more lines through each of the remaining three points.

Proof. The number of fixed points (one or four) follows from Lemma 2.1. The number of fixed lines and incidences with the fixed points are determined by two obvious claims: (1) every fixed line is incident with either one or four fixed points, and (2) the number of fixed lines through a fixed point is divisible by 3. □

Accordingly, there are seven types of orbit matrices. Dimensions of the matrices range from 13 × 37 in case (a) with g = 0 to 15 × 45 in case (c). The number of orbit matrices is enormous and we were not able to perform a complete classification in either of the seven cases. However, we did examine a particularly interesting case in some detail, namely case (a) with g = 12. Any orbit matrix of this type can be put into the following form:

[ \begin{matrix}j_{12}^{t} & 0_{33}^{t} \\ I_{12} & M \end{matrix} ]

The first row and the first twelve columns of the matrix above correspond to the fixed point and lines, and the remaining rows are ordered lexicographically. Above and in the sequel, I_{n} denotes the identity matrix of order n, while j_{n} and 0_{n} denote the all-one vector and the zero vector with n entries. The unknown part is a 12×33 matrix M. It is not difficult to show that M is necessarily an incidence matrix of a (12, 4, 3) BIBD, i.e. a {0, 1}-matrix satisfying the equations M · M^{t} = 8 I_{12} + 3 J_{12} and M^{t} · j_{12} = 4 j_{33} (J_{n} being the n × n all-one matrix).

According to Mathon and Rosa’s tables [9], there are more than 17 million nonisomorphic (12, 4, 3) BIBDs. The exact number is not known, but this is already too much for indexing with the resources available to us. We were only able to examine a smaller number of orbit matrices, generated in several ways.

We first looked at orbit matrices corresponding to (12, 4, 3) BIBDs with some additional properties. All resolvable (12, 4, 3) designs were determined by L.B. Morales and C. Velarde [12]; there are only five such designs. In terms of [12], the orbit matrices corresponding to (12, 4, 3)-RBIBDs number 1, 2 and 3 can be indexed; the ones corresponding to designs number 4 and 5 cannot. Nine S(2, 4, 37) designs arise, but one of them has an automorphism of order 11 and was already constructed in the previous section.

Morales’ and Velarde’s designs number 1 and 5 have an automorphism of order 3 without fixed points and lines. We were able to find all (12, 4, 3) BIBDs with such an automorphism, using the orbit matrix method described earlier. Without going into details, there are 1197 such BIBDs; 182 of the corresponding orbit matrices could be indexed, giving rise to 217 nonisomorphic S(2, 4, 37) designs. All but six of them are new (these six are the ones arising from the (12, 4, 3)-RBIBD number 1). Although the automorphism of the orbit matrix was not taken into account for indexing, the majority of the constructed S(2, 4, 37) designs (214 of 217) actually have full automorphism groups of order at least 9.

Finally, we generated (12, 4, 3) BIBDs at random using a tabu search algorithm described in [6]. Some 500000 designs were constructed, most of them with trivial full automorphism groups. About 1700 of the corresponding orbit matrices could be indexed, giving rise to 1745 Steiner 2-designs S(2, 4, 37). All have ℤ_{3} as their full automorphism group and none are isomorphic to the previously constructed designs.

Although we only considered automorphisms of order 3 fixing one point and 12 lines, a number of the 2250 designs constructed so far (including the cyclic examples) posses automorphisms of order 3 with other fixed structures. Besides type (a) with g = 12, automorphisms of type (a) with g = 0 and of type (b) also occur. It remains to be seen whether automorphisms of type (a) with g = 3, 6, 9 and of type (c) are possible.

4. Automorphisms of order 2

Lemma 2.1 does not apply to involutory automorphisms of S(2, 4, 37) designs. Possible configurations of fixed points and lines can be determined similarly as in [5, Theorem 2.6].

Proposition 4.1. Let α be an automorphism of order 2 of a S(2, 4, 37) design. The set of points and lines kept fixed by α is one of the following:

(a) one point and nine lines without incidences;

(b) four points on a line and one more point outside that line; all the lines joining the fixed points and six more lines without incidences;

(c) five points in general position (no three collinear), ten lines joining the fixed points and three more lines without incidences;

(d) the unique linear space with 13 points and 23 lines, 11 of the lines incident with four points and 12 with two points.

Configurations (b) and (c) are shown in Figure 1. The linear space (d) is obtained by breaking up into pairs two lines of a finite projective plane of order 3.

Figure 1. Configurations (b) and (c) of Proposition4.1.

Proof. Let f, g be the number of fixed points and lines and m, n the number of point and line orbits of size 2, respectively. Clearly f + 2m = v = 37 and g + 2n = b = 111. Denote the set of lines incident with exactly i fixed points by B_{i} and let b_{i} = |B_{i}|, for i = 0, …, 4. Obviously, B_{3} is empty (b_{3} = 0) and lines in B_{2} and B_{4} are fixed. Lines in B_{1} are not fixed and lines in B_{0} can be either fixed or non-fixed. Let b′_{0} be the number of fixed lines in B_{0} and b′′_{0} the number of non-fixed lines in B_{0}. These numbers satisfy the following system of equations.

\begin{aligned}b′_{0} + b′′_{0} + b_{1} + b_{2} + b_{4} & = & b = 111 \\ b′_{0} + b_{2} + b_{4} & = & g = 111 − 2n \\ 2b′_{0} + b_{2} & = & m \\ b_{2} + 6b_{4} & = & \binom{f}{2} = (37 − 2m)(18 − m) \\ 6(b′_{0} + b′′_{0}) + 3b_{1} + b_{2} & = & \binom{2m}{2} = m(2m − 1) \end{aligned}

The first three equations are obtained by expressing the total number of lines, the number of fixed lines and the number of point orbits of size 2 in terms of the b_{i}s. The fourth and fifth equation follow by counting pairs of fixed points and pairs of non-fixed points, respectively. The system of equations has a unique solution if m and n are known:

\begin{aligned}b′_{0} & = & \frac{m(m − 34)}{2} + 2n \\ b′′_{0} & = & 22m − 6n \\ b_{1} & = & −22m + 8n \\ b_{2} & = & m(35 − m) − 6n \\ b_{4} & = & 111 + \frac{m(m − 36)}{2} + n \end{aligned}

Non-negative integers are obtained for seven pairs (m, n) ∈ {1, …, 18} × {1, …, 55}, reported in Table 1. Rows 1-3 clearly correspond to configu-

\begin{matrix}No. & m & n & b′_{0} & b′′_{0} & b_{1} & b_{2} & b_{4} & f & g \\ 1 & 18 & 51 & 9 & 90 & 12 & 0 & 0 & 1 & 9 \\ 2 & 16 & 50 & 6 & 52 & 48 & 4 & 1 & 5 & 11 \\ 3 & 16 & 49 & 3 & 58 & 40 & 10 & 0 & 5 & 13 \\ 4 & 14 & 49 & 7 & 14 & 84 & 0 & 6 & 9 & 13 \\ 5 & 14 & 48 & 4 & 20 & 76 & 6 & 5 & 9 & 15 \\ 6 & 14 & 47 & 1 & 26 & 68 & 12 & 4 & 9 & 17 \\ 7 & 12 & 44 & 0 & 0 & 88 & 12 & 11 & 13 & 23 \end{matrix}

Table 1. Pairs (m, n) yielding non-negative integer values for the b_{i}s. rations (a)-(c). Rows 4-6 describe impossible configurations. They contain four or more lines fixed pointwise (b_{4} ≥ 4), but only nine fixed points (f = 9). Row 7 corresponds to the linear space (d). The uniqueness of such a linear space was established by an exhaustive computer search. □

Here the most interesting case is (d). Let f be the number of points of a S(2, k, v) design kept fixed by an automorphism of prime order p. In [7, Theorem 2.2] the following bound was proved:

f ≤ \{ \begin{matrix}r + k − p − 1, & if p ≤ k − 1, \\ r − \frac{p−1}{k−1}, & if p ≥ k. \end{matrix}

If the bound is met with equality, the design is called a p-MFP(v, k) (“MFP” is an abbreviation for “maximum fixed point”).

Designs S(2, 4, 37) with involutory automorphisms of type (d) are 2-MFP(37, 4). An example was constructed in [7]. The authors note that non-fixed points and lines of a 2-MFP(37, 4) constitute a 3-GDD of type 2^{12}, i.e. a S(2, 3, 25) design with one point and all lines through it removed (for a general definition see [13]). The approach in [7] is first to generate such GDDs, then try to attach the fixed part (the linear space (d)). This turned out to be quite difficult, because the two parts need to be compliant with each other to form a S(2, 4, 37) design (for a more precise description see [7]).

Our orbit matrix approach differs in two aspects. First, the non-fixed part of an orbit matrix only records incidences of the orbits, not of individual points and lines. In this case the non-fixed part is an incidence matrix of a (12, 3, 2) BIBD; it becomes a 3-GDD of type 2^{12} after indexing. Furthermore, we do not build orbit matrices by joining the fixed part with complete (12, 3, 2) BIBDs. Instead, we build them up row by row, at each step taking into account necessary interconnections of the fixed part and the non-fixed part.

P.R.J. Östergård [14] showed that there are exactly 242995846 nonisomorphic (12, 3, 2) BIBDs, among them 88616310 simple ones (without repeated blocks). There is no simple connection with the number of orbit matrices. For some (12, 3, 2) BIBDs it may not be possible to adjoin the linear space (d), while for others it can be done in several inequivalent ways. We were not able to perform a complete classification of orbit matrices, but we very quickly got thousands of examples. When the underlying (12, 3, 2) BIBD has repeated blocks, it is easy to see that the orbit matrix cannot be indexed. On the other hand, all of the orbit matrices based on simple (12, 3, 2) BIBDs that were examined could be indexed, always producing 4096 or 8192 S(2, 4, 37) designs. Thus, we literally got millions of S(2, 4, 37)s. It would take lots of CPU time and memory to test them all for isomorphism. We did this only for designs arising from the first 12 orbit matrices, and got 49152 nonisomorphic S(2, 4, 37) designs. All have ℤ_{2} as the full automorphism group and none are isomorphic to the previously constructed designs.

Some of the designs constructed in the previous sections also have automorphisms of order 2, besides automorphisms of order 3 and 11. These involutory automorphisms are of type (a) and (c) (cf. Proposition 4.1), while type (b) does not occur.

5. Concluding remarks

The designs constructed in this work give a new lower bound for the number of pairwise nonisomorphic S(2, 4, 37)s.

Proposition 5.1. There are at least 51402 noisomorphic S(2, 4, 37) designs.

However, the actual number of designs is evidently much larger. The distribution of the 51402 designs by order of full automorphism group is given in Table 2, and their incidence matrices can be downloaded from the author’s web page http://www.math.hr/~krcko. The list of incidence matrices starts with the two cyclic examples, followed by the 284 designs with automorphisms of order 11 and the remaining designs with automorphisms of order 3 and 2.

Necessary conditions for resolvability are not satisfied, but S(2, 4, 37) designs can be near resolvable. This means that by deleting a suitably chosen point and all lines through it, a resolvable incidence structure is obtained. Exactly 10 designs from our list are near resolvable (among them are the 9 designs arising from resolvable (12, 4, 3) BIBDs).

M. Meszka and A. Rosa [10] initiated a systematic study of embeddings of S(2, 3, v) designs into S(2, 4, w) designs. The embedding spectrum E(v) is defined as the set of all admissible w for which a S(2, 4, w) design with a S(2, 3, v) subdesign exists. In [10], E(7) is completely determined, and E(9) with one possible exception, w = 37. A search for subdesigns revealed that 49679 designs from our list have S(2, 3, 7) subdesigns and 244 have S(2, 3, 9) subdesigns (both kinds of subdesigns appear in 84 of our designs). An example is obtained by developing the following base blocks over ℤ_{9} (this

|Aut| # |Aut| # |Aut| # |Aut| #
111 1 33 4 11 280  2 49152
54 4 27 2 9 203
37 1 18 7  3 1748

Table 2. Distribution by order of full automorphism group. is design no. 304 from the list).

{∞, a_{0}, a_{3}, a_{6}}, {∞, b_{0}, b_{3}, b_{6}}, {∞, c_{0}, c_{3}, c_{6}}, {∞, d_{0}, d_{3}, d_{6}},
{a_{0}, a_{1}, b_{3}, c_{0}}, {a_{0}, a_{5}, b_{6}, c_{6}}, {a_{0}, a_{7}, d_{0}, d_{1}}, {a_{0}, b_{0}, b_{4}, c_{3}},
{a_{1}, c_{3}, c_{8}, d_{0}}, {a_{2}, c_{6}, c_{7}, d_{0}}, {a_{3}, b_{8}, d_{0}, d_{7}}, {a_{4}, b_{2}, b_{3}, d_{0}},
{b_{0}, c_{1}, d_{0}, d_{5}}, {b_{5}, b_{7}, c_{0}, d_{0}}, {b_{6}, c_{2}, c_{4}, d_{0}}

The points {a_{0}, a_{3}, a_{6}, b_{0}, b_{3}, b_{6}, c_{0}, c_{3}, c_{6}} induce a S(2, 3, 9) subdesign. Thus, 37 ∈ E(9) and [10, Theorem 21] can be strengthened to the following.

Theorem 5.2. E(9) = {13} ∪ {w | w ≡ 1, 4 (mod 12), w ≥ 28}

References

[1] P. Bofill and C. Torras, MBMUDs: a combinatorial extension of BIBDs showing good optimality behaviour, J. Statist. Plann. Inference (to appear).

[2] C.J. Colbourn, S.S. Magliveras and D.R. Stinson, Steiner triple systems of order 19 with nontrivial automorphism group, Math. Comp. 59 (1992), 283–295.

[3] F. Franek, T.S. Griggs, C.C. Lindner and A. Rosa, Completing the spectrum of 2-chromatic S(2, 4, v), Discrete Math. 247 (2002), 225–228.

[4] V. Krčadinac, Steiner 2-designs S(2, 5, 41) with automorphisms of order 3, J. Combin. Math. Combin. Comput. 43 (2002), 83–99.

[5] V. Krčadinac, Steiner 2-designs S(2, 4, 28) with nontrivial automorphisms, Glas. Mat. Ser. III 37(57) (2002), 259–268.

[6] V. Krčadinac, Constructing block designs by tabu search, preprint.

[7] D.L. Kreher, D.R. Stinson and L. Zhu, On the maximum number of fixed points in automorphisms of prime order of 2-(v, k, 1) designs, Ann. Comb. 1 (1997), 227–243.

[8] R. Mathon, “Computational methods in design theory,” Computational and constructive design theory, W.D. Wallis (Editor), Kluwer Academic Publishers, 1996, pp. 29–48.

[9] R. Mathon and A. Rosa, “2-(v, k, λ) designs of small order,” The CRC handbook of combinatorial designs, C.J. Colbourn and J.H. Dinitz (Editors), CRC Press, 1996, pp. 3–41.

[10] M. Meszka and A. Rosa, Embedding Steiner triple systems into Steiner systems S(2, 4, v), Discrete Math. 274 (2004), 199–212.

[11] B.D. McKay, nauty user’s guide (version 1.5), Technical Report TR-CS-90-02, Department of Computer Science, Australian National University, 1990.

[12] L.B. Morales and C. Velarde, A complete classification of (12, 4, 3)-RBIBDs, J. Combin. Des. 9 (2001), 385–400.

[13] R.C. Mullin, H.-D. Gronau, “PBDs and GDDs: the basics,” The CRC handbook of combinatorial designs, C.J. Colbourn and J.H. Dinitz (Editors), CRC Press, 1996, pp. 185–193.

[14] P.R.J. Östergård, Enumeration of 2-(12, 3, 2) designs, Australas. J. Combin. 22 (2000), 227–231.

[15] D.R. Stinson and H. Ferch, 2000000 Steiner triple systems of order 19, Math. Comp. 44 (1985), 533–535.

Department of Mathematics, University of Zagreb, P.P. 335, HR-10002 Zagreb, Croatia

E-mail address: krcko@math.hr