Short rational generating functions for lattice point problems-猫眼课题宝

格点问题的短有理生成函数

DOI：

发表时间：

2002

期刊：

影响因子：

通讯作者：

中科院分区：

文献类型：

作者：

A. Barvinok;Kevin M. Woods

抽象的。证明了对于任意ﬁ，d维有理多面体中整数点集的射影母函数可以在多项式时间内计算。作为推论，我们推出了各种有趣的格点集，特别是有理锥的整数半群和(极小)Hilbert基，如果某些参数(生成元的维度和数目)是ﬁX的，则它们具有短的有理生成函数。于是，对于这类集合的许多计算问题(例如，ﬁ和不能表示为给定互质正整数的非负整数组合的正整数的个数)允许多项式时间算法。我们还讨论了计算由单项式生成的环的Hilbert级数的一个相关问题。1.引言和主要结果我们的主要动机是以下问题，这可以追溯到Frobenius和Sylvester。(1.1)Frobenius问题。设a 1，…，a d是互素正整数且S=n

Abstract. We prove that for any ﬁxed d the generating function of the projectionof the set of integer points in a rational d-dimensional polytope can be computed inpolynomial time. As a corollary, we deduce that various interesting sets of latticepoints, notably integer semigroups and (minimal) Hilbert bases of rational cones,have short rational generating functions provided certain parameters (the dimensionand the number of generators) are ﬁxed. It follows then that many computationalproblems for such sets (for example, ﬁnding the number of positive integers notrepresentable as a non-negative integer combination of given coprime positive integersa 1 ,... ,a d ) admit polynomial time algorithms. We also discuss a related problem ofcomputing the Hilbert series of a ring generated by monomials. 1. Introduction and Main ResultsOur main motivation is the following question which goes back to Frobenius andSylvester.(1.1) The Frobenius Problem. Let a 1 ,... ,a d be positive coprime integers andletS =nµ

Short rational generating functions for lattice point problems

格点问题的短有理生成函数

文献摘要

被引文献

相似文献