Parametric polyhedra with at least k lattice points: Their semigroup structure and the k-Frobenius problem
Parametric polyhedra with at least k lattice points: Their semigroup structure and the k-Frobenius problem
复制标题
至少有 k 个格点的参数多面体：它们的半群结构和 k-Frobenius 问题
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Q. Louveaux
中科院分区：
文献类型：
--
作者：
I. Aliev;J. D. Loera;Q. Louveaux
给定一个积分 d × n 矩阵 A，经过充分研究的仿射半群 (mathrm{Sg}(A) ={ b: Ax = b, x in mathbb{Z}^{n},x geq 0}) 可以通过参数多面体 P A (b) = { x: Ax = b, x ≥ 0} 内的格点数进行分层。这些参数多面体族出现在组合数学、凸几何、代数和数论的许多领域中。本文的关键主题是：（1）一种结构理论，精确描述所有向量（mathrm{Sg}(A) 中的 b）的子集 Sg ≥ k(A)，使得 (P_{A}(b) cap mathbb{Z}^{n}) 至少有 k 个解。我们证明这个集合是有限生成的，它是半群的平移副本的并集，可以通过希尔伯特基计算显式计算。对于 (P_{A}(b) cap mathbb{Z}^{n}) 恰好有 k 个解或少于 k 个解的那些右侧向量 b，可以导出相关结果。 (2)计算复杂性理论。我们证明，当 n、k 是固定的自然数时，我们可以使用有理函数的短和，在多项式时间内计算 (mathrm{Sg}_{geq k}(A)) 的编码作为多元生成函数。因此，我们可以识别至少有 k 个解的有界范数的所有右侧向量。 (3) k-Frobenius数的应用和计算。使用生成函数，我们证明对于固定的 n、k，可以在多项式时间内计算 k-Frobenius 数。这概括了 R. Kannan 的众所周知的 k = 1 结果。使用动态规划的一些改编，我们展示了 k-Frobenius 数及其相关数的一些实际计算。
Given an integral d × n matrix A, the well-studied affine semigroup (mathrm{Sg}(A) ={ b: Ax = b, x in mathbb{Z}^{n},x geq 0}) can be stratified by the number of lattice points inside the parametric polyhedra P A (b) = { x: Ax = b, x ≥ 0}. Such families of parametric polyhedra appear in many areas of combinatorics, convex geometry, algebra, and number theory. The key themes of this paper are: (1) A structure theory that characterizes precisely the subset Sg ≥ k(A) of all vectors (b in mathrm{Sg}(A)) such that (P_{A}(b) cap mathbb{Z}^{n}) has at least k solutions. We demonstrate that this set is finitely generated, it is a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computations. Related results can be derived for those right-hand-side vectors b for which (P_{A}(b) cap mathbb{Z}^{n}) has exactly k solutions or fewer than k solutions. (2) A computational complexity theory. We show that, when n, k are fixed natural numbers, one can compute in polynomial time an encoding of (mathrm{Sg}_{geq k}(A)) as a multivariate generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors of bounded norm that have at least k solutions. (3) Applications and computation for the k-Frobenius numbers. Using generating functions we prove that for fixed n, k the k-Frobenius number can be computed in polynomial time. This generalizes a well-known result for k = 1 by R. Kannan. Using some adaptation of dynamic programming we show some practical computations of k-Frobenius numbers and their relatives.