The bottom of the Shub-Smale tau conjecture: an exact census of integer roots for constant-free straight-line programs of length at most seven

Abstract

For a univariate integer polynomial f, let tau(f) be the minimum number of +,-,x gates needed to compute f from x and the constants -1,0,1, and let z(f) be its number of distinct integer roots. The Shub-Smale tau conjecture (Smale's fourth problem) asserts z(f) ≤ (1+tau(f))^k for a universal k; it implies P != NP over the complex numbers in the Blum-Shub-Smale model and VP0 != VNP0, and it is open even for k = 1. This preprint reports the first exact census of the conjecture's growth function at the bottom of its ladder: writing z_max(tau) for the maximum of z(f) over nonzero f with tau(f) ≤ tau, we establish by exhaustive, exactly verified computation that z_max(1..7) = 1, 2, 3, 3, 4, 5, 5. In particular the minimum cost of 4 distinct integer roots is 5 gates, of 5 roots is 6 gates, and of 6 roots is EXACTLY 8 gates (new in v0.02: the window was closed by a case-split scan of the 25,844,905-state depth-6 frontier, with explicit verified 8-gate witnesses such as q(q-2)(q-6), q = x^2-x, via chained subtraction sharing); the growth function has plateaus at tau = 4 and tau = 7, and z_max(8) >= 6. The censuses are decision-complete: depth 6 required the exact construction of all 25,844,905 reachable computation states, and depth 7 a complete scan of 2,013,706 new polynomials, via a last-gate lemma that decides one depth beyond any exhausted frontier without storing the next frontier. The enumerator is anchored on Markstrom's published exhaustive census of integer targets (fourteen of fourteen anchor values reproduced exactly) and cross-checked against an independent computer-algebra root counter on 284 polynomials. Two elementary stall theorems explain the record mechanisms: towers built by iterating any fixed monic map of degree at least 2 have depth-independent integer root counts (for x^2-2, the iterates keep exactly 2 integer roots against 2^k real roots), and across the quadratic family x^2-c with c ≤ 200 the maximum tower yield is 5, attained only at c = 2, with a second yield series at c = m^2+m+1 produced by genuine integer 2-cycles and closed by the classical bound on integer polynomial cycle lengths. All computations are exact integer arithmetic, reproducible from committed code with hypotheses declared before each run; three of the author's pre-registered predictions were refuted by the machine and are reported as such. This is an experimental-mathematics record in the tradition of Markstrom's census: it decides nothing about the conjecture asymptotically, and says so. Code and machine records: https://github.com/fsantibanezleal/CAOS_RESEARCH (problems/computation-complexity/tau-conjecture).