Research

1. Finite cross-polytope packings

2. The Sausage Conjecture

3. The Sausage Catastrophe in dimension 4

4. Exact coverings of disks and balls

References

Research projects

1. Finite cross-polytope packings

I studied the problem of how many cross-polytopes can be translatively packed inside a larger cross-polytope. I focused on 3 dimensions but also explored the d-dimensional case.

Definition:
For any d ∈ N, convex body K ⊆ R^d, and r > 0,
Let γ(K, r) be the maximum number of points in a packing set of rK that is contained in K.

Denote the unit cross-polytope in R^d by C*_d. We know that

γ(C*_d, r) = 1 for r ∈ (1, ∞) (trivial),
19 ≤ γ(C₃*, r) ≤ 26 for r = 1/2 (Larman and Zong 1999, Talata 2000, Hadwiger 1957).

I found some basic results that apply for all d:

γ(C*_d, r) = 2n for r ∈ (1 – 1/d, 1].

I used methods similar to Larman and Zong (1999) and Talata (1999) to obtain several upper bounds in three dimensions. In contrast, the lower bounds were obtained by constructions of packings with the given numbers of points.

γ(C₃*, r) = 6 for r ∈ (2/3, 1] (a special case of γ(C*_d, r) = 2n),
γ(C₃*, r) = 10 for r ∈ (3/5, 2/3],
γ(C₃*, r) = 12 for r ∈ (4/7, 3/5],
12 ≤ γ(C₃*, r) = 14 for r ∈ (6/11, 4/7],
13 ≤ γ(C₃*, r) = 14 for r ∈ (1/2, 6/11].

Preprint and Publication:

Ji Hoon Chun. The maximum number of points in the cross-polytope that form a packing set of a scaled cross-polytope. arXiv, August 2019.
Ji Hoon Chun. On Local Packings of the Cross-Polytope, The Electronic Journal of Combinatorics 27(3) (2020), #3.38.

A packing of 13 cross-polytopes of radius 6/11 (green, blue, purple, pink) whose centers are contained inside a unit cross-polytope (translucent grey).

2. The Sausage Conjecture

The Sausage Conjecture of László Fejés Tóth (1975) states that in dimensions d ≥ 5, the densest packing of any finite number n of spheres is a sausage arrangement—where all the sphere centers are placed in a line as close together as possible—for any n. Also, the maximal density is only obtained with the sausage.

To more precisely state this conjecture, it helps to introduce several definitions.

Preliminary Definitions:
Let n ∈ N. For any finite packing set C_n ⊂ R^d with n points,
Let δ(d, C_n) be the finite packing density of C in R^d.
Let δ(d, n) := max{δ(d, C_n) | C_n ⊂ R^d is a packing set with n points} be the density of the densest finite packing of n spheres in R^d.

Definitions for the Sausage Conjecture:
For all d ≥ 2 and n ∈ N, let S^d_n be the sausage arrangement of n points in R^d.
Let ψ be the smallest dimension d ≥ 2 such that for all n ∈ N, if C_n is any nonsausage packing in R^d with n points, then δ(d, C_n) < δ(d, S^d_n).
Let Ψ be the smallest dimension D ≥ 2 such that for all d ≥ D and n ∈ N, if C_n is any nonsausage packing in R^d with n points, then δ(d, C_n) < δ(d, S^d_n).
Let ψ_d be the smallest number n ∈ N of points such that if C_n is any nonsausage packing in R^d with n points, then δ(d, C_n) < δ(d, S^d_n).
Let Ψ_d be the smallest number N ∈ N of points such that for all n ≤ N, if C_n is any nonsausage packing in R^d with n points, then δ(d, C_n) < δ(d, S^d_n).

We require d, d' ≥ 2 in the definitions for ψ and Ψ because the sausage is trivially identical to the densest packing in dimensions 1 and 0.

If d ≥ ψ then the sausage is the unique packing that achieves the maximal packing density of n spheres in R^d for all n ∈ N.
If D ≥ Ψ then the sausage is the unique packing that achieves the maximal packing density of n spheres in R^d for all d ≥ D and n ∈ N.

A direct consequence of the definitions are the inequalities ψ ≤ Ψ and ψ_d ≤ Ψ_d for all d ≥ 2.

With this notation, we may restate the Sausage Conjecture as

ψ = Ψ = 5.

This conjecture has been neither proved nor disproved, but many partial results have been obtained over the years. In particular, Betke, Gritzmann, and Wills (1982) proved that the Sausage Conjecture is true for all finite packings C with dim C ≤ 7/12 · (d – 1), which implies Ψ_d ≤ 7/12 · (d – 1). The current best result for Ψ is from Betke and Henk (1998), who proved that Ψ ≤ 42.

