Rojas, Maurice

We raise some open questions related to fewnomial theory over and . These problems fall naturally within the general scope of amoeba theory and tropical geometry, but have important connections to complexity theory, including an analogue of the famous problem. We then briefly discuss background and related issues.

Around the 1980's, Askold Khovanski proved his beautiful Theorem on Complex Fewnomials [few]. Roughly speaking, his result gives an explicit upper bound on the number of roots (of a system of polynomial equations) lying in a complex angular sector in . Recently, Rojas proved a -adic analogue [amd]: His theorem on -adic Complex Fewnomials gives an explicit upper bound on the number of roots lying in the poly-disc
,
where are any given constants. The key novelty of both results is that the resulting bounds are completely independent of the degrees of the underyling polynomials: they depend just on (the number of variables) and (the number of exponent vectors in the monomial term expansions of the polynomials).

Two important facts can be observed:

1. For fixed , the upper bound from the -adic Complex Fewnomial Theorem is polynomial in (the number of distinct exponent vectors) for fixed , while the bound from the (ordinary) Complex Fewnomial Theorem is exponential in (even if one fixes the angular sector).
2. The Complex Fewnomial Theorem follows straightforwardly from Khovanski's Real Fewnomial Theorem. On the other hand, the -adic Complex Fewnomial Theorem was proved from scratch and then used to derive a Fewnomial Theorem for .

This inspires two obvious questions. However, to further clarify matters, let us first state the fewnomial theorems over and we've been alluding to.

Fewnomial Theorem Over $R$ (few)   Suppose and that there are exactly distinct exponent vectors in the monomial term expansions of . Then the number of in the positive orthant with of rank and is no more than .

Fewnomial Theorem Over $Q_p$ (amd)   Suppose and that there are exactly distinct exponent vectors in the monomial term expansions of . Then the number of in with and a -dimensional component of the zero set of in is no more than

Question 1: Can one improve the upper bound from Khovanski's Fewnomial Theorem Over to a function polynomial in for fixed ? How about for ?

Question 2: Is there a direct proof of Khovanski's Complex Fewnomial Theorem? In particular, is there a proof which gives significantly better bounds and does not rely on the real fewnomial theorem?

Question 3: Improving on Question 2, is there a unified proof of the fewnomial theorems over both and (or both and )? If so, what other sorts of complete fields can one expect to have fewnomial theorems as above?

Question 4: Specializing Question 3, is there a fewnomial theorem (analogous to those stated above) over the

ground field ?

We discuss the above questions a little more in the next section. However, let us first state one last question.

Definition 1   Suppose a polynomial in one variable is expressed as a sequence of the form , where , , , and for all we have that is a sum, difference, or product of some pair of elements with . Such a computational sequence is called a straight-line program (SLP). We then let denote the smallest possible value of , i.e., the smallest length for such a computation of . Finally, we say that additive complexity (over ) iff there exist constants , and arrays of nonnegative integers and with , where , , and for all . The additive complexity of , , is then the least in such a presentation of as an algebraic expression.

Note in particular that repeated additions or subtractions in different sub-expressions are thus not counted in additive complexity, e.g., . Note on the other hand that is already unbounded for polynomials of the form , which clearly have additive complexity . So can be, and usually is, tremendously smaller than .

