A fascinating polynomial sequence arising from an electrostatics problem on the sphere

A positive unit point charge approaching from infinity a perfectly spherical isolated conductor carrying a total charge of +1 will eventually cause a negatively charged spherical cap to appear. The determination of the smallest distance ρ(d) (d is the dimension of the unit sphere) from the point charge to the sphere where still all of the sphere is positively charged is known as Gonchar’s problem. Using classical potential theory for the harmonic case, we show that 1+ρ(d) is equal to the largest positive zero of a certain sequence of monic polynomials of degree 2d?1 with integer coefficients which we call Gonchar polynomials. Rather surprisingly, ρ(2)?is the Golden ratio and ρ(4) the lesser known Plastic number. But Gonchar polynomials have other interesting properties. We discuss their factorizations, investigate their zeros and present some challenging conjectures.     

Packing polyominoes clumsily

For a set D of polyominoes, a packing of the plane with D is a maximal set of copies of polyominoes from D that are not overlapping. A packing with smallest density is called a clumsy packing. We give an example of a set D such that any clumsy packing is aperiodic. In addition, we compute the smallest possible density of a clumsy packing when D consists of a single polyomino of a given size and show that one can always construct a periodic packing arbitrarily close in density to the clumsy packing.     

Lattices from elliptic curves over finite fields

In their well known book [6] Tsfasman and Vladut introduced a construction of a family of function field lattices from algebraic curves over finite fields, which have asymptotically good packing density in high dimensions. In this paper we study geometric properties of lattices from this construction applied to elliptic curves. In particular, we determine the generating sets, conditions for well-roundedness and a formula for the number of minimal vectors. We also prove a bound on the covering radii of these lattices, which improves on the standard inequalities.     

Riesz extremal measures on the sphere for axis-supported external fields

We investigate the minimal Riesz s-energy problem for positive measures on the d-dimensional unit sphere Sd in the presence of an external field induced by a point charge, and more generally by a line charge. The model interaction is that of Riesz potentials |x−y|^−s with d−2?s<d. For a given axis-supported external field, the support and the density of the corresponding extremal measure on Sd is determined. The special case s=d−2 yields interesting phenomena, which we investigate in detail. A weak^∗ asymptotic analysis is provided as s→⁺(d−2).     

Globally optimized packings of non-uniform size spheres in $$\mathbb {R}^{d}$$: a computational study

In this work we discuss the following general packing problem: given a finite collection of d-dimensional spheres with (in principle) arbitrarily chosen radii, find the smallest sphere in \(\mathbb {R}^{d}\) that contains the given d-spheres in a non-overlapping arrangement. Analytical (closed-form) solutions cannot be expected for this very general problem-type: therefore we propose a suitable combination of constrained nonlinear optimization methodology with specifically designed heuristic search strategies, in order to find high-quality numerical solutions in an efficient manner. We present optimized sphere configurations with up to \(n = 50\) spheres in dimensions \(d = 2, 3, 4, 5\). Our numerical results are on average within 1% of the entire set of best known results for a well-studied model-instance in \(\mathbb {R}^{2}\), with new (conjectured) packings for previously unexplored generalizations of the same model-class in \(\mathbb {R}^{d}\) with \(d= 3, 4, 5.\) Our results also enable the estimation of the optimized container sphere radii and of the packing fraction as functions of the model instance parameters n and 1 / n, respectively. These findings provide a general framework to define challenging packing problem-classes with conjectured numerical solution estimates.     

On Free Planes in Lattice Ball Packings

This note, by studying the relations between the length of theshortest lattice vectors and the covering minima of a lattice,proves that for every d-dimensional packing lattice of ballsone can find a four-dimensional plane, parallel to a latticeplane, such that the plane meets none of the balls of the packing,provided that the dimension d is large enough. Nevertheless,for certain ball packing lattices, the highest dimension ofsuch ‘free planes’ is far from d.     

Riesz External Field Problems on the Hypersphere and Optimal Point Separation

We consider the minimal energy problem on the unit sphere ?? ^d in the Euclidean space ? ^d+1 in the presence of an external field Q, where the energy arises from the Riesz potential 1/r ^s (where r is the Euclidean distance and s is the Riesz parameter) or the logarithmic potential log(1/r). Characterization theorems of Frostman-type for the associated extremal measure, previously obtained by the last two authors, are extended to the range d ? 2 ≤ s < d ? 1. The proof uses a maximum principle for measures supported on ?? ^d . When Q is the Riesz s-potential of a signed measure and d ? 2 ≤ s < d, our results lead to explicit point-separation estimates for (Q,s)-Fekete points, which are n-point configurations minimizing the Riesz s-energy on ?? ^d with external field Q. In the hyper-singular case s > d, the short-range pair-interaction enforces well-separation even in the presence of more general external fields. As a further application, we determine the extremal and signed equilibria when the external field is due to a negative point charge outside a positively charged isolated sphere. Moreover, we provide a rigorous analysis of the three point external field problem and numerical results for the four point problem.     

