{"id":"arxiv/2603.16378","url":"https://arxiv.org/abs/2603.16378","tags":["cs.SC","math.AC"],"score":0,"title":"A complexity analysis of the F4 Gröbner basis algorithm with tracer data","domain":"cs.SC","source":"arxiv","authors":["Robin Kouba","Vincent Neiger","Mohab Safey El Din"],"reviews":0,"subject":"cs.SC","summary":"We provide a new complexity bound for the computation of grevlex Gröbner bases in the generic zero-dimensional case, relying on Moreno-Socías' conjecture. We first formalize a property of regular sequences that implies a well-known folklore consequence, which we call the increasing degree property. We then derive a new understanding of the selection of pairs in the F4 algorithm based on Moreno-Socías' conjecture. Moreover, we obtain an exact formula for the number of elements in the grevlex Gröbner basis of a given degree, for half of the relevant degrees. Combining these results, we derive…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-17","reactions":{}}