An infinite family of non-embeddable Hadamard designs

K. Mackenzie-Fleming Department of Mathematics, Central Michigan University Mount Pleasant MI 48859 U.S.A.

                         kirsten.fleming@cmich.edu

Submitted: Mar 22, 1999; Accepted: May 16, 1999

Abstract

The parameters 2 - (2λ + 2, λ + 1, λ) are those of a residual Hadamard 2 - (4λ + 3, 2λ + 1, λ) design. All 2 - (2λ + 2, λ + 1, λ) designs with λ ≤ 4 are embeddable. The existence of non-embeddable Hadamard 2-designs has been determined for the cases λ = 5, λ = 6, and λ = 7. In this paper the existence of an infinite family of non-embeddable 2 - (2λ + 2, λ + 1, λ) designs, λ = 3(2^{m}) − 1, m ≥ 1 is established.

Mathematical Reviews Subject Number: 05B05

Dedicated to the memory of George Mackenzie

1 Introduction

To date λ = 5, 6 and 7 are the only values for which non-embeddable quasi-residual 2 - (2λ + 2, λ + 1, λ) are known to exist. In 1977 van Lint, van Tilborg and Wiekema [1] proved that all quasi-residual 2 - (2λ+2, λ+1, λ) designs with λ ≤ 4 are residual. The first known example of a non-embeddable 2 - (2λ+2, λ+1, λ) design was constructed in 1978 by van Lint [2], this being a design having λ = 5. Subsequently Tonchev ([3] and [4]) demonstrated the existence of non-embeddable 2 - (14, 7, 6) designs and constructed several non-embeddable 2 - (16, 8, 7) designs. This paper describes the first known infinite family of non-embeddable 2 - (2λ + 2, λ + 1, λ) designs.

2 Terminology and notation

An incidence structure D = (P, B, I), with point set P, block set B and incidence I is a 2-(v, k, λ) design, if |P| = v, every block B ∈ B is incident with precisely k points, and every pair of points are together incident with precisely λ blocks. Further, |B| = b and any point is contained in exactly r blocks, where b and r are dependent on v, k, and λ. A symmetric 2 - (v, k, λ) design has v = b or equivalently r = k. A residual design of a symmetric design is a 2 - (v − k, k − λ, λ) design obtained by removing a block B and all points in B from the other blocks. A 2-design with r = k + λ is a quasi-residual design. If such a design is residual then it is embeddable, otherwise it is non-embeddable. A Hadamard 2-design is one in which v = 4λ+3, and k = 2λ + 1. An incidence matrix of a 2 - (v, k, λ) design is a b × v matrix A = a_{ij}, in which a_{ij} = 1 if block i contains point j and a_{ij} = 0 otherwise.

3 Results

The strategy for establishing the existence of an infinite family of non-embeddable 2 - (2λ + 2, λ + 1, λ) designs has three steps.

1) Prove that if D contains a collection of five blocks with specified pairwise intersection sizes then D is not embeddable in a 2 - (4λ + 3, 2λ + 1, λ) design;

2) Describe a recursive construction for an infinite family of 2 - (2λ + 2, λ + 1, λ) designs. This construction has the property that if the initial design in the infinite family has the collection of five blocks mentioned above then so do all other members of the infinite family;

3) Give a design having the required collection of five blocks.

Theorem 1 A 2 - (2λ + 2, λ + 1, λ) design D containing a set of five blocks, say, l_{1}, l_{2}, l_{3}, l_{4}, l_{5} with intersection sizes given in the following table:

l_{1}  l_{2}  l_{3}  l_{4}  l_{5}
l_{1} λ + 1 \frac{2λ+2}{3}  \frac{λ+1}{2}  \frac{λ+1}{3}  \frac{λ+1}{2}

l_{2} \frac{2λ+2}{3} λ + 1 \frac{2λ+2}{3}  \frac{λ+1}{2}  \frac{λ+1}{3}

l_{3} \frac{λ+1}{2}  \frac{2λ+2}{3} λ + 1 \frac{λ+1}{3}  \frac{λ+1}{3}

l_{4} \frac{λ+1}{3}  \frac{λ+1}{2}  \frac{λ+1}{3} λ + 1 \frac{2λ+2}{3}

l_{5} \frac{λ+1}{2}  \frac{λ+1}{3}  \frac{λ+1}{3}  \frac{2λ+2}{3} λ + 1

is not embeddable in a 2 - (4λ + 3, 2λ + 1, λ) design.

To embed D we require 2λ + 1 new points, say, S = {1, 2, ..., 2λ + 1} and each block of D must be extended using λ points from S. Without loss of generality, let the extensions of l_{3} and l_{5} be:

