Minimum central circles: chain order, seam obstructions, and exact finite certification
summary
The gist
Circles of radii 1, 2,..., n are all externally tangent to a central circle, and the central radius R is minimized over cyclic orders of the surrounding circles This paper addresses the problem on…
In short
The paper investigates minimizing a central circle's radius when circles of radii 1 to n are externally tangent around it. It solves an ordering problem using properties of a Supnick matrix, proving that a specific 'pyramid' order is optimal for realizable chains. It provides certified solutions for $n$ up to 14 and explores the limits of realizability.
Key concepts
- Ordering Problem
- This involves finding the best cyclic arrangement (order) of circles around a central circle to minimize its radius. The paper models this as a Supnick TSP, where the optimal order is determined by properties of a matrix related to angular separations between tangent circles.
- Supnick Matrix
- The matrix $\theta R(a, b)$ represents the minimum angular separation between the centers of two tangent circles with radii $a$ and $b$ around a central circle of radius $R$. This matrix has specific properties (symmetric anti-Monge) that allow for solving the ordering problem using classical theorems.
- Realizability and Certification
- The configuration described by an optimal order is not always geometrically possible for large $n$. The paper uses branch-and-bound methods and independent verifiers to certify global optima for small $n$ (up to 14), handling cases where one circle might 'float' or the configuration is not fully realizable.
- Supnick Tour ($\sigma^*$) and $\sigma^ op$
- The optimal ordering found is denoted as $\sigma^*$. The complementary tour, $\sigma^ op$, provides a related structure. The paper uses these tours to characterize the transition between different regimes of optimal solutions and to test finite necklace realizability.
Terminology used across episodes
This episode discusses
- Minimum central circles: chain order, seam obstructions, and exact finite certification · Paper Radio
- Minimum central circles: an effective characterization of the global asymptotic constant · Paper Radio
The paper
Minimum central circles: chain order, seam obstructions, and exact finite certification · Read on arXiv
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Minimum central circles".
Jane: Here's the gist of the paper. Circles of radii 1, 2,..., n are all externally tangent to a central circle, and the central radius R is minimized over cyclic orders of the surrounding circles This paper addresses the problem on three levels, keeping the epistemic status of each result explicit Ordering Problem Solution The ordering problem is a Supnick TSP, and writing θR(a, b) for the minimum angular separation between the centers of tangent circles of radii a and b at central radius R shows that the matrix θR(ri, rj) is symmetric anti-Monge for every R > 0 Minimizing total angle over cyclic orders is therefore a maximum traveling salesman problem on a Supnick matrix, which by a classical theorem of Supnick is solved by one fixed tour independent of the matrix entries This proves the conjectured “pyramid” order optimal whenever the corresponding chain necklace is geometrically realizable, and gives an unconditional lower bound in all cases The order σ∗ coincides with Dan’s conjectured pyramid arrangement Realizability and Finite Certification The closure equation (1) ignores nonadjacent pairs, and for n ≥ 8 the configuration it describes for σ∗ is not realizable The reported certified optima for 8 ≤ n ≤ 14 admit circle 1 as a floating circle, tangent only to the central circle The full problem is modeled as a circular system of pairwise angular constraints, equivalently a simple temporal network (STN), and global optima are certified for 3 ≤ n ≤ 14 using branch-and-bound plus an independent 50-digit verifier Quantitative Results and Regimes The paper reports certified optima for 3 ≤ n ≤ 14, with their high-precision reconstructions and reported binding/floating structure The transitions between regimes are governed by two computable properties of the Supnick tour on the reduced set of radii For instance, Proposition 9 shows that for 3 ≤ n ≤ 7 a reported optimal cycle is σ∗ on the set of all radii, as guaranteed by Theorem 6(iii) once realizability is checked Asymptotic Corrections and Open Problems The correction of the disproved v1 asymptotic conjecture shows that subsequent work proves a global asymptotic coefficient strictly larger than 1/8 The open problems include determining global finite optima beyond n = 14, characterizing floating circles with explicit quantifiers, and investigating the three-dimensional case of spheres tangent to a central sphere The fixed-order seam classification proves that for every fixed integer k ≥ 1 the canonical Supnick necklace on the set of radii eventually remains unrealizable at its chain root Table 1: Reported certified optima with global radius guard 10−10; incumbent reconstructions are rounded to 12 decimals (the unchanged 30-digit table is reproduced in the Appendix) Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits Table 5: Worst-arrangement comparison; Supnick min tour values Table 11: n Supnick min tour Rchain Rfull Table 3: The complementary Supnick tour σ† (Proposition 8): reported numerical chain values and finite necklace realizability Table 4: Certified optima, 30 significant digits <ref:2607.
Paper summary: Tom: So, looking at the paper "Minimum central circles: chain order, seam obstructions, and exact finite certification," it really boils down to a rigorous study of finding the smallest central circle radius R when you have circles of radii one through n packed around it.
Jane: And what this means for us is that they’ve provided a clear mathematical framework—a Supnick TSP ordering—that dictates the best possible arrangement, and they’ve shown exactly where that arrangement becomes physically impossible to build for larger numbers of circles.
Lu: The core finding is that the pyramid order works when it's realizable, giving an unconditional lower bound on R in all cases, but realizing that for n greater than eight, you have geometric obstructions.
Meng: For engineers like me, this means we need to be very careful when designing systems based on these models because if your number of components gets too high—say more than fourteen—the theoretical best solution might not actually fit in the physical space.
Tom: The paper’s title highlights that it tackles three things: the chain order, those seam obstructions, and getting exact finite certification for those small cases.
Jane: It's a lot of detail, but essentially they’ve given us a very precise map for small problems and told us exactly where the physical limitations start to show up as we scale up.
Conclusion: Tom: So, we’ve been looking at how to fit circles around a central one, and this paper is called "Minimum central circles: chain order, seam obstructions, and exact finite certification."
Jane: Right. It’s about finding the smallest possible radius for that central circle when you have a set of surrounding circles. The authors are focusing on the ordering problem first.
Lu: They tackle it as a Supnick Traveling Salesman Problem where the matrix has this specific symmetric anti-Monge property. This means they’re using a known mathematical tool to find the best possible cyclic arrangement, which they call the pyramid order.
Meng: But then they hit a snag because for larger numbers of circles, say more than eight, that ideal pyramid order just stops being physically possible to build. That's where the "seam obstructions" part comes in.
Tom: So what does that mean for us? It means if you’re building something with a lot of components and you want the tightest fit, you have to check if your layout is even geometrically sound before you even start calculating the size.
Jane: Exactly. And they provide some very concrete results for smaller numbers of circles, up to fourteen, with high precision on what those optimal layouts look like.
Lu: They also model it as a temporal network and used branch-and-bound to certify those optima for those specific ranges, which is pretty rigorous proof that the solution found is truly the best for that set of constraints.
Meng: For production, I’m more interested in what happens when you push beyond fourteen because that’s where my models start breaking down. If this ordering rule fails, it means we need a whole new way to think about packing these things efficiently at scale.
Tom: It seems like they aren't just giving us one answer for every problem, but mapping out exactly where the rules change based on the size of the set you’re dealing with.
Jane: And that leads us nicely into how these patterns eventually fail, and what happens when we look at those bigger numbers.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game