On the Number of Integer Zeros of Straight-Line Polynomials and Smale's 4th Problem

Abstract

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 &implies; P&complex; ≠ NP&complex; 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&complex; ≠ NP&complex; in the BSS model over &complex;. 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.Keywords: Smale's 4th Problem, Integer Zeros, Straight-Line Program, Arithmetic Circuits, Descartes' Rule of Signs, Shub-Smale Tau-Conjecture, Koiran's Tau-Conjecture, BSS Model, Valiant's Conjecture, VP vs VNP, Formal Verification, Lean 4, Mathlib.