key: cord-0047203-dvtlxtcq
authors: Topalova, Svetlana; Zhelezova, Stela
title: Isomorphism and Invariants of Parallelisms of Projective Spaces
date: 2020-06-06
journal: Mathematical Software - ICMS 2020
DOI: 10.1007/978-3-030-52200-1_16
sha: 49f542dc5f82f052201423dbdcffc59d552d7005
doc_id: 47203
cord_uid: dvtlxtcq

We consider the computer-aided constructive classification of parallelisms with predefined automorphism groups in small finite projective spaces. The usage of a backtrack search algorithm makes it very important to filter away equivalent partial solutions as soon as possible and to use a fast method for checking for isomorphism of any two parallelisms. The rejection of most of the equivalent solutions can be done by a test which uses the normalizer of the predefined automorphism group. We consider the applicability and effectiveness of such a test, and present sensitive invariants of resolutions of Steiner 2-designs. They can be used to facilitate any type of test for isomorphism of parallelisms.

invariants, however, can obviously not be isomorphic to each other, and this is very useful. The sensitivity of an invariant is measured by the ratio of the number of classes it distinguishes to the number of non-isomorphic objects under consideration [10] . A complete invariant has sensitivity 1. In a less formal manner, an invariant with relatively high sensitivity is called sensitive. Very often, however, sensitive invariants need considerable time to be calculated, and a considerable amount of memory to be stored.

The present paper describes invariants of design resolutions and parallelisms of projective spaces. These invariants are quite simple. They can be calculated and compared relatively fast and do not need much memory to be stored. We do not know previous papers presenting them. We show their effectiveness on some of our recent classifications of parallelisms with a predefined automorphism group. The invariants are used after the rejection of most of the isomorphic solutions by a normalizer-based minimality test (NM test). We present the main principles of such a test and point out the cases in which it may not establish that two parallelisms are isomorphic, and therefore the calculation of good invariants might be very helpful.

The basic concepts and notations concerning designs and resolutions, and spreads and parallelisms in projective spaces, can be found, for instance, in [14, 16, 38] .

A t-spread in the projective space P G(n, q) is a set of distinct t-dimensional subspaces which partition the point set. A t-parallelism is a partition of the set of t-dimensional subspaces by t-spreads. Usually 1-spreads and 1-parallelisms are called line spreads (parallelisms) or just spreads (parallelisms). There can be line spreads and parallelisms if n is odd. Two parallelisms are isomorphic if there exists an automorphism of the projective space which maps each spread of the first parallelism to a spread of the second one.

Let v, k, and λ be positive integers,

be a finite set of points, and B = {B j } b j=1 a finite collection of k-element subsets of V , called blocks. D = (V, B) is a 2-design with parameters 2-(v,k,λ) if any 2-subset of V is contained in exactly λ blocks of B. If λ = 1 the design is called a Steiner 2-design. A parallel class is a partition of the point set by blocks. A resolution of the design is a partition of the collection of blocks by parallel classes. Two resolutions are isomorphic if there exists an automorphism of the design which maps each parallel class of the first resolution to a parallel class of the second one. Proposition 1. [37, 2.35-2.36 ] The incidence of the points and t-dimensional subspaces of P G(n, q) defines a 2-design. There is a one-to-one correspondence between the t-parallelisms of P G(n, q) and the resolutions of this design. Example 1. A parallelism of P G (3, 2) . The projective space P G(3, 2) has 15 points and 35 lines with 3 points each. A parallelisms has 7 spreads consisting of 5 disjoint lines. The point-line incidence defines a 2-(15, 3, 1) design ( Fig. 1 ) whose points and blocks correspond respectively to the points and lines of the projective space. The parallelisms of P G (3, 2) correspond to resolutions of this design (Fig. 2) . P\B 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 There are several theoretical constructions of infinite families of parallelisms that are presently known [2, 7, 11, 15, 28, 42] . A full classification is available in P G (3, 2) and P G(3, 3) [3] , but it is currently out of reach in the other projective spaces. There are computer aided classifications of parallelisms with predefined automorphism groups [5, 6, 13, [29] [30] [31] 34, 36, [39] [40] [41] ].