My joint work with Professor Henk refines Betke and Henk's techniques to slightly improve the upper bound on Ψ:

Ψ ≤ 40.

Additionally, we obtained positive results for Ψ_d in several dimensions below 40 as long as the packings are "round" enough. Intuitively, a sausage has two endpoints. Betke, Henk, and Wills (1994) generalized this notion of an endpoint to arbitrary packings. Their definition is complicated, but an endpoint x ∈ C resembles an endpoint of a sausage in the sense that from the vantage point of x, all all other points of C are in roughly one direction. Every packing has 0, 1, or 2 endpoints.

The view of a sausage from an endpoint.

Note: The spheres have been shrunk for clarity.

The view of a general packing from an endpoint.

Note: The spheres and angles have been shrunk for clarity.

Now we modify our definition of ψ_d and Ψ_d to account for differing numbers of endpoints.

Definitions:
For all d ≥ 2 and k ∈ {0, 1, 2},
Let ψ_d(k) be the smallest number n ∈ N of points such that if C_n is any nonsausage packing in R^d with n points and at most k endpoints, then δ(d, C_n) < δ(d, S^d_n).
Let Ψ_d(k) be the smallest number N ∈ N of points such that for all n ≤ N, if C_n is any nonsausage packing in R^d with n points and at most k endpoints, then δ(d, C_n) < δ(d, S^d_n).

As before, for each k ∈ {0, 1, 2} we have ψ_d(k) ≤ Ψ_d(k) for all d ≥ 2.

In particular, for any d ≥ 2, we have ψ_d(0) ≤ ψ_d(1) ≤ ψ_d(2) = ψ_d and Ψ_d(0) ≤ Ψ_d(1) ≤ Ψ_d(2) = Ψ_d. The collection of finite packings with 0 or 1 endpoint is smaller than the collection of all finite packings, and it's easier for all packings in a smaller collection to be less dense than the sausage.

We provide the following upper bounds for Ψ_d(k) with certain values of d < 40 and k ∈ {0, 1}:

Ψ_39(0) ≤ 49 and Ψ_39(1) ≤ 25.

We also obtained Ψ_38(0) ≤ 20 and Ψ_38(1) ≤ 11, along with other nontrivial upper bounds for several lower dimensions. However, all of them are subsumed by Betke, Gritzmann, and Wills's inequality Ψ_d ≤ 7/12 · (d – 1). For example, this inequality yields Ψ_39 ≤ 22.16... < 25 but Ψ_38 ≤ 21.58... > 20.

Additionally, we conjecture Ψ ≤ 36 via a challenging extension of Betke and Henk's methods. We hope to release a preprint containing this result in 2025 as a Part 2 of the Thesis Part 2.

3. The Sausage Catastrophe in dimension 4

The Sausage Conjecture is false in dimensions 2, 3, and 4. The Sausage Catastrophe (Jörg Wills, 1985) states that in dimensions 3 and 4, the densest packing of n spheres is a sausage for small n but suddenly becomes full dimensional at a certain threshold.

Note that this transition may occur multiple times: As n increases, the dimension of the densest packing of n spheres could bounce from a sausage to a full-dimensional packing and back. However, for all sufficiently large n the densest packing will be of full dimension.

Definitions:
For d ∈ {0, 1, 2, 3, 4},
Let υ_d be the smallest n ∈ N for which the densest packing of n spheres in R^d is full-dimensional,
Let Υ_d be the smallest N ∈ N for which the densest packing of n spheres in R^d is full-dimensional for all n ≥ N.

It is known that

υ₀ = Υ₀ = 1 (trivial),
υ₁ = Υ₁ = 1 (trivial),
υ₂ = Υ₂ = 3 (elementary),
5 ≤ υ₃ ≤ 56 (Böröczky Jr. 1993, Wills 1985) and Υ₃ ≤ 58 (Gandini and Wills 1992, Scholl 2000), and
5 ≤ υ₄ < 367,300 (Betke and Gritzmann 1984, Gandini and Zucco 1992).

This project extends the methods of Gandini and Zucco to obtain the following new upper bounds on υ₄ and Υ₄:

5 ≤ υ₄ ≤ 338,196 and 5 ≤ Υ₄ ≤ 516,946. (We also write the existing lower bounds for context.)

Preprint:

Ji Hoon Chun, On the Sausage Catastrophe in 4 Dimensions, arXiv, February 2023.

