key: cord-0584623-rst8ko20
authors: Rojas, J. Maurice
title: Counting Real Roots in Polynomial-Time for Systems Supported on Circuits
date: 2020-12-09
journal: nan
DOI: nan
sha: 5f8e8096c8d82e1daa7e4461616af4dfa974642b
doc_id: 584623
cord_uid: rst8ko20

Suppose $A={a_1,ldots,a_{n+2}}subsetmathbb{Z}^n$ has cardinality $n+2$, with all the coordinates of the $a_j$ having absolute value at most $d$, and the $a_j$ do not all lie in the same affine hyperplane. Suppose $F=(f_1,ldots,f_n)$ is an $ntimes n$ polynomial system with generic integer coefficients at most $H$ in absolute value, and $A$ the union of the sets of exponent vectors of the $f_i$. We give the first algorithm that, for any fixed $n$, counts exactly the number of real roots of $F$ in in time polynomial in $log(dH)$.

Solving sparse polynomial systems remains a challenging problem, even 40 years after the dawn of fewnomial theory [Kho80, Kho91] . More recently, connections have emerged between fewnomial theory over finite fields, cryptography, and number theory [CFKLLS00, BBK09, CGRW17] ; and sparse polynomial systems over the real numbers are important in applications including computational biology and biochemistry [BDG19, DMST19, DGRM20, BDG20a] , and circuit complexity [KPT15b] . However, efficiently counting the number of real roots, or even just finding a reasonably tight upper bound on the number of real roots, remains an open problem. Here, we focus on the problem of exactly counting real roots, and roots in any given orthant. In what follows, all O-constants are absolute and effective, time will refer to the number of (deterministic) bit operations in the classical Turing model of computation, and we will use #S for the cardinality of a set S.

Suppose A = {a 1 , . . . , a t } ⊂ Z n has cardinality t, with all coordinates of the a j having absolute value at most d. Writing x a j := x a 1,j 1 · · · x a n,j n and f (x) = t j=1 c j x a j ∈ Z x ±1 1 , . . . , x ±1 n , we define the support of f to be Supp(f ) := {a j | c j = 0}. We then call a system of the form F := (f 1 , . . . , f n ) ∈ Z x ±1 1 , . . . , x ±1 n n , with f i (x) := t j=1 c i,j x a j for all i and # n i=1 Supp(f i ) = t, a t-nomial n × n system (over Z) supported on A. We denote the positive orthant by R n + and call a root of F in R n + a positive root. We also let R * := R \ {0}. If the a j do not all lie in the same affine hyperplane then we clearly have t ≥ n + 1. It is natural to assume that the exponent vectors are non-coplanar in this sense, and we will do so, for otherwise one could use a monomial change of variables to reduce F to a system in fewer variables: See Remark 2.6 from Section 2 below. Our main theorem gives a dramatic speedup for counting the exact number of real roots of F in the special case t ≤ n + 2. is checkable in time O n 3.373 log 2 (ndH) : See Lemma 2.16 and Corollary 2.19 of Section 2.3. In particular, the fraction of coefficient matrices failing to satisfy this genericity condition is no greater than 2n 2 2H+1 . The genericity condition for counting affine roots is more technical but still holds practically often: probability 1 − ε when H has Ω(n log(d) − log ε) bits (see Section 5.1). Root counting without genericity assumptions is rather non-trivial: Deciding infinitude for the number of real (or positive) roots in time polynomial in (n log(dH)) n , when t = n + 2 and f 2 = · · · = f n , is already an open question [BRS09, Bih11] . Furthermore, for any fixed ε > 0, deciding whether F = (f 1 , . . . , f 1 ) has any real (or positive) roots is NP-hard already for t = n + n ε [BRS09] .

Remark 1.2. We count roots without multiplicity. In particular, degenerate 1 isolated roots are not a problem, and are counted correctly by our algorithms. ⋄ Other than an algorithm for the very special case (n, t) = (1, 3) from [BRS09] , the best previous complexity bound for t = n + 2 appears to have been n (1+n/2) 2 d O(n 2 ) (log H) O(n 2 ) , as a consequence of more general algorithms (see, e.g., [BPR06a, BPR06b] ), based on older computational algebra techniques (see, e.g., [CG84, BKR86, Can88, Ren92] ). (One can also derive a (d log H) O(n) bound via [PRS93] if one assumes the complex zero set is finite.) There have also been important recent advances from the point of view of numerical conditioning (e.g., [CKMW08, CKS18] ), even enabling practical computation of homology of real projective sets, but work in this direction has not yet focussed on speed-ups like Theorem 1.1. With few exceptions, earlier work on solving polynomial systems over the real numbers focused on coarser complexity bounds that ignored the finer monomial term structure. Then Algorithm 4.3 from Section 4 (simulated in a few lines of Maple code 2 ) tells us in under a second that F has exactly 2, 6, 6, 2, 2, or 0 positive roots, respectively when c is 1 20731 , 1 20730 , 1 14392 , 1 14391 , 1 13059 , or 1 13058 . (All roots in (R * ) 5 of these F happen to lie in R 5 + .) We will return to this family in Section 2.3, and see another example there as well. It is interesting to observe that Maple's Solve command (which employs Gröbner bases) gives no useful information about any of these systems, even after 3 hours. 2 Bertini (a state of the art homotopy solver, version 1.4 [BHSW13] ), on each of the preceding systems, immediately returns a message stating "ERROR: The system is numerically zero 0! Please input a nondegenerate system. Bertini will now exit due to this error." This is partially because each of our F has 3 over 245 million roots in (C * ) 5 , and older polynomial system solving techniques have complexity super-linear, or worse, in the number of complex roots. ⋄ Remark 1.4. The main intent of Theorem 1.1 is to set the stage (building on the framework of [PPR19, EPR19, EPR20]) for more practical improvements in real-solving, such as complexity sub-exponential in n in the average-case/smoothed analysis setting for sparse systems. In particular, just as binomial systems are a building block for polyhedral homotopy algorithms for arbitrary n × n systems [HS95, Ver10, LL11] , (n + 2)-nomial n × n systems are a building block behind recent optimization techniques such as SONC/SAGE-optimization (see, e.g., [PRT09, CS16, DKdW18] ). So while tackling the remaining exceptional cases (involving infinitely many real roots in (R * ) n ) is important, such cases are provably rare when the coefficients are random. ⋄ There has been growing interest in generalizing Descartes' Rule of Signs (see, e.g., [SL54, Gra99] ) from univariate polynomials to n × n polynomial systems. This began with Khovanski's seminal Theorem on Real Fewnomials [Kho91] which, in our notation, asserted an upper bound of 2 ( t 2 ) (n + 1) t for the number of non-degenerate positive roots of any tnomial n × n system. It was then shown in [LRW03] that Khovanski's bounds could be greatly improved for various structured systems, e.g., the correct tight upper bound on the number of isolated 4 positive roots for 2 × 2 systems of trinomials is 5 -far less than the best previous bound of 248832. Sharper upper bounds for new families of systems, including a tight upper bound of n + 1 (resp. (n + 1)2 n ) roots in R n + (resp. (R * ) n ) for the case t = n + 2, were then derived in [BBS06] . Explicit families of systems attaining these bounds for each n were then given in [PR13] (see also [Bih11] ). Khovanski's general upper bound was vastly improved to e 2 + 3 4 2 ( t−n−1 2 ) n t−n−1 positive roots in [BS07] , and a remarkable bound for curve intersections was derived later in [KPT15a] . More recently, a beautiful and considerably sharper average-case upper bound of 1 2 n−1 · t! n!(t − n)! for the number of positive roots was proved in [BET19] , using independent real Gaussians for the coefficients. It should also be noted that counting roots on coordinate subspaces quickly abuts #P-hardness, already for n × n binomial systems: See [CD07, Mon20] and Remark 2.9 in Section 2.2 below. So it wasn't just the convenience of torus actions that made earlier work on fewnomials focus on (R * ) n instead of R n .

However, fewnomial bounds so far have not made significant use of the signs of the coefficients (much less their values) and such refined bounds remain elusive: See, e.g., [BHNS16, Thm. 2 .1] and [BD17, BDG20b, BDF20] . The latter works, particularly [BDF20] , culminated in a refined characterization of the maximal number of positive roots -incorporating the signs of n × n sub-determinants of the coefficient matrix [c i,j ] and the matroidal structure of A -in the case t = n+ 2. Nevertheless, no algorithm for exactly counting the real or positive roots, faster than combining more general results on rational univariate reduction (see, e.g., [Kro95, Roj99, Rou99] ) with the computation of real dimension (see, e.g., [BPR06a] ) or real root isolation (see, e.g., [Sag11] ), appears to have been known before Theorem 1.1 above.

Exactly counting the real or positive roots of F , and even formulating a reasonable generalization of Descartes' Rule, appears to be much harder for t ≥ n + 3. This is why there is so much attention on the case t = n + 2 to develop further intuition. An even harder open question is the complexity of actually approximating the real roots of such F and we hope to address this in future work.