Section 2 briefly describes the specifics of the classification problem for parallelisms and the approach that we have used in several recent works. One of the major difficulties in all these cases is the final test for isomorphism of the obtained parallelisms. Since parallelisms can be considered as resolutions of the point-line design of P G(n, q), Sect. 3 is devoted to invariants of design resolutions. The invariants that we offer, are fast to calculate, do not need too much memory to store, and partition the parallelisms to numerous invariant classes. Section 4 is a comment on their further usability for the classification of parallelisms with bigger parameters, and on their applicability to other problems.

The software for construction of parallelisms is based on the exhaustive backtrack search techniques. A lexicographic order can be defined both on the parallelisms, and on the partial solutions. This allows the rejection of partial solutions which are not minimal with respect to the lexicographic order. Such a technique for classification of various combinatorial structures is known as orderly generation [12] , [21, chapter 4] , [33] . One way to implement the method is by applying a minimality test to some of the partial solutions and to all full solutions.

The automorphism group G ∼ = P Γ L(n+1, q) of the projective space P G(n, q), however, is very rich, and this makes the minimality test too slow. That is why only a normalizer-based minimality test (NM test) is usually applied when parallelisms invariant under some predefined automorphism group G c are classified. The NM test checks if the normalizer N (G c ) = g ∈ G | gG c g −1 = G c contains an element which maps the constructed (partial) parallelism to a lexicographically smaller (partial) solution. If so, the current (partial) solution is discarded. We briefly explain below how the normalizer can help us remove isomorphic solutions.

Let G c be a Sylow subgroup of the automorphism group of P G(n, q), and let each of the parallelisms P and P be invariant under G c . Then to establish an isomorphism of P and P it is enough to check if there is an element of the normalizer

Proof. The statement was first proved in [31] for parallelisms of P G (3, 5) with automorphisms of order 31. We present here the main ideas for the general case. Denote by G P the full automorphism group of P . We have to check if there is some ϕ ∈ G such that P = ϕP . Let α ∈ G c . Then ϕP = αϕP and thus P = ϕ −1 αϕP . Namely ϕ −1 αϕ is also an automorphism of P . That is why P is invariant both under G c and under

If G c and ϕ −1 G c ϕ are conjugate in G P too (for instance, this always holds if G c is a Sylow subgroup of G), then since ϕ is not an automorphism of P , there must exist an automorphism β ∈ G P , such that ϕ −1 G c ϕ = βG c β −1 . Then G c = ϕβG c β −1 ϕ −1 and therefore ϕβ ∈ N G (G c ). Since ϕβP = ϕP , the statement follows.

If the predefined group is not a Sylow subgroup of G, the normalizer-based minimality test may not succeed in removing all isomorphic parallelisms. That is why a further test for isomorphism must be applied.

Our experience shows that a very small number of isomorphic parallelisms remain if an NM test has been applied to them. In [40] and [41] we classify parallelisms with predefined groups which are of prime order, but not Sylow, and observe that the NM test removes all isomorphic solutions. Constructing parallelisms of P G (3, 4) invariant under cyclic groups of order 4 [6] we obtain 253344 parallelisms after the NM test, and 252738 after a full test for isomorphism, i.e. the latter removed 0.23% of the solutions obtained after the NM test.

If the number of parallelisms is big, we can first determine the order of their full automorphism groups. Whatever algorithm or software we use for that purpose, invariants of the points, lines and spreads of the parallelism might be very helpful, because only points (lines, spreads) with the same invariants can be mapped to one another. When we know the full automorphism groups, we can look for isomorphisms only among parallelisms with |G P | > |G c |. In the cases that we have considered, the percentage of these parallelisms is very small. Their number, however, might be quite big, and therefore it might be very slow to test for isomorphisms any two of them. If we can easily calculate sensitive invariants of the parallelisms, we can only check for isomorphisms among parallelisms with the same invariants.

Parallelisms can be considered as resolutions of the point-line design of the projective space. The next section presents the invariants we use, as invariants of resolutions of Steiner 2-designs, because we believe that they can also have various applications outside the parallelisms classification problem.

Resolutions of designs with small parameters have been classified in many papers (for instance, [20, 22, 26, 27] ). The invariants that are usually used, are the order of the automorphism group and some properties of the underlying design.