This paper uses code which is available on GitHub.

An updated version of this paper has been accepted by the RSME Springer Series in conjunction with the geOmetry, anaLysis & convExity — Sevilla 2022 conference.

4. Exact coverings of disks and balls

I worked on the following small project on coverings with Lászlo Kozma, Michaela Borzechowski, Vera Chekan, Christian Kipp, and Sandro Roch. The topic of coverings is adjacent to packings and this problem was mentioned at the Facets of Complexity Problem-Solving-Workshop 2022.

Naoki Inaba (2008) posed the following problem: Is it possible to cover any set of 10 points on the plane by disjoint unit disks? Inaba proved his claim using a brief and elegant probabilistic argument.

Definitions:
For any d ∈ N,
Let σ_d be the largest n such that any set in R^d with n points can be covered by nonoverlapping unit d-balls.
Let σ̂_d be the largest n such that any set in R^d with n points can be exactly covered by unit d-balls. In exact covering, the disks may overlap but each point can be in only one ball.

In particular, σ_d ≤ σ̂_d for all d. Inaba showed that σ₂ ≥ 10. It is known that 12 ≤ σ₂ ≤ 44 (Aloupis, Hearn, Iwasawa, and Uehara 2012).

By building on Inaba's original proof, we show the following bounds for σ̂₂ and σ̂_d:

17 ≤ σ̂ ₂ ≤ 657,
σ̂ ₃ ≥ 9.
σ̂ _d ≥ d + 4 for all d ≥ 4.

An exact covering of several points (blue and green dots) by disks. The green triangle is the convex hull of the point set.

Preprints:

Ji Hoon Chun, Christian Kipp, and Sandro Roch, On exact covering with unit disks, arXiv, January 2024.
An older version was accepted by the EuroCG2024 conference and is available here.

References

Greg Aloupis, Robert A. Hearn, Hirokazu Iwasawa, and Ryuhei Uehara, Covering points with disjoint unit disks, Canadian Conference on Computational Geometry (2012). URL: https://api.semanticscholar.org/ CorpusID:16280099.
Ulrich Betke and Peter Gritzmann, Über L. Fejes Tóth’s wurstvermutung in kleinen dimensionen, Acta Mathematica Hungarica, 43 (1984), pp. 299–307.
Ulrich Betke, Peter Gritzmann, and Jörg M. Wills, Slices of L. Fejes Tóth’s sausage conjecture, Mathematika, 29 (1982), pp. 194–201.
Ulrich Betke and Martin Henk, Finite packings of spheres, Discrete & Computational Geometry, 19 (1998), pp. 197–227.
Ulrich Betke, Martin Henk, and Jörg M. Wills, Finite and infinite packings, Journal für die reine und angewandte Mathematik, 453 (1994), pp. 165–192.
Károly Böröczky, Jr., About four-ball packings, Mathematika, 40 (1993), pp. 226–232.
Károly Böröczky, Jr. and Martin Henk, Radii and the sausage conjecture, Canadian Mathematical Bulletin, 38 (1995), pp. 156–166.
Pier M. Gandini and Jörg M. Wills, On finite sphere packings, Mathematica Pannonica, 3 (1992), pp. 19–29.
Pier M. Gandini and Andreana Zucco, On the sausage catastrophe in 4-space, Mathematika, 39 (1992), pp. 274–278.
Hugo Hadwiger, Über treffanzahlen bei translationsgleichen eikörpern, Archiv der Mathematik, 8 (1957), pp. 212–213.
Martin Henk, Finite and Infinite Packings, Habilitationsschrift, Universität-GH-Siegen, Sep 1994.
Naoki Inaba, "10 points" http://inabapuzzle.com/hirameki/suuri_4.html .
Naoki Inaba, "10 points Answer" http://inabapuzzle.com/hirameki/suuri_ans4.html .
David G. Larman and Chuanming Zong, On the kissing numbers of some special convex bodies, Discrete & Computational Geometry, 21 (1999), pp. 233–242.
Peter Scholl, Finite kugelpackungen, 2000.
István Talata, A lower bound for the translative kissing numbers of simplices, Combinatorica, 20 (2000), pp. 281–293.
L. Fejes Tóth, Research problem 13, Periodica Mathematica Hungarica, 6 (1975), pp. 197–199.
Jörg M. Wills, Research problem 35, Periodica Mathematica Hungarica, 14 (1983), pp. 309–314.
Jörg M. Wills, On the density of finite packings, Acta Mathematica Hungarica, 46 (1985), pp. 205–210.

Page updated

Google Sites

Report abuse