GLASNIK MATEMATIČKI Vol. 40(60)(2005), 139 – 147

FINITE LINEAR SPACES CONSISTING OF TWO SYMMETRIC CONFIGURATIONS

Vedran Krčadinac and Juraj Šiftar

University of Zagreb, Croatia

Abstract. We investigate finite linear spaces consisting of two symmetric configurations. A construction method using projective planes is presented, giving a possibly infinite number of examples. Other examples are constructed by difference families and authomorphism groups, including a complete classification of the smallest case. A question whether any Steiner 2-design with twice as many lines as points belongs to this family of linear spaces is raised, and answered in the affirmative for all known examples of such designs.

1. Introduction

A finite linear space is an incidence structure with v points and b lines, subject to the conditions:

1. any two points are joined by a unique line and

2. each line is incident with at least two points.

A line incident with exactly k points is said to be of length k and is also called a k-line. Assume that k and l are integers with 2 ≤ k ≤ l. A linear space will be called a TSC space for (k, l), briefly a TSC(k, l), if the following conditions are met:

(3) the set of lines can be partitioned into two subsets, the first containing only k-lines, the second only l-lines;

(4) each point is incident with exactly k lines from the first subset and l lines from the second subset.

2000 Mathematics Subject Classification. 51E26, 05B30.

Key words and phrases. Finite linear space, symmetric configuration.

Here, TSC stands for “twofold symmetric configuration”. Namely, in a TSC space the set of points together with the first subset of lines is a (v_{k}) configuration, and with the second subset it is a (v_{l}) configuration. Consequently, the total number of lines in a TSC(k, l) is twice the number of points, b = 2v. By counting incident point-line pairs for all the lines through an arbitrary point, the following relation is obtained:

v = k(k − 1) + l(l − 1) + 1.

Furthermore, TSC spaces are regular, both in the usual sense (each point is incident with exactly k + l lines), and in the stronger sense of A.Betten and D.Betten [1]. This means that the lines through any point partition the complement of this point equivalently, or alternatively that for each k all klines in the linear space constitute a configuration (not necessarily symmetric). In [1] the authors study small examples of such linear spaces, including a complete classification up to v = 14. Regular linear spaces in the usual sense were classified up to v = 12 by H.Gropp [3].

Two extreme cases for the parameters of TSC spaces occur for 2 = k < l and 2 < k = l. In the former case we have v = l(l −1)+3. For l = 3 this gives v = 9, corresponding to incidence structures obtained from the well-known (9_{3}) configurations (the Pappus configuration and two others) by adding a 2line for each pair of points not joined in the original configuration. Generally, any (v_{l}) configuration with v = l(l − 1) + 3 allows such a simple completion to a TSC(2, l).

On the other hand, any TSC(k, k) is actually a Steiner system S(2, k, v) with b = 2v, e.g. S(2, 3, 13), S(2, 4, 25), S(2, 5, 41), etc. A question of interest is whether the converse holds, i.e. can any S(2, k, v) with b = 2v be decomposed into two symmetric (v_{k}) configurations?

The main subject of this paper are “proper” TSC spaces, with parameters 2 < k < l. All TSC(3, 4) will be fully determined and some constructions, using difference families and automorphism groups, will be given for other small parameters. It appears that most of these linear spaces are new. Firstly, however, a direct construction of TSC spaces based on projective planes will be presented.

2. A geometric construction

Let P be a projective plane of order n and B a closed Baer subset of P, other than a subplane. B either consists of (i) all the points on an arbitrary line and all the lines through one of these points, or (ii) all the points on an arbitrary line, another point outside that line and all the lines joining the chosen points. Removing B from P, there remains a group divisible design n-GDD of type n^{n} or (n − 1)^{n+1}, respectively. More precisely, we get an incidence structure with n points on each line and n lines through each point, such that the points can be partitioned into n groups of size n, or n+1 groups of size n − 1. No pair of points from the same group is joined by a line, while each pair of points from different groups is joined by a unique line.

