Hyperspheric Integer Programming

This paper develops an efficient method for finding the optimal solution to linear mathematical programs on 0–1 variables. It is shown that the lattice (0–1) points satisfying some linear constraint of dimension n can equally be represented by those lying in a hypersphere of the same dimension. The lattice points satisfying two linear constraints can be represented by a hypersphere which contains the intersection of the hyperspheres of the two constraints. The method for finding the optimal solution consists of enumerating lattice points which are close to the center of the hypersphere corresponding to the constraints. As soon as a better value of the objective function has been found, than some lower bound, we find a new hypersphere which contains the lattice points of the constraints at which the objective function remains higher than the best known value. We continue in this manner until we have at some stage enumerated all lattice points within a given hypersphere and found none which give a better value.     

A strengthened Barvinok-Pataki bound on SDP rank

The Barvinok-Pataki bound provides an upper bound on the rank of extreme points of a spectrahedron. This bound depends solely on the number of affine constraints of the problem, i.e., on the algebra of the problem. Specifically, the triangular number of the rank r is upper bounded by the number of affine constraints. We revisit this bound and provide a strengthened upper bound on the rank using the singularity degree of the spectrahedron. Thus we bring in the geometry and stability of the spectrahedron, i.e., increased instability as seen by higher singularity degree, yields a lower, strengthened rank bound.     

Minimal half-spaces and external representation of tropical polyhedra

We give a characterization of the minimal tropical half-spaces containing a given tropical polyhedron, from which we derive a counter-example showing that the number of such minimal half-spaces can be infinite, contradicting some statements which appeared in the tropical literature, and disproving a conjecture of F. Block and J. Yu. We also establish an analogue of the Minkowski–Weyl theorem, showing that a tropical polyhedron can be equivalently represented internally (in terms of extreme points and rays) or externally (in terms of half-spaces containing it). A canonical external representation of a polyhedron turns out to be provided by the extreme elements of its tropical polar. We characterize these extreme elements, showing in particular that they are determined by support vectors.     

Volume and Lattice Points of Reflexive Simplices

Using new number-theoretic bounds on the denominators of unit fractions summing up to one, we show that in any dimension d ≥ 4 there is only one d-dimensional reflexive simplex having maximal volume. Moreover, only these reflexive simplices can admit an edge that has the maximal number of lattice points possible for an edge of a reflexive simplex. In general, these simplices are also expected to contain the largest number of lattice points even among all lattice polytopes with only one interior lattice point. Translated in algebro-geometric language, our main theorem yields a sharp upper bound on the anticanonical degree of d-dimensional Q-factorial Gorenstein toric Fano varieties with Picard number one, e.g., of weighted projective spaces with Gorenstein singularities.     

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.     

Tropical polar cones, hypergraph transversals, and mean payoff games

We discuss the tropical analogues of several basic questions of convex duality. In particular, the polar of a tropical polyhedral cone represents the set of linear inequalities that its elements satisfy. We characterize the extreme rays of the polar in terms of certain minimal set covers which may be thought of as weighted generalizations of minimal transversals in hypergraphs. We also give a tropical analogue of Farkas lemma, which allows one to check whether a linear inequality is implied by a finite family of linear inequalities. Here, the certificate is a strategy of a mean payoff game. We discuss examples, showing that the number of extreme rays of the polar of the tropical cyclic polyhedral cone is polynomially bounded, and that there is no unique minimal system of inequalities defining a given tropical polyhedral cone.     

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.     

A Blichfeldt-type inequality for centrally symmetric convex bodies

In this note, we derive an asymptotically sharp upper bound on the number of lattice points in terms of the volume of a centrally symmetric convex body. Our main tool is a generalization of a result of Davenport that bounds the number of lattice points in terms of volumes of suitable projections.     

Dyadic Diaphony of Digital Nets Over ?2

The dyadic diaphony, introduced by Hellekalek and Leeb, is a quantitative measure for the irregularity of distribution of point sets in the unit-cube. In this paper we study the dyadic diaphony of digital nets over ℤ₂. We prove an upper bound for the dyadic diaphony of nets and show that the convergence order is best possible. This follows from a relation between the dyadic diaphony and the L₂{\cal L}_2 discrepancy. In order to investigate the case where the number of points is small compared to the dimension we introduce the limiting dyadic diaphony, which is defined as the limiting case where the dimension tends to infinity. We obtain a tight upper and lower bound and we compare this result with the limiting dyadic diaphony of a random sample.     

On the extremal solutions for capacitated network problems

In this note we give a unifying approach to the problem of characterizing the extreme points of those convex matrix sets which correspond to the domains of various types of capacitated network problems. It is shown that we can determine whether a matrix is an extreme point of the sets by examining the pattern of a certain graph associated with it. We also study the extreme points of the convex matrix sets which are related to network problems free from capacity constraints by linking them up with certain capacitated network problem.     

VC Dimensions of Principal Component Analysis

Motivated by statistical learning theoretic treatment of principal component analysis, we are concerned with the set of points in ℝ ^d that are within a certain distance from a k-dimensional affine subspace. We prove that the VC dimension of the class of such sets is within a constant factor of (k+1)(d−k+1), and then discuss the distribution of eigenvalues of a data covariance matrix by using our bounds of the VC dimensions and Vapnik’s statistical learning theory. In the course of the upper bound proof, we provide a simple proof of Warren’s bound of the number of sign sequences of real polynomials.     

