A new lower bound construction for commutative thue systems with applications
Chee Keng Yap · Journal of Symbolic Computation · 1991
For n ≥1, d ≥ 2, we describe a commutative Thue system that has ∼2n variables and O(n) rules, each rule of size d + O(1) and that counts to d2n in a certain technical sense. This gives a more “efficient” alternative to a well-known construction of Mayr and Meyer. Using this construction, we sharpen the known double-exponential lower bounds for the maximum degrees D(n, d), I(n, d), S(n, d) associated (respectively) with Gröbner bases, ideal membership problem and the syzygy basis problem: D(n,d)≥S(n,d)≥d2m,I(n,d)≥d2m, where m∼n/2, and n, d sufficiently large. For comparison, it was known that D(n, d) ≤ d2n and I(n, d) ≤ (2d)2n.