On maximal codes in polynomial metric spaces

On Maximal Codes in Polynomial Metric Spaces Peter Boyvalenkov, Danyo Danev Institute of Mathematics, Bulgarian Academy of Sciences, 8 G.Bonchev str., Sofia 1113, Bulgaria [email protected], [email protected] Abstract We study the possibilities for attaining the best known universal linear programming bounds on the cardinality of codes in polynomial metric spaces (finite or infinite). We show that in many cases these bounds cannot be attained. Applications in different antipodal polynomial metric spaces are considered with special emphasis on the Euclidean sphere and the binary Hamming space.

1

Introduction

Let M be a metric space with a finite diameter D and a finite normalized measure µM . Let the Hilbert space L2 (M) of complex-valued functions decomposes into a countable (when M is infinite) or a finite (with D + 1 members when M is finite) direct sum of mutually orthogonal subspaces L2 (M) = V0 ⊕ V1 ⊕ · · · . (1) Then M is called a polynomial metric space (PMS) if there exists an ordering of the spaces V0 , V1 , . . . (V0 is the space of constants) such that there exist real polynomials Qi (t), i = 0, 1, . . ., (Qi (t) of degree i) called zonal spherical functions (ZSF) such that for all x, y ∈ M Qi (tM (d(x, y))) =

ri 1 X vij (x)vij (y), ri j=1

(2)

where ri = dim(Vi ), {vij (x) : 1 ≤ j ≤ ri } is an orthonormal basis of Vi , and tM (d) is a continuous decreasing real function (substitution) such that tM (0) = 1 and tM (D) = −1. The ZSF constitute an orthogonal system of polynomials with respect to some weight w(t) (cf. Section 2.1 or [18, Eqs.(1.9)-(1.12)]). The infinite PMS have been classified to be the Euclidean spheres Sn−1 and the projective spaces IFPn−1 where IF = IR, C, I IH, O I (IOPn−1 exists for n = 2, 3 only). They are the connected compact strongly homogeneous spaces [14, 15, 22, 25, 29]. The finite PMS are nothing but (P and Q)-polynomial association schemes [5, 9] which are not still completely classified [5, 8, 9, 25, 26]. 1

We denote

Z

1

bi =

ti w(t)dt for i ≥ 0.

(3)

−1

Pk Pk To any real polynomial f (t) = i=0 ai ti we associate its ZSF expansion f (t) = i=0 fi Qi (t) R1 Pk for well-defined coefficients fi = ri −1 f (t)Qi (t)w(t)dt. In particular, one has f0 = i=0 ai bi . An (M, M, s) code is a finite subset W ⊂ M of cardinality |W | = M for which tM (d(x, y)) ≤ s ∈ [−1, 1) for all x, y ∈ W , x 6= y. In fact, s = tM (d) where d = min{d(x, y) : x, y ∈ W, x 6= y} is the minimum distance of W . For M and s fixed, the maximal possible cardinality of an (M, M, s) code is denoted by A(M, s). A general upper bound on A(M, s) has been derived in different PMS by Levenshtein [17, 18]. This bound can be stated in terms of ZSF and their adjacent systems (cf. Section 2.1 or [18, Section 3]) as follows [18, p.8]:  k−1 X ¡ Q1,0  1,0 k−1 (s) ¢   ri for t1,1 L (M, s) = 1 −  2k−1 k−1 ≤ s ≤ tk ,  Qk (s) i=0 A(M, s) ≤ (4) k 1,0  X ¡ ¢ Q (s)  1,0 1,1  L (M, s) = 1 − k  ri for tk ≤ s ≤ tk ,  2k Q0,1 k (s) i=0 1,0 where t1,1 and t1,0 are the greatest zeros of the adjacent polynomials Q1,1 i i i (t) and Qi (t) respectively. The bound (4) was obtained by the linear programming method (cf. Section 2.2) due to Delsarte [9], Delsarte-Goethals-Seidel [11], Kabatyanskii-Levenshtein [15]. Suitable polynomials which are extremal in some sense [18, 24] (they are the best among the polynomials of the same or lower degree) were used in [17, 18] (cf. Section 2.3). Tables with codes attaining (4) are given in [18]. A PMS M is called antipodal if for every point x ∈ M there exists a point x ∈ M such that for any point y ∈ M we have tM (d(x, y)) + tM (d(x, y)) = 0. The point x is uniquely determined by d(x, x) = D, i.e. tM (d(x, x)) = −1. For antipodal PMS, the system of ZSF is symmetric, i.e. Qi (t) = (−1)i Qi (−t) for all i and t. The Euclidean spheres and the binary Hamming spaces are the most important examples of antipodal spaces. In fact, it is not known if the bound (4) is valid in all PMS. However, it is proved for all antipodal PMS and all infinite PMS (see, e.g. [18]). An important property of the antipodal PMS is the equality bi = 0 for i odd. This simplifies the formula for f0 . In this paper we deal with codes in PMS which attain the bound (4). In Section 3 we compute the distance distribution of all such codes. For M antipodal, we prove that every (M, L2k (M, s), s) code must have s = t1,0 or s = t1,1 k k . It turns out that such codes are what are called tight designs (see Sections 2.3 and 2.5 below, or [11, 18]). In Section 4 we combine this with investigations of tight designs on the Euclidean spheres [3, 4, 6] and the binary Hamming spaces [9, 23].

