On finite sphere packings and coverings

This thesis provides improved upper and lower bounds on the finite packing densities of spheres and cross-polytopes in the Euclidean space Rᵈ. Let K be an origin-symmetric convex body in Rᵈ and denote the set of such bodies by (K₀) ᵈ. A set C ⊂ Rᵈ is called a packing set of K ∈ (K₀) ᵈ if (x + int K) ∩ (y + int K) = ∅ for all x, y ∈ C and x ≠ y. Let Cᵈ (K) be the collection of all packing sets of K in Rᵈ and (Cₙ) ᵈ (K) ⊂ Cᵈ (K) be the subset of packings with cardinality | (Cₙ) ᵈ| = n. The density δ (K, (Cₙ) ᵈ) of any (Cₙ) ᵈ ∈ (Cₙ) ᵈ (K) is defined by δ (K, (Cₙ) ᵈ): = | (Cₙ) ᵈ|vol (K) / vol (conv ( (Cₙ) ᵈ) + K), where vol is the d‑dimensional volume and conv is the convex hull. We write δ ( (Cₙ) ᵈ): = δ (Bᵈ, (Cₙ) ᵈ). Cross-Polytope Packings. We consider packing sets of scaled cross-polytopes r (Cd) *, r > 0, where (Cd) *: = x = (x₁,. . . , xd) T ∈ Rᵈ | ∑ (i = 1, d, |xᵢ| ≤ 1) is also known as the closed unit ball in the 1‑norm. The cross-polytope in dimensions one and two is a line segment and a rotated square respectively, both of which have packing density 1. So we focus primarily on d = 3, in which (C₃) * is the octahedron of edge length √2. For r > 0, define γ ( (Cd) *, r): = max|C| | C ∈ Cᵈ (r (Cd) *) and C ⊂ (Cd) *, which is the maximum number of almost disjoint cross-polytopes of radius r whose centers are contained within (Cd) *. Since γ ( (Cd) *, r) = 1 for r > 1 and γ ( (Cd) *, r) grows exponentially in d for r ≤ 1/2 Tal00, we focus on the interval 1/2 1/2. Depending on the value of r, the presence of a scaled octahedron r (C₃) * in one or more subsets can be ruled out, lowering the upper bound for γ ( (C₃) *, r) accordingly. All lower bounds for γ ( (C₃) *, r) are attained via explicit examples of packing sets for the appropriate values of r. The Sausage Conjecture (joint work with Martin Henk). A sausage arrangement (Sₙ) ᵈ is any packing set that can be translated to a set of the form 2iu ∈ Rᵈ | i ∈ {0,. . . , n − 1} for some n ∈ N and a unit vector u ∈ S^ (d − 1). The Sausage Conjecture of L. Fejes Tóth (1975) FT75 is the assertion that for all d ≥ 5, the sausage arrangement is the unique densest packing of any number of identical spheres. Many partial results for the Sausage Conjecture exist, and in particular Betke and Henk (1998) proved the conjecture for all d ≥ 42 BH98. We refine their methods to prove that the conjecture also holds for d ≥ 40. Moreover, we show that the Sausage Conjecture holds in several lower dimensions for a certain restricted set of packings. Let k ∈ 0, 1, 2 denote the number of “endpoints” of a packing (see Definition 8. 10). We show that for d = 39, all packing sets with at most 25 points and one endpoint, or at most 49 points and no endpoints, are less dense than the sausage. Additional results of this form are available in Table 11. 1. The Sausage Catastrophe. For each d ≤ 4 and n ∈ N, let (Cₙ) ^d, max ∈ (Cₙ) ᵈ (Bᵈ) have maximal density. This packing is known to be a sausage (dim ( (Cₙ) ^d, max) = dim ( (Sₙ) ᵈ) = 1) if n is small, and full‑dimensional (dim ( (Cₙ) ^d, max) = d) if n is large, but dim ( (Cₙ) ^d, max) can never be in between. Jörg Wills (1983) Wil83 termed this phenomenon the Sausage Catastrophe. Define υd: = minn ∈ N | dim ( (Cₙ) ^{d, max) = d}, Υd: = minn' ∈ N | dim ( (Cₙ) ^{d, max) = d for all n ≥ n'}. These constants are the thresholds for n at which the densest packing with n spheres changes from a sausage to a full‑dimensional set, and remains full‑dimensional for all n' ≥ n spheres, respectively. For any d ∈ N we have υd ≤ Υd. It is known that 1. υ₁ = υ₁ = 1 (trivial), 2. υ₂ = υ₂ = 3 (elementary), 3. 5 ≤ υ₃ ≤ 56 Bör93, Wil85 and Υ₃ ≤ 58 GW92, Sch00a, and 4. 5 ≤ υ₄ < 367, 300 BG84, GZ92. We build upon Gandini and Zucco's (1992) GZ92 work in four dimensions to show that υ₄ ≤ 338, 196 and Υ₄ ≤ 516, 946. Additionally, we show that full‑dimensional packings are optimal for various n between 338, 196 and 516, 946 (see Proposition 15. 6 for the lengthy list). Exact coverings (joint work with Christian Kipp and Sandro Roch). Let d ∈ N and X be a point set in Rᵈ. A collection Dcal of closed unit disks in Rᵈ is an almost disjoint cover of X if distinct disks in Dcal are almost disjoint and for each x ∈ X there exists a D ∈ Dcal such that x ∈ D. Let σd be the smallest n ∈ N such that any set of n distinct points in Rᵈ can be covered by almost disjoint unit disks. Inaba (2008) Ina08a, Ina08b showed that σ₂ ≥ 10, and Aloupis, Hearn, Iwasawa, and Uehara (2012) AHIU12 improved the lower bound to σ₂ ≥ 12 and provided an upper bound of σ₂ < 45. We study a weaker version of this problem in which the disks no longer need to be almost disjoint, but each x ∈ X must be part of exactly one D ∈ Dcal. This notion is called exact covering. Let σdₕat be the smallest n ∈ N such that any set of n distinct points in Rᵈ can be exactly covered by unit disks. We have σd ≤ σdₕat. Our main result is σ₂ₕat ≥ 17, which stacks various combinatorial methods on top of Inaba's original proof. In higher dimensions, we obtain the near-trivial general result of σdₕat ≥ d + 4 for all d ∈ N along with the not-so-trivial σ₃ₕat ≥ 9. These results are based on a straightforward generalization of Inaba's method to d ≥ 3.