The simultaneous packing and covering constants in the plane

In 1950, C.A. Rogers introduced and studied two simultaneous packing and covering constants for a convex body and obtained the first general upper bound. Afterwards, these constants have attracted the interests of many authors because, besides their own geometric significance, they are closely related to the packing densities and the covering densities of the convex body, especially to the Minkowski-Hlawka theorem. However, so far our knowledge about them is still very limited. In this paper we will determine the optimal upper bound of the simultaneous packing and covering constants for two-dimensional centrally symmetric convex domains, and characterize the domains attaining this upper bound.     

Packing,covering and tiling in two-dimensional spaces

Packing, covering and tiling is a fascinating subject in pure mathematics. It mainly deals with arrangement patterns and efficiencies of geometric objects. This subject has a long and rich history, even back to Kepler, Newton, Lagrange and Gauss. Inspired by its applications and with the help of computing methods, in recent years it has become a very active research area in mathematics once again. Most of the fundamental problems in this subject can be characterized as simple sounding but challenging. This subject has important applications in many other areas such as Number Theory, Logic, Complex Analysis, Optimization, Coding Theory, Crystallography, Material Science, Industry, and even Biology. In spite of the long history, many of its key problems are still open, even in the plane. The purpose of this paper is to present a comprehensive review for packing, covering and tiling in the two-dimensional spaces. We will focus on the key problems, the fundamental results, the creative ideas, some important applications, and some significant connections with other areas.     

On the Packing Densities and the Covering Densities of the Cartesian Products of Convex Bodies

In this article we study the following problem: Is the covering (packing) density of a Cartesian product of two convex bodies always equal to the product of their corresponding covering (packing) densities? For the covering case we get a negative answer. For the packing case we get a combinatorial version which seems to be important for its own interest.     

On projections of arbitrary lattices

In this paper we prove that given any two point lattices _Λ1⊂Rⁿ${\Lambda }_1\subset {\mathbb{R}}^n$ and _Λ2⊂R^n−k${\Lambda }_2\subset {\mathbb{R}}^{n-k}$, there is a set of k   vectors {_v1,…,_vk}⊂_Λ1$\{{\mathit{v}}_1,\dots ,{\mathit{v}}_k\}\subset {\Lambda }_1$ such that _Λ2${\Lambda }_2$ is, up to similarity, arbitrarily close to the projection of _Λ1${\Lambda }_1$ onto the orthogonal complement of the subspace spanned by {_v1,…,_vk}$\{{\mathit{v}}_1,\dots ,{\mathit{v}}_k\}$. This result extends the main theorem of Sloane et al. (2011) [1] and has applications in communication theory.     

An optimal lower bound for the Frobenius problem

Given N?2 positive integers a₁,a₂,…,aN with GCD(a₁,…,aN)=1, let fN denote the largest natural number which is not a positive integer combination of a₁,…,aN. This paper gives an optimal lower bound for fN in terms of the absolute inhomogeneous minimum of the standard (N−1)-simplex.     

Lattice translates of a polytope and the Frobenius problem

This paper considers the Frobenius problem: Givenn natural numbersa ₁,a ₂,...a _n such that their greatest common divisor is 1, find the largest natural number that is not expressible as a nonnegative integer combination of them. This problem can be seen to be NP-hard. For the casesn=2,3 polynomial time algorithms, are known to solve it. Here a polynomial time algorithm is given for every fixedn. This is done by first proving an exact relation between the Frobenius problem and a geometric concept called the covering radius. Then a polynomial time algorithm is developed for finding the covering radius of any polytope in a fixed number of dimensions. The last algorithm relies on a structural theorem proved here that describes for any polytopeK, the setK+ ^h ={xx ⁿ ;x=y+z;yK;z ⁿ } which is the portion of space covered by all lattice translates ofK. The proof of the structural theorem relies on some recent developments in the Geometry of Numbers. In particular, it uses a theorem of Kannan and Lovász [11], bounding the width of lattice-point-free convex bodies and the techniques of Kannan, Lovász and Scarf [12] to study the shapes of a polyhedron obtained by translating each facet parallel, to itself. The concepts involved are defined from first principles. In a companion paper [10], I extend the structural result and use that to solve a general problem of which the Frobenius problem is a special case.Supported by NSF-Grant CCR 8805199     

