Answers are grounded in this paper and cite their sources.
Mathematical analysis uncovers bounds on polynomial integer zeros from arithmetic circuits, highlighting structural connections between algebraic complexity classes and formal Lean 4 verification.
This preprint provides an exhaustive 10-page mathematical monograph on Smale's 4th Problem (Steve Smale, 2000), dedicated to the number of integer and real zeros of polynomials computed by short straight-line programs (arithmetic circuits). Smale's 4th problem asks whether the number of integer zeros Z(f) of a univariate polynomial f ∈ ℤ[x] computed by an arithmetic circuit of length k using basic ring operations {+, −, ×} can be bounded by a polynomial kc in the circuit length, despite the degree growing up to 2k: Z(f) ≤ (τ(f) + 1)c P ≠ NP This treatise presents a comprehensive survey of Descartes' rule of signs, Khovanskii's fewnomial theory, H. W. Lenstra's rational root bounds for sparse polynomials, the Shub-Smale τ-conjecture (1995), and Pascal Koiran's real τ-conjecture (2011) bridging arithmetic circuit roots to Valiant's landmark algebraic separation VP ≠ VNP. Key Mathematical Results & Contributions Formal Straight-Line Architecture: Axiomatic DAG framework bounding the arithmetic complexity τ(f) and distinguishing degree explosion from zero locus complexity. Descartes' Rule of Signs & Rolle Induction: Complete, non-elliptical proof showing that the number of positive real roots is bounded by the number of sign variations v(f), extending to Lenstra's O(t2 log t) bound on t-sparse polynomials. The Shub-Smale τ-Conjecture (1995): Structural analysis of integer factorizations and root counting, establishing that polynomial bounds on integer zeros imply P ≠ NP in the BSS model over . Koiran's Bridge to VP vs VNP (2011): Complete reduction proving that bounding real roots of sums of products of sparse polynomials unconditionally implies VP ≠ VNP (the algebraic analogue of P vs NP). 100% Machine-Checked Verification in Lean 4: Monomial root uniqueness, linear polynomial root uniqueness, power-of-two degree bounds, and real power injectivity are machine-certified with 0 axioms, 0 linter warnings, and 0 sorry placeholders via the Lean 4 interactive theorem prover and Mathlib. Repository and Verification Artifacts The companion machine-checked code and formal verification artifacts are publicly hosted on GitHub:https://github.com/flouzzy/smale-problemsInteractive Portal: https://maths-proofs.edounze.com/#smale-04-integer-roots Primary MSC (2020): 68Q17, 12D10, 11C08, 68V20, 14Q05, 03D15, 68Q15.
No takes yet. Share an insight, caveat, or question.
Charles EDOU NZE (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: