On Euclidean Tight 4-Designs

Etsuko Bannai

Graduate School of Mathematics Kyushu University

Abstract

Euclidean designs is a concept defined by Neumaier and Seidel in 1988 which is a generalization of the concept of spherical designs. In this article we show a lemma proved by the author with Eiichi Bannai and give a classification of tight Euclidean 4-design having constant weight. We also talk about Gaussian designs and Optimal designs.

This article is based on my talk given at the 5-th Conference on Algebra and Computation held at Tokyo Metropolitan University in Octorber 2003. Also these are joint works with Eiichi Bannai.

First we give notations used in this article. In Section 1, we give some basic facts about Euclidean t-designs. In Section 2, we give the main theorem of this talk. In Section 3, we talk about Gausian designs and in Section 4, we talk about optimal designs.

Notation Let X be a finite subset in ℝ^{n}. Let w be a positive weight function defined on X.

• For x = (x_{1}, …, x_{n}), y = (y_{1}, …, y_{n}) ∈ ℝ^{n}, (x, y) = ∑_{i=1}^{n} x_{i}y_{i} and ∥x∥^{2} = (x, x).

• {r_{1}, …, r_{p}} = {∥x∥ | x ∈ X}.

• S_{i} = {x ∈ ℝ^{n} | ∥x∥ = r_{i}} for 1 ≤ i ≤ p.

• X_{i} = X ∩ S_{i} for 1 ≤ i ≤ p.

• S = ∪_{i=1}^{p}S_{i}=union of p concentric spheres supporting X.

(Also we say X is supported by p concentric spheres S_{1}, …, S_{p}. We consider the case when 0 ∈ X. Hence one of the spheres possibly satisfies S_{i} = {0}.)

• w(X_{i}) = ∑_{x∈X} w(x) for 1 ≤ i ≤ p.

• S^{n−1} = {x ∈ ℝ^{n} | ∥x∥ = 1}.

• σ and σ_{i} are Haar measures on S^{n−1} and S_{i} respectively.

• |S^{n−1}| = ∫_{S^{n−1}} dσ(ξ), |S_{i}| = ∫_{S_{i}} dσ_{i}(x) for 1 ≤ i ≤ p, where each σ_{i} is chosen so that dσ_{i}(x) = r_{i}^{n−1}dσ(ξ) holds for x = r_{i}ξ ∈ S_{i}, with ξ ∈ S^{n−1}.

• When r_{i} = 0, then \frac{1}{|S_{i}|} ∫_{S_{i}} f(x)dσ_{i}(x) = f(0) for any function f on ℝ^{n}.

• P(ℝ^{n}) = the vector space of all the polynimials in n variables, x_{1} …, x_{n}.

• Hom_{l}(ℝ^{n}) = subspace of P(ℝ^{n}) spanned by all the monomials of degree l.

• P_{e}(ℝ^{n}) = ⊕_{l=0}^{e}Hom_{l}(ℝ^{n})

• Δ = \frac{∂^{2}}{∂x_{1}^{2}} + ⋯ + \frac{∂^{2}}{∂x_{n}^{2}} = Laplacian of ℝ^{n}.

• Harm(ℝ^{n}) = {f ∈ P(ℝ^{n}) | Δf ≡ 0}.

• Harm_{l}(ℝ^{n}) = Harm(ℝ^{n}) ∩ Hom_{l}(ℝ^{n}).

• For a subset E ⊂ ℝ^{n}, P(E) = {f|_{E} | f ∈ P(ℝ^{n})}, Hom_{l}(E) = {f|_{E} | f ∈ Hom_{l}(ℝ^{n})}, etc..

1 Introduction

Definition 1.1 (Neumaier-Seidel(1988)) Let t be a natural number. Then a finite subset X in ℝ^{n} is a Euclidean t-design if the following condition holds:

∑_{i=1}^{p} \frac{w(X_{i})}{|S_{i}|} ∫_{S_{i}} f(x)dσ_{i}(x) = ∑_{x∈X} w(x)f(x)

for any polynomial f ∈ P_{t}(ℝ^{n}).

Remark: In the above definition if p = 1, r_{1} > 0 and w is constant on X, then X is similar to a spherical t-design defined by Delsarte, Goethals and Seidel in [6]

