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

Finite Sphere Packings and Critical Radii

Dedicated to Edmund Hlawka at the occasion of his 80th birthday

K. Böröczky^{1} Jr. J. M. Wills

Math. Inst. Hung. Acad. Sci. Budapest Pf. 127, 1364 Hungary Math. Inst. Universität Siegen 57068 Siegen, Germany

Abstract. The parametric density permits a joint theory for classical packings and sausage packings of convex bodies, in particular spheres. If the parameter ϱ is small then linear packings (“sausages”) are optimal; if ϱ is large then full dimensional packings (“clusters”) are optimal and the packings tend to the classical densest infinite packing as the number of bodies tend to infinity. It was conjectured, namely, the Strong Sausage Conjecture, that for sphere packings no intermediate optimal packings exist, i.e. either the minimal or the maximal possible dimension of the packing configuration is attained. The proof of this conjecture would imply a proof of Kepler’s conjecture for infinite sphere packings, so even in E^{3} only partial results can be expected. The critical parameter depends on the dimension and on the number of spheres, so if the parameter ϱ is fixed then abrupt changes of the shape of the optimal packings (“sausage catastrophe”) occur as the number of spheres grows. In this paper, we give several partial results, in particular in E^{3}, which support the conjectures.

1. Introduction

Let B^{d} denote the unit ball in euclidean d-space E^{d}, d ≥ 2. For a convex body K ⊂ E^{d} let V (K) denote its volume, e.g. V (B^{d}) = κ_{d}. For a finite set C_{n} = {c_{1}…. , c_{n}} ⊂ E^{d} with ||c_{i} − c_{j}|| ≥ 2, i ≠ j we call C_{n} + B^{d} a finite sphere packing or briefly a packing. If L ⊂ E^{d} is a packing lattice for B^{d} and C_{n} ⊂ L, then C_{n} + B^{d} is called a lattice packing of spheres. For ϱ > 0 the parametric density of C_{n} + B^{d} is defined (cf. [8], [28]) by

1Research of the first named author is supported by the Magyary Zoltán Fund, by OTKA grant No. 14220 and by the Volkswagen Stiftung 0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1997 Heldermann Verlag

δ_{ϱ}(B^{d}, C_{n}) = \frac{nV (B^{d})}{V (conv C_{n} + ϱB^{d})},

where ‘+’ denotes the Minkowski sum. Further let

δ_{ϱ}(B^{d}, n) = max{δ_{ϱ}(B^{d}, C_{n})|C_{n} + B^{d} packing}.

The optimal C_{n} with δ_{ϱ}(B^{d}, C_{n}) = δ_{ϱ}(B^{d}, n) are denoted by C_{d,n,ϱ} or briefly by C_{n,ϱ}. Linear arrangements, i.e. with conv C_{n} being a segment, play an essential role in finite sphere packing. If conv C_{n} is a segment of length 2(n − 1), we write C_{n} = S_{n} and call S_{n} + B^{d} a sausage. Its density δ_{ϱ}(B^{d}, S_{n}) can easily be calculated and gives a good lower bound for δ_{ϱ}(B^{d}, n), as the following simple and basic result from [8] (Theorem 1a, slightly different notation) shows: For d ≥ 2 and n ≥ 3 there is a ϱ_{d,n} > 0 with

C_{n,ϱ} = S_{n} and δ_{ϱ}(B^{d}, n) = δ_{ϱ}(B^{d}, S_{n}) for 0 < ϱ ≤ ϱ_{d,n}
C_{n,ϱ} ≠ S_{n} and δ_{ϱ}(B^{d}, n) > δ_{ϱ}(B^{d}, S_{n}) for ϱ > ϱ_{d,n}.

If one restricts oneself to lattice packings, then one gets analogously δ_{L,ϱ}(B^{d}, n) and ϱ_{n,d}^{L}. The densities δ_{ϱ}(B^{d}, n), δ_{L,ϱ}(B^{d}, n) and the critical radii ϱ_{n,d} and ϱ_{n,d}^{L} are the essential functionals in finite sphere packings.

The classical sphere packing density is denoted by δ(B^{d}) and in the lattice case by δ_{L}(B^{d}). The density of an ‘infinite sausage’ is given by

δ_{s,ϱ}(B^{d}) = lim_{n→∞} δ_{ϱ}(B^{d}, S_{n}) = (κ_{d}/2κ_{d−1})ϱ^{1−d}.

Now we can define the relevant functionals for infinite parametric sphere packings:

δ_{ϱ}(B^{d}) = lim sup_{n→∞} δ_{ϱ}(B^{d}, n)

ϱ_{d,s} = sup{ϱ|δ_{ϱ}(B^{d}) = δ_{s,ϱ}(B^{d})}

ϱ_{d,c} = inf{ϱ|δ_{ϱ}(B^{d}) = δ(B^{d})}

and the corresponding functionals for lattice packings: δ_{L,ϱ}(B^{d}), ϱ_{d,s}^{L}, ϱ_{d,c}^{L}. Clearly

ϱ_{d,s} ≤ ϱ_{d,s}^{L} ≤ ϱ_{d,c}^{L} and ϱ_{d,s} ≤ ϱ_{d,c}.

For d = 2 Groemer [19] showed, in a different notation:

ϱ_{2,n} = ϱ_{2,n}^{L} = ϱ_{2,s} = ϱ_{2,s}^{L} = ϱ_{2,c} = ϱ_{2,c}^{L} =\sqrt{3}/2 for n ∈ N.

The situation for d ≥ 3 is much more complicated. In this paper some partial results on these critical radii for d ≥ 3 are given.

The following results from [8] show the close relation between critical radii and classical packing densities:

(κ_{d}/2κ_{d−1})(ϱ_{d,c})^{1−d} ≤ δ(B^{d}) ≤ (κ_{d}/2κ_{d−1})(ϱ_{d,s})^{1−d}

(κ_{d}/2κ_{d−1})(ϱ_{d,c}^{L})^{1−d} ≤ δ_{L}(B^{d}) ≤ (κ_{d}/2κ_{d−1})(ϱ_{d,s}^{L})^{1−d}.

In [8] it was conjectured

Strong Sausage Conjecture (SSC):

ϱ_{d,c} = ϱ_{d,s}  (1.1)

and

ϱ_{d,n} > ϱ_{d,s} for d ≥ 3, n ≥ 3;  (1.2)

and the corresponding

Strong Sausage Conjecture for lattice packings:

ϱ_{d,c}^{L} = ϱ_{d,s}^{L}  (1.3)

and

ϱ_{d,n}^{L} > ϱ_{d,s}^{L} for d ≥ 3, n ≥ 3.  (1.4)

These conjectures are closely related to L. Fejes Tóth’s sausage conjecture:

ϱ_{d,n} > 1 for d ≥ 5 and n ≥ 3

and the conjecture on sausage catastrophes [27], [18]:

ϱ_{3,n} > 1 for n < 56
ϱ_{4,n} > 1 for n < 375.000.

A proof of the SSC in E^{3} would also imply a proof of Kepler’s conjecture. So at the moment a general proof of the SSC or even the SSC for lattice packings seems to be out of reach. In this paper we give partial results on the SSC for lattice packings. The following three partial approaches are successful:

1. All n ∈ N and special lattice C_{n}. Our Theorems 1,2 and 3 are of this type.

