2003/04/07 by J. Maurice Rojas, Rojas, J. Maurice
Computer Science · Mathematics · #Algebraic Geometry and Number Theory #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation #Topological and Geometric Data Analysis #cs.CC #math.NT
paper · pdf · doi:10.48550/arxiv.math/0304100
9 pages, no figures. Submitted for publication
openalex publication_date 2003/04/07 · arxiv created 2003/04/09 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Shub-Smale Tau Conjecture is a hypothesis relating the number of integral roots of a polynomial f in one variable and the Straight-Line Program (SLP) complexity of f. A consequence of the truth of this conjecture is that, for the Blum-Shub-Smale model over the complex numbers, P differs from NP. We prove two weak versions of the Tau Conjecture and in so doing show that the Tau Conjecture follows from an even more plausible hypothesis. Our results follow from a new p-adic analogue of earlier work relating real algebraic geometry to additive complexity. For instance, we can show that a nonzero univariate polynomial of additive complexity s can have no more than 15+s3(s+1)(7.5)s s! =O(eslog s) roots in the 2-adic rational numbers Q2, thus dramatically improving an earlier result of the author. This immediately implies the same bound on the number of ordinary rational roots, whereas the best previous upper bound via earlier techniques from real algebraic geometry was a quantity in Omega((22.6)s2). This paper presents another step in the author's program of establishing an algorithmic arithmetic version of fewnomial theory.