2

Levenshtein Bounds

2.1. ZSF and Adjacent Polynomials. The ZSF of the infinite PMS are Jacobi polyno2

mials [2, Chapter 22] which can be defined by ¶µ ¶ k µ X 1 k+α k+β (α,β) (t) = ¡k+α¢ Pk (t + 1)i (t − 1)k−i , k ≥ 0. k i k − i 2 k i=0 n−3 n−3 1 n−1 , IRPn−1 We have (α, β) = ( n−3 2 , 2 ), ( 2 , − 2 ), (n − 2, 0), (2n − 3, 1) for M = S n−1 n−1 , CP I , IHP , respectively. The ZSF for the Hamming and Johnson spaces are the Krawtchouk and Hahn polynomials respectively. The normalized Krawtchouk polynomials can be defined by the following recurrence relation (n)

(n)

(n)

(n)

(n)

(n − k)Qk+1 (t) = ntQk (t) − kQk−1 (t), Q0 (t) = 1, Q1 (t) = t. ∞ The adjacent (to the ZSF) polynomials {Qa,b k (t)}k=0 are defined to satisfy the orthogonality condition Z 1 a,b a,b a,b a b ri c Qa,b i (t)Qj (t)(1 − t) (1 + t) w(t)dt = δi,j −1

Qa,b m (1)

