Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 38 (1997), No. 2, 227-232.

Entropy, Capacity and Arrangements on the Cube

Walter Börner and Christian Richter

Friedrich-Schiller-Universität Jena Mathematisches Institut D-07740 Jena, Germany

Abstract. Capacity numbers of convex sets are characterized as a kind of packing numbers. After that entropy numbers and capacity numbers of the unit ball of l_{∞}^{d} are computed.

MSC 1991: 52C17

1. Introduction

Let (E, ∥ · ∥) be a (real) normed space and X ⊆ E a fixed bounded subset of E. The closed balls of radius r > 0 centered in x_{0} ∈ E are denoted by B(x_{0}, r). We need the following basic geometric concepts for explaining two kinds of entropy quantities (cf. [3], [2]) of X: A system C ⊆ 2^{E} of subsets of X is called a covering of X if X ⊆ ⋃ C. A packing in X is a system P ⊆ 2^{X} of subsets of X which are pairwise disjoint. By a ρ-distant subset in X, ρ > 0, we mean a subset D ⊆ X with ∥x − y∥ > 2ρ for all x, y ∈ D, x ≠ y.

The n-th entropy number of X, n ∈ {1, 2, 3, …}, is defined by

ε_{n}(X) = inf{ ε > 0 : there exists a covering of X
consisting of at most n balls of radius ε } .  (1)

The n-th capacity number (or inner entropy number) of X is given by

φ_{n}(X) = sup{ ρ > 0 : there exists a ρ-distant
subset of X of cardinality n + 1 }  (2)

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1997 Heldermann Verlag

228 Walter Börner and Christian Richter: Entropy, Capacity and Arrangements on the Cube

if card(X) ≥ n + 1, and by φ_{n}(X) = 0 if card(X) < n + 1. Of course, both concepts can be defined in the same way for bounded subsets of general metric spaces instead of (E, ∥ · ∥).

If the set X is convex we can give a characterization of φ_{n}(X) by special packings which is based on the close relation between ρ-distant subsets of X and packings in the so-called parallel set X + B(0, ρ) = { x + y : x ∈ X, y ∈ B(0, ρ) } of X.

Proposition 1. Let X be a convex subset of a normed space E, n a positive integer, and ρ > 0. Then the following are equivalent:

(i) There exists a ρ-distant subset D of X of cardinality n + 1. (ii) There exists a packing P in X + B(0, ρ) consisting of n + 1 balls of radius ρ.

Proof. The implication (i) ⇒ (ii) is simple to verify and does not make use of the convexity of X: Assume D = {x_{0}, x_{1}, …, x_{n}} to be a ρ-distant subset in X. We obtain the asserted packing by setting P = {B(x_{0}, ρ), B(x_{1}, ρ), …, B(x_{n}, ρ)}.

To prove (ii) ⇒ (i) we consider a packing P = {B(x_{0}, ρ), B(x_{1}, ρ), …, B(x_{n}, ρ)} in X + B(0, ρ). First we show that the centres x_{i}, i = 0, 1, …, n, belong to the closure \overline{X} of X. Assume the contrary x_{0} ∉ \overline{X}. Then x_{0} can be seperated from the closed convex set \overline{X} by a suitable functional f ∈ E′. Thus we obtain

⟨x_{0}, f⟩ > sup\{ ⟨x, f⟩ : x ∈ \overline{X} \} ,
⟨x_{0}, f⟩ + sup\{ ⟨y, f⟩ : y ∈ B(0, ρ) \} > sup\{ ⟨x, f⟩ : x ∈ \overline{X} \} +
sup{ ⟨y, f⟩ : y ∈ B(0, ρ) } ,
sup\{ ⟨x_{0} + y, f⟩ : y ∈ B(0, ρ) \} > sup\{ ⟨x + y, f⟩ : x ∈ \overline{X}, y ∈ B(0, ρ) \} ,
sup\{ ⟨z, f⟩ : z ∈ B(x_{0}, ρ) \} > sup\{ ⟨z, f⟩ : z ∈ \overline{X} + B(0, ρ) \}

in contradiction to B(x_{0}, ρ) ⊆ \overline{X} + B(0, ρ) since B(x_{0}, ρ) belongs to the packing P in X + B(0, ρ). Consequently, x_{0}, x_{1}, …, x_{n} ∈ \overline{X}.

