Finite and Uniform Stability of Sphere Packings

The main purpose of this paper is to discuss how firm or steady certain known ball packing are, thinking of them as structures. This is closely related to the property of being locally maximally dense. Among other things we show that many of the usual best-known candidates, for the most dense packings with congruent spherical balls, have the property of being uniformly stable, i.e., for a sufficiently small ε > 0 every finite rearrangement of the balls of this packing, where no ball is moved more than ε , is the identity rearrangement. For example, the lattice packings D _d and A _d for d ≥ 3 in E ^d are all uniformly stable. The methods developed here can work for many other packings as well. We also give a construction to show that the densest cubic lattice ball packing in E ^d for d ≥ 2 is not uniformly stable. A packing of balls is called finitely stable if any finite subfamily of the packing is fixed by its neighbors. If a packing is uniformly stable, then it is finitely stable. On the other hand, the cubic lattice packings mentioned above, which are not uniformly stable, are nevertheless finitely stable. Received April 22, 1996, and in revised form October 11, 1996.     

Finite sphere packing and sphere covering

A basic problem of finite packing and covering is to determine, for a given number ofk unit balls in Euclideand-spaceE ^d , (1) the minimal volume of all convex bodies into which thek balls can be packed and (2) the maximal volume of all convex bodies which can be covered by thek balls. In the sausage conjectures by L. Fejes Tóth and J. M. Wills it is conjectured that, for alld5, linear arrangements of thek balls are best possible. In the paper several partial results are given to support both conjectures. Furthermore, some relations between finite and infinite (space) packing and covering are investigated.This paper was written while the first named author was visiting the Forschungsinstitut für Geistes- und Sozialwissenschaften at the University of Siegen.     

Highly saturated packings and reduced coverings

We introduce and study certain notions which might serve as substitutes for maximum density packings and minimum density coverings. A body is a compact connected set which is the closure of its interior. A packingP with congruent replicas of a bodyK isn-saturated if non–1 members of it can be replaced withn replicas ofK, and it is completely saturated if it isn-saturated for eachn1. Similarly, a coveringC with congruent replicas of a bodyK isn-reduced if non members of it can be replaced byn–1 replicas ofK without uncovering a portion of the space, and its is completely reduced if it isn-reduced for eachn1. We prove that every bodyK ind-dimensional Euclidean or hyperbolic space admits both ann-saturated packing and ann-reduced covering with replicas ofK. Under some assumptions onKE ^d (somewhat weaker than convexity), we prove the existence of completely saturated packings and completely reduced coverings, but in general, the problem of existence of completely saturated packings, and completely reduced coverings remains unsolved. Also, we investigate some problems related to the the densities ofn-saturated packings andn-reduced coverings. Among other things, we prove that there exists an upper bound for the density of ad+2-reduced covering ofE ^d with congruent balls, and we produce some density bounds for then-saturated packings andn-reduced coverings of the plane with congruent circles.     

Improving Rogers' Upper Bound for the Density of Unit Ball Packings via Estimating the Surface Area of Voronoi Cells from Below in Euclidean \sl d -Space for All \sl d ≥ \bf 8

   Abstract. The sphere packing problem asks for the densest packing of unit balls in E ^d . This problem has its roots in geometry, number theory and information theory and it is part of Hilbert's 18th problem. One of the most attractive results on the sphere packing problem was proved by Rogers in 1958. It can be phrased as follows. Take a regular d -dimensional simplex of edge length 2 in E ^d and then draw a d -dimensional unit ball around each vertex of the simplex. Let σ _d denote the ratio of the volume of the portion of the simplex covered by balls to the volume of the simplex. Then the volume of any Voronoi cell in a packing of unit balls in E ^d is at least ω _d /σ _d , where ω _d denotes the volume of a d -dimensional unit ball. This has the immediate corollary that the density of any unit ball packing in E ^d is at most σ _d . In 1978 Kabatjanskii and Levenštein improved this bound for large d . In fact, Rogers' bound is the presently known best bound for 4≤ d≤ 42 , and above that the Kabatjanskii—Levenštein bound takes over. In this paper we improve Rogers' upper bound for the density of unit ball packings in Euclidean d -space for all d≥ 8 and improve the Kabatjanskii—Levenštein upper bound in small dimensions. Namely, we show that the volume of any Voronoi cell in a packing of unit balls in E ^d , d≥ 8 , is at least ω _d /

Locally dense finite lattice packings of spheres

We consider finite packings of unit-balls in Euclidean 3-spaceE ³ where the centres of the balls are the lattice points of a lattice polyhedronP of a given latticeL ³E³. In particular we show that the facets ofP induced by densest sublattices ofL ³ are not too close to the next parallel layers of centres of balls. We further show that the Dirichlet-Voronoi-cells are comparatively small in this direction. The paper was stimulated by the fact that real crystals in general grow slowly in the directions normal to these dense facets.The results support, to some extent, the hypothesis that real crystals grow preferably such that they need little volume, i.e that they are locally dense.Dedicated to A. Florian on the occasion of this 60th birthday     