On formulas for Dedekind sums and the number of lattice points in tetrahedra

This paper explores a simple yet powerful relationship between the problem of counting lattice points and the computation of Dedekind sums. We begin by constructing and proving a sharp upper estimate for the number of lattice points in tetrahedra with some irrational coordinates for the vertices. Besides providing a sharper estimate, this upper bound (Theorem 1.1) becomes an equality (i.e. gives the exact number of lattice points) in a tetrahedron where the lengths of the edges divide each other. This equality condition can then be applied to the explicit computation of the classical Dedekind sums, a topic that is the central focus in the second half of our paper. In this half of the paper, we come up with a number of interesting results related to Dedekind sums, based on our upper estimate (Theorem 1.1). Among these findings, Theorem 1.9 and Theorem 1.10 deserve special attention, for they successfully generalize two of Apostol's formulas in [T.M. Apostol, Modular Functions and Dirichlet Series in Number Theory, Springer-Verlag, New York, 1997], and also directly imply the famous Reciprocity Law of Dedekind sums.     

Lattice polytopes of degree 2

A theorem of Scott gives an upper bound for the normalized volume of lattice polygons with exactly i>0 interior lattice points. We will show that the same bound is true for the normalized volume of lattice polytopes of degree 2 even in higher dimensions. In particular, there is only a finite number of quadratic polynomials with fixed leading coefficient being the h^∗-polynomial of a lattice polytope.     

Distance Measures for Well-Distributed Sets

In this paper we investigate the Erdos/Falconer distance conjecture for a natural class of sets statistically, though not necessarily arithmetically, similar to a lattice. We prove a good upper bound for spherical means that have been classically used to study this problem. We conjecture that a majorant for the spherical means suffices to prove the distance conjecture(s) in this setting. For a class of non-Euclidean distances, we show that this generally cannot be achieved, at least in dimension two, by considering integer point distributions on convex curves and surfaces. In higher dimensions, we link this problem to the question about the existence of smooth well-curved hypersurfaces that support many integer points.     

An upper bound on the covering radius of the logarithmic lattice for cyclotomic number fields

Recently, in coding theory and cryptography, it has been important the diversified use of lattices. One use of them is to cover a space. Each lattice has a covering radius, a number corresponding to the radius of a ball whose translations by all the points of the lattice cover efficiently the space generated by a basis of it. A way to obtain lattices algebraically is from subgroups of the multiplicative group of units of a number field via the logarithm embedding. This includes the logarithm lattice. In this work, it is presented an upper bound on the covering radius of the logarithm lattice obtained from the units of general cyclotomic number fields via the logarithm embedding, which generalizes an upper bound present in a previous work for cyclotomic number fields of prime-power indices.     

Random polytopes: Their definition,generation and aggregate properties

The definition of random polytope adopted in this paper restricts consideration to those probability measures satisfying two properties. First, the measure must induce an absolutely continuous distribution over the positions of the bounding hyperplanes of the random polytope; and second, it must result in every point in the space being equally as likely as any other point of lying within the random polytope. An efficient Monte Carlo method for their computer generation is presented together with analytical formulas characterizing their aggregate properties. In particular, it is shown that the expected number of extreme points for such random polytopes increases monotonically in the number of constraints to the limiting case of a polytope topologically equivalent to a hypercube. The implied upper bound of 2 ⁿ wheren is the dimensionality of the space is significantly less than McMullen's attainable bound on the maximal number of vertices even for a moderate number of constraints.     

Concerning the shape of a geometric lattice

A well-known conjecture states that the Whitney numbers of the second kind of a geometric lattice (simple matroid) are logarithmically concave. We show this conjecture to be equivalent to proving an upper bound on the number of new copoints in the free erection of the associated simple matroid M. A bound on the number of these new copoints is given in terms of the copoints and colines of M. Also, the points-lines-planes conjecture is shown to be equivalent to a problem concerning the number of subgraphs of a certain bipartite graph whose vertices are the points and lines of a geometric lattice.     

Ehrhart polynomials of cyclic polytopes

The Ehrhart polynomial of an integral convex polytope counts the number of lattice points in dilates of the polytope. In (Coefficients and roots of Ehrhart polynomials, preprint), the authors conjectured that for any cyclic polytope with integral parameters, the Ehrhart polynomial of it is equal to its volume plus the Ehrhart polynomial of its lower envelope and proved the case when the dimension d=2. In our article, we prove the conjecture for any dimension.     

On the Number of Determining Nodes for the Generalized Ginzburg-Landau Equation

In this paper, we obtain that the number of determining nodes for the generalized Ginzburg-Landau equation is two closely points, as a consequence, an upper bound for the winding number of stationary is established in terrns of the parameters in the equation. It is also proven that the fractal dimension of the set of stationary solution is less than or equal to 4.     

Characterizations of extreme normalized circulations satisfying linear constraints

This paper considers polytopes of circulations (flows) on a graph which satisfy given linear (homogenous) constraints. Algebraic characterizations of the extreme points of such polytopes are obtained. We also characterize subgraphs which support extreme points. Finally, a formula (geometric in nature) is obtained for the dimension of the flow space of a set of cycles.