If we take another projective plane P′ of order m with the total number of points equal to the group size from either of the previous two cases, a TSC(m + 1, n) can be constructed by covering all the groups by copies of P′. In the new incidence structure every pair of points is uniquely joined either by an n-line from the GDD, or by an (m + 1)-line from a copy of P′. Obviously, every point is incident with exactly n lines of length n and m + 1 lines of length m + 1. Hence, we have

Theorem 2.1. Provided there exist projective planes of order m and of order n, with n = m^{2} + m + 1 or n = m^{2} + m + 2, there exists a TSC space for (m + 1, n).

All known projective planes are of prime power order. Thus, to actually obtain TSC spaces in the described manner, we need both m and n to be powers of primes. According to a famous conjecture in [10], the integers m and n = m^{2} + m + 1 are indeed simultaneously prime infinitely many times. If the conjecture is true, the first case yields an infinite family of TSC spaces, starting with TSC(3, 7), TSC(4, 13), TSC(6, 31), etc.

In the second case n = m^{2} + m + 2 is even, and thus for our purposes necessarily a power of two. The equation m^{2} + m + 2 = 2^{r} is equivalent to the celebrated Nagell-Ramanujan equation (2m + 1)^{2} + 7 = 2^{r+2}, known to have exactly five solutions (for a simple proof see [4]). Among them only m = 2, r = 3 and m = 5, r = 5 suit our purposes, yielding TSC(3, 8) and TSC(6, 32). These are the only TSC spaces arising in the second case from projective planes of prime power order. Of course, the construction would work just as well without m and n being prime powers if projective planes of non-prime power order were available.

The construction method of Theorem 2.1 allows much variation, producing many nonisomorphic TSC spaces for fixed parameters. Obviously, if nonisomorphic projective planes P and/or P′ are used, different TSC spaces will arise. In general, by varying the closed Baer subset B nonisomorphic GDDs may be obtained, except in Desarguesian planes where any two closed Baer subsets of the same type can be mapped onto each other by a collineation. Even in this case, relabelling the points of P′ within a single or several groups generally gives rise to nonisomorphic TSC spaces. For example, many nonisomorphic TSC(3, 7) can be constructed although projective planes of order 2 and 7 are unique and all GDDs obtained by deleting type (i) Baer subsets of P G(2, 7) are isomorphic.

Finally, let us point out that an analogous construction is not possible if the closed Baer subset B is chosen as a subplane. After removing such a subplane, there remains an n-GDD with groups of size n−\sqrt{n}. Since n−\sqrt{n} is an even number, these groups cannot be covered by projective planes, which always have an odd number of points.

3. Complete classification of TSC(3, 4)

The smallest proper TSC spaces are TSC(3, 4), with 19 points and 38 lines. A cyclic example was discovered by A.Beutelspacher and J.Meinhardt [2], by virtue of being a 4-semiaffine plane. More generally, any TSC(k, l) is {k, l}-semiaffine, meaning that for nonincident point-line pairs (p, L), the number of lines through p missing L is either k or l.

Our goal is to determine all TSC(3, 4) up to isomorphism by an exhaustive computer search and to find invariants by which they can be distinguished. The algorithm that was used builds up incidence matrices of TSC(3, 4) row by row, eliminating isomorphic partial matrices at each step. The search starts from the following 7 × 38 partial incidence matrix:

1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0

The first part of any complete incidence matrix can obviously be put into this form. Suppose that at some step the algorithm produces a list of r×38 partial incidence matrices. In the next step each of these matrices is expanded by one row in all possible ways consistent with the axioms of TSC(3, 4). The added row has 31 entries equal to 0 and 7 entries equal to 1, a single 1-entry in common with each of the previous rows, and column sums in the expanded matrix do not exceed 4. Among the expanded matrices isomorphic copies (equivalent under rearrangement of rows and columns to one of the previous matrices) are omitted. For this task nauty [9] by B.D.McKay is used.

