Lemma 2.2 — truncation retains nearby roots
ProvedIntegerRootsFN.Main.lemma_2_2bit-complexityinteger-polynomialsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1root-finding
Let be integers and have exact degree , nonzero leading coefficient and . Put and . If , every integer root of with satisfies
The truncation is constructed from the coefficients, not provided as an unrelated polynomial. The restriction on leaves to be handled separately.
Differences from the source:
- encoding: positive integer parameters and a truncated integer polynomial viewed over C → positive natural parameters and canonical complexification of the coefficient-defined truncation; reason: these denote the same parameters, coefficients and roots without any machine input or output assertion
Preamble
import Mathlib import Definitions.Def_IntegerRootsFN_Main_PolynomialData set_option autoImplicit false
Formal statement
namespace IntegerRootsFN.Main
theorem lemma_2_2 (n b : ℕ) (f : Polynomial ℤ) (hf : Valid f n b)
(hd : min n b < n) (r : ℤ) (hr : f.IsRoot r) (hrlarge : 2 ≤ |r|) :
∃ α : ℂ, (complexify (truncate f n b)).IsRoot α ∧ ‖(r : ℂ) - α‖ < 2 := by sorry
end IntegerRootsFN.Main
Source
Yansong Feng, Itamar Nir, STOC 2027 submission #1353 (October 2026), p. 5, Lemma 2.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.