Penny-packings with minimal second moments

We consider the problem of packingn disks of unit diameter in the plane so as to minimize the second moment about their centroid. Our main result is an algorithm which constructs packings that are optimal among hexagonal packings. Using the algorithm, we prove that, except forn=212, then-point packings obtained by Graham and Sloane [1] are optimal among hexagonal packings. We also prove a result that makes precise the intuition that the greedy algorithm of Graham and Sloane produces approximately circular packings.     

Patterns and Structures in Disk Packings

Using a computational procedure that imitates tightening of an assembly of billiard balls, we have generated a number of packings of n equal and non-equal disks in regions of various shapes. Our experiments are of three major types. In the first type, the values of n are in thousands, the initial disk configuration is random and a priori one expects the generated packings to be random. In fact, the packings turn out to display non-random geometric patterns and regular features, including polycrystalline textures with "rattlers" typically trapped along the grain boundaries. An experiment of the second type begins with a known or conjectured optimal disk packing configuration, which is then "frustrated" by a small perturbation such as variation of the boundary shape or a relative increase of the size of a selected disk with respect to the sizes of the other disks. We present such frustrated packings for both large n (~ 10, 000) and small n (~ 50 to 200). Motivated by applications in material science and physics, the first and second type of experiments are performed for boundary shapes rarely discussed in the literature on dense packings: torus, a strip cut from a cylinder, a regular hexagon with periodic boundaries. Experiments of the third type involve the shapes popular among mathematicians: circles, squares, and equilateral triangles the boundaries of which are hard reflecting walls. The values of n in these experiments vary from several tens to few hundreds. Here the obtained configurations could be considered as candidates for the densest packings, rather than random ones. Some of these conjecturally optimal packings look regular and the regularity often extends across different values of n. Specifically, as n takes on an increasing sequence of values, n = n(1), n(2), ...n(k), ..., the packings follow a well-defined pattern. This phenomenon is especially striking for packings in equilateral triangles, where (as far as we can tell from our finite computational experiments), not only are there an infinite number of different patterns, each with its own different sequence n(1), n(2), ...n(k), ..., but many of these sequences seem to continue indefinitely. For other shapes, notably squares and circles, the patterns either cease to be optimal or even cease to exist (as packings of non-overlapping disks) above some threshold value n(k0) (depending on the pattern). In these cases, we try to identify the values of n(k0).     

Maximal partial packings of $${Z_2^n}$$ with perfect codes

A maximal partial Hamming packing of is a family of mutually disjoint translates of Hamming codes of length n, such that any translate of any Hamming code of length n intersects at least one of the translates of Hamming codes in . The number of translates of Hamming codes in is the packing number, and a partial Hamming packing is strictly partial if the family does not constitute a partition of . A simple and useful condition describing when two translates of Hamming codes are disjoint or not disjoint is proved. This condition depends on the dual codes of the corresponding Hamming codes. Partly, by using this condition, it is shown that the packing number p, for any maximal strictly partial Hamming packing of , n = 2 ^m −1, satisfies . It is also proved that for any n equal to 2 ^m −1, , there exist maximal strictly partial Hamming packings of with packing numbers n−10,n−9,n−8,...,n−1. This implies that the upper bound is tight for any n = 2 ^m −1, . All packing numbers for maximal strictly partial Hamming packings of , n = 7 and 15, are found by a computer search. In the case n = 7 the packing number is 5, and in the case n = 15 the possible packing numbers are 5,6,7,...,13 and 14.      

The Forest Hiding Problem

Let Ω be a disk of radius R in the plane. A set F of unit disks contained in Ω forms a maximal packing if the unit disks are pairwise interior-disjoint and the set is maximal, i.e., it is not possible to add another disk to F while maintaining the packing property. A point p is hidden within the “forest” defined by F if any ray with apex p intersects some disk of F, that is, a person standing at p can hide without being seen from outside the forest. We show that if the radius R of Ω is large enough, one can find a hidden point for any maximal packing of unit disks in Ω. This proves a conjecture of Joseph Mitchell. We also present an O(n ^5/2log n)-time algorithm that, given a forest with n (not necessarily congruent) disks, computes the boundary illumination map of all disks in the forest.     

Disk allocation methods for binary Cartesian product files

Since a file is usually stored on a disk, the response time to a query is dominated by the disk access time. In order to reduce the disk access time, a file can be stored on several independently accessible disks. In this paper, we discuss the problem of allocating buckets in a file among disks such that the maximum disk accessing concurrency can be achieved. We are particularly concerned with the disk allocation problem for binary Cartesian product files. A new allocation method is first proposed for the cases when the number (m) of available disks is a power of 2. Then it is extended to fit the cases wherem is not a power of 2. The proposed algorithm has a near strict optimal performance for a partial match query in which the number of unspecified attributes is greater than a small number (5 or 6).This work was supported in part by NSF Grant DCR-8405498.     

Existence and uniqueness of solutions to two point boundary value problems for ordinary differential equations

In this paper, using the optimal control method, we deal with the following boundary value problemy + f(x, y)=0,y(0)=c,y(1)=d, under new nonresonance conditions of the form –A f _y ^/ (x, y) (x) B, where A > 0. We obtain the existence and uniqueness of solutions of the BVP (1).     