e_{3} = \{1, 2, ..., λ\} and e_{5} = \{1, 2, ...\frac{2λ − 1}{3}, λ + 1, λ + 2, ..., \frac{4λ + 1}{3}\}.

Let

S_{1} = \{1, 2, ..., \frac{2λ−1}{3}\}  then |S_{1}| = \frac{2λ−1}{3}
S_{2} = \{\frac{2λ+2}{3}, \frac{2λ+5}{3}, ..., λ\}  then |S_{2}| = \frac{λ+1}{3}
S_{3} = \{λ + 1, λ + 2, ..., \frac{4λ+1}{3}\} then |S_{3}| = \frac{λ+1}{3}
S_{4} = \{\frac{4λ+4}{3}, \frac{4λ+7}{3}, ..., 2λ + 1\} then |S_{4}| = \frac{2λ+2}{3}

Further let x_{i}, i = 1, 2, 3, 4 be the number of points from S_{i} in the extension of l_{4}. Then

\begin{aligned}x_{1} & + & x_{2} & = & λ − \frac{λ+1}{3} & = & \frac{2λ−1}{3} & (1) \\ x_{1} & + & x_{3} & = & λ − \frac{2λ+2}{3} & = & \frac{λ−2}{3} & (2) \end{aligned}

Equations (1) and (2) give x_{2} − x_{3} = \frac{λ+1}{3}, which together with |S_{2}| = \frac{λ+1}{3} gives x_{2} = \frac{λ+1}{3}, and x_{3} = 0. This then gives x_{1} = \frac{λ−2}{3} and x_{4} = \frac{λ+1}{3}. This implies that, up to isomorphism, there is a unique extension for l_{4}, this extension being

e_{4} = \{1, 2, ...\frac{λ − 2}{3}, \frac{2λ + 2}{3}, \frac{2λ + 5}{3}, ..., λ, \frac{4λ + 4}{3}, \frac{4λ + 7}{3}, ..., \frac{5λ + 2}{3}\}.

Now let

T_{1} = \{1, 2, ...\frac{λ−2}{3}\}  then |T_{1}| = \frac{λ−2}{3}
T_{2} = \{\frac{λ+1}{3}, \frac{λ+4}{3}, ..., \frac{2λ−1}{3}\}  then |T_{2}| = \frac{λ+1}{3}
T_{3} = \{\frac{2λ+2}{3}, \frac{2λ+5}{3}, ..., λ\}  then |T_{3}| = \frac{λ+1}{3}
T_{4} = \{λ + 1, λ + 2, ..., \frac{4λ+1}{3}\} then |T_{4}| = \frac{λ+1}{3}
T_{5} = \{\frac{4λ+4}{3}, \frac{4λ+7}{3}, ..., \frac{5λ+2}{3}\} then |T_{5}| = \frac{λ+1}{3}
T_{6} = \{\frac{5λ+5}{3}, \frac{5λ+8}{3}, ..., 2λ + 1\} then |T_{6}| = \frac{λ+1}{3}

Let y_{j}, j = 1, 2, ..., 6 be the number of points from T_{j} in the extension of l_{1}. Then

\begin{aligned}y_{1} & + & y_{2} & + & y_{3} & = & λ − \frac{λ+1}{2} & = & \frac{λ−1}{2} & (3) \\ y_{1} & + & y_{2} & + & y_{4} & = & λ − \frac{λ+1}{2} & = & \frac{λ−1}{2} & (4) \\ y_{1} & + & y_{3} & + & y_{5} & = & λ − \frac{λ+1}{3} & = & \frac{2λ−1}{3} & (5) \end{aligned}

Equations (3), (4) and (5) give y_{1} + y_{4} + y_{5} = \frac{2λ−1}{3}. Let z_{k}, k = 1, 2, ..., 6 be the number of points from T_{k} in the extension of l_{2}. Then

\begin{aligned}z_{1} & + & z_{2} & + & z_{3} & = λ − \frac{2λ+2}{3} & = & \frac{λ−2}{3} & (6) \\ z_{1} & + & z_{2} & + & z_{4} & = λ − \frac{λ+1}{3} & = & \frac{2λ−1}{3} & (7) \\ z_{1} & + & z_{3} & + & z_{5} & = λ − \frac{λ+1}{2} & = & \frac{λ−1}{2} & (8) \end{aligned}

Equations (6),(7) and (8) give z_{1} +z_{4} +z_{5} = \frac{5λ−1}{6}. Since \frac{5λ−1}{6} > \frac{2λ−1}{3} and |T_{1}|+|T_{4}|+ |T_{5}| = λ, the size of the intersection of the extensions of l_{1} and l_{2} is at least

