Staged fixed-denominator jet arithmetic and integer Cramer recovery #
In the subexponential common-zero counting algorithm of
OpenAI, The Exponential Time Hypothesis is False (§5.4 and Appendix B.2–B.3,
printed pp. 48–50), intermediate polynomials in the Taylor variable z and the shared truncation
marker V lie in the truncated bivariate algebra ℚ[V] / (V ^ ℓ)[z] / (z ^ J). Rather than
performing rational arithmetic with growing denominators across exponentially many summands, the
algorithm clears denominators in three fixed stages (Δ = d_den ^ k, Γ = Δ ^ (2 * ℓ - 1), and
Ω = Γ ^ m_test), storing (J × ℓ) integer numerator tables and recovering the integer evaluations
H_s(0) at T = 0 by exact integer division of Hermite Cramer determinants.
Main definitions #
Cslib.JetTable:(J × ℓ)truncated bivariate jet tablesFin J → Fin ℓ → R, equipped withzero,const,one,add,neg,sub,smul,conv,vPow, aCommRinginstance, and ring homomorphismsconstRingHom,mapRingHom,castRingHom,ofBivarPoly,ofPolyZ,transpose, andofPolyVPolyZ.Cslib.JetTable.l1Norm: integerℓ₁coefficient norm∑ j, ∑ u, (A j u).natAbs.Cslib.JetTable.clearedMonomialJet,Cslib.JetTable.clearedMonomialSumJet,Cslib.JetTable.clearedUnivariateJet,Cslib.JetTable.parityFactorJet,Cslib.JetTable.clearedParityFactorJet,Cslib.JetTable.signedPrefixJet: staged fixed-denominator numerator constructions for Stages 1–3.Cslib.hermiteCramerNumerator: integer Cramer determinantN_Hreplacing theX ^ 0column ofPolynomial.hermiteMatrixwith anΩ-scaled integer Taylor jet.
Main results #
Cslib.JetTable.l1Norm_add_le,Cslib.JetTable.l1Norm_smul,Cslib.JetTable.l1Norm_conv_le: triangle inequality, scalar homogeneity, and submultiplicativity under 2D truncated convolution.Cslib.JetTable.cast_clearedMonomialSumJet,Cslib.JetTable.l1Norm_clearedMonomialSumJet_le: Stage-1 denominator clearing byΔ = d_den ^ kandM₀ * B₀ ^ knorm bound.Cslib.JetTable.cast_clearedUnivariateJet,Cslib.JetTable.l1Norm_clearedUnivariateJet_le: univariate homogeneous clearing byΔ ^ DandC_amp * B_max ^ Dnorm bound.Cslib.JetTable.cast_clearedParityFactorJet,Cslib.JetTable.l1Norm_clearedParityFactorJet_le,Cslib.JetTable.l1Norm_clearedParityFactorJet_le_B1: Stage-2 denominator clearing byΓ = Δ ^ (2 * ℓ - 1)andB₁ = ℓ * E_ℓ * (B + Δ.natAbs + 2) ^ (2 * ℓ - 1)norm bound.Cslib.JetTable.cast_groupProd_cleared,Cslib.JetTable.l1Norm_groupProd_cleared_le,Cslib.JetTable.cast_signedPrefixJet,Cslib.JetTable.l1Norm_signedPrefixJet_le,Cslib.JetTable.l1Norm_clearedSliceSum_le: Stage-3Ω = Γ ^ m_testclearing and prefix/slice accumulator norm boundM_star * 2 ^ n * B₁ ^ m_test.Cslib.hermiteCramerNumerator_eq_mul,Cslib.mul_det_hermiteMatrix_dvd_hermiteCramerNumerator,Cslib.hermiteCramerNumerator_ediv_eq,Cslib.hermiteCramerNumerator_emod_two_pow_eq,Cslib.sum_hermiteCramerNumerator_emod_two_pow_eq: exact integer Cramer factorization, divisibility, Euclidean quotientN_H / (Ω * D_H) = H_zero(eq. B.1), and residue recovery modulo2 ^ ℓ.
References #
- OpenAI, The Exponential Time Hypothesis is False, §5.4 and Appendix B.2–B.3
1. Truncated bivariate jet tables for R[V] / (V ^ ℓ)[z] / (z ^ J) #
A (J × ℓ) table of coefficients in R, representing a truncated bivariate polynomial in
R[V] / (V ^ ℓ)[z] / (z ^ J) via (j, u) ↦ [z ^ j V ^ u].
Instances For
Private index reindexing helpers #
Quotient extraction homomorphism R[V][z] →+* JetTable J ℓ R sending a bivariate polynomial
p : Polynomial (Polynomial R) to its low-degree coefficient table
(j, u) ↦ (p.coeff j).coeff u.
Instances For
Embed a univariate z-polynomial p : R[X] into JetTable J ℓ R along V ^ 0.
Instances For
Quotient extraction homomorphism R[z][V] →+* JetTable J ℓ R sending a bivariate polynomial
Q : Polynomial (Polynomial R) (outer variable V, inner variable z) to its (J × ℓ)
coefficient table (j, u) ↦ (Q.coeff u).coeff j, obtained by composing ofBivarPoly ℓ J with
transpose.
Instances For
Embedding a z-polynomial p : Polynomial R into R[z][V] via Polynomial.C and extracting
its (J × ℓ) table via ofPolyVPolyZ J ℓ agrees with ofPolyZ J ℓ p.
Extracting Polynomial.C (Polynomial.C c) via ofPolyVPolyZ J ℓ yields const c.
Extracting Polynomial.X ^ s : Polynomial (Polynomial R) via ofPolyVPolyZ J ℓ yields
vPow s.
3. Staged fixed-denominator clearing and prefix norm bounds (Appendix B.2) #
Stage-1 integer numerator for a single monomial M of degree #M ≤ k, cleared by
Δ = d_den ^ k via padding d_den ^ (k - #M) ([OpenAI2026ETH, Appendix B.2, p. 48]).
Instances For
Stage-1 integer numerator for a sum of listed monomials of degree at most k, cleared by
Δ = d_den ^ k ([OpenAI2026ETH, Appendix B.2, p. 48]).
Instances For
Stage-1 denominator clearing (Appendix B.2, p. 48). If d_den • θ_rat v is represented by
θ_int v, then Δ = d_den ^ k clears any sum of monomials of degree at most k.
Stage-1 ℓ₁-norm bound (Appendix B.2, p. 48). When d_den.natAbs ≤ B₀ and every input jet
θ_int v has ℓ₁-norm at most B₀, a sum of at most M₀ monomials of degree at most k cleared
by Δ = d_den ^ k has ℓ₁-norm at most M₀ * B₀ ^ k.
Univariate homogeneous denominator clearing. If Δ • L_rat = castRingHom K A_int, then
Δ ^ D clears ∑ u ∈ range (D + 1), a u • L_rat ^ u.
Univariate homogeneous ℓ₁-norm bound. If ‖A_int‖₁ ≤ B_max, Δ.natAbs ≤ B_max, and
∑ u ∈ range (D + 1), |a u| ≤ C_amp, then
‖clearedUnivariateJet Δ D a A_int‖₁ ≤ C_amp * B_max ^ D.
The substituted shared-V parity factor
B_i(z, V) = ∑ s < ℓ, (a_s + b_s L) (L (L - 1)) ^ s V ^ s modulo (z ^ J, V ^ ℓ)
([OpenAI2026ETH, §5.3 eq. (5.4) and Appendix B.2, p. 48]).
Instances For
Stage-2 integer numerator Γ • B_i(z, V) for Γ = Δ ^ (2 * ℓ - 1) and A_int = Δ • L,
obtained by clearing e_s(L) with Δ, L (L - 1) with Δ ^ 2, and padding term s by
Δ ^ (2 * (ℓ - 1 - s)) ([OpenAI2026ETH, Appendix B.2, pp. 48–49]).
Instances For
Stage-2 denominator clearing (Appendix B.2, pp. 48–49). If
Δ • L_rat = castRingHom K A_int, then Γ = Δ ^ (2 * ℓ - 1) clears parityFactorJet L_rat a b.
Stage-2 ℓ₁-norm bound (Appendix B.2, p. 49). If ‖A_int‖₁ ≤ B and every linear remainder
e_s(Y) = a_s + b_s Y satisfies |a_s| + |b_s| ≤ E_ℓ, then
‖clearedParityFactorJet Δ A_int a b‖₁ ≤ ℓ * E_ℓ * (B + Δ.natAbs) ^ (2 * ℓ - 1).
Specialization of l1Norm_clearedParityFactorJet_le to the manuscript's explicit parameter
B₁ = ℓ * E_ℓ * (B + Δ.natAbs + 2) ^ (2 * ℓ - 1) ([OpenAI2026ETH, Appendix B.2, p. 49]).
Product of m Γ-cleared factors. Multiplying m rational factor tables cleared by Γ
gives an integer table clearing the product by Γ ^ m.
Group-product denominator clearing (Appendix B.2, p. 49). If group g's sum S_rat g is
cleared by Γ ^ (m_group g) and ∑ g, m_group g = m_test, then Ω = Γ ^ m_test clears the full
product ∏ g, S_rat g.
Group-product ℓ₁-norm bound (Appendix B.2, p. 49). If each group sum S_int g satisfies
‖S_int g‖₁ ≤ 2 ^ (s_group g) * B₁ ^ (m_group g) with ∑ g, s_group g ≤ n and
∑ g, m_group g = m_test, then ‖∏ g, S_int g‖₁ ≤ 2 ^ n * B₁ ^ m_test.
Prefix accumulator denominator clearing (Appendix B.2, p. 49). At every step t, Ω clears
the intermediate accumulator signedPrefixJet.
Intermediate prefix accumulator ℓ₁-norm bound (Appendix B.2, p. 49). If every signed
contribution (ε, Π_int) has |ε| ≤ 1 and ‖Π_int‖₁ ≤ 2 ^ n * B₁ ^ m_test, then at every step
t with min t updates_int.length ≤ M_star, the integer accumulator Ω • T_t satisfies
‖Ω • T_t‖₁ ≤ M_star * 2 ^ n * B₁ ^ m_test.
Finset slice-sum ℓ₁-norm bound (Appendix B.2, p. 49). Summing m_test-factor products
with signs |ε u| ≤ 1 across an index set slices of cardinality #slices ≤ M_star * 2 ^ n,
where each factor has ℓ₁-norm at most B₁, yields an integer (J × ℓ) table of ℓ₁-norm at
most M_star * 2 ^ n * B₁ ^ m_test.
4. Exact integer Cramer divisibility and modulo-2 ^ ℓ recovery (Appendix B.3) #
The integer Cramer numerator N_H = det V_{(0)} ([OpenAI2026ETH, Appendix B.3, eq. (B.1),
p. 50]), obtained by replacing column (0, 0) (corresponding to X ^ 0) of the integer confluent
Vandermonde matrix Polynomial.hermiteMatrix nodes J with the Ω-scaled integer Taylor jet
J_int.
Instances For
Integer Cramer factorization (Appendix B.3, p. 50). If H : ℚ[X] has degree less than
Q * J, integer value H.eval 0 = (H_zero : ℚ) at 0, and Ω-scaled integer Taylor jet J_int
at nodes, then N_H = Ω * D_H * H_zero in ℤ.
At distinct integer nodes and nonzero denominator Ω ≠ 0, the integer Cramer denominator
Ω * det (hermiteMatrix nodes J) is nonzero ([OpenAI2026ETH, Appendix B.3, p. 50]).
Exact integer Cramer divisibility (Appendix B.3, p. 50). Under the hypotheses of
hermiteCramerNumerator_eq_mul, Ω * D_H divides N_H over ℤ.
Exact integer Cramer recovery (Appendix B.3, eq. (B.1), p. 50). At distinct integer nodes
with Ω ≠ 0, exact Euclidean integer division N_H / (Ω * D_H) recovers the integer H_zero.
Modulo-2 ^ ℓ recovery from integer-scaled jets. If H_zero ≡ Z [ZMOD 2 ^ ℓ] with
0 ≤ Z < 2 ^ ℓ, then (N_H / (Ω * D_H)) % 2 ^ ℓ = Z.
Summed ℓ-coordinate recovery modulo 2 ^ ℓ (Appendix B.3, p. 50). Given (J × ℓ)
integer jet tables T_int i at distinct integer nodes nodes i representing Ω-scaled Taylor jets
of coordinate polynomials H s (s < ℓ) whose values at 0 are integers H_zero s, if
∑ s, H_zero s ≡ Z [ZMOD 2 ^ ℓ] with 0 ≤ Z < 2 ^ ℓ, then the least nonnegative residue modulo
2 ^ ℓ of the summed Cramer quotients equals Z.