Paper 2020/1538

Homological Characterization of bounded $F_2$-regularity

Timothy J. Hodges and Sergio Molina

Abstract

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. It is believed that most such systems are semi-regular and this property has important consequences for understanding the complexity of Grobner basis algorithms such as F4 and F5 for solving such systems. In fact even in one of the simplest and most important cases, that of quadratic sequences of length $n$ in $n$ variables, the question of the existence of semi-regular sequences for all $n$ remains open. In this paper we present a new framework for the concept of semiregularity which we hope will allow the use of ideas and machinery from homological algebra to be applied to this interesting and important open question. First we introduce an analog of the Koszul complex and show that $\mathbb{F}_2$-semi-regularity can be characterized by the exactness of this complex. We show how the well known formula for the Hilbert series of a semiregular sequence can be deduced from the Koszul complex. Finally we show that the concept of first fall degree also has a natural description in terms of the Koszul complex.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Semi-regular sequenceKoszul complex
Contact author(s)
timothy hodges @ uc edu
History
2020-12-13: received
Short URL
https://ia.cr/2020/1538
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1538,
      author = {Timothy J.  Hodges and Sergio Molina},
      title = {Homological Characterization of bounded $F_2$-regularity},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1538},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1538}},
      url = {https://eprint.iacr.org/2020/1538}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.