The Eisenbud–Green–Harris conjecture on Hilbert functions of ideals containing a regular sequence

The Eisenbud–Green–Harris (EGH) conjecture, raised in 1993, predicts that the Hilbert function of a homogeneous ideal containing a regular sequence of degrees $a_1,\dots,a_n$ is governed, degree by degree, by the corresponding lex-plus-powers ideal — a sharp refinement of Macaulay's classical bound on Hilbert-function growth. In the original quadrics case (Conjecture $V_m$) it asserts $H_{R/I}(d+1)\le H_{R/I}(d)^{(d)}$ with a fixed-top Macaulay raising, strictly sharper than Macaulay's theorem. Despite thirty years of work the conjecture is open in general, and its quadrics case is proved only for at most five variables (plus special structures in six). The conjecture is the hypothesis on which the sharpest known bounds on the maximal Gröbner-basis degree of overdetermined quadratic polynomial systems — and on their solving degree when the defining ideal is in generic coordinates — rest; these are the estimates used to gauge the cost of Gröbner-basis attacks in multivariate cryptography, so a proof or refutation would directly change both core commutative algebra and these cryptographic complexity estimates.

Background

Gröbner-basis methods are the standard tool for solving systems of polynomial equations over finite fields, and their cost is the security anchor of multivariate public-key cryptography and of index-calculus attacks on elliptic-curve discrete logarithms. The algorithms in question (F4/F5 and their relatives) repeatedly apply Gaussian elimination to Macaulay matrices — matrices whose rows are the input polynomials multiplied by all monomials up to a given degree — and their complexity is controlled by the largest degree that must be processed, called the solving degree of the system. A related invariant, the degree of regularity, is the smallest degree at which the ideal generated by the highest-degree parts of the equations contains all monomials of that degree; it is widely used as a heuristic proxy for the solving degree, although examples show it is not an upper bound.

Both parameters are governed by classical commutative algebra. Let $K$ be a field and $R=K[x_1,\dots,x_n]$ with the standard grading, so that $(R/I)_d$ is the vector space of degree-$d$ residue classes and the Hilbert function is $H_{R/I}(d)=\dim_K(R/I)_d$. Macaulay's theorem bounds the growth of the Hilbert function of every graded quotient: if $h=H_{R/I}(d)$ has the degree-$d$ binomial (Macaulay) expansion $h=\binom{b_d}{d}+\binom{b_{d-1}}{d-1}+\dots+\binom{b_1}{1}$ with $b_d>b_{d-1}>\dots\ge b_1\ge0$, then $H_{R/I}(d+1)\le\binom{b_d+1}{d+1}+\binom{b_{d-1}+1}{d}+\dots+\binom{b_1+1}{2}$; the bound is tight and is attained by quotients by lexicographic (lex) ideals — monomial ideals that contain, in each degree, the largest monomials in the lexicographic order.

Macaulay's bound uses nothing about the ideal beyond its Hilbert function. A regular sequence is a sequence of homogeneous polynomials $f_1,\dots,f_r$ such that $f_i$ is a nonzerodivisor on $R/(f_1,\dots,f_{i-1})$; containing one is strong structural information (an ideal generated by a full-length regular sequence is a complete intersection, and its Hilbert function depends only on the degrees $a_i$). Eisenbud, Green, and Harris, motivated by Cayley–Bacharach-type questions on point sets that impose independent conditions on hypersurfaces, conjectured in Higher Castelnuovo Theory (1993) that this structure forces a sharper bound. Their conjecture (EGH) predicts: if the homogeneous ideal $I\subseteq R$ contains a regular sequence of degrees $2\le a_1\le\dots\le a_n$ (a full-length, i.e. $n$-element, regular sequence), then the Hilbert function of $R/I$ coincides, degree by degree, with that of a lex-plus-powers ideal — an ideal of the form $(x_1^{a_1},\dots,x_n^{a_n})+J$ with $J$ a lex ideal. Equivalently, the monomial object $\mathrm{LPP}_{\mathbf a}(I)$ constructed degree-by-degree from $H_{R/I}$ is itself an ideal. In the original case of a regular sequence of quadrics ($a_1=\dots=a_n=2$; their Conjecture $V_m$) the assertion takes a Macaulay-type form: $H_{R/I}(d+1)\le H_{R/I}(d)^{(d)}$ for all $d>0$, where the raising $\ell^{(d)}$ keeps the top indices of the Macaulay expansion fixed ($\ell=\binom{b_d}{d}+\dots+\binom{b_1}{1}$ gives $\ell^{(d)}=\binom{b_d}{d+1}+\dots+\binom{b_1}{2}$) — a strictly finer inequality than Macaulay's, which raises both indices.