2. Small n and arbitrary lattice C_{n}. Our Theorems 4, 5 and 6 are of this type. Results of this type for general packings are in [3].

3. d = 3, large n and arbitrary lattice C_{n}. Theorems of this type are in [1].

Final remarks:

1) If d ≥ 3 then there are even centrally symmetric convex bodies K, for which no analogue of SSC holds. This was first observed by Gritzmann [14] for d ≥ 4, cf. also [8]. In E^{3}, the regular octahedron is such an example (cf. [1]).

2) The problem of finding densest sphere packings, in particular for d = 3 and small n, occurs also for other packing densities, namely for the Lennard-Jones potential in crystal physics (cf. [22], [23]) and for the second moment density (“penny packings”, cf. [17], [26]). Their methods are completely different from ours: They use various effective computer programs, whereas for our parametric density the classical and powerful Brunn-Minkowski theory of convexity is available. Independently of the method chosen, the best packings for d = 3 and n ≤ 5 are the same for all of these densities; whereas they differ for large n.

2. Results

The first three results show that the SSC for lattice packings holds for special classes of lattice polytopes; and for all n ∈ N, not only for large n.

Theorem 1. The strong sausage conjecture for lattice packings (1.3), (1.4) holds for lattice zonotopes in E^{d}, d ≤ 48.

Remarks. 1.) The reason for the restriction d ≤ 48 is only because of limited information on δ_{L}. 2.) In the plane, any empty lattice triangle is one half of some fundamental parallelogram. It follows that Theorem 1 can be proved for a somewhat wider class of lattice polytopes Q_{n} = conv C_{n}, namely if Q_{n} = Z + P_{1} + … + P_{m}, m ≤ d/2, where Z is a lattice zonotope and P_{1}, …, P_{m} are planar lattice polygons so that aff P_{1}, …, aff P_{m} are independent.

The next classes of polytopes are rather small, but they contain the densest known lattice packings in E^{3}, besides sausage packings. Some definitions are needed. Let a, b, c be a basis of a lattice L ⊂ E^{3} such that the angles of any face of the tetrahedron conv{o, a, b, c} are ≤ π/2.

Let T = conv (O, a, b, c) be the lattice tetrahedron generated by a, b, c and the origin O. Any lattice polytope of L with all its facets (at most 8) parallel to one of the 4 facets of T is called a generalized lattice octahedron.

Theorem 2. The strong sausage conjecture for lattice packings (1.3),(1.4) holds for generalized lattice octahedra.

For the next result we only consider the critical lattice or fcc-lattice L′ ⊂ E^{3} (cf. [13], [17]), which generates the densest lattice packing of spheres in E^{3}. Let Q be the convex hull of the 12 lattice points of L′ with distance 2 from the origin. Q is the regular cuboctahedron of edge-length 2. It is centrally symmetric and has 14 facets, namely 6 squares and 8 regular triangles. Any lattice polytope of L′ with all its facets (at most 14) parallel to one of the 14 facets of Q is called a generalized L′-cuboctahedron. Observe that each cube, each regular simplex and each regular octahedron of L′ is a generalized L′-cuboctahedron.

Theorem 3. The strong sausage conjecture for lattice packings (1.3),(1.4) holds for generalized L′-cuboctahedra.

Remark. From the proof follows that Theorem 3 also holds for lattices which are close to L′ (in the sense of Mahler).

The next 3 results deal with small n. T^{d} means the regular d-simplex.

Theorem 4. For d ≥ 3, n = 4 and ϱ > ϱ_{d,4}^{L} holds conv C_{d,4,ϱ} = T^{3}.

Corollary 1. The equality ϱ_{d,4}^{L} = 0.6814 …\sqrt{d} holds for large d.

Theorem 5. For d = 3, n = 5 and ϱ > ϱ_{3,5}^{L} holds conv C_{3,5,ϱ} = N, where N is the pyramid over the square, with all edges of length 2.

Denote by D_{5} the bipyramid over the regular triangle having edge-length 2. As V (D) = V (N) and V_{i}(D_{5}) < V_{i}(N) for i = 1, 2, we deduce a significant difference between lattice and nonlattice packings:

Corollary 2. For ϱ > ϱ_{3,5}^{L}, the optimal packing is D_{5}, i.e. not a lattice packing.

Finally, we present a result supporting the sausage catastrophe. Note that ϱ_{d,4}^{L} ∼ 0.6814d^{1/2} and (see [21])

lim inf_{n→∞} ϱ_{d,n} ≤ \frac{\sqrt{21}}{2} = 2.2912.

Theorem 6. 1. V (T^{d} + ϱB^{d}) < V (S_{n} + ϱB^{d}) holds if ϱ > 0.6d^{1/2}.

2. For large d, V (T^{d} + ϱB^{d}) > V (S_{n} + ϱB^{d}) holds if ϱ < d^{1/2−o(1)}.

3. Proof of Theorem 1

For the proofs, we need some classical definitions which can be found e.g. in [13], [15], or in [25]. We mention them briefly, in order to keep the paper self-contained.

Let K be a convex, compact set in E^{d}. The intrinsic i-volume V_{i}(K) of K can be defined via Steiner’s formula:

V (K + ϱB^{d}) = ∑_{i=0}^{d} κ_{i}V_{d−i}(K) ϱ^{i}  (3.5)

where κ_{i} is the volume of the unit i-ball. Here V_{d}(K) = V (K), 2V_{d−1}(K) is the surface-area S(K) of K and V_{0}(K) = 1. In addition, \frac{2κ_{d−1}}{dκ_{d}} V_{1}(K) is the mean width of K. The intrinsic volumes are continuous, monotone and dimension invariant valuations.

Let P be a convex d-polytope, and denote by F_{i} the set of i-faces of it. For an F ∈ F_{i}, α(F, P) is the interior angle at F and β(F, P) is the exterior angle, normalized so that the total angle is one. We set β(P, P) = 1. Then V_{i}(P) can be calculated by

V_{i}(P) = ∑_{F ∈F_{i}} β(F, P) |F |,  (3.6)

where |F | denotes the relative volume in the affine hull.

Let Λ be a packing lattice. The weighted lattice point enumerator of a lattice polytope P (see [6] or [15]) is defined as

Ĝ_{Λ}(P) = ∑_{x∈Λ∩P} α(x, P).

Note that there exists a corresponding simple valuation which is Ĝ_{Λ}(P) for d-polytopes and zero otherwise. The number of lattice points in P satisfies the relation (see [6])

G_{Λ}(P) = ∑_{i=0}^{d} ∑_{F ∈F_{i}} β(F, P) Ĝ_{Λ}(F)  (3.7)

where α(x, P) = 1 if x ∈ intP. Comparing (3.6) and (3.7) shows that in order to establish a formula of the type

∑_{i=0}^{d} λ_{i}V_{i}(P) ≥ G_{Λ}(P)

for non-negative λ_{0}, …, λ_{d}, it is sufficient to prove that

λ_{i}|F | ≥ Ĝ_{Λ}(F)  (3.8)

holds for any i-face F of P.

Now let ϱ > 0 and C_{n} ⊂ Λ. We deduce from (3.8) and Steiner’s formula that V (convC_{n} + ϱB^{d}) > V (convS_{n} + ϱB^{d}) holds if

\frac{κ_{d−i}}{ϱ^{i−1}2κ_{d−1}} |F | > Ĝ_{Λ}(F).  (3.9)

for any i-face F of convC_{n}.

So we assume that convC_{n} is a lattice zonotope which can be dissected into lattice parallelotopes. For any lattice parallelotope P (see [6])

|P | = det(aff P ∩ Λ) · Ĝ_{Λ}(P)  (3.10)

holds. Let Λ_{d} be a densest packing lattice for B^{d} (i.e. a critical lattice) and define

ϱ(d, i) = ^{i−1} \sqrt{\frac{κ_{d−i}}{2κ_{d−1}} det Λ_{i}} = ^{i−1} \sqrt{\frac{κ_{d−i}κ_{i}}{2κ_{d−1}δ_{L}(B^{i})}}, i = 2, …, d.

We deduce from (3.10) that (3.9) holds if ϱ < ϱ(d, i).

We claim that

ϱ(d, i) > ϱ(d, d)  (3.11)

for i = 2, …, d − 1 implies Theorem 1. So we assume that (3.11) holds. Then we deduce by (3.9) that V (convC_{n} + ϱB^{d}) > V (convS_{n} + ϱB^{d}) for ϱ < ϱ(d, d), which in turn yields that

δ(C_{n}, ϱ(d, d)) ≤ δ(S_{n}, ϱ(d, d))

where δ_{ϱ}(·) is denoted by δ(·, ϱ) in order to avoid too complicated indices. Since

lim_{n→∞} δ(S_{n}, ϱ(d, d)) = δ_{L}(B^{d}),

one obtains that (3.11) yields Theorem 1. In the following lemmas, we verify (3.11) for various cases.

Lemma 1. 1. ϱ(d + 1, i) ≥ ϱ(d, i) holds if d ≥ i ≥ 2.

2. ϱ(d, i) > 1 holds if d > i.

Proof. The first property follows as κ_{k}/κ_{k+1} is monotonely increasing (see [7]). Therefore it is sufficient to check the second property for d = i + 1, when

ϱ(i + 1, i) = ^{i−1} \sqrt{\frac{1}{δ_{L}(B^{i})}} > 1. □

Lemma 2. (3.11) holds if i = d − 3, d − 2, d − 1 or if i = d − 4 and i ≥ 7.

Proof. By Lemma 1, it is sufficient to prove that for i = d − 4, …, d − 1, the inequality

det Λ_{d} < κ_{d−i} · det Λ_{i}  (3.12)

holds.

According to a result of Blichfeldt (see [24], p.79, Lemma 1), the covering radius of Λ_{i} is at least \sqrt{2i/(i + 1)}, and hence constructing suitable (i + 1)-lattice shows that

det Λ_{i+1} ≤ \sqrt{\frac{2(i + 2)}{i + 1}} · det Λ_{i}.

In particular,

det Λ_{d} ≤ \sqrt{\frac{d + 1}{i + 1}} · \sqrt{2}^{d−i} · det Λ_{i}.

Finally, for k = 1, 2, 3 and for k = 4 and d ≥ 11, the inequality

κ_{k} > \sqrt{\frac{d + 1}{d + 1 − k}} · \sqrt{2}^{k}

yields (3.12). □

Table 1 collects upper bounds ϱ^{∗}(d, d) for ϱ(d, d). For these upper bounds, we use the list of good packing lattices in [10].

d ϱ^{∗}(d, d) d ϱ^{∗}(d, d) d ϱ^{∗}(d, d) d ϱ^{∗}(d, d)
2 0.8660 14 1.2329 26 1.3129 38 1.4703
3 0.9488 15 1.2335 27 1.3431 39 1.4768
4 0.9847 16 1.2249 28 1.3653 40 1.4706
5 1.0347 17 1.2465 29 1.3872 41 1.4780
6 1.0564 18 1.2574 30 1.3954 42 1.4803
7 1.0755 19 1.2650 31 1.3884 43 1.4808
8 1.0781 20 1.2640 32 1.3761 44 1.4767
9 1.1367 21 1.2647 33 1.4397 45 1.4732
10 1.1626 22 1.2580 34 1.4541 46 1.4655
11 1.1231 23 1.2500 35 1.4659 47 1.4567
12 1.1354 24 1.2361 36 1.4716 48 1.4443
13 1.2179 25 1.2788

Table 1

On the other hand, the known values of det Λ_{i}, i = 2, …, 6 yield that ϱ(6, 2) = 1.6237, ϱ(7, 3) = 1.6434, ϱ(8, 4) = 1.6105, ϱ(9, 5) = 1.6194, ϱ(10, 6) = 1.5963. In addition, we deduce by Blichfeldt’s bound (see [11] or [13])

det Λ_{d} ≥ \frac{2 κ_{d}}{d + 2}\sqrt{2}^{d}

and by κ_{5} = 8π^{2}/15 that

ϱ(d, d − 5) > ^{d−6} \sqrt{\frac{\sqrt{2}^{d−5}κ_{5}κ_{d−5}}{(d − 3)κ_{d−1}}} = \sqrt{2} ^{d−6} \sqrt{\frac{2\sqrt{2}(d − 1)}{15}}.

Since the function (t + 5)^{1/t} is monotonely decreasing for positive t, it follows that

ϱ(d, d − 5) > ^{42} \sqrt{\frac{2\sqrt{2} · 47}{15}} = 1.4896 …

for d ≤ 48.

Each entry of Table 1 is smaller than ϱ(i, i+4) for i = 2, …, 6 or ϱ(i, i+5) for i = 7, …, 43. Hence (3.11) follows by Lemma 1 and Lemma 2, which in turn yields Theorem 1.

Remark. Using Stirling’s estimate for the Gamma function and Blichfeldt’s lower and Minkowski’s upper bound (see [11] or [13]) for det Λ_{d}, it is not hard to establish that ϱ(d, i) > ϱ(d, d) if i ≤ d/2. On the other hand, these bounds are not good enough to yield that Theorem 1 holds in general.

Actually, (3.11) is a necessary condition for the SSC for lattice packings, so these relations for ϱ(d, i) support the general statement as well.

4. Proof of Theorem 2

A dissection or tiling of a set S ⊂ E^{d} by sets S_{i}, i = 1, …, m means:

S = ⋃_{i=1}^{m} S_{i} and int (S_{i} ∩ S_{j}) = ∅ for i ≠ j.

Let C_{n} + B^{d} and ϱ > 0 be given. Further let P_{1}, …, P_{m} be a tiling of E^{d}. This tiling induces a tiling P′_{1}, …, P′_{m} on C_{n} + B^{d} and a tiling P′′_{1}, …, P′′_{m} on conv C_{n} + ϱB^{d}. For simplicity we always assume that the P_{i} and hence the P′_{i}, P′′_{i} are in the convex ring, i.e. unions of finitely many convex bodies.

Let V (P′_{i}) = v′_{i}, V (P′′_{i}) = v′′_{i} and Θ_{i} = v′_{i}/v′′_{i}, i = 1, …, m. Then δ_{ϱ}(B^{d}, C_{n}) = (∑_{i=1}^{m} v′_{i}) / (∑_{i=1}^{m} v′′_{i}) = (∑_{i=1}^{m} Θ_{i} v′′_{i}) / (∑_{i=1}^{m} v′′_{i}). We further assume that the tilings always contain the outer normal cones of the vertices of conv C_{n} as tiles. We call these tiles vertex tiles. For vertex tiles holds Θ_{i} = ϱ^{−d}. These tilings just described we call appropriate tilings, and we get the simple but useful