Anderson localization and Lifshits tails for random surface potentials

We consider Schrödinger operators on L²(R^d) with a random potential concentrated near the surface R^d₁×{0}⊂R^d. We prove that the integrated density of states of such operators exhibits Lifshits tails near the bottom of the spectrum. From this and the multiscale analysis by Boutet de Monvel and Stollmann [Arch. Math. 80 (2003) 87-97] we infer Anderson localization (pure point spectrum and dynamical localization) for low energies. Our proof of Lifshits tails relies on spectral properties of Schrödinger operators with partially periodic potentials. In particular, we show that the lowest energy band of such operators is parabolic.     

On a generalization of distance sets

A subset X in the d-dimensional Euclidean space is called a k-distance set if there are exactly k distinct distances between two distinct points in X and a subset X is called a locally k-distance set if for any point x in X, there are at most k distinct distances between x and other points in X.Delsarte, Goethals, and Seidel gave the Fisher type upper bound for the cardinalities of k-distance sets on a sphere in 1977. In the same way, we are able to give the same bound for locally k-distance sets on a sphere. In the first part of this paper, we prove that if X is a locally k-distance set attaining the Fisher type upper bound, then determining a weight function w, (X,w) is a tight weighted spherical 2k-design. This result implies that locally k-distance sets attaining the Fisher type upper bound are k-distance sets. In the second part, we give a new absolute bound for the cardinalities of k-distance sets on a sphere. This upper bound is useful for k-distance sets for which the linear programming bound is not applicable. In the third part, we discuss about locally two-distance sets in Euclidean spaces. We give an upper bound for the cardinalities of locally two-distance sets in Euclidean spaces. Moreover, we prove that the existence of a spherical two-distance set in (d−1)-space which attains the Fisher type upper bound is equivalent to the existence of a locally two-distance set but not a two-distance set in d-space with more than d(d+1)/2 points. We also classify optimal (largest possible) locally two-distance sets for dimensions less than eight. In addition, we determine the maximum cardinalities of locally two-distance sets on a sphere for dimensions less than forty.     

Random Sequential Adsorption of Discs on Surfaces of Constant Curvature: Plane,Sphere, Hyperboloid,and Projective Plane

We present an algorithm to simulate random sequential adsorption (random “parking”) of discs on constant curvature surfaces: the plane, sphere, hyperboloid, and projective plane, all embedded in three-dimensional space. We simulate complete parkings efficiently by explicitly calculating the boundary of the available area in which discs can park and concentrating new points in this area. We use our algorithm to study the number distribution and density of discs parked in each space, where for the plane and hyperboloid we consider two different periodic tilings each. We make several notable observations: (1) on the sphere, there is a critical disc radius such the number of discs parked is always exactly four: the random parking is deterministic. We prove this statement and also show that random parking on the surface of a d-dimensional sphere would have deterministic behaviour at the same critical radius. (2) The average number of parked discs does not always monotonically increase as the disc radius decreases: on the plane (square with periodic boundary conditions), there is an interval of decreasing radius over which the average decreases. We give a heuristic explanation for this counterintuitive finding. (3) As the disc radius shrinks to zero, the density (average fraction of area covered by parked discs) appears to converge to the same constant for all spaces, though it is always slightly larger for a sphere and slightly smaller for a hyperboloid. Therefore, for parkings on a general curved surface we would expect higher local densities in regions of positive curvature and lower local densities in regions of negative curvature.     

Upper Bound on the Packing Density of Regular Tetrahedra and Octahedra

Aristotle contended that (regular) tetrahedra tile space, an opinion that remained widespread until it was observed that non-overlapping tetrahedra cannot subtend a solid angle of 4π around a point if this point lies on a tetrahedron edge. From this 15th century argument, we can deduce that tetrahedra do not tile space but, more than 500 years later, we are unaware of any known non-trivial upper bound to the packing density of tetrahedra. In this article, we calculate such a bound. To this end, we show the existence, in any packing of regular tetrahedra, of a set of disjoint spheres centered on tetrahedron edges, so that each sphere is not fully covered by the packing. The bound on the amount of space that is not covered in each sphere is obtained in a recursive way by building on the solid angle argument. The argument can be readily modified to apply to other polyhedra. The resulting lower bound on the fraction of empty space in a packing of regular tetrahedra is 2.6…×10⁻²⁵ and reaches 1.4…×10⁻¹² for regular octahedra.     

Application of an idea of Voronoĭ to lattice packing

The geometric variant of a criterion of Vorono? says, a lattice packing of balls in \(\mathbb{E }^d\) has (locally) maximum density if and only if it is eutactic and perfect. This article deals with refinements of Vorono?’s result and extensions to lattice packings of smooth convex bodies. Versions of eutaxy and perfection are used to characterize lattices with semi-stationary, stationary, maximum and ultra-maximum lattice packing density, where ultra-maximality is a sharper version of maximality. Surprisingly, for balls, the lattice packings with maximum density have ultra-maximum density. To make the picture more complete, for \(d=2,3\) , we specify the lattices that provide lattice packings of balls with maximum properties. These lattices are related to Bravais types. Finally, similar results of a duality type are given.     