= 1. and the normalization 2.2 The Linear Programming Bound. The following theorem is known as the ”linear programming bound” for codes in PMS (cf. [8, Chapter 9], [9, 18, 25]). Theorem 2.1. Let f (t) be a real polynomial such that (A1) f (t) ≤ 0 for −1 ≤ t ≤ s, and Pk (A2) The coefficients in the ZSF expansion f (t) = i=0 fi Qi (t) satisfy f0 > 0, fi ≥ 0 for i = 1, . . . , k. Then A(M, s) ≤ f (1)/f0 . For a finite PMS, the set {tM (d(x, y))|x, y ∈ M} is discrete. Thus the above condition (A1) is stronger than what is really required. 2.3. Levenshtein Polynomials and Levenshtein Bound. The upper bound on A(M, s) obtained from the linear programming bound for the polynomials ( (s) 1,0 1,0 f2k−1 (t) = (t − s)(Kk−1 (t, s))2 for t1,1 k−1 ≤ s ≤ tk , f (t) = (s) 1,1 1,0 1,1 f2k (t) = (t + 1)(t − s)(Kk−1 (t, s))2 for tk ≤ s ≤ tk , Pk a,b a,b a,b where Kka,b (u, v) = i=0 ri Qi (u)Qi (v), is known as the Levenshtein bound. It is (s) customary to call the polynomials fm (t) the Levenshtein polynomials. The real numbers {t1,1 : i = 0, 1, . . .} (t1,1 = −1) and {t1,0 : i = 1, 2, . . .} divide 0 i i the interval [−1, 1) into consecutive closed nonoverlapping intervals {Im : m = 1, 2, . . .}. For each positive integer m and all s ∈ Im one has A(M, s) ≤ Lm (M, s). The numbers Lm (M, s) are given explicitly by (4). In the common boundary points of Im and Im+1 we have k X 1,0 1,0 L2k−1 (M, tk ) = L2k (M, tk ) = ri i=0

and L2k (M, t1,1 k )

=

L2k+1 (M, t1,1 k ) 3

k X Q1,0 k (−1) = (1 − ) ri . Qk+1 (−1) i=0

(s)

2.4 Some Properties of the Levenshtein Polynomials. The polynomial f2k−1 (t) (s)

(resp. f2k (t)) has exactly k (resp. k + 1) different zeros α0 < α1 < · · · < αk−1 = s (resp. −1 = β0 < β1 < · · · < βk = s) in the interval [−1, s]. Furthermore, there exist positive weights ρi , i = 0, 1, . . . , k (resp. γi , i = 0, 1, . . . , k + 1) such that the equality f0 = ρk f (1) +

k−1 X

ρi f (αi ) (resp. f0 = γk+1 f (1) +

i=0

k X

γi f (βi ))

(5)

i=0

holds for any polynomial of degree at most 2k − 1 (resp. 2k). Theorem 2.2 We have ρk = 1/L2k−1 (M, s) (resp. γk+1 = 1/L2k (M, s)) for t1,1 k−1 ≤ 1,0 1,1 s ≤ t1,0 (resp. for t ≤ s ≤ t ). k k k (s) (s) Proof. Set the polynomial f2k−1 (t) (resp. f2k (t)) in (5). ¦ P 2.5 Designs in PMS. A code W ⊂ M is called a τ -design iff x∈W f (x) = 0 for any function f (x) ∈ V1 ∪ · · · ∪ Vτ . We use the following equivalent definition (see, e.g. [13, Equation 1.10]). P Definition 2.3 A code W ⊂ M is called a τ -design iff x∈W f (t(d(x, y))) = f0 |W | holds for any real polynomial f (t) of degree at most τ and any point y ∈ M. The cardinality of a τ -design W ⊂ M is bounded from below by [11, 12, 18]  k X    ri   |W | ≥

if τ = 2k,

i=0

k  X Q1,0  k (−1)   ) ri  (1 − Q k+1 (−1) i=0

(6) if τ = 2k + 1.

Definition 2.4 A τ -design is said to be tight if this bound is attained (compare (6) with 1,1 the equalities for L2k (M, t1,0 k ) and L2k+1 (M, tk ) in the end of Section 2.3).

3

Distance Distributions of (M, Lm (M, s), s) Codes

Let W be an (M, M, s) code and let x ∈ W . The nonnegative integers At (x) are defined by At (x) = |{y ∈ W : t(d(x, y)) = t}|. The system of numbers {At (x) : −1 ≤ t < 1} is called the distance distribution of W with respect to x. Definition 3.1 A code W ⊂ M is called a p-distance set if the set A(W ) assumed by the different values of tM (d(x, y)) for x, y ∈ W, x 6= y has exactly p elements. The following theorem is a generalization of Theorem 7.4 from [11] (that concerns the case M = Sn−1 ). Theorem 3.2 Let W ⊂ M be a τ -design and a p-distance set where A(W ) = {a1 , a2 , . . . , ap }. If p ≤ τ + 1 then the numbers At (x) do not depend on the point x and can be computed by the following Vandermonde system Aa1 (x)ai1 + Aa2 (x)ai2 + · · · + Aap (x)aip = bi |W | − 1, i = 0, 1, . . . , p − 1. Proof. Apply Definition 2.3 with y = x and for f (t) = 1, t, . . . , tp−1 , using (3). ¦

4

(7)

It is well known that every (n, Lm (n, s), s) code W is an m-design (see Eq. (5.18) in [18, Theorem 5.1]). Moreover, such a code is an [(m + 2)/2]-distance set [18, Theorem 5.1]. This and Theorem 3.2 immediately imply the following: Corollary 3.3 If W is an (M, Lm (M, s), s) code, then its distance distribution does not depend on the choice of the point x and can be computed by the system (7). ¦ Theorem 3.4 If W is an (M, L2k−1 (M, s), s) (resp. (M, L2k (M, s), s)) code, then Aαi = ρi |W | = ρi /ρk for i = 0, 1, . . . , k−1 (resp. Aβi = γi |W | = γi /γk+1 for i = 0, 1, . . . , k). Proof. We set f (t) = 1, t, . . . , tk−1 (resp. f (t) = 1, t, . . . , tk ) in (5) and divide these equalities by ρk (resp. γk+1 ). Using Theorem 2.2, we obtain that the resulting system with respect to the numbers ρ0 /ρk , ρ1 /ρk , . . . , ρk−1 /ρk (resp. γ0 /γk+1 , γ1 /γk+1 , . . . , γk /γk+1 ) coincides with the system (7) for the code W . ¦ In the next section we shall prove the nonexistence of (M, L2k (M, s), s) codes in antipodal PMS. Thus the formulae one can obtain by Theorem 3.4 are interesting for nonantipodal spaces and for (M, L2k−1 (M, s), s) codes in antipodal PMS. The following assertion is a consequence of the explicit expressions for ρ0 , ρ1 , . . . , ρk (resp. γ0 , γ1 , . . . , γk+1 ) given in [18, Section 4] and Theorem 3.4. Corollary 3.5 If W is an (M, L2k−1 (M, s), s) (resp. (M, L2k (M, s), s)) code, then Aαi =

ρi |W | = , i = 0, 1, . . . , k − 1, 1,0 1,0 ρk c (1 − αi )Kk−1 (αi , αi )

(resp. Aβi =

γi γk+1

=

c1,1 (1

|W | , i = 0, 1, . . . , k). − βi2 )Kk1,1 (βi , βi )

Proof. Apply Theorem 3.4 and Theorems 4.1 and 4.2 from [18]. ¦ For M antipodal, the system (7) is simpler due to the equalities bi = 0 for i odd. We consider the equations with i odd in order to find new formulae for the distance distributions of (M, L2k−1 (M, s), s) codes in antipodal M. In fact, the next lemma is true for an arbitrary PMS. Lemma 3.6 The numbers α0 , α1 , . . . , αk−1 are strictly increasing functions in s ∈ 1,0 (t1,1 k−1 , tk ). Proof. The numbers α0 , α1 , . . . , αk−1 are the roots of the equation [18, Eq. 4.7] Q1,0 k (t)

Q1,0 k−1 (t)

=

Q1,0 k (s)

Q1,0 k−1 (s)

.

These ratios are strictly increasing in every interval which does not contain zeros of the denominator. Therefore slight changes of s give changes of the αi ’s in the same direction 1,1 that completes the proof since t1,0 k−1 < tk−1 . ¦ Lemma 3.7 For M antipodal, we have αi 6= −αj for all i, j ∈ {0, 1, . . . , k − 1} and all 1,0 s ∈ (t1,1 k−1 , tk ]. 1,0 Proof. For s = t1,0 k , the numbers α0 , α1 , . . . , αk−1 are the zeros of the polynomial Qk (t) which possess the desired unsymmetry [18, Section 3]. 1,0 For s ∈ (t1,1 k−1 , tk ), it follows by Lemma 3.6 that αi = −αj for some i, j ∈ {0, 1, . . . , k−1} can occur only for a finite number of s0 . Let us suppose that for s = s0 we have αi = −αj . 5

1,0 There exists small enough ε > 0 such that (s0 − ε, s0 + ε) ⊂ (t1,1 k−1 , tk ) and αi1 6= −αi2 for every i1 , i2 ∈ {0, 1, . . . , k−1} whenever s ∈ (s0 −ε, s0 +ε)\{s0 }. We set f (t) = t, t3 , . . . , t2k−1 in (5) and obtain a Vandermonde system with respect to the ratios ρl /ρk , l = 0, 1, . . . , k − 1. For s ∈ (s0 − ε, s0 + ε)\{s0 } this system has a unique solution. In particular, we have 2 2 2 (1 − α02 )(1 − α12 ) · · · (1 − αi−1 )(1 − αi+1 ) · · · (1 − αk−1 ) ρi . =− 2 2 2 2 2 2 2 2 2 2 ) ρk αi (αi − α0 )(αi − α1 ) · · · (αi − αi−1 )(αi − αi+1 ) · · · (αi − αk−1

By this equality, it is easy to see that ρi /ρk changes its sign for s = s0 , which is impossible since ρi and ρk are positive. ¦ 1,0 Theorem 3.8 If M is antipodal, s ∈ (t1,1 and W is an (M, k−1 , tk ], L2k−1 (M, s), s) code, then Aαi =

2 2 2 (1 − α02 )(1 − α12 ) · · · (1 − αi−1 )(1 − αi+1 ) · · · (1 − αk−1 ) ρi =− 2 2 2 2 2 2 2 2 2 2 ρk αi (αi − α0 )(αi − α1 ) · · · (αi − αi−1 )(αi − αi+1 ) · · · (αi − αk−1 )

for i = 0, 1, . . . , k − 1. Proof. As in the proof of Lemma 3.7, set f (t) = 1, t3 , . . . , t2k−1 in (5) and resolve by the Cramer rule the resulting system. ¦ 1,0 Corollary 3.9 If M is antipodal and s ∈ (t1,1 k−1 , tk ] then |α0 | > |αk−1 | > |α1 | > |αk−2 | > · · · > |αj(k) | where j(k) = bk/2c + 1. In particular, αj(k) < 0 < αj(k)+1 for k odd, and αj(k)−1 < 0 < αj(k) for k even. Proof. Let |αi0 | > |αi1 | > · · · > |αik−1 | (equalities are impossible by Lemma 3.7), where (i0 , i1 , . . . , ik−1 ) is a permutation of (0, 1, . . . , k − 1). By the formulae from Theorem 3.8 for ρi /ρk > 0, we conclude that sign(αij ) = (−1)j+1 . This and −1 < α0 < α1 < · · · < αk−1 = s < 1 implies the assertion. ¦ Theorem 3.8 is very convenient for computer calculations of the distance distributions (simply checking if they are integral) of (M, L2k−1 (M, s), s) codes. For example, we have found all possible parameters of (M, L2k−1 (M, s), s) codes in the cases M = Sn−1 and k = 2 (in dimensions n ≤ 1600) and k = 3 (in dimensions n ≤ 400). In a recent application, we use the formulae from Theorem 3.8 for investigations on necessary conditions for the existence of (2k − 1)-designs in PMS.

4

Nonexistence of (M, L2k (M, s), s) Codes in Antipodal PMS

4.1. Any (M, L2k (M, s), s) Code in Antipodal M Is a Tight Design. Let W be an (M, L2k (M, s), s) code in antipodal M. By [18, Theorem 4.2] we have explicit formulae for γi , i = 0, 1, . . . , k + 1. We need the expressions for γ0 and γk+1 only (see [18, Eqs. 4.13-4.15]). Lemma 4.1 γ0 = Kk (s, 1)/(Kk (−1, −1)Kk (s, 1) − Kk (−1, 1)Kk (s, −1)), γk+1 = Kk (s, −1)/(Kk (1, 1)Kk (s, −1) − Kk (1, −1)Kk (s, 1)). ¦ Lemma 4.2 The function A(s) = Kk (s, 1)/Kk (s, −1) does not change its sign in the 1,1 1,1 k+1 interval (t1,0 . k , tk ] and this sign is determined by A(tk ) = (−1)

6

Proof. By [18, Lemma 3.1] we have A(s) =

Q1,0 k (s)

Kk (1, 1) · K Q0,1 (s) k (1, −1) k

Pk 1,1 Since Qi (1) = 1 by (2), we have Kk (1, 1) = i=0 ri > 0. Further, for s ∈ (t1,0 k , tk ] we have 1,0 0,1 Qk (s) > 0 and Qk (s) < 0 [18, Section 3] which implies sign(A(s)) = −sign(Kk (1, −1)). 1,1 Thus the function A(s) has a constant sign in (t1,0 k , tk ] depending only on k. Again by [18, Lemma 3.1] we have Kk (s, −1) + (−1)k Kk (s, 1) = const.Q1,1 k (s)

(8)

k+1 whence A(t1,1 . ¦ k ) = (−1) Theorem 4.3 If M is antipodal and W is an (M, L2k (M, s), s) code, then s = t1,0 k or s = t1,1 . k Proof. For any point x ∈ M there exist a unique (antipodal) point x such that tM (d(x, x)) = −1. Therefore A−1 = Aβ0 ∈ {0, 1}. By Theorem 3.4 we have A−1 = γ0 /γk+1 . If γ0 /γk+1 = 0, then γ0 = 0, which is equivalent to Kk (s, 1) = 0. Since Kk (s, 1) = 1,0 Kk (1, 1)Q1,0 k (s) by [18, Lemma 3.1] and Kk (1, 1) > 0, it follows that Qk (s) = 0 which is 1,0 possible iff s = tk . Let us suppose that γ0 /γk+1 = 1. Trivial calculations by Lemma 4.1 show that this is equivalent to A(s) = ±1. By Lemma 4.2 we conclude that A(s) = (−1)k+1 . By (8), this 1,1 implies Q1,1 k (s) = 0 which is possible only for s = tk . This completes the proof. ¦ Corollary 4.4 If M is antipodal and W is an (M, L2k (M, s), s) code, then W is a tight 1,1 (2k)-design (when s = t1,0 k ) or a tight (2k + 1)-design (when s = tk ). 1,0 1,1 Proof. Compare Section 2.3 and (6) for L2k (M, tk ) and L2k (M, t1,1 k ). For s = tk , W is a (2k)-design and an antipodal code, which means that it is a (2k + 1)-design. ¦ 4.2. M = Sn−1 . In this case L2 (Sn−1 ) decomposes into the sum (1) where Vi = Harm(i) is the space of all n-variable homogeneous harmonic polynomials (spherical harmonics) of total degree i. The dimension of Vi is µ ¶ µ ¶ n+k−1 n+k−3 ri = − . n−1 n−1 (n)

The corresponding ZSF is a normalized Gegenbauer (ultraspherical) polynomial Qi (t) (cf. Section 2.1). The measure w(t) is given by w(t) = (1 − t2 )(n−3)/2 . Then (3) implies bi = 0 for i odd and bi = ((i − 1)!!)/(n(n + 2) · · · (n + i − 2)) for i even (b0 = 1). Theorem 4.5 [7] If W is an (n, L2k (n, s), s) code (k ≥ 2, n ≥ 3), then one of the following holds: a) k = 2, n = m2 − 3, m √≥ 3 is odd, s = 1/(m + 1), and W is a tight spherical 4-design; b) k = 2, n = 3, s = 1/ 5, and W is the icosahedron (which is a tight spherical 5-design); c) k = 2, n = m2 − 2, m ≥ 3 is odd, s = 1/m, and W is a tight spherical 5-design; d) k = 3, n = 3m2 − 4, m ≥ 2 is integer, s = 1/m, and W is a tight spherical 7-design; e) k = 5, n = 24, s = 1/2, and W is the unique tight spherical 11-design formed by the vectors of minimal norm in the Leech lattice. 7

