一句话:研究等变多项式理想的有限基,扩展 Buchberger 算法计算 Gröbner 基并判定成员问题。
本文研究无限多变量多项式的理想。变量取自可数逻辑结构 A,A 到 A 的嵌入通过重命名变量作用于多项式。作者首先刻画 A 需满足的充分必要条件,以保证 Hilbert 基定理的如下推广成立:每个在变量重命名下不变的等变多项式理想都有限生成。其次,他们把经典 Buchberger 算法推广到该设定,用以计算给定等变理想的 Gröbner 基,由此得到等变理想成员问题的可判定性。最后概述结果在寄存器自动机、带数据 Petri 网、轨道有限生成向量空间和轨道有限线性方程组等方向的应用。
We study existence and computability of finite bases for ideals of polynomials over infinitely many variables. In our setting, variables come from a countable logical structure A, and embeddings from A to A act on polynomials by renaming variables. First, we give a sufficient and necessary condition for A to guarantee the following generalisation of Hilbert's Basis Theorem: every polynomial ideal which is equivariant, i.e. invariant under renaming of variables, is finitely generated. Second, we develop an extension of classical Buchberger's algorithm to compute a Gröbner basis of a given equivariant ideal. This implies decidability of the membership problem for equivariant ideals. Finally, we sketch upon various applications of these results to register automata, Petri nets with data, orbitfinitely generated vector spaces, and orbit-finite systems of linear equations.