We have ∥x_{i} − x_{j}∥ > 2ρ for all i, j ∈ {0, 1, …, n}, i ≠ j, since the balls B(x_{i}, ρ) are pairwise disjoint. So we can find an ε > 0 such that ∥x_{i}−x_{j}∥ > 2 (ρ+ε) for i, j ∈ {0, 1, …, n}, i ≠ j. Finally we choose points y_{i} from the non-empty sets X ∩ B(x_{i}, ε), i = 0, 1, …, n, and thus obtain

∥y_{i} − y_{j}∥ ≥ ∥x_{i} − x_{j}∥ − ∥y_{i} − x_{i}∥ − ∥y_{j} − x_{j}∥ > 2 (ρ + ε) − ε − ε = 2ρ

for i ≠ j which shows that D = {y_{0}, y_{1}, …, y_{n}} is a ρ-distant subset in X. □

Combining formula (2) and Proposition 1 we get the following characterization of the capacity numbers of X:

Theorem 1. Let X be a convex and bounded infinite subset of a normed space E and n a positive integer. Then

φ_{n}(X) = sup{ ρ > 0 : there exists a packing in X + B(0, ρ)
consisting of n + 1 balls of radius ρ } .  □

It can be shown by an example in the euclidean plane l_{2}^{2} that the supposition of convexity of X is not superfluous in Proposition 1 and Theorem 1.

The capacity numbers of a ball in E can be given not only as a kind of packing numbers in a parallel set as above but also as packing numbers in the ball itself:

Theorem 2. Let B(x_{0}, r) be a (closed) ball in a normed space E and n a positive integer. Then

φ_{n}(B(x_{0}, r)) = \frac{r μ_{n}(B(x_{0}, r))}{r − μ_{n}(B(x_{0}, r))}  with
μ_{n}(B(x_{0}, r)) = sup{ μ ∈ (0, r) : there exists a packing in B(x_{0}, r)

consisting of n + 1 balls of radius μ } .

Proof. We use Theorem 1. Considering B(x_{0}, r) + B(0, ρ) = B(x_{0}, r + ρ) we obtain

φ_{n}(B(x_{0}, r)) = sup{ ρ > 0 : there exists a packing in B(x_{0}, r + ρ)

consisting of n + 1 balls of radius ρ }

= sup{ ρ > 0 : there exists a packing in B(x_{0}, r)

consisting of n + 1 balls of radius \frac{r ρ}{r + ρ} \}

= sup\{ \frac{r μ}{r − μ} : there exists a packing in B(x_{0}, r)

consisting of n + 1 balls of radius μ ∈ (0, r) }

which shows the asserted equation since the function \frac{r μ}{r−μ} is monotonically increasing for μ ∈ (0, r). □

The simplest set X ⊆ E whose sequences (ε_{n}(X))_{n=1}^{∞} and (φ_{n}(X))_{n=1}^{∞} are of interest is the unit ball X = B(0, 1) of E. In [2] it is shown that

n^{− \frac{1}{d}} ≤ ε_{n}(B(0, 1)) ≤ 2 φ_{n}(B(0, 1)) ≤ 4 n^{− \frac{1}{d}}  if  dim(E) = d ,

but the exact calculation of entropy and capacity numbers of the unit ball is a nontrivial open problem. The goal of this paper is to give the solution for the space l_{∞}^{d}.

2. Entropy and capacity numbers of the cube

We consider the d-dimensional Banach space l_{∞}^{d} the unit ball X = B(0, 1) of which is the d-dimensional cube [−1, 1]^{d}. The following result on the sequences (ε_{n}(X))_{n=1}^{∞} and (φ_{(}X))_{n=1}^{∞} seems to be obvious because one expects intuitively that lattice-like arrangements are optimal on the cube. Nevertheless, an exact proof requires detailed considerations.

Theorem 3. Let X be the unit ball of the space l_{∞}^{d} and m a positive integer. Then

ε_{m^{d}}(X) = ε_{m^{d}+1}(X) = … = ε_{(m+1)^{d}−1}(X) = \frac{1}{m}