Proof. We refer to the classification of the tight spherical designs [3, 4, 6, 11]. Indeed, tight (2k)-designs do not exist when k ≥ 3 [3] and tight (2k + 1)-designs do not exist when k ≥ 4 except for k = 5 and n = 24 [4]. Tight 4- or 5-designs could possibly exist in dimensions n = m2 − 3 (for 4-designs) or n = 3 and n = m2 − 2 (for 5-designs), m ≥ 3 is odd [6]. Tight 7-designs could possibly exist in dimensions n = 3m2 − 4, m ≥ 2 is an integer. ¦ 4.3 M = H(n, 2). Another important example of an antipodal PMS is the binary Hamming space with the usual Hamming metric. It is finite with diameter D(H(n, 2)) = n. The space L¡2 (H(n, 2)) decomposes into a finite direct sum with n + 1 members, and ¢ dim(Vi ) = ri = ni . The ZSF are obtained by applying the substitution d = n(1−t)/2 to the usual Krawtchouk (n) polynomials Kk (d) [21, Chapter 5] (n)

Kk (d) =

k X

(−1)j

j=0

µ ¶µ ¶ d n−d j k−j

and normalizing (cf. Section 2.1). Since w(t(d)) = b2j+1 = 0, b2j =

¡n¢ d , (3) gives