Lemma 3. Let C_{n} + B^{d} a packing, ϱ > 0 and P′_{1}, …, P′_{m} and P′′_{1}, …, P′′_{m} appropriate tilings of C_{n} + B^{d} and conv C_{n} + ϱB^{d}. Further let the inequality Θ_{i} ≤ (κ_{d}/2κ_{d−1})ϱ^{1−d} hold for all tiles except the vertex tiles, with strict inequality for at least one i. Then

δ_{ϱ}(B^{d}, C_{n}) < δ_{ϱ}(B^{d}, S_{n}).

Proof. We have V (conv C_{n} + ϱ B^{d}) = ∑_{i}^{1} v′′_{i} + ∑_{i}^{2} v′′_{i}, where ∑_{i}^{2} contains exactly the vertex tiles. Hence ∑_{i}^{2} v′′_{i} = V (ϱ B^{d}) = κ_{d} ϱ^{d} and V (conv C_{n} + ϱB^{d}) − κ_{d} ϱ^{d} = ∑_{i}^{1} v′′_{i} = ∑_{i}^{1} v′_{i}/Θ_{i} and

∑_{i}^{1} v′_{i} = (n − 1)κ_{d}.  (4.13)

We now consider the sausage packing S_{n} + B^{d} and the appropriate tiling induced by the n hyperplanes orthogonal to conv S_{n} and containing one of the sphere centers c_{i}. If we denote the tiles and densities by v̂_{j}, Θ̂_{j}, then Θ̂_{j} = Θ_{j} = (κ_{d}/2κ_{d−1}) ϱ^{1−d}, and

V (conv S_{n} + ϱ B^{d}) − κ_{d} ϱ^{d} = ∑_{j}^{1} v̂′_{j}/Θ̂_{j} = (2κ_{d−1}/κ_{d})ϱ^{d−1} ∑_{j}^{1} v̂′_{j} = 2(n − 1)κ_{d−1} ϱ^{d−1}.

So V (conv S_{n} + ϱ B^{d}) − V (conv C_{n} + ϱ B^{d}) = 2(n − 1)κ_{d−1} ϱ^{d−1} − ∑_{i} v′_{i}/Θ_{i}. By assumption Θ_{i} ≤ (κ_{d}/2κ_{d−1}) ϱ^{1−d}, and for at least one i with <, so we get with (4.13)

V (conv S_{n} + ϱ B^{d}) − V (conv C_{n} + ϱ B^{d}) < 2(n − 1)κ_{d−1} ϱ^{d−1} (1 − ((n − 1)κ_{d})^{−1} ∑_{i}^{1} v′_{i}) = 0. □

With Lemma 3 we are ready for the

Proof of Theorem 2. Let L ⊂ E^{3} be a packing lattice and let a, b, c be a basis of L such that the four heights h_{0}, h_{a}, h_{b}, h_{c} of the simplex T = conv (0, a, b, c) are all ≥ 1. This is the case if e.g. all angles at the facets of T are ≤ π/2, and hence for each packing lattice such bases exist.

Without restriction we assume 1 ≤ h_{0} ≤ h_{a} ≤ h_{b} ≤ h_{c}, because otherwise we rearrange 0, a, b, c without changing L and T.

The corresponding facets of T are

f_{0} = conv (a, b, c), f_{a} = conv (0, b, c), f_{b} = conv (0, a, c), f_{c} = conv (0, a, b).

For simplicity we use the same letters also for the 2-dimensional volumes and so we have

f_{0} ≥ f_{a} ≥ f_{b} ≥ f_{c}.

Now let Q ⊂ E^{3} be a generalized lattice-octahedron of L with respect to T. The facets parallel to f_{0} are denoted by F_{0}, F′_{0}; similarly for F_{a}, F′_{a}, F_{b}, F′_{b}, F_{c}, F′_{c}. Some of these facets may be empty. Then the tiling is constructed as follows:

From T one gets the corresponding fundamental cell Z of L with V (Z) = det L = 6V (T). The parallelotope Z can be dissected into 3 tiles as follows:

T, a translate of T′ = −T and the remaining octahedron O′ with V (O′) = 4V (T). The translates Z_{i} of Z and their dissections into translates T_{i} of T, T′_{i} of T′ and O′_{i} of O′ induce a tiling of E^{3}.

Easy considerations show that this tiling of E^{3} induces also a tiling of Q, and this tiling has the nice property that the Z_{i} can be dissected at most by F_{0}, F′_{0}, but not by F_{a}, F′_{a}, F_{b}, F′_{b}, F_{c}, F′_{c}, because these facets are parallel to those of the Z_{i}.

In the following, it turns out that the proof is simple if the facets F_{0}, F′_{0} do not exist. The tiling of Q induces a tiling on the facets of Q into triangles congruent to f_{0}, f_{a}, f_{b}, f_{c}

and hence a tiling on Q + ϱ_{c} B^{d} into the tiles in Q and triangular prisms of height ϱ_{c} over the facets, denoted by P_{0,i}, P_{a,i}, P_{b,i}, P_{c,i}, further cylindrical tiles at the edges and vertex tiles at the vertices.

From Lemma 3 follows that the vertices need not be considered. The density of the cylindrical tiles is δ_{L}^{3}, the same holds for any cell Z_{i}; hence these tiles need not be considered.

All triangular prisms over the facets of Q have height ϱ_{c} = 2^{2/3}π^{−1/2} and density at most (π/(3\sqrt{2}))^{3} = (δ_{L}^{3})^{3} < δ_{L}^{3}. These prisms will be needed to compensate the critical tiles of possibly high density, namely

tetrahedra T_{i} or T′_{i} or octahedra O′_{i} having one triangle in a facet F_{0} or F′_{0} of Q. These triangles are either translates of f_{0} or of −f_{0} = f′_{0}, and we denote them by f_{0,i} and f′_{0,i}. If we join these triangles in pairs along their common edge parallel to the edge \overline{b_{c}}, then we get a tiling of aff F_{0} and aff F′_{0} into parallelograms.

In the following we consider only F_{0}, because everything holds also for F′_{0}. Each parallelogram in F_{0} is incident with one tetrahedron and one octahedron. Here it suffices to consider one half of the octahedron, because the other half either coincides with another tetrahedron and hence is a tile with density ≤ δ_{L}^{3} or has one triangular face in F′_{0} and is considered in F′_{0}.

So each parallelogram in F_{0} incident with one tetrahedron and one half of an octahedron is a tile of density ≤ δ_{L}^{3}.

The remaining triangles of F_{0}, which cannot be completed to a parallelogram, have the property that their edge parallel to \overline{b_{c}} is contained in one of the two edges E_{1}, E_{2} of F_{0} parallel to \overline{b_{c}}, and belonging to F_{a} or F′_{a} (E_{1}, E_{2} may be empty).

Let m_{1} be the number of these triangles in E_{1}, m_{2} in E_{2}, and without restriction let m_{1} ≥ m_{2}. Then m_{2} pairs of triangles belong again to pairs of tetrahedra and half octahedra and give new tiles of density ≤ δ_{L}^{3}.

The remaining m = m_{1} − m_{2} cannot be completed to parallelograms. They are incident to m tetrahedra or m half octahedra and we associate to them 4 m prisms as follows:

a) m prisms over these m triangles in F_{0} with 2-volume f_{0}.

