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     

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.     

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.     

On finite lattice coverings

We consider finite lattice coverings of strictly convex bodies K. For planar centrally symmetric K we characterize the finite arrangements C _n such that conv , where C _n is a subset of a covering lattice for K (which satisfies some natural conditions). We prove that for a fixed lattice the optimal arrangement (measured with the parametric density) is either a sausage, a so-called double sausage or tends to a Wulff-shape, depending on the parameter. This shows that the Wulff-shape plays an important role for packings as well as for coverings. Further we give a version of this result for variable lattices. For the Euclidean d-ball we characterize the lattices, for which the optimal arrangement is a sausage, for large parameter. Received 19 May 1999.     

Saturated packings and reduced coverings obtained by perturbing tilings

Let a normed space X possess a tiling T consisting of unit balls. We show that any packing P of X obtained by a small perturbation of T is completely translatively saturated; that is, one cannot replace finitely many elements of P by a larger number of unit balls such that the resulting arrangement is still a packing.In contrast with that, given a tiling T of Rⁿ with images of a convex body C under Euclidean isometries, there may exist packings P consisting of isometric images of C obtained from T by arbitrarily small perturbations which are no longer completely saturated. This means that there exists some positive integer k such that one can replace k−1 members of P by k isometric copies of C without violating the packing property. However, we quantify a tradeoff between the size of the perturbation and the minimal k such that the above phenomenon occurs.Analogous results are obtained for coverings.     

Constructions of uniform designs by using resolvable packings and coverings

Uniform designs have been widely used in computer experiments, as well as in industrial experiments when the underlying model is unknown. Based on the discrete discrepancy, the link between uniform designs, and resolvable packings and coverings in combinatorial theory is developed. Through resolvable packings and coverings without identical parallel classes, many infinite classes of new uniform designs are then produced.     

Maximal resolvable packings and minimal resolvable coverings of triples by quadruples

Determination of maximal resolvable packing number and minimal resolvable covering number is a fundamental problem in designs theory. In this article, we investigate the existence of maximal resolvable packings of triples by quadruples of order v (MRPQS(v)) and minimal resolvable coverings of triples by quadruples of order v (MRCQS(v)). We show that an MRPQS(v) (MRCQS(v)) with the number of blocks meeting the upper (lower) bound exists if and only if v≡0 (mod 4). As a byproduct, we also show that a uniformly resolvable Steiner system URS(3, {4, 6}, {r₄, r₆}, v) with r₆≤1 exists if and only if v≡0 (mod 4). All of these results are obtained by the approach of establishing a new existence result on RH(6²ⁿ) for all n≥2. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 209–223, 2010     

Tilings,packings, coverings,and the approximation of functions

A packing (resp. covering) ? of a normed space X consisting of unit balls is called completely saturated (resp. completely reduced) if no finite set of its members can be replaced by a more numerous (resp. less numerous) set of unit balls of X without losing the packing property (resp. covering property) of ?. We show that a normed space X admits completely saturated packings with disjoint closed unit balls as well as completely reduced coverings with open unit balls, provided that there exists a tiling of X with unit balls. Completely reduced coverings by open balls are of interest in the context of an approximation theory for continuous real‐valued functions that rests on so‐called controllable coverings of compact metric spaces. The close relation between controllable coverings and completely reduced coverings allows an extension of the approximation theory to non‐compact spaces. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On linear sections of lattice packings

Ind-dimensional euclidean spaceE ^d letP be a lattice packing of subsets ofE ^d , and letH be ak-dimensional linear subspace ofE ^d (0<k<d). Then,P induces a packing inH consisting of all setsPH withPP. The relationship between the density of this packing inH and the density ofP is investigated. A result from the theory of uniform distribution of linear forms is used to prove an integral formula that enables one to evaluate the density of the induced packing inH (under suitable assumptions on the sets ofP and the functionals used to define the densities). It is shown that this result leads to explicit formulas for the averages of the induced densities under the rotation ofH. If the densities are taken with respect to the mean cross-sectional measures of convex bodies one obtains analogues of the integral geometric intersection formulas of Crofton.Dedicated to Professor E. Hlawka on the occasion of his seventieth birthdaySupported by National Science Foundation Research Grant DMS 8300825.     

A criterion for finite lattice coverings

For a centrally symmetric convex and a covering lattice L for K, a lattice polygon P is called a covering polygon, if . We prove that P is a covering polygon, if and only if its boundary bd(P) is covered by (L ∩ P) + K. Further we show that this characterization is false for non-symmetric planar convex bodies and in Euclidean d–space, d ≥ 3, even for the unit ball K = B ^d. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Gilbert-Varshamov-type bound for lattice packings

A Gilbert-Varshamov-type bound for Euclidean packings was recently found by Nebe and Xing. In this present paper, we derive a Gilbert-Varshamov-type bound for lattice packings by generalizing Rush's approach of combining p-ary codes with the lattice pZn. Specifically, we will exploit suitable sublattices of Zn as well as lattices of number fields in our construction. Our approach allows us to compute the center densities of lattices of moderately large dimensions which compare favorably with the best known densities given in the literature as well as the densities derived directly via Rush's method.     

Economical coverings of sets of lattice points

Lett(n, d) be the minimum numbert such that there aret of then ^d lattice points

Minkowski bisectors,Minkowski cells and lattice coverings

We prove Barth-type connectedness results for low-codimension smooth subvarieties with good numerical properties inside certain “easy” ambient spaces (such as homogeneous varieties, or spherical varieties). The argument employs some basics from the theory of cones of cycle classes, in particular the notion of bigness of a cycle class.     

Slope packings and coverings,and generic algorithms for the discrete logarithm problem

We consider the set of slopes of lines formed by joining all pairs of points in some subset S of a Desarguesian affine plane of prime order p. If all the slopes are distinct and non‐infinite, we have a slope packing; if every possible non‐infinite slope occurs, then we have a slope covering. We review and unify some results on these problems that can be derived from the study of Sidon sets and sum covers. Then we report some computational results, we have obtained for small values of p. Finally, we point out some connections between slope packings and coverings and generic algorithms for the discrete logarithm problem in prime order (sub)groups. Our results provide a combinatorial characterization of such algorithms, in the sense that any generic algorithm implies the existence of a certain slope packing or covering, and conversely. © 2002 Wiley Periodicals, Inc. J Combin Designs 11: 36–50, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10033