Removing the first-fall-degree heuristic

Formal research question

Let $E/\mathbb F_{q^n}$ be an elliptic curve, let $f_{m+1}(x_1,\ldots,x_{m+1})$ be Semaev's summation polynomial, and let $S(q,n,m)$ be a polynomial system over $\mathbb F_q$ obtained by Weil restriction.

Given $q,n,m$, find an unconditional, explicit upper bound on the degree of regularity or solving degree of $S(q,n,m)$ without assuming that its first fall degree approximates either quantity.

PROVED For regularity and solving degree, the repository's finite-field system convention is

[ F(q,n,m)=S(q,n,m)\cup {x_1^q-x_1,\ldots,x_m^q-x_m}. ]

First fall remains defined in the finite-field function ring as recorded in NOTES.md.

The eventual target regime is $n\sim\log q$. The initial experimental range is $n\in\{2,3\}$ and $m\leq 4$.

Global formal bound (2026-07-23)

PROVED For every standard Weil-restricted Semaev system and every degree-compatible monomial order,

[ d_{\mathrm{reg}}(F)\le m(q-1)+1,\qquad \operatorname{sd}(F)\le \max{m(q-1)+2,m2^{m-1}}. ]

The first bound follows because the top ideal contains $(x_1^q,\ldots,x_m^q)$. The second combines it with the individual-degree formula for $f_{m+1}$ and Salizzoni (2023), Proposition 3.10. This is an unconditional explicit answer for all $q,n,m$, independent of $n$, but it is intentionally not presented as a subexponential cryptanalytic bound. The proof and adversarial audit are in CLAIM.md and A007.

Strong target resolved negatively (2026-07-23)

PROVED The displayed global bound does not remove the cryptanalytic use of the first-fall heuristic: it is linear in $q$, exponential in $m$, and does not give the hoped-for bound in the regime $n\sim\log q$.

PROVED A008 proves that this weakness is unavoidable for a universal theorem. Every proper Weil core generated by at most $n<m$ coordinate equations satisfies

[ \operatorname{sd}_\sigma(F)\ge q ]

for every degree-compatible order. It also constructs an infinite nonsingular $n=2,m=3$ Semaev family with non-base targets for which

[ d_{\mathrm{ff}}=14,\qquad q\le\operatorname{sd}_\sigma(F)\le2q+2. ]

Thus no $q$-independent, first-fall-scale universal replacement for A007 exists under the explicit-field-equation convention. In the regime $n\asymp\log q$, every solvable underdetermined system $m>n$ already has a degree lower bound exponential in $n$.

Sharper factor-base-size-two resolution (2026-07-23)

PROVED For odd $q$, $m=2$, and any non-base target in any extension, the constant-degree mutant construction gives

[ \operatorname{sd}_{\mathrm{grevlex}}(F)\le\max{q,5}. ]

Thus the earlier $q$-bound is not restricted to $n=2$; A006 proves it for every extension degree. The exact first-fall/regularity classification below remains special to $n=2$.

Quadratic resolution (2026-07-23)

For $n=m=2$, odd prime powers $q\ge5$, nonsingular short-Weierstrass curves, and non-base target $x$-coordinates, the strongest unconditional statement proved here is

[ d_{\mathrm{ff}}=5,\qquad d_{\mathrm{reg}}=q,\qquad \operatorname{sd}_{\mathrm{grevlex}}\le q. ]

For $q>5$, the equality $\operatorname{sd}_{\mathrm{grevlex}}=q$ holds if and only if the field equations enlarge the two-coordinate core ideal. Automatic nonredundancy is false: attempts/A005-field-equation-counterexample.md gives an infinite eligible Semaev family with redundant field equations and certifies a $q=7$ example with solving degree $5$, not $7$.

Session-one target

Fix conventions for first fall degree, degree of regularity, solving degree, and the maximum degree reached by a concrete algorithm. Give a worked toy example that separates the notions, and establish a route to observable intermediate-degree data.

State in five lines

