An Optimization Problem Related to Minkowski’s Successive Minima

The purpose of this paper is to establish an inequality connecting the lattice point enumerator of a 0-symmetric convex body with its successive minima. To this end, we introduce an optimization problem whose solution refines former methods, thus producing a better upper bound. In particular, we show that an analogue of Minkowski’s second theorem on successive minima with the volume replaced by lattice point enumerator is true up to an exponential factor, whose base is approximately 1.64.     

A Brunn-Minkowski inequality for the integer lattice

A close discrete analog of the classical Brunn-Minkowksi inequality that holds for finite subsets of the integer lattice is obtained. This is applied to obtain strong new lower bounds for the cardinality of the sum of two finite sets, one of which has full dimension, and, in fact, a method for computing the exact lower bound in this situation, given the dimension of the lattice and the cardinalities of the two sets. These bounds in turn imply corresponding new bounds for the lattice point enumerator of the Minkowski sum of two convex lattice polytopes. A Rogers-Shephard type inequality for the lattice point enumerator in the plane is also proved.

     

Lattice-point enumerators of ellipsoids

Minkowski’s second theorem on successive minima asserts that the volume of a 0-symmetric convex body K over the covolume of a lattice Λ can be bounded above by a quantity involving all the successive minima of K with respect to Λ. We will prove here that the number of lattice points inside K can also accept an upper bound of roughly the same size, in the special case where K is an ellipsoid. Whether this is also true for all K unconditionally is an open problem, but there is reasonable hope that the inductive approach used for ellipsoids could be extended to all cases.     

Successive-minima-type inequalities

We show analogues of Minkowski's theorem on successive minima, where the volume is replaced by the lattice point enumerator. We further give analogous results to some recent theorems by Kannan and Lovász on covering minima.     

Inequalities between successive minima and intrinsic volumes of a convex body

The second theorem of Minkowski establishes a relation between the successive minima and the volume of a 0-symmetric convex body. Based on this theorem we will prove a series of inequalities connecting the product of certain successive minima with certain intrinsic volumes.     

Intrinsic volumes and lattice points of crosspolytopes

Hadwiger showed by computing the intrinsic volumes of a regular simplex that a rectangular simplex is a counterexample to Wills' conjecture for the relation between the lattice point enumerator and the intrinsic volumes in dimensions not less than 441. Here we give formulae for the volumes of spherical polytopes related to the intrinsic volumes of the regular crosspolytope and of the rectangular simplex. This completes the determination of intrinsic volumes for regular polytopes. As a consequence we prove that Wills' conjecture is false even for centrally symmetric convex bodies in dimensions not less than 207.     

f-Vectors of Minkowski Additions of Convex Polytopes

The objective of this paper is to present two types of results on Minkowski sums of convex polytopes. The first is about a special class of polytopes we call perfectly centered and the combinatorial properties of the Minkowski sum with their own dual. In particular, we have a characterization of the face lattice of the sum in terms of the face lattice of a given perfectly centered polytope. Exact face counting formulas are then obtained for perfectly centered simplices and hypercubes. The second type of results concerns tight upper bounds for the f-vectors of Minkowski sums of several polytopes.     

Sectional genus and the volume of a lattice polytope

Journal of Algebraic Combinatorics - For a convex lattice polytope having at least one interior lattice point, a lower bound for its volume is derived from Hibi’s lower bound theorem for the...     

Géométrie des nombres adélique et lemmes de Siegel généralisés

A Siegel’s lemma provides an explicit upper bound for a non-zero vector of minimal height in a finite dimensional vector spaces over a number field. This article explains how to obtain Siegel’s lemmas for which the minimal vectors do not belong to a finite union of vector subspaces (Siegel’s lemmas with conditions). The proofs mix classical results of adelic geometry of numbers and an adelic variant of a theorem of Henk about the number of lattice points of a centrally symmetric convex body in terms of the successive minima of the body.     

On the variance of random polytopes

A random polytope is the convex hull of uniformly distributed random points in a convex body K. A general lower bound on the variance of the volume and f-vector of random polytopes is proved. Also an upper bound in the case when K is a polytope is given. For polytopes, as for smooth convex bodies, the upper and lower bounds are of the same order of magnitude. The results imply a law of large numbers for the volume and f-vector of random polytopes when K is a polytope.     

Polar reciprocal convex bodies

The minimum of the product of the volume of a symmetric convex bodyK and the volume of the polar reciprocal body ofK relative to the center of symmetry is attained for the cube and then-dimensional crossbody. As a consequence, there is a sharp upper bound in Mahler’s theorem on successive minima in the geometry of numbers. The difficulties involved in the determination of the minimum for unsymmetricK are discussed. Reserch partially supported by NSF Grant GP-27960. An erratum to this article is available at .     

Notes on the Roots of Ehrhart Polynomials

