Some irreducible polynomials factor into quadratics modulo every
prime, so recombination has to search the whole support lattice to
learn that no proper subset divides. The Swinnerton-Dyer polynomials
are the standard example: at modular width 16 the walk is
32768 nodes to answer irreducible, and the width doubles with
each new radicand.
For that class the answer is available directly. The quadratic norm
Hex.quadNorm of g at d is the norm of g(X - t)
along ℤ[t]/(t² - d) → ℤ, and Hex.iteratedNorm folds it over a
list of radicands from X - c, producing the product of X - c - ∑ᵢ εᵢ √dᵢ
over all sign patterns. When no nonempty subproduct of the radicands is
a perfect square, that polynomial is the minimal polynomial of
c + ∑ᵢ √dᵢ over a field of degree 2ⁿ, hence irreducible.
Translation and radicands for one iterated quadratic norm.
Constructor
Hex.QuadraticNormCertificate.mk
Fields
translation : ℤ
The translation: the certified polynomial is ∏_ε (X - c - ∑ εᵢ √dᵢ).
radicands : Array ℤ
The radicands, in the order the norms are taken.
Does the certificate prove f irreducible?
A true result asserts both halves: the radicands are independent, and f is,
up to the unit -1, exactly the iterated quadratic norm they describe.
Every F(c; d) is monic and -1 is a unit of ℤ[X], so f and -f are
irreducible together; that sign is the whole normalization the identification
needs. There is no scaling and no content division, since a primitive integer
polynomial with leading coefficient outside {1, -1} is never ± F(c; d).
Both halves of the check are integer arithmetic: no number field is
constructed, the radicands are never factored, and no floating point is
used. Finding the certificate is a separate, untrusted step
(Hex.QuadraticNormCertificate.recover?), because a wrong
proposal is refused by the check.
Does the budget-gated iterated-quadratic-norm certificate prove core
irreducible?
width is the number of modular factors, known once the modular factorization
is in hand. Below Hex.QuadraticNormCertificate.widthFloor the answer is
false with nothing constructed, so a row that recombines cheaply pays nothing
for the attempt. Above it, Hex.QuadraticNormCertificate.recover?
proposes a translation and radicands and
Hex.QuadraticNormCertificate.check decides them; a failure at either
step is an ordinary false carrying no state.
Normalization. Every F(c; d) is monic, so the certificate applies to
core exactly when core has leading coefficient 1 or -1, and the only
normalization is negation: -1 is a unit of ℤ[X], so core and -core are
irreducible together. There is no scaling and no content division, because a
primitive integer polynomial with leading coefficient outside {1, -1} is
never ± F(c; d); Hex.ZPoly.normalizePrimitiveSign, inside the check,
is that negation and nothing else.
The gate is consulted once, where the modular factorization is already in hand and before any Hensel lift. A success answers the whole square-free core as one irreducible factor, reassembled by the same code path as every other singleton proof; a failure falls through to ordinary recombination carrying no state.