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^d. Let K be an origin-symmetric convex body in R^d and denote the set of such bodies by (K_0)^d. A set C ⊂ R^d is called a packing set of K ∈ (K_0)^d if (x + int K) ∩ (y + int K) = ∅ for all x,y ∈ C and x ≠ y. Let C^d(K) be the collection of all packing sets of K in R^d and (C_n)^d(K) ⊂ C^d(K) be the subset of packings with cardinality |(C_n)^d| = n. The density δ(K, (C_n)^d) of any (C_n)^d ∈ (C_n)^d(K) is defined by δ(K, (C_n)^d) := |(C_n)^d|vol(K) / vol(conv((C_n)^d) + K), where vol is the d‑dimensional volume and conv is the convex hull. We write δ((C_n)^d) := δ(B^d,(C_n)^d). Cross-Polytope Packings. We consider packing sets of scaled cross-polytopes r(C_d)*, r > 0, where (C_d)* := {x = (x_1, ..., x_d)^T ∈ R^d | ∑(i = 1, d, |x_i| ≤ 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_3)* is the octahedron of edge length √2. For r > 0, define γ((C_d)*, r) := max{|C| | C ∈ C^d(r(C_d)*) and C ⊂ (C_d)*}, which is the maximum number of almost disjoint cross-polytopes of radius r whose centers are contained within (C_d)*. Since γ((C_d)*, r) = 1 for r > 1 and γ((C_d)*, r) grows exponentially in d for r ≤ 1/2 [Tal00], we focus on the interval 1/2 < r ≤ 1. We obtain the following results: 1. For any d ∈ N, if r ∈ (1 − 1/d, 1] then γ((C_d)*, r) = 2d. Additionally, (1 − 1/d, 1] is the largest possible interval such that γ((C_d)*, r) = 2d for all r in the interval. 2. If r ∈ (3/5, 2/3] then γ((C_3)*, r) = 10 3. If r ∈ (4/7, 3/5] then γ((C_3)*, r) = 12 4. If r ∈ (1/2, 4/7] then 13 ≤ γ((C_3)*, r) ≤ 14 We establish all upper bounds for γ((C_3)*, r) using combinatorial methods. We divide (C_3)* into fourteen subsets corresponding to the six vertices and eight facets to show that γ((C_3)*, r) ≤ 14 when r > 1/2. Depending on the value of r, the presence of a scaled octahedron r(C_3)* in one or more subsets can be ruled out, lowering the upper bound for γ((C_3)*, r) accordingly. All lower bounds for γ((C_3)*, 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_n)^d is any packing set that can be translated to a set of the form {2iu ∈ R^d | 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_n)d, max ∈ (C_n)^d(B^d) have maximal density. This packing is known to be a sausage (dim((C_n)d, max) = dim((S_n)^d) = 1) if n is small, and full‑dimensional (dim((C_n)d, max) = d) if n is large, but dim((C_n)d, max) can never be in between. Jörg Wills (1983) [Wil83] termed this phenomenon the Sausage Catastrophe. Define υ_d := min{n ∈ N | dim((C_n)d, max) = d}, Υ_d := min{n' ∈ N | dim((C_n)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 = υ_1 = 1 (trivial), 2. υ_2 = υ_2 = 3 (elementary), 3. 5 ≤ υ_3 ≤ 56 [Bör93, Wil85] and Υ_3 ≤ 58 [GW92, Sch00a], and 4. 5 ≤ υ_4 < 367,300 [BG84, GZ92]. We build upon Gandini and Zucco's (1992) [GZ92] work in four dimensions to show that υ_4 ≤ 338,196 and Υ_4 ≤ 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^d. A collection D_cal of closed unit disks in R^d is an almost disjoint cover of X if distinct disks in D_cal are almost disjoint and for each x ∈ X there exists a D ∈ D_cal such that x ∈ D. Let σ_d be the smallest n ∈ N such that any set of n distinct points in R^d can be covered by almost disjoint unit disks. Inaba (2008) [Ina08a, Ina08b] showed that σ_2 ≥ 10, and Aloupis, Hearn, Iwasawa, and Uehara (2012) [AHIU12] improved the lower bound to σ_2 ≥ 12 and provided an upper bound of σ_2 < 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 ∈ D_cal. This notion is called exact covering. Let σ_d_hat be the smallest n ∈ N such that any set of n distinct points in R^d can be exactly covered by unit disks. We have σ_d ≤ σ_d_hat. Our main result is σ_2_hat ≥ 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_hat ≥ d + 4 for all d ∈ N along with the not-so-trivial σ_3_hat ≥ 9. These results are based on a straightforward generalization of Inaba's method to d ≥ 3.