Presburger arithmetic is the first-order theory of the natural numbers with addition (but no multiplication). We characterize sets that can be defined by a Presburger formula as exactly the sets whose characteristic functions can be represented by rational generating functions; a geometric characterization of such sets is also given. In addition, if p=(p_1,...,p_n) are a subset of the free variables in a Presburger formula, we can define a counting function g(p) to be the number of solutions to the formula, for a given p. We show that every counting function obtained in this way may be represented as, equivalently, either a piecewise quasi-polynomial or a rational generating function. Finally, we translate known computational complexity results into this setting and discuss open directions.
The importance of understanding Presburger Arithmetic is highlighted by the fact that many problems in computer science and mathematics can be phrased in this language: for example, integer programming @cite_9 @cite_42 , geometry of numbers @cite_41 @cite_22 , Gr "obner bases and algebraic integer programming @cite_24 @cite_36 , neighborhood complexes and test sets @cite_15 @cite_12 , the Frobenius problem @cite_17 , Ehrhart theory @cite_43 @cite_34 , monomial ideals @cite_47 , and toric varieties @cite_30 . Several of the above references analyze the computational complexity of their specific problem. In most of the above references, the connection to Presburger arithmetic is only implicit.
@cite_30 @cite_47 @cite_22 @cite_41 @cite_36 @cite_9 @cite_42 @cite_24 @cite_43 @cite_15 @cite_34 @cite_12 @cite_17
2566917795 1537258143 1557027117 2114616381 2949688382 1974880185 2332901121
Monomial Ideals.- Squarefree monomial ideals.- Borel-fixed monomial ideals.- Three-dimensional staircases.- Cellular resolutions.- Alexander duality.- Generic monomial ideals.- Toric Algebra.- Semigroup rings.- Multigraded polynomial rings.- Syzygies of lattice ideals.- Toric varieties.- Irreducible and injective resolutions.- Ehrhart polynomials.- Local cohomology.- Determinants.- Plucker coordinates.- Matrix Schubert varieties.- Antidiagonal initial ideals.- Minors in matrix products.- Hilbert schemes of points. Notation Prologue Chapter I. Lattices 1. Introduction 2. Bases and sublattices 3. Lattices under linear transformation 4. Forms and lattices 5. The polar lattice Chapter II. Reduction 1. Introduction 2. The basic process 3. Definite quadratic forms 4. Indefinite quadratic forms 5. Binary cubic forms 6. Other forms Chapter III. Theorems of Blichfeldt and Minkowski 1. Introduction 2. Blichfeldt's and Mnowski's theorems 3. Generalisations to non-negative functions 4. Characterisation of lattices 5. Lattice constants 6. A method of Mordell 7. Representation of integers by quadratic forms Chapter IV. Distance functions 1. Introduction 2. General distance-functions 3. Convex sets 4. Distance functions and lattices Chapter V. Mahler's compactness theorem 1. Introduction 2. Linear transformations 3. Convergence of lattices 4. Compactness for lattices 5. Critical lattices 6. Bounded star-bodies 7. Reducibility 8. Convex bodies 9. Speres 10. Applications to diophantine approximation Chapter VI. The theorem of Minkowski-Hlawka 1. Introduction 2. Sublattices of prime index 3. The Minkowski-Hlawka theorem 4. Schmidt's theorems 5. A conjecture of Rogers 6. Unbounded star-bodies Chapter VII. The quotient space 1. Introduction 2. General properties 3. The sum theorem Chapter VIII. Successive minima 1. Introduction 2. Spheres 3. General distance-functions Chapter IX. Packings 1. Introduction 2. Sets with V( varphi) =n^2 Delta( varphi) 3. Voronoi's results 4. Preparatory lemmas 5. Fejes Toth's theorem 6. Cylinders 7. Packing of spheres 8. The proudctio of n linear forms Chapter X. Automorphs 1. Introduction 2. Special forms 3. A method of Mordell 4. Existence of automorphs 5. Isolation theorems 6. Applications of isolation 7. An infinity of solutions 8. Local methods Chapter XI. Ihomogeneous problems 1. Introduction 2. Convex sets 3. Transference theorems for convex sets 4. The producti of n linear forms Appendix References Index quotient space. successive minima. Packings. Automorphs. Inhomogeneous problems. It is shown that the integer linear programming problem with a fixed number of variables is polynomially solvable. The proof depends on methods from geometry of numbers. We determine the maximal gap between the optimal values of an integer program and its linear programming relaxation, where the matrix and cost function are fixed but the right hand side is unspecified. Our formula involves irreducible decomposition of monomial ideals. The gap can be computed in polynomial time when the dimension is fixed. In this paper I discuss various properties of the simplicial complex of maximal lattice free bodies associated with a matrix A. If the matrix satisfies some mild conditions, and is generic, the edges of the complex form the minimal test set for the family of integer programs obtained by selecting a particular row of A as the objective function, and using the remaining rows to impose constraints on the integer variables. © 1997 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V. Preface Acknowledgements 1. Algorithmic Aspects 2. The Frobenius Number for Small n 3. The General Problem 4. Sylvester Denumerant 5. Integers without Representation 6. Generalizations and Related Problems 7. Numerical Semigroups 8. Applications of the Frobenius Number 9. Appendix A Bibliography