\frac{5λ − 1}{6} + \frac{2λ − 1}{3} − λ = \frac{λ − 1}{2}

which is greater than the intersection size of \frac{λ−2}{3} required for the extensions of l_{1} and l_{2}. □

Let I be the (0,1) incidence matrix of a 2 - (2λ + 2, λ + 1, λ) design, D_{1}, I^{c} be the incidence matrix of the complementary design of D, \underline{1} be the all-one vector of length 2λ + 2 and \underline{0} be the all-zero vector of length 2λ + 2. One can easily verify that

[ \begin{matrix}I & I \\ I^{c} & I \\ \underline{1} & \underline{0} \\ \underline{0} & \underline{1} \end{matrix} ]

is the incidence matrix of a 2 - (4λ + 4, 2λ + 2, 2λ + 1) design, D_{2}. If, in particular, this construction is implemented without reordering the rows of I then any pair of blocks b_{i}, b_{j} from D_{1} with |b_{i} ∩ b_{j}| = s will give rise to a pair of blocks in D_{2} whose intersection size is 2s. Further, note that if t is any of the intersection sizes specified in Theorem 1, then replacing λ by 2λ + 1 gives a required intersection size of 2t. Thus, if D_{1} satisfies the conditions of Theorem 1 then so does D_{2} and the problem of establishing the existence of an infinite family of non-embeddable quasi-residual 2 - (2λ + 2, λ + 1, λ) designs is reduced to finding a single design which fulfils the conditions of Theorem 1. The following 2 - (12, 6, 5) design satisfies the conditions of Theorem 1.

\begin{matrix}b_{1} & \{1 & 2 & 3 & 7 & 8 & 9\} \\ b_{2} & \{4 & 5 & 6 & 7 & 8 & 9\} \\ b_{3} & \{1 & 2 & 4 & 7 & 8 & 10\} \\ b_{4} & \{3 & 5 & 6 & 7 & 8 & 10\} \\ b_{5} & \{1 & 2 & 5 & 7 & 9 & 11\} \\ b_{6} & \{3 & 4 & 6 & 7 & 9 & 12\} \\ b_{7} & \{1 & 2 & 6 & 7 & 10 & 12\} \\ b_{8} & \{3 & 4 & 5 & 7 & 10 & 11\} \\ b_{9} & \{1 & 3 & 4 & 7 & 11 & 12\} \\ b_{10} & \{2 & 5 & 6 & 7 & 11 & 12\} \\ b_{11} & \{1 & 3 & 5 & 8 & 9 & 12\} \\ b_{12} & \{2 & 4 & 6 & 8 & 9 & 11\} \\ b_{13} & \{1 & 3 & 6 & 8 & 10 & 11\} \\ b_{14} & \{2 & 4 & 5 & 8 & 10 & 12\} \\ b_{15} & \{1 & 4 & 5 & 8 & 11 & 12\} \\ b_{16} & \{2 & 3 & 6 & 8 & 11 & 12\} \\ b_{17} & \{1 & 4 & 6 & 9 & 10 & 11\} \\ b_{18} & \{2 & 3 & 5 & 9 & 10 & 11\} \\ b_{19} & \{1 & 5 & 6 & 9 & 10 & 12\} \\ b_{20} & \{2 & 3 & 4 & 9 & 10 & 12\} \\ b_{21} & \{1 & 2 & 3 & 4 & 5 & 6\} \\ b_{22} & \{7 & 8 & 9 & 10 & 11 & 12\} \end{matrix}

where l_{1} = b_{1}, l_{2} = b_{3}, l_{3} = b_{7}, l_{4} = b_{8} and l_{5} = b_{18}. Therefore, there is an infinite family of non-embeddable 2 - (2λ + 2, λ + 1, λ) designs with λ = 3(2^{m}) − 1.

The author would like to thank the Department of Mathematical Sciences at Clemson University for their hospitality during the 98/99 academic year.

References

[1] J. H. van Lint, H. C. A. van Tilborg and J. R. Wiekema Block designs with v = 10, k = 5, λ = 4 J. Combin. Theory A, 23, 105–115, 1977.

[2] J. H. van Lint Non-embeddable quasi-residual designs Indag. Math., 40, 269–275, 1978.

[3] V. D. Tonchev Embeddings of the Preece quasi-residual designs into symmetric designs Sankhya: The Indian Journal of Statistics, Series B, 49, 216–223, 1986.

[4] V. D. Tonchev Some small non-embeddable designs Discrete Mathematics, 06/10, 489–492, 1992.