The Simple 7-(33,8,10)-Designs with Automorphism Group PΓL(2,32)

Alfred Wassermann

Abstract

Lattice basis reduction in combination with an efficient backtracking algorithm is used to find all (4 996 426) simple 7- (33,8,10) designs with automorphism group PΓL(2,32). The paper contains a short description of the algorithm.

1 Introduction

Let X be a v-set (i.e. a set with v elements) whose elements are called points. A t-(v, k, λ) design is a collection of k-subsets (called blocks) of X with the property that any t-subset of X is contained in exactly λ blocks. A t-(v, k, λ) design is called simple if no blocks are repeated, and trivial if every k-subset of X is a block and occurs the same number of times in the design.

A straightforward approach to the construction of t-(v, k, λ) designs is to consider the matrix

M_{t,k}^{v} := (m_{i,j}), i = 1, …, \binom{v}{t}, j = 1, …, \binom{v}{k} :

The rows of M_{t,k}^{v} are indexed by the t-subsets of X and the columns by the k-subsets of X. We set m_{i,j} := 1 if the i-th t-subset is contained in the j-th k-subset, otherwise m_{i,j} := 0. Simple t-(v, k, λ) designs therefore correspond to \{0, 1\}-solutions x of the system of \binom{v}{t} linear equations:

M_{t,k}^{v} · x = λ(1, 1, …, 1)^{⊤}.

Unfortunately, for most designs with interesting parameters v, t, k the size of the matrix M_{t,k}^{v} is prohibitively large. For example in the case of v = 33, t = 7 and k = 8 the matrix M_{7,8}^{33} has 4 272 048 rows and 13 884 156 columns.

But by assuming a group action on the set X the size of M_{t,k}^{v} can be dramatically reduced. A group G acting on X induces also an action on the set of t-subsets and the set of k-subsets of X. With A_{t,k} = (a_{i,j}) we denote the matrix where a_{ij} counts the number of those elements in the j-th orbit of G on the k-subsets of X which contain a representative of the i-th orbit of t-subsets of X. This matrix was introduced by Kramer and Mesner [7]. They observed:

Theorem 1 (see [7]) A simple t-(v, k, λ) design with G ≤ Sym(X) as an automorphism group exists if and only if there is a {0, 1}-solution x to the matrix equation

A_{t,k} · x = λ(1, 1, …, 1)^{⊤}.  (1)

Taking the group PΓL(2, 2^{5}) the matrix A_{7,8} in the above example has 32 rows and 97 columns. Nevertheless it is still a respectable task to find solutions of (1).

Finding solutions for this problem requires algorithms which do searching in high dimensional spaces. These algorithms can roughly be divided into two classes, depending on whether they search in a systematic manner for all possible solutions or if they just try to find one solution.

For finding just one solution the algorithms are mostly randomized, for example simulated annealing, combinatorial optimization, local search [13] and lattice basis reduction [8, 15, 1]. See [13] for a survey. Recently also algorithms which use Gröbner bases have been proposed [21, 22].

In [8] the authors used the original lattice basis reduction algorithm (LLL) as described in [11] and a lattice like the one proposed in [9]. Meanwhile lattice basis reduction algorithms have been greatly improved. New algorithms were invented by Schnorr, [17, 18, 19]. Also new lattices have been proposed, see [2, 4].

On the contrary, in order to find \underline{all} \{0, 1\}-solutions of (1) until now only exhaustive search techniques based on backtracking have been used, see for example [13, 14]. Schmalz [16] used a graph theoretical approach, he enumerates all solutions implicitely via graphs.

The new approach – using lattice basis reduction [11] – is to construct a basis of the kernel of the equation

( \begin{matrix}& 1 \\ A_{t,k} & ⋮ \\ & 1 \end{matrix} ) ( \begin{matrix}x \\ y \end{matrix} ) = ( 0 ⋮ 0 ) , x_{i} ∈ Z, y ∈ Z  (2)

which consists of short integer vectors. But the shortest integer vectors (in the euclidean norm) in the kernel of (2) need not correspond to solutions of our {0, 1}-problem (1). Kaib and Ritter proposed in [5] an algorithm which enumerates all solutions with y = ±λ as linear combination of this short integer basis vectors.