and

φ_{m^{d}}(X) = φ_{m^{d}+1}(X) = … = φ_{(m+1)^{d}−1}(X) = \frac{1}{m} .

Proof. For a fixed n ∈ {m^{d}, m^{d} + 1, …, (m + 1)^{d} − 1} we have

ε_{n}(X) = inf{ ε ∈ (0, 1] : there exists a covering of X
consisting of at most n balls of radius ε }  (3)

in accordance with formula (1) and

φ_{n}(X) = \frac{μ_{n}(X)}{1 − μ_{n}(X)}  with  (4)
μ_{n}(X) = sup{ μ ∈ (0, 1) : there exists a packing in X
consisting of at least n + 1 balls of radius μ }  (5)

according to Theorem 2. In the following H = [0, 2)^{d} denotes the half open ball of radius 1 centered in (1, 1, …, 1). The characterizations of ε_{n}(X) and φ_{n}(X) as an infimum or supremum, respectively, allow to replace all the balls in (3) and (5) by half open balls, i.e.

ε_{n}(X) = inf{ ε ∈ (0, 1] : there exists a covering of H consisting
of at most n balls from { x + εH : x ∈ ℝ^{d} } } ,  (6)
μ_{n}(X) = sup{ μ ∈ (0, 1) : there exists a packing in H consisting
of at least n + 1 balls from { x + μH : x ∈ ℝ^{d} } } .  (7)

The next step is to show that we can restrict our considerations in formulas (6) and (7) to lattice like arrangements on H. Therefore we make use of the arrangements L_{δ} = { x + δH : x ∈ 2δℤ^{d} } which form partitions of l_{∞}^{d} into half open balls of radius δ ∈ (0, 1]. We obtain coverings of H and packings in H by setting

C_{δ} = { M ∈ L_{δ} : M ∩ H ≠ ∅ } = { x + δH : x ∈ 2δℤ^{d} ∩ H } ,  (8)
P_{δ} = { M ∈ L_{δ} : M ⊆ H } = { x + δH : x ∈ 2δℤ^{d} ∩ [0, 2(1 − δ)]^{d} } .  (9)

The cardinalities of these arrangements are

card(C_{δ}) = card(2δℤ^{d} ∩ H) = card(ℤ^{d} ∩ \frac{1}{2δ} [0, 2)^{d})
= card((ℤ ∩ [0, \frac{1}{δ}) )^{d}) = (card(ℤ ∩ [1, \frac{1}{δ} + 1) ))^{d}

which means that

card(C_{δ}) = c_{δ}^{d}  with  c_{δ} ∈ ℤ ∩ [\frac{1}{δ}, \frac{1}{δ} + 1)  (10)

and

card(P_{δ}) = card(2δℤ^{d} ∩ [0, 2(1 − δ)]^{d}) = card(ℤ^{d} ∩ \frac{1}{2δ} [0, 2(1 − δ)]^{d})
= card((ℤ ∩ [0, \frac{1 − δ}{δ}] )^{d}) = (card(ℤ ∩ [1, \frac{1}{δ}] ))^{d}

showing that

card(P_{δ}) = p_{δ}^{d}  with  p_{δ} ∈ ℤ ∩ (\frac{1}{δ} − 1, \frac{1}{δ}] .  (11)

Now let us show that formula (6) can be rewritten as

ε_{n}(X) = inf{ ε ∈ (0, 1] : card(C_{ε}) ≤ n }  (12)

by verifying the following: Each covering C of H consisting of half open balls from { x + εH : x ∈ ℝ^{d} }, ε ∈ (0, 1], does not contain less balls than C_{ε}.

For showing this we map each ball x_{0} + εH from C_{ε} (i.e. x_{0} ∈ 2εℤ^{d} ∩ H due to (8)) onto one ball B_{0} from C which covers x_{0}. This mapping from C_{ε} into C is injective since two different points x_{0}, x_{1} ∈ 2εℤ^{d} ∩ H have a distance ∥x_{0} − x_{1}∥ ≥ 2ε and cannot be included in the same half open ball B_{0} ∈ C of radius ε. Consequently, card(C) ≥ card(C_{ε}).

Formula (7) can be sharpened to