Orthogonal packings inPG(5, 2)

Aspread inPG(n, q) is a set of lines which partitions the point set. A packing inPG(n, q) (n odd) is a partition of the lines into spreads. Two packings ofPG(n, q) are calledorthogonal if and only if any two spreads, one from each packing, have at most one line in common. Recently, R. D. Baker has shown the existence of a pair of orthogonal packings inPG(5, 2). In this paper we enumerate all packings inPG(5, 2) having both an automorphism of order 31 and the Frobenius automorphism. We find all pairs of orthogonal packings of the above type and display a set of six mutually orthogonal packings. Previously the largest set of orthogonal packings known inPG(5, 2) was two.     

Double-lattice packings of convex bodies in the plane

Mahler [7] and Fejes Tóth [2] proved that every centrally symmetric convex plane bodyK admits a packing in the plane by congruent copies ofK with density at least 3/2. In this paper we extend this result to all, not necessarily symmetric, convex plane bodies. The methods of Mahler and Fejes Tóth are constructive and produce lattice packings consisting of translates ofK. Our method is constructive as well, and it produces double-lattice packings consisting of translates ofK and translates of–K. The lower bound of 3/2 for packing densities produced here is an improvement of the bounds obtained previously in [5] and [6].     

Spiral hexagonal circle packings in the plane

We discuss an intriguing geometric algorithm which generates infinite spiral patterns of packed circles in the plane. Using Kleinian group and covering theory, we construct a complex parametrization of all such patterns and characterize those whose circles have mutually disjoint interiors. We prove that these coherent spirals, along with the regular hexagonal packing, give all possible hexagonal circle packings in the plane. Several examples are illustrated.The last two authors gratefully acknowledge support of the National Science Foundation and the Tennessee Science Alliance.     

Minimum perimeter rectangles that enclose congruent non-overlapping circles

We use computational experiments to find the rectangles of minimum perimeter into which a given number, n, of non-overlapping congruent circles can be packed. No assumption is made on the shape of the rectangles. In many of the packings found, the circles form the usual regular square-grid or hexagonal patterns or their hybrids. However, for most values of n in the tested range n≤5000, e.g., for n=7,13,17,21,22,26,31,37,38,41,43,…,4997,4998,4999,5000, we prove that the optimum cannot possibly be achieved by such regular arrangements. Usually, the irregularities in the best packings found for such n are small, localized modifications to regular patterns; those irregularities are usually easy to predict. Yet for some such irregular n, the best packings found show substantial, extended irregularities which we did not anticipate. In the range we explored carefully, the optimal packings were substantially irregular only for n of the form n=k(k+1)+1, k=3,4,5,6,7, i.e. for n=13,21,31,43, and 57. Also, we prove that the height-to-width ratio of rectangles of minimum perimeter containing packings of n congruent circles tends to 1 as n→∞.     

On the cardinality of blocking sets in PG(2,q)

Denote by PG(2,q) the finite desarguesian projective plane of order q, where q=p^h, p a prime, q>2. We define the function m(q) as follows: m(q)=q, if q is a square; m(q)=(q+1)/2, if q is a prime; m(q)=p^h–d, if q=p^h with h an odd integer, where d denotes the greatest divisor of h different from h. The following theorem is proved: For any integer k with q+m(q)+1 k q²–m(q), there exists a blocking set in PG(2,q) having exactly k elements.To Professor Adriano Barlotti on his 60th birthday.Research partially supported by G.N.S.A.G.A. (CNR)     

The region of values of the system {ƒ(z1), …, ƒ(zn)} in the class of typically real functions. II

The paper studies the region of values D_m,1(T) of the system {ƒ(z₁), ƒ(z₂), …, ƒ(zm), ƒ(r)}, m e 1, where z_j (j = 1, 2, …,m) are arbitrary fixed points of the disk U = {z: |z| < 1} with Im zj ≠ 0 (j = 1, 2, …,m), and r, 0 < r < 1, is fixed, in the class T of functions ƒ(z) = z+a₂z²+ ⋯ regular in the disk U and satisfying in the latter the condition Im ƒ(z) Imz > 0 for Im z ≠ 0. An algebraic characterization of the set D_m,1(T) in terms of nonnegative-definite Hermitian forms is given, and all the boundary functions are described. As an implication, the region of values of ƒ(z_m) in the subclass of functions from the class T with prescribed values ƒ(z_k) (k = 1, 2, …,m − 1) and ƒ(r) is determined. Bibliography: 5 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 323, 2005, pp. 24–33. Original article submitted June 13, 2005.     

