ON A GENERALIZATION OF SPHERICAL CODES AND DESIGNS.

RENAUD COULANGEON

Abstract. We introduced with C. Bachoc and G. Nebe a notion of design (resp. code) in Grassmannian spaces. This extends the classical notions of spherical design (resp. code), which in this setting corresponds to the Grassmannian space G_{1,n}, the set of lines in ℝ^{n}. This paper will survey on various results and applications, in particular to the study of Rankin invariants of lattices. We also give some bounds for the size of designs and codes which were obtained in collaboration with E. Bannai.

1. Introduction.

This a survey on recent work with C. Bachoc, E. Bannai and G. Nebe. To start with, let us recall the classical notions of spherical designs and codes (see [5]). We endow the sphere S^{n−1} with its canonical O(n)-invariant measure dx, normalized so as ∫_{S^{n−1}} dx = 1.

Definition 1.1. A finite subset set X of S^{n−1} is a t-design, t a positive integer, if for any homogeneous polynomial f of degree at most t one has

∫_{S^{n−1}} f(x)dx = \frac{1}{|X|} ∑_{x∈X} f(x) (1)

Definition 1.2. A finite subset set X of S^{n−1} is an s-code, s a positive integer, if the scalar products of pairwise distinct vectors in X take at most s values

|{x · y, x ≠ y ∈ X}| ≤ s (2)

Examples of designs arise in the theory of Euclidean lattices: if L is a lattice in ℝ^{n}, i.e. a discrete subgroup of ℝ^{n} of maximal rank, one defines the set S(L) of minimal vectors of L as the (finite) set of nonzero vectors in L with minimal length. One can of course view S(L), conveniently rescaled, as a finite subset of S^{n−1}. The following theorem, due to B. Venkov, is one of the motivation for our work on generalized designs:

Theorem 1.3 ([11]). If S(L) is a 4-design, then L achieves a local maximum of the Hermite function γ(L) = \frac{min L}{(det L)^{1/n}}

Recall that min L stands for the minimal squared length of nonzero vectors in L, and det L = vol(ℝ^{n}/L)^{2}, so that γ(L)^{n/2} is proportional to the density of the sphere packing associated to L.

Our definition of designs in general Grassmanian spaces give rise to similar results for higher dimensional analogues of the Hermite invariants, the socalled Rankin invariants ([10]), see section 5.

It is natural to ask for a lower (resp. upper) bound for the size of a t-design (resp. s-code). Such bounds were exhibited in [5], and the notion of tightdesign and code (i.e. achieving these bounds) was introduced. Moreover, a kind of duality between tight-designs and tight-codes was brought to the fore. In section 6, we give similar bounds for designs and codes in general Grassmanian spaces.

2. Grassmannnians.

The Grassmannian space G_{m,n} (resp. G_{m,n}^{∘}) is the set of m-dimensional subspaces (resp. oriented subspaces) of ℝ^{n}. They are homogeneous spaces isomorphic respectively to O(n)/O(m)×O(n−m) and O(n)/SO(m)×O(n− m), and G_{m,n}^{∘} is a 2 to 1 covering of G_{m,n}.

\xymatrix{G_{m,n}^{∘} \ar[d]_{(2:1)} & ≃ O(n)/SO(m) × O(n − m) \\ G_{m,n} & ≃ O(n)/O(m) × O(n − m)}

Example: m = 1

\xymatrix{G_{1,n}^{∘} \ar[d]_{(2:1)} & = S^{n−1} \\ G_{1,n} & = ℙ^{n−1}}

We need to characterize the relative positions of two m-dimensional subspaces of ℝ^{n}, or, in more sophisticated words, to characterize the O(n)-orbit of a couple (p, q) ∈ G_{m,n}^{2}. If m = 1, the relative positions of two lines through 0 is determined by their angle. In general, we define a m-tuple of principal angles as follows: we fix a base point p_{0}, for instance p_{0} := the mdimensional subspace generated by the first m vectors of the canonical basis of ℝ^{n}. Then, each couple (p, q) ∈ G_{m,n}^{2} can be written as (p, q) = (g.p_{0}, h.p_{0}) for suitable g and h in O(n). We decompose the matrix g^{−1}h into blocks

g^{−1}h = (\begin{matrix}A & B \\ C & D \end{matrix})

with A ∈ M_{m}(ℝ), and denote by 1 ≥ y_{1} ≥ y_{2} ≥ ⋯ ≥ y_{m} ≥ 0 the eigenvalues of the real symmetric matrix AA^{t}. Finally, we let t_{i} := \sqrt{y_{i}} = cos θ_{i} ∈ [0, 1]. Then, the O(n)-orbit of (p, q) is characterized by the m-tuple (t_{1}, ⋯, t_{m})

