A new lower bound construction for commutative Thue systems with applications
The author describes a commutative Thue system with about 2n variables and O(n) rules, each of size \(d+0(1)\), that ``counts'' to \(d^{2^ n}\) in a certain technical sense. Using this construction he is able to sharpen the known double-exponential lower bounds for (i) the maximum degree D(n,d) of Gröbner basis, (ii) the maximum degree I(n,d) in ideal membership, and (iii) the maximum degree S(n,d) of the syzygy basis problem: \(D(n,d)\geq S(n,d)\geq d^{2^ m},\) \(I(n,d)\geq d^{2^ m},\) where \(m\sim n/2\), and n, d sufficiently large.
maximum degree of the syzygy basis problem
scientific article; zbMATH DE number 4209609
scientific article