b) m − 1 prisms over triangles in F_{0}, which are adjacent to just 2 of the triangles in a). They also have 2-volume f_{0}.

c) m prisms over triangles in F_{a} (or F′_{a}) having a common edge with one of the m triangles in a). They have 2-volume f_{a}.

d) At least m + 1 prisms over triangles in F_{a}, F_{b}, F_{c} which have one edge in F_{0}. At least one of these triangles has 2-volume f_{b} and at least one: f_{c}.

Now the volume of these at least 4m prisms is at least:

((2m − 1)f_{0} + mf_{a} + f_{b} + mf_{c})ϱ_{c} ≥ m(f_{0} + f_{a} + f_{b} + f_{c})ϱ_{c}

by (4.13). So each of the m tetrahedra or half octahedra can be associated to 4 prisms of volume f_{0}ϱ_{c}, f_{a}ϱ_{c}, f_{b}ϱ_{c} and f_{c}ϱ_{c} and for these new tiles T_{j} it is to show δ(T_{j}) < δ_{L}^{3}.

This is equivalent to showing that in the tetrahedral case

δ_{ϱ_{c}}(B^{3}, T) < δ_{ϱ_{c}}(B^{3}, convS_{4})  (4.14)

or, for the octahedron

δ_{ϱ_{c}}(B^{3}, O′) < δ_{ϱ_{c}}(B^{3}, convS_{6}).  (4.15)

But we know from Theorem 5 that δ_{1}(B^{3}, T) < δ_{1}(B^{3}, convS_{4}) and from [4] that δ_{1}(B^{3}, O′) < δ_{1}(B^{3}, convS_{6}).

So (4.14) and (4.15) hold a fortiori and we have for these tiles that their density is < δ_{L}^{3}. Finally, we conclude that we have a tiling of Q+ϱ_{c}B^{3}, such that for all tiles except the vertex tiles the density is ≤ δ_{L}^{3} and in at least one case we have < δ_{L}^{3}. This proves Theorem 2.

5. Proof of Theorem 3

This proof is simpler than that of Theorem 2, because we consider only the critical lattice. Again we use Lemma 3 and construct an appropriate tiling.

Let L ⊂ E^{3} be the critical lattice and let a, b, c be a reduced basis of L such that a, b, c have length 2 and mutual angles π/3. The basis a, b, c generates a basic cell Z of L with V (Z) = det L and a tiling of E^{3} by translates Z_{i} of Z. Each Z_{i} can be dissected in the obvious way into two regular simplices S_{i,1}, S_{i,2} of volume \frac{1}{6} det L and a regular octahedron O_{i} of volume \frac{2}{3} det L.

Now let Q be a generalized octahedron. The facets of Q induce a dissection of Z_{i} and hence a tiling of Q. We classify those parts of Z_{i} which tile Q.

Easy considerations show that no simplex S_{i1}, S_{i2} can be dissected. An octahedron O_{i} can be dissected by any of the planes which meet 4 of its 6 vertices. But at most 2 of them can dissect one octahedron simultaneously, because otherwise its center c is a vertex of the lattice polytope Q, which contradicts the fact that int O_{i} contains no lattice point. So Q can be dissected into two types of tiles, both tetrahedra of volume \frac{1}{6} det L = \frac{2}{3} \sqrt{2}:

a) T_{1}: regular tetrahedra of edge-length 2;

b) T_{2}: distorted tetrahedra, a quarter of an O_{i}.

This dissection induces a dissection of the boundary region (Q + ϱ_{c}B^{d})\Q into two types of orthogonal prisms of height ϱ_{c}:

c) P_{1} prisms with a regular triangle as base and volume \sqrt{3}ϱ_{c},

d) P_{2} prisms with an orthogonal triangle as base and volume 2ϱ_{c},

e) C_{i}: cylindrical pieces, generated by the outer normals of Q at its edges and of radius ϱ_{c},

f) vertex tiles. We now have an appropriate tiling and we are ready to calculate the densities Θ_{i} as for Theorem 2: For the vertex tiles, which need not be considered by Lemma 1, again Θ_{i} = (ϱ_{3,c}^{L})^{−3} > δ_{L}^{3}. Further, for C_{i}

Θ_{i} = (κ_{3}/2κ_{2}) (ϱ_{3,c}^{L})^{−2} = δ_{L}^{3}

holds. For the other Θ_{i}, we have to investigate Θ(T_{1}), Θ(T_{2}), Θ(P_{1}), Θ(P_{2}). For T_{1} we have the well-known Rogers bound Θ_{i} = σ_{3} > δ_{L}^{3}. For T_{2} one has Θ(T_{2}) = Θ(O_{i}) and \frac{1}{3}Θ(T_{1}) + \frac{2}{3}Θ(T_{2}) = δ_{L}^{3}, so Θ(T_{2}) = Θ(O_{i}) = τ_{3} = 0, 7208 < δ_{L}^{3}.

Further

Θ(P_{1}) = \frac{1}{4}κ_{3}(V (P_{1})ϱ_{c})^{−1} = π(3\sqrt{3}ϱ_{c})^{−1} < δ_{L}^{3}

and

Θ(P_{2}) = \frac{1}{4}κ_{3}(V (P_{2})ϱ_{c})^{−1} = π(6ϱ_{c})^{−1} < δ_{L}^{3}.

So the only critical case is T_{1}. The crucial idea to overcome this difficulty is to put each T_{1} together with some other tiles such that the new tile has density Θ ≤ δ_{L}^{3}.

For each T_{1} at least one of the following combinations as a new tile T′ are possible:

1. T_{1} and one half of an octahedron of the same Z_{i}.

Then Θ(T′) = \frac{1}{3}Θ(T_{1}) + \frac{2}{3}Θ(T_{2}) = δ_{L}^{3}

2. T_{1} and nothing of an octahedron of the same Z_{i}. Then at least one facet of T_{1} belongs to bd(conv C_{n}) and we can associate a prism P_{1}. Then with ϱ_{3,c}^{L} = 8^{\frac{1}{4}} π^{− \frac{1}{2}} :

Θ(T′′) = (V (T_{1})Θ(T_{1}) + V (P_{1})Θ(P_{1}))(V (T_{1}) + V (P_{1}))^{−1} =
= (\frac{2}{3} \sqrt{2} · σ_{3} + \frac{π}{3} ) (\frac{2}{3} \sqrt{2} + \sqrt{3} ϱ_{3,c}^{L}) = (1, 782 …)(2, 586 …)^{−1} =
= 0, 689 … < δ_{L}^{3}.

3. T_{1} and exactly one quarter of an octahedron of the same Z_{i}, i.e. exactly one T_{2}. Then at least one of the nonregular facets of T_{2} belongs to bd(conv C_{n}) and we can associate a prism P_{2}. Then

Θ(T′′) = (V (T_{1})Θ(T_{1}) + V (T_{2})Θ(T_{2}) + V (P_{2})Θ(P_{2}))(V (T_{1}) + V (T_{2}) + V (P_{2}))^{−1} =
= (\frac{2}{3}\sqrt{2} σ_{3} + \frac{2}{3}\sqrt{2} · τ_{3} + \frac{π}{3} ) (\frac{4}{3}\sqrt{2} + 2ϱ_{c})^{−1} < Θ(T′′) < δ_{L}^{3}.

