On the existence of homogeneous semi-regular sequences in F2[X1,...,Xn]/(X12,...,Xn2)

Semi-regular sequences over F2 are sequences of homogeneous elements of the algebra B(n)=F2[X1,...,Xn]/(X12,...,Xn2), which have as few relations between them as possible. They were introduced in order to assess the complexity of Gröbner basis algorithms such as F4 and F5 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. We prove some results on the existence and non-existence of semi-regular sequences. In particular, we show that if an element of degree d in B(n) is semi-regular, then we must have n≤3d. Also, we show that if d=2t and n=3d, then there exists a semi-regular element of degree d establishing that the bound is sharp for infinitely many n. Finally, we generalize the result of non-existence of semi-regular elements to the case of sequences of a fixed length m.