A Direct Ultrametric Approach to Additive Complexity and the Shub-Smale Tau Conjecture

Details A Direct Ultrametric Approach to Additive Complexity and the Shub-Smale Tau Conjecture A Direct Ultrametric Approach to Additive Complexity and the Shub-Smale Tau Conjecture

2003-04-07

arxiv.org/abs/math/0304100v2

Mathematics

Number Theory

9 pages, no figures. Submitted for publication

Scientific paper

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+s^3(s+1)(7.5)^s s! =O(e^{s\log s}) roots in the 2-adic rational numbers Q_2, 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)^{s^2}). This paper presents another step in the author's program of establishing an algorithmic arithmetic version of fewnomial theory.

Affiliated with

Also associated with

No associations

Rating

A Direct Ultrametric Approach to Additive Complexity and the Shub-Smale Tau Conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Direct Ultrametric Approach to Additive Complexity and the Shub-Smale Tau Conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Direct Ultrametric Approach to Additive Complexity and the Shub-Smale Tau Conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-604427