μ_{n}(X) = sup{ μ ∈ (0, 1) : card(P_{μ}) ≥ n + 1 }  (13)

which is based on the fact that each packing P in H formed with half open balls from { x + μH : x ∈ ℝ^{d} }, μ ∈ (0, 1), does not contain more balls than P_{μ}:

P_{μ} covers [0, 2(1 − μ)]^{d} in accordance with formula (9). On the other hand for each ball x_{0} + μH ∈ P we have x_{0} ∈ [0, 2(1 − μ)]^{d} since x_{0} + μH ⊆ H. Therefore we can map each x_{0}+μH ∈ P onto that ball B_{0} ∈ P_{μ} which contains x_{0}. For two different x_{0}+μH, x_{1}+μH ∈ P we have ∥x_{0} − x_{1}∥ ≥ 2μ since x_{0} + μH and x_{1} + μH are disjoint. Thus x_{0} and x_{1} can not belong to the same half open ball B_{0} ∈ P_{μ}. Hence the mapping from P into P_{μ} defined above is injective which implies that card(P) ≤ card(P_{μ}).

Combining formulas (12) and (10) and remembering that n has been chosen from {m^{d}, m^{d} + 1, …, (m + 1)^{d} − 1} we obtain

ε_{n}(X) = inf\{ ε ∈ (0, 1] : c_{ε}^{d} ≤ n with c_{ε} ∈ ℤ ∩ [\frac{1}{ε}, \frac{1}{ε} + 1) \}
= inf\{ ε ∈ (0, 1] : c_{ε} ≤ m with c_{ε} ∈ ℤ ∩ [\frac{1}{ε}, \frac{1}{ε} + 1) \}
= inf\{ ε ∈ (0, 1] : \frac{1}{ε} ≤ m \}
= \frac{1}{m}

which proves the first part of Theorem 3. Similarly we make use of (13) and (11) and get

μ_{n}(X) = sup\{ μ ∈ (0, 1) : p_{μ}^{d} > n with p_{μ} ∈ ℤ ∩ (\frac{1}{μ} − 1, \frac{1}{μ}] \}
= sup\{ μ ∈ (0, 1) : p_{μ} ≥ m + 1 with p_{μ} ∈ ℤ ∩ (\frac{1}{μ} − 1, \frac{1}{μ}] \}
= sup\{ μ ∈ (0, 1) : \frac{1}{μ} ≥ m + 1 \}
= \frac{1}{m + 1}

which implies

φ_{n}(X) = \frac{1}{m}

according to (4). This completes the proof of Theorem 3. □

Let us remark that, of course, entropy numbers and capacity numbers of a set do not coincide in general. We see that the sequences (ε_{n}(X))_{n=1}^{∞} and (φ_{n}(X))_{n=1}^{∞} are strictly decreasing only in the one-dimensional case d = 1. In [1] it is shown that there exist convex polytopes P ⊆ l_{∞}^{d} which have a strictly decreasing sequence (ε_{n}(P))_{n=1}^{∞}.

The question for the sequence ε_{n}(S) of a given set S in a normed or, more general, in a metric space arises for instance in branches of approximation theory. Especially the jumps in the sequence are of interest (cf. [5], [4]). The proof of Theorem 3 is closely related to the geometry of the space l_{∞}^{d}. We encourage the reader to search for new results. Even the question for the exact values of entropy numbers and capacity numbers of balls in the euklidean space l_{2}^{d} is unsolved.

References

[1] Börner, W.: Simplexe mit streng monotoner Entropiezahlenfolge. Beiträge Algebra Geom. 32 (1991), 53–59.

[2] Carl, B.; Stephani, I.: Entropy, compactness and the approximation of operators. Cambridge Tracts in Mathematics 98, Cambridge University Press 1990.

[3] Kolmogoroff, A. N.; Tichomirow, W. M.: Arbeiten zur Informationstheorie III. Deutscher Verlag der Wissenschaften, Berlin 1960.

[4] Richter, Ch.: Entropy, approximation quantities and the asymptotic behaviour of the modulus of continuity (to appear).

[5] Stephani, I.: Entropy and the approximation of continuous functions. Arch. Math. 58 (1992), 280–287.

Received March 4, 1996