论文标题
在$δ$ - 模块化polyhedra中计数的晶格点计数
On lattice point counting in $Δ$-modular polyhedra
论文作者
论文摘要
令多面体$ p $由以下方式之一定义： （i）$ p = \ {x \ in r^n \ colon a x \ leq b \} $，其中$ a \ in z^{（n+k）\ times n} $，$ b \ in z^{（n+k）} $ in （ii）$ p = \ {x \ in r _+^n \ colon a x = b \} $，其中$ a \ in z^{k \ times n} $，$ b \ in z^{k} $ in z^{k} $ and $ stark \ in $ rank \，a = k $。 并让所有排名未成年人$ a $的未成年人在绝对值中受$δ$界定。我们表明，可以使用算术复杂性$ o \ left（t_ {snf}（snf}（d）\ cdot d^{k} \ cdot d^$ log _ k $ k $ k $ k $ k $ k $ k $ k $ k $ k $ j $ k $ k $ k $ k $ k $ k $ k $ k $ k $ k $ k $ k $ k $ j $ wery，可以计算出功率系列$$ $ \ sum \ sum \ sum \ sum \ sum \ sum \ sum \ sum \ sum \ limits的简短有理生成函数$固定，$ d = \ dim p $，$ t_ {snf}（m）$是计算$ m \ times m $整数矩阵的史密斯普通表格的复杂性。特别是，案例（i）和$ d = n-k $的$ d = n $（ii）。符合条件（i）或（ii）的多面体的最简单示例是简单，子集总和polytope和knapsack或多维背包多型。我们将这些结果应用于参数多面体，并表明函数的步骤多项式表示形式$ c_p（y）= | p_ {y} \ cap z^n | $，其中$ p_ {y} $是parametric polytope，即使在varying dimension dimension dife $ p_} $ ii）或结束了i} $ collectime {y} $ collectime cometimal polytope中，也可以计算。另一个结果，我们证明了ehrhart quasi-polynomial $$ \ left的系数$ e_i（p，m）$ mp \ cap z^n \ right | = \ sum \ limits_ {j = 0}^n e_i（p，m）m^j $$可以通过固定$ k $和$δ$的多项式时间算法来计算。
Let a polyhedron $P$ be defined by one of the following ways: (i) $P = \{x \in R^n \colon A x \leq b\}$, where $A \in Z^{(n+k) \times n}$, $b \in Z^{(n+k)}$ and $rank\, A = n$; (ii) $P = \{x \in R_+^n \colon A x = b\}$, where $A \in Z^{k \times n}$, $b \in Z^{k}$ and $rank\, A = k$. And let all rank order minors of $A$ be bounded by $Δ$ in absolute values. We show that the short rational generating function for the power series $$ \sum\limits_{m \in P \cap Z^n} x^m $$ can be computed with the arithmetic complexity $ O\left(T_{SNF}(d) \cdot d^{k} \cdot d^{\log_2 Δ}\right), $ where $k$ and $Δ$ are fixed, $d = \dim P$, and $T_{SNF}(m)$ is the complexity to compute the Smith Normal Form for $m \times m$ integer matrix. In particular, $d = n$ for the case (i) and $d = n-k$ for the case (ii). The simplest examples of polyhedra that meet conditions (i) or (ii) are the simplicies, the subset sum polytope and the knapsack or multidimensional knapsack polytopes. We apply these results to parametric polytopes, and show that the step polynomial representation of the function $c_P(y) = |P_{y} \cap Z^n|$, where $P_{y}$ is parametric polytope, can be computed by a polynomial time even in varying dimension if $P_{y}$ has a close structure to the cases (i) or (ii). As another consequence, we show that the coefficients $e_i(P,m)$ of the Ehrhart quasi-polynomial $$ \left| mP \cap Z^n\right| = \sum\limits_{j = 0}^n e_i(P,m)m^j $$ can be computed by a polynomial time algorithm for fixed $k$ and $Δ$.