¶2j µ ¶ n µ 1 X n 2d , b0 = 1. 1 − n 2 n d d=0

The (H(n, 2), M, s) codes are usually referred to as (n, M, d) codes, where d = n(1 − s)/2 is their minimum distance. The value A(H(n, 2), s) is the well known and extensively studied quantity A(n, d) [21]. A code W ⊂ H(n, 2) is a τ -design if and only if any set of τ columns of the matrix formed of all vectors of W (as rows) consists each τ -tuple the same number of times (namely |W |/2τ , i.e. 2τ divides |W |). Thus a τ -design in H(n, 2) is nothing but an orthogonal array of strength τ [10] or, equivalently, a τ -wise independent set as defined in [1]. A tight (2k + 1)-design in H(n + 1, 2) exists if and only if a tight (2k)-design in H(n, 2) exists. Thus we need to consider tight (2k)-designs only. Tight 4-designs in H(n, 2) for n ≥ 6 do not exist [23]. The only tight 6-design in H(n, 2) for n ≥ 8 is the (23, 211 , 8) code (orthogonal to the binary Golay code) [10]. These statements were proved by using the following Lloyd-type theorem [9, 10] (originally designed for the existence of perfect and uniformly packed codes in the Hamming spaces [20, 21, 27, 28, 30]). Lemma 4.6 [9] If k < n/2 is a positive integer and a tight (2k)-design in H(n, 2) exists (n−1) then the Krawtchouk polynomial Kk (d) has k different integral zeros. The assumption k 6∈ {4, . . . , [n/2] − 1} in the next theorem is natural because of the (n−1) well known conjecture [16] that every Krawtchouk polynomial Kk (d) has at least one noninteger zero for 3 < k < (n − 1)/2. We conjecture that Theorem 4.7 completely describes the situation with the (n, L2k (H(n, 2), s), d) codes, i.e. it is true without the assumption k 6∈ {4, . . . , [n/2] − 1}. Theorem 4.7 If W is an (n, L2k (H(n, 2), s), d) code (k 6∈ {4, . . . , [n/2] − 1} or 2k = n), then one of the following holds: a) k = 1, n = 4m−1, m ≥ 1 is integer, s = −1/n, and d = 2m, i.e. W is a (4m−1, 4m, 2m) shortened Hadamard code which is a tight 2-design; b) k = 1, n = 4m, m ≥ 1 is integer, s = 0, and d = 2m, i.e. W is a (4m, 8m, 2m) Hadamard 8