Every Banach space with a <Emphasis Type="Italic">w</Emphasis><Superscript>*</Superscript>-separable dual has a 1+<Emphasis Type="Italic">ɛ</Emphasis>-equivalent norm with the ball covering property

A normed space is said to have ball-covering property if its unit sphere can be contained in the union of countably many open balls off the origin. This paper shows that for every ɛ > 0 every Banach space with a w ^*-separable dual has a 1+ɛ-equivalent norm with the ball covering property.     

Note on induced subgraphs of the unit distance graphE n

The unit distance graphE ⁿ is the graph whose vertices are the points in Euclideann-space, and two vertices are adjacent if and only if the distance between them is 1. We prove that for anyn there is a finite bipartite graph which cannot be embedded inE ⁿ as an induced subgraph and that every finite graph with maximum degreed can be embedded inE ^N ,N=(d ³ –d)/2, as an induced subgraph.     

Self-similar sets with optimal coverings and packings

We prove that if a self-similar set E in Rn with Hausdorff dimension s satisfies the strong separation condition, then the maximal values of the Hs-density on the class of arbitrary subsets of Rn and on the class of Euclidean balls are attained, and the inverses of these values give the exact values of the Hausdorff and spherical Hausdorff measure of E. We also show that a ball of minimal density exists, and the inverse density of this ball gives the exact packing measure of E. Lastly, we show that these elements of optimal densities allow us to construct an optimal almost covering of E by arbitrary subsets of Rn, an optimal almost covering of E by balls and an optimal packing of E.     

VORONOI POLYHEDRA OF UNIT BALL PACKINGS WITH SMALL SURFACE AREA

In this note, first, we give a very short new proof of the theorem which yields a lower bound for the surface area of Voronoi cells of unit ball packings in E ^d and implies Rogers' upper bound for the density of unit ball packings in E ^d for all d ≥ 2. Second we sharpen locally a classical result of Gauss by finding the locally smallest surface area Voronoi cells of lattice unit ball packings in E ³. This revised version was published online in August 2006 with corrections to the Cover Date.     

Tiling convex sets by translates

LetK be a compact, convex subset ofE ^dwhich can be tiled by a finite number of disjoint (on interiors) translates of some compact setY. Then we may writeK=X+Y, whereX is finite. The possible structures forK, X andY are completely determined under these conditions.     

Helly-Type Theorems for Line Transversals to Disjoint Unit Balls

We prove Helly-type theorems for line transversals to disjoint unit balls in ℝ ^d . In particular, we show that a family of n≥2d disjoint unit balls in ℝ ^d has a line transversal if, for some ordering ≺ of the balls, any subfamily of 2d balls admits a line transversal consistent with ≺. We also prove that a family of n≥4d−1 disjoint unit balls in ℝ ^d admits a line transversal if any subfamily of size 4d−1 admits a transversal. Andreas Holmsen was supported by the Research Council of Norway, prosjektnummer 166618/V30. Otfried Cheong and Xavier Goaoc acknowledge support from the French-Korean Science and Technology Amicable Relationships program (STAR).     

Existence,uniqueness, and algorithmic computation of general lilypond systems

The lilypond system based on a locally finite subset φ of the Euclidean space ?ⁿ is defined as follows. At time 0 every point of φ starts growing with unit speed in all directions to form a system of balls in which any particular ball ceases its growth at the instant that it collides with another ball. Based on a more formal definition of lilypond systems given in 1 , we will prove that these systems exist and are uniquely determined. Our approach applies to the far more general setting, where φ is a locally finite subset of some space ?? equipped with a pseudo‐metric d. We will also derive an algorithm approximating the system with at least linearly decreasing error. Several examples will illustrate our general results. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

The Choquet integral representation in the affine vector-valued case

LetX be any compact convex subset of a locally convex Hausdorff space andE be a complex Banach space. We denote byA(X, E) the space of all continuous and affineE-valued functions defined onX. In this paper we prove thatX is a Choquet simplex if and only if the dual ofA(X, E) is isometrically isomorphic by a selection map toM _m (X, E*), the space ofE*-valued,w*-regular boundary measures onX. This extends and strengthens a result of G. M. Ustinov. To do this we show that for any compact convex setX, each element of the dual ofA(X, E) can be represented by a measure inM _m (X, E*) with the same norm, and this representation is unique if and only ifX is a Choquet simplex. We also prove that ifX is metrizable andE is separable then there exists a selection map from the unit ball of the dual ofA(X, E) into the unit ball ofM _m (X, E*) which is weak* to weak*-Borel measurable.This work will constitute a portion of the author's Ph.D. Thesis at the University of Illinois.     

Randomized allocation processes