Take an incidence matrix of an arbitrary TSC(3, 4) and order its rows and columns as above. It is not difficult to show by induction that for each r = 7, 8, …, 19 the first r rows of the matrix are isomorphic to one of the constructed partial incidence matrices. Consequently, the 56 matrices with 19 rows obtained in the final step indeed represent all possible TSC(3, 4).

Proposition 3.1. Up to isomorphism there are exactly 56 TSC spaces for (3, 4).

The bulge of the search occurred at row 14, with almost six million nonisomorphic partial incidence matrices. In the next step there remained well over five million 15 × 38 matrices, but from then on the number of matrices dropped quite rapidly. The complete list of incidence matrices will not be reproduced here, but they can be downloaded from the first author’s web page:

                   http://www.math.hr/~krcko

No. |Aut| 4-Q Q 3-P 4-P No. |Aut| 4-Q Q 3-P 4-P
1  57 19 99 4  3 29  1  29 108 5  4
2  57 19 93 4  3 30  1  29 91 6  3
3  12 22 114 5  3 31  1  28 97 6  3
4  12 22 107 6  3 32  1  28 94 6  4
5  12  8 101 5  4 33  1  27 102 6  4
6  4  30 116 6  3 34  1  27 100 6  3
7  4  24 102 6  3 35  1  27 98 6  4
8  4  24 95 6  3 36  1  27 95 6  3
9  4  22 102 6  3 37  1  27 94 5  3
10  4  10 107 5  3 38  1  27 92 6  4
11  3  32 111 6  4 39  1  27 89 6  3
12  3  31 98 6  3 40  1  26 104 6  4
13  3  29 106 6  4 41  1  26 98 6  4
14  3  28 104 5  4 42  1  26 98 6  3
15  3  28 83 5  3 43  1  26 96 5  3
16  3  26 116 6  4 44  1  26 95 6  3
17  3  26 101 5  3 45  1  26 92 6  3
18  3  26 91 6  4 46  1  25 108 5  4
19  3  25 105 6  4 47  1  25 102 6  4
20  3  25 101 6  4 48  1  25 97 6  4
21  3  25 101 6  3 49  1  25 97 5  4
22  3  25 94 5  3 50  1  25 94 5  4
23  3  25 88 5  3 51  1  24 98 6  4
24  3  22 109 5  3 52  1  23 102 5  4
25  3  22 101 5  4 53  1  23 101 6  4
26  3  19 100 5  4 54  1  23 91 5  4
27  1  31 94 6  3 55  1  21 100 5  4
28  1  31 88 6  3 56  1  21 98 6  4

Table 1. Invariants for TSC(3, 4).

Each of the TSC(3, 4) can be uniquely identified by invariants provided in Table 1. The first two columns contain the position at which the incidence matrix occurs in our complete list of representatives and the order of the full automorphism group (computed by nauty [9]). The groups of order 57 are isomorphic to the semidirect product ℤ_{3}.ℤ_{19}, the groups of order 12 to the alternating group A_{4} and the groups of order 4 to the direct product ℤ_{2} × ℤ_{2}. A powerful invariant turned out to be the number of “complete quadrilaterals” contained in the TSC(3, 4), i.e. sets of four lines intersecting in six different points. The total number of such substructures, allowing both 3-lines and 4-lines, is denoted by Q. Additionally, the number of substructures consisting only of 4-lines was enumerated and is denoted by 4-Q. All TSC(3, 4) not distinguished by these numbers could be differentiated by the maximal number of parallel 3-lines and 4-lines, denoted by 3-P and 4-P.

4. Other small examples

A powerful technique for constructing various kinds of incidence structures are difference families. Suppose the incidence structure has a pointregular automorphism group G. We can identify the points with elements of the group G, and blocks (lines) with subsets of G (provided the structure is simple, i.e. no two blocks are incident with the same set of points). The whole incidence structure can be reconstructed from a list of base blocks, comprising a single representative from each block orbit.

