ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.40139 J. Algebra Comb. Discrete Appl. 3(3) • 165–176 Received: 28 October 2015 Accepted: 29 November 2015 Journal of Algebra Combinatorics Discrete Structures and Applications Some new large sets of geometric designs of type LS[3][2, 3, 28] Research Article Michael R. Hurley, Bal K. Khadka, Spyros S. Magliveras Abstract: Let V be an n-dimensional vector space over Fq. By a geometric t-[qn,k,λ] design we mean a collection D of k-dimensional subspaces of V , called blocks, such that every t-dimensional subspace T of V appears in exactly λ blocks in D. A large set, LS[N][t,k,qn], of geometric designs, is a collection of N t-[qn,k,λ] designs which partitions the collection [ V k ] of all k-dimensional subspaces of V . Prior to recent article [4] only large sets of geometric 1-designs were known to exist. However in [4] M. Braun, A. Kohnert, P. Östergard, and A. Wasserman constructed the world’s first large set of geometric 2-designs, namely an LS[3][2,3,28], invariant under a Singer subgroup in GL8(2). In this work we construct an additional 9 distinct, large sets LS[3][2,3,28], with the help of lattice basis-reduction. 2010 MSC: 05B25, 05B40, 05E18 Keywords: Geometric t-designs, Large sets of geometric t-designs, t-designs over GF(q), Parallelisms, Lattice basis reduction, LLL algorithm. 1. Introduction In this article we deal with large sets of geometric t-designs. By a geometric t-design we mean what earlier authors have called t-designs over a finite field, or designs on vector spaces. Geometric t-designs are the Fq-analogs of ordinary t-(v,k,λ) designs. The earliest mention of t-[qn,k,λ] designs, although not using our terminology or notation, was by P.J. Cameron in 1974 [5, 6] and P. Delsarte in 1976 [7]. In 1987, S. Thomas [20] exhibited the first simple geometric 2-design, and in the 1990’s H. Suzuki [19], M. Miyakawa et al. [17] , and T. Itoh [10] constructed new geometric 2-designs and families of such designs. In 1994, D.K. Ray-Chaudhuri and E.J. Schram [18] studied and constructed geometric t-designs from quadratic forms, allowing repeated blocks. For the first time, the latter authors also studied large sets of geometric t-designs. Michael R. Hurley, Bal K. Khadka, Spyros S. Magliveras (Corresponding Author); Department of Mathe- matical Sciences, Florida Atlantic University, Boca Raton, Florida 33472, USA (email: mhurley6@my.fau.edu, bkhadka@my.fau.edu, spyros@fau.edu). 165 M.R. Hurley et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 165–176 M. Braun, A. Kerber and R. Laue [3] constructed in 2005 the first simple geometric 3-design. In 2013, Braun et al. [2] constructed the first example of a q-Steiner system, that is a simple, geometric t-design with λ = 1, namely a 2-[213, 3, 1] design. In a short recent arXiv preprint [8], and based on a probabilistic existence theorem of G. Kuperberg, S. Lovett and R. Peled in preprint [14], A. Fazeli, S. Lovett, and A. Vardy, appear to have proved the remarkable theorem that simple geometric t-designs exist for all values of t. This would be a q-analog of the famous theorem of L. Tierlinck for ordinary t-designs. It should be noted however, that the result in [8] is purely existential and there is no known efficient algorithm which can produce t-[qn,k,λ] designs for t > 3. The authors present the following challenge: Problem 1.1. Design an efficient algorithm to produce simple, non-trivial t-[qn,k,λ] designs for large t, (say t ≥ 4). Of course, finding large sets of geometric t-designs is even harder than just finding geometric t- designs. Prior to recent article [4] only large sets of geometric 1-designs were known to exist. However in [4] M. Braun, A. Kohnert, P. Östergard, and A. Wasserman constructed the world’s first large set of geometric 2-designs, namely an LS[3][2,3,28], invariant under a Singer subgroup in GL8(2). In this paper we construct 9 distinct large sets LS[3][2, 3, 28], all different from the large set con- structed in [4]. The computation involved our APL package knuth for group theoretic matters, and various LLL variants in the NTL library, augmented by certain optimization techniques for parallel lattice basis reduction. It should be noted that some of the recent work on geometric t-designs has been motivated by present day coding theoretic applications as discussed in [9] and [11]. 2. Preliminaries Let V be an n-dimensional vector space over the field Fq. If U is a j-dimensional subspace of V , we say that U is a j-subspace of V . If X is a set and 0 ≤ s ≤ |X|, ( X s ) denotes the collection of all subsets of cardinality s of X. A geometric t-[qn,k,λ] design is a pair (V,B) where B is a multiset of k-subspaces of V , called blocks, such that any t-subspace T of V is contained in exactly λ blocks. (V,B) is said to be simple if B is a set, i.e. if there are no repeated blocks. In this paper we deal only with simple geometric designs, and the square brackets of the symbol t-[qn,k,λ] will imply “geometric” in contrast to the round parentheses for an ordinary t-(v,k,λ) design. We denote the collection of all k-subspaces of V by [ V k ] and note that | [ V k ] | = [ n k ] q , where [ n k ] q is the well known Gaussian binomial coefficient, given by: [ n k ] q = [n]q! [k]q![n−k]q! (1) where for positive integer r, [r]q! := [1]q[2]q · · · [r]q, and [j]q := (1 + q + · · · + qj−1). (2) Analogously to the case of ordinary t-(v,k,λ) designs, a geometric t-[qn,k,λ] design (V,B) is also an s-[qn,k,λi] design for every 0 ≤ s ≤ t with: λs = λ [ n−s t−s ] q / [ k −s t−s ] q , (3) 166 M.R. Hurley et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 165–176 Thus, a necessary condition for the existence of a t-[qn,k,λ] design is that the λs given by the equations (3) must be integral for all 0 ≤ s ≤ t. By a large set LS[N][t,k,qn] we mean a collection L = {(V,Bi)}Ni=1 of simple t-[q n,k,λ] designs where {Bi}Ni=1 is a partition of [ V k ] . We can immediately see that for a given large set LS[N][t,k,qn], N can be expressed in terms of the other parameters as : N = [ n− t k − t ] q /λ (4) Two t-[qn,k,λ] designs D = (V,B) and D′ = (V,B′) are said to be isomorphic if there exists α ∈ GLn(q) such that Bα = B′, that is, Bα ∈B′ for all B ∈B, in which case we also write Dα = D′. If Dα = D, then α is said to be an automorphism of D. The group of all automorphisms of D is denoted by Aut(D). Let B = {Bi}Ni=1 be the collection of designs in a large set L. A group G ≤ GLn(q) is said to be an automorphism group of L if Bg=B for all g ∈ G, that is, if Bgi ∈ B for all Bi ∈ B and g ∈ G. Equivalently, we say that a large set with this property is G-invariant. The group of all automorphisms of L is denoted by Aut(L). If the stronger condition holds, that Bgi =Bi for all Bi ∈ B and g ∈ G, we say that the large set L is [G]-invariant. In 1976, E.S. Kramer and D.M. Mesner [12] presented a theorem which provides necessary and sufficient conditions for the existence of an ordinary G-invariant t-(v,k,λ) design. Beginning with a given group action G|X, the authors define certain integer matrices, presently known as the Kramer-Mesner (KM) matrices. Roughly speaking such a matrix At,k is the result of fusing under G the incidence matrix between ( X t ) and ( X k ) where incidence is set inclusion (fused R.Wilson matrix). These matrices extend naturally to the case of a group G ≤ GLn(q) acting on AGn(q) or PGn−1(q), and provide necessary and sufficient conditions for the existence of geometric, G-invariant t-[qn,k,λ] designs. We proceed to define these matrices in the context of geometric t-designs, and state the analog of the Kramer-Mesner theorem. Let V be an n-dimensional vector space over Fq, and G ≤ GLn(q). Suppose that t and k are integers, 0 ≤ t < k ≤ n, and consider the actions of G on [ V t ] and [ V k ] respectively, with corresponding G-orbit decompositions: [ V t ] = ∆1 + ∆2 + · · · + ∆ρ(t), (5) and [ V k ] = Γ1 + Γ2 + · · · + Γρ(k). (6) where ρ(s) denotes the number of G-orbits on [ X s ] . Just as in [12], it can be shown that for any fixed t-subspaces T,T ′ ∈ ∆i, we have that |{K ∈ Γj : T ≤ K}| = |{K ∈ Γj : T ′ ≤ K}|, (7) that is, the number at,k(i,j) = |{K ∈ Γj : T ≤ K}| is independent of the choice of a fixed T ∈ ∆i. The Kramer-Mesner matrix At,k is then defined as the ρ(t) ×ρ(k) matrix : At,k = (at,k(i,j)) (8) Dually, for K fixed in Γj, let bt,k(i,j) := |{T ∈ ∆i : T ≤ K}|, and define the dual KM matrix Bt,k by: Bt,k = (bt,k(i,j)) (9) In the following Lemma we state without proof geometric analogs of some properties of the At,k and Bt,k as included for the ordinary t-design context in [13]. Lemma 2.1. Let At,k and Bt,k, ∆i, Γj be as defined above. 167 M.R. Hurley et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 165–176 (i) If t ≤ s ≤ k ≤ n, then [ k−t k−s ] q At,k = At,s ·As,k (ii) At,k has constant row sums [ v−t k−t ] q (iii) |∆i| ·At,k(i,j) = |Γj| ·Bt,k(i,j) Keeping in mind that we are only interested in simple geometric t-designs, we now state, without proof, the Kramer-Mesner theorem for geometric t-designs : Theorem 2.2. If G ≤ GLn(q), there is a G-invariant (simple) t-[qn,k,λ] design if and only if there is a ρ(k) × 1 0-1 vector u which is solution of the matrix equation At,ku = λJ (10) where J is the ρ(t) × 1 vector of all 1’s. Here, the 1’s in a solution u select the G-orbits of [ V k ] whose union will constitute the design. The following corollary follows immediately: Corollary 2.3. There is a [G]-invariant large set LS[N][t,k,qn] of geometric designs if and only if there exist N distinct solutions, u1, . . . ,uN, to the matrix equation (10), whose sum is the ρ(k) × 1 all 1’s vector. 3. Main result It is well known that GLn(q) has a cyclic subgroup of order qn−1 , called a Singer subgroup, acting regularly on the non-zero vectors of V = Fnq . It is also known that all Singer subgroups are conjugate in GLn(q). A Singer subgroup G of Γ = GL8(2) is the centralizer of a Sylow-17 subgroup of Γ and its normalizer N in Γ is a split extension of G by its Frobenius group Φ8, thus |N| = 2040. In particular, for the rest of the paper we adopt the notation V = F82, Γ = GL8(2), and G = 〈α〉, where α is the same Singer cycle as the one used in [4], that is : α =   0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0   . We will presently construct 9 distinct large sets of geometric 2 − [28, 3, 21] designs which are [G]- invariant under Singer subgroup G of Γ. We have used the exact same Singer subgroup G = 〈α〉 as in [4] so that it will be easy to check that our large sets are different from the one constructed in [4]. 3.1. Computing and presenting A2,3 Members of [ V 2 ] are Klein 4-groups, and those of [ V 3 ] elementary abelian groups of order 8. Viewed projectively, the 2- and 3-spaces can be seen as collinear triples and Fano planes respectively. There are in all 10795 2-spaces, and 97155 3-spaces. We begin by computing the G-orbits on [ V 2 ] and [ V 3 ] , where G = 〈α〉. There are exactly 43 G-orbits on [ V 2 ] , all of which have length 255, except for one which has length 85. The short orbit is explained by 168 M.R. Hurley et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 165–176 the fact that the cyclic subgroup of order 3 in G fixes a collinear triple. There are 381 G-orbits on [ V 3 ] all of length 255. The vectors of V = F82 are represented by the radix-2 representation of integers in Z256. Orbits of 2- and 3-spaces are represented by the lexically smallest basis among all members of the orbit, but since G is transitive on the non-zero vectors, each such basis will consist of the vector 1 ↔ 00000001, and one (or two) elements of Z256 −{1}. Hence, to represent 〈α〉-orbits of 2-spaces, it suffices to specify the second vector in the lexically minimal basis over all 2-spaces for that orbit. Thus, the 〈α〉-orbits of 2-spaces are represented by the following 43 integers : 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 24, 28, 30, 32, 34, 36, 38, 40, 42, 44, 50, 54, 56, 58 60, 62, 70, 74, 76, 78, 80, 86, 88, 96, 100, 106, 114, 128, 136, 146, 164, 210, 218. Similarly, orbit representatives of the 381 orbits of 3-spaces are given by the pair of integers in Z256 which together with 1, form the lexically minimal basis among the members of the orbit of 3-spaces. The pairs x,y ∈ Z256 representing the G-orbits on 3-spaces will appear in our display of the KM-matrix A2,3 below. To compute A2,3, we found it easier to first compute matrix B2,3 and then compute the A2,3(i,j) entries, using Lemma 2.1, equation (iii) : A2,3(i,j) = |Γj| |∆i| B2,3(i,j). Almost all ratios |Γj||∆i| are 1, that is all, except for those involving the short orbit ∆43 of length 85, in which case the ratio is 3. For any particular Fano plane F in orbit Γj, it is easy to determine how the 7 lines of F are distributed among the orbits {∆i}, thus computation of B2,3 is straightforward. In an effort to overcome the difficulty of presenting in this article the 43 × 381 matrix A2,3, the next two pages display a coded version of A2,3 from which, with a little effort, a user-friendly version of A2,3 can be recovered. Each column of A2,3 is a vector consisting of 43 elements from {0, 1, 3}. We adjoin two extra 0’s at the top of the column and transpose, transforming the column to a row vec- tor v ∈ Z454 . We then use the following alphabet of 64 characters, as digits with values from 0 to 63: 0123456789abcdefghijklmnopqrstuvwxyzABCDEGFHIJKLMNOPQRSTUVWXYZ+− . The vector v ∈ Z454 is separated into 15 triples, and each triple, belonging to Z34, is encoded as a symbol in the alphabet using radix-4 notation. For example, 1000110101000101000000000000000000000000000 =⇒ 001 000 110 101 000 101 000 000 000 000 000 000 000 000 000 =⇒ 1 0 k h 0 h 0 0 0 0 0 0 0 0 0 =⇒ 10kh0h000000000 The next page displays the first 192 columns, and the subsequent page the remaining columns of A2,3. The 381 columns of A2,3 correspond to 381 short rows in the display. For example the short row 5 2 20 10kh0h000000000 means the following: i) 5 is the column index for A2,3, corresponding to the 5th orbit of 3-spaces under G. (ii) Augmenting the pair 2 20 with 1, yields the basis of 3 vectors {1, 2, 20} in F82 from which a Fano plane is constructed, and from which the complete 5th G-orbit can be generated. (iii) By reversing the en- coding process discussed earlier, the code “10kh0h000000000” yields the 5th column of A2,3, as the transpose of 1000110101000101000000000000000000000000000 . Remark 3.1. In passing, we present some properties of A2,3 which may be used to establish still unknown features of designs and large sets related to A2,3. We say that a vector with integer entries has type x λ1 1 x λ2 2 · · ·x λm m if the value xi appears λi times in the vector, for 1 ≤ i ≤ m. (i) The row sums of A2,3 are all 63, as expected, (ii) The vector of column sums of A2,3 is of type 7360921, (iii) The row vectors of the long orbits of 2-spaces are all of type 032016031, (iv) the row vector for the short orbit of 2-spaces is of type 0360321, 169 M.R. Hurley et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 165–176 (v) There are 4 column types for A2,3 as follows: 1 2 4 3k0000000040004 65 4 26 k00l0040001000 129 6 80 400g000001hg0g 2 2 8 1lg000100000100 66 4 32 h000h040g00003 130 6 82 404400401004g0 3 2 12 1k5000000011000 67 4 34 gg004g10000140 131 6 88 4000000400s004 4 2 16 111k0000g000040 68 4 40 hg0004g00gg000 132 6 96 40g40100001500 5 2 20 10kh0h000000000 69 4 42 h040g500400000 133 6 98 40g00g0000kk00 6 2 24 1140M0400000000 70 4 48 gc00000h010000 134 6 106 405000g0000k10 7 2 28 10h050000000013 71 4 50 g10ggg50000000 135 6 112 40g014g00g0g00 8 2 32 100g1k00000040g 72 4 56 g540000h000010 136 6 114 41g040g0001100 9 2 36 100541g000000g0 73 4 58 g1001004g01010 137 6 120 40544010040000 10 2 40 1101g05000000g0 74 4 64 ggh00001gg0000 138 6 122 5000g000150g00 11 2 44 110gg04g4000000 75 4 66 g100001g410400 139 6 130 40010014g0g040 12 2 48 104gg004000g400 76 4 72 g04100g00k4000 140 6 136 4001004140004g 13 2 52 1045g0010004000 77 4 74 ggg000001400k0 141 6 138 4k00k004000100 14 2 56 100g400gk00000g 78 4 80 g0h10040410000 142 6 144 44000g0g0h0010 15 2 60 100110001g10040 79 4 82 h04000000gM000 143 6 146 4000g0140g00h0 16 2 64 10144g001g00000 80 4 90 g040441000g010 144 6 154 40400004h400g0 17 2 68 100004001l00100 81 4 96 g00g0000g11g0g 145 6 160 44000104004440 18 2 72 10001h00gh00000 82 4 98 g0g101000044g0 146 6 162 4000000140k04g 19 2 76 1g0000g040k1000 83 4 104 k00l00g0400000 147 6 168 4g00044g001400 20 2 80 104400k01010000 84 4 106 g0500000504400 148 6 170 50100050g000g0 21 2 84 1000001c000g010 85 4 112 g1040045000g00 149 6 176 400000g140005g 22 2 88 1000000j000400g 86 4 114 g00g1g0400010g 150 6 178 400gg01104g000 23 2 92 1h40000000gg004 87 4 120 k10l0000040000 151 6 192 4001g0g001g100 24 2 96 10400g0000g5040 88 4 122 g000400000ggk4 152 6 194 401400g00h00g0 25 2 100 10g004140000g10 89 4 128 g000g004040gg4 153 6 200 404000001100hg 26 2 104 14k004g00000400 90 4 130 k00l0100010000 154 6 202 50104004100400 27 2 108 1000010hg500000 91 4 136 g000c400000050 155 6 216 40001c0g0g0000 28 2 112 11000000g400hg0 92 4 138 gg000hg0500000 156 6 218 4000104gg00007 29 2 116 101g110g4000000 93 4 144 g0041g10401000 157 6 224 4000g0014g004g 30 2 120 100040k05000g00 94 4 146 h0000000ggg050 158 6 232 4040k0g0g0000g 31 2 124 140004100g40004 95 4 152 g004ggg0g00g00 159 6 234 40g0041000h100 32 2 128 100014k010000g0 96 4 160 g100g40000140g 160 6 240 4g0014110g0000 33 2 132 151000004040004 97 4 162 g0100g001g4040 161 6 242 40000M0g000410 34 2 136 10gg40000g00440 98 4 168 h00011g0000410 162 6 248 40000g0g404014 35 2 140 100004000c00gg0 99 4 170 g00045000000hg 163 6 250 41g01100004004 36 2 144 100010g000g0k10 100 4 176 g00g10g0040g40 164 8 20 10144010040004 37 2 148 1000000101g4110 101 4 178 g000g01g0004h0 165 8 22 10g10g400000gg 38 2 152 10004100g1g0040 102 4 192 g44000g001gg00 166 8 34 10045100014000 39 2 156 1gh000000g4000g 103 4 194 g01000g0g10440 167 8 38 30010g0100000g 40 2 160 10000g000015440 104 4 200 g01000411040g0 168 8 50 11g00054010000 41 2 164 10040g00000504g 105 4 202 gg00000400030g 169 8 52 14000gg10010g0 42 2 168 1000001400005h0 106 4 216 g000141g000440 170 8 66 11004040500g00 43 2 172 1104g040000gg00 107 4 218 g000h00g400007 171 8 70 11100400440100 44 2 176 10000g001105040 108 4 224 g400000h000gg4 172 8 80 1g00l000014000 45 2 180 1000g01l0000010 109 4 226 g0001040000ggk 173 8 82 1g44001000g040 46 2 188 10000010004h40g 110 4 232 g004g10400010g 174 8 98 10005000014k00 47 2 192 100100k0100h000 111 4 234 g041001g001400 175 8 100 140g00g0100k00 48 2 196 1010000g0014013 112 4 240 g400040h0g1000 176 8 102 1g00ghg0100000 49 2 200 1000010044g0gg0 113 4 242 gg004405000010 177 8 112 1104g00g000h00 50 2 204 10010011gg0000g 114 4 248 g0g00g40g44000 178 8 114 1040000g044h00 51 2 212 100000000gh0504 115 4 250 l0000040400007 179 8 116 11041000040050 52 2 216 1000504g0010003 116 6 16 40M00000001h00 180 8 118 11005000015000 53 2 220 10000100g300100 117 6 18 c05000001000g0 181 8 128 10g0001gg000k0 54 2 224 10000004140ggg0 118 6 32 4g00gg0g000g10 182 8 130 1g4100000g5000 55 2 228 1g000400400010k 119 6 34 4l005100000000 183 8 144 10k40h01000000 56 2 232 10110g000005040 120 6 40 5400040g000h00 184 8 146 100000041k1010 57 2 236 10g40101000010g 121 6 42 410g11g0000040 185 8 148 10000014k010g0 58 2 240 1000400000hg0h0 122 6 48 5k004010001000 186 8 160 101000g4000c00 59 2 244 10g51000g000g00 123 6 50 440014400g0040 187 8 162 100101010041g0 60 2 248 140000g0005g004 124 6 56 5000g00gk00003 188 8 166 10g0040g0k0040 61 2 252 100g040k4400000 125 6 58 4h000005004010 189 8 182 10001000g01030 62 4 16 M0h00000104000 126 6 64 400g0001k0004g 190 8 192 140g0010g0g0g0 63 4 18 g0k00101110000 127 6 66 41011101g00000 191 8 194 101g0004g00410 64 4 24 k00l0010000100 128 6 74 401000401g0g0g 192 8 196 10100104410400 170 M.R. Hurley et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 165–176 193 8 198 10g000g10g000k 256 12 192 4h1h00000g000 319 18 226 400040gg0504 194 8 212 10005040054000 257 12 194 41400400g000k 320 18 230 4000hg00401g 195 8 224 1004g04100400g 258 12 196 500000g01g1g0 321 18 234 401g040010g4 196 8 226 10010041101004 259 12 198 44040g4g00400 322 18 236 4h00004g4100 197 8 228 1k04000000010k 260 12 214 4000000040hk3 323 20 38 101g500g000g 198 8 230 1041gg0000010g 261 12 224 40000g1010114 324 20 44 1100gkg0g000 199 8 240 14010g001g000g 262 12 226 44g0444100000 325 20 78 1k4110040000 200 8 242 111000g0001014 263 12 228 4h0l000000004 326 20 102 10010004h110 201 8 244 10g4000g0000c0 264 12 230 5004000h0100g 327 20 132 1g4g05000003 202 8 246 1g000010510004 265 12 240 4h0h0004g0000 328 20 140 14501004g000 203 10 16 gggg0000k00g0 266 12 242 4g10g00440010 329 20 162 1g0001404110 204 10 18 g5g1000400004 267 14 20 11g0g00040044 330 20 164 100040gh004g 205 10 50 g01004g003000 268 14 22 1gg400h0g0000 331 20 170 1000g10011k0 206 10 52 l040000h000g0 269 14 38 1100k000041g0 332 20 192 14010g01g00g 207 10 64 g00g001h50000 270 14 66 30000500g0g00 333 20 202 10010Q00000g 208 10 66 h0104g0004003 271 14 86 1000g0400k044 334 20 206 100g0410g00j 209 10 68 Mg00000g400g0 272 14 100 100g0110g0k00 335 20 230 10010g000g1k 210 10 70 g0000h04g400g 273 14 128 100400gk0g0g0 336 20 234 10g500401004 211 10 84 g00014040g440 274 14 130 10h41000040g0 337 24 38 g0g10k04100 212 10 100 g000hg0100g40 275 14 148 1000g141g0g00 338 24 106 g0001gg0504 213 10 102 h000hg010g000 276 14 150 10k00401g0400 339 24 110 g10g0100150 214 10 112 g110000000M10 277 14 160 100040004040M 340 24 128 k400g0h00g0 215 10 118 h0g1001040400 278 14 164 10104001004gg 341 24 130 h400g1g1000 216 10 130 g110040000g44 279 14 166 104000g00g4k0 342 24 162 g4g0g0k4000 217 10 132 g400444410000 280 14 178 140gh00000044 343 24 164 g4100011g0g 218 10 144 k000hh0100000 281 14 194 1300400001100 344 24 166 g0000111g4g 219 10 146 g040400014013 282 14 198 1000gg00100k4 345 24 168 g10g4400440 220 10 160 kg000000404gg 283 14 214 110g4g000g100 346 24 170 gM0100000h0 221 10 162 g04100040k400 284 14 224 1s00101000000 347 24 234 g1100g01014 222 10 164 h00040040g40g 285 14 226 1004g400h0100 348 24 236 k000g504100 223 10 180 g4g004g001004 286 14 240 1g000104g0h00 349 28 32 cg005000g00 224 10 192 g00000k00k00k 287 14 242 1k00000410014 350 28 74 41000h0h010 225 10 194 g1g0000g100k0 288 14 244 10gg00g00g0g4 351 28 96 40h0044h000 226 10 196 g0410000h00gg 289 16 38 g00h10g01g00 352 28 102 4010l004g00 227 10 198 g11g0g00g0g00 290 16 42 g1011k010000 353 28 226 40440500404 228 10 210 g050410001004 291 16 70 g0500040hg00 354 28 236 40000gg0514 229 10 212 g10000l010010 292 16 74 g00414110010 355 30 36 31004g0g000 230 10 224 g00404h005000 293 16 78 g0040014g01g 356 30 38 1kg0g010400 231 10 226 g0gg045000010 294 16 98 g40400g04h00 357 30 40 10411010404 232 10 228 g4g0004000144 295 16 108 gh00kg040000 358 30 64 1101110g100 233 10 240 g4g00000hg004 296 16 110 h0400110g003 359 30 78 10g40050140 234 10 244 g0g0g0g40g400 297 16 140 g04000gg0504 360 30 110 1k000100k04 235 12 16 4g4000000401k 298 16 164 gg0g0100g00j 361 30 162 105000040M0 236 12 18 4510000440010 299 16 166 k40400100050 362 30 174 14510000044 237 12 32 400g1k000g100 300 16 196 g00014430000 363 30 228 1041010000c 238 12 50 40000l0g0400g 301 16 200 gg04001040h0 364 32 78 g10015h000 239 12 54 4000154000g40 302 16 202 gg400410000j 365 32 94 k0gg10g100 240 12 66 501000044001g 303 16 226 g0g05000g0h0 366 32 156 g500k4000g 241 12 68 5010004h0g000 304 16 228 k0010hg00004 367 32 196 g400150044 242 12 70 5400100l00000 305 16 232 gggg00000414 368 32 216 gk40g10100 243 12 84 4h0h040004000 306 16 234 g40gg0401004 369 34 192 404100g150 244 12 98 4040040105400 307 18 32 44g4k4000000 370 34 200 40g14g10g0 245 12 112 4400010040k03 308 18 40 404k44000040 371 36 64 140104gk00 246 12 118 400100400kg04 309 18 44 4040kgg40000 372 36 78 1013040400 247 12 128 40440g00000gk 310 18 68 4440g0ggg000 373 36 196 1101050500 248 12 130 40100004k0050 311 18 96 400010001h43 374 36 198 14kg040100 249 12 132 4011104000140 312 18 100 4g1000011g0g 375 38 68 k00M04g00 250 12 144 4040k00k01000 313 18 132 40g0044k1000 376 40 68 4g0g54g00 251 12 148 4144g10040000 314 18 160 41k0000g4400 377 42 76 3000M0003 252 12 162 40g0500g04g00 315 18 164 414000000g5g 378 42 78 111140g04 253 12 166 40000100014k3 316 18 196 401g400101g0 379 44 64 M10010g4 254 12 176 400g504400040 317 18 200 4000000415g3 380 44 78 kg0c4000 255 12 182 4050000440110 318 18 206 403g000000gg 381 58 128 c0k10g0 a.) 320 columns of type 03617 b.) 40 columns of type 0381431 c.) 20 columns of type 0361631 d.) a single column of type 04033 (vi) Since all G-orbits on 3-spaces have length 255, each of the three constituent designs of any [G]−invariant large set LS[3][2, 3, 28] will be comprised of 127 G-orbits of 3-spaces. In particular, properties (v) d.) and (vi) imply that a large set LS[3][2, 3, 28] whose automorphism group contains a Singer subgroup as a normal subgroup, can not have a group of automorphisms transitive on the 3 2-[28, 3, 21] designs. 171 M.R. Hurley et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 165–176 3.2. Constructing and presenting the designs and large sets As the number of columns of A2,3 is rather large, a backtrack, depth-first search or similar algorithm would be hopeless in finding solutions to equation (10). Instead, we use lattice basis reduction to seek solutions. This technique is nicely described in [15], pages 277-300. For each of the 9 large sets of 2-[28, 3, 21] designs we proceed using the following non-deterministic procedure, which, in general, is not guaranteed to terminate. Procedure 3.2. (i) Determine a 0-1 solution u1 to equation A2,3u1 = 21J, thus extracting a 2-[28, 3, 21] design D1 as the union of 127 G-orbits of 3-spaces. If this step succeeds, proceed to step (ii), otherwise stop. (ii) Remove from A2,3 the 127 columns corresponding to design D1 to obtain a 43×254 matrix C2,3, and find a 0-1 solution u2 to equation C2,3u2 = 21J, thus extracting a second design D2 consisting of 127 G-orbits among the orbits corresponding to the columns of C2,3. If this step succeeds, proceed to step (iii), otherwise stop. (iii) Remove the 127 columns constituting D2 from C2,3. The remaining 127 columns of C2,3 correspond to orbits whose union is a third design D3, and L = {D1,D2,D3} is a LS[3][2, 3, 28] large set. If steps (i) and (ii) are successful, so is (iii) and we have a successful termination with output large set L. Thus, the procedure of finding u1 and u2 becomes a matter of solving systems of integer equations through lattice basis reduction [15]. The following procedure describes briefly how the problems are set up so that lattice basis reduction can be used. Procedure 3.3. First we construct a matrix that will constitute a basis for an integral lattice Λ1 by adjoining the identity matrix of order 381 above KM matrix A2,3. To the right of the 424×381 matrix just formed we adjoin a 424×1 column vector which has zeros in the first 381 positions and −21’s in the remaining 43 positions. Let M1 denote the 424 × 382 matrix just formed. M1 = [ I 0 A2,3 −21J ] , M2 = [ I 0 C2,3 −21J ] If basis reduction produces a short enough basis M′1 for Λ1 which contains a short vector v1 with 0’s and 1’s (or 0’s and −1’s) in the first 381 positions and all 0’s below, then the projection u1 of v1 (or −v1) to the first 381 coordinates is likely to be a solution to A2,3u1 = 21J (see [15].) The weight of u1 will be 127, and the union of orbits of 3-spaces corresponding to the 1’s in u1 will form a 2-[28, 3, 21] design D1. If a solution u1 is found, then replacing A2,3 by C2,3 yields a 297×255 matrix M2 which spans a lattice Λ2, and by the same process as above, M2 can yield a solution to C2,3u2 = 21J, that is, a design D2 disjoint from D1. It is now clear that when the 127 columns corresponding to the orbits forming D2 are removed from C2,3, the remaining 127 orbits will form a 2-[28, 3, 21] design D3, and that {D1,D2,D3} will be a large set. However, the above procedure is not guaranteed to find a solution at first try, so if the basis reduction algorithm was unable to find a column in reduced basis M′1 that met the conditions in Procedure 3.2.2 , we would repeat the process, twiking the order of the columns of M1, and the same later for M2. The above procedure was repeated a number of times and we successfully constructed 9 distinct large sets {L1, . . . ,L9} which we exhibit below. 3.3. Reconstruction of the large sets We briefly describe the display, to enable the reader to reconstruct the large sets and related designs. The first column is the index of the G-orbits on 3-spaces. There are 9 additional columns, each corresponding to one of the large sets. Each column has 127 1’s, 127 2’s and 127 3’s in it, which select the orbits contained in D1, D2 and D3 respectively, for each large set. Since the orbits can be computed from the representative bases in the presentation of A2,3, the reader can readily reconstruct the 9 large sets and the designs involved. Direct computation shows that indeed the 9 large sets are different from each other and different from the large set L0 constructed in [4]. However, a peculiar visual symmetry is observed in the structure of our 9 large sets 172 M.R. Hurley et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 165–176 Figure 1. The 10 large sets {L0, . . . ,L9} which is perhaps only related to our search method. The 9 large sets can be divided into 3 clusters of 3 large sets per cluster. The large sets of each cluster share a common 2-[28, 3, 21] design forming a triad of large sets, with a central design and three peripheral pairs of designs as illustrated in Figure 1. The three centers are different from each other, and the 18 peripheral designs are also different from each other and the 3 centers. Actually, there are no elements of Γ permuting non-trivially the 3 clusters of large sets, nor elements of order 3 permuting the 3 designs of any one of the large sets. Checking the list of maximal subgroups of Γ = GL8(2) shows that N = NΓ(G) is not maximal in Γ. Let Φ8 = 〈ζ〉≤ N , ζ : α → α2 be the Frobenius subgroup normalizing G. We have checked that Φ8 does not fix any of the 9 large sets, and does not move any one of the 9 large sets to any other. Let L0 be the LS[3][2, 3, 28] discovered by the authors of [4], and let S = {Li : 0 ≤ i ≤ 9}. We already know that G ≤ Aut(Li) for each i ∈ {0, . . . , 9}. It is conceivable that the automorphism groups of the 10 large sets in S are not all identical, but we think this is very unlikely and we conjecture that in fact Aut(Li) are all identical, and equal to the Singer subgroup G. ζ =   1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1   We presently rephrase, in the context of our notation, a very useful theorem of A. Betten, R. Laue, and A. Wassermann in [1]. This will immediately yield a corollary concerning the question of isomorphism between the 10 large sets in S = {L0,L1, . . . ,L9}. Theorem 3.4. (Theorem 3.1 in [1]) Let G be a finite group acting on a set X. Suppose that x1,x2 ∈ X and g ∈G such that xg1 = x2. Moreover, suppose that a Sylow subgroup P of G is contained in the stabilizers Gx1 and Gx2. Then, x n 1 = x2 for some n ∈ NG(P). 173 M.R. Hurley et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 165–176 1 222332233 65 311113121 129 122221313 193 233223323 257 111111111 321 123111112 2 111111111 66 211232221 130 333112123 194 233333323 258 132321213 322 311333321 3 211232221 67 233333333 131 223333232 195 122111113 259 111221311 323 211222321 4 133111112 68 111111111 132 211323231 196 223332232 260 132111112 324 223112133 5 132111112 69 232112123 133 132111112 197 133321213 261 233112122 325 123221213 6 311323331 70 322332323 134 323113123 198 311222331 262 232112133 326 233112133 7 333233333 71 323113133 135 323223233 199 311112131 263 111321311 327 233232223 8 332112122 72 322323333 136 123111113 200 322112133 264 211232231 328 211333321 9 133111112 73 111221311 137 311222231 201 322322323 265 311112131 329 232332322 10 211222331 74 122111113 138 133111112 202 211223321 266 211323221 330 223333232 11 311333221 75 311223321 139 211322221 203 332233323 267 223113132 331 111331311 12 133321313 76 233113132 140 111111111 204 123111112 268 223112123 332 211333221 13 311223331 77 322233223 141 332322232 205 322323333 269 211113131 333 233223232 14 122331213 78 223333332 142 232113132 206 133111112 270 322323232 334 122221212 15 211223221 79 232322322 143 332113123 207 333113123 271 322233233 335 111111111 16 333333223 80 111331211 144 111331211 208 211322331 272 111331211 336 323333323 17 222222332 81 111331311 145 323232223 209 223322332 273 123221213 337 111111111 18 232322323 82 211112131 146 323112123 210 332322233 274 323332222 338 232233233 19 111111111 83 222112122 147 111231311 211 211113131 275 122331312 339 211113121 20 223332232 84 222333232 148 123231313 212 123221213 276 222222232 340 223333322 21 233223332 85 211232321 149 133321212 213 111111111 277 232232323 341 133111113 22 222332323 86 332113133 150 132231212 214 233332233 278 223333332 342 133221212 23 322232223 87 111111111 151 323233223 215 311112121 279 332113132 343 233113132 24 223233322 88 133321313 152 322322323 216 332232222 280 233323322 344 311232221 25 322333322 89 111111111 153 211223331 217 132231313 281 332333223 345 233333232 26 211333331 90 332323232 154 223113132 218 332333223 282 111231311 346 223333332 27 132231212 91 332333332 155 223222222 219 132111112 283 332113122 347 332233222 28 323113132 92 233332222 156 333113123 220 223323232 284 223112123 348 111221311 29 111111111 93 123111113 157 111221311 221 211232331 285 211222221 349 222232333 30 311323321 94 122331312 158 322333233 222 323332322 286 333112123 350 323323323 31 222112133 95 222222232 159 223332322 223 222222222 287 111321211 351 323232232 32 132111113 96 132221213 160 133231212 224 332113123 288 223332233 352 111111111 33 311113121 97 332222323 161 222332223 225 311112121 289 132111112 353 132331212 34 233113133 98 322232233 162 311333331 226 111111111 290 111221211 354 311112131 35 322223223 99 133111112 163 211232331 227 211332321 291 132221213 355 222233223 36 133221313 100 322112133 164 332232233 228 111111111 292 223113133 356 322223333 37 133111112 101 233112122 165 133111112 229 322112132 293 311112121 357 122111113 38 232113132 102 211113131 166 122111112 230 332333333 294 211113121 358 222112132 39 222233222 103 133221312 167 333333332 231 122221212 295 132111112 359 311332231 40 333112132 104 211322221 168 332112132 232 111321211 296 111111111 360 311323321 41 111221211 105 323223233 169 223113122 233 133231212 297 322322222 361 322222223 42 111231211 106 111321211 170 232323223 234 311112121 298 322323333 362 223112122 43 322233232 107 223112132 171 123111112 235 123331212 299 333232233 363 332223333 44 111111111 108 111221211 172 323223233 236 132231312 300 332332333 364 111111111 45 233322233 109 311323331 173 232233333 237 111321211 301 122221313 365 311112131 46 133321312 110 133331312 174 111231211 238 333113122 302 211332221 366 311113131 47 111111111 111 133231212 175 123111113 239 323112122 303 222222232 367 122321213 48 111221311 112 333233233 176 111221311 240 222223332 304 311332321 368 122111112 49 211333231 113 223113133 177 233332322 241 333233333 305 211232321 369 311233321 50 311112121 114 323322223 178 222222333 242 132231313 306 333323322 370 311222221 51 123111113 115 111111111 179 211322221 243 123221213 307 311223321 371 111321311 52 323322222 116 232233332 180 133111112 244 322113123 308 133111113 372 333323232 53 323332322 117 332323332 181 211233331 245 323113122 309 111111111 373 222223322 54 333112133 118 211232221 182 211322221 246 233112122 310 223223332 374 311332331 55 222222322 119 311112121 183 322223222 247 232332232 311 322323232 375 332333332 56 232322233 120 211233321 184 211323231 248 123111113 312 223112123 376 233222232 57 323223223 121 132231313 185 311112121 249 122221312 313 232332332 377 322333333 58 311113121 122 222112122 186 322322223 250 211222231 314 111111111 378 211223331 59 122321312 123 232322332 187 132231213 251 111221311 315 311112121 379 232233332 60 333222323 124 133321213 188 111231211 252 332322323 316 222332223 380 322333323 61 111231311 125 111221311 189 322322223 253 211233331 317 232232323 381 333322322 62 333223322 126 222112132 190 111321211 254 223113123 318 332333333 63 311332231 127 133321312 191 133231312 255 133231213 319 111111111 64 133321313 128 123231213 192 232323333 256 311233231 320 111111111 174 M.R. Hurley et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 165–176 Corollary 3.5. The ten Large Sets in S = {L0,L1, . . . ,L9} are pairwise non-isomorphic. Proof. Let L be the collection all large sets of type LS[3][2, 3, 28], and G = 〈α〉 be the Singer subgroup as defined earlier. Then, Γ acts on L, and for any λ ∈ L the stabilizer Γλ is the full automorphism group of λ. In particular, for each λ ∈ S we have that P < G ≤ Γλ where P is the Sylow-17 subgroup of G. Let β,γ ∈ S, β 6= γ, and suppose there is g ∈ Γ such that βg = γ. Then, by Theorem 3.4, there would exist an element n ∈ NΓ(P) = NΓ(G) such that βn = γ. But we know, by direct checking, that no element of the Frobenius group Φ8, and therefore no element of NΓ(G) = G · Φ8 sends β to γ, a contradiction. 3.4. Conclusions Until 2014, the only large sets of geometric t-[qn,k,λ] designs known were for t = 1. In finite geometry, LS[N]-[t,k,qn] large sets with t = 1, are known as (k-1)-parallelisms of (k-1)-spreads in PG(n− 1,q). The first large set L0 of geometric 2-designs, a LS[3]-[2, 3, 28], was constructed by the authors of [4]. In this paper we construct an additional nine pairwise different large sets L1, . . . ,L9 which are also different from L0. All these large sets are [G]-invariant, under the same Singer subgroup G of order 255. In fact, the large sets {L0, . . . ,L9} are pairwise non-isomorphic. 3.5. Possible future work The necessary conditions for the existence of a LS[3]-[3, 4, 29] are satisfied and we are close to settling the question of existence of a LS[3]-[3, 4, 29]. Acknowledgment: The authors would like to express their thanks to Dr. Igor Kliakhandler whose generous support made possible a most significant conference on Algebraic Combinatorics and Applications at Michigan Technical University, in August, 2015. The authors also wish to thank Prof. Vladimir Tonchev for putting together a superbly organized conference. References [1] A. Betten, R. Laue, A. Wassermann, Simple 7−designs with small parameters, J. Combin. Des. 7(2) (1999) 79–94. [2] M. Braun, T. Etzion, P. J. R. Östergard, A. Vardy, A. Wassermann, Existence of q−analogs of Steiner Systems, submitted, 2013. [3] M. Braun, A. Kerber, R. Laue, Systematic construction of q−analogs of t− (v,k,λ)−designs, Des. Codes Cryptogr. 34(1) (2005) 55–70. [4] M. Braun, A. Kohnert, P. R. J. Östergard, A. Wassermann, Large sets of t−designs over finite fields, J. Combin. Theory Ser. A 124 (2014) 195–202. [5] P. J. Cameron, Generalisation of Fisher’s inequality to fields with more than one element, Lond. Math. Soc. Lecture Note Ser. 13 (1974) 9–13. [6] P. J. Cameron, Locally symmetric designs, Geometriae Dedicata 3(1) (1974) 65–76. [7] P. Delsarte, Association schemes and t−designs in regular semilattices, J. Combin. Theory Ser. A 20(2) (1976) 230–243. [8] A. Fazeli, S. Lovett, A. Vardy, Nontrivial t−designs over finite fields exist for all t, J. Combin. Theory Ser. A 127 (2014) 149–160. [9] T. Etzion, A. Vardy, Error-correcting codes in projective space, IEEE Trans. Inf. Theory 57(2) (2011) 1165–1173. [10] T. Itoh, A new family of 2-designs over GF(q) admitting SLm(q`), Geometriae Dedicata 69(3) (1998) 261–286. 175 http://dx.doi.org/10.1002/(SICI)1520-6610(1999)7:2<79::AID-JCD1>3.0.CO;2-D http://dx.doi.org/10.1002/(SICI)1520-6610(1999)7:2<79::AID-JCD1>3.0.CO;2-D http://dx.doi.org/10.1007/s10623-003-4194-z http://dx.doi.org/10.1007/s10623-003-4194-z http://dx.doi.org/10.1016/j.jcta.2014.01.008 http://dx.doi.org/10.1016/j.jcta.2014.01.008 http://dx.doi.org/10.1017/CBO9780511662072.003 http://dx.doi.org/10.1017/CBO9780511662072.003 http://dx.doi.org/10.1007/BF00181362 http://dx.doi.org/10.1016/0097-3165(76)90017-0 http://dx.doi.org/10.1016/0097-3165(76)90017-0 http://dx.doi.org/10.1016/j.jcta.2014.06.001 http://dx.doi.org/10.1016/j.jcta.2014.06.001 http://dx.doi.org/10.1109/TIT.2010.2095232 http://dx.doi.org/10.1109/TIT.2010.2095232 http://dx.doi.org/10.1023/A:1005057610394 http://dx.doi.org/10.1023/A:1005057610394 M.R. Hurley et al. / J. Algebra Comb. Discrete Appl. 3(3) (2016) 165–176 [11] R. Koetter, F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inf. Theory 54(8) (2008) 3579–3591. [12] E. S. Kramer, D. M. Mesner, t−designs on hypergraphs, Discrete Math. 15(3) (1976) 263–296. [13] E. S. Kramer, D. W. Leavitt, S. S. Magliveras, Construction procedures for t−designs and the existence of new simple 6−designs, Ann. Discrete Math. 26 (1985) 247–274. [14] G. Kuperberg, S. Lovett, R. Peled, Probabilistic existence of regular combinatorial structures, arXiv:1302.4295v2. [15] D. L. Kreher, D. R. Stinson, Combinatorial Algorithms : generation, enumeration and search, CRC Press, vol. 7, 1998. [16] R. Laue, S. S. Magliveras, A. Wassermann, New large sets of t−sesigns, J. Combin. Des. 9(1) (2001) 40–59. [17] M. Miyakawa, A. Munemasa, S. Yoshiara, On a class of small 2−designs over GF(q), J. Combin. Des. 3(1) (1995) 61–77. [18] D. K. Raychaudhuri, E. J. Schram, A large set of designs on vector spaces, J. Number Theory 47(3) (1994) 247–272. [19] H. Suzuki, 2−Designs over GF(q), Graphs Combin. 8(4) (1992) 381–389. [20] S. Thomas, Designs over finite fields, Geom. Dedicata 24(2) (1987) 237–242. 176 http://dx.doi.org/10.1109/TIT.2008.926449 http://dx.doi.org/10.1109/TIT.2008.926449 http://dx.doi.org/10.1016/0012-365X(76)90030-3 http://dx.doi.org/10.1016/S0304-0208(08)72985-2 http://dx.doi.org/10.1016/S0304-0208(08)72985-2 http://arxiv.org/abs/1302.4295v2 http://arxiv.org/abs/1302.4295v2 http://dx.doi.org/10.1002/1520-6610(2001)9:1<40::AID-JCD4>3.0.CO;2-0 http://dx.doi.org/10.1002/1520-6610(2001)9:1<40::AID-JCD4>3.0.CO;2-0 http://dx.doi.org/10.1002/jcd.3180030108 http://dx.doi.org/10.1002/jcd.3180030108 http://dx.doi.org/10.1006/jnth.1994.1036 http://dx.doi.org/10.1006/jnth.1994.1036 http://dx.doi.org/10.1007/BF02351594 http://dx.doi.org/10.1007/BF00150939 Introduction Preliminaries Main result References