Our main tools are reduction to a canonical form (a special case of Gale Dual Form from [BS07] ) and a careful application of diophantine approximation to the critical values of this reduction. In particular, the locus of F with degenerate roots forms a discriminant variety which partitions the coefficient space into connected open regions we call chambers (see, e.g., [GKZ94, Ch. 11] ). Classical topological results, such as Hardt's Triviality Theorem [Har80] , tell us that counting the real roots of F is tantamount to identifying the chamber in which F lies. Such a calculation is challenging, since the theory of A-discriminants [GKZ94] does not directly provide a tractable description of our chambers. However, a combination of Rolle's Theorem with Gale Dual Form allows one to replace chamber identification by the determination of signs of the critical values and poles of a single univariate rational function.

A new obstacle is that the usual univariate root-finding algorithms, combined with classical height bounds on polynomial roots, do not yield a useful complexity bound. Indeed, the degree of the resulting univariate reduction can be so high that a naive use of real root isolation would lead to complexity super-linear in n n/2 d n . So we leverage the special structure of the derivative of our univariate reduction to apply a powerful theorem from diophantine approximation: A refinement of an estimate of Baker and Wustholtz on linear forms in logarithms of algebraic numbers (see [Bak77, BW93, Mat00, BMS06] or Section 2 below).

Remark 1.5. A by-product of our framework is that sufficiently sharp lower bounds for linear forms in logarithms of algebraic numbers would easily imply that root counting in R n , for generic systems over Z supported on circuits 5 , can be sped up to worst-case complexity polynomial in n. While the necessary new diophantine bounds appear far out of reach, Baker has proved [Bak98] , in the special case of linear forms of logarithms of rational numbers, that such bounds would follow from a refined version of the famous Masser-Oesterle abc-Conjecture [Mas85, Oes88, Nit13] . Unfortunately, the latter refinement also appears out of reach (as of early 2021). This is one reason that new average-case speed-ups, using geometric numerical conditioning techniques (e.g., [EPR19, EPR20] ) instead of diophantine approximation, may arrive sooner than new worst-case speed-ups. ⋄ 2. Background 2.1. The Complexity of Linear Algebra over Z. Let ω denote the well-known matrix multiplication exponent, i.e., the infimum over all ω such that there exists an algorithm that can multiply an arbitrary pair of n × n matrices, in any field K, using O(n ω ) field operations in K. The best current upper bound is ω < 2.3728639 [V-W12, Leg14] . Recall the notions of reduced row echelon form and leading entries of a matrix, from basic linear algebra (see, e.g., [Pra04] ). For any rational number p q with p, q ∈ Z and gcd(p, q) = 1, its (absolute) logarithmic height is h(p/q) := max{log |p|, log |q|}. (We set h(0) := 0.) We will first need a result on the bit complexity of row reduction for matrices:

Definition 2.1. [Her51, Sch86] We call a matrix U ∈ Z n×n with determinant ±1 unimodular. Given any matrix M ∈ Z n×t , we then call any identity of the form UM = R, with U ∈ Z n×n unimodular and R upper-triangular with all leading entries positive, a Hermite factorization. Finally, we call any identity of the form UMV = S, with U ∈ Z n×n and V ∈ Z t×t both unimodular, and S with diagonal entries s 1 , . . . , s n satisfying s 1 |s 2 , . . . , s n−1 |s n , a Smith factorization of M. ⋄ Lemma 2.2. Suppose M ∈ Z n×t with t ≥ n and all entries having absolute value at most H. Then, in time O tn ω log 2 (nH) , we can row-reduce M to reduced row echelon form R ∈ Q n×t with every nonzero entry of R having logarithmic height O(n log(nH)).

The complexity bound from Lemma 2.2 is easily obtainable by applying a fast algorithm for Hermite Factorization (see, e.g., [Sto00, Ch. 6]) to reduce M to an upper-triangular matrix in Z n×t , dividing through by the leading entries, and then back-substituting to obtain the desired reduced row echelon form. An illuminating alternative discussion, via the Newton identities for sums of powers of roots of a polynomial, can be found in [BCSS98, Ch. 15, Sec. 15.5] .

Via Cramer's Rule and Hadamard's classical inequality on the absolute values of determinants [Mig82, Thm. 1], we can easily obtain the following related bound: Lemma 2.3. If A ∈ Z n×(n+1) has rank n and the entries of the ith row of A have absolute value at most d i , then any generator (b 1 , . . . , b n+1 ) ⊤ ∈ Z (n+1)×1 of the right-null space of A,

We will also need the following complexity bound on Smith factorization:

has all entries of absolute value at most d. Then a Smith factorization UMV = S for M can be found in time O kn ω log 2 (nd) , with all the entries of U, V, S having logarithmic height O(n log(nd)).

Binomial and (n+1)-nomial Systems over (R * ) n . A simple, folkloric algebraic/analytic fact we'll need is the following:

Proposition 2.5. Suppose A, B ∈ Z n×n and x = (x 1 , . . . , x n ) is a vector of indeterminates. Let us define x A to be the vector of monomials x a 1,1 1 · · · x a n,1 n , . . . , x a 1,n 1 · · · x an,n n , where A = [a i,j ]. Then (x A ) B = x AB and, if A is unimodular, the function defined by x → x A defines an analytic group automorphism of (C * ) n that restricts to an analytic group automorphism of R n + . Remark 2.6. A simple consequence of Proposition 2.5 is that if f ∈ R x ±1 1 , . . . , x ±1 n is an n-variate t-nomial with support A, and d is the dimension of the smallest affine subspace containing A, then there is a monomial change of variables x = y U (with U unimodular), and a monomial y b ∈ R y ±1 1 , . . . , y ±1 d , such that g(y) := y b f y U ∈ R y ±1 1 , . . . , y ±1 d is a d-variate t-nomial, and the zero set of f in (R * ) n is analytically isomorphic to the Cartesian product of (R * ) n−d and the zero set of g in (R * ) d . So A in an affine hyperplane implies that the zero set of f in (R * ) n can be easily characterized by the zero set of another t-nomial in fewer variables. ⋄ Another consequence of Lemma 2.2 is that we can almost trivially count the positive roots of binomial systems, provided the exponent vectors are in general position.

Proposition 2.7. Suppose c = (c 1 , . . . , c n ) ∈ (R * ) n , a 1 , . . . , a n ∈ Z n , A is the n × n matrix with jth column a j for all j, UAV = S is a Smith factorization of A, and c ′ := (c ′ 1 , . . . , c ′ n ) := c V . Let s j be the (j, j) entry of S. Then G := (x a 1 −c 1 , . . . , x an −c n ) and (y s 1 1 − c ′ 1 , . . . , y sn n − c ′ n ) have the same number of roots in R n + (resp. (R * ) n , (C * ) n ). In particular, G has exactly 0, 1, or infinitely many roots in R n + under the following respective conditions: 0 : Some c i is negative or [Rank(A) = j < n and c ′ i = 1 for some i ∈ {j + 1, . . . , n}]. 1 : c ∈ R n + and det A = 0. ∞ : c ∈ R n + , Rank(A) = j < n, and c ′ j+1 = · · · = c ′ n = 1.

Proposition 2.7 follows directly from Proposition 2.5. Both facts are folkloric in the toric geometry/Lie group literature (see, e.g., [HS95] or [BG06, Ch. 3]). A more in-depth discussion of binomial systems can be found in [CD07, CL14, PPR19] . Counting roots in (R * ) n is slightly more complicated but still admits efficient formulae.

Proposition 2.8. Following the notation of Proposition 2.7, assume the exponent vectors a 1 , . . . , a n are linearly independent. Let r denote the rank, over the field F 2 , of the mod 2 reduction of A. Also let V denote the upper r × n sub-matrix of V . Then the map m : (R * ) n −→ (R * ) n defined by m(x) := x A is 2 n−r -to-1, and the ith coordinate of its range is R * (resp. R + ) if and only if some (resp. no) entry of the ith column of V is odd. In particular, F has exactly 0 (resp. 2 n−r ) roots in (R * ) n if and only if c ′ i < 0 for some (resp. no) i ≥ r + 1.

Proof: First note that, by the definition of Smith factorization, we have that the diagonal entries s i of S are such that s 1 , . . . , s r are odd and s r+1 , . . . , s n are even. By Proposition 2.5, exponentiating by U or V induces a permutation of the open orthants of R n . In particular, we see that the range of

depends only on the parity of v i,j and the sign of ε j , we then see that the ith coordinate of the range of m is R * (resp. R + ) if and only if some (resp. no) entry of {v 1,i , . . . , v r,i } is odd. So now we know the range of m.

The final remaining assertion follows from our earlier definition c ′ := c V and our earlier assumption that c ∈ (R * ) n .

Remark 2.9. It is important to remember that counting affine roots of n × n binomial systems, with arbitrary exponents and n varying, is in fact #P-complete [CD07] . This implies, for instance, that polynomial-time root counting in R n for systems of the form (x α 1 f 1 , . . . , x αn f n ) -with F = (f 1 , . . . , f n ) an (n + 1)-nomial n × n system and α 1 , . . . , α n ∈ (N ∪ {0}) n -would imply P = NP. In particular, our restriction to n × n systems with union of supports having cardinality ≤ n + 2 is critical if we are to have any hope of someday counting affine roots in P. ⋄