We restrict our attention to cyclic difference families for TSC spaces. Suppose D_{1} and D_{2} are subsets of the cyclic group ℤ_{v}, with |D_{1}| = k, |D_{2}| = l and v = k(k − 1) + l(l − 1) + 1. If D_{1} and D_{2} have trivial stabilizers, the development dev{D_{1}, D_{2}} = {x + D_{1} | x ∈ ℤ_{v}} ∪ {x + D_{2} | x ∈ ℤ_{v}} is an incidence structure consisting of k-lines and l-lines, with k lines of length k and l lines of length l through each point. A necessary and sufficient condition for it to be a TSC space is that every element d ∈ ℤ_{v}, d ≠ 0 is uniquely expressible as a difference d = x − y with either x, y ∈ D_{1} or x, y ∈ D_{2}.

(k, l) Group Difference families
(3, 4) ℤ_{19} D_{1} = {0, 1, 8}, D_{2} = {0, 2, 5, 15}
D_{1} = {0, 1, 8}, D_{2} = {0, 2, 6, 16}
(3, 5) ℤ_{27} D_{1} = {0, 1, 5}, D_{2} = {0, 2, 8, 15, 18}
D_{1} = {0, 1, 5}, D_{2} = {0, 2, 11, 14, 21}
(3, 6) ℤ_{37} D_{1} = {0, 1, 11}, D_{2} = {0, 2, 5, 18, 25, 33}
D_{1} = {0, 1, 11}, D_{2} = {0, 2, 6, 14, 21, 34}
D_{1} = {0, 1, 11}, D_{2} = {0, 2, 6, 22, 25, 30}
D_{1} = {0, 1, 11}, D_{2} = {0, 2, 9, 14, 17, 33}
(3, 7) ℤ_{49} D_{1} = {0, 1, 19}, D_{2} = {0, 2, 8, 12, 15, 35, 40}
D_{1} = {0, 1, 19}, D_{2} = {0, 2, 11, 16, 36, 39, 43}
(3, 8) ℤ_{63} D_{1} = {0, 9, 27}, D_{2} = {0, 1, 3, 7, 15, 20, 31, 41}
D_{1} = {0, 9, 27}, D_{2} = {0, 1, 11, 35, 41, 43, 48, 60}

Table 2. Cyclic difference families for TSC spaces.

We have mounted a computer search for such difference families. It was possible to examine all the cases with 2 < k < l < 10 exhaustively. Difference families were found for k = 3 and l = 4, 5, 6, 7, 8 and are listed in Table 2. For each pair of parameters there are several difference families, giving rise to nonisomorphic TSC spaces. Interestingly, the two cyclic TSC(3, 7) cannot be obtained by Theorem 2.1, because they contain (49_{7}) configurations that are not GDDs. On the other hand, the TSC(3, 8) obtained by difference families also arise from Theorem 2.1. In fact, the construction of Theorem 2.1 was discovered while analyzing this particular example.

A more general construction method for incidence structures with a prescribed automorphism group relies on the notion of orbit matrices. The method is mainly used for block designs (see [7] for more details and references), but with some minor modifications it can also be applied to TSC spaces.

Proposition 4.1. There are exactly 12 TSC spaces for (4, 5) admitting an automorphism of order 3 without fixed points and lines.

Proof. There are exactly 29712 orbit matrices up to rearrangement of rows and columns. They were classified by an orderly algorithm, similarly as in [7]. Only 12 orbit matrices can be transformed into incidence matrices of TSC(4,5), whereby each of them yields exactly one TSC(4,5). The 12 obtained TSC spaces are mutually nonisomorphic.

A single incidence matrix of a TSC(4, 5) is reproduced in Figure 1 (empty squares correspond to zero-entries, filled squares to one-entries). All 12 incidence matrices can be downloaded from our web page, referred to earlier.

Figure 1. An incidence matrix of a TSC(4, 5).

