论文标题
Gröbner基础和临界值：确定性系统的渐近组合学
Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems
论文作者
论文摘要
我们考虑涉及多项式基质的最大未成年人的理想。例如，在多项式限制多项式优化的多项式的临界值的计算中产生的。 Gröbner基础是解决多项式系统的经典工具。对于实际计算，这包括两个阶段。首先，根据DRL（逆向词典）排序计算Gröbner基础。然后，通过Faugère和Mou设计的订购算法的更改，例如\ textsf {稀疏fglm}，用于找到相同理想的Gröbner基础，但相对于词典排序。就算术操作而言，后一个步骤的复杂性为$ O（md^2）$，其中$ d $是理想的程度，$ m $是特定$ d \ times d $矩阵的非平凡列的数量。虽然渐近估计值以通用多项式系统而闻名，但到目前为止，\ textsf {稀疏fglm}的复杂性对于确定性系统而言尚不清楚。 通过假设Fröberg的猜想，我们通过在确定环境中详细介绍DRL楼梯的结构来扩展Moreno-Socías的工作。然后，我们通过将其与这些希尔伯特系列的系数联系起来，研究数量$ m $的渐近学。因此，我们对\ textsf {稀疏fglm}算法的复杂性达到了新的限制，用于通用确定系统和通用临界点系统。我们考虑了多项式环$ \ mathbb {k} [x_1，\ dots，x_n] $中的理想，其中$ \ mathbb {k} $是某个无限领域，由$ p $ p $ generic po $ dg $ $ d $和$ p \ times $ p pynomial $ dnomial $ dnom nomial $ dnomial nix $ p pynomials $ d-nim y ricix of $ p $ poline polynomials生成。然后，对于$ d = 2 $，对于$ n \ gg p $，我们给出了$ n $和$ p $的$ m $的确切公式。此外，对于$ d \ geq 3 $，我们给出一个渐近公式，为$ n \ to \ infty $，以$ n，p $和$ d $表示$ m $。
We consider ideals involving the maximal minors of a polynomial matrix. For example, those arising in the computation of the critical values of a polynomial restricted to a variety for polynomial optimisation. Gröbner bases are a classical tool for solving polynomial systems. For practical computations, this consists of two stages. First, a Gröbner basis is computed with respect to a DRL (degree reverse lexicographic) ordering. Then, a change of ordering algorithm, such as \textsf{Sparse-FGLM}, designed by Faugère and Mou, is used to find a Gröbner basis of the same ideal but with respect to a lexicographic ordering. The complexity of this latter step, in terms of arithmetic operations, is $O(mD^2)$, where $D$ is the degree of the ideal and $m$ is the number of non-trivial columns of a certain $D \times D$ matrix. While asymptotic estimates are known for $m$ for generic polynomial systems, thus far, the complexity of \textsf{Sparse-FGLM} was unknown for determinantal systems. By assuming Fröberg's conjecture we expand the work of Moreno-Socías by detailing the structure of the DRL staircase in the determinantal setting. Then we study the asymptotics of the quantity $m$ by relating it to the coefficients of these Hilbert series. Consequently, we arrive at a new bound on the complexity of the \textsf{Sparse-FGLM} algorithm for generic determinantal systems and for generic critical point systems. We consider the ideal in the polynomial ring $\mathbb{K}[x_1, \dots, x_n]$, where $\mathbb{K}$ is some infinite field, generated by $p$ generic polynomials of degree $d$ and the maximal minors of a $p \times (n-1)$ polynomial matrix with generic entries of degree $d-1$. Then for the case $d=2$ and for $n \gg p$ we give an exact formula for $m$ in terms of $n$ and $p$. Moreover, for $d \geq 3$, we give an asymptotic formula, as $n \to \infty$, for $m$ in terms of $n,p$ and $d$.