We determine lattice polytopes of smallest volume with a given number of interior lattice points. We show that the Ehrhart polynomials of those with one interior lattice point have largest roots with norm of order n², where n is the dimension. This improves on the previously best known bound n and complements a recent result of Braun where it is shown that the norm of a root of a Ehrhart polynomial is at most of order n². For the class of 0-symmetric lattice polytopes we present a conjecture on the smallest volume for a given number of interior lattice points and prove the conjecture for crosspolytopes. We further give a characterisation of the roots of Ehrhart polyomials in the three-dimensional case and we classify for n ≤ 4 all lattice polytopes whose roots of their Ehrhart polynomials have all real part -1/2. These polytopes belong to the class of reflexive polytopes.     

关于多胞形一个新仿射不变量的应用

用组合极值方法导出了n维欧氏空间中关于原点对称的一个凸多胞形子类上一个新的仿射不变量(最近由Lutwak,Yang和Zhang引入)的解析表达式,并给出了其在凸多胞形Minkowski问题的一个应用．     

The Willmore functional and the containment problem in R~4

Let∑be a convex hypersurface in the Euclidean space R4 with mean curvature H. We obtain a geometric lower bound for the Willmore functional∫∑H2dσ. This bound is an invariant involving the area of∑, the volume and Minkowski quermassintegrals of the convex body that∑bounds. We also obtain a sufficient condition for a convex body to contain another in the Euclidean space R4.     

The brick polytope of a sorting network

The associahedron is a polytope whose graph is the graph of flips on triangulations of a convex polygon. Pseudotriangulations and multitriangulations generalize triangulations in two different ways, which have been unified by Pilaud & Pocchiola in their study of flip graphs on pseudoline arrangements with contacts supported by a given sorting network.In this paper, we construct the brick polytope of a sorting network, obtained as the convex hull of the brick vectors associated to each pseudoline arrangement supported by the network. We combinatorially characterize the vertices of this polytope, describe its faces, and decompose it as a Minkowski sum of matroid polytopes.Our brick polytopes include Hohlweg & Lange’s many realizations of the associahedron, which arise as brick polytopes for certain well-chosen sorting networks. We furthermore discuss the brick polytopes of sorting networks supporting pseudoline arrangements which correspond to multitriangulations of convex polygons: our polytopes only realize subgraphs of the flip graphs on multitriangulations and they cannot appear as projections of a hypothetical multiassociahedron.     

Sums, Projections, and Sections of Lattice Sets, and the Discrete Covariogram

Basic properties of finite subsets of the integer lattice ℤⁿ are investigated from the point of view of geometric tomography. Results obtained concern the Minkowski addition of convex lattice sets and polyominoes, discrete X-rays and the discrete and continuous covariogram, the determination of symmetric convex lattice sets from the cardinality of their projections on hyperplanes, and a discrete version of Meyer’s inequality on sections of convex bodies by coordinate hyperplanes.     

Local tensor valuations on convex polytopes

Local versions of the Minkowski tensors of convex bodies in $n$ -dimensional Euclidean space are introduced. An extension of Hadwiger’s characterization theorem for the intrinsic volumes, due to Alesker, states that the continuous, isometry covariant valuations on the space of convex bodies with values in the vector space of symmetric $p$ -tensors are linear combinations of modified Minkowski tensors. We ask for a local analogue of this characterization, and we prove a classification result for local tensor valuations on polytopes, without a continuity assumption.     

Bounds for the lattice point enumerator

For the lattice point enumerator of a lattice and a convex body K we give bounds in terms of the intrinsic volumes of K and of minimal determinants of . The intrinsic volumes are the normalized Minkowski quermassintegrals and the minimal determinants are analogous functionals of .     

Rigidity and flexibility of virtual polytopes

All 3-dimensional convex polytopes are known to be rigid. Still their Minkowski differences (virtual polytopes) can be flexible with any finite freedom degree. We derive some sufficient rigidity conditions for virtual polytopes and present some examples of flexible ones. For example, Bricard's first and second flexible octahedra can be supplied by the structure of a virtual polytope.     

Translational tilings by a polytope, with multiplicity

We study the problem of covering ? ^d by overlapping translates of a convex polytope, such that almost every point of ? ^d is covered exactly k times. Such a covering of Euclidean space by a discrete set of translations is called a k-tiling. The investigation of simple tilings by translations (which we call 1-tilings in this context) began with the work of Fedorov [5] and Minkowski [15], and was later extended by Venkov and McMullen to give a complete characterization of all convex objects that 1-tile ? ^d . By contrast, for k ≥2, the collection of polytopes that k-tile is much wider than the collection of polytopes that 1-tile, and there is currently no known analogous characterization for the polytopes that k-tile. Here we first give the necessary conditions for polytopes P that k-tile, by proving that if P k-tiles ? ^d by translations, then it is centrally symmetric, and its facets are also centrally symmetric. These are the analogues of Minkowski’s conditions for 1-tiling polytopes, but it turns out that very new methods are necessary for the development of the theory. In the case that P has rational vertices, we also prove that the converse is true; that is, if P is a rational polytope, is centrally symmetric, and has centrally symmetric facets, then P must k-tile ? ^d for some positive integer k.