5. Is every Steiner 2-design with b = 2v a TSC space?

TSC spaces with lines of equal length are Steiner 2-designs having twice as many lines as points. Such designs have parameters S(2, k, v), v = 2k^{2}−2k+1. For the converse to be true, it should be possible to partition lines of the design into two symmetric (v_{k}) configurations. As opposed to the obvious and unique partition by separating “short” and “long” lines when k < l, the task is far more difficult if all the lines are of equal length. The partition need not be unique and we do not know if it always exists. In this section, known examples of S(2, k, 2k^{2} − 2k + 1) designs are examined.

Up to isomorphism there are exactly two designs S(2, 3, 13) and 18 designs S(2, 4, 25), enumerated by E.Spence [11]. Using a simple backtracking algorithm we were able to determine all partitions into (13_{3}), resp. (25_{4}) configurations. Each of the designs can be partitioned in more ways than one. The minimum occurred for a S(2, 4, 25) allowing only two partitions, while the S(2, 4, 25) with the largest automorphism group (of order 504) allows the most number of partitions, namely 1064.

Proposition 5.1. All Steiner systems S(2, 3, 13) and S(2, 4, 25) are TSC spaces.

The designs S(2, 5, 41) have not been fully classified yet. R.Mathon and A.Rosa [8] constructed four S(2, 5, 41)s with automorphisms of order 5 and one more by applying a certain transformation. V.Krčadinac [6] found 9 further examples with automorphisms of order 3 and another one with a single involution [5]. To the best of our knowledge, these 15 designs are all known examples of S(2, 5, 41)s. Our program was not fast enough to examine the 15 designs exhaustively, but in each case it was possible to find partitions into (41_{5}) configurations by incomplete search.

The existence of S(2, k, 2k^{2} − 2k + 1) designs, k ≥ 6, is an open problem. Thus, all known examples of Steiner 2-designs with b = 2v are TSC spaces, but we do not feel this is enough evidence to make any general conjectures. A negative example is provided by the following (14_{6}, 28_{3}) configuration, which is quite close to S(2, 3, 13), but cannot be partitioned into two symmetric (14_{3}) configurations.

{1, 2, 12} {1, 3, 5}  {1, 6, 10}  {1, 7, 13} {1,8, 9}
{1, 11, 14} {2, 3,13} {2, 4, 6}  {2, 5, 7}  {2, 8, 10}
{2, 9, 11} {3, 4, 8}  {3, 7,10}  {3, 9, 14} {3, 11, 12}
{4, 5, 13} {4, 7, 11} {4, 9, 12}  {4, 10, 14} {5, 6, 11}
{5, 8, 14} {5, 9, 10} {6, 7, 9}  {6, 8, 12} {6, 13, 14}
{7, 12, 14} {8, 11, 13} {10, 12, 13}

References

[1] A. Betten, and D. Betten, Regular linear spaces, Beiträge Algebra Geom. 38 (1997), 111–124.

[2] A. Beutelspacher, and J. Meinhardt, On finite h-semiaffine planes, European J. Combin. 5 (1984), 113–122.

[3] H. Gropp, Configurations and (r, 1)-designs, Discrete Math. 129 (1994), 113–137.

[4] W. Johnson, The diophantine equation X^{2} + 7 = 2^{n}, Amer. Math. Monthly 94 (1987), 59–62.

[5] V. Krčadinac, A new Steiner S(2, 5, 41) design (summary), 2nd Croatian congress of mathematics, Croatian Mathematical Society, 2000, pp. 52.

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

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

[8] 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.

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

[10] A. Schinzel, and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, Acta Arith. 4 (1958), 185-208.

[11] E. Spence, The complete classification of Steiner systems S(2, 4, 25), J. Combin. Des. 4 (1996), 295–300.

E-mail address: krcko@math.hr, siftar@math.hr

Department of Mathematics, Bijenička 30, HR-10002 Zagreb, Croatia