We can now state more explicitly how we deal with positive root counting for t-nomial systems in the case t = n + 1.

n n is an (n + 1)-nomial n × n system, with union of supports A = {a 1 , . . . , a n+1 } not lying in an affine hyperplane, and the coefficient matrix of F has rank n, then the number of positive roots of F is either 0 or 1. Furthermore, if all the coefficients of all the f i have absolute value at most H, then we can determine the number of positive roots of F in time O(n 1+ω log 2 (nH)).

Remark 2.11. The reader disturbed by the complexity bound being independent of A may be reassured to know that (a) checking the hyperplane condition takes time dependent on A and (b) the analogue of our lemma for counting roots in (R * ) n (Corollary 2.12 below) has complexity dependent on A. ⋄ Proof of Lemma 2.10: By our assumption on the coefficient matrix, we may reorder monomials so that the left-most n×n minor of the coefficient matrix has nonzero determinant. So we may divide every f i by x a n+1 without changing the roots of F in (C * ) n , and assume a 1 , . . . , a n are linearly independent and a n+1 = O.

From Lemma 2.2 it is then clear that we can reduce the coefficient matrix of F , [c i,j ] ∈ Z n×(n+1) , to a reduced row echelon form in Q n×(n+1) , in time O(n 1+ω log 2 (nH)). The underlying linear combinations of rows can then be applied to the equations f i = 0 so that F = O can be reduced to a binomial system of the form x A = γ where γ = (γ 1 , . . . , γ n ), A ∈ Z n×n , and the solutions of x A = γ in (C * ) n are the same as the roots of F in (C * ) n .

Clearly then, γ i ≤ 0 for any i implies that F has no positive roots. In which case, we simply report that F has 0 positive roots and conclude, having taken time O(n 1+ω log 2 (nH)).

So γ ∈ R n + implies that F has exactly 1 positive root by Proposition 2.7, and we are done. A simple consequence of our development so far is a method to efficiently count roots in (R * ) n for generic (n + 1)-nomial systems.

Corollary 2.12. Following the notation and assumptions of Lemma 2.10 and its proof, the number of roots of F in (R * ) n is either 0 or 2 n−r , where r is the rank, over the field F 2 , of the mod 2 reduction of A. In particular, we can determine the number of roots of F in (R * ) n in time O(n 1+ω log 2 (ndH)), where d is the maximum absolute value of any entry of A.

Proof: Continuing from the proof of Lemma 2.10 (and having already reduced our input (n + 1)-nomial n × n system to a binomial system), it is clear that Proposition 2.8 tells us that we can easily count the roots of F in (R * ) n : We merely need to check the signs of γ ′ r+1 , . . . , γ ′ n where γ ′ := γ V and UAV = S is a Smith factorization of A. More precisely, instead of computing γ V , we compute sign(γ) (V mod 2) . Computing the mod 2 reduction of V takes time O(n 2 ) and then computing the resulting vector of signs clearly takes time just O(n 2 ). So the only remaining work (after performing Gauss-Jordan elimination on the coefficient matrix of F ) is extracting the Smith factorization of A via, say, Theorem 2.4. So our final complexity bound is O(n 1+ω log 2 (nH) + n 1+ω log(dH)), which is clearly bounded from above by our stated bound.

2.3. Circuits, (n + 2)-nomial systems, and Gale Dual Form with Heights. We now show how to reduce root counting in (R * ) n for F to root counting in certain sub-intervals of R for a linear combination of logarithms in one variable. This reduction dates back to [BS07] , if not earlier, but our statement here includes height and computational complexity bounds that appear to be new. Before proving our reduction, however, let us recall the combinatorial/geometric notion of a circuit:

Definition 2.13. We call any subset A = {a 1 , . . . , a m+2 } ⊂ R n with #A = m + 2 a circuit if and only if the (n + 1) × (m + 2) matrix A with jth column 1 a j has right nullspace of dimension one. In which case, we call any generator b ∈ Z (m+2)×1 \{O} for the right nullspace of A, with 1 for its gcd of coordinates, a (minimal) circuit relation of A. We also call A a degenerate circuit if and only if b has at least one zero coordinate. ⋄ Note that all circuit relations for a fixed circuit (other than the trivial relation O) have zero entries occuring at the same set of coordinates. More precisely, the following proposition is elementary.

Proposition 2.14. Any circuit A = {a 1 , . . . , a m+2 } ⊂ Z n has a unique subset Σ = {a i 1 , . . . , a i ℓ+2 } with Σ a non-degenerate circuit of cardinality ℓ + 2. In particular, {i 1 , . . . , i ℓ+2 } is exactly the set of indices of the nonzero coordinates of any (non-trivial) circuit relation for A. Furthermore, if J ⊆ {i 1 , . . . , i ℓ+2 } and j∈J a j = O, then J = {i 1 , . . . , i ℓ+2 }.

We call Σ the unique non-degenerate sub-circuit of A. Note that any A = {a 1 , . . . , a n+2 } ⊂ Z n with cardinality n + 2, and A not lying in any affine hyperplane, is a circuit.

circuit, and that letting Σ consist of the first 3 points of A yields the unique non-degenerate sub-circuit of A. In particular, Σ has the same minimal circuit relation (up to sign) as the

n n is an (n + 2)-nomial n × n system supported on a circuit A = {a 1 , . . . , a n+2 } with unique non-degenerate sub-circuit Σ = {a 1 , . . . , a m , a n+1 , a n+2 } and all coordinates of the a j have absolute value at most d. Suppose

non-singular for all i = j. Then in time O n 1+ω log 2 (ndH) , we can give either a true declaration that F has no positive roots, or find rational numbers γ 1,0 , γ 1,1 , . . . , γ n+1,0 , γ n+1,1 and nonzero integers b 1 , . . . , b m+1 (with 1 ≤ m ≤ n) satisfying the following properties: 1. The number of roots of the function L(u)

3. L is a non-constant real analytic function on I. 4. We have height bounds h(b i ) = O(n log(nd)) and h(γ i,j ) = O(n log(nH)) for all i.

Example 2.17. Returning to Example 1.3, one can easily apply Gauss-Jordan elimination to the underlying linear combinations of monomials, and then divide every equation by the last monomial x 166 3 x 68 4 x 343 5 , to reduce F = O to the following system having the same roots in (R * ) 5 :