In the condition of the definition of Euclidean t-designs, the left hand side of the equation means averaging the values of polynomial f(x) on S = S_{1} ∪ ⋯ ∪ S_{p} by integration of f(x) on S. The right hand side means weighted average of the values of polynomial f(x) on X with the weight function w. Since we put the word “ Euclidean” to the definition, we want to define something representing or approximating whole Euclidean space ℝ^{n}. In Definition 1.1, if p is large enough then it is not so bad if we say S is approximating ℝ^{n}. Then the equality means when we are considering polynomials with degree at most t, it is not so bad if we say a Euclidean t-design X is approximating ℝ^{n}.

There are different approaches to approximate the whole space ℝ^{n}. In Section 3, we take the average of polynomials on ℝ^{n} using integration ∫_{ℝ^{n}} exp(−α∥x∥^{2})dx and define Gaussian designs. In Section 4 we consider optimal designs.

P. Seymour and T. Zaslavsky [17] proved that if the cardinality of the finite set is large enough Euclidean t-design always exists.

Following theorem gives an equivalent condition to the definition of the Euclidean tdesigns.

Theorem 1.2 ([14]) Let X ⊂ ℝ^{n} be a finite set. Then the following conditions are equivalent:

(1) X is a Euclidean t-design.

(2) For any integers l, j satisfying 1 ≤ l ≤ t, 0 ≤ j ≤ [\frac{t−l}{2}] and polynomials φ_{l} ∈ Harm_{l}(ℝ^{n}) the following equation hilds:

∑_{x∈X} w(x)∥x∥^{2j}φ_{l}(x) = 0.

Proof The following well known facts implies the Theorem 1.2:

• If l ≥ 1 and φ_{l} ∈ Harm_{l}(ℝ^{n}), then

∫_{S^{n−1}} φ_{l}(x)dσ(x) = 0.

• Hom_{l}(ℝ^{n}) = Harm_{l}(ℝ^{n}) ⊕ ∥x∥^{2}Harm_{l−2}(ℝ^{n}) ⊕ ⋯ ⊕ ∥x∥^{2[ \frac{l}{2} ]}Harm_{l−2[ \frac{l}{2} ]}(ℝ^{n}).

It is easy to see that Theorem 1.2 implies the following theorems. Theorem 1.3 Let X be a finite set in ℝ^{n}. Then X ∪{0} is a Euclidean t-design if and only if X is an Euclidean t-design. Proof It is obvious. Theorem 1.4 ( See [7], [14], [6]) Let X be a Euclidean 2e-design. Then |X| ≥ dim(P_{e}(S)) holds, where S is the union of p concentric spheres supporting X. Proof Let f ∈ P_{e}(ℝ^{n}). Assume f|_{X} = 0 in P_{e}(X). Then f^{2} ∈ P_{2e}(ℝ^{n}) and f^{2}|_{X} = 0 in P_{2e}(X). Since X is a 2e-design this implies ∫_{S_{i}} f(x)^{2}dσ_{i}(x) = 0 for i = 1, …, p. Then f|_{S} = 0 in P_{e}(S). This implies that the map f|_{S} ⟶ f|_{X} gives an isomorphism between P_{e}(S) and P_{e}(X). Since dim(P_{e}(X)) ≤ |X|, we have the assertion.

Remark In [7], Delsarte-Seidel gave precise formula of dim(P_{e}(S)) in terms of n, p, and e for S satisfying 0 ∉ S (Proposition 1.7 given below ). If X is a Euclidean (2e + 1)- design, then X is also a Euclidean 2e- design. Hence we have at least a lower bound for the cardinality of X. In [7], Delsarte-Seidel showed a better lower bound for the antipodal Euclidean (2e + 1)-designs. However if we do not assume X be antipodal, then there is no better bound known.

In this article we only consider only the case t = 2e.

Definition 1.5 (Tight 2e-designs on p concentric spheres) Let X be a Euclidean 2edesign supported by p concentric spheres. We call X a tight 2e-design on p concentric spheres if |X| = dim(P_{e}(S)) holds.

Definition 1.6 (Euclidean tight 2e-designs) Let X be a tight 2e-design on p concentric spheres. If |X| = dim(P_{e}(S)) = dim(P_{e}(ℝ^{n})) holds, then we say X is a tight Euclidean 2e-design.

Remark In above definitions we consider that if dim(P_{e}(S)) < dim(P_{e}(ℝ^{n})) holds, then it would not be appropriate to say union S of p concentric spheres approximates ℝ^{n}.

As for the dimensions of the polynomial spaces following proposition is well known (see [14], [7], [1]).