The first step of this algorithm – finding a basis of the kernel – can be done in polynomial time in the number of columns of the Kramer Mesner matrix A_{tk} with the help of lattice basis reduction [11]. But the explicit enumeration in the second step of [5] is still an exponential algorithm whilst in most cases much faster than the brute force enumeration as it was used in the above mentioned algorithms. Thus in some sense this algorithm combines the two classes of algorithms to solve (1).

This is the first announcement of the 4 996 246 7-(33,8,10)-designs with automorphism group PΓL(2,32) together with a short overview of the algorithm. A more detailed description will be submitted to the Journal of Combinatorial Designs.

2 From linear equations to lattices

As in [1] we transform the Kramer Mesner matrix A_{tk} with l rows and s columns into the matrix

( \begin{matrix}& & & c_{0}1 & 0 \\ & c_{0}A_{tk} & & ⋮ & ⋮ \\ & & & c_{0}1 & 0 \\ c_{1}2 & 0 & & 0 & c_{1}1 \\ & ... & & ⋮ & ⋮ \\ & 0 & c_{1}2 & 0 & c_{1}1 \\ 0 & … & 0 & 1 & 0 \\ 0 & … & 0 & 0 & c_{1}1 \end{matrix} )  (3)

containing s+2 column vectors with l+s+2 rows. The set of all integer linear combinations of these vectors is called a lattice. A minimal set of vectors which generates the lattice is called a basis of the lattice. Important in our context are bases which contain short vectors. These are called reduced bases if they fulfill certain criteria of shortness, see [11].

The lattice L spanned by the columns of the matrix (3) has the column vectors of the matrix itself as a basis. This basis is reduced with the algorithm proposed in [20] to a new basis.

Definition 1 Let L ⊂ R^{n} be a lattice. For 1 ≤ p < ∞ the norm defined by the mapping

∥.∥_{p} : R^{n} → R, x ↦ ∥x∥_{p} := (∑_{i=1}^{n} |x_{i}|^{p})^{1/p}

is called p-norm. The norm defined by the mapping

∥.∥_{∞} : R^{n} → R, x ↦ ∥x∥_{∞} := max{|x_{i}| | 1 ≤ i ≤ n}

is called ∞-norm. For 1 ≤ p ≤ ∞ we call a vector ∈ L p-shortest if it is a shortest vector in L in p-norm.

If we set in (3) c_{1} = λ and c_{0} > λ, the ∞-shortest vectors of the lattice are solutions of the equation (1). ∞-shortest vectors in L consist of zeros in the first l rows and have only the entries −1 · c_{1} or 1 · c_{1} in the rows l + 1, …, l + s. Further, in row l + s + 1 and l + s + 2 they contain ±λ and ±1, respectively.

Until now only reduction techniques for the norm p = 2 are working efficiently. To find a ∞-shortest vector we have to employ backtracking methods. Since the 2-norm and the ∞-norm are equivalent (for all x ∈ R^{n}: ∥x∥_{∞} ≤ ∥x∥_{2} ≤ \sqrt{n}∥x∥_{∞}) it’s reasonable to use 2-short vectors to find the ∞-shortest vectors.

Let ⟨., .⟩ denote the ordinary inner product in R^{n}, n ∈ N. For a sequence of linear independent vectors b_{1}, …, b_{m} ∈ R^{n} we let b_{1}^{∗}, …, b_{m}^{∗} be the Gram-Schmidt orthogonalized sequence. We thus have

b_{i}^{∗} := b_{i} − ∑_{j=1}^{i−1} μ_{i,j}b_{j}^{∗} for i = 1, …, m, where μ_{i,j} = \frac{⟨b_{i}, b_{j}^{∗}⟩}{⟨b_{j}^{∗}, b_{j}^{∗}⟩} . (4)

