On the arithmetic complexity of computing Grobner bases of comaximal determinantal ideals

作     者：Gopalakrishnan, Sriram 

作者机构：Sorbonne Univ 4 Pl Jussieu F-75005 Paris France Univ Waterloo 200 Univ Ave W Waterloo ON N2L 3G1 Canada 

出 版 物：《JOURNAL OF ALGEBRA》 (J. Algebra)

年 卷 期：2025年第668卷

页      面：233-264页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Quantum Information Center Sorbonne (QICS) Agence Nationale de la Recherche (ANR) [ANR-18-CE33-0011 SESAME, ANR-23-CE48-0003 CREAM, ANR-19-CE40-0018 DE RERUM NATURA] ANR-Austrian Science Fund FWF [ANR-22-CE91-0007 EAGLES, ANR-FWF ANR-19-CE48-0015 ECARP] EOARD-AFOSR [FA8665-20-1-7029] 

主　　题：Grobner basis Polynomial system solving Determinantal ideals Arithmetic complexity 

摘      要：Let M be an nxn matrix of homogeneous linear forms over a field k. If the ideal In-2(M) generated by minors of size n-1 is Cohen-Macaulay, then the Gulliksen-Negard complex is a free resolution of In-2(M). It has recently been shown that by taking into account the syzygy modules for In-2(M) which can be obtained from this complex, one can derive a refined signature-based Grobner basis algorithm DetGB which avoids reductions to zero when computing a grevlex Grobner basis for In-2(M). In this paper, we establish sharp complexity bounds on DetGB. To accomplish this, we prove several results on the sizes of reduced grevlex Grobner bases of reverse lexicographic ideals, thanks to which we obtain two main complexity results which rely on conjectures similar to that of Froberg. The first one states that, in the zero-dimensional case, the size of the reduced grevlex Grobner basis of In-2(M) is bounded from below by n(6) asymptotically. The second, also in the zero-dimensional case, states that the complexity of DetGB is bounded from above by n(2 omega+3) asymptotically, where 2 =omega = 3 is any complexity exponent for matrix multiplication over k. (c) 2025 The Author. Published by Elsevier Inc. This is an open access article under the CC BY license (http:// ***/licenses/by/4.0/).