Proposition 1.7 Let S be a union of p concentric spheres centered at the origin. Let ε_{S} be defined by ε_{S} = 1 if 0 ∈ S and ε_{S} = 0 if 0 ∉ S. Then the following hold:

(1) dim(P_{e}(ℝ^{n})) = \binom{n+e}{e}.

(2) If p ≤ [\frac{e+ε_{S}}{2} ], then dim(P_{e}(S)) = ε_{S} + ∑_{i=0}^{2(p−ε_{S})−1} \binom{n+e−i−1}{e−i} < \binom{n+e}{e}.

(3) If p ≥ [\frac{e+ε_{S}}{2} ] + 1, then dim(P_{e}(S)) = dim(P_{e}(ℝ^{n})) = \binom{n+e}{e}.

2 Euclidean tight 4-designs

If the cardinality X is large, then Seymour-Zaslavsky proved that there always exist Euclidean t-designs for any t. However their theorem is not a constructive. Hence our interests goes to the question of concrete construction and also the classification of the smallest possible ones.

In this section we consider Euclidean 2e-designs and give some result we obtained in our paper [4]. When we consider a Euclidean tight 4-design X, Proposition 1.7 implies the number p of the spheres supporting X satisfies p ≥ 2. If we assume that the weight w is constant on X\{0}, then we obtained the following theorem.

Theorem 2.1 (B-B) ([4]) Let X be a Euclidean tight 4-design X in ℝ^{n}. Assume w is constant on X\{0}. Then p = 2, 0 ∈ X and X\{0} is similar to a spherical tight 4-design.

The following is one of the important lemmas to prove Theorem 2.1.

Lemma 2.2 (B-B) ([4]) Let X be a tight 2e-design on p concentric spheres. Then the following hold:

(1) The weight function w is constant on each X_{i}, 1 ≤ i ≤ p.

(2) Each X_{i} (1 ≤ i ≤ p) is at most an e -distance set.

(3) If w is constant on X\{0}, then p − ε_{S} ≤ e, where ε_{S} is defined in Proposition 1.7.

Lemma 2.2, Proposition 1.7, and Theorem 1.3 imply that a Euclidean tight 4-design X satisfies one of the following two conditions:

(1) 0 ∈ X and X\{0} is similar to a spherical tight 4-design.

(2) 0 ∉ X and X is supported by 2 concentric spheres.

If we proved that (2) is impossible, then we obtain Theorem 2.1.

Suppose (2) holds. Then Lemma 2.2 implies that X_{1} and X_{2} are at most 2-distance sets. Since |X| = \binom{n+2}{2}, At least one of them satisfies |X_{i}| ≥ \frac{|X|}{2} = n + 2, then |X_{i}| has to be a 2-distance set. When we prove Lemma 2.2 we obtain quadratic equations which determines the possible 2 distances explicitly. Then using the following theorem proved by Larman, Rogers and Seidel we introduce a contradiction. For n ≤ 6, we need to do case by case arguments to introduce contradictions.

Theorem 2.3 (Larman-Rogers-Seidel) Let X be a 2-distance set in ℝ^{n}. Let a, b be the distances between 2 distinct points in X. Assume |X| > 2n + 3. Then there exists an integer k ≥ 2 satisfying (\frac{a}{b})^{2} = \frac{k−1}{k}.

The following is an example of Euclidean tight 4-design in ℝ^{2} with non-constant weight.

Example X = X_{1} ∪ X_{2} ⊂ ℝ^{2}. X_{1} and X_{2} are regular triangles defined by X_{1} = \{ (1, 0), (−\frac{1}{2}, \frac{\sqrt{3}}{2}), (−\frac{1}{2}, −\frac{\sqrt{3}}{2}) \}, X_{2} = \{ (−r, 0), (\frac{r}{2}, \frac{\sqrt{3} r}{2}), (\frac{r}{2}, −\frac{\sqrt{3} r}{2}) \},