O(n).(p, q) ↔ (t_{1}, ⋯, t_{m}). (3)

Remark. it is readily seen that this definition of the principal angles is equivalent to the classical one, as given in [7], p.584, for instance.

As for the O(n)-orbit of a couple (p̃, q̃) ∈ G_{m,n}^{∘}^{2}, one needs one more invariant, namely ϵ := \frac{det A}{| det A|}:

O(n).(p̃, q̃) ↔ (ϵ, t_{1}, ⋯, t_{m}). (4)

3. Some harmonic analysis. Zonal functions.

The space of square integrable functions on G_{m,n}, resp G_{m,n}^{∘} splits into O(n)-irreducible modules H_{m,n}^{μ}, indexed by partitions μ = μ_{1} ≥ ⋯ ≥ μ_{m} of an integer k in at most m nonzero parts, as follows (see [8] p. 546 or [2]): we say that a partition μ = μ_{1} ≥ ⋯ ≥ μ_{m} ≥ 0 of an integer k is admissible if

(5) μ_{i} ≡ μ_{j} mod 2 for all (i, j),

and that μ is even (resp. odd), if its components are even (resp. odd). The integer k = ∑ μ_{i}, denoted by |μ|, is the degree of μ. We the have:

\xymatrix{L^{2}(G_{m,n}^{∘}) & = & ⨁_{μ admissible} H_{m,n}^{μ} \\ L^{2}(G_{m,n}) \ar@{^{(}->}[u] & = & ⨁_{μadmissible and even} H_{m,n}^{μ}}

Example: m = 1, μ = k, H_{1,n}^{k} = Harm_{k}[X_{1}, ⋯, X_{n}], the space of harmonic polynomials of degree k.

It is worth noticing that the H_{m,n}^{μ} do depend only on n and μ, that is to say, if m ≤ m′ and μ is a partition with at most m nonzero parts, then H_{m,n}^{μ} ≃ H_{m′,n}^{μ}.

To each irreducible constituent H_{m,n}^{μ} is attached a zonal function P_{μ} on G_{m,n}^{∘} × G_{m,n}^{∘}, characterized by:

1. P_{μ}(p, .) ∈ H_{m,n}^{μ} for all p ∈ G_{m,n}^{∘}, P_{μ}(., q) ∈ H_{m,n}^{μ} for all q ∈ G_{m,n}^{∘}

2. P_{μ}(σp, σq) = P_{μ}(p, q) for all σ ∈ O(n), (p, q) ∈ G_{m,n}^{∘}^{2}. If μ is even, one has

P_{μ}(p, q) = p_{μ}(y_{1}(p, q), ⋯, y_{m}(p, q)),

where p_{μ}(Y_{1}, ⋯, Y_{m}) is a symmetric polynomial of degree \frac{|μ|}{2}, whereas if μ is odd

P_{μ}(p, q) = (ϵt_{1} ⋯ t_{m})p_{μ}(y_{1}, ⋯, y_{m}),

with p_{μ}(Y_{1}, ⋯, Y_{m}) a symmetric polynomial of degree \frac{|μ|−m}{2}.

From now on, we normalize the zonal functions so as:

P_{μ}(p, p) = 1.

We then have the two following properties:

1. ⟨P_{μ}(p, .), P_{λ}(q, .)⟩ = \frac{δ_{λ,μ}}{d_{μ}} P_{μ}(p, q), where d_{μ} = dim H_{m,n}^{μ}.

2. P_{λ}P_{μ} = ∑_{τ} c_{λ,μ}(τ)P_{τ}, with c_{λ,μ}(τ) ≥ 0.

4. Designs.

For any integer k ≥ 1, we define

H_{k}^{+} := ⨁_{{|μ|≤k \atop μeven}} H_{m,n}^{μ} ⊂ L^{2}(G_{m,n}) ⊂ L^{2}(G_{m,n}^{∘})

and H_{k}^{−} := ⨁_{{|μ|≤k \atop μodd}} H_{m,n}^{μ} ⊂ L^{2}(G_{m,n})^{⊥} ⊂ L^{2}(G_{m,n}^{∘}).

Definition 4.1 ([2]). A subset D ⊂ G_{m,n} is a 2k-design if

∀φ ∈ H_{2k}^{+} , ∫_{G_{m,n}} φ(p)dp = \frac{1}{|D|} ∑_{p∈D} φ(p)

Notice that, since the definition is given in the setting of non oriented grassmannians, what we get for m = 1 is not exactly the definition of spherical designs, but more restrictively, the notion of antipodal design (see [5]).

There are several criteria to test whether a given subset of a Grassmannian space is a design. The first one involves the zonal functions P_{μ} mentioned above.

Proposition 4.2 ([2]). The following properties, for a subset D ⊂ G_{m,n}, are equivalent:

1. D is a 2k-design.

2. ∀μ with 2 ≤ |μ| ≤ 2k, ∑_{p∈D} P_{μ}(p, ·) = 0.

3. ∀μ with 2 ≤ |μ| ≤ 2k, ∑_{(p,q)∈D^{2}} P_{μ}(p, q) = 0.

In order to apply this proposition, one has to compute explicitly the polynomials P_{μ}. This is done in [9]. For m = 1, the P_{μ} are the classical Gegenbauer polynomials [5].

We also have criteria of a completely different kind, involving group theory. The orthogonal group O(n) acts on the set of n by n symmetric matrices SM_{n} by g.S = (g^{t})^{−1}Sg^{−1}, which in turn induces a representation of O(n) in Hom_{k}(SM_{n}), the space of homogeneous polynomials of degree k in the matrix argument S = (S_{i,j}) ∈ SM_{n}

g.P (S) := P (g^{−1}.S) = P (g^{t}Sg). (6)

We then have the following theorem:

Theorem 4.3 ([2]). Let G be a finite subgroup of O(n). Then, the following properties are equivalent:

1. ∀m ≤ \frac{n}{2}, ∀p ∈ G_{m,n}, G · p is a 2k-design.

2. Hom_{k}(SM_{n})^{G} = Hom_{k}(SM_{n})^{O(n)}.

This applies in particular when G = Aut L is the automorphism group of a lattice L. For instance, if L = 𝔻_{4}, 𝔼_{6} or 𝔼_{7}, theorem (4.3) applies with k = 2, if L = 𝔼_{8}, it applies with k = 3, and if L = Λ_{24} (the Leech lattice), with k = 5 (see [2]).

5. Rankin invariants.

Besides the classical Hermite function γ (= γ_{1} in what follows), which we mentioned in the introduction, Rankin [10] defined a collection of functions γ_{m}, in the following way : let L be a lattice in ℝ^{n}, endowed with the usual scalar product denoted x · y, and 1 ≤ m ≤ dim L an integer. One defines

δ_{m}(L) = inf_{p∈L(m)} det p, (7)

in which L(m) stands for the set of m-dimensional sublattices of L, and

γ_{m}(L) = δ_{m}(L)/(det L)^{\frac{m}{n}} (8)

For m = 1, γ_{1}(L) is the classical Hermite invariant of L. In general, the function γ_{m} is bounded on the set of n-dimensional positive definite lattices ([10]), and the supremum, which actually is a maximum, is denoted by γ_{m,n}. The lattices achieving a local maximum for γ_{m} are called m-extreme (see [4] for a characterization of m-extreme lattices in terms of m-perfection and m-eutaxy).

We define the set of minimal m-sections of L as

S_{m}(L) = {p ∈ L(m) | det p = δ_{m}(L)} (9)

which is a finite set. The map p ↦ ℝp (the m-dimensional subspace spanned by p) induces an embedding of S_{m}(L) in G_{m,n} (this is because ℝp/p is torsionfree, by the minimality of p). So, we can view S_{m}(L) as a subset of G_{m,n}. We then have the following theorem, analogous to Venkov’s theorem mentioned in the introduction:

Theorem 5.1 ([2]). S_{m}(L) is a 4-design ⇒ L is m-extreme.

The proof relies on the characterization of m-extreme lattices in terms of m-perfection and m-eutaxy mentioned above. This theorem, together with theorem 4.3, allows to check that some classical lattices are extreme with respect to all Rankin invariants:

Proposition 5.2. If L = 𝔻_{4}, 𝔼_{6}, 𝔼_{7}, 𝔼_{8} or Λ_{24}, then L is m-extreme for any m, 1 ≤ m ≤ \frac{dim L}{2}.

This kind of results would be out of reach without the help of theorem 4.3 and 5.1.

6. Codes in Grassmannian varieties. Bounds.

Definition 6.1 ([1]). Let f(Y_{1}, ⋯, Y_{m}) be a symmetric polynomial such that f(1, ⋯, 1) = 1.

A subset D ⊂ G_{m,n} is an f-code if for all (p, q) ∈ D^{2}, p ≠ q one has

f(y_{1}(p, q), ⋯, y_{m}(p, q)) = 0.

Remark. For m = 1, one recovers the usual definition of an s-code, i.e. a set of points on the sphere such that the mutual distances take at most s distinct values.

Let d_{k}^{+} = dim H_{k}^{+} and d_{k}^{−} = dim H_{k}^{−}. These dimensions can be easily calculated from the dimensions d_{n}^{μ} of the irreducible components H_{m,n}^{μ}, as given for instance in [6], chapter 24. They are involved in the following two theorems, which give bounds for the size of designs and codes in G_{m,n}.

Theorem 6.2 ([1]). Let D ⊂ G_{m,n} be a 2k-design. Then

|D| ≥ max(d_{k}^{+}, d_{k}^{−}).

If equality holds, then D is an f-code with respect to

f =\frac{1}{d_{k}^{+}} ∑_{{|μ|≤k \atop μ even}} d_{μ}p_{μ} or  \frac{y_{1} ⋯ y_{m}}{d_{k}^{−}} ∑_{{|μ|≤k \atop μ odd}} d_{μ}p_{μ}

(d_{k}^{+} > d_{k}^{−})  (d_{k}^{−} > d_{k}^{+})

Definition 6.3 ([1]). An f-code has type 1 if Y_{1} ⋯ Y_{m} divides f, type 0 otherwise.

Theorem 6.4 ([1]). Any f-code D ⊂ G_{m,n} satisfies

|D| ≤ d_{k}^{+},

where k = 2 deg f. If moreover f has type 1, then D ⊂ G_{m,n} satisfies

|D| ≤ d_{k}^{−},

where k = 2 deg f − m.

If equality holds, then

f = \frac{1}{d_{k}^{+}} ∑_{{|μ|≤k \atop μ even}} d_{μ}p_{μ} (type 0),

resp.

f = \frac{y_{1} ⋯ y_{m}}{d_{k}^{−}} ∑_{{|μ|≤k \atop μ odd}} d_{μ}p_{μ} (type 1)

and D is a 2k-design.

Designs, resp. codes, achieving the bound of theorem 6.2, resp. 6.4, are called tight.

Example. In [3], §5, an infinite family D_{p} of packings in G_{\frac{p−1}{2} ,p}, p a prime which is either 3 or congruent to −1 modulo 8, is defined. It consists on \frac{p(p+1)}{2} = d_{[0,··· ,0]} + d_{[2,0,··· ,0]} = d_{2}^{+} subspaces with same pairwise chordal

distance d^{2} = \frac{(p+1)^{2}}{4(p+2)}. Since d^{2} = ∑ sin^{2} θ_{i} = \frac{p−1}{2} − ∑ y_{i}, D_{p} is an f-code,

with f = ^{\frac{4(p+2)(∑ Y_{i})−(p^{2}−5)}{p^{2}−5}}, and theorem 6.4 applies, so that:

Proposition 6.5 ([1]). For any prime p which is either 3 or congruent to −1 modulo 8, D_{p} is a tight 4-design in G_{\frac{p−1}{2} ,p}.

References

[1] Bachoc, C., Bannai, E. and Coulangeon, R. Codes and designs in Grassmannian spaces, in preparation.

[2] Bachoc, C., Coulangeon, R and Nebe, G. Designs in Grassmannian spaces and lattices, to appear in J. Algebraic Combin.

[3] Calderbank, A. R., Hardin, R. H., Rains, E. M., Shor, P. W. and Sloane, N. J. A., A group-theoretic framework for the construction of packings in Grassmannian spaces, J. Algebraic Combin. 9 (1999), no. 2, 129–140.

[4] Coulangeon, R. Réseaux k-extrêmes, Proc. London Math. Soc. (3) 73 (1996), no. 3, 555-574.

[5] Delsarte, Ph., Goethals, J.M. and Seidel, J.J. Spherical codes and designs, Geom. Dedicata (6) (1977), 363-388.

[6] Fulton, W. and Harris, J. Representation Theory, a first course, GTM 129 Springer 1991

[7] Golub, G. H. and Van Loan, C. F. Matrix computations, John Hopkins Univ. Press, 2nd ed., 1989.

[8] Goodman, R. and Wallach, N. R. Representations and invariants of the classical groups, Encyclopedia of Mathematics and its Applications 68, Cambridge University Press, 1998.

[9] James, A.T. and Constantine, A.G. Generalized Jacobi polynomials as spherical functions of the Grassmann manifold, Proc. London Math. Soc. (3) 29 (1974), 174-192.

[10] Rankin, R. A. On positive definite quadratic forms, J. London Math. Soc. (28) (1953), 309–314.

[11] Venkov, B. Réseaux et designs sphériques, in Monographies de l’Enseignement Mathématique (37) (2001), 10–86.

R. Coulangeon, Laboratoire A2X, Université Bordeaux I, 351, cours de la Libération, 33405 Talence France

E-mail address: coulange@math.u-bordeaux.fr