Uniform finite-machine exact filtering of short candidate lists
OpenIntegerRootsFN.Main.candidate_filtering_machineLet for positive . Assume one uniform candidate-generating finite machine whose output contains every integer root, has entries, and has total evaluation-point size , with actual running time . Assume the exact multipoint-evaluation machine guarantee of Lemma 3.5.
Then there is one uniform finite multitape machine that outputs exactly the distinct integer roots, in signed binary, with actual running time
The machine and all constants precede every varying polynomial and size parameter. The result applies to any candidate-generating method satisfying the same interface and any dominating scale .
Formalization Note. This child is the reusable machine-composition and exact-filtering obligation. It includes preservation of the original polynomial input, formation of the evaluation input word, exact zero tests, duplicate removal and output writing. The repository proves analogous correctness and costs in its Costed model; this statement additionally requires their realization by the mission's literal finite-machine execution semantics.
import Definitions.Def_IntegerRootsFN_Main_CandidatePipeline set_option autoImplicit false
namespace IntegerRootsFN.Main
theorem candidate_filtering_machine
(F : ℕ → ℕ → ℝ)
(hscale : ∀ n b : ℕ, 1 ≤ n → 1 ≤ b → (n : ℝ) * b ≤ F n b)
(heval : MultipointEvaluationContract)
(hgen : CandidateAlgorithm F) :
∃ A : IntMul.MultitapeTM, ∃ C : ℝ, 0 < C ∧ ∃ k l : ℕ,
∀ (n b : ℕ) (f : Polynomial ℤ), Valid f n b →
RootRuns A f n b (softBound C k l n b (F n b)) := by sorry
end IntegerRootsFN.Main