Divergence points of self-similar measures and packing dimension

Let μ be a self-similar measure in Rd. A point x∈Rd for which the limit does not exist is called a divergence point. Very recently there has been an enormous interest in investigating the fractal structure of various sets of divergence points. However, all previous work has focused exclusively on the study of the Hausdorff dimension of sets of divergence points and nothing is known about the packing dimension of sets of divergence points. In this paper we will give a systematic and detailed account of the problem of determining the packing dimensions of sets of divergence points of self-similar measures. An interesting and surprising consequence of our results is that, except for certain trivial cases, many natural sets of divergence points have distinct Hausdorff and packing dimensions.     

Error estimates for Hermite interpolation on spheres

In this paper, we prove convergence rates for spherical spline Hermite interpolation on the sphere S^d−1 via an error estimate given in a technical report by Luo and Levesley. The functionals in the Hermite interpolation are either point evaluations of pseudodifferential operators or rotational differential operators, the desirable feature of these operators being that they map polynomials to polynomials. Convergence rates for certain derivatives are given in terms of maximum point separation.     

Approximation lattices of p-adic numbers

Approximation lattices occur in a natural way in the study of rational approximations to p-adic numbers. Periodicity of a sequence of approximation lattices is shown to occur for rational and quadratic p-adic numbers, and for those only, thus establishing a p-adic analogue of Lagrange's theorem on periodic continued fractions. Using approximation lattices we derive upper and lower bounds for the best approximations to a p-adic number, thus establishing the p-adic analogue of a theorem of Hurwitz.     

Minimum Energy Problem on the Hypersphere

We consider the minimum energy problem on the unit sphere \(\mathbb {S}^{d-1}\) in the Euclidean space \(\mathbb {R}^{d}\), d = 3, in the presence of an external field Q, where the charges are assumed to interact according to Newtonian potential 1/r ^d-2, with r denoting the Euclidean distance. We solve the problem by finding the support of the extremal measure, and obtaining an explicit expression for the density of the extremal measure. We then apply our results to an external field generated by a point charge of positive magnitude, placed at the North Pole of the sphere, and to a quadratic external field.     

Periodicity and Circle Packings of the Hyperbolic Plane

We prove that given a fixed radius r, the set of isometry-invariant probability measures supported on 'periodic' radius r-circle packings of the hyperbolic plane is dense in the space of all isometry-invariant probability measures on the space of radius r-circle packings. By a periodic packing, we mean one with cofinite symmetry group. As a corollary, we prove the maximum density achieved by isometry-invariant probability measures on a space of radius r-packings of the hyperbolic plane is the supremum of densities of periodic packings. We also show that the maximum density function varies continuously with radius.     

Point Sets on the Sphere \mathbb{S}^{2} with Small Spherical Cap Discrepancy

In this paper we study the geometric discrepancy of explicit constructions of uniformly distributed points on the two-dimensional unit sphere. We show that the spherical cap discrepancy of random point sets, of spherical digital nets and of spherical Fibonacci lattices converges with order?N ^?1/2. Such point sets are therefore useful for numerical integration and other computational simulations. The proof uses an area-preserving Lambert map. A?detailed analysis of the level curves and sets of the pre-images of spherical caps under this map is given.     

Asymptotic synchronization in n-dimensional second order dissipative lattices of coupled oscillators

By introducing a new norm which is equivalent to the usual norm in the phase space, we prove that for n-dimensional second order dissipative lattices of coupled oscillators with external periodic forces under Dirichlet, Neumann and periodic boundary conditions, if the system is bounded dissipative and the coupled coefficients are both large enough, the asymptotic synchronization will occur. And we give a concrete bounded dissipative second order lattices system. Our results show that the bounds of the difference between the components of any solution are directly proportional to mn/2 and inversely proportional to the coupled coefficients, where m is the mesh size and n is the space dimension of lattice points.     

Dynamic multi-dimensional bin packing

A natural generalization of the classical online bin packing problem is the dynamic bin packing problem introduced by Coffman et al. (1983) [7]. In this formulation, items arrive and depart and the objective is to minimize the maximal number of bins ever used over all times. We study the oriented multi-dimensional dynamic bin packing problem for two dimensions, three dimensions and multiple dimensions. Specifically, we consider dynamic packing of squares and rectangles into unit squares and dynamic packing of three-dimensional cubes and boxes into unit cubes. We also study dynamic d-dimensional hypercube and hyperbox packing. For dynamic d-dimensional box packing we define and analyze the algorithm NFDH for the offline problem and present a dynamic version. This algorithm was studied before for rectangle packing and for square packing and was generalized only for multi-dimensional cubes. We present upper and lower bounds for each of these cases.