So in all cases, except for the vertex tiles, we have Θ_{i} ≤ δ_{L}^{3} and in at least one case < ; so with Lemma 3 the theorem is proved.

6. Some isoperimetric inequalities

For some hyperplane H, denote by π the reflection in H. Let 0 < ε < 1. We define the ε-Steiner symmetrization K′ of a convex body K so that for any line l orthogonal to H, the following holds:

l ∩ K′ = (1 − ε)(l ∩ K) + ε(l ∩ π(K)).

It is well-known (see [20], p.256) that V (K′) = V (K) and for i = 1, …, d−1, V_{i}(K′) ≤ V_{i}(K) with equality if and only if K has a symmetry hyperplane parallel to H. If the choice of ε is irrelevant, we speak simply about the Steiner symmetrization. The case ε = \frac{1}{2} is the classical Steiner-symmetrization and then K′ is symmetric in H.

If K is a simplex, Hadwiger proved (cf. [20], p.273)

Lemma 4. Among all simplices of a given volume, the regular simplex has the minimal intrinsic i-volume for i = 1, …, d − 1.

Note that the result as it is stated in [20], concerns only the surface area, but the same proof using the Steiner symmetrization yields Lemma 4 also for the other intrinsic volumes.

For 3-polytopes having five vertices, the isoperimetric problem is solved in [4]. We remind the reader that S(K) = 2V_{d−1}(K) is the surface-area of K.

Lemma 5. For a 3-polytope P with five vertices, we have

\frac{V_{1}(P)}{V (P)^{1/3}} ≥ 3.0925 … and \frac{S(P)}{V (P)^{2/3}} ≥ 6.2402 ….

The extremal bodies are certain bipyramids over triangles.

For a generalization of the next results of Steiner, see [4].

Lemma 6. In E^{3}, among all quadrilateral-based bipyramids of a given volume, the regular octahedron has the minimal intrinsic i-volume for i = 1, 2.

We consider a very specific inequality, which is needed for the proof of Lemma 9. Let N be the pyramid over the square having edge-length 2 and set ϕ(K) = V_{1}(K) + 0.3S(K). If B is the base of N and O is the regular octahedron with edge-length 2 then V_{i}(N) = \frac{1}{2}(V_{i}(O)+V_{i}(B)) for i = 1, 2.

Lemma 7. Let K be a pyramid in E^{3} with V (K) ≥ V (N) and assume that the base P of K is a parallelogram whose edges have length at least 2. Then the function ϕ(K) is minimal if and only if K = N.

Remark. It is not hard to see that V_{1}(K) ≥ V_{1}(N). The reason for such a complicated calculation is that S(K) can be actually smaller than S(N).

Proof. If A(P) ≥ 4 then define O′ as the union of K and its reflected image through the center of P. Lemma 6 and V (K) ≥ V (N) yield that V_{i}(K) = \frac{1}{2}(V_{i}(O′) + 2V_{i}(P)) ≥ V_{i}(N), with equality if and only if K = N.

So assume that A(P) ≤ 4. Using ε-Steiner symmetrization with respect to the planes orthogonal to the sides of P for small ε > 0 shows that we may assume that P is a rhombus having side-length 2, K is a right pyramid and V (K) = V (N).

Denote by α the smaller angle of P and set t = cos α, 0 ≤ t < 1. Some simple calculations show that ψ_{1}(t) = V_{1}(K) can be written as

ψ_{1}(t) = 2 [1 − \frac{1}{π} arctan (\frac{\sqrt{2}}{1 − t^{2}} )]

+ \frac{1}{\sqrt{2}}\sqrt{\frac{1}{1 − t^{2}} + 1 + t} [1 − \frac{2}{π} arctan (\sqrt{\frac{2}{1 + t} − t − t^{2} + t^{3}})]

+ \frac{1}{\sqrt{2}}\sqrt{\frac{1}{1 − t^{2}} + 1 − t} [1 − \frac{2}{π} arctan (\sqrt{\frac{2}{1 − t} + t − t^{2} − t^{3}})] ,

and for the surface area,

ψ_{2}(t) = S(K) = \sqrt{1 − t^{2}} + \sqrt{\frac{2}{1 − t^{2}} + 1 − t^{2}}.

We write the derivative of ψ_{1}(t) as ψ′_{1}(t) = ψ_{11}(t) + ψ_{12}(t) where

ψ_{11}(t) = \frac{1}{2\sqrt{2}}\sqrt{\frac{1 − t^{2}}{1 + (1 + t)(1 − t^{2})}} (\frac{2t}{(1 − t^{2})^{2}} + 1) ×

[1 − \frac{2}{π} arctan (\sqrt{\frac{2}{1 + t} − t − t^{2} + t^{3}})]

and

ψ_{12}(t) = \frac{1}{2\sqrt{2}}\sqrt{\frac{1 − t^{2}}{1 + (1 − t)(1 − t^{2})}} (\frac{2t}{(1 − t^{2})^{2}} − 1) ×

[1 − \frac{2}{π} arctan (\sqrt{\frac{2}{1 − t} + t − t^{2} − t^{3}})] .

If 2t/(1 − t^{2})^{2} ≥ 1 then ψ′_{1}(t) ≥ ψ_{11}(t). Using the monotonicity of the argument of arctan, t ≥ 0 and 1 + t < 2 for ψ_{11}(t) show that

ψ′_{1}(t) ≥ \frac{1}{\sqrt{6}} (1 − \frac{2}{π} arctan \sqrt{2}) t = 0.1599 t.

Now assume that 2t/(1 − t^{2})^{2} < 1, and hence t < 0.5. Set ω = \frac{1}{2\sqrt{2}}(1 − \frac{2}{π} arctan \sqrt{2}). We deduce that

ψ′_{1}(t) ≥ 2ω (\frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}}) t − ω (\frac{1}{\sqrt{1 + (1 − t)(1 − t^{2})}} − \frac{1}{\sqrt{1 + (1 + t)(1 − t^{2})}}) .

The derivative of the expression in the parentheses is at most 1.5 because 0 ≤ t < 0.5, which in turn yields that

ψ′_{1}(t) ≥ 2ω (\frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} − \frac{3}{4}) t = 0.1480 t.

On the other hand, differentiating ψ_{2}(t) via a substitution s = 1 − t^{2} results in

ϕ′_{2}(t) = (\frac{2}{s^{3/2}\sqrt{2 + s^{2}}} − \frac{1}{\sqrt{s}} − \begin{matrix}√ & \overline{s} \\ √ & \overline{2 + s^{2}} \end{matrix} ) t.

Here the expression in the parentheses is monotonely decreasing for 0 < s ≤ 1 as one can verify by differentiation, and hence

0.3ψ′_{2}(t) ≥ 0.3 (\frac{1}{\sqrt{3}} − 1) t = −0.1267 t.

It follows that ψ(t) = ψ_{1}(t) + 0.3ψ_{2}(t) is strictly monotonely increasing for 0 ≤ t < 1, which in turn yields that ϕ(K) ≥ ϕ(N) with equality if and only if K = N. □

7. Four-ball and five-ball packings

With respect to four-ball packings in E^{d}, d ≥ 3, and five-ball packings in E^{3}, we give a complete characterization of the optimal lattice packing for ϱ > 0 (see Theorem 7 and Theorem 8). The result about five-ball packings points to an interesting phenomenon: the optimal packing is not a lattice packing for ϱ ≥ 1.0483 . . ..

