On the existence of homogeneous semi-regular sequences in F₂[X₁,,X_n]/(X₁^2,,X_n^2)

DOI10.1016/J.JALGEBRA.2016.11.025MaRDI QIDQ511873zbMATH OpenOpenAlexFDO

Authors Timothy J. Hodges, Sergio D. Molina, Jacob Schlather

Publication date 22 February 2017

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.7865

zbMATH Keywords

existencefinite fieldnon-existencesemi-regular sequences

Mathematics Subject Classification ID

Computational methods for problems pertaining to field theory (12-08) Polynomials in general fields (irreducibility, etc.) (12E05) Syzygies, resolutions, complexes and commutative rings (13D02) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Solving polynomial systems; resultants (13P15)

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

Recommendations

• Semi-regularity of pairs of Boolean polynomials
• Homological characterization of bounded \(\mathbb{F}_2\)-regularity
• Bounded regularity
• Syzygies of semi-regular sequences
• Semi-regular sequences and other random systems of equations

Cites work

• Bounded regularity
• First fall degree and Weil descent
• GROWTH OF THE IDEAL GENERATED BY A QUADRATIC MULTIVARIATE FUNCTION OVER GF(3)
• scientific article; zbMATH DE number 1114507 (Why is no real title available?)
• The degree of regularity of HFE systems

Cited in

(9)

• Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gröbner bases
• Homological characterization of bounded \(\mathbb{F}_2\)-regularity
• Syzygies of semi-regular sequences
• Semi-regularity of pairs of Boolean polynomials
• Semi-regular sequences and other random systems of equations
• A single exponential time algorithm for homogeneous regular sequence tests
• On the soundness of algebraic attacks against code-based assumptions
• Wedges, oil, and vinegar. An analysis of UOV in the exterior algebra
• Multivariate signatures with polynomial factorization

This page was built for publication: On the existence of homogeneous semi-regular sequences in \(\mathbb{F}_2[X_1,\ldots,X_n]/(X_1^2,\ldots,X_n^2)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511873)