A bound for Wilson''''s general theorem

Given any set K of positive integers and positive integer λ, let c(K,λ) denote the smallest integer such that v∈B(K,λ) for every integer v≥c(K,λ) that satisfies the congruences λv(v-1)≡0 (mod β(K) and λ(v-1)≡0 (mod α(K)). Let K0 be an equivalent set of K, k and k* be the smallest and the largest integers in K0. We prove that c(K,λ)≤exp exp{Q0}Qo=max{2(2p(ko)2-k2kk)p(ko)4,(Kk242y-k-2)(y2)}, whereand y=k*+k(k-1)+1.     

A generalized conjugate gradient algorithm for minimization

Summary A generalized conjugate gradient algorithm which is invariant to a nonlinear scaling of a strictly convex quadratic function is described, which terminates after at mostn steps when applied to scaled quadratic functionsf: R _n R₁ of the formf(x)=h(F(x)) withF(x) strictly convex quadratic andhC ¹ (R₁) an arbitrary strictly monotone functionh. The algorithm does not suppose the knowledge ofh orF but only off(x) and its gradientg(x).     

On a generalization of the Cauchy functional equation

Summary While looking for solutions of some functional equations and systems of functional equations introduced by S. Midura and their generalizations, we came across the problem of solving the equationg(ax + by) = Ag(x) + Bg(y) + L(x, y) (1) in the class of functions mapping a non-empty subsetP of a linear spaceX over a commutative fieldK, satisfying the conditionaP + bP P, into a linear spaceY over a commutative fieldF, whereL: X × X Y is biadditive,a, b K\{0}, andA, B F\{0}. Theorem.Suppose that K is either R or C, F is of characteristic zero, there exist A ₁,A ₂,B ₁,B ₂, F\ {0}with L(ax, y) = A ₁ L(x, y), L(x, ay) = A ₂ L(x, y), L(bx, y) = B ₁ L(x, y), and L(x, by) = B ₂ L(x, y) for x, y X, and P has a non-empty convex and algebraically open subset. Then the functional equation (1)has a solution in the class of functions g: P Y iff the following two conditions hold: L(x, y) = L(y, x) for x, y X, (2)if L 0, then A ₁ =A ₂,B ₁ =B ₂,A = A ₁ ² ,and B = B ₁ ² . (3) Furthermore, if conditions (2)and (3)are valid, then a function g: P Y satisfies the equation (1)iff there exist a y ₀ Y and an additive function h: X Y such that if A + B 1, then y ₀ = 0;h(ax) = Ah(x), h(bx) =Bh(x) for x X; g(x) = h(x) + y ₀ + 1/2A ₁ ^-1 B ₁ ^-1 L(x, x)for x P.     

P.I.G-rings and the contractability of primes

LetR=F{x ₁, …, x_k} be a prime affine p.i. ring andS a multiplicative closed set in the center ofR, Z(R). The structure ofG-rings of the formR _s is completely determined. In particular it is proved thatZ(R _s)—the normalization ofZ(R _s) —is a prüfer ring, 1≦k.d(R _s)≦p.i.d(R _s) and the inequalities can be strict. We also obtain a related result concerning the contractability ofq, a prime ideal ofZ(R) fromR. More precisely, letQ be a prime ideal ofR maximal to satisfyQϒZ(R)=q. Then k.dZ(R)/q=k.dR/Q, h(q)=h(Q) andh(q)+k.dZ(R)/q=k.dz(R). The last condition is a necessary butnot sufficient condition for contractability ofq fromR.     

Compact Packings of the Plane with Two Sizes of Discs

We consider packings of the plane using discs of radius 1 and r. A packing is compact if every disc D is tangent to a sequence of discs D₁, D₂, ..., D_n such that D_i is tangent to D_i+1. We prove that there are only nine values of r with r < 1 for which such packings are possible. For each of the nine values we describe the possible compact packings.     

Apollonian circle packings: Number theory II. Spherical and hyperbolic packings

Apollonian circle packings arise by repeatedly filling the interstices between mutually tangent circles with further tangent circles. In Euclidean space it is possible for every circle in such a packing to have integer radius of curvature, and we call such a packing an integral Apollonian circle packing. There are infinitely many different integral packings; these were studied in Part I (J. Number Theory 100, 1–45, 2003). Integral circle packings also exist in spherical and hyperbolic space, provided a suitable definition of curvature is used and again there are an infinite number of different integral packings. This paper studies number-theoretic properties of such packings. This amounts to studying the orbits of a particular subgroup of the group of integral automorphs of the indefinite quaternary quadratic form . This subgroup, called the Apollonian group, acts on integer solutions . This paper gives a reduction theory for orbits of acting on integer solutions to valid for all integer k. It also classifies orbits for all k≡0 (mod 4) in terms of an extra parameter n and an auxiliary class group (depending on n and k), and studies congruence conditions on integers in a given orbit. Much of this work was done while the authors were at AT&T Labs-Research, whom the authors thank for support. N. Eriksson was also supported by an NDSEG fellowship and J.C. Lagarias by NSF grant DMS-0500555.     

Asymptotics for the remainder of a class of positive quadratures for integrands with an interior singularity

Summary For functions with an interior singularity, the errors of a class of positive quadrature formulae with high algebraic degree are reduced to those of the much simpler Euler-Maclaurin type formulae. Applying this method to certain classes of functions, such as, for example,f(x)=h(x)|x-u| , where >–1, with a sufficiently smooth functionh, we obtain the main term of the error expansion for quadrature rules of ultraspherical type.     

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.