code which is a tight 3-design; c) k = 3, n = 23, s = 8/23, and d = 8, i.e. W is the (23, 211 , 8) code which is a tight 6-design; d) k = 3, n = 24, s = 1/3, and d = 8, i.e. W is the (24, 212 , 8) extended binary Golay code which is a tight 7-design; e) k = [(n − 1)/2], s = (n − 4)/n, and d = 2, i.e. W is the (n, 2n−1 , 2) even-weight code which is a tight (n − 1)-design. Acknowledgement. This research was partially supported by the Bulgarian NSF under Contract MM-502/95. The authors thank an anonymous referee for useful remarks.

References [1] N.Alon, O.Goldreich, J.Hastad, R.Peralta, Simple construction of almost k-wise independent random variables, Random Structures and Algorithms 3, 1992, 289-304. [2] M.Abramowitz, I.A.Stegun, Handbook of Mathematical Functions, Dover, New York, 1965. [3] E.Bannai, R.M.Damerell, Tight spherical designs I, J. Math. Soc. Japan 31, 1979, 199207. [4] E.Bannai, R.M.Damerell, Tight spherical designs II, J. London Math. Soc. 21, 1980, 13-30. [5] E.Bannai, T.Ito, Algebraic Combinatorics I: Association Schemes, Benjamin, Menlo Park CA, 1984. [6] P.G.Boyvalenkov, Computing distance distribution of spherical designs, Lin. Alg. Appl. 226/228, 1995, 277-286. [7] P.G.Boyvalenkov, D.Danev, I.N.Landgev, On maximal spherical codes II, submitted. [8] J.H.Conway, N.J.A.Sloane, Sphere Packings, Lattices and Groups, Springer – Verlag, New York 1988. [9] P.Delsarte, An Algebraic Approach to the Association Schemes in Coding Theory, Philips Res. Rep. Suppl. 10, 1973. [10] P.Delsarte, Four fundamental parameters of a code and their combinatorial significance, Inform. Contr. 23, 1973, 407-438. [11] P.Delsarte, J.-M.Goethals, J.J.Seidel, Spherical codes and designs, Geom. Dedicata 6, 1977, 363-388. [12] C.F.Dunkl, Discrete quadrature and bounds on t-designs, Mich. Math. J. 26, 1979, 81-102. [13] G.Fazekas, V.I.Levenshtein, On the upper bounds for code distance and covering radius of designs in polynomial metric spaces, J. Comb. Theory A70, 1995, 267-288. 9