w(x) = \{ \begin{matrix}1  for x ∈ X_{1} \\ \frac{1}{r^{3}}  for x ∈ X_{2}. \end{matrix}

In above example, if r = 1, X is a 4-design on the unit circle. If r ≠ 1, then X is a Euclidean tight 4-design.

3 Gaussian t-designs

In the definition of Euclidean t-designs we consider that union S of concentric spheres centered at the origin to approximate ℝ^{n}. If the number of the spheres are large enough, then P_{e}(S) = P_{e}(ℝ^{n}) hold and at least considering polynomials of degree at most e we may consider that S is approximating ℝ^{n}. In this section instead of finite number of concentric sphere, we consider weighted integration defined on ℝ^{n}. Let α be a fixed positive real number. Let V (ℝ^{n}) = ∫_{ℝ^{n}} exp(−α∥x∥^{2})dx

Definition 3.1 ([2]) Let X be a finite subset in ℝ^{n}. Then X is a Gaussian t-design if the following condition holds:

\frac{1}{V (ℝ^{n})} ∫_{ℝ^{n}} f(x) exp(−α∥x∥^{2})dx = ∑_{x∈X} w(x)f(x)

for any f ∈ P_{t}(ℝ^{n}), where ∑_{x∈X} w(x) = 1.

Clearly Gaussian t-designs are among Euclidean t-designs. Hence a Gaussian 2e-design X satisfies inequality

|X| ≥ dim(P_{e}(ℝ^{n})) = \binom{n + e}{e}.

Gaussian 2e-design having \binom{n+e}{e} points are called a Gaussian tight 2e-design. Then we can prove the following lemma which is proved in [2].

Lemma 3.2 (B-B) Let X be a Gaussian tight 2e-design. Let p be the number of the concentric spheres supporting X. Then the following hold:

(1) p ≥ [\frac{e}{2}] + 1.

(2) w is constant on each X_{i} (1 ≤ i ≤ p).

(3) Each X_{i} (1 ≤ i ≤ p) is at most an e-distance set.

We also have the following theorem on Gaussian tight 4-deigns (see [2]).

Theorem 3.3 (B-B) (1) If 0 ∈ X, then X is a Gaussian tight 4-design if and only if X − \{0\} is a spherical tight 4-design on the sphere of radius \sqrt{\frac{n+2}{2α}} and the weight w is uniquely determined as follows:

w(u) = \{ \begin{matrix}\frac{2}{n+2} & for u = 0 \\ \frac{2}{(n+3)(n+2)} & for ||u|| = \sqrt{\frac{n+2}{2α}}. \end{matrix}

(2) If p = 2 and 0 ∉ X, then n = 2 and X equals the 6 points set

\{r_{1}(cos \frac{2lπ}{3} , sin \frac{2lπ}{3} ), −r_{2}(cos \frac{2lπ}{3} , sin \frac{2lπ}{3} ) | l = 0, 1, 2\}

up to orthogonal transformation of ℝ^{2}, where r_{1} = \frac{\sqrt{5}+1}{\sqrt{2α}} and r_{2} = \frac{\sqrt{5}−1}{\sqrt{2α}}. The weight function is given by

w(u) = \{ \begin{matrix}w_{1} = \frac{1}{6} − \frac{\sqrt{5}}{15} & for u ∈ X_{1} \\ w_{2} = \frac{1}{6} + \frac{\sqrt{5}}{15} & for u ∈ X_{2}. \end{matrix}

(Note that \frac{w_{1}}{w_{2}} = (\frac{r_{2}}{r_{1}} )^{3} holds.)

(3) There is no Gaussian tight 4-design with weight

w(u) = \frac{e^{−α||u||^{2}}}{∑_{x∈X} e^{−α||x||^{2}}} .

(4) There is no Gaussian tight 4-design with constant weight w = \frac{1}{|X|}.

In the proof of Theorem 3.3 also Theorem 2.3 by Larman-Rogers-Seidel played an important role.

4 Optimal designs

Optimal designs are defined in the study of statistics. Please refer [10], [11], [13], [15], [16] for more information. Let O(n) be the orthogonal group of ℝ^{n}. Let E be a subset in ℝ^{n} invariant under the action of O(n). A pair (E, ξ) is called a design if ξ is a mesure on E satisfying

∫_{E} dξ(x) = 1.

For polynomials f and g in P_{e}(E) define a inner product by

< f, g >_{ξ}= ∫_{E} f(x)g(x)dξ(x).

A design (E, ξ) is called of degree e if the inner product < −, − >_{ξ} is positive definite on P_{e}(ℝ^{n}). Let f_{1}, f_{2}, …, f_{m} be a fixed basis of P_{e}(ℝ^{n}). For each design (E, ξ) define an m × m matrix M_{ξ} by

M_{ξ} = (< f_{i}, f_{j} >_{ξ})_{1≤i, j≤m} .

M_{ξ} is called an information matrix of the design (E, ξ).

Definition 4.1 Let (E, μ) be a design of degree e. Then (E, μ) is an optimal design of degree e, if the following condition holds:

det(M_{μ}) ≥ det(M_{ξ}) for any design (E, ξ) of degree e.

The following are well known facts (see [15], [16], etc.):

• For any fixed E in ℝ^{n} and e, there exists an optimal design (E, μ) of degree e which is invariant under the action of the orthogonal group O(n) of ℝ^{n}, i.e., μ(τ(Y)) = μ(Y) holds for any subset Y ⊂ E and τ ∈ O(n).

• An O(n) invariant optimal design (E, μ) of degree e is supported by a union S of finitely many concentric spheres centered at the origin, i.e., μ(E\S) = 0.

Let (E, μ) be an O(n) invariant optimal design of degree e.

Definition 4.2 We say a finite set X ⊂ E represents (E, μ) if the following condition holds:

∫_{E} f(x)dμ(x) = ∑_{x∈X} w(x)f(x)

for any f ∈ P_{2e}(ℝ^{n}), where w is a positive weight function defined on X.

It is easy to see that if X represents an an O(n) invariant optimal design (E, μ) of degree e, then X is a Euclidean 2e-design.

Definition 4.3 A Euclidean 2e-design X is called optimal 2e-design on E, if X represents an O(n) invariant optimal design (E, μ) of degree e.

It is also easy to see that an optimal 2e-design X on E satisfies

|X| ≥ dim(P_{e}(E)).  (4.1)

We say X is an optimal tight 2e-design on E if the equality in (4.1) holds.

We studied optimal 4-design on a union S of 2 concentric spheres centered at the origin and obtained the following theorem [3].

Theorem 4.4 (B-B) (See [3]) Let S be a union of 2 concentric spheres centered at the origin. Let X be an optimal tight 4-design on S. Then 0 ∈ X and X\{0} is similar to a spherical tight 4-design and the weight function w is constant on X.

References

[1] E. Bannai and E. Bannai Algebraic combinatorics on spheres (in Japanese), Springer Tokyo 1999.

[2] E. Bannai and E. Bannai, Tight Gaussian 4-Designs, Journal of Algebraic Combinatorics, accepted for publication.

[3] E. Bannai and E. Bannai, On Optimal Tight 4-Designs on 2 Concentric Spheres, Europ. J. Combinatorics, accepted for publication.

[4] E. Bannai and E. Bannai, On Euclidean Tight 4-Designs, preprint.

[5] G. E. P. Box and J. S. Hunter, Multi-fuctor experimental designs for exploring response surfaces, Ann. Math. Statist. 28, (1957)195–241

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

[7] P. Delsarte and J. J. Seidel, Fisher type inequalities for Euclidean t-designs, Lin. Algebra and its Appl. 114-115 (1989) 213-230.

[8] S. J. Einhorn and I. J. Schoenberg, On Euclidean sets having only two distances between points I, Nederl. Akad. Wetensch. Proc. Ser. A 69=Indag. Math. 28 (1966) 479–488.

[9] A. Erdélyi et al. Higher transcendental Functions, Vol II, (Bateman Manuscript Project), MacGraw-Hill (1953).

[10] S. Karlin and W. J. Studden, Tchebycheff Systems with Application in Analysis and Statistics, Interscience, 1966.

[11] J. Kiefer, Optimum designs V, with applications to systematic and rotatable designs, Proc. 4th Berkeley Sympos. 1, (1960) 381–405.

[12] D. G. Larman, C. A. Rogers and J. J. Seidel, On two-distance sets in Euclidean space, Bull London Math. Soc. 9 (1977) 261-267.

[13] T. S. Lau, D-optimal designs on the unit q-ball, J. Statist. Plann. Inference 19 (1988), no. 3, 299-315.

[14] A. Neumaier and J. J. Seidel, Discrete measures for spherical designs, eutactic stars and lattices, Nederl. Akad. Wetensch. Proc. Ser. A 91=Indag. Math. 50 (1988) 321-334.

[15] A. Neumaier and J. J. Seidel, Measures of strength 2e and optimal designs of degree e, Sankya 54 (1991) 299-309.

[16] I. J. Schoenberg, On the maxima of certain Hankel determinants and the zeros of the classical orthogonal polynomials, Nederl. Akad. Wetensch. Proc. Ser. A 62 = Indag. Math. 21 (1959) 282–290.

[17] P. Seymour and T. Zaslavsky, Averaging sets: a generalization of mean values and spherical designs, Adv. in Math. 52 , no. 3, (1984)213-240.