  Semi-regular sequences over $\mathbb{F}_2$ are sequences of homogeneous
elements of the algebra $ B^{(n)}=\mathbb{F}_2[X_1,...,X_n]/(X_1^2,...,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\leq 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$.