First we consider four-ball packings. We need the following lemma proved in [4]:

Lemma 8. Assume that x_{0} ∈ C for C = conv{x_{1}, x_{2}, x_{3}} and d(x_{i}, x_{j}) ≥ 2 for 0 ≤ i < j ≤ 3. Then V_{1}(C) ≥ 3 + \sqrt{3} = 4.7320 . . .. In addition, V_{1}(C) ≥ 3 + \sqrt{3} for a planar C ∈ F_{5}^{3}.

Note that V_{1}(convS_{4}) = 6 and using Steiner’s formula, the inequality V (convC_{4} + ϱB^{d}) ≥ V (convS_{4} + ϱB^{d}) can be written in the form

\frac{κ_{d−3}}{κ_{d−1}} \frac{1}{ϱ^{2}} V_{3}(convC_{4}) + \frac{κ_{d−2}}{2κ_{d−1}} \frac{1}{ϱ} S(convC_{4}) ≥ 6 − V_{1}(convC_{4}).  (7.16)

Let ϱ_{d,4}^{L} be the unique positive ϱ such that equality holds in (7.16) for convC_{4} = T^{3}.

Theorem 7. For a given ϱ > 0, assume that V (convC_{4} + ϱB^{d}) is minimal. Then

i) C_{4} = S_{4} if ϱ < ϱ_{d,4}^{L}, ii) C_{4} = S_{4} or convC_{4} = T^{3} if ϱ = ϱ_{d,4}^{L}, iii) convC_{4} = T^{3} if ϱ > ϱ_{d,4}^{L}.

Remark. Let ω = 0.2927 … be the positive root of the equation

4V_{3}(T^{3}) ω^{2} + S(T^{3}) ω = 6 − V_{1}(T^{3}).

Then for large d, ϱ_{d,4}^{L} ∼ (2\sqrt{2π}ω)^{−1}\sqrt{d} = 0.6814 … \sqrt{d}. If d = 3 then ϱ_{4} = 1.1332.

Proof of Theorem 7. If dim(convC_{4}) = 3 then V (convC_{4}) ≥ V (T^{3}) because the edges of T^{3} determine the densest lattice packing of B^{3}, which in turn yields V_{i}(convC_{4}) ≥ V_{i}(T^{3}) by Lemma 4, with equality only if convC_{4} = T^{3}.

So assume dim(convC_{4}) = 2 and ϱ ≥ ϱ_{d,4}^{L}. Then we deduce the inequality

ϱ^{2}π(V_{1}(convC_{4}) − V_{1}(T^{3})) ≥ 1.4158 > V (T^{3})

as V_{1}(convC_{4}) ≥ 4 by Lemma 8, and hence V (convC_{4} +ϱB^{d}) > V (T^{3} +ϱB^{d}) by S(convC_{4}) ≥ S(T^{3}) and by Steiner’s formula. Finally, (7.16) yields the case ϱ < ϱ_{d,4}^{L} since strict inequality holds for ϱ = ϱ_{d,4}^{L}. □

For five-ball packings, the following lemma is the core of the proof. Again, let ϕ(K) = V_{1}(K) + 0.3S(K).

Lemma 9. If int(convC_{5}) is non-empty then ϕ(convC_{5}) ≥ ϕ(N) with equality iff convC_{5} = N.

Proof. Let convC_{5} = conv{x_{0}, …, x_{4}} where x_{0}, …, x_{4} are points of some packing lattice. If convC_{5} can be dissected into at least three simplices then V (convC_{5}) ≥ 2\sqrt{2}. We deduce S(convC_{5}) > S(N) and V_{1}(convC_{5}) > V_{1}(N) by Lemma 5, which in turn yields ϕ(convC_{5}) > ϕ(N).

So assume that convC_{5} is a pyramid over the base P where x_{1}, …, x_{4} are the only lattice points in P. If P is a triangle then V_{1}(P) ≥ 3 + \sqrt{3} by Lemma 8. It follows by S(convC_{5}) ≥ 6\sqrt{3} and V_{1}(N) = 4.3509 … that

ϕ(convC_{5}) − ϕ(N) ≥ (3 + \sqrt{3} − V_{1}(N)) + 0.3(2\sqrt{3} − 4) = 0.2203 > 0.

The only remaining case, if P is a parallelogram, is settled in Lemma 7. □

Define ϱ_{3,5}^{L} = 1.1025 … by the equality V (N + ϱ_{3,5}^{L}B^{3}) = V (convS_{5} + ϱ_{3,5}^{L}B^{3}).

Theorem 8. For a given ϱ > 0, assume that V (convC_{5} + ϱB^{3}) is minimal. Then

i) C_{5} = S_{5} if ϱ < ϱ_{3,5}^{L}, ii) C_{5} = S_{5} or convC_{5} = N if ϱ = ϱ_{3,5}^{L}, iii) convC_{5} = N if ϱ > ϱ_{3,5}^{L}.

Proof. By Steiner’s formula, the inequality V (convC_{5}+ϱB) ≥ V (convS_{5}+ϱB) can be written in the form

\frac{1}{ϱ^{2}π} V (convC_{5}) + \frac{1}{ϱπ} S(convC_{5}) + V_{1}(convC_{5}) ≥ 8.  (7.17)

First let ϱ ≤ ϱ_{3,5}^{L} and let dim(convC_{5}) = 2. According to Oler’s inequality (cf. [15]),

\frac{1}{2\sqrt{3}}S(convC_{5}) + V_{1}(convC_{5}) ≥ 8,

which in turn yields (7.17) by ϱπ ≤ 3.4635 < 2\sqrt{3}.

If ϱ ≥ ϱ_{3,5}^{L} and dim(convC_{5}) = 3 then V (convC_{5} + ϱB) ≥ V (N + ϱB) is equivalent with

\frac{1}{ϱ^{2}π} V (convC_{5}) + \frac{1}{ϱπ} S(convC_{5}) + V_{1}(convC_{5}) ≥ \frac{1}{ϱ^{2}π} V (N) + \frac{1}{ϱπ} S(N) + V_{1}(N). (7.18)

Here V (convC_{5}) ≥ V (N) as convC_{5} can be dissected into at least two packing-lattice simplices, and hence it is sufficient to verify

V_{1}(convC_{5}) − V_{1}(N) ≥ \frac{1}{ϱπ} (S(N) − S(convC_{5})).

This inequality follows by 1/(ϱπ) = 0.2887 … < 0.3 and by Lemma 9.

So far we have proved ii), which in turn yields i) by (7.17). If ϱ ≥ ϱ_{3,5}^{L} then the only remaining case to consider is dim(convC_{5}) = 2. Set t = 1/ϱ and t_{5} = 1/ϱ_{3,5}^{L}. The inequality V (convC_{5} + ϱB) ≥ V (N + ϱB) can be written in the form

\frac{V (N)}{π} t^{2} + \frac{S(N) − S(convC_{5})}{π} t ≤ V_{1}(convC_{5}) − V_{1}(N).

As 0 is a root of the quadric polynomial on the left-hand side and the inequality holds for t = t_{5} by the case ii), strict inequality also holds for t < t_{5}. □