Some remarks concerning kissing numbers,blocking numbers and covering numbers

This article shows an inequality concerning blocking numbers and Hadwiger's covering numbers and presents a strange phenomenon concerning kissing numbers and blocking numbers. As a simple corollary, we can improve the known upper bounds for Hadwiger's covering numbers ford-dimensional centrally symmetric convex bodies to 3 ^d –1.     

Rational and Heron tetrahedra

Buchholz [R.H. Buchholz, Perfect pyramids, Bull. Austral. Math. Soc. 45 (1991) 353-368] began a systematic search for tetrahedra having integer edges and volume by restricting his attention to those with two or three different edge lengths. Of the fifteen configurations identified for such tetrahedra, Buchholz leaves six unsolved. In this paper we examine these remaining cases for integer volume, completely solving all but one of them. Buchholz also considered Heron tetrahedra, which are tetrahedra with integral edges, faces and volume. Buchholz described an infinite family of Heron tetrahedra for one of the configurations. Another of the cases yields a new infinite family of Heron tetrahedra which correspond to the rational points on a two-parameter elliptic curve.     

Simultaneous Packing and Covering in the Euclidean Plane

 In this article we study the simultaneous packing and covering constants of two-dimensional centrally symmetric convex domains. Besides an identity result between translative case and lattice case and a general upper bound, exact values for some special domains are determined. Similar to Mahler and Reinhardt’s result about packing densities, we show that the simultaneous packing and covering constant of an octagon is larger than that of a circle. (Received 17 January 2001; in revised form 13 July 2001)     

Effective equidistribution and the Sato-Tate law for families of elliptic curves

Text

Extending recent work of others, we provide effective bounds on the family of all elliptic curves and one-parameter families of elliptic curves modulo p (for p prime tending to infinity) obeying the Sato-Tate law. We present two methods of proof. Both use the framework of Murty and Sinha (2009) [MS]; the first involves only knowledge of the moments of the Fourier coefficients of the L-functions and combinatorics, and saves a logarithm, while the second requires a Sato-Tate law. Our purpose is to illustrate how the caliber of the result depends on the error terms of the inputs and what combinatorics must be done.

Video

For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=faW2iDpe5IE.     

On integral Apollonian circle packings

The curvatures of four mutually tangent circles with disjoint interiors form what is called a Descartes quadruple. The four least curvatures in an integral Apollonian circle packing form what is called a root Descartes quadruple and, if the curvatures are relatively prime, we say that it is a primitive root quadruple. We prove a conjecture of Mallows by giving a closed formula for the number of primitive root quadruples with minimum curvature −n. An Apollonian circle packing is called strongly integral if every circle has curvature times center a Gaussian integer. The set of all such circle packings for which the curvature plus curvature times center is congruent to 1 modulo 2 is called the “standard supergasket.” Those centers in the unit square are in one-to-one correspondence with the primitive root quadruples and exhibit certain symmetries first conjectured by Mallows. We prove these symmetries; in particular, the centers are symmetric around y=x if n is odd, around x=1/2 if n is an odd multiple of 2, and around y=1/2 if n is a multiple of 4.     

Perfect, strongly eutactic lattices are periodic extreme

We introduce a parameter space for periodic point sets, given as unions of m translates of point lattices. In it we investigate the behavior of the sphere packing density function and derive sufficient conditions for local optimality. Using these criteria we prove that perfect, strongly eutactic lattices cannot be locally improved to yield a periodic sphere packing with greater density. This applies in particular to the densest known lattice sphere packings in dimension d?8 and d=24.     

On the supremum of the pseudocompact group topologies

P is the class of pseudocompact Hausdorff topological groups, and P^′ is the class of groups which admit a topology T such that (G,T)∈P. It is known that every G=(G,T)∈P is totally bounded, so for G∈P^′ the supremum T^∨(G) of all pseudocompact group topologies on G and the supremum T#(G) of all totally bounded group topologies on G satisfy T^∨⊆T#.The authors conjecture for abelian G∈P^′ that T^∨=T#. That equality is established here for abelian G∈P^′ with any of these (overlapping) properties. (a) G is a torsion group; (b) |G|?c²; (c) r₀(G)=|G|=ω|G|; (d) |G| is a strong limit cardinal, and r₀(G)=|G|; (e) some topology T with (G,T)∈P satisfies w(G,T)?c; (f) some pseudocompact group topology on G is metrizable; (g) G admits a compact group topology, and r₀(G)=|G|. Furthermore, the product of finitely many abelian G∈P^′, each with the property T^∨(G)=T#(G), has the same property.     

