Quasi-polynomials, linear Diophantine equations and semi-linear sets (Q764313): Difference between revisions

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).\)