Definition 2 For an (ordered) basis b_{1}, b_{2}, …, b_{m} of a lattice L ⊂ R^{n} and 1 ≤ i ≤ m, π_{i}(v) is the orthogonal projection of v ∈ R^{n} into ⟨b_{1}, b_{2}, …, b_{i}⟩^{⊥}. L_{i} := π_{i}(L) is the orthogonal projection of the lattice L into ⟨b_{1}, b_{2}, …, b_{i}⟩^{⊥}.

Since

v = ∑_{j=1}^{m}⟨v, b_{j}^{∗}⟩b_{j}^{∗}

we see that

π_{i}(v) = ∑_{j=i}^{m}⟨v, b_{j}^{∗}⟩b_{j}^{∗}.  (5)

3 Explicit enumeration

For every basis vector b_{t} and j ≤ t we have:

π_{j}(b_{t}) = ∑_{i=j}^{t} μ_{t,i}b_{i}^{∗}.

With c_{s} := ∥b_{s}^{∗}∥_{2}^{2} for 1 ≤ s ≤ k it follows

π_{j}(∑_{t=j}^{m} u_{t}b_{t}) = (∑_{i=j}^{m} u_{i}μ_{i,j})b_{j}^{∗} + π_{j+1}( ∑_{t=j+1}^{m} u_{t}b_{t}),  (6)

and

∥π_{j}(∑_{t=j}^{m} u_{t}b_{t})∥_{2}^{2} = (∑_{i=j}^{m} u_{i}μ_{i,j})^{2}c_{j} + ∥π_{j+1}( ∑_{t=j+1}^{m} u_{t}b_{t})∥_{2}^{2}.

Definition 3 For u_{j}, u_{j+1}, …, u_{m} ∈ Z we write w_{j} := π_{j}(∑_{t=j}^{m} u_{t}b_{t}).

The backtracking algorithm tries all possible integer values for u_{m}, u_{m−1}, …, u_{1}. Starting from t = m it computes w_{t} for m ≥ t ≥ 1 and finally w_{1} = ∑_{i=1}^{m} u_{i}b_{i}.

Remark 1 If u_{j+1}, u_{j+2}, …, u_{m} ∈ Z are fixed and u_{j} ∈ Z has to be choosen such that ∥w_{j}∥_{2}^{2} is minimal, then u_{j} has to be set to the nearest integer to − ∑_{i=j+1}^{m} u_{i}μ_{i,j}, since

∥w_{j}∥_{2}^{2} = ∥π_{j}(∑_{t=j}^{m} u_{t}b_{t})∥_{2}^{2} = (u_{j} + ∑_{i=j+1}^{m} u_{i}μ_{i,j})^{2}c_{j} + ∥π_{j+1}( ∑_{t=j+1}^{m} u_{t}b_{t})∥_{2}^{2}.

The solutions of our system of linear equations (2) are the ∞- shortest vectors in the lattice generated by the vectors in (3), but we describe the search for the p-shortest vector in L for arbitrary 1 ≤ p ≤ ∞.

Let F be an upper bound of the p-shortest vector of L. Since all p-norms in R^{n} are equivalent, there exist constants r_{p}, R_{p} such that r_{p}∥x∥_{p} ≤ ∥x∥_{2} ≤ R_{p}∥x∥_{p} for all x ∈ R^{n}. Therefore a p-shortest vector v has 2-norm ∥v∥_{2} ≤ R_{p}F and in order to find p-shortest vectors we enumerate all vectors with 2-norm not greater than R_{p}F.

Moreover, Kaib, Ritter [5] use Hölder’s inequality to combine the search for p-shortest vectors with enumeration in 2-norm:

Theorem 2 If for fixed u_{j}, u_{j+1}, …, u_{m} ∈ Z there exist

u_{1}, u_{2}, …, u_{j−1} ∈ Z

with ∥ ∑_{i=1}^{m} w_{i}∥_{p} ≤ F, then for all y_{j}, y_{j+1}, …, y_{m} ∈ R:

|∑_{i=j}^{m} y_{i}∥w_{i}∥_{2}^{2}| ≤ F · ∥ ∑_{i=j}^{m} y_{i}w_{i}∥_{q}  (7)

with 1 ≤ q ≤ ∞ such that 1/p + 1/q = 1.

