The Bottom of the Shub–Smale Tau Conjecture: an Exact Census of Integer Roots for Constant-Free Straight-Line Programs of Length at Most Eight

For a univariate integer polynomial f, let τ(f) be the minimum number of +, -, × 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 + τ(f))^κ for a universal κ; it implies P ≠ NP over the complex numbers in the Blum–Shub–Smale model and VP0 ≠ VNP0, and it is open even for κ = 1. We report the first exact census of the conjecture's growth function at the bottom of its ladder: writing z_max(τ) for the maximum of z(f) over all nonzero f with τ(f) ≤ τ, we prove by exhaustive, exactly verified computation that z_max(1), ..., z_max(8) = 1, 2, 3, 3, 4, 5, 5, 6. 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, by an explicit verified witness: q(q-2)(q-6) for q = x^2 - x, computable in 8 gates by chained subtraction sharing; the growth function has plateaus at τ = 4 and τ = 7, so an extra gate does not always buy an extra root, and z_max(8) = 6 exactly: no 8-gate program of any shape has 7 distinct integer roots, so the seven-root threshold lies in {9, 10}. At the ninth gate, no program whose final gate is a multiplication reaches 7 roots, and no program whose final gate is an addition or a subtraction reaches 7 roots inside the window [-32, 32]; a nine-gate seven-rooter would need a root outside that window and a trailing coefficient of absolute value at least 396. The censuses are decision-complete: depth 6 required the exact construction of all 25,844,905 reachable computation states; depth 7 a complete scan of 2,013,706 new polynomials, using a last-gate lemma that decides one depth beyond any exhausted frontier without storing the next frontier; and depth 8 the first complete construction of the depth-7 frontier itself: 1,048,460,912 states, built out-of-core by hash-partitioned external deduplication and scanned exhaustively (about 2 × 10^11 last-gate applications) by a validated multiprocess engine. The enumerator is anchored on Markström's published exhaustive census of integer targets (all fourteen anchor values reproduced exactly) and cross-checked against an independent computer-algebra root counter on 284 polynomials. The six-root threshold is decided by a case split: the last gate of an 8-gate 6-rooter must involve the seventh value, and if it is a multiplication its root count is a union of two known root sets, so that case reduces to a co-occurrence query over the depth-6 frontier; the scan found 408 witnesses. We further prove two elementary stall theorems explaining the observed record mechanisms: for any monic h in Z[x] of degree at least 2, towers built by iterating h alone have depth-independent integer root counts (for h = x^2 - 2, the iterates h^k(x) - x keep exactly 2 integer roots against 2^k real roots), and across the quadratic family h_c = x^2 - c with c ≤ 200 the maximum tower yield is 5, attained only at c = 2; a second yield series at c = m^2 + m + 1, produced by genuine integer 2-cycles, is identified and closed by the classical fact that integer polynomial cycles have length at most 2. All computations are exact integer arithmetic, reproducible from the released code. We also report the exact ladders of the digit-restricted census (the form of the conjecture Rojas proved sufficient): the maximum number of odd roots grows as 1, 2, 2, 2, 2, 3, 4 through τ = 7, with its own extremal family (x^2 - 1)(x^2 - 9), distinct from the unrestricted records. Finally we place the census against its two neighbouring worlds, measured on the same enumerated programs. Over F_p the analogous maximum is exactly 2^(τ-1) for every τ (proved here; the extremal program is k squarings and one subtraction, and the Fermat primes that the small cases suggest are not required, only a prime p ≡ 1 mod 2^k). Over R it is 1, 2, 3, 4, 6, 8 through τ = 6, exhaustively, by exact Sturm counting with no floating point; its τ = 4 and τ = 6 records are linked by a step from g to g(g - x^2) that costs two gates and doubles the real root count, beating a Chebyshev tower's three gates per doubling, and that step itself stalls after three iterations. The three ladders agree at τ ≤ 2 and separate at τ = 3 and τ = 4 respectively; over F_p the degree ceiling 2^(τ-1) is saturated at every τ, over R it is not, and over Z the census stays linear. A five-gate program with six distinct real roots and only two integer ones exhibits the difference concretely. The work is experimental mathematics in the tradition of Markström's census; it decides nothing about the conjecture asymptotically. Source code, data and computational records: https://github.com/fsantibanezleal/CAOS_RESEARCH (problems/computation-complexity/tau-conjecture).