Additive Complexity Theorem   [#!add!#, Introduction and Thm. 3] The maximum number of geometrically isolated roots of in is exactly or (according as is or ), no greater than , , or (according as is , , or ), and no greater than for .

Question 5: Is there a family of univariate polynomials with but isolated roots¹in ?

Discussion of Our Open Questions

Questions 1-3 are mainly centered on refining and expanding fewnomial theory. In particular, the connection to amoeba theory can be spelled out as follows: A weak form of the Fewnomial Theorem Over (counting just the number of distinct -adic norms of roots in ) follows quite easily from Kapranov's Non-Archimedean Amoeba Theorem [kapranov,amd]. Moreover, it would appear that if one could sufficiently refine Archimedean amoeba theory [gkz94] then one would perhaps obtain an answer to Question 2. In any event, the existence of two parallel fewnomial theorems over and is just too much of a coincidence for there not to be a more elegant theory incorporating some large class of complete fields simultaneously.

More practically, there is a rather large gap between the precision of fewnomial theory over and fewnomial theory over : the bounds over are far closer to asymptotic optimality than the bounds over . In particular, the optimality of the Fewnomial Theorem Over was open for about 20 years until new signficant sharpenings were found by Li, Rojas, and Wang for a particular family of fewnomial systems [lrw]. For instance, the system of equations

is now known to have no more than topologically isolated roots in the positive quadrant [lrw], whereas Khovanski's Fewnomial Theorem Over implies a much looser upper bound of , and the latter applies to just the non-degenerate roots. Strangely, as of late 2003, no better upper bounds are known, even for the above family of equations.

Remark 1   It is worth noting that fewnomial theory over began with work of Denef and van den Dries related to model theory [vandenef]. Furthermore, the effective estimates we mention here were derived by far simpler techniques.

Regarding Question 4, the author suspects that there should be an analogue of the Fewnomial Theorem Over applying to . Evidence is provided by a result for the special case by Bjorn Poonen [bjorn]. Fewnomial theorems in this setting would appear to have interesting applications in cryptology.

Question 5 is related to complexity theory in the following manner: The Blum-Shub-Smale (BSS) model over can be thought of roughly as a Turing machine augmented with additional registers that perform arithmetic operations on complex numbers at unit cost. (See [bcss] for a much more complete description.) This model of computation possesses a natural analogue of the classical question: the question. This new analogue was introduced with the hope of (a) enabling researchers to enlarge their usual bag of tricks with the arsenals of number theory and analysis and (b) gaining new information on the original question.

Indeed, Steve Smale proved that (see [shub] for the details). Since the latter containment is widely disbelieved, this makes it plausible that . The implications of for classical complexity are still not clear. However, assuming the Boolean parts of and are sufficiently well-behaved, the truth of would yield some evidence that [koiran,dzh]. Better still, Mike Shub and Steve Smale were able to obtain an elegant number-theoretic statement that implies (see [duke] or [#!bcss!#, Thm. 3, Pg. 127]).

The Shub-Smale $$-Conjecture   There is an absolute constant such that for all
, the number of distinct integral roots of is no more than .

It is easily checked that so we at least know that has no more than complex roots. However, little else is known about the relation of to the number of integral roots of : as of late 2003, the -conjecture remains open, even in the special case . The polynomials easily show that the -conjecture fails if we allow .

The Additive Complexity Theorem then represents the first significant improvement over the trivial bound for the number of integral roots of . In particular, a natural attack on the -Conjecture would be to count roots in a field containing , where admits sufficiently good quantitative bounds in terms of . The Additive Complexity Theorem is then the case of this strategy, and Question 5 essentially asks the limits to this approach.

It is worth noting that working over appears to give worse bounds: Dima Yu. Grigoriev [grigo] and Jean-Jacques Risler [risler] (preceded by important seminal work of Allan Borodin and Stephen A. Cook [bocook]) showed that an with could have no more than (or ) real roots [#!risler!#, Pg. 181, Line 6].

Bibliography

[bcss] Blum, Lenore; Cucker, Felipe; Shub, Mike; and Smale, Steve, Complexity and Real Computation, Springer-Verlag, 1998.

[bocook] Borodin, Allan and Cook, Stephen A., ``On the Number of Additions to Compute Specific Polynomials,'' SIAM J. Comput. 5 (1976), no. 1, pp. 146-157.

[vandenef] Denef, Jan and van den Dries, Lou, ``-adic and Real Subanalytic Sets,'' Annals of Mathematics (2) 128 (1988), no. 1, pp. 79-138.

[gkz94] Gel'fand, I. M., Kapranov, M. M., and Zelevinsky, A. V., Discriminants, Resultants and Multidimensional Determinants, Birkhauser, Boston, 1994.

[grigo] Grigor'ev, Dima Yu., ``Lower Bounds in the Algebraic Complexity of Computations,'' The Theory of the Complexity of Computations, I; Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov (LOMI) 118 (1982), pp. 25-82, 214.

[grigokarp] Grigor'ev, Dima Yu. and Karpinski, Marek, ``Computing the Additive Complexity of Algebraic Circuits with Root Extracting,'' SIAM J. Comput., Vol. 27, No. 3, pp. 694-701, June 1998.

[kapranov] Kapranov, Mikhail M., ``Amoebas Over Non-Archimedean Fields,'' manuscript, University of Toronto, 2000.

[few] Khovanski, Askold Georgievich, Fewnomials, AMS Press, Providence, Rhode Island, 1991.

[koblitz] Koblitz, Neal I., -adic Numbers, -adic Analysis, and Zeta-Functions, ed., Graduate Texts in Mathematics, 58, Springer-Verlag, New York-Berlin, 1984.

[koiran] Koiran, Pascal, ``Hilbert's Nullstellensatz is in the Polynomial Hierarchy,'' DIMACS Technical Report 96-27,July 1996. (This preprint considerably improves the published version which appeared Journal of Complexity 12 (1996), no. 4, pp. 273-286.)

[lrw] Li, Tien-Yien; Rojas, J. Maurice; and Wang, Xiaoshen, ``Counting Real Connected Components of Trinomial Curves Intersections and m-nomial Hypersurfaces,'' Discrete and Computational Geometry, to appear.

[bjorn] Poonen, Bjorn, ``Zeros of Sparse Polynomials Over Local Fields of Characteristic ,'' Math. Res. Lett. 5 (1998), pp. 273-279.

[risler] Risler, Jean-Jacques, ``Additive Complexity and Zeros of Real Polynomials,'' SIAM J. Comput. 14 (1985), no. 1, pp. 178-183.

[add] Rojas, J. Maurice, ``Additive Complexity and the Roots of Polynomials Over Number Fields and -adic Fields,'' Proceedings of the 5 Annual Algorithmic Number Theory Symposium (ANTS V), Lecture Notes in Computer Science #2369, pp. 506-515, Springer-Verlag (2002).

[amd] , ``Arithmetic Multivariate Descartes' Rule,'' American Journal of Mathematics, to appear.

[dzh] , ``Dedekind Zeta Functions and the Complexity of Hilbert's Nullstellensatz,'' Math ArXiV preprint math.NT/0301111, submitted for publication.

[shub] Shub, Mike, ``Some Remarks on Bézout's Theorem and Complexity Theory,'' From Topology to Computation: Proceedings of the Smalefest (Berkeley, 1990), pp. 443-455, Springer-Verlag, 1993.

[duke] Shub, Mike and Smale, Steve, ``On the Intractibility of Hilbert's Nullstellensatz and an Algebraic Version of `NP not equal to P?','' Duke Math J., Vol. 81 (1995), pp. 47-54.

Back to the main index for Amoebas and tropical geometry.