Many dynamic resource allocation and on‐line load balancing problems can be modeled by processes that sequentially allocate balls into bins. The balls arrive one by one and are to be placed into bins on‐line without using a centralized controller. If n balls are sequentially placed into n bins by placing each ball in a randomly chosen bin, then it is widely known that the maximum load in bins is ln n /ln ln n?(1+o(1)) with high probability. Azar, Broder, Karlin, and Upfal extended this scheme, so that each ball is placed sequentially into the least full of d randomly chosen bins. They showed that the maximum load of the bins reduces exponentially and is ln ln n/In d+Θ(1) with high probability, provided d<2. In this paper we investigate various extensions of these schemes that arise in applications in dynamic resource allocation and on‐line load balancing. Traditionally, the main aim of allocation processes is to place balls into bins to minimize the maximum load in bins. However, in many applications it is equally important to minimize the number of choices performed (the allocation time). We study adaptive allocation schemes that achieve optimal tradeoffs between the maximum load, the maximum allocation time, and the average allocation time. We also investigate allocation processes that may reallocate the balls. We provide a tight analysis of a natural class of processes that each time a ball is placed in one of d randomly chosen bins may move balls among these d bins arbitrarily. Finally, we provide a tight analysis of the maximum load of the off‐line process in which each ball may be placed into one of d randomly chosen bins. We apply this result to competitive analysis of on‐line load balancing processes. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 297–331, 2001     

On combinatorial and affine automorphisms of polytopes

We disprove the longstanding conjecture that every combinatorial automorphism of the boundary complex of a convex polytope in euclidean spaceE ^d can be realised by an affine transformation ofE ^d .     

The structure of injective covers of special modules

In this paper, we prove that the injective cover of theR-moduleE(R/B)/R/B for a prime ideal B ofR is the direct sum of copies ofE(R/B) for prime ideals D ⊃ B, and if B is maximal, the injective cover is a finite sum of copies ofE(R/B). For a finitely generatedR-moduleM withn generators andG an injectiveR-module, we argue that the natural mapG ⁿ →G ⁿ/Hom _R (M, G) is an injective precover if Ext _R ¹ (M, R) = 0, and that the converse holds ifG is an injective cogenerator ofR. Consequently, for a maximal ideal R ofR, depth_R R ≧ 2 if and only if the natural mapE(R/R) →E(R/R)/R/R is an injective cover and depth_R R > 0.     

On the covering multiplicity of lattices

Let the lattice Λ have covering radiusR, so that closed balls of radiusR around the lattice points just cover the space. The covering multiplicityCM(Λ) is the maximal number of times the interiors of these balls overlap. We show that the least possible covering multiplicity for ann-dimensional lattice isn ifn≤8, and conjecture that it exceedsn in all other cases. We determine the covering multiplicity of the Leech lattice and of the latticesI _n, A_n, D_n, E_n and their duals for small values ofn. Although it appears thatCM(I _n)=2 ⁿ⁻¹ ifn≤33, asn → ∞ we haveCM(I _n)∼2.089... ⁿ . The results have application to numerical integration.     

On the product of twists of rank two and a conjecture of Larsen

In this note we present examples of elliptic curves and infinite parametric families of pairs of integers (d,d′) such that, if we assume the parity conjecture, we can show that E ^d ,E ^d′ and E ^dd′ are all of positive even rank over ℚ. As an application, we show examples where a conjecture of M. Larsen holds.      

The Complexity of Definite Elliptic Problems with Noisy Data

We study the complexity of 2mth order definite elliptic problemsLu=f(with homogeneous Dirichlet boundary conditions) over ad-dimensional domain Ω, error being measured in theH^m(Ω)-norm. The problem elementsfbelong to the unit ball ofW^r,p(Ω), wherep∈ [2, ∞] andr>d/p. Information consists of (possibly adaptive) noisy evaluations offor the coefficients ofL. The absolute error in each noisy evaluation is at most δ. We find that thenth minimal radius for this problem is proportional ton^−r/d+ δ, and that a noisy finite element method with quadrature (FEMQ), which uses only function values, and not derivatives, is a minimal error algorithm. This noisy FEMQ can be efficiently implemented using multigrid techniques. Using these results, we find tight bounds on the ?-complexity (minimal cost of calculating an ?-approximation) for this problem, said bounds depending on the costc(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation isc(δ) = δ^−s(fors> 0), then the complexity is proportional to (1/?)^d/r+s.     

Theorems on the existence of separating surfaces

LetR andG be finite of sets inE ^d. This paper presents theorems on the existence of strict linear and spherical separators ofR andG that are similar to the fundamental separation theorem of Kirchberger. Kirchberger's theorem impliet that the strict linear separability of finite setsR andG is determined by the separability of all subsets of up tod+2 points ofR⊃G. This paper shows that under certain conditions, the linear separability ofR andG is determined by the separability of significantly fewer than all subfamilies of up tod+2 members ofR ⊃G. The same treatment is made of Lay's extension of Kirchberger's theorem to separation by hyperspheres. This research was supported by a PGS3 scholarship from NSERC.