It remains to select y_{j}, …, y_{m} appropiately to enable an early recognition of enumeration branches which cannot yield solutions. Kaib, Ritter [5] proposed two selections:

1. (y_{j}, y_{j+1}, …, y_{m}) = (1, 0, …, 0): Test if ∥w_{j}∥_{2}^{2} ≤ F ∥w_{j}∥_{q}.

2. (y_{j}, y_{j+1}, …, y_{m}) = (η, 1 − η, 0, …, 0) with η ∈ ]0, 1[ .

Let’s say w_{j} = xb_{j}^{∗} +w_{j+1} for an x ∈ R. Then for every successive w′_{j} in the same direction, that means every w′_{j} = (x + r)b_{j}^{∗} + w_{j+1} with r ∈ Z and having the same sign as x, we have for η := \frac{x}{x+r}:

w_{j} = ηw′_{j} + (1 − η)w_{j+1} and 0 < η < 1.  (8)

If w′_{j} can lead to a solution, then from (7) it follows for every η ∈ ]0, 1[:

η∥w′_{j}∥_{2}^{2} + (1 − η)∥w_{j+1}∥_{2}^{2} ≤ F ∥ηw′_{j} + (1 − η)w_{j+1}∥_{q}. (9)

With (8) the inequality reduces to

∥w_{j}∥_{2}^{2} ≤ F ∥w_{j}∥_{q}.

Here 0 ≤ η ≤ 1 is needed.

Therefore we can cut the enumeration in the direction of x if ∥w_{j}∥_{2}^{2} > F ∥w_{j}∥_{q}.

This results in the following algorithm:

Algorithm 1 1. Compute a LLL-reduced integer basis of the kernel of the linear system (1): Choose c_{0} large enough such that the number of remaining columns will be equal to s − l + 2 and LLLreduce the matrix (3).

2. Remove the columns with nonzero entries in the first l rows. From the remaining columns remove the first l rows (the zero entries).

3. Compute for the remaining columns b_{1}, …, b_{m} the Gram-Schmidt vectors b_{1}^{∗}, b_{2}^{∗}, …, b_{m}^{∗} with their Gram-Schmidt coefficients μ_{i,j}, see (4).

4. Set j := 1; F := upper limit to the p-shortest vector in L. Set F̄ := R_{p}^{2}F^{2}.

5. Do the search loop:

while j ≤ m Compute w_{j} from w_{j+1}. if ∥w_{j}∥_{2}^{2} > F̄ then

j := j + 1 NEXT(u_{j})

else

if j > 1 then

if PRUNE(u_{j}) then

if onedirection then j := j + 1

NEXT(u_{j})

else onedirection := true NEXT(u_{j})

end if

else j := j − 1 y := ∑_{i=j+1}^{m} u_{i}μ_{i,j} u_{j} := round(−y) onedirection := false

end if else /* (j = 1) */

PRINT u_{1}, …, u_{m} NEXT(u_{j})

end if end if

end while

The procedure NEXT determines the next value of the variable u_{j}. Initially u_{j} is set to the nearest value of −y_{j} := − ∑_{i=j+1}^{m} u_{i}μ_{i,j}, say u_{j}^{1}. The next value (u_{j}^{2}) of u_{j} is the second nearest integer to −y_{j} then follows u_{j}^{3} and so forth. Therefore the values of u_{j} alternate around −y_{j}. If PRUNE is true for one value of u_{j} we do one more jump around −y_{j}, then the enumeration is only proceeded in this remaining direction until it is pruned again.

For arbitrary p with and q such that 1/p + 1/q = 1 the procedure PRUNE looks like this:

Algorithm 2 Choose y_{j}, …, y_{m}

PRUNE(u_{j})

if |∑_{i=j}^{m} y_{i}∥w_{i}∥_{2}^{2}| ≤ F · ∥ ∑_{i=j}^{m} y_{i}w_{i}∥_{q}

Return false else

Return true end if

4 Results

We used the algorithm to find all 7-(33,8,10) designs with automorphism group PΓL_{2}(32). The Kramer Mesner matrix was already published in [12]. The algorithm described in [1] produced the following 32 × 97 matrix which is a permutation of the rows and columns of the matrix in [12]:

2222222222222000000000000000000000000000000000000000000000000000000000000000000000000000000000000 2101110000000211112111111111111000000000000000000000000000000000000000000000000000000000000000000 1110000001000100200000000001000111112112111111100000000000000000000000000000000000000000000000000 0011000000000021001000000000000100011000000100012131111111110000000000000000000000000000000000000 0001200000000000000001000001001110000000010010010011000100001121111111100000000000000000000000000 0000110000000001000000100020000001001000001100111000000101001000000110021111110000000000000000000 0000013000110100100000101001001000100020001000100101010010000001000100010010001000000000000000000 0000004200000000020000200220000000020000002000000000000200000200000000000002000200000000000000000 0000000220000000002000002000002000002000020000000020000000000200002000022020000000000000000000000 0001000121000001100100000101000000001000100010100100001000000010011100000101001011100000000000000 0000002001200010011011010000110000001101000110010000010000000000100000000100001010011000000000000 0000000200020200000002200020000200000022000000020000200000000000000000000020000000020000000000000 0000000001012000000000101000022000000000000000111000000110010110000100100100010200101000000000000 0200000000002210020000101000001111000000000100000000000000001000110010100000001000010111000000000 0010100000001001001200100000010001000002000000001001011011000100000000000001010000000102110000000 0000110011000010100001020100000000000000101000000101000000010100100000000010000000010211001110000 0011020000000010010000000100100000010001000000000001010000100000100011000010001010212000001001000 0000000220000000000240002000000000000000000000000000000000000000200220000000220200000000002000000 0000010010011000010110010011001110000100000001000001010001000000001000000101100010000000100011000 0200000200000200000200000200020002000000002020000000000000200000000000000200020000000000000020000 0001000001010011000000000001000011000100010000100001000001000011000000100000000020010031010100100 0010100000011000102001001000000001000110000101100100110000000000200000100000000000100000100000300 0200000000000001000001000000000010220100000110000000000010010010011000000100011010021000010000100 0011000000000000100001000000010100011010000001000100000010100000020100000101000000101002000100120 0000000200000000000020020000000000000020000000200000000200000000020020220000000000002000200002000 0010000000000000000110000101000000000000100000010010100002001000001101110011000000001110000002110 0000000000010000010000011010000000000010001020000000200110000200000010010000111000100110001001010 0000000000000000000010010100010110000100000100001010101100000010001010002010011000000000003001100 0000000010000001000000000010100011010001001000011100100010000001001000110001000000000111001011001 0000000005000000000000000000000000000500000000000500050000000000000000000000000000000000050000001 0000000000000000000000000000000000000000000000005000000005000000050005000000000050000000000000001 0000000000000000000000000000000000000000000000000050000000000050000000000000000000500500000500001

The method of [1] in it’s first version found only 1 solution for λ = 10. It was Brendan McKay [14] who observed with his general integer backtracking algorithm that there are more than one solutions. In fact he estimated the number of solutions to be between 5 and 7 million. He also estimated that the backtracking algorithm as described in [14] would have taken 100 years to enumerate all these solutions with the computers we had at hand at that time.

For each of the two matrices the above Algorithm 1 found that there are 4 996 426 solutions for λ = 10 and that there are no solutions for other values of λ beside the complementary designs with λ = 16. All these solutions give nonisomorphic designs: By [10] PΓL(2, 2^{5}) is a maximal subgroup of S_{33}. Therefore the full automorphism group could be either PΓL(2, 2^{5}) or S_{33}. The latter case is impossible, since it would require all 8-subsets to be included into the design because of the transitivity of S_{33} on X.

The computing time was about one week on a DEC ALPHA 3000. The newest results of the Bayreuth group on t-designs can be found at

http://www.mathe2.uni-bayreuth.de/betten/DESIGN/d1.html

and

http://www.mathe2.uni-bayreuth.de/people/laue.html.

References

[1] A. Betten, A. Kerber, A. Kohnert, R. Laue, A. Wassermann: The Discovery of Simple 7-Designs with Automorphism Group P ΓL(2, 32). AAECC 11 in Lecture Notes in Computer Science 547 (1995), 281–293.

[2] M. J. Coster, B. A. LaMacchia, A. M. Odlyzko, C. P. Schnorr: An improved low-density subset sum algorithm. Proceedings EUROCRYPT ’91, Brighton, May 1991 in Springer Lecture Notes in Computer Science 547 (1991), 54–67.

[3] H. H. Hörner: Verbesserte Gitterbasenreduktion; getestet am Chor-Rivest Kryptosystem und an allgemeinen Rucksack-Problemen. Diplomarbeit, Universität Frankfurt (August 1994).

[4] A. Joux, J. Stern: Improving the Critical Density of the Lagarias-Odlyzko Attack Against Subset Sum Problems. Proceedings of Fundamentals of Computation Theory 91 in Lecture Notes in Computer Science 529 (1991), 258–264.

[5] M. Kaib, H. Ritter: Block Reduction for Arbitrary Norms. Preprint 1995.

[6] R. Kannan: Improved algorithms for integer programming and related lattice problems. 15th Ann. ACM Symb. on Theory of Computing (1983), 193–206.

[7] E. S. Kramer, D. M. Mesner: t-designs on hypergraphs. Discrete Math. 15 (1976), 263–296.

[8] D. L. Kreher, S. P. Radziszowski: Finding Simple t-Designs by Using Basis Reduction. Congressus Numerantium 55 (1986), 235–244.

[9] J. C. Lagarias, A. M. Odlyzko: Solving low-density subset sum problems. J. Assoc. Comp. Mach. 32 (1985), 229–246.

[10] M. W. Liebeck, C. E. Praeger, J. Saxl: The maximal factorizations of the finite simple groups and their automorphism groups, Memoirs of the Amer. Math. Soc. 432 (1990), Chapter 9.

[11] A. K. Lenstra, H. W. Lenstra Jr., L. Lovász: Factoring Polynomials with Rational Coefficients, Math. Ann. 261 (1982), 515–534.

[12] S. S. Magliveras, D. W. Leavitt: Simple 6-(33,8,36) Designs from P ΓL_{2}(32). Computational Group Theory M. D. Atkinson ed., Academic Press (1984) 337–352.

[13] R. Mathon: Computational Methods in Design Theory. London Math. Soc. Lect. Notes 166 (1991), 101–117.

[14] B. McKay: Personal communication.

Email-address: bdm@cs.anu.edu.au.
WWW-page: http://cs.anu.edu.au:80/people/bdm/

[15] S. P. Radziszowski, D. L. Kreher: Solving subset sum problems with the L^{3} algorithm. J. Combin. Math. Comput. 3 (1988), 49–63.

[16] B. Schmalz: The t-designs with prescribed automorphism group, new simple 6-designs. J. Combinatorial Designs 1 (1993), 125–170.

[17] C. P. Schnorr: A hierachy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science 53 (1987), 201– 224.

[18] C. P. Schnorr: A More Efficient Algorithm for Lattice Basis Reduction. J. Algorithms 9 (1988), 47–62.

[19] C. P. Schnorr, M. Euchner: Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Proceedings of Fundamentals of Computation Theory 91 in Lecture Notes in Computer Science 529 (1991), 68–85.

[20] C. P. Schnorr, H. H. Hörner: Attacking the Chor-Rivest cryptosystem by improved lattice reduction. Advances in Cryptology – Eurocrypt ’51 in Lecture Notes in Computer Science 921 (1995), 1–12.

[21] B. Sturmfels, R. Weismantel: Gröbner bases of lattices, corner polyhedra, and integer programming. Preprint (1994)

[22] R. Urbaniak, R. Weismantel, G. M. Ziegler: A Variant of the Buchberger Algorithm for Integer Programming. SIAM J. Discrete Mathematics, to appear.

Address of the author: Alfred Wassermann Department of Mathematics University of Bayreuth D-95440 Bayreuth Germany

Email: Alfred.Wassermann@uni-bayreuth.de
WWW: http://did.mat.uni-bayreuth.de/wassermann/wassermann.html