PROVED With explicit field equations, $d_{\mathrm{reg}}\le m(q-1)+1$ and $\operatorname{sd}\le\max\{m(q-1)+2,m2^{m-1}\}$ for all $q,n,m$. PROVED Every proper core generated by at most $n<m$ coordinates has $\operatorname{sd}_\sigma\ge q$ for every degree-compatible order. PROVED An infinite genuine $n=2,m=3$ family has $d_{\mathrm{ff}}=14,d_{\mathrm{reg}}=2q+1$, and $q\le\operatorname{sd}_\sigma\le2q+2$. PROVED For odd $q$, $m=2$, and every non-base target in any extension, $\operatorname{sd}_{\mathrm{grevlex}}\le\max\{q,5\}$. REFUTED A $q$-independent first-fall-scale universal bound for $m>2$ cannot hold under the fixed convention.

Literal upper bound

Let [ F=S(q,n,m)\cup{x_1^q-x_1,\ldots,x_m^q-x_m}. ]

PROVED The top ideal contains $(x_1^q,\ldots,x_m^q)$, which fills every form in degree $m(q-1)+1$.

CITED Semaev's individual-degree formula bounds each Weil coordinate by total degree $m2^{m-1}$, and Salizzoni (2023), Proposition 3.10, gives [ \operatorname{sd}\sigma(F)\le \max{d{\mathrm{reg}}(F)+1,\max_{f\in F}\deg f}. ]

Strong obstruction

CITED Krull height gives $\operatorname{ht}(C)\le n$ for a core with at most $n$ generators.

PROVED If $n<m$, a proper $C$ cannot contain every field equation: otherwise its quotient would be finite-dimensional and $C$ would have height $m$.

PROVED For $d<q$, $V_{F,d}\subseteq C$. Since $(F)\supsetneq C$, no such space contains a Groebner basis of $(F)$; hence $\operatorname{sd}_\sigma(F)\ge q$.

Exact $m=3$ family

For $q\equiv3\pmod4,q\ge7$, use $\mathbb F_{q^2}=\mathbb F_q[u]/(u^2+1)$, choose $h\notin\{0,\pm1\}$, and set [ \rho=(h+h^{-1})/2,\quad \sigma=(h^{-1}-h)/2,\quad a=-4\sigma^2,\quad c=2\sigma^2. ]

PROVED On $E:Y^2=X^3+aX$, the target $(cu,-2\rho\sigma^2(1-u))$ is on curve and non-base. The triple $(2(1+\rho),-2(1+\rho),0)$ is a root of $f_4(x,y,z,cu)$.

PROVED The two core top parts are [ x^4y^4z^4,\qquad -4c,x^3y^3z^3(xy+xz+yz). ] Their primitive pair gives exact first fall $14$. The full top ideal has exact regularity $2q+1$, and Salizzoni gives the upper bound $2q+2$.

EMPIRICAL: $q=7,11,19$ Exact specializations verify the target, root, top pair, first fall, and nonzero field-equation normal forms.

Factor-base size two

PROVED A006 normalizes the core top parts to $(xy)^2,-2xy(x+y),x^2+\mu xy+y^2$ when the target degree is at least three. Both $\mu$ branches have regularity four and cubic-or-lower field remainders. Target degree two is A004.

PROVED At $n=m=2$, $d_{\mathrm{ff}}=5,d_{\mathrm{reg}}=q,\operatorname{sd}\le q$. For $q>5$, equality holds iff the field equations enlarge the core.

REFUTED Automatic nonredundancy is false. A005 gives an infinite redundant family and a $q=7$ instance with tuple $(5,7,5)$.

Validation packet

• code/certify_underdetermined_obstruction.py and dated JSON: A008.
• code/certify_global_field_bound.py and dated JSON: A007.
• code/certify_cubic_extension_family.py and dated JSON: A006.
• code/certify_quadratic_family.py: A004.
• code/certify_quadratic_field_equations.py: A005.
• papers/P1.3.pdf: 17-page paper with the upper bound and strong no-go.

Exact boundary

P1.3 is resolved as a bound-or-obstruction problem: the unconditional upper bound exists, and the hoped-for universal first-fall-scale strengthening is false. Sharper constants or a classification of square/overdetermined cores $n\ge m>2$ are optional follow-on questions, not missing steps in this resolution.