Note in particular that this new system clearly reveals that all the roots of F in (R * ) 5 (for our earlier chosen values of c) must in fact lie in R 5 + , since the right-hand sides are all positive on (R * ) 5 . The underlying circuit relation for the exponent vectors above is the same as the circuit relation for the exponent vectors of F : b = (−2, 2, −2, 2, −2, 1, 1) ⊤ . Part of the proof of Lemma 2.16, applied to our example here, will imply that the resulting linear combination of logarithms L(u) can be easily read from b and the righthand sides of our reduced system: −2 log 16384cu + 1 4 + 2 log |4096cu + 1| − 2 log |256cu + 1| + 2 log |16cu + 1| − 2 log |cu + 1| + log |u|. In particular, for any c > 0, the number of roots of L in I = R + is the same as the number of roots of F in R 5 + . Our family of examples here is in fact an obfuscated version of a family derived in [PR13] , thus accounting for the nice coefficients and high number of positive roots (6) for c ∈ 1 20730 , 1 14392 . A more realistic example of coefficient growth can be found in Example 2.22 below (see also Example 3.2 from Section 3). ⋄ Example 2.18. The stated indexing of the non-degenerate sub-circuit Σ within the union of supports A is important, for otherwise it is possible for F to have infinitely many positive roots. For instance, the 5-nomial 3×3 system (x 2 −1,

, with union of supports ordered so that a 4 = (0, 0, 1) ⊤ and a 5 = (0, 0, 0) ⊤ , has [c i,j ] 3 i,j=1 non-singular (among other 3 × 3 sub-matrices), but infinitely many positive roots: (1 + t, 1, t) for all t ∈ R. Note that, unlike the statement of Lemma 2.16, the indexing is such that the last 2 exponent vectors {a 4 , a 5 } are not in the unique non-degenerate sub-circuit

Proof of Lemma 2.16: We can divide f 1 , . . . , f n by x a n+2 without affecting the positive roots of F . So we may assume a n+2 = O and, since this at worst doubles our original d, our O-estimates will be unaffected. We can then apply Lemma 2.2, thanks to our assumption on the n × n sub-matrices of [c i,j ], to reduce F = O to a system of equations of the form G = O, having the same solutions in R n as F , where G := (g 1 , . . . , g n ),

the γ i,j have logarithmic height O(n log(nH)), and this reduction takes time just O n 1+ω log 2 (nH) . To complete our notation, let us set γ n+1,1 := 1 and γ n+1,0 := 0.

Clearly, if there is an i such that both γ i,0 and γ i,1 are non-positive, then G (and thus F ) has no positive roots, and we can simply stop, having spent time just O n 1+ω log 2 (nH) . So we may assume the following:

We can easily check whether I is non-empty after sorting the (possibly infinite) numbers −γ i,0 /γ i,1 , using just O(n log n) comparisons of integers with O(n log(nH)) bits (via, say, merge sort [CLRS09] ). If I is empty then we can conclude that F has no positive roots and stop (having spent time just O n 1+ω log 2 (nH) ). So we may also assume the following:

I is non-empty.

(2)

We now establish Assertions (1)-(4) via G and Σ: First let b ∈ Z (m+2)×1 be the unique (up to sign) minimal circuit relation of Σ. Note that the coordinates of b are of logarithmic height O(m log(mH)), and the computation of b takes time O mn ω log 2 (nd) , thanks to Lemmata 2.2 and 2.3.

Observe that any root ζ ∈ (R * ) n of G must satisfy

So let P (u) := (γ 1,1 u + γ 1,0 ) b 1 · · · (γ m,1 u + γ m,0 ) bm u b m+1 − 1. Note that n = 1 =⇒ (γ 1,1 , γ 1,0 ) = (−c 2 /c 1 , −c 3 /c 1 ) ∈ (R * ) 2 and thus P is a non-constant real rational function when n = 1. So L(u) is a non-constant real analytic function on I when n = 1. Let us then assume n ≥ 2. By Cramer's Rule, and our assumption on the n × n sub-matrices of [c i,j ], we have γ i,0 = 0 for all i. If m = 1 then we have that P is a non-constant real rational function since b m+1 = 0 (thanks to Σ being a non-degenerate circuit and Proposition 2.14) and there is thus no way to cancel the u b m+1 factor in the product term of P . So L(u) is a non-constant real analytic function on I when m = 1, and we thus now assume m ≥ 2.

By our assumption on the rightmost 2 × 2 minors of [c i,j ], we see that γ i,1 = 0 for some i ∈ {1, . . . , m}, and thus P must have −γ i,0 /γ i,1 ( = 0) as a zero of possibly non-positive order. In particular, the order must be nonzero, thanks to Proposition 2.14. So we see that P is a non-constant real rational function and, again, L is a non-constant real analytic function on I. Now observe that any root ζ ∈ R n + of F yields ζ a n+1 ∈ I as a root of P by Equation (3). Moreover, by Proposition 2.5, any root ζ ′ ∈ R n + of F with (ζ ′ ) a n+1 = ζ a n+1 must satisfy ζ ′ = ζ, since G reduces to a binomial system with a unique positive root once the value of x a n+1 is fixed. (This is because the vectors a 1 , . . . , a n are linearly independent, thanks to {a n+1 , O} ⊂ Σ and A being a circuit.) So P has at least as many roots in I as F has in R n + . Conversely, Proposition 2.5 tells us that any root u ∈ I of P yields a unique ζ ∈ R n + satisfying (ζ a 1 , . . . , ζ an ) = (γ 1,1 u + γ 1,0 , . . . , γ n,1 u + γ n,0 ). Recall that b m+1 = 0. So we also obtain ζ a n+1 = (γ 1,1 u + γ 1,0 ) −b 1 · · · (γ m,1 u + γ m,0 ) −bm 1/b m+1 = u b m+1 /b m+1 = u by the definition of P . So ζ is in fact a root of G. Similarly, a root u ′ ∈ I of P with u ′ = u would yield a positive root of ((ζ ′ ) a 1 , . . . , (ζ ′ ) an ) = (γ 1,1 u ′ + γ 1,0 , . . . , γ n,1 u ′ + γ n,0 ) with (ζ ′ ) a n+1 = ζ a n+1 and thus a root ζ ′ = ζ of F . So F has at least as many roots in R n + as P has in I. Observing that P (u) = 0 ⇐⇒ L(u) = 0 (for u ∈ I), and recalling Assumptions (1) and (2), we thus obtain Assertions (1)-(4). Noting that m ≤ n, we are done.

Our sub-matrix condition from Lemma 2.16 in fact holds for a large fraction of integer coefficients: non-singular for all i = j is at least 1 − 2n 2 2H+1 . Also, the fraction of matrices [c i,j ] ∈ {−H, . . . , H} n×(n+1) with leftmost n × n sub-matrix non-singular is at least 1 − n 2H+1 . Proof: Schwartz's Lemma [Sch80] is a classic result that tells us that if f ∈ C[z 1 , . . . , z n ] has degree d and S ⊂ C is a set of finite cardinality N, then f vanishes at no more than dN n−1 points of S n . The condition stated in our corollary is simply the non-vanishing of a product of n + 1 many n × n sub-determinants of [c i,j ] and n 2 many 2 × 2 sub-determinants of [c i,j ]. The resulting polynomial clearly has degree (n + 1)n + n(n−1) 2 · 2 = 2n 2 . Taking S = {−H, . . . , H} and applying Schwartz's Lemma, we obtain our first bound. Our second bound follows almost identically, just considering one determinant instead.

Recall that a critical point of a function L : R −→ R is a root of the derivative L ′ .

Proposition 2.20. Following the notation and assumptions of Lemma 2.16, let u 0 := inf I, u k := sup I, and suppose u 1 < · · · < u k−1 are the critical points of L in I (k = 1 implying no critical points). Then the number of positive roots of F is exactly the number of We can now state analogues of Lemma 2.16 and Proposition 2.20 for roots in (R * ) n .

Lemma 2.21. Following the notation and assumptions of Lemma 2.16, assume further that b m+1 is odd, a n+2 = O, and let A := [a 1 , . . . , a n ]. Let UAV = S be a Smith factorization of A, and r the rank, over the field F 2 , of the mod 2 reduction of A. Also, for any u ∈ R, let

, and (Γ ′ 1 (u), . . . , Γ ′ n (u)) := (ε 1 , . . . , ε n ) V mod 2 . Then the number of roots of F in (R * ) n is exactly 2 n−r times the number of roots u ∈ R of L satisfying both Λ(u) = sign(u) and Γ ′ r+1 (u), . . . , Γ ′ n (u) > 0. Example 2.22. Consider the 6-nomial 4 × 4 system F = (f 1 , . . . , f 4 ) (The mod 2 reduction of our A here has full rank r = 4 and thus the condition involving the Γ ′ i (u) becomes vacuously true.) It is then easily checked that L is strictly decreasing, with range R, on the first and third intervals; and L is positive on the second interval. (See also Corollary 2.23 below.) So L has exactly 2 roots in R * satisfying the sign conditions 6 of Lemmata 2.21, and thus F has exactly 2 roots in (R * ) 4 . PHCpack (a state of the art polyhedral homotopy solver [Ver10] ) confirms our root count for this F in about 15 minutes, along with a count of 70834 for the total number of roots in (C * ) 4 , as well as approximations of all these roots to 14 decimal places. Our Maple simulation counts the roots of F in (R * ) 4 and R 4 + in under one second. ⋄ Proof of Lemma 2.21: Continuing the notation of the proof of Lemma 2.16, we need to revisit the properties of the rational function P defined earlier. In particular, whereas before we had a natural bijection between the roots of F in R n + and the roots of P in a particular interval I, we now need to consider roots of F with negative coordinates and roots of P throughout R. In particular, a key difference from our earlier lemma is the following simple equivalence, valid for all u ∈ R: P (u) = 0 ⇐⇒ [L(u) = 0 and Λ(u) = sign(u)]. (Indeed, we 12 J. MAURICE ROJAS could obtain u with P (u) = −2 without the condition involving Λ(u).) Note also that by construction, P (0) is either 1 or undefined.

So let ζ ∈ (R * ) n be a root of F . By Relation (3), ζ a n+1 must be a nonzero real root of P and, by the definition of G and the γ i,j (and Proposition 2.8), we must have Γ ′ r+1 (ζ a n+1 ) , . . . , Γ ′ n (ζ a n+1 ) > 0. By Proposition 2.8, there must also be exactly 2 n−r many ζ ′ ∈ (R * ) n of F with (ζ ′ ) a n+1 = ζ a n+1 , because G reduces to a binomial system once the value of ζ a n+1 is fixed. So F has no more than 2 n−r times as many roots in (R * ) n as P has in R * .

Conversely, if u ∈ R * is a root of P then Proposition 2.8 tells us that Γ ′ r+1 (u), . . . , Γ ′ n (u) > 0 implies that there are exactly 2 n−r many ζ ∈ (R * ) n satisfying (ζ a 1 , . . . , ζ an ) = (γ 1,1 u + γ 1,0 , . . . , γ n,1 u + γ n,0 ). (Note also that γ i,1 u + γ i,0 = 0 for all i since P (u) = 0 when γ i,1 u + γ i,0 = 0.) We then also obtain ζ b m+1 a n+1 = (γ 1,1 u + γ 1,0 ) −b 1 · · · (γ m,1 u + γ m,0 ) −bm = u b m+1 by Relation (3). Since b m+1 is odd, all our resulting ζ must satisfy ζ a n+1 = u and therefore be roots of G (and thus of F ). Similarly, a real root u ′ of P with (u ′ ) b m+1 = u b m+1 would yield a collection of 2 n−r many ζ ′ ∈ (R * ) n that are roots of F but with (ζ ′ ) a n+1 = ζ a n+1 , since b m+1 is odd and u ∈ R * . So the number of roots of F in (R * ) n is at least 2 n−r times the number of roots of P in R * .

The following variant of Proposition 2.20 can be proved almost the same as Proposition 2.20, simply using Lemma 2.21 instead of Lemma 2.16:

Corollary 2.23. Following the notation and assumptions of Lemma 2.21, let w 1 < · · · < w ℓ−1 be the critical points and poles of L in R, and set w 0 := −∞ and w ℓ := +∞. Let N be the number of i ∈ {0, . . . , ℓ − 1} such that Λ(u) = sign(u) and Γ ′ r+1 (u), . . . , Γ ′ n (u) > 0 for all u ∈ (w i , w i+1 ), and lim u→w + i L(u) lim u→w − i+1 L(u) < 0. Then the number of roots of F in (R * ) n is exactly N plus the number of degenerate roots of L in R. 

Letting c 0 + c 1 x 1 + · · · + c d x d 1 2 := d i=0 |c i | 2 , we recall the following classical inequality:

Landau's Inequality. [Mig82] If β ∈ Q has minimal polynomial m ∈ Z[x 1 ] with relatively prime coefficients then h(β) ≤ log |m| 2 deg m .

It will also be useful to have a mildly refined version Liouville's classic bound [Lio51] on the separation between rational numbers and irrational algebraic numbers.

q d for all p, q ∈ Z with q > 0.

Proof: First note that the numerator of the large fraction above is positive since m is the minimal polynomial of β and thus m ′ (β) = 0.

Via Taylor expansion we then obtain the following:

Since m is irreducible and of degree ≥ 2, m has no rational roots, and thus q d m(p/q) must be a nonzero integer. So we obtain q d |m(p/q)| ≥ 1 and thus |m(p/q)| ≥ 1/q d . Combined with our last Taylor series inequalities, we are done. 

Letting c 0 + c 1 x 1 + · · · + c d x d 1 ∞ := max i |c i |, recall the following classic bounds on the size and minimal spacing of roots of polynomials: 1.7, (i), (8.1.3) ].) If f ∈ Z[x 1 ] satisfies |f | ∞ ≤ H and ζ ∈ C is a nonzero root of f then 1 1+H < |ζ| < 1 + H. Mahler's Theorem. [Mah64] Suppose f ∈ Z[x 1 ] is square-free, has degree d, and |f | ∞ ≤ H. Then any two distinct complex roots ζ 1 , ζ 2 of f satisfy |ζ 1 − ζ 2 | > √ 3(d + 1) −(2d+1)/2 H −(d−1) . In particular, | log |ζ 1 − ζ 2 || = O(d log(dH)).