Finally, we compare general packings and lattice packings. Let D_{5} be the bipyramid with all edges of length 1, and define ϱ_{5} = 1.0483 < ϱ_{3,5}^{L} by the formula V (D_{5} + ϱ_{5}B^{3}) = V (convS_{5} + ϱ_{5}B^{3}). Most probably ϱ_{5} = ϱ_{3,5}. Observe that V (D_{5}) = V (N) and V_{i}(D_{5}) < V_{i}(N) for i = 1, 2. Therefore Lemma 8 yields that a lattice packing can be the optimal general packing only for small ϱ; namely, when it is the sausage.

Phenomenon 1. For ϱ > ϱ_{5}^{∗}, the general packing of five balls minimizing V (convC_{5} + ϱB^{3}) is not induced by a lattice packing.

8. Proof of Theorem 6

We compare the sausage arrangement of d + 1 balls with the arrangement determined by T^{d}. The edges of T^{d} determine a packing lattice Λ such that T^{d} is a lattice simplex.

Note that if F is an i-face of T^{d} then

\frac{Ĝ_{Λ}(F) · κ_{i}}{|F |} = σ_{i},

namely, the classical Rogers bound. It follows by (3.9) (actually with the opposite inequality sign), that V (T^{d} + ϱB^{d}) < V (convS_{n} + ϱB^{d}) holds if

ϱ > ^{i−1} \sqrt{\frac{κ_{d−i}}{2κ_{d−1}} · \frac{1}{σ_{i}}}

for i = 2, …, d. The inequalities (see [7])

\frac{κ_{m−2}}{κ_{m}} = \frac{m}{2π} and \frac{κ_{m−1}}{κ_{m}} < \sqrt{\frac{m + 1}{2π}}

yield that in order to prove 1), it is sufficient to verify that

0.6 · \sqrt{d} > \sqrt{\frac{d}{2π}} · ^{i−1} \sqrt{\frac{1}{2σ_{i}}} .  (8.19)

If i ≤ 8 then we deduce (8.19) from the known values of the Rogers constant (see [11]). On the other hand, Blichfeldt’s method yields that σ_{i} > \frac{i+2}{i+1} \sqrt{2}^{−i} (see [13]), and if i > 8 then (8.19) follows using this estimate.

Now we verify 2). Let ε > 0, and choose k so that 2/(k − 1) < ε. Observe that V (T^{d} + ϱB^{d}) > V (convS_{n} + ϱB^{d}) is equivalent to

∑_{i=1}^{d} \frac{κ_{d−i}}{2κ_{d−1}} \frac{1}{2d} V_{i}(T^{d}) · \frac{1}{ϱ^{i−1}} > 1.  (8.20)

For large d, the asymptotic value of V_{k}(T^{d}) is calculated in [2]. It follows that for large d,

\frac{κ_{d−k}}{2κ_{d−1}} \frac{1}{2d} V_{k}(T^{d}) ∼ c(k) · \frac{\sqrt{d}^{k−1}\sqrt{ln d}^{k}}{d} > \sqrt{d}^{k−3}.

Now the choice of k and (8.20) yield that if ϱ < \sqrt{d}^{1−ε} then

V (T^{d} + ϱB^{d}) > V (convS_{n} + ϱB^{d}).

Acknowledgement. We would like to thank Uwe Schnell for helpful comments.

References

[1] Arhelger, V.; Betke, U.; Böröczky Jr., K.: Large finite packings. (In preparation)

[2] Affentranger, F.; Schneider, R.: Random Projections of Regular Simplices. Disc. Comp. Geom. 7 (1992), 219–226.

[3] Böröczky Jr., K.: Packings of four and five balls. Proceedings of the 4th Intuitive Geometry Conference, Budapest, Hungary (accepted).

[4] Böröczky, K.; Böröczky Jr., K.: Isoperimetric problems for polytopes with given number of vertices. Mathematika (accepted).

[5] Bonnesen, T.; Fenchel, W.: Theorie der konvexen Körper. Springer, Berlin 1934.

[6] Betke, U.; Gritzmann, P.: An application of valuation theory to two problems in discrete geometry. Discrete Mathematics 58 (1986), 81–85.

[7] Betke, U.; Gritzmann, P.; Wills, J. M.: Slices of L. Fejes Tóth’s Sausage Conjecture. Mathematika 29 (1982), 194–201.

[8] Betke, U.; Henk, M.; Wills, J. M.: Finite and infinite packings. Journal für Reine und Angewandte Mathematik 453 (1994), 165–191.

[9] Betke, U.; Henk, M.; Wills, J. M.: Sausages are good packings. Discrete and Computational Geometry 13 (1995), 297–311.

[10] Conway, J. H.; Sloane, N. J. A.: Laminated lattices. Annals of Mathematics 116 (1982), 593–620.

[11] Conway. J. H.; Sloane, N. J. A.: Sphere packings, Lattices and Groups. Springer-Verlag, Berlin–New York 1989.

[12] Florian, A.: Extremum problems for convex discs and polyhedra. Handbook of Convex Geometry, P. M. Gruber and J. M. Wills eds., North Holland, Amsterdam 1993, 177–221.

[13] Gruber, P. M.; Lekkerkerker, C. G.: Geometry of Numbers. North Holland, Amsterdam 1987.

[14] Gritzmann, P.: Finite Packungen und Überdeckungen. Habilitationschrift, Universität Siegen (1984).

[15] Gritzmann, P.; Wills, J. M.: Lattice points. Handbook of Convex Geometry, P. M. Gruber and J. M. Wills eds., North Holland, Amsterdam 1993, 765–798.

[16] Gritzmann, P.; Wills, J. M.: Finite packing and covering. Handbook of Convex Geometry, P. M. Gruber and J. M. Wills eds., North Holland, Amsterdam 1993, 861–898.

[17] Graham, R. L.; Sloane, N. J. A.: Penny-Packing and two dimensional codes. Disc. Comp. Geom. 5 (1990), 1–11.

[18] Gandini, P. M.; Zucco, A.: On the sausage catastrophe in 4-space. Mathematika 39 (1992), 274–278.

[19] Groemer, H.: Über die Einlagerung von Kreisen in einen konvexen Bereich. Math. Z. 73 (1960), 285–290.

[20] Hadwiger. H.: Vorlesung über Inhalt, Oberfläche und Isometrie. Springer-Verlag, Berlin 1957.

[21] Henk, M.: Finite and infinite packings. Habilitationschrift, Universität Siegen (1995).

[22] Hoare, M. R.; Pal, P.: Physical cluster mechanics: statics and energy systems for monoatomic systems. Adv. Phys. 20 (1971), 161–166.

[23] Hoare, M. R.; Pal, P.: Physical cluster mechanics: statistical thermodynamics and nucleation theory for monoatomic systems. Adv. Phys. 24 (1975), 645–678.

[24] Rogers, C. A.: Packing and covering. Cambridge University Press, Cambridge 1964.

[25] Schneider, R.: Convex Bodies - the Brunn-Minkowski theory. Cambridge Univ. Press, Cambridge 1993.

[26] Sloane, N. J. A.; Hardin, R. H.; Duff, T. D. S.; Conway, J. H.: Minimal-energy clusters of hard spheres. Disc. Comp. Geom. 14 (1995), 237–259.

[27] Wills, J. M.: On the density of finite packings. Acta Math. Hung. 46 (1985), 205–210.

[28] Wills, J. M.: Finite sphere packings and sphere coverings. Rendic. del Semin. Mat. Messina 2 (1993), 1–7.

Received January 5, 1996