Quasi-polynomials, linear Diophantine equations and semi-linear sets
The main subject of the paper are semi-linear sets. They are of great importance because the set of non-negative solutions of a system \(A\mathbf{x}=\mathbf{b}\) is a such set. For a system \(A\mathbf{x}=\mathbf{b}, A\in\mathbb{Z}^{t\times n}, \mathbf{b}\in\mathbb{Z}^{t}\) the partition function \(\delta_A(b)\) is defined as a number of all non-negative solutions of the system. It is proved that this function is a quasi-polynomial on polyhedral regions in \(\mathbb{Z}^{t}\). This result is a version of the theorem of Dahmen and Micchelli. The presented proof is combinatorial and rather elementary. It is also proved that there exists a finite partition of \(\mathbb{Z}^{t}\) in simple sets such that \(\delta_A(b)\) is a polynomial on each of them. In fact both these results are consequences of the more general theorems concerning semi-linear sets. If \(X\) is a semi-linear subset of \(\mathbb{N}^{t}\) then its growth function is a piecewise quasi-polynomial on polyhedral regions in \(\mathbb{N}^{t}.\) It should be mentioned that all theorems are effective. It means that if the system \(A\mathbf{x}=\mathbf{b}\) is given then we can construct a polyhedral partition of \(\mathbb{Z}^{t}\) and quasi-polynomials describing \(\delta_A(b).\)
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
- Computing the Continuous Discretely
- Convex Analysis
- Counting integer flows in networks
- Every semilinear set is a finite union of disjoint linear sets
- scientific article; zbMATH DE number 5761834 (Why is no real title available?)
- scientific article; zbMATH DE number 5643878 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3588051 (Why is no real title available?)
- scientific article; zbMATH DE number 1219584 (Why is no real title available?)
- scientific article; zbMATH DE number 2008526 (Why is no real title available?)
- scientific article; zbMATH DE number 3293666 (Why is no real title available?)
- Interpolated Denumerants and Lambert Series
- Local Euler-Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of a rational polytope
- On the structure of the counting function of sparse context-free languages.
- On vector partition functions
- Rational sets in commutative monoids
- Remarks on piecewise-linear algebra
- Residue formulae for vector partitions and Euler-Maclaurin sums.
- Semigroups, Presburger formulas, and languages
- The many aspects of counting lattice points in polytopes
- The Number of Solutions to Linear Diophantine Equations and Multivariate Splines
- The Parikh counting functions of sparse context-free languages are quasi-polynomials
- Topics in hyperplane arrangements, polytopes and box-splines
- Vector partition functions and generalized Dahmen and Micchelli spaces
- On bounded linear codes and the commutative equivalence
- On the commutative equivalence of bounded context-free and regular languages: the semi-linear case
- On The Number of Nonnegative Integer Solutions of a System of Linear Diophantine Equations
- On the commutative equivalence of bounded context-free and regular languages: the code case
- On the commutative equivalence of semi-linear sets of \(\mathbb{N}^k\)
- D-finite multivariate series with arithmetic restrictions on their coefficients
- On the Commutative Equivalence of Algebraic Formal Series and Languages
- Quaternionic lattices and the poly-context-free word problem
- Effective equation solving, constraints, and growth in virtually abelian groups
This page was built for publication: Quasi-polynomials, linear Diophantine equations and semi-linear sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764313)
