A new lower bound construction for commutative Thue systems with applications (Q808265)

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.