On the Existence of Semi-Regular Sequences

Semi-regular sequences over ${\mathbb{F}}_2$ are sequences of homogeneous elements of the algebra $B^{(n)}={\mathbb{F}}_2[X_1,\mathrm{.}\mathrm{.}\mathrm{.},X_n]\mathrm{/}(X_1^2,\mathrm{.}\mathrm{.}\mathrm{.},X_n^2)$, which have as few relations between them as possible. They were introduced in order to assess the complexity of Gr"obner basis algorithms such as ${\bf F}_4, {\bf F}_5$ 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\le 3d$. Also, we show that if $d=2^t$ and $n=3d$ there exits 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$.