The resolution isomorphism problem can be transformed to graph isomorphism problems (for instance, Betten's approach in [5] ). This makes it possible to use Nauty [25] or some other graph isomorphism software [4, 18, 23, 32] , and to use graph invariants to distinguish resolutions in a way similar to that for designs (for example, [22, 24] ). These invariants, however, do not take in consideration the fact that we deal with resolutions and are therefore quite complex.

Invariants of resolutions (not of their underlying design, or related graph) are used in the works of Morales and Velarde [26, 27] and Kaski et al. [20] who construct matrices of the intersections between the parallel classes. The invariants and their usage are different from those that we describe. Invariants of resolutions of 2-(v, 3, 1) designs (Kirkman triple systems) are applied by Stinson and Vanstone in [35] . They are defined by a function which maps 3-subsets of points to 3-subsets of parallel classes and are different from the invariants we present.

Our first aim is to describe the relation of each block to each resolution class. Consider a resolution of a 2-(v, k, λ) design with b blocks and r parallel classes . Denote by B 1 , B 2 , . . . B b the blocks of the design, and by C 1 , C 2 , . . . C r the parallel classes of the resolution. Denote by N d j the number of blocks in the parallel class of block B j , which are different from B j and disjoint with all the blocks of class C d that contain some of the points of B j . The number N d j remains unchanged by a permutation of the points of the design, and a permutation of the blocks which maps parallel classes to parallel classes defines a permutation on the numbers N d j , where d = 1, 2, . . . r and j = 1, 2, . . . b.

A resolution isomorphism maps parallel classes to parallel classes. That is why the vector Ω j will be the same for the image of B j under a resolution isomorphism. So we will call these vectors resolution block invariant vectors, or just block invariants. To compare block invariants we define a lexicographic order such that

Let n b be the number of the different block invariants and let us denote them by β 1 , β 2 , . . . β n b , and the set they form, by β. The block invariants are relatively easy to calculate, because they are based on the relation of each block to the r parallel classes, while the most used block invariants of designs [22] present the relation of each block to all the (b-1)(b-2)/2 pairs of different other blocks. For the design considered in Example 2, for instance, r = 21 and b = 357.

Each point P i is in r blocks. Their block invariants become the elements of a resolution point invariant vector Π i = (β i1 , β i2 , . . . β ir ), such that β ij ≤ β ij+1 . We next find the number n p of the different point invariants and denote them by π 1 , π 2 , . . . π np , and the set of these invariants by π. Each parallel class C l contains v/k blocks. Their block invariants make up a resolution class invariant vector Γ l = (β l1 , β l2 , . . . β l v/k ), such that β lj ≤ β lj+1 . We denote the different class invariants by γ 1 , γ 2 , . . . γ nc and the set they comprise by γ.

Example 2. Parallelisms of P G (3, 4) . They can be considered as resolutions of the 2-(85, 5, 1) point-line design. There are 21 parallel classes with 17 blocks each. Table 1 presents three of the parallel classes of a resolution with automorphism group order 960. The blocks are given by their points.

In this example N 2 2 = 12, because each of the blocks B 6 , B 7 , . . . , B 17 of parallel class C 1 is disjoint with each of the blocks B 18 , B 19 , . . . , B 22 (these blocks of C 2 contain points of B 2 ). In the same manner N 3 2 = 6 because blocks B 1 , B 3 , B 6 , B 7 , B 8 , B 9 are pairwise disjoint with blocks B 40 , B 44 , B 46 , B 49 , B 50 , and N 1 2 = 16 because B 1 , B 3 , B 4 , . . . , B 17 are disjoint with B 2 . In the same way we find N d 2 for d = 4, 5, . . . , 21 (for the classes that are not given in Table 1 ). In total, the value is 6 for 15 classes, 12 for five, and 16 for C 1 , namely Ω 2 = (0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 5, 0, 0, 0, 1). We proceed with finding Ω j for each j = 1, 3, 4, . . . 357, and establish that there are n b = 5 different vectors Table 2 . The number m in column inv of Table 1 means that the block invariant is β m . We next calculate the point invariants and establish that n p = 2, namely Π i = π 1 = (1, 3, . . . , 3, 4, 4, 4, 4) for i ≤ 5 and Π i = π 2 = (2, 3, 3, 3, 3, 4, 5, . . . , 5) for i > 5. This means that the first five points, for instance, are in one block with invariant β 1 , 12 blocks with invariant β 3 , and 4 blocks with invariant β 4 . Finally we calculate the invariants of the classes and obtain that Γ 1 = γ 1 = (1, 2, . . . , 2) for the first parallel class and Γ l = γ 2 = (3, 3, 3, 3, 4, 5, . . . , 5) for l > 1.

Interested readers can obtain the whole example using the invariant calculation C++ source available at http://www.moi.math.bas.bg/moiuser/ ∼ stela and the example files going with it.

The invariant sets β = {β 1 , β 2 , . . . , β n b }, π = π 1 , π 2 , . . . , π np and γ = {γ 1 , γ 2 , . . . , γ nc } make up an invariant of the resolution. We calculated the resolution invariants for some of the known nonisomorphic parallelisms of P G (3, 4) [5, 6, [39] [40] [41] . They partition the parallelisms to invariant classes that contain either one, or two parallelisms. The results are presented in Table 3 , where |G P | is the order of the full automorphism group, I the number of invariant classes, N the number of isomorphism classes, and S the sensitivity of the invariant, S = I/N . The most complex part of the invariant calculation is the determination of the block invariants Ω 1 , Ω 2 , . . . , Ω b . It can be done, for instance, as shown in Example 3, where the main operations are repeated b 3 r times, b is the number of blocks, and r the number of parallel classes. The complexity is O(b 3 ), but the actual performance is faster because b r = v k is much smaller than b. 

-Our experience with classification of parallelisms with predefined automorphism groups, shows that the normalizer-based minimality test is a powerful fast way of filtering away most of the isomorphic solutions. -The invariants presented in Sect. 3 are very useful for the classification of the parallelisms we applied them to, because they partition them to numerous small invariant classes. We believe that they will be helpful to future classifications of parallelisms with bigger parameters too. -We suppose that these invariants will work well on the resolutions of any 2-(v, k, 1) design (Steiner 2-design). For resolutions of designs with λ = 1, however, modifications of the block invariants might be more suitable, such that the exact number of common points of two blocks is encountered (not only if these blocks are disjoint or not).

Large Arcs in Small Planes

Partitioning the planes of AG2m(2) into 2-designs

The packings of P G(3, 3)

Orbiter -A program to classify discrete objects

Parallelisms of P G(3, 4) invariant under a Baer involution

Parallelisms of PG(3, 4) invariant under cyclic groups of order 4

On parallelisms in finite projective spaces

About the code equivalence

Representing equivalence problems for combinatorial objects

Algorithmic aspects of combinatorial designs: a survey

Some packings of projective spaces

Constructive enumeration of combinatorial objects

Mutually 2-orthogonal resolutions of finite projective space

Handbook of Combinatorial Designs. Discrete mathematics and its applications

Some new classes of finite parallelisms. Note Mat

Combinatorics of Spreads and Parallelisms. Chapman & Hall Pure and Applied Mathematics

New invariants for incidence structures

Bliss: a tool for computing automorphism groups and canonical labelings of graphs

Engineering an efficient canonical labeling tool for large and sparse graphs

Classification of resolvable 2-(14,7,12) and 3-(14,7,5) designs

Classification Algorithms for Codes and Designs

The Steiner systems S(2, 4, 25) with nontrivial automorphism group

Practical graph isomorphism

Nauty User's Guide (Version 2.6)

A complete classification of (12, 4, 3)-RBIBDs

Enumeration of resolvable 2-(10, 5, 16) and 3-(10, 5, 6) designs

Regular packings of P G(3, q)

3) invariant under a collineation of order 5

Uniform parallelisms of PG(3,3)

The cyclic parallelisms of P G(3, 5)

Every one a winner; or, How to avoid isomorphism search when cataloguing combinatorial configurations

Resolutions of P G(5, 2) with point-cyclic automorphism group

Some non-isomorphic Kirkman triple systems of orders 39 and 51

Orthogonal packings in P G(5, 2)

Handbook of Combinatorial Designs

Combinatorial Configurations. Longman Scientific and Technical

On transitive parallelisms of P G(3, 4)

On point-transitive and transitive deficiency one parallelisms of P G(3, 4)

New parallelisms of P G(3, 4)

Interrelation of Preparata and Hamming codes and extension of Hamming codes to new double-error-correcting codes