The structure of d-dimensional sets with small sumset

We describe the structure of d-dimensional sets of lattice points, having a small doubling property. Let K be a finite subset of Zd such that dimK=d?2. If and |K|>3⋅d⁴, then K lies on d parallel lines. Moreover, for every d-dimensional finite set K⊆Zd that lies on d?1 parallel lines, if , then K is contained in d parallel arithmetic progressions with the same common difference, having together no more than terms. These best possible results answer a recent question posed by Freiman and cannot be sharpened by reducing the quantity v or by increasing the upper bounds for |K+K|.     

On the Nochka-Chen-Ru-Wong proof of Cartan's conjecture

In 1982-1983, E. Nochka proved a conjecture of Cartan on defects of holomorphic curves in Pn relative to a possibly degenerate set of hyperplanes. This was further explained by W. Chen in his 1987 thesis, and subsequently simplified by M. Ru and P.-M. Wong in 1991. The proof involved assigning weights to the hyperplanes. This paper provides further simplification of the proof of the construction of the weights, by bringing back the use of the convex hull in working with the “Nochka diagram.”     

A refinement of the Bernštein-Kušnirenko estimate

A theorem of Kušnirenko and Bernštein (also known as the BKK theorem) shows that the number of isolated solutions in a torus to a system of polynomial equations is bounded above by the mixed volume of the Newton polytopes of the given polynomials, and this upper bound is generically exact. We improve on this result by introducing refined combinatorial invariants of polynomials and a generalization of the mixed volume of convex bodies: the mixed integral of concave functions. The proof is based on new techniques and results from relative toric geometry.     

On the Dirichlet—Voronoi cell of unimodular lattices

This paper consists of two results concerning the Dirichlet-Voronoi cell of a lattice. The first one is a geometric property of the cell of an integral unimodular lattice while the second one gives a characterization of all those lattice vectors of an arbitrary lattice whose multiples by 1/2 are on the boundary of the cell containing the origin. This result is a generalization of a well-known theorem of Voronoi characterizing the so-called relevants of the cell.Supported by Hung. Nat. Found. for Sci. Research (OTKA) grant No. T.7351 (1994).     

Triangular array limits for continuous time random walks

A continuous time random walk (CTRW) is a random walk subordinated to a renewal process, used in physics to model anomalous diffusion. Transition densities of CTRW scaling limits solve fractional diffusion equations. This paper develops more general limit theorems, based on triangular arrays, for sequences of CTRW processes. The array elements consist of random vectors that incorporate both the random walk jump variable and the waiting time preceding that jump. The CTRW limit process consists of a vector-valued Lévy process whose time parameter is replaced by the hitting time process of a real-valued nondecreasing Lévy process (subordinator). We provide a formula for the distribution of the CTRW limit process and show that their densities solve abstract space–time diffusion equations. Applications to finance are discussed, and a density formula for the hitting time of any strictly increasing subordinator is developed.     

Largest integral simplices with one interior integral point: Solution of Hensley's conjecture and related results

For each dimension d, d-dimensional integral simplices with exactly one interior integral point have bounded volume. This was first shown by Hensley. Explicit volume bounds were determined by Hensley, Lagarias and Ziegler, Pikhurko, and Averkov. In this paper we determine the exact upper volume bound for such simplices and characterize the volume-maximizing simplices. We also determine the sharp upper bound on the coefficient of asymmetry of an integral polytope with a single interior integral point. This result confirms a conjecture of Hensley from 1983. Moreover, for an integral simplex with precisely one interior integral point, we give bounds on the volumes of its faces, the barycentric coordinates of the interior integral point and its number of integral points. Furthermore, we prove a bound on the lattice diameter of integral polytopes with a fixed number of interior integral points. The presented results have applications in toric geometry and in integer optimization.