Approximate roots compile to a nearly linear candidate generator
OpenIntegerRootsFN.Main.approximation_candidate_machineAssume the approximation routine of Proposition 3.4, including its literal finite-machine runtime, rational representation-size bound, root coverage and aggregate logarithmic root-size bound. Assume also Lemma 2.2, which transports each integer root of magnitude at least two to a root of the leading truncation within distance two. Then leading-part extraction followed by rational approximation and the seven integer neighbors of each rounded real part yields a uniform candidate generator on the original dense input.
For every valid degree- polynomial with coefficient-bit parameter , its list contains every integer root, has entries and total evaluation-point size , and its actual running time is
The constants and one finite multitape machine are uniform. The approximation routine is a hypothesis, so the Pan runtime obligation and its source caveat remain unresolved upstream. The conclusion outputs candidates, without claiming that nonroots have already been removed.
Formalization Note. This is the finite-machine refinement of the repository's candidate-generation theorem. Extraction, parsing, rational rounding, bounded-offset addition and word output must all be implemented and charged; a Costed bound alone does not discharge this child.
import Definitions.Def_IntegerRootsFN_Main_CandidatePipeline set_option autoImplicit false
namespace IntegerRootsFN.Main
theorem approximation_candidate_machine
(happrox : ApproximationRoutineContract)
(htruncate : TruncationRootContract) :
CandidateAlgorithm (fun n b => (n : ℝ) * b) := by sorry
end IntegerRootsFN.Main