Semi-Regular Sequences over F2

Abstract: The concept of semi-regular sequences was introduced in order to assess the complexity of Gröumlbner basis algorithms such as F4 for the solution of polynomial equations. Despite the experimental evidence that semi-regular sequences are common, it was unknown whether there existed semi-regular sequences for all n, except in extremely trivial situations. In the present work, I prove some results on the existence and non-existence of semi-regular sequences. It was observed by J. Schlather and T. Hodges that if an element of degree d in Β(n)-variables is semi-regular, then we must have n≤3d. In this thesis, I establish precisely when the elementary symmetric polynomial of degree d is semi-regular. In particular, when d=2t and n=3d, the elementary symmetric polynomial of degree d is semi-regular establishing that the bound given by J. Schlather and T. Hodges is sharp for infinitely many n. For the general case of existence of semi-regular sequences Bardet, Faug&egravere and Salvy conjecture that the proportion π(n, m, d1, . . . , dm) of semiregular sequences over F2 in the set Ε(n, m, d1, . . . , dm) of algebraic systems of mequations of degrees d1, . . . , dm in n-variables tends to 1 as n tends to infinity. In this work, I show that for a fixed choice of (m, d1, . . . , dm), we have that limn→∞ π(n, m, d1, .. . , dm ) — 0 showing that the conjecture is false in this case