[14] S.Helgason, Differential Geometry, Lie Groups and Symmetric Spaces, Acad. Press NY, 1978. [15] G.A.Kabatyanskii, V.I.Levenshtein, Bounds for packings on a sphere and in space, Probl. Inform. Transm. 14, 1978, 1-17. [16] I.Krasikov, S.Litsyn, On integral zeros of Krawtchouk polynomials, J. Comb. Theory A74, 1996, 71-99. [17] V.I.Levenshtein, Bounds for packings in metric spaces and certain applications, Probl. Kibernetiki 40, 1983, 44-110 (in Russian). [18] V.I.Levenshtein, Designs as maximum codes in polynomial metric spaces, Acta Appl. Math. 29, 1992, 1-82. [19] V.I.Levenshtein, Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces, IEEE Trans. Inform. Theory 41, 1995, 1303-1321. [20] J.H.van Lint, A survey of perfect codes, Rocky Mountain J. Math. 5, 1975, 199-224. [21] F.J.MacWilliams, N.J.A.Sloane, The Theory of Error-Correcting Codes, North Holland, Amsterdam, 1977. [22] A.Neumaier, Combinatorial configurations in terms of distances, Memorandum 81-09 (Dept. Math.), Eindhoven Univ. Technology, 1981. [23] R. Noda, On orthogonal arrays of strength 4 achieving Rao’s bound, J. London Math. Soc. 19, 1979, 385-390. [24] V.M.Sidel’nikov, On extremal polynomials used to estimate the size of codes, Probl. Inform. Transm. 16, 1980, 174-186. [25] N.J.A.Sloane, Recent bounds for codes, sphere packings and related problems obtained by linear programming and other methods, Contemp. Math. 9, 1982, 153-185. [26] P.Terwilliger, A characterization of P- and Q-polynomial schemes, J. Combin. Theory A45, 1987, 8-26. [27] A.Tiet¨av¨ainen, A.Perko, There are no unknown perfect binary codes, Ann. Univ. Turku Ser. A, I 148, 1971, 3-10. [28] H.C.A. van Tilborg, Uniformly packed codes, Ph.D. Thesis, Eindhoven, 1976. [29] H.-C.Wang, Two-point homogeneous spaces, Ann. Math. 55, 1952, 177-191. [30] V.Zinoviev, V.Leontjev, The nonexistence of perfect codes over Galois fields, Problemy upravleniya i teorii informatsii 2, 1973, 123-132 (in Russian).

10