Quasi-polynomials, linear Diophantine equations and semi-linear sets
type: Item
instance of: scholarly article
title: Quasi-polynomials, linear Diophantine equations and semi-linear sets
zbMATH Open document ID: 1253.11042
author: Flavio D'Alessandro
author: Benedetto Intrigila
author: Stefano Varricchio
published in: Theoretical Computer Science
publication date: 2012-03-13T00:00:00Z
review text: 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).\)
Mathematics Subject Classification ID: 11D04
Mathematics Subject Classification ID: 52C07
Mathematics Subject Classification ID: 68Q70
zbMATH DE Number: 6014305
zbMATH Keywords: semi-linear sets
zbMATH Keywords: systems of linear Diophantine equations
zbMATH Keywords: quasi-polynomials
reviewed by: Dmitriy Frolenkov
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.10.014
OpenAlex ID: W2089841370
cites work: Q3601417
cites work: Counting integer flows in networks
cites work: A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
cites work: Computing the Continuous Discretely
cites work: Interpolated Denumerants and Lambert Series
cites work: Q3575467
cites work: On the structure of the counting function of sparse context-free languages.
cites work: The Parikh counting functions of sparse context-free languages are quasi-polynomials
cites work: The Number of Solutions to Linear Diophantine Equations and Multivariate Splines
cites work: Topics in hyperplane arrangements, polytopes and box-splines
cites work: Vector partition functions and generalized Dahmen and Micchelli spaces
cites work: The many aspects of counting lattice points in polytopes
cites work: Rational sets in commutative monoids
cites work: Q5576254
cites work: Semigroups, Presburger formulas, and languages
cites work: Q4434671
cites work: Every semilinear set is a finite union of disjoint linear sets
cites work: Q4217266
cites work: Convex Analysis
cites work: Q3651209
cites work: Q4155837
cites work: Q3818127
cites work: Remarks on piecewise-linear algebra
cites work: On vector partition functions
cites work: Residue formulae for vector partitions and Euler-Maclaurin sums.
DOI: 10.1016/J.TCS.2011.10.014
description: scientific article; zbMATH DE number 6014305