The cryptographic connection is direct. Semi-regular sequences — homogeneous sequences $f_1,\dots,f_m$ whose quotient has the Hilbert series $\prod_i(1-z^{d_i})/(1-z)^n$ truncated at non-negative values, i.e. sequences with as few syzygies as possible — are the standard model of a random overdetermined system, and Pardue conjectured (a statement equivalent to Fröberg's conjecture on Hilbert series of generic forms) that they are generic over infinite fields. The source paper, Bigdeli–De Negri–Dizdarevic–Gorla–Minko–Tsakou (2021) [1], proves that under EGH for quadrics (its Conjecture 4.3) the maximal Gröbner-basis degree of any system of $m>n$ linearly independent quadratic equations whose ideal contains a regular sequence of $n$ quadrics is at most $n-\alpha$, where $\alpha$ is read off from $m$ and $n$, and its solving degree is at most $n-\alpha$ when the ideal is in addition in generic coordinates (Theorem 4.4), with parallel conditional bounds for inhomogeneous systems (Theorem 4.7) and for systems obtained by Weil descent — the standard rewriting of a system over an extension field into a system over the base field, used in index-calculus and in cryptanalysis over $\mathbb F_2$ (Corollaries 4.6 and 4.9). These are the sharpest bounds available for such systems; unconditionally only the coarser Macaulay bound holds. The conjecture is known for ideals generated by generic quadrics, for monomial ideals, for ideals whose regular-sequence elements split into linear factors, for fast-growing degree sequences $a_i\ge\sum_{j<i}(a_j-1)$, and for quadrics in at most five variables — but open in general and for quadrics in six or more variables.

Problem Statement

Let $K$ be an arbitrary field and $R=K[x_1,\dots,x_n]$ with the standard grading; write $H_{R/L}(d)=\dim_K(R/L)_d$ for the Hilbert function of a graded quotient, i.e. the dimension of its vector space of degree-$d$ residue classes. Recall that a lex ideal is a monomial ideal containing, in each degree, every monomial that precedes one of its minimal generators of the same degree in the lexicographic order. The Eisenbud–Green–Harris conjecture asserts: if $I\subseteq R$ is a homogeneous ideal containing a regular sequence $f_1,\dots,f_n$ with $\deg f_i=a_i$, where $2\le a_1\le\dots\le a_n$, then there exists a lex-plus-powers ideal $L=(x_1^{a_1},\dots,x_n^{a_n})+J$, with $J$ a lex ideal of $R$, such that $H_{R/L}(d)=H_{R/I}(d)$ for all $d\ge0$. Equivalently: let $\mathbf a=(x_1^{a_1},\dots,x_n^{a_n})$ be the pure-powers ideal and, for each $d>0$, let $L_d\subseteq R_d$ be the largest lex-segment with $\dim_K\langle L_d+\mathbf a_d\rangle=\dim_K I_d$, where $\mathbf a_d$ is the degree-$d$ component of $\mathbf a$; the conjecture predicts that the graded vector space $\mathrm{LPP}_{\mathbf a}(I)=\sum_{d>0}\langle L_d+\mathbf a_d\rangle$ is an ideal (the construction terminates, since $I$ contains a full-length regular sequence, so $R/I$ is Artinian and $I_d=R_d$ for $d\gg0$). In the quadrics case $a_1=\dots=a_n=2$ (Conjecture $V_m$ of Eisenbud–Green–Harris, invoked as Conjecture 4.3 of the source paper), this is equivalent to the Macaulay-type growth inequality

$$H_{R/I}(d+1)\le\bigl(H_{R/I}(d)\bigr)^{(d)}\quad\text{for all }d>0,$$

where, if $h=H_{R/I}(d)$ has the Macaulay (binomial) expansion $h=\binom{b_d}{d}+\binom{b_{d-1}}{d-1}+\dots+\binom{b_1}{1}$ with $b_d>b_{d-1}>\dots\ge b_1\ge0$ with respect to $d$, then $h^{(d)}=\binom{b_d}{d+1}+\binom{b_{d-1}}{d}+\dots+\binom{b_1}{2}$ (top indices fixed — strictly stronger than Macaulay's theorem, which would permit $\binom{b_d+1}{d+1}+\binom{b_{d-1}+1}{d}+\dots$).

The problem is to prove the conjecture for arbitrary fields, numbers of variables, and degree sequences — in particular to settle the quadrics case, which would make the solving-degree bounds of the source paper for overdetermined quadratic systems unconditional — or to refute it by exhibiting an explicit homogeneous ideal $I$ containing a regular sequence of the claimed degrees for which no lex-plus-powers ideal $(x_1^{a_1},\dots,x_n^{a_n})+J$ has the same Hilbert function as $R/I$; in the quadrics case, equivalently, an $I$ whose Hilbert function violates the growth inequality above in some degree.

References

1. Mina Bigdeli, Emanuela De Negri, Manuela Muzika Dizdarevic, Elisa Gorla, Romy Minko, Sulamithe Tsakou. Semi-Regular Sequences and Other Random Systems of Equations. In: Women in Number Europe III, Association for Women in Mathematics Series, Springer, 2021. DOI: 10.1007/978-3-030-77700-5_3; arXiv:2011.01032. https://arxiv.org/abs/2011.01032
2. David Eisenbud, Mark Green, Joe Harris. Higher Castelnuovo Theory. Astérisque 218, 187–202, 1993 (Journées de Géométrie Algébrique d'Orsay, 1992). SMF (Astérisque 218): https://smf.emath.fr/Publications/Asterisque/1993/218/html/smf_ast_218_187-202.html
3. David Eisenbud, Mark Green, Joe Harris. Cayley-Bacharach theorems and conjectures. Bulletin of the American Mathematical Society (N.S.) 33(3), 295–324, 1996. DOI: 10.1090/S0273-0979-96-00666-0. https://doi.org/10.1090/S0273-0979-96-00666-0
4. Giulio Caviglia, Alessandro De Stefani, Enrico Sbarra. The Eisenbud-Green-Harris Conjecture. In: Commutative Algebra, Springer, 159–187, 2021. DOI: 10.1007/978-3-030-89694-2_5; arXiv:2106.14759. https://arxiv.org/abs/2106.14759
5. Sema Güntürkün. A Survey on the Eisenbud-Green-Harris Conjecture. In: Women in Commutative Algebra, Association for Women in Mathematics Series, Springer, 327–342, 2022. DOI: 10.1007/978-3-030-91986-3_13; arXiv:2103.14106. https://arxiv.org/abs/2103.14106
6. Sema Güntürkün, Melvin Hochster. The Eisenbud-Green-Harris Conjecture for Defect Two Quadratic Ideals. Mathematical Research Letters 27(5), 1341–1365, 2020. DOI: 10.4310/MRL.2020.v27.n5.a4; arXiv:1812.07539. https://arxiv.org/abs/1812.07539
7. Giulio Caviglia, Alessandro De Stefani. The Eisenbud-Green-Harris conjecture for fast-growing degree sequences. Annali della Scuola Normale Superiore di Pisa, Classe di Scienze (5) 25(3), 1753–1762, 2024. DOI: 10.2422/2036-2145.202203_025; arXiv:2007.15467. https://arxiv.org/abs/2007.15467
8. Giulio Caviglia, Diane Maclagan. Some cases of the Eisenbud-Green-Harris conjecture. Mathematical Research Letters 15(3), 427–433, 2008. DOI: 10.4310/MRL.2008.v15.n3.a3; arXiv:math/0611488. https://arxiv.org/abs/math/0611488
9. Abed Abedelfatah. On the Eisenbud-Green-Harris Conjecture. Proceedings of the American Mathematical Society 143(1), 105–115, 2015. DOI: 10.1090/S0002-9939-2014-12216-7; arXiv:1212.2653. https://arxiv.org/abs/1212.2653
10. Abed Abedelfatah. Quadratic Ideals in Six Variables and the Eisenbud–Green–Harris Conjecture. arXiv:2607.20035, 2026. https://arxiv.org/abs/2607.20035
11. Alessio Caminata, Elisa Gorla. Solving Multivariate Polynomial Systems and an Invariant from Commutative Algebra. In: Arithmetic of Finite Fields (WAIFI 2020), Lecture Notes in Computer Science 12542, Springer, 3–36, 2021. DOI: 10.1007/978-3-030-68869-1_1; arXiv:1706.06319. https://arxiv.org/abs/1706.06319
12. Alessio Caminata, Elisa Gorla. Solving degree, last fall degree, and related invariants. Journal of Symbolic Computation 114, 322–335, 2023. DOI: 10.1016/j.jsc.2022.05.001; arXiv:2112.05579. https://arxiv.org/abs/2112.05579
13. Elisa Gorla, Daniela Mueller, Christophe Petit. Stronger bounds on the cost of computing Gröbner bases for HFE systems. Journal of Symbolic Computation 109, 386–398, 2022. DOI: 10.1016/j.jsc.2020.07.011; arXiv:2011.01050. https://arxiv.org/abs/2011.01050
14. Alessio Caminata, Michela Ceria, Elisa Gorla. The complexity of solving Weil restriction systems. Journal of Algebra 621, 116–133, 2023. DOI: 10.1016/j.jalgebra.2023.01.008; arXiv:2112.10506. https://arxiv.org/abs/2112.10506
15. Timothy J. Hodges, Sergio D. Molina, Jacob Schlather. On the existence of homogeneous semi-regular sequences in $\mathbb F_2[X_1,\dots,X_n]/(X_1^2,\dots,X_n^2)$. Journal of Algebra 476, 519–547, 2017 (arXiv preprint title: On the Existence of Semi-Regular Sequences). DOI: 10.1016/j.jalgebra.2016.11.025; arXiv:1412.7865. https://arxiv.org/abs/1412.7865
16. Timothy J. Hodges, Hari R. Iyer. Semi-regularity of pairs of Boolean polynomials. Finite Fields and Their Applications 79, 101992, 2022. DOI: 10.1016/j.ffa.2022.101992. https://doi.org/10.1016/j.ffa.2022.101992
17. John Baena, Daniel Cabarcas, Sharwan K. Tiwari, Javier Verbel, Luis Villota. Admissible parameters for the Crossbred algorithm and semi-regular sequences over finite fields. Designs, Codes and Cryptography 93, 2561–2589, 2025. DOI: 10.1007/s10623-025-01610-2. https://doi.org/10.1007/s10623-025-01610-2
18. Magali Bardet, Jean-Charles Faugère, Bruno Salvy. Complexity of Gröbner basis computation for semi-regular overdetermined sequences over $\mathbb F_2$ with solutions in $\mathbb F_2$. INRIA Research Report RR-5049, 2003. HAL: https://hal.science/inria-00071534
19. Ralf Fröberg. An inequality for Hilbert series of graded algebras. Mathematica Scandinavica 56, 117–144, 1985. DOI: 10.7146/math.scand.a-12092. https://doi.org/10.7146/math.scand.a-12092
20. Keith Pardue. Generic sequences of polynomials. Journal of Algebra 324(4), 579–590, 2010. DOI: 10.1016/j.jalgebra.2010.04.018. https://doi.org/10.1016/j.jalgebra.2010.04.018
21. Ralf Fröberg, Clas Löfwall. Generic forms. arXiv:2504.13591, 2025. https://arxiv.org/abs/2504.13591
22. Flavio Salizzoni. An upper bound for the solving degree in terms of the degree of regularity. arXiv:2304.13485, 2023. https://arxiv.org/abs/2304.13485
23. Momonari Kudo, Kazuhiro Yokoyama. On Hilbert-Poincaré series of affine semi-regular polynomial sequences and related Gröbner bases. arXiv:2401.07768, 2024. https://arxiv.org/abs/2401.07768
24. Momonari Kudo, Kazuhiro Yokoyama. The solving degrees for computing Gröbner bases of affine semi-regular polynomial sequences. arXiv:2404.03530, 2024. https://arxiv.org/abs/2404.03530
25. Antonio Corbo Esposito, Rosa Fera, Francesco Romeo. Hilbert series and degrees of regularity of Oil & Vinegar and mixed quadratic systems. Designs, Codes and Cryptography 93, 3521–3541, 2025. DOI: 10.1007/s10623-025-01644-6. https://doi.org/10.1007/s10623-025-01644-6