Letting c 0 + c 1 x 1 + · · · + c d x d 1 1 := d i=0 |c i |, recall also the following nice bound on the coefficients of divisors of polynomials:

Lemma 2.28. [Mig82, Thm. 4 ] Suppose f, g ∈ C[x 1 ] have respective leading coefficients c and γ, and g|f . Then |g| 1 ≤ 2 deg g γ c |f | 2 . A simple consequence of the last two bounds is the following extension of Mahler's bound to the case of polynomials with degenerate roots.

Corollary 2.29. Suppose f ∈ Z[x 1 ] has degree d and |f | ∞ ≤ H. Then any two distinct complex roots ζ 1 , ζ 2 of f satisfy | log |ζ 1 − ζ 2 || = O(d 2 + d log(dH)).

We will also need the following bound on the coefficients of products of polynomials:

Gelfond's Lemma. (See, e.g., [BG06, Lemma 1.6.11, pg. 27]) (Special case) If f 1 , . . . , f k ∈

Finally, we will need the following bound on higher derivatives of polynomials, dating back to work of Duffin and Schaeffer [DS41] , based on a classic bound of A. A. Markov [Mar89] :

After rescaling the variable so it ranges over [− 

We are now ready to prove two key lemmata (3.1 and 3.4 below) that enable our new complexity bounds. Example 3.2. Example 2.22 is more representative (than Example 2.17) of the coefficient growth one encounters when converting F into a univariate linear combination of logarithms L: There we saw an input 6-nomial 4 × 4 system F with coefficients and exponents having at most 2 digits, resulting in an L with coefficients having 6 or fewer digits. In particular, the polynomial g encoding the critical points of L is

which has coefficients with at most 24 digits, and 2 real roots, neither of which lies in the sub-intervals of R contributing to the root count of F in (R * ) 4 . More to the point, it is the signs of the poles of L, instead of the signs of the critical values, that determine the number of roots of F in (R * ) 4 for Example 2.22. ⋄ Example 3.3. Returning to Example 2.17, which had L(u) being −2 log 16384cu + 1 4 + 2 log |4096cu + 1| − 2 log |256cu + 1| + 2 log |16cu + 1| − 2 log |cu + 1| + log |u|, it is easily checked via Maple that this L has exactly 5 critical values, alternating in sign, and the underlying critical points interlace the 6 positive roots of L. ⋄ Proof of Lemma 3.1: First observe that L ′ (u) = m i=1 b i γ i,1 γ i,1 u+γ i,0 . Thanks to our determinant assumption, L ′ has exactly m distinct poles. Gelfond's Lemma implies that the coefficients of the monomial term expansion of (r 1 u + s 1 ) · · · (r k u + s k ) have logarithmic height O(k log H) if the r i and s i are integers of absolute value at most H. Letting ν i be the least common multiple of the denominators of γ i,1 and γ i,0 , and setting

, and g(u) is nothing more than L ′ (u) m j=1 (γ j,1 u + γ j,0 )ν j . So we clearly obtain the statement on the real critical points of L being the real roots of g, and it is clear that deg g ≤ m − 1.

Gelfond's Lemma implies that |g i | ∞ ≤ BH 2 2 m−1 H 2(m−1) . Clearly then, |g| ∞ ≤ m2 m−1 BH 2m . That L has at most m roots in I is immediate from Rolle's Theorem, since deg g ≤ m − 1.

Recall that a critical value of a function L : R −→ R is the value of L at a critical point of L.

Lemma 3.4. Following the notation and assumptions of Lemma 3.1, let I be any open interval defined by consecutive real poles of L, let ε denote any nonzero critical value of L, and let δ (resp. η) be the minimum of |ζ 1 − ζ 2 | over all distinct roots ζ 1 , ζ 2 ∈ I of L (resp. the derivative L ′ ). Finally, let ∆ denote the minimum of |ζ − µ| as ζ (resp. µ) ranges over the critical points (resp. poles) of L. Assertion (1) then follows immediately by applying Corollary 2.29 to g, thanks to Lemma 3.1.

Assertion (2) then follows routinely from Theorem 2.26 upon observing that |ε| is nothing more than the absolute value of a linear combination of logarithms of real algebraic numbers. In particular, the arguments of the logarithms constituting L(u j ) at a critical value u j ∈ I (for some j ∈ {1, . . . , k − 1}) all lie in the same real algebraic extension: Q(u j ). Noting that the minimal polynomial, p, of u j has degree ≤ m − 1, Lemmata 2.28 and 3.1 then tell us that |p| ∞ ≤ 2 m−1 |g| ∞ |g| 2 (since p|g), and thus

So log |p| 2 ≤ log √ m · m 3/2 B 2 8 m−1 H 4m , and thus Landau's Inequality tells us that deg(p)h(u j ) ≤ log (m 2 8 m−1 B 2 H 4m ). Proposition 2.27 then tells us that 

(picking, say, θ 1 = log(30.25/30) and θ 2 = 0.25/30.25), thus proving Assertion (2). Note that we could have used any number strictly greater than 60, instead of 61, but we have opted for a more concise bound and a shorter proof.

To prove Assertion (3) observe that ∆ = min{u 1 − u 0 , u k − u k−1 }, i.e., ∆ = |u j ′ − u ℓ | for some j ′ ∈ {1, k − 1} and ℓ ∈ {0, k − 1}, by our earlier definitions. If ∆ = ∞ then there is nothing to prove, so let us assume ∆ < ∞. If u j ′ ∈ Q then Assertion (3) follows easily from Proposition 2.24, since u ℓ has logarithmic height no greater than 2 log H and u j ′ must have logarithmic height no greater than O(log(B) + m log H). So we may assume that u j ′ is algebraic of degree at least 2 over Q.

We can then apply Theorem 2.25 and Lemma 3.1 to obtain that ∆ must be bounded from below by

We know that |u j ′ | < 1 + m2 m−1 BH 2m by Proposition 2.27, so it is enough to minimize the preceding sum of derivative norms over the interval J := [−1 − m2 m−1 BH 2m , 1 + m2 m−1 BH 2m ].

Noting the easy inequality max −t≤x 1 ≤t |f (x 1 )| ≤ |f | 1 max 1, |t| d for any f ∈ R[x 1 ] of degree d and t ∈ R we then have max x 1 ∈J |g(x 1 )| ≤ |g| 1 max

and Corollary 2.30 then implies

since p has degree ≤ m − 1. Since |p| 1 ≤ m|p| ∞ , Inequality (4) tells us that p (r) (u j ′ ) is bounded from above by

where the last inequality follows easily from Stirling's classical estimate for the factorial function. So then, |p ′ (u j ′ )| +

is strictly less than (m − 1) 2 e + ((m−1) 2 e/2) 2 2! + · · · + ((m−1) 2 e/r) r r!

Now, by the Maclaurin series for e x , the bracketed factor above is strictly less than e (m−1) 2 e . So then, |p ′ (u j ′ )| +

for any θ 3 , θ 4 > 0. Observing that 2e e < 30.31, we can then clearly pick θ 3 and θ 4 to obtain

and thus, combining with Inequality (5), 1 ∆ = O 31 m(m−1) B m+2 H 2m 2 +6m−2 , and we obtain Assertion (3) by taking logarithms.

To prove Assertion (4) we merely use the Mean Value Theorem. First, let δ ′ be the minimum distance between u j and ζ ′ where ζ ′ is any root of L. (Recall that u j , with j ∈ {1, . . . , k − 1}, is a critical point of L corresponding to a nonzero critical value ε of L.) Clearly, δ ≥ 2δ ′ > 0 (thanks to Rolle's Theorem), so it is enough to prove a sufficiently good lower bound on δ ′ . Note in particular that if δ ′ > ∆/2 then we are done, thanks to Assertion (3). So let us assume δ ′ ≤ ∆/2.

Recall that, from the proof of Lemma 3.1, we have L ′ (u) = g(u)/ m i=1 (γ i,1 u + γ i,0 )ν i where ν i is the least common multiple of the denominators of γ i,1 and γ i,0 .

By the Mean Value Theorem, we must have |L ′ (ξ)| = ε δ ′ for some ξ ∈ (u j − δ ′ , u j + δ ′ ). So then, thanks to Inequalities (6) and (7), we obtain

Since δ ′ = |ε/L ′ (ξ)| we thus obtain that log δ ′ = log |ε| − log |L ′ (ξ)|, which is then bounded from below by −O 61 m log m+1 (BH 3m−1 ) − O(log(m) + m + log(B) + m log(H) + m log(m2 m−1 BH 2m )) −mO(m 2 log(31) + m log(B) + m 2 log H), which reduces to −O 61 m log m+1 (BH 3m−1 ) .

3.1. The Complexity of Approximating Logarithms and Real Roots of Polynomials. Any real number can be expressed in binary. Since 2 ⌊log 2 x⌋ ≤ x ≤ 2 1+⌊log 2 x⌋ for any x ∈ R + , it is easy to check that 1 + ⌊log 2 x⌋ is the number of bits for the integer part of x. It then makes sense to call the binary expansion of 2 ℓ−1−⌊log 2 x⌋ x the ℓ most significant bits of an x ∈ R + . Clearly, knowing the ℓ most significant bits of x means that one knows x within a multiple of (1 + 2 −ℓ ) ±1 .

Let us recall the following classical fact on approximating logarithms via Arithmetic-Geometric Iteration:

Theorem 3.5. [Ber03, Sec. 5] Given any positive x ∈ Q of logarithmic height h, and ℓ ∈ N with ℓ ≥ h, we can compute ⌊log 2 max{1, log |x|}⌋ and the ℓ most significant bits of log x in time O(ℓ log 2 ℓ).

The underlying technique dates back to Gauss and was refined for computer use in the 1970s by many researchers (see, e.g., [Bre76, Sal76, BB88] ). We note that in the complexity bound above, we are applying the recent O(n log n) algorithm of Harvey and van der Hoeven for multiplying two n-bit integers [HvdH19] . Should we use a more practical (but asymptotically slower) integer multiplication algorithm then the time can still be kept at O(ℓ 1.585 ) or lower.

Recall that bisection is the ancient technique of approximating a root of a continuous function f : [r 1 , r 2 ] −→ R by the following trick: If sign(f (r 1 )f (r 2 )) < 0 then f must have a root in the open interval (r 1 , r 2 ), and this root lies in the left half-interval r 1 , r 1 +r 2 2 if and only if sign f (r 1 )f r 1 +r 2 2 < 0. Bisection thus allows one to extract an extra bit of precision for a root of f at the cost of one more evaluation of f . Put another way, bisection allows one to halve the size of an isolating interval at the cost of one more evaluation of f . We will need the following result on the bit complexity of approximating the real roots of a polynomial in Z[x 1 ] by rational numbers. Proof: The case ℓ = 0 is well-known in the computational algebra community and is elegantly described in [Sag11] . (In fact, [Sag11] even allows polynomials with real coefficients known only up to a given tolerance.) In particular, we merely apply Theorem 24 of [Sag11] to the square-free part, p := f / gcd(f, f ′ ), of f . Note that p can be computed within time O(d 2 log 2 H), and its coefficients are integers of logarithmic height log H ′ = O(d + log H), thanks to Lemma 2.28. So our overall complexity bound holds thanks to Lemma 2.28 and the O(d 4 log 2 H ′ ) bound (in our notation) from [Sag11, Thm. 24 ].

The case of arbitrary ℓ can be derived simply by applying bisection after using the ℓ = 0 case to start with isolating intervals that are likely larger than desired, but correct in number, for the real roots of f : One first observes that if α ∈ Q has logarithmic height L then Proposition 2.24 implies that f (α) has height O(d log(H)+d 2 L). So we can correctly find the sign of f (α) by, say, Horner's Rule [vzGG13] , using O(d log(H) + d 2 L) bits of accuracy in all intermediate calculations.

Since there are at most d roots, and each application of Horner's Rule takes O(d) multiplications and additions, we see that applying bisection to each of our initial isolating intervals (to halve the size of each interval) takes time O((d 3 log(H) + d 4 L) log(dL log H)), assuming we use the fast multiplication algorithm of [HvdH19] .

Corollary 2.29 then tells us that | log δ(f )| = O(d 2 + d log(dH)). This means that getting ℓ additional bits of accuracy beyond the minimum root separation requires time Remark 3.7. We have opted for a streamlined proof at the expense of a larger complexity estimate. In particular, the exponent of d in our bound can likely be lowered slightly if one uses more sophisticted techniques, some of which are discussed further in [Sag11] and the references therein. ⋄

Our central algorithm for counting roots in (R * ) n is conceptually simple but ultimately somewhat laborious: Reduce to computing the signs of a linear combination of m logarithms at its critical points and poles. To compute the signs at the critical points, we simply approximate the input to each logarithm, and each resulting summand, to extremely high accuracy. The devil is in the level of accuracy, but thanks to our earlier development, the required accuracy can be estimated explicitly, and the resulting complexity bound is quadratic in (m log(BH)) m+1 .

Algorithm 4.1. Input: Integers b 1 , . . . , b m and rational numbers γ 1,1 , γ 1,0 , . . . , γ m,1 , γ m,0 , u 0 , u ∞ , with m ≥ 2, γ i,1 u + γ i,0 > 0 for all u ∈ (u 0 , u ∞ ) and i ∈ {1, . . . , m}, and det γ i,1 γ i,0 γ j,1 γ j,0 = 0 for all i, j. 

where ν i denotes the least common multiple of the denominators of γ i,1 and γ i,0 . 2. Via Lemma 3.6, find respective isolating intervals J 1 , . . . , J k−1 to the roots u 1 < · · · < u k−1 of g in (u 0 , u ∞ ) such that each J i has width no greater than 2 −ρ . 3. For all i ∈ {1, . . . , k − 1} do: 4.

For all j ∈ {1, . . . , m} do: 6.

Compute, via Theorem 3.5, a rational number L j agreeing with log |γ j,1ūi + γ j,0 | in its first ⌈1.443E + log 2 (6m)⌉ most significant bits.

End For 8.

Let L i := m j=1 b j L j and θ i := sign(L i ).

If |L i | > 1 2 2 −1.443E then 10.

Output "The sign of L at u i is θ i ." 11.

Else 12.

Output "L(u i ) = 0." 13.

End If 14. End For Proof: The correctness of our algorithm follows directly from Theorem 2.26 and Lemmata 3.1 and 3.4. First note that the classical inequality 1 − 1 x ≤ log x ≤ x − 1 (for all x > 0), yields s v+s ≤ log(v + s) − log v ≤ s v (for all v > 0 and s > −v), upon setting x = v+s v . Setting v = γ j,1ūj + γ j,0 and s = γ j,1 (u j −ū j ), and assuming γ j,1 u j + γ j,0 , γ j,1ūj + γ j,0 > 0, we then obtain (u j −ū j )γ j,1 γ j,1 u j + γ j,0 ≤ log(γ j,1 u j + γ j,0 ) − log(γ j,1ūj + γ j,0 ) ≤ (u j −ū j )γ j,1 γ j,1ūj + γ j,0 .

The proof of Assertion (3) of Lemma 3.4 tells us that |γ j,1 u j +γ j,0 | |γ j,1 | ≥ ∆. Since 1/ log 2 < 1.443 we have ∆ > 2 −1.443D , thanks to the definition of D. So the definition of s tells us that |u j −ū j | ≤ 1 2 2 −1.443D is sufficient to guarantee that |γ j,1ūj +γ j,0 | |γ j,1 | ≥ ∆/2. So, by Inequality (8), we obtain that |u j −ū j | ≤ 2 −ρ guarantees | log(γ i,1 u i + γ i,0 ) − log(γ i,1ūi + γ i,0 )| ≤ 1 6m 2 −1.443E . Should γ i,1 u + γ i,0 < 0 we can repeat our preceding argument, with a sign flip, to obtain that |u j −ū j | ≤ 2 −ρ guarantees | log |γ i,1 u i + γ i,0 | − log |γ i,1ūi + γ i,0 || ≤ 1 6m 2 −1.443E . So then, thanks to Step 6 and the Triangle Inequality, we see that our algorithm computes, for each i ∈ {1, . . . , k − 1}, a rational L i such that |L(u i ) − L i | ≤ 1 3 2 −1.443E . Theorem 2.26 then tells us that |L(u i )| is either 0 or strictly greater than 2 −1.443E . So the threshold on |L i | from Step 9 indeed correctly distinguishes between L(u i ) being nonzero or zero, and the signs of L(u i ) and L i also match when L(u i ) = 0 thanks to our chosen accuracy. In other words, our algorithm is correct.

We now analyze the complexity of our algorithm. First note that H, A , E, D, and ρ need not be computed exactly: it is sufficient to work with the ceilings of these quantities, or even the smallest powers of 2 respectively greater than these quantities. In particular, these parameters can easily be computed via standard efficient methods for computing the exponential function [Ahr99] (along with Theorem 3.5) and thus the complexity of Step 0 is negligible, and in fact asymptotically dominated by Steps 2 and beyond.

Likewise, Step 1 is easily seen to take time within O(m 2 (log 2 (B) + m log 2 H)), to be asymptotically dominated by Step 2 and beyond. (The preceding bound is a crude overestimate of what can be obtained by combining the fast polynomial multiplication method from, say, [vzGG13, Sec. 8.4 ] with the fast integer multiplication method of Harvey and van der Hoeven [HvdH19].) Lemma 3.1 tells us that the complexity of Step 2 can be estimated by replacing (d, H, ℓ) in the statement of Lemma 3.6 by (m − 1, m2 m−1 BH 2m , ρ). Noting that ρ = O(E) and m r , log r B, log r H = O(E) for any r > 0, Lemma 3.6 then tells us that Step 2 takes time O(m 4 E 2 log 2 E), which is bounded from above by By Assertion (1) of Lemma 5.3, if min π i (A) > 0 for some i ∈ {1, . . . , ℓ} then F has infinitely many real roots. So we may assume that min π i (A) = 0 for all i ∈ {1, . . . , ℓ}.

Observe now that if ℓ = n (i.e., if min π i (A) = 0 for all i) and A i is empty for some i then F has infinitely many real roots by Assertion (2) of Lemma 5.3. So if ℓ = n we may assume that A i is non-empty for all i. Since Supp(f i ) = A generically for all i, Assertion (4) of Lemma 5.3 tells us that F generically has no roots on any coordinate subspace containing one of the coordinate axes. So now we are left with checking whether F vanishes at O. Since F vanishes at O if and only if A 1 ∩ · · · ∩ A n is non-empty, the case ℓ = n is done and we assume now that ℓ < n. In other words, we now need only check for roots on the coordinate subspace {x 1 = · · · = x ℓ = 0} of R n . Now, should A 1 ∩ · · · ∩ A ℓ be empty, then Assertion (2) of Lemma 5.3 tells us that F has infinitely many real roots. So we may assume A 1 ∩ · · · ∩ A ℓ = ∅. Since Supp(f i ) = A generically, Assertion (4) of Lemma 5.3 then tells us that F generically has no roots on any coordinate subspace of R n containing {x 1 = · · · = x ℓ = 0}.

We have thus shown how to count roots in all coordinate subspaces of R n . In particular, we see that the complexity of counting roots in R n is asymptotically the same as our complexity bound for counting in (R * ) n , since the only additional work is computing the π i (A), the A i , A 1 ∩ · · · ∩ A ℓ , and A 1 ∩ · · · ∩ A n , which takes time neglible compared to our main bound.

A consequence of our preceding proof is that the additional genericity condition needed to efficiently count roots in R n can be taken to be the following:

All the coefficients of F are nonzero, and a collection of sparse resultants (one for each coordinate subspace of R n ), in the coefficients of F , all not vanish. So by Proposition 5.1 and Lemma 5.2, the degree of the product of all these underlying polynomials is no greater than n(n + 2) + d n + nd n−1 + n 2 d n−2 + · · · + nd = n 2 + n + (d + 1) n − 1. By Schwartz's Lemma [Sch80] , as applied in the proof of Corollary 2.19, it is then clear that F having uniformly random coefficients in − n 2 +n+(d+1) n −1 2ε , . . . , n 2 +n+(d+1) n −1 2ε is enough to make our additional genericity condition hold with probability greater than 1 − ε.

Fast computations of the exponential function

Efficient Algorithms

The Theory of Linear Forms in Logarithms

Logarithmic forms and the abc-conjecture

Logarithmic forms and group varieties

Computing the dimension of a semialgebraic set

Algorithms in real algebraic geometry

Software for the Gale transform of fewnomial systems and a Descartes rule for fewnomials

Numerically solving polynomial systems with Bertini, Software, Environments, and Tools 25

The Complexity of Elementary Algebra and Geometry

Computing Logarithm Intervals with the Arithmetic-Geometric Mean Iterations

Polynomial Systems with Few Real Zeroes

Topologie des variétés creuses, Habilitation thesis

Descartes' Rule of Signs for Polynomial Systems Supported on Circuits

Optimal Descartes' rule of signs for systems supported on circuits

Regions of multistationarity in cascades of Goldbeter-Koshland loops

Lower bounds for positive roots and regions of multistationarity in chemical reaction networks

Sign conditions for the existence of at least one positive solution of a sparse polynomial system

Faster Real Feasibility via Circuit Discriminants

New Fewnomial Upper Bounds from Gale Dual Polynomial Systems

Heights in Diophantine Geometry, new mathematical monographs: 4

Roots of polynomials in subgroups of F * p and applications to congruences

On the Complexity of Familiar Functions and Numbers

Fast Multiple-Precision Evaluation of Elementary Functions

Classical and modular approaches to exponential Diophantine equations, I, Fibonacci and Lucas perfect powers

On the Number of Real Zeros of Random Fewnomials

Ran Canetti

On the statistical properties of Diffie-Hellman distributions

Some Algebraic and Geometric Computations in PSPACE

Counting solutions to binomial complete intersections

Relative Entropy Relaxations for Signomial Optimization

Solutions to Systems of Binomial Equations

Sparse Univariate Polynomials with Many Roots Over a Finite Field

Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields

Introduction to Algorithms

A numerical algorithm for zero counting. I: Complexity and Accuracy

Computing the homology of real projective sets

Parameter regions that give rise to 2[n/2] + 1 positive steady states in the n-site phosphorylation system

Multistationarity in Structured Reaction Networks

Optimization over the boolean hypercube via sums of nonnnegative circuit polynomials

A refinement of an inequality of the brothers Markoff

MixedVolume-SparseResultants software package

Probabilistic Condition Number Estimates for Real Polynomial Systems I: A Broader Family of Distributions

Probabilistic Condition Number Estimates for Real Polynomial Systems II: Structure and Smoothed Analysis

Defective dual varieties or real spectra

Modern Computer Algebra

Descartes' Rule of Signs: Another Construction

Bounded-degree factors of lacunary multivariate polynomials

Semi-Algebraic Local-Triviality in Semi-Algebraic Mappings

Integer multiplication in time

Sur l'introduction des variables continues dans la théorie des nombres

A Polyhedral Method for Solving Sparse Polynomial Systems

A class of systems of transcendental equations

On the intersection of a sparse curve and a low-degree curve: A polynomial version of the lost theorem

A Wronskian approach to the real tauconjecture

Newton Polytopes and the Bézout Theorem

Mixed volume computation in solving polynomial systems

Powers of tensors and fast matrix multiplication

Counting Real Connected Components of Trinomial Curves Intersections and m-nomial Hypersurfaces

Sur des classes trèsétendues de quantités dont la valeur n'est ni algébrique, ni même réductibleá des irrationnelles algébriques

An inequality for the discriminant of a polynomial

On a certain problem of D. I. Mendeleiff," (in Russian) Utcheniya Zapiski Imperatorskoi Akademii Nauk

Open Problems

An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers, II

Some Useful Bounds

How many zeroes? Counting the number of solutions of systems of polynomials via geometry at infinity

Linear forms in logarithms of rational numbers

The abc Conjecture Home Page

Nouvelles approches du 'Théorème' de Fermat

A Faster Solution to Smale's 17th Problem I: Real Binomial Systems

Optimization and NP R -completeness of certain fewnomials

Counting real zeros in the multivariate case

Fewnomial Systems with Many Roots, and an Adelic Tau Conjecture

Problems and Theorems in Linear Algebra, translations of mathematical monographs

Analytic Theory of Polynomials

On the Computational Complexity and Geometry of the First-Order Theory of the Reals, I-III

Solving degenerate sparse polynomial systems faster

Why Polyhedra Matter in Non-Linear Equation Solving

Solving zero-dimensional systems through the rational univariate representation

A General Approach to Isolating Roots of a Bit-stream Polynomial

Computation of π using arithmetic-geometric mean

Theory of Linear and Integer Programming

Fast Probabilistic Algorithms for Verification of Polynomial Identities

The Geometry of René Descartes, translated from the French and Latin

Algorithms for Matrix Canonical Forms

Multiplying matrices faster than Coppersmith-Winograd

Polynomial Homotopy Continuation with PHCpack

Acknowledgements I thank Dan Bates and Jon Hauenstein for answering my questions on how Bertini handles polynomial systems of extremely high degree. I also thank Jan Verschelde for answering my questions on fine-tuning the options in PHCpack. Special thanks to Timo de Wolff for pointing out reference [CS16] and Alexander Barvinok for pointing out reference [PRS93] .I am also happy to thank Weixun Deng, Alperen Ergür, and Grigoris Paouris for good company and inspirational conversations.

Tien-Yien Li passed away a few months into the COVID-19 pandemic. TY (as he was known to his friends) was an immensely kind and generous man, and a dear friend, in addition to being a great mathematician. Through hours-long grilling sessions in October 1993, at the Centre de Recerca Matematica in Barcelona, he taught me lessons on perseverance, curiosity, scholarship, and generosity that I would always remember. It was there that I also got to know TY and his unique sense of humor. He always faced the greatest difficulties with a smile. I admired him both as a person and a mathematician. I truly miss him. 

We thus see, from comparison to Estimate (9), that Step 2 in fact dominates the asymptotic complexity of our entire algorithm, so our complexity estimate follows.We can now state our algorithm for counting the positive roots of circuit systems: c n,1 · · · c n,n c n,n+2   are non-singular, and whether c i,n+1 c i,n+2 c j,n+1 c j,n+2 is non-singular for all i = j. If not, then Output "Your system might have infinitely many roots but I'm not sure: Please check if there are any updates to this algorithm, addressing the cases of vanishing minors." and STOP. 2. Reduce F = O to a system of equations of the form G = O, where G := (g 1 , . . . , g n )andbe the unique (up to sign) minimal circuit relation of Σ, and define Proof: Letting u 0 := inf I, u ∞ := u k := sup I, and letting u 1 < · · · < u k−1 be the critical points of L in I as before, note that the sign of lim u→u(This index is unique thanks to Step 1 ensuring the 2 × 2 minor condition.) Similarly, lim u→u − k L(u) is simply the sign of −b i ′′ (resp. b 1 + · · · + b m+1 ) for some easily computable unique index i ′′ ∈ {1, . . . , m + 1} if u k < ∞ (resp. u k = +∞). So the use of Proposition 2.20 is clear.The correctness of Algorithm 4.3 then follows directly from Lemmata 2.16, Proposition 2.20, and Lemma 4.2. So we now analyze the complexity of our algorithm.Thanks to Lemmata 2.2 and 2.3, it is clear that Steps 0-3 are doable in time O(n 2+ω log 2 (ndH)). This will not be the dominant part of the algorithm: Observing that h(γ i,j ) = O(n log(nH)) and h(b i ) = O(n log(nd)) for all i, j, Lemma 4.2 then tells us that applying Algorithm 4.1 and Proposition 2.20 (with m ≤ n + 1) takes time O(n log(nd) + n 2 log(nH)) 2n+4 .We are now ready to state the analogue of Lemma 4.4 for counting roots in (R * ) n :Lemma 4.5. Given any (n + 2)-nomial n × n system F = (f 1 , . . . , f n ) ∈ Z x ±1 1 , . . . , x ±1 n n supported on a circuit A with cardinality n + 2, we can count exactly the number of roots of In particular, the modifications to Algorithm 4.3 are that we replace Steps 0, 3, and 4 respectively by Steps 0', 3', and 4' stated below: 0'. Find the unique non-degenerate sub-circuit Σ of A and underlying minimal circuit relation b ∈ Z (m+2)×1 , re-index the points of A so that Σ = {a 1 , . . . , a m , a n+1 , a n+2 } and b m+1 is odd, translate a 1 , . . . , a n+1 by −a n+2 , and set a n+2 := O. Note in particular that, in Step 0', b must have an odd coordinate since minimal circuit relations are assumed to have relatively prime coordinates. Also, the left or right-handed limits of L at a real (possibly infinite) pole are easy to compute via the sign of a suitable b i (if the pole is finite) or the sign of b 1 + · · · + b m+1 (if the pole is ±∞). The correctness of the modified algorithm is then immediate. The complexity analysis for our modified algorithm is almost identical to that of Algorithm 4.3, save that there is extra work taking time O(n · n 2 ) to compute the signs of Λ(u) and the Γ ′ (u i ). This is negligible compared to the other steps, so our final asymptotic complexity bound remains the same.Remark 4.6. While we could have simply applied Algorithm 4.3 2 n times (once for each orthant of (R * ) n ), our proof above is more practical: It enables complexity polynomial in n for root counting in (R * ) n should sufficiently sharp new diophantine estimates become available (see Remark 1.5 from the introduction). ⋄

To conclude, we'll first need to recall some observations regarding sparse resultants and roots of t-nomial (n + 1) × n (over-determined) systems on coordinate subspaces. For further details on sparse resultants we refer the reader to [GKZ94] .Proposition 5.1. If A ⊂ Z n is a circuit and X is any coordinate subspace of R n then A ∩ X is either empty, the vertex set of a simplex, or a circuit. , c i,j , . . .) = 0] =⇒ F has no roots in (C * ) n . In particular, if t = n + 1 (resp. t = n + 2) then ∆ A = det[c i,j ] (resp. deg ∆ A ≤ n · n!V ), where V is the volume of the convex hull of A, normalized so that the unit n-cube has volume 1.

The polynomial ∆ A above is an example of a sparse resultant, and is one of many ways to formulate the fact that (n + 1)-tuples of n-variate polynomials generically have no roots. Our statement above is minimalist and is meant to approach affine roots in the following simple way: Example 5.4. It is easy to check (by specializing subsets of variables to 0, and then dividing out by x 1 x 2 x 3 ) that the real zero set of the 4-nomial 3 × 3 systemis the union of the point (1, 1, 1) , the x 1 -axis, the x 2 -axis, and the x 3 -axis. Note in particular that while the underlying support A satisfies min π i (A) = 0 for all i, A does not intersect any of the coordinate axes. Hence the infinitude of real roots for our example. ⋄ Proof of Lemma 5.3: Assertion (1) is merely the case of all the f j being divisible by x i . Assertion (2) is immediate upon rewriting the f j as elements of C x ±1 ℓ+1 , . . . , x ±1n [x 1 , . . . , x ℓ ]: The condition on A holds if and only if all the f j lack a non-trivial monomial term of degree 0 with respect to (x 1 , . . . , x ℓ ). Assertion (3) is merely the observation that roots with x i = 0 are impossible if some f j has a monomial with negative exponent for x i .To prove Assertion (4) observe that setting x 1 = · · · = x ℓ = 0 in F results in such an F generically becoming an (over-determined) n × (n − ℓ) system. In particular, for F to fail to have roots, it is enough for the first n − ℓ + 1 polynomials to fail to have a common root. So by Lemma 5.2 we are done. 5.1. The Proof of Theorem 1.1. The cases of root counting in R n + and (R * ) n follow respectively from Lemmata 4.4 and 4.5 when t = n + 2. For t = n + 1 we simply use Lemma 2.10 and Corollary 2.12 instead.To count roots in R n , let us first compute min π i (A) for all i ∈ {1, . . . , n}: This can be done simply by reading the coordinates of the points of A, and this takes time O(n 2 log d). Let A i denote the intersection of A with the x i -axis. Then we can also easily compute A 1 , . . . , A n and A 1 ∩ · · · ∩ A n within the same time bound as well. Since we have already derived how to efficiently count roots in (R * ) n and R n + , it suffices to prove that we can count roots on all the proper coordinate subspaces of R n within our stated time bound.By Assertion (3) of Lemma 5.3, min π i (A) < 0 for all i implies that all the roots of F in R n lie in (R * ) n . So, without loss of generality, we can re-order variables and assume min π i (A) < 0 for all i ≥ ℓ + 1 ≥ 2.