#
Counting Real Roots in Polynomial-Time for Systems Supported on Circuits

J. Maurice Rojas<EMAIL_ADDRESS>TAMU 3368, College Station, TX
77843-3368  In memory of Tien-Yien Li, June 28, 1945 – June 25, 2020.

###### Abstract.

Suppose $A\\!=\\!\\{a_{1},\ldots,a_{n+2}\\}\\!\subset\\!\mathbb{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 $n\times 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 time polynomial in $\log(dH)$.

###### Key words and phrases:

sparse polynomial system, real root, positive root, circuit, Baker-Wustholtz
Theorem, Descartes’ Rule, Rolle’s Theorem, Mahler’s Theorem

Partially supported by NSF grant CCF-1900881

##  1\. Introduction

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},\ldots,a_{t}\\}\\!\subset\\!\mathbb{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}\cdots x^{a_{n,j}}_{n}$ and
$f(x)\\!=\\!\sum^{t}_{j=1}c_{j}x^{a_{j}}\\!\in\\!\mathbb{Z}\\!\left[x^{\pm
1}_{1},\ldots,x^{\pm 1}_{n}\right]$, we define the support of $f$ to be
$\mathrm{Supp}(f)\\!:=\\!\\{a_{j}\;|\;c_{j}\\!\neq\\!0\\}$. We then call a
system of the form
$F\\!:=\\!(f_{1},\ldots,f_{n})\\!\in\\!\mathbb{Z}\\!\left[x^{\pm
1}_{1},\ldots,x^{\pm 1}_{n}\right]^{n}$, with
$f_{i}(x)\\!:=\\!\sum^{t}_{j=1}c_{i,j}x^{a_{j}}$ for all $i$ and
$\\#\bigcup^{n}_{i=1}\mathrm{Supp}(f_{i})\\!=\\!t$, a $t$-nomial $n\times n$
system (over $\mathbb{Z}$) supported on $A$. We denote the positive orthant by
$\mathbb{R}^{n}_{+}$ and call a root of $F$ in $\mathbb{R}^{n}_{+}$ a positive
root. We also let $\mathbb{R}^{*}\\!:=\\!\mathbb{R}\setminus\\{0\\}$.

If the $a_{j}$ do not all lie in the same affine hyperplane then we clearly
have $t\\!\geq\\!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 speed-up
for counting the exact number of real roots of $F$ in the special case
$t\\!\leq\\!n+2$.

######  Theorem 1.1.

Following the notation above, assume the coefficient matrix $[c_{i,j}]$ of $F$
is generic and $t\\!\leq\\!n+2$. Then, in time
$O\\!\left(n\log(nd)+n^{2}\log(nH)\right)^{2n+4}$, we can determine the number
of roots of $F$ in $\mathbb{R}^{n}$, ${(\mathbb{R}^{*})}^{n}$, and
$\mathbb{R}^{n}_{+}$. Furthermore, if $t\\!=\\!n+1$, then we can do the same
in time $O\\!\left(n^{3.373}\log^{2}(nH)\right)$.

We prove Theorem 1.1 in Section 5.1, based mainly on Algorithms 4.1 and 4.3
from Section 4. A central ingredient is diophantine approximation.

The genericity condition for counting roots in ${(\mathbb{R}^{*})}^{n}$ and
$\mathbb{R}^{n}_{+}$, when $t\\!=\\!n+2$, is the non-singularity of a
collection of sub-matrices of $[c_{i,j}]$, depending solely on the support of
$F$, and is checkable in time $O\\!\left(n^{3.373}\log^{2}(ndH)\right)$: 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 $\frac{2n^{2}}{2H+1}$. The genericity condition for counting
affine roots is more technical but still holds practically often: probability
$1-\varepsilon$ when $H$ has $\Omega(n\log(d)-\log\varepsilon)$ 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}\\!=\cdots\\!=\\!f_{n}$, is already an open question [BRS09, Bih11].
Furthermore, for any fixed $\varepsilon\\!>\\!0$, deciding whether
$F\\!=\\!(f_{1},\ldots,f_{1})$ has any real (or positive) roots is
${\mathbf{NP}}$-hard already for $t\\!=\\!n+n^{\varepsilon}$ [BRS09].

######  Remark 1.2.

We count roots without multiplicity. In particular, degenerate111roots
yielding a Jacobian with less than full rank. isolated roots are not a
problem, and are counted correctly by our algorithms. $\diamond$

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.

######  Example 1.3.

Consider the $7$-nomial $5\times 5$ system $F\\!=\\!(f_{1},\ldots,f_{5})$
defined by
$\displaystyle\left(2x^{36}_{1}x^{194}_{2}x^{50}_{3}x^{82}_{4}x^{60}_{5}+x^{76}_{1}x^{240}_{2}x^{41}_{4}x_{5}+x^{74}_{1}x^{179}_{2}x^{25}_{3}x^{57}_{5}+x^{25}_{1}x^{203}_{2}x^{44}_{3}x_{4}+x^{20}_{1}x^{167}_{2}x^{64}_{3}x^{12}_{4}x^{68}_{5}-37137cx^{58}_{1}x^{194}_{2}x^{24}_{3}x^{36}_{4}x^{25}_{5}-\text{\scalebox{0.8}[0.8]{$\frac{9}{2}$}}x^{166}_{3}x^{68}_{4}x^{343}_{5},\right.$
$\displaystyle
x^{36}_{1}x^{194}_{2}x^{50}_{3}x^{82}_{4}x^{60}_{5}+2x^{76}_{1}x^{240}_{2}x^{41}_{4}x_{5}+x^{74}_{1}x^{179}_{2}x^{25}_{3}x^{57}_{5}+x^{25}_{1}x^{203}_{2}x^{44}_{3}x_{4}+x^{20}_{1}x^{167}_{2}x^{64}_{3}x^{12}_{4}x^{68}_{5}-24849cx^{58}_{1}x^{194}_{2}x^{24}_{3}x^{36}_{4}x^{25}_{5}-\text{\scalebox{0.8}[0.8]{$\frac{21}{4}$}}x^{166}_{3}x^{68}_{4}x^{343}_{5},$
$\displaystyle
x^{36}_{1}x^{194}_{2}x^{50}_{3}x^{82}_{4}x^{60}_{5}+x^{76}_{1}x^{240}_{2}x^{41}_{4}x_{5}+2x^{74}_{1}x^{179}_{2}x^{25}_{3}x^{57}_{5}+x^{25}_{1}x^{203}_{2}x^{44}_{3}x_{4}+x^{20}_{1}x^{167}_{2}x^{64}_{3}x^{12}_{4}x^{68}_{5}-21009cx^{58}_{1}x^{194}_{2}x^{24}_{3}x^{36}_{4}x^{25}_{5}-\text{\scalebox{0.8}[0.8]{$\frac{21}{4}$}}x^{166}_{3}x^{68}_{4}x^{343}_{5},$
$\displaystyle
x^{36}_{1}x^{194}_{2}x^{50}_{3}x^{82}_{4}x^{60}_{5}+x^{76}_{1}x^{240}_{2}x^{41}_{4}x_{5}+x^{74}_{1}x^{179}_{2}x^{25}_{3}x^{57}_{5}+2x^{25}_{1}x^{203}_{2}x^{44}_{3}x_{4}+x^{20}_{1}x^{167}_{2}x^{64}_{3}x^{12}_{4}x^{68}_{5}-20769cx^{58}_{1}x^{194}_{2}x^{24}_{3}x^{36}_{4}x^{25}_{5}-\text{\scalebox{0.8}[0.8]{$\frac{21}{4}$}}x^{166}_{3}x^{68}_{4}x^{343}_{5},$
$\displaystyle\left.x^{36}_{1}x^{194}_{2}x^{50}_{3}x^{82}_{4}x^{60}_{5}+x^{76}_{1}x^{240}_{2}x^{41}_{4}x_{5}+x^{74}_{1}x^{179}_{2}x^{25}_{3}x^{57}_{5}+x^{25}_{1}x^{203}_{2}x^{44}_{3}x_{4}+2x^{20}_{1}x^{167}_{2}x^{64}_{3}x^{12}_{4}x^{68}_{5}-20754cx^{58}_{1}x^{194}_{2}x^{24}_{3}x^{36}_{4}x^{25}_{5}-\text{\scalebox{0.8}[0.8]{$\frac{21}{4}$}}x^{166}_{3}x^{68}_{4}x^{343}_{5}\right).$
Then Algorithm 4.3 from Section 4 (simulated in a few lines of Maple
code222Using Maple 2019 on a Dell XPS 13 laptop with an Intel core i7-5500u
microprocessor, 8 Gb RAM, and a 256Gb solid state hard-drive, running Ubunu
19.10. Maple code available on request.) tells us in under a second that $F$
has exactly $2$, $6$, $6$, $2$, $2$, or $0$ positive roots, respectively when
$c$ is $\frac{1}{20731}$, $\frac{1}{20730}$, $\frac{1}{14392}$,
$\frac{1}{14391}$, $\frac{1}{13059}$, or $\frac{1}{13058}$. (All roots in
$(\mathbb{R}^{*})^{5}$ of these $F$ happen to lie in $\mathbb{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 non-
degenerate system. Bertini will now exit due to this error.” This is partially
because each of our $F$ has333 Via Kushnirenko’s Theorem [Kus77, Roj03],
Ioannis Emiris’ MixVol code [Emi20], and a simple check that the underlying
facial systems have no roots in $(\mathbb{C}^{*})^{5}$. over $245$ million
roots in $(\mathbb{C}^{*})^{5}$, and older polynomial system solving
techniques have complexity super-linear, or worse, in the number of complex
roots. $\diamond$

######  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\times
n$ systems [HS95, Ver10, LL11], $(n+2)$-nomial $n\times 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
${(\mathbb{R}^{*})}^{n}$) is important, such cases are provably rare when the
coefficients are random. $\diamond$

There has been growing interest in generalizing Descartes’ Rule of Signs (see,
e.g., [SL54, Gra99]) from univariate polynomials to $n\times n$ polynomial
systems. This began withKhovanski’s seminal Theorem on Real Fewnomials [Kho91]
which, in our notation, asserted an upper bound of
$\displaystyle{2^{\binom{t}{2}}(n+1)^{t}}$ for the number of non-degenerate
positive roots of any $t$-nomial $n\times 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
isolated444even allowing degenerate isolated roots positive roots for $2\times
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 $\mathbb{R}^{n}_{+}$ (resp.
${(\mathbb{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
$\displaystyle{\frac{e^{2}+3}{4}2^{\binom{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
$\displaystyle{\frac{1}{2^{n-1}}\cdot\frac{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 $\\#\mathbf{P}$-hardness, already for
$n\times 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 ${(\mathbb{R}^{*})}^{n}$ instead of
$\mathbb{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\times n$ sub-
determinants of the coefficient matrix $[c_{i,j}]$ and the matroidal structure
of $\mathcal{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\\!\geq\\!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 $\mathcal{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 $\mathbb{R}^{n}$, for generic systems over $\mathbb{Z}$ supported
on circuits555…not to be confused with the circuits from complexity theory
(which are layered directed graphs with specially labelled nodes having
additional structure). See Section 2.3., 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.
$\diamond$

##  2\. Background

###  2.1. The Complexity of Linear Algebra over $\mathbb{Z}$

Let $\omega$ denote the well-known matrix multiplication exponent, i.e., the
infimum over all $\omega$ such that there exists an algorithm that can
multiply an arbitrary pair of $n\times n$ matrices, in any field $K$, using
$O(n^{\omega})$ field operations in $K$. The best current upper bound is
$\omega\\!<\\!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 $\frac{p}{q}$ with
$p,q\\!\in\\!\mathbb{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\\!\in\\!\mathbb{Z}^{n\times n}$ with
determinant $\pm 1$ unimodular. Given any matrix
$M\\!\in\\!\mathbb{Z}^{n\times t}$, we then call any identity of the form
$UM\\!=\\!R$, with $U\\!\in\\!\mathbb{Z}^{n\times 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\\!\in\\!\mathbb{Z}^{n\times n}$ and $V\\!\in\\!\mathbb{Z}^{t\times t}$ both
unimodular, and $S$ with diagonal entries $s_{1},\ldots,s_{n}$ satisfying
$s_{1}|s_{2},\ldots,s_{n-1}|s_{n}$, a Smith factorization of $M$. $\diamond$

######  Lemma 2.2.

Suppose $M\\!\in\\!\mathbb{Z}^{n\times t}$ with $t\\!\geq\\!n$ and all entries
having absolute value at most $H$. Then, in time
$O\\!\left(tn^{\omega}\log^{2}(nH)\right)$, we can row-reduce $M$ to reduced
row echelon form $R\\!\in\\!\mathbb{Q}^{n\times t}$ with every nonzero entry
of $R$ having logarithmic height $O(n\log(nH))$. $\blacksquare$

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 $\mathbb{Z}^{n\times 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 $\mathcal{A}\\!\in\\!\mathbb{Z}^{n\times(n+1)}$ has rank $n$ and the
entries of the $i$th row of $\mathcal{A}$ have absolute value at most $d_{i}$,
then any generator
$(b_{1},\ldots,b_{n+1})^{\top}\\!\in\\!\mathbb{Z}^{(n+1)\times 1}$ of the
right-null space of $\mathcal{A}$, with $\gcd(b_{1},\ldots,b_{n+1})\\!=\\!1$,
satisfies $|b_{j}|\\!\leq\\!n^{n/2}\prod\limits^{n}_{i=1}d_{i}$ for all $j$.
$\blacksquare$

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

######  Theorem 2.4.

[Sto00, Ch. 8] Suppose $M\\!\in\\!\mathbb{Z}^{n\times k}$ (with
$k\\!\leq\\!n$) has all entries of absolute value at most $d$. Then a Smith
factorization $UMV\\!=\\!S$ for $M$ can be found in time
$O\\!\left(kn^{\omega}\log^{2}(nd)\right)$, with all the entries of $U,V,S$
having logarithmic height $O(n\log(nd))$. $\blacksquare$

###  2.2. Binomial and $(n+1)$-nomial Systems over ${(\mathbb{R}^{*})}^{n}$

A simple, folkloric algebraic/analytic

fact we’ll need is the following:

######  Proposition 2.5.

Suppose $\mathcal{A},\mathcal{B}\\!\in\\!\mathbb{Z}^{n\times n}$ and
$x\\!=\\!(x_{1},\ldots,x_{n})$ is a vector of indeterminates. Let us define
$x^{\mathcal{A}}$ to be the vector of monomials $\left(x^{a_{1,1}}_{1}\cdots
x^{a_{n,1}}_{n},\ldots,x^{a_{1,n}}_{1}\cdots x^{a_{n,n}}_{n}\right)$, where
$\mathcal{A}\\!=\\![a_{i,j}]$. Then
$(x^{\mathcal{A}})^{\mathcal{B}}\\!=\\!x^{\mathcal{A}\mathcal{B}}$ and, if
$\mathcal{A}$ is unimodular, the function defined by $x\mapsto
x^{\mathcal{A}}$ defines  an analytic group automorphism of
${(\mathbb{C}^{*})}^{n}$ that restricts to an analytic group automorphism of
$\mathbb{R}^{n}_{+}$. $\blacksquare$

######  Remark 2.6.

A simple consequence of Proposition 2.5 is that if
$f\\!\in\\!\mathbb{R}\\!\left[x^{\pm 1}_{1},\ldots,x^{\pm 1}_{n}\right]$ 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}\\!\in\\!\mathbb{R}\\!\left[y^{\pm 1}_{1},\ldots,y^{\pm 1}_{d}\right]$,
such that
$g(y)\\!:=\\!y^{b}f\\!\left(y^{U}\right)\\!\in\\!\mathbb{R}\\!\left[y^{\pm
1}_{1},\ldots,y^{\pm 1}_{d}\right]$ is a $d$-variate $t$-nomial, and the zero
set of $f$ in ${(\mathbb{R}^{*})}^{n}$ is analytically isomorphic to the
Cartesian product  of $(\mathbb{R}^{*})^{n-d}$ and the zero set of $g$ in
$(\mathbb{R}^{*})^{d}$. So $A$ in an affine hyperplane implies that the zero
set of $f$ in ${(\mathbb{R}^{*})}^{n}$ can be easily characterized by the zero
set of another $t$-nomial in fewer variables. $\diamond$

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},\ldots,c_{n})\\!\in\\!{(\mathbb{R}^{*})}^{n}$,
$a_{1},\ldots,a_{n}\\!\in\\!\mathbb{Z}^{n}$, $\mathcal{A}$ is the $n\times n$
matrixwith $j$th column $a_{j}$ for all $j$, $U\mathcal{A}V\\!=\\!S$ is a
Smith factorization of $\mathcal{A}$, and
$c^{\prime}\\!:=\\!\left(c^{\prime}_{1},\ldots,c^{\prime}_{n}\right)\\!:=\\!c^{V}$.
Let $s_{j}$ be the $(j,j)$ entry of $S$. Then
$G\\!:=\\!(x^{a_{1}}-c_{1},\ldots,x^{a_{n}}-c_{n})$ and
$\left(y^{s_{1}}_{1}-c^{\prime}_{1},\ldots,y^{s_{n}}_{n}-c^{\prime}_{n}\right)$
have the same number of roots in $\mathbb{R}^{n}_{+}$ (resp.
${(\mathbb{R}^{*})}^{n}$, ${(\mathbb{C}^{*})}^{n}$). In particular, $G$ has
exactly $0$, $1$, or infinitely many roots in $\mathbb{R}^{n}_{+}$ under the
following respective conditions:
$0$: Some $c_{i}$ is negative or [$\mathrm{Rank}(\mathcal{A})\\!=\\!j\\!<\\!n$
and $c^{\prime}_{i}\\!\neq\\!1$ for some $i\\!\in\\!\\{j+1,\ldots,n\\}$].
$1$: $c\\!\in\\!\mathbb{R}^{n}_{+}$ and $\det\mathcal{A}\\!\neq\\!0$.
$\infty$: $c\\!\in\\!\mathbb{R}^{n}_{+}$,
$\mathrm{Rank}(\mathcal{A})\\!=\\!j\\!<\\!n$, and
$c^{\prime}_{j+1}\\!=\cdots=\\!c^{\prime}_{n}\\!=\\!1$. $\blacksquare$

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 ${(\mathbb{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},\ldots,a_{n}$ are linearly independent. Let $r$ denote the rank, over
the field $\mathbb{F}_{2}$, of the mod $2$ reduction of $\mathcal{A}$. Also
let $\overline{V}$ denote the upper $r\times n$ sub-matrix of $V$. Then the
map $m:{(\mathbb{R}^{*})}^{n}\longrightarrow{(\mathbb{R}^{*})}^{n}$ defined by
$m(x)\\!:=\\!x^{\mathcal{A}}$ is $2^{n-r}$-to-$1$, and the $i$th coordinate of
its range is $\mathbb{R}^{*}$ (resp. $\mathbb{R}_{+}$) if and only if some
(resp. no) entry of the $i$th column of $\overline{V}$ is odd. In particular,
$F$ has exactly $0$ (resp. $2^{n-r}$) roots in ${(\mathbb{R}^{*})}^{n}$ if and
only if $c^{\prime}_{i}\\!<\\!0$ for some (resp. no) $i\\!\geq\\!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},\ldots,s_{r}$ are odd
and $s_{r+1},\ldots,s_{n}$ are even. By Proposition 2.5, exponentiating by $U$
or $V$ induces a permutation of the open orthants of $\mathbb{R}^{n}$. In
particular, we see that the range of $x\mapsto x^{S}$ is exactly
$(\mathbb{R}^{*})^{r}\times\mathbb{R}^{n-r}_{+}$. So the pre-image assertion
on $m$ is proved.

Now note that the range of $m$ must be
$\left((\mathbb{R}^{*})^{r}\times\mathbb{R}^{n-r}_{+}\right)^{V}$. Since the
sign of $\varepsilon^{v_{i,j}}_{j}$ depends only on the parity of $v_{i,j}$
and the sign of $\varepsilon_{j}$, we then see that the $i$th coordinate of
the range of $m$ is $\mathbb{R}^{*}$ (resp. $\mathbb{R}_{+}$) if and only if
some (resp. no) entry of $\\{v_{1,i},\ldots,v_{r,i}\\}$ is odd. So now we know
the range of $m$.

The final remaining assertion follows from our earlier definition
$c^{\prime}\\!:=\\!c^{V}$ and our earlier assumption that
$c\\!\in\\!{(\mathbb{R}^{*})}^{n}$. $\blacksquare$

######  Remark 2.9.

It is important to remember that counting affine roots of $n\times n$ binomial
systems, with arbitrary exponents and $n$ varying, is in fact
$\\#\mathbf{P}$-complete [CD07]. This implies, for instance, that polynomial-
time root counting in $\mathbb{R}^{n}$ for systems of the form
$(x^{\alpha_{1}}f_{1},\ldots,x^{\alpha_{n}}f_{n})$ — with
$F\\!=\\!(f_{1},\ldots,f_{n})$ an $(n+1)$-nomial $n\times n$ system and
$\alpha_{1},\ldots,\alpha_{n}\\!\in\\!(\mathbb{N}\cup\\{0\\})^{n}$ — would
imply $\mathbf{P}\\!=\\!{\mathbf{NP}}$. In particular, our restriction to
$n\times n$ systems with union of supports having cardinality $\leq\\!n+2$ is
critical if we are to have any hope of someday counting affine roots in
$\mathbf{P}$. $\diamond$

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

######  Lemma 2.10.

If $F\\!=\\!(f_{1},\ldots,f_{n})\\!\in\\!\mathbb{Z}\\!\left[x^{\pm
1}_{1},\ldots,x^{\pm 1}_{n}\right]^{n}$ is an $(n+1)$-nomial $n\times n$
system, with union of supports $A\\!=\\!\\{a_{1},\ldots,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+\omega}\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
${(\mathbb{R}^{*})}^{n}$ (Corollary 2.12 below) has complexity dependent on
$A$. $\diamond$

Proof of Lemma 2.10: By our assumption on the coefficient matrix, we may
reorder monomials so that the left-most $n\times 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 ${(\mathbb{C}^{*})}^{n}$,
and assume $a_{1},\ldots,a_{n}$ are linearly independent and
$a_{n+1}\\!=\\!\mathbf{O}$.

From Lemma 2.2 it is then clear that we can reduce the coefficient matrix of
$F$, $[c_{i,j}]\\!\in\\!\mathbb{Z}^{n\times(n+1)}$, to a reduced row echelon
form in $\mathbb{Q}^{n\times(n+1)}$, in time $O(n^{1+\omega}\log^{2}(nH))$.
The underlying linear combinations of rows can then be applied to the
equations $f_{i}\\!=\\!0$ so that $F\\!=\\!\mathbf{O}$ can be reduced to a
binomial system of the form $x^{\mathcal{A}}\\!=\\!\gamma$ where
$\gamma\\!=\\!(\gamma_{1},\ldots,\gamma_{n})$,
$\mathcal{A}\\!\in\\!\mathbb{Z}^{n\times n}$, and the solutions of
$x^{\mathcal{A}}\\!=\\!\gamma$ in ${(\mathbb{C}^{*})}^{n}$ are the same as the
roots of $F$ in ${(\mathbb{C}^{*})}^{n}$.

Clearly then, $\gamma_{i}\\!\leq\\!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+\omega}\log^{2}(nH))$.

So $\gamma\\!\in\\!\mathbb{R}^{n}_{+}$ implies that $F$ has exactly $1$
positive root by Proposition 2.7, and we are done. $\blacksquare$

A simple consequence of our development so far is a method to efficiently
count roots in $(\mathbb{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 ${(\mathbb{R}^{*})}^{n}$ is either $0$ or $2^{n-r}$, where
$r$ is the rank, over the field $\mathbb{F}_{2}$, of the mod $2$ reduction of
$\mathcal{A}$. In particular, we can determine the number of roots of $F$ in
${(\mathbb{R}^{*})}^{n}$ in time $O(n^{1+\omega}\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\times 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
${(\mathbb{R}^{*})}^{n}$: We merely need to check the signs of
$\gamma^{\prime}_{r+1},\ldots,\gamma^{\prime}_{n}$ where
$\gamma^{\prime}\\!:=\\!\gamma^{V}$ and $U\mathcal{A}V\\!=\\!S$ is a Smith
factorization of $\mathcal{A}$. More precisely, instead of computing
$\gamma^{V}$, we compute $\mathrm{sign}(\gamma)^{(V\text{ 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 $\mathcal{A}$ via,
say, Theorem 2.4. So our final complexity bound is
$O(n^{1+\omega}\log^{2}(nH)+n^{1+\omega}\log(dH))$, which is clearly bounded
from above by our stated bound. $\blacksquare$

###  2.3. Circuits, $(n+2)$-nomial systems, and Gale Dual Form with Heights

We now show how to reduce root counting in ${(\mathbb{R}^{*})}^{n}$ for $F$ to
root counting in certain sub-intervals of $\mathbb{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},\ldots,a_{m+2}\\}\\!\subset\\!\mathbb{R}^{n}$ with
$\\#A\\!=\\!m+2$ a circuit if and only if the $(n+1)\times(m+2)$ matrix
$\widehat{\mathcal{A}}$ with $j$th column $\begin{bmatrix}1\\\
a_{j}\end{bmatrix}$ has right nullspace of dimension one. In which case, we
call any generator $b\\!\in\\!\mathbb{Z}^{(m+2)\times
1}\setminus\\{\mathbf{O}\\}$ for the right nullspace of
$\widehat{\mathcal{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. $\diamond$

Note that all circuit relations for a fixed circuit (other than the trivial
relation $\mathbf{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},\ldots,a_{m+2}\\}\\!\subset\\!\mathbb{Z}^{n}$
has a unique subset $\Sigma\\!=\\!\\{a_{i_{1}},\ldots,a_{i_{\ell+2}}\\}$ with
$\Sigma$ a non-degenerate circuit of cardinality $\ell+2$. In particular,
$\\{i_{1},\ldots,i_{\ell+2}\\}$ is exactly the set of indices of the nonzero
coordinates of any (non-trivial) circuit relation for $A$. Furthermore, if
$J\\!\subseteq\\!\\{i_{1},\ldots,i_{\ell+2}\\}$ and $\sum_{j\in
J}a_{j}\\!=\\!\mathbf{O}$, then $J\\!=\\!\\{i_{1},\ldots,i_{\ell+2}\\}$.
$\blacksquare$

We call $\Sigma$ the unique non-degenerate sub-circuit of $A$. Note that any
$A\\!=\\!\\{a_{1},\ldots,a_{n+2}\\}\\!\subset\\!\mathbb{Z}^{n}$ with
cardinality $n+2$, and $A$ not lying in any affine hyperplane, is a circuit.

######  Example 2.15.

It is easily checked that $A\\!=$ $\left\\{\begin{bmatrix}0\\\ 0\\\ 0\\\
0\end{bmatrix},\begin{bmatrix}1\\\ 0\\\ 0\\\
0\end{bmatrix},\begin{bmatrix}2\\\ 0\\\ 0\\\
0\end{bmatrix},\begin{bmatrix}0\\\ 1\\\ 0\\\
0\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 1\\\
0\end{bmatrix},\begin{bmatrix}0\\\ 0\\\ 0\\\ 1\end{bmatrix}\right\\}$
$\subset\\!\mathbb{R}^{4}$ is a degenerate circuit, and that letting $\Sigma$
consist of the first $3$ points of $A$ yields the unique non-degenerate sub-
circuit of $A$. In particular, $\Sigma$ has the same minimal circuit relation
(up to sign) as the non-degenerate circuit $\\{0,1,2\\}$ in $\mathbb{R}^{1}$.
$\diamond$

######  Lemma 2.16.

Suppose $F\\!=\\!(f_{1},\ldots,f_{n})\\!\in\\!\mathbb{Z}\\!\left[x^{\pm
1}_{1},\ldots,x^{\pm 1}_{n}\right]^{n}$ is an $(n+2)$-nomial $n\times n$
system

supported on a circuit $A\\!=\\!\\{a_{1},\ldots,a_{n+2}\\}$ with unique non-
degenerate sub-circuit $\Sigma=$$\\{a_{1},\ldots,a_{m},a_{n+1},a_{n+2}\\}$ and
all coordinates of the $a_{j}$ have absolute value at most $d$. Suppose also
that $F$ has coefficient matrix
$[c_{i,j}]\\!\in\\!\\{-H,\ldots,H\\}^{n\times(n+2)}$ with all $n\times n$ sub-
matrices of  $\begin{bmatrix}c_{1,1}&\cdots&c_{1,n}&c_{1,n+2}\\\
\vdots&\ddots&\vdots\\\ c_{n,1}&\cdots&c_{n,n}&c_{n,n+2}\end{bmatrix}$ non-
singular and  $\begin{bmatrix}c_{i,n+1}&c_{i,n+2}\\\
c_{j,n+1}&c_{j,n+2}\end{bmatrix}$ non-singular for all $i\\!\neq\\!j$. Then in
time $O\\!\left(n^{1+\omega}\log^{2}(ndH)\right)$, we can give either a true
declaration that $F$ has no positive roots, or find rational numbers
$\gamma_{1,0},\gamma_{1,1},\ldots,\gamma_{n+1,0},\gamma_{n+1,1}$ and nonzero
integers $b_{1},\ldots,b_{m+1}$ (with $1\\!\leq\\!m\\!\leq\\!n$) satisfying
the following properties:
1\. The number of roots of the function
$L(u)\\!:=\\!\sum^{m+1}_{i=1}b_{i}\log|\gamma_{i,1}u+\gamma_{i,0}|$ in the
open interval
$I\\!:=\\!\\{u\\!\in\\!\mathbb{R}\;|\;\gamma_{i,1}u+\gamma_{i,0}\\!>\\!0\text{
for all }i\\!\in\\!\\{1,\ldots,n+1\\}\\}$ is exactly the number of positive
roots of $F$.
2\. $I$ is non-empty and, for each $i\\!\in\\!\\{1,\ldots,n+1\\}$, we have
$\max\\{\gamma_{i,1},\gamma_{i,0}\\}\\!>\\!0$.
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(\gamma_{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\\!=\\!\mathbf{O}$ to the following system having the same roots in
$(\mathbb{R}^{*})^{5}$:
$\displaystyle x^{36}_{1}x^{194}_{2}x^{-116}_{3}x^{14}_{4}x^{-283}_{5}\hskip
284.52756pt$ $\displaystyle=$ $\displaystyle
16384cx^{58}_{1}x^{194}_{2}x^{-142}_{3}x^{-32}_{4}x^{-318}_{5}+\frac{1}{4}$
$\displaystyle\mbox{}\hskip
71.13188ptx^{76}_{1}x^{240}_{2}x^{-166}_{3}x^{-27}_{4}x^{-342}_{5}\hskip
213.39566pt$ $\displaystyle=$ $\displaystyle\hskip
5.69046pt4096cx^{58}_{1}x^{194}_{2}x^{-142}_{3}x^{-32}_{4}x^{-318}_{5}+1$
$\displaystyle\mbox{}\hskip
142.26378ptx^{74}_{1}x^{179}_{2}x^{-141}_{3}x^{-68}_{4}x^{-286}_{5}\hskip
142.26378pt$ $\displaystyle=$ $\displaystyle\hskip
11.38092pt256cx^{58}_{1}x^{194}_{2}x^{-142}_{3}x^{-32}_{4}x^{-318}_{5}+1$
$\displaystyle\mbox{}\hskip
213.39566ptx^{25}_{1}x^{203}_{2}x^{-122}_{3}x^{-67}_{4}x^{-343}_{5}\hskip
71.13188pt$ $\displaystyle=$ $\displaystyle\hskip
17.07182pt16cx^{58}_{1}x^{194}_{2}x^{-142}_{3}x^{-32}_{4}x^{-318}_{5}+1$
$\displaystyle\mbox{}\hskip
284.52756ptx^{20}_{1}x^{167}_{2}x^{-102}_{3}x^{-56}_{4}x^{-275}_{5}$
$\displaystyle=$ $\displaystyle\hskip
28.45274ptcx^{58}_{1}x^{194}_{2}x^{-142}_{3}x^{-32}_{4}x^{-318}_{5}+1$
Note in particular that this new system clearly reveals that all the roots of
$F$ in $(\mathbb{R}^{*})^{5}$ (for our earlier chosen values of $c$) must in
fact lie in $\mathbb{R}^{5}_{+}$, since the right-hand sides are all positive
on $(\mathbb{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)^{\top}$. 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\left|16384cu+\frac{1}{4}\right|+2\log\left|4096cu+1\right|-2\log\left|256cu+1\right|+2\log\left|16cu+1\right|-2\log|cu+1|+\log|u|$.
In particular, for any $c\\!>\\!0$, the number of roots of $L$ in
$I\\!=\\!\mathbb{R}_{+}$ is the same as the number of roots of $F$ in
$\mathbb{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\\!\in\\!\left[\frac{1}{20730},\frac{1}{14392}\right]$. A more realistic
example of coefficient growth can be found in Example 2.22 below (see also
Example 3.2 from Section 3). $\diamond$

######  Example 2.18.

The stated indexing of the non-degenerate sub-circuit $\Sigma$ 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\times 3$
system $(x_{2}-1,x_{1}x_{2}-x_{3}-1,x^{2}_{1}x_{2}-x_{3}-1)$, with union of
supports ordered so that $a_{4}\\!=\\!(0,0,1)^{\top}$ and
$a_{5}\\!=\\!(0,0,0)^{\top}$, has $[c_{i,j}]^{3}_{i,j=1}$ non-singular (among
other $3\times 3$ sub-matrices), but infinitely many positive roots:
$(1+t,1,t)$ for all $t\\!\in\\!\mathbb{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
$\\{(0,1,0)^{\top},(1,1,0)^{\top},(2,1,0)^{\top}\\}$. $\diamond$

Proof of Lemma 2.16: We can divide $f_{1},\ldots,f_{n}$ by $x^{a_{n+2}}$
without affecting the positive roots of $F$. So we may assume
$a_{n+2}\\!=\\!\mathbf{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\times n$ sub-matrices of $[c_{i,j}]$, to reduce
$F\\!=\\!\mathbf{O}$ to a system of equations of the form
$G\\!=\\!\mathbf{O}$, having the same solutions in $\mathbb{R}^{n}$ as $F$,
where $G\\!:=\\!(g_{1},\ldots,g_{n})$,

$\displaystyle g_{i}(x)$ $\displaystyle=$ $\displaystyle
x^{a_{i}}-\gamma_{i,1}x^{a_{n+1}}-\gamma_{i,0}\text{ for all }i,$

the $\gamma_{i,j}$ have logarithmic height $O(n\log(nH))$, and this reduction
takes time just $O\\!\left(n^{1+\omega}\log^{2}(nH)\right)$.

To complete our notation, let us set $\gamma_{n+1,1}\\!:=\\!1$ and
$\gamma_{n+1,0}\\!:=\\!0$.

Clearly, if there is an $i$ such that both $\gamma_{i,0}$ and $\gamma_{i,1}$
are non-positive, then $G$ (and thus $F$) has no positive roots, and we can
simply stop, having spent time just
$O\\!\left(n^{1+\omega}\log^{2}(nH)\right)$. So we may assume the following:

(1) $\displaystyle\text{For each }i\\!\in\\!\\{1,\ldots,n+1\\}\text{ we have
}\max\\{\gamma_{i,1},\gamma_{i,0}\\}\\!>\\!0.$

We can easily check whether $I$ is non-empty after sorting the (possibly
infinite) numbers $-\gamma_{i,0}/\gamma_{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\\!\left(n^{1+\omega}\log^{2}(nH)\right)$).
So we may also assume the following:

(2) $\displaystyle I\text{ is non-empty.}$

We now establish Assertions (1)–(4) via $G$ and $\Sigma$: First let
$b\\!\in\\!\mathbb{Z}^{(m+2)\times 1}$ be the unique (up to sign) minimal
circuit relation of $\Sigma$. Note that the coordinates of $b$ are of
logarithmic height $O(m\log(mH))$, and the computation of $b$ takes time
$O\\!\left(mn^{\omega}\log^{2}(nd)\right)$, thanks to Lemmata 2.2 and 2.3.

Observe that any root $\zeta\\!\in\\!{(\mathbb{R}^{*})}^{n}$ of $G$ must
satisfy

(3)

So let
$P(u)\\!:=\\!(\gamma_{1,1}u+\gamma_{1,0})^{b_{1}}\cdots(\gamma_{m,1}u+\gamma_{m,0})^{b_{m}}u^{b_{m+1}}-1$.
Note that
$n\\!=\\!1\Longrightarrow(\gamma_{1,1},\gamma_{1,0})\\!=\\!(-c_{2}/c_{1},-c_{3}/c_{1})\\!\in\\!(\mathbb{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\\!\geq\\!2$. By Cramer’s Rule, and our assumption on the
$n\times n$ sub-matrices of $[c_{i,j}]$, we have $\gamma_{i,0}\\!\neq\\!0$ for
all $i$. If $m\\!=\\!1$ then we have that $P$ is a non-constant real rational
function since $b_{m+1}\\!\neq\\!0$ (thanks to $\Sigma$ 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\\!\geq\\!2$.

By our assumption on the rightmost $2\times 2$ minors of $[c_{i,j}]$, we see
that $\gamma_{i,1}\\!\neq\\!0$ for some $i\\!\in\\!\\{1,\ldots,m\\}$, and thus
$P$ must have $-\gamma_{i,0}/\gamma_{i,1}$ ($\neq\\!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 $\zeta\\!\in\\!\mathbb{R}^{n}_{+}$ of $F$ yields
$\zeta^{a_{n+1}}\\!\in\\!I$ as a root of $P$ by Equation (3). Moreover, by
Proposition 2.5, any root $\zeta^{\prime}\\!\in\\!\mathbb{R}^{n}_{+}$ of $F$
with $(\zeta^{\prime})^{a_{n+1}}\\!=\\!\zeta^{a_{n+1}}$ must satisfy
$\zeta^{\prime}\\!=\\!\zeta$, 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},\ldots,a_{n}$ are linearly independent, thanks to
$\\{a_{n+1},\mathbf{O}\\}\\!\subset\\!\Sigma$ and $A$ being a circuit.) So $P$
has at least as many roots in $I$ as $F$ has in $\mathbb{R}^{n}_{+}$.

Conversely, Proposition 2.5 tells us that any root $u\\!\in\\!I$ of $P$ yields
a unique $\zeta\\!\in\\!\mathbb{R}^{n}_{+}$ satisfying
$\left(\zeta^{a_{1}},\ldots,\zeta^{a_{n}}\right)\\!=\\!(\gamma_{1,1}u+\gamma_{1,0},\ldots,\gamma_{n,1}u+\gamma_{n,0})$.
Recall that $b_{m+1}\\!\neq\\!0$. So we also obtain
$\zeta^{a_{n+1}}=\left((\gamma_{1,1}u+\gamma_{1,0})^{-b_{1}}\cdots(\gamma_{m,1}u+\gamma_{m,0})^{-b_{m}}\right)^{1/b_{m+1}}\\!=\\!u^{b_{m+1}/b_{m+1}}\\!=\\!u$
by the definition of $P$. So $\zeta$ is in fact a root of $G$. Similarly, a
root $u^{\prime}\\!\in\\!I$ of $P$ with $u^{\prime}\\!\neq\\!u$ would yield a
positive root of
$\left((\zeta^{\prime})^{a_{1}},\ldots,(\zeta^{\prime})^{a_{n}}\right)\\!=\\!(\gamma_{1,1}u^{\prime}+\gamma_{1,0},\ldots,\gamma_{n,1}u^{\prime}+\gamma_{n,0})$
with $(\zeta^{\prime})^{a_{n+1}}\\!\neq\\!\zeta^{a_{n+1}}$ and thus a root
$\zeta^{\prime}\\!\neq\\!\zeta$ of $F$. So $F$ has at least as many roots in
$\mathbb{R}^{n}_{+}$ as $P$ has in $I$.

Observing that $P(u)\\!=\\!0\Longleftrightarrow L(u)\\!=\\!0$ (for
$u\\!\in\\!I$), and recalling Assumptions (1) and (2), we thus obtain
Assertions (1)–(4). Noting that $m\\!\leq\\!n$, we are done. $\blacksquare$

Our sub-matrix condition from Lemma 2.16 in fact holds for a large fraction of
integer coefficients:

######  Corollary 2.19.

The fraction of matrices $[c_{i,j}]\\!\in\\!\\{-H,\ldots,H\\}^{n\times(n+2)}$
with all $n\times n$ sub-matrices of
$\begin{bmatrix}c_{1,1}&\cdots&c_{1,n}&c_{1,n+2}\\\ \vdots&\ddots&\vdots\\\
c_{n,1}&\cdots&c_{n,n}&c_{n,n+2}\end{bmatrix}$ non-singular and
$\begin{bmatrix}c_{i,n+1}&c_{i,n+2}\\\ c_{j,n+1}&c_{j,n+2}\end{bmatrix}$ non-
singular for all $i\\!\neq\\!j$ is at least $1-\frac{2n^{2}}{2H+1}$. Also, the
fraction of matrices $[c_{i,j}]\\!\in\\!\\{-H,\ldots,H\\}^{n\times(n+1)}$ with
leftmost $n\times n$ sub-matrix non-singular is at least $1-\frac{n}{2H+1}$.

Proof: Schwartz’s Lemma [Sch80] is a classic result that tells us that if
$f\\!\in\\!\mathbb{C}[z_{1},\ldots,z_{n}]$ has degree $d$ and
$S\\!\subset\\!\mathbb{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\times
n$ sub-determinants of $[c_{i,j}]$ and $\binom{n}{2}$ many $2\times 2$ sub-
determinants of $[c_{i,j}]$. The resulting polynomial clearly has degree
$(n+1)n+\frac{n(n-1)}{2}\cdot 2\\!=\\!2n^{2}$. Taking
$S\\!=\\!\\{-H,\ldots,H\\}$ and applying Schwartz’s Lemma, we obtain our first
bound. Our second bound follows almost identically, just considering one
determinant instead. $\blacksquare$

Recall that a critical point of a function
$L:\mathbb{R}\longrightarrow\mathbb{R}$ is a root of the derivative
$L^{\prime}$.

######  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}\\!<\cdots<\\!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$i\\!\in\\!\\{0,\ldots,k-1\\}$ such that $\left(\lim_{u\rightarrow
u^{+}_{i}}L(u)\right)\left(\lim_{u\rightarrow
u^{-}_{i+1}}L(u)\right)\\!<\\!0$, plus the number of degenerate roots of $L$
in $I$.

Proof: It is clear that $L$ is strictly monotonic on any open sub-interval
$(u_{i},u_{i+1})$ of $I$. So the image of $(u_{i},u_{i+1})$ under $L$ is
$L_{i}\\!:=\\!\left(\min\left\\{\lim_{u\rightarrow
u^{+}_{i}}L(u),\lim_{u\rightarrow
u^{-}_{i+1}}L(u)\right\\},\max\left\\{\lim_{u\rightarrow
u^{+}_{i}}L(u),\lim_{u\rightarrow u^{-}_{i+1}}L(u)\right\\}\right)$,
and we see by the Intermediate Value Theorem that $L_{i}$ does not contain
$0\Longleftrightarrow[\lim_{u\rightarrow u^{+}_{i}}L(u)$ and
$\lim_{u\rightarrow u^{-}_{i+1}}L(u)$ are both non-positive or both non-
negative$]$. So by Lemma 2.16, we are done. $\blacksquare$

We can now state analogues of Lemma 2.16 and Proposition 2.20 for roots in
${(\mathbb{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}\\!=\\!\mathbf{O}$, and let
$\mathcal{A}\\!:=\\![a_{1},\ldots,a_{n}]$. Let $U\mathcal{A}V\\!=\\!S$ be a
Smith factorization of $\mathcal{A}$, and $r$ the rank, over the field
$\mathbb{F}_{2}$, of the mod $2$ reduction of $\mathcal{A}$. Also, for any
$u\\!\in\\!\mathbb{R}$, let
$\varepsilon_{i}\\!:=\\!\mathrm{sign}(\gamma_{i,1}u+\gamma_{i,0})$,
$\Lambda(u)\\!:=\\!\prod\limits^{m}_{i=1}\varepsilon^{b_{i}\mathrm{mod}\;2}_{i}$,
and
$(\Gamma^{\prime}_{1}(u),\ldots,\Gamma^{\prime}_{n}(u))\\!:=\\!(\varepsilon_{1},\ldots,\varepsilon_{n})^{V\mathrm{mod}\;2}$.
Then the number of roots of $F$ in ${(\mathbb{R}^{*})}^{n}$ is exactly
$2^{n-r}$ times the number of roots $u\\!\in\\!\mathbb{R}$ of $L$ satisfying
both $\Lambda(u)\\!=\\!\mathrm{sign}(u)$ and
$\Gamma^{\prime}_{r+1}(u),\ldots,\Gamma^{\prime}_{n}(u)\\!>\\!0$.

######  Example 2.22.

Consider the $6$-nomial $4\times 4$ system $F\\!=\\!(f_{1},\ldots,f_{4})$
defined by

$\displaystyle\left(-12x^{8}_{1}x^{18}_{2}x^{16}_{4}-5x^{4}_{1}x_{2}x^{3}_{3}x^{8}_{4}+17x^{11}_{1}x^{19}_{2}x_{3}x^{17}_{4}-4x^{11}_{1}x^{9}_{2}x^{14}_{3}+2x^{18}_{2}x^{13}_{3}x^{17}_{4}+3x^{5}_{1}x^{14}_{3}x^{16}_{4},\right.$
$\displaystyle-9x^{8}_{1}x^{18}_{2}x^{16}_{4}+14x^{4}_{1}x_{2}x^{3}_{3}x^{8}_{4}-8x^{11}_{1}x^{19}_{2}x_{3}x^{17}_{4}+3x^{11}_{1}x^{9}_{2}x^{14}_{3}+12x^{18}_{2}x^{13}_{3}x^{17}_{4}-x^{5}_{1}x^{14}_{3}x^{16}_{4},$
$\displaystyle
5x^{8}_{1}x^{18}_{2}x^{16}_{4}+4x^{4}_{1}x_{2}x^{3}_{3}x^{8}_{4}+11x^{11}_{1}x^{19}_{2}x_{3}x^{17}_{4}-16x^{11}_{1}x^{9}_{2}x^{14}_{3}+18x^{18}_{2}x^{13}_{3}x^{17}_{4}-19x^{5}_{1}x^{14}_{3}x^{16}_{4},$
$\displaystyle\left.-x^{8}_{1}x^{18}_{2}x^{16}_{4}+2x^{4}_{1}x_{2}x^{3}_{3}x^{8}_{4}+11x^{11}_{1}x^{19}_{2}x_{3}x^{17}_{4}-17x^{11}_{1}x^{9}_{2}x^{14}_{3}-14x^{18}_{2}x^{13}_{3}x^{17}_{4}-6x^{5}_{1}x^{14}_{3}x^{16}_{4}\right).$

Proceeding as in Lemmata 2.16 and 2.21, we see that Gauss-Jordan elimination
on the coefficient matrix, and computing the circuit relation underlying the
exponent vectors, yields the following linear combination of logarithms:

$\displaystyle L(u)$ $\displaystyle=$ $\displaystyle
54667\log\left|\frac{39898}{27281}-\frac{84556}{27281}u\right|-16978\log\left|\frac{47210}{27281}-\frac{125680}{27281}u\right|$
$\displaystyle-43727\log\left|\frac{42139}{27281}-\frac{126754}{27281}u\right|+5123\log\left|\frac{20845}{27281}-\frac{114296}{27281}u\right|-10129\log|u|$

In particular, $L$ is an analytic function on
$\mathbb{R}\setminus\\{0,0.182377...,0.332447...,0.375636...,0.471852...\\}$
whose roots encode the roots of $F$ in $(\mathbb{R}^{*})^{4}$: Observing that
$\Lambda(u)\\!=\\!\mathrm{sign}\\!\left(39898-84556u\right)\mathrm{sign}\\!\left(42139-126754u\right)\mathrm{sign}\\!\left(20845-114296u\right)$,
we see that the only open intervals containing $u$ satisfying
$\Lambda(u)\\!=\\!\mathrm{sign}(u)$ are
$(0,0.182377...)$, $(0.332447...,0.375636...)$, $(0.375636...,0.471852...)$.
(The mod $2$ reduction of our $\mathcal{A}$ here has full rank $r\\!=\\!4$ and
thus the condition involving the $\Gamma^{\prime}_{i}(u)$ becomes vacuously
true.) It is then easily checked that $L$ is strictly decreasing, with range
$\mathbb{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 $\mathbb{R}^{*}$ satisfying the sign conditions666$L$ also happens to be
increasing, with range $\mathbb{R}$, on $(-\infty,0)$ and
$(0.182377...,0.332447...)$, and thus $L$ has $2$ more roots in
$\mathbb{R}^{*}$ that do not satisfy the necessary sign conditions. of Lemmata
2.21, and thus $F$ has exactly $2$ roots in $(\mathbb{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 $(\mathbb{C}^{*})^{4}$, as well as approximations of all
these roots to $14$ decimal places. Our Maple simulation counts the roots of
$F$ in $(\mathbb{R}^{*})^{4}$ and $\mathbb{R}^{4}_{+}$ in under one second.
$\diamond$

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 $\mathbb{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 $\mathbb{R}$. In particular, a key difference from our earlier
lemma is the following simple equivalence, valid for all
$u\\!\in\\!\mathbb{R}$: $P(u)\\!=\\!0\Longleftrightarrow[L(u)\\!=\\!0$ and
$\Lambda(u)\\!=\\!\mathrm{sign}(u)]$. (Indeed, we could obtain $u$ with
$P(u)\\!=\\!-2$ without the condition involving $\Lambda(u)$.) Note also that
by construction, $P(0)$ is either $1$ or undefined.

So let $\zeta\\!\in\\!{(\mathbb{R}^{*})}^{n}$ be a root of $F$. By Relation
(3), $\zeta^{a_{n+1}}$ must be a nonzero real root of $P$ and, by the
definition of $G$ and the $\gamma_{i,j}$ (and Proposition 2.8), we must have
$\Gamma^{\prime}_{r+1}\\!\left(\zeta^{a_{n+1}}\right),\ldots,$$\Gamma^{\prime}_{n}\\!\left(\zeta^{a_{n+1}}\right)\\!>\\!0$.
By Proposition 2.8, there must also be exactly $2^{n-r}$ many
$\zeta^{\prime}\\!\in\\!{(\mathbb{R}^{*})}^{n}$ of $F$ with
$(\zeta^{\prime})^{a_{n+1}}\\!=\\!\zeta^{a_{n+1}}$, because $G$ reduces to a
binomial system once the value of $\zeta^{a_{n+1}}$ is fixed. So $F$ has no
more than $2^{n-r}$ times as many roots in ${(\mathbb{R}^{*})}^{n}$ as $P$ has
in $\mathbb{R}^{*}$.

Conversely, if $u\\!\in\\!\mathbb{R}^{*}$ is a root of $P$ then Proposition
2.8 tells us that
$\Gamma^{\prime}_{r+1}(u),\ldots,\Gamma^{\prime}_{n}(u)\\!>\\!0$ implies that
there are exactly $2^{n-r}$ many $\zeta\\!\in\\!{(\mathbb{R}^{*})}^{n}$
satisfying
$(\zeta^{a_{1}},\ldots,\zeta^{a_{n}})\\!=\\!(\gamma_{1,1}u+\gamma_{1,0},\ldots,\gamma_{n,1}u+\gamma_{n,0})$.
(Note also that $\gamma_{i,1}u+\gamma_{i,0}\\!\neq\\!0$ for all $i$ since
$P(u)\\!\neq\\!0$ when $\gamma_{i,1}u+\gamma_{i,0}\\!=\\!0$.) We then also
obtain
$\zeta^{b_{m+1}a_{n+1}}=(\gamma_{1,1}u+\gamma_{1,0})^{-b_{1}}\cdots(\gamma_{m,1}u+\gamma_{m,0})^{-b_{m}}\\!=\\!u^{b_{m+1}}$
by Relation (3). Since $b_{m+1}$ is odd, all our resulting $\zeta$ must
satisfy $\zeta^{a_{n+1}}\\!=\\!u$ and therefore be roots of $G$ (and thus of
$F$). Similarly, a real root $u^{\prime}$ of $P$ with
$(u^{\prime})^{b_{m+1}}\\!\neq\\!u^{b_{m+1}}$ would yield a collection of
$2^{n-r}$ many $\zeta^{\prime}\\!\in\\!{(\mathbb{R}^{*})}^{n}$ that are roots
of $F$ but with $(\zeta^{\prime})^{a_{n+1}}\\!\neq\\!\zeta^{a_{n+1}}$, since
$b_{m+1}$ is odd and $u\\!\in\\!\mathbb{R}^{*}$. So the number of roots of $F$
in ${(\mathbb{R}^{*})}^{n}$ is at least $2^{n-r}$ times the number of roots of
$P$ in $\mathbb{R}^{*}$. $\blacksquare$

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}\\!<\cdots<\\!w_{\ell-1}$ be the critical points and poles of $L$ in
$\mathbb{R}$, and set $w_{0}\\!:=\\!-\infty$ and $w_{\ell}\\!:=\\!+\infty$.
Let $\mathcal{N}$ be the number of $i\\!\in\\!\\{0,\ldots,\ell-1\\}$ such that
$\Lambda(u)\\!=\\!\mathrm{sign}(u)$ and
$\Gamma^{\prime}_{r+1}(u),\ldots,\Gamma^{\prime}_{n}(u)\\!>\\!0$ for all
$u\\!\in\\!(w_{i},w_{i+1})$, and $\left(\lim_{u\rightarrow
w^{+}_{i}}L(u)\right)\left(\lim_{u\rightarrow
w^{-}_{i+1}}L(u)\right)\\!<\\!0$. Then the number of roots of $F$ in
${(\mathbb{R}^{*})}^{n}$ is exactly $\mathcal{N}$ plus the number of
degenerate roots of $L$ in $\mathbb{R}$. $\blacksquare$

###  2.4. Heights of Algebraic Numbers and Linear Forms in Logarithms

Recall that if $\beta$ is in the algebraic closure $\overline{\mathbb{Q}}$ of
$\mathbb{Q}$, with minimal polynomial
$m(x_{1}):=c_{0}+\cdots+c_{d}x^{d}_{1}\\!\in\\!\mathbb{Z}[x_{1}]$ satisfying
$\gcd(c_{0},\ldots,c_{d})\\!=\\!1$, then we may define the (absolute)
logarithmic height of $\beta$ to be
$\displaystyle{h(\beta)\\!:=\\!\frac{1}{d}\left(\log|c_{d}|+\sum\limits^{d}_{i=1}\log\max\\{|\beta_{i}|,1\\}\right)}$,
where $\beta_{1},\ldots,\beta_{d}$ (among them, $\beta$) are all the roots of
$m$. This definition in fact agrees with our earlier definition for rational
numbers. Since $m$ must be irreducible we have
$\\#\\{\beta_{1},\ldots,\beta_{d}\\}\\!=\\!d$.

######  Proposition 2.24.

(See, e.g., [BG06, Prop. 1.5.15, pg. 18].) If
$\alpha_{1},\ldots,\alpha_{k}\\!\in\\!\overline{\mathbb{Q}}$ then
$h\\!\left(\sum\limits^{k}_{i=1}\alpha_{i}\right)$ is no greater than
$\log(k)+\sum\limits^{k}_{i=1}h(\alpha_{i})$. Also,
$h\\!\left(\prod\limits^{k}_{i=1}\alpha_{i}\right)\\!\leq\\!\sum\limits^{k}_{i=1}h(\alpha_{i})$.
$\blacksquare$

Letting
$\left|c_{0}+c_{1}x_{1}+\cdots+c_{d}x^{d}_{1}\right|_{2}\\!:=\\!\sqrt{\sum^{d}_{i=0}|c_{i}|^{2}}$,
we recall the following classical inequality:

######  Landau’s Inequality .

[Mig82] If $\beta\\!\in\\!\overline{\mathbb{Q}}$ has minimal polynomial
$m\\!\in\\!\mathbb{Z}[x_{1}]$ with relatively prime coefficients then
$\displaystyle{h(\beta)\\!\leq\\!\frac{\log|m|_{2}}{\deg m}}$. $\blacksquare$

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.

######  Theorem 2.25.

Suppose $\beta\\!\in\\!\overline{\mathbb{Q}}$, with minimal polynomial
$m\\!\in\\!\mathbb{Z}[x_{1}]$ of degree $d\\!\geq\\!2$. Then
$\displaystyle{\left|\beta-\frac{p}{q}\right|<1\Longrightarrow\left|\beta-\frac{p}{q}\right|\geq\frac{\left(|m^{\prime}(\beta)|+\left|\frac{m^{\prime\prime}(\beta)}{2!}\right|+\cdots+\left|\frac{m^{(d)}(\beta)}{d!}\right|\right)^{-1}}{q^{d}}}$
for all $p,q\\!\in\\!\mathbb{Z}$ with $q\\!>\\!0$.

Proof: First note that the numerator of the large fraction above is positive
since $m$ is the minimal polynomial of $\beta$ and thus
$m^{\prime}(\beta)\\!\neq\\!0$.

Via Taylor expansion we then obtain the following:

$\displaystyle|m(p/q)|$ $\displaystyle=$
$\displaystyle\left|m(\beta)+m^{\prime}(\beta)\left(\frac{p}{q}-\beta\right)+\frac{m^{\prime\prime}(\beta)}{2!}\left(\frac{p}{q}-\beta\right)^{2}+\cdots+\frac{m^{(d)}(\beta)}{d!}\left(\frac{p}{q}-\beta\right)^{d}\right|$
$\displaystyle=$
$\displaystyle\left|\beta-\frac{p}{q}\right|\left|0+m^{\prime}(\beta)+\frac{m^{\prime\prime}(\beta)}{2!}\left(\frac{p}{q}-\beta\right)+\cdots+\frac{m^{(d)}(\beta)}{d!}\left(\frac{p}{q}-\beta\right)^{d-1}\right|$
$\displaystyle\leq$
$\displaystyle\left|\beta-\frac{p}{q}\right|\left(|m^{\prime}(\beta)|+\left|\frac{m^{\prime\prime}(\beta)}{2!}\right|\left|\frac{p}{q}-\beta\right|+\cdots+\left|\frac{m^{(d)}(\beta)}{d!}\right|\left|\frac{p}{q}-\beta\right|^{d-1}\right)$
$\displaystyle<$
$\displaystyle\left|\beta-\frac{p}{q}\right|\left(|m^{\prime}(\beta)|+\left|\frac{m^{\prime\prime}(\beta)}{2!}\right|+\cdots+\left|\frac{m^{(d)}(\beta)}{d!}\right|\right).$

Since $m$ is irreducible and of degree $\geq\\!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)|\\!\geq\\!1$ and thus $|m(p/q)|\\!\geq\\!1/q^{d}$. Combined with
our last Taylor series inequalities, we are done. $\blacksquare$

Finally, we recall the following paraphrase of a bound of Matveev [Mat00, Cor.
2.3], considerably strengthening earlier bounds of Baker and Wustholtz [BW93].
(See also [BMS06, Thm. 9.4].)

######  Theorem 2.26.

Suppose $K$ is a degree $d$ real algebraic extension of $\mathbb{Q}$,
$\alpha_{1},\ldots,\alpha_{m}\\!\in\\!K\setminus\\{0\\}$, and
$b_{1},\ldots,b_{m}\\!\in\\!\mathbb{Z}\setminus\\{0\\}$. Let
$B\\!:=\\!\max\\{|b_{1}|,\ldots,|b_{m}|\\}$ and
$\mathscr{A}_{i}\\!:=\\!\max\\{dh(\alpha_{i}),|\log\alpha_{i}|,0.16\\}$ for
all $i$. Then $\sum^{m}_{i=1}b_{i}\log\alpha_{i}\\!\neq\\!0$ implies that
$\displaystyle{\log\left|\sum^{m}_{i=1}b_{i}\log\alpha_{i}\right|>-1.4\cdot
m^{4.5}30^{m+3}d^{2}(1+\log d)(1+\log(mB))\prod^{m}_{i=1}\mathscr{A}_{i}}$.
$\blacksquare$

###  2.5. Bounds on Coefficients, Roots, and Derivatives of Univariate
Polynomials

Letting
$\left|c_{0}+c_{1}x_{1}+\cdots+c_{d}x^{d}_{1}\right|_{\infty}\\!:=\\!\max_{i}|c_{i}|$,
recall the following classic bounds on the size and minimal spacing of roots
of polynomials:

######  Proposition 2.27.

(See, e.g., [RS02, Thm. 8.1.4 & Thm. 8.1.7, (i), (8.1.3)].) If
$f\\!\in\\!\mathbb{Z}[x_{1}]$ satisfies $|f|_{\infty}\\!\leq\\!H$ and
$\zeta\\!\in\\!\mathbb{C}$ is a nonzero root of $f$ then
$\frac{1}{1+H}\\!<\\!|\zeta|\\!<\\!1+H$. $\blacksquare$

######  Mahler’s Theorem .

[Mah64] Suppose $f\\!\in\\!\mathbb{Z}[x_{1}]$ is square-free, has degree $d$,
and $|f|_{\infty}\\!\leq\\!H$. Then any two distinct complex roots
$\zeta_{1},\zeta_{2}$ of $f$ satisfy
$\displaystyle{|\zeta_{1}-\zeta_{2}|\\!>\\!\sqrt{3}(d+1)^{-(2d+1)/2}H^{-(d-1)}}$.
In particular, $|\log|\zeta_{1}-\zeta_{2}||\\!=\\!O(d\log(dH))$.
$\blacksquare$

Letting
$\left|c_{0}+c_{1}x_{1}+\cdots+c_{d}x^{d}_{1}\right|_{1}\\!:=\\!\sum^{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\\!\in\\!\mathbb{C}[x_{1}]$ have respective
leading coefficients $c$ and $\gamma$, and $g|f$. Then
$|g|_{1}\\!\leq\\!2^{\deg g}\left|\frac{\gamma}{c}\right||f|_{2}$.
$\blacksquare$

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\\!\in\\!\mathbb{Z}[x_{1}]$ has degree $d$ and
$|f|_{\infty}\\!\leq\\!H$. Then any two distinct complex roots
$\zeta_{1},\zeta_{2}$ of $f$ satisfy
$|\log|\zeta_{1}-\zeta_{2}||\\!=\\!O(d^{2}+d\log(dH))$. $\blacksquare$

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},\ldots,f_{k}\\!\in\mathbb{Z}[x_{1}]$ then
$\left|\prod\limits^{k}_{i=1}f_{i}\right|_{\infty}\\!\leq\\!\prod\limits^{k}_{i=1}2^{\deg
f_{i}}|f_{i}|_{\infty}$. $\blacksquare$

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]:

######  Corollary 2.30.

Suppose $f\\!\in\\!\mathbb{C}[x_{1}]$ has degree $d$ and $t\\!>\\!0$. Then
$\displaystyle{\underset{-t\leq x_{1}\leq
t}{\max}\left|f^{(j)}(x_{1})\right|\leq\frac{d^{2}(d^{2}-1^{2})\cdots(d^{2}-(j-1)^{2})}{1\cdot
3\cdots(2j-1)}\cdot\frac{\underset{-t\leq x_{1}\leq
t}{\max}|f(x_{1})|}{t^{j}}}$. $\blacksquare$

After rescaling the variable so it ranges over $[-1,1]$, the statement above
follows immediately from [RS02, Thm. 15.2.6 & Cor. 15.2.7, Sec. 15.2]. The
latter results in fact include conditions for equality in the bound above.

##  3\. Critical Values of Linear Forms in Logarithms and Their Signs

We are now ready to prove two key lemmata (3.1 and 3.4 below) that enable our
new complexity bounds.

######  Lemma 3.1.

Suppose $m\\!\geq\\!2$, $b_{i}\\!\in\\!\mathbb{Z}\setminus\\{0\\}$ and
$\gamma_{i,1},\gamma_{i,0}\\!\in\\!\mathbb{Q}$ for all
$i\\!\in\\!\\{1,\ldots,m\\}$, $\det$
$\begin{bmatrix}\gamma_{i,1}&\gamma_{i,0}\\\
\gamma_{j,1}&\gamma_{j,0}\end{bmatrix}$ $\neq\\!0$ for all $i$, $j$,
$B\\!:=\\!\max_{i}|b_{i}|$, and $h(\gamma_{i,j})\\!\leq\\!\log H$ for some
$H\\!>\\!1$. Let
$\displaystyle{L(u):=\sum^{m}_{i=1}b_{i}\log|\gamma_{i,1}u+\gamma_{i,0}|}$.
Then the critical points of $L$ in $\mathbb{R}$ are exactly the real roots of
a polynomial $g\\!\in\\!\mathbb{Z}[u]$ of degree at most $m-1$ with
$|g|_{\infty}\\!\leq\\!m2^{m-1}BH^{2m}$. In particular,
$\log|g|_{\infty}\\!=\\!O(\log(B)+m\log H)$ and $L$ has at most $m$ real
roots.

######  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\times 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
$\displaystyle-85015812446550320118784u^{4}+160578806134338659719072u^{3}-78932164016242868100268u^{2}$
$\displaystyle+13833463598904597755876u-837930167824219163155,$
which has coefficients with at most $24$ digits, and $2$ real roots, neither
of which lies in the sub-intervals of $\mathbb{R}$ contributing to the root
count of $F$ in $(\mathbb{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 $(\mathbb{R}^{*})^{4}$ for Example 2.22.
$\diamond$

######  Example 3.3.

Returning to Example 2.17, which had $L(u)$ being
$-2\log\left|16384cu+\frac{1}{4}\right|+2\log\left|4096cu+1\right|-2\log\left|256cu+1\right|+2\log\left|16cu+1\right|-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$. $\diamond$

Proof of Lemma 3.1: First observe that
$L^{\prime}(u)\\!=\\!\sum\limits^{m}_{i=1}\frac{b_{i}\gamma_{i,1}}{\gamma_{i,1}u+\gamma_{i,0}}$.
Thanks to our determinant assumption, $L^{\prime}$ has exactly $m$ distinct
poles. Gelfond’s Lemma implies that the coefficients of the monomial term
expansion of $(r_{1}u+s_{1})\cdots(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 $\nu_{i}$ be the least common multiple of the denominators of
$\gamma_{i,1}$ and $\gamma_{i,0}$, and setting
$\displaystyle{g_{i}(u)\\!:=\\!\left.\left(b_{i}\gamma_{i,1}\nu_{i}\prod\limits^{m}_{j=1}(\gamma_{j,1}u+\gamma_{j,0})\nu_{j}\right)\right/((\gamma_{i,1}u+\gamma_{i,0})\nu_{i})}$,
let us define $g(u)\\!:=\\!\sum^{m}_{i=1}g_{i}(u)$. Clearly,
$g_{i}\\!\in\\!\mathbb{Z}[u]$ for all $i$, $g\\!\in\\!\mathbb{Z}[u]$, and
$g(u)$ is nothing more than
$L^{\prime}(u)\prod^{m}_{j=1}(\gamma_{j,1}u+\gamma_{j,0})\nu_{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\\!\leq\\!m-1$.

Gelfond’s Lemma implies that
$|g_{i}|_{\infty}\\!\leq\\!BH^{2}\left(2^{m-1}H^{2(m-1)}\right)$. Clearly
then, $|g|_{\infty}\\!\leq\\!m2^{m-1}BH^{2m}$.

That $L$ has at most $m$ roots in $I$ is immediate from Rolle’s Theorem, since
$\deg g\\!\leq\\!m-1$. $\blacksquare$

Recall that a critical value of a function
$L:\mathbb{R}\longrightarrow\mathbb{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 $\varepsilon$ denote
any nonzero critical value of $L$, and let $\delta$ (resp. $\eta$) be the
minimum of $|\zeta_{1}-\zeta_{2}|$ over all distinct roots
$\zeta_{1},\zeta_{2}\\!\in\\!I$ of $L$ (resp. the derivative $L^{\prime}$).
Finally, let $\Delta$ denote the minimum of $|\zeta-\mu|$ as $\zeta$ (resp.
$\mu$) ranges over the critical points (resp. poles) of $L$. Then:
1\. $\log\eta>-O(m\log(B)+m^{2}\log H)$,
2\.
$\log|\varepsilon|>-O\\!\left(61^{m}\log^{m+1}\left(BH^{3m-1}\right)\right)$,
3\. $\log\Delta>-O\\!\left(m\log(B)+m^{2}\log H\right)$, and
4\. $\log\delta>-O\\!\left(61^{m}\log^{m+1}\left(BH^{3m-1}\right)\right)$.

Proof: If $L$ has no critical points then, by Rolle’s Theorem, $L$ has at most
$1$ root in $I$ and Assertions (1)–(3) are vacuously true. So let us assume
$L$ has exactly $k-1$ critical points (with $k\\!\geq\\!2$) in the open
interval $I$, $u_{0}\\!:=\\!\inf I$, $u_{k}\\!:=\\!\sup I$, and suppose
$u_{1}\\!<\cdots<\\!u_{k-1}$ are the critical points of $L$ in $I$. Also let
$g$ denote the polynomial from Lemma 3.1. Below we illustrate a coarse
approximation of what the graph of $L$ can look like, along with some of our
notation:

$u_{0}$

$\Delta$

$u_{1}$

$\eta$

$\varepsilon$

$u_{2}$

$u_{5}$

$u_{7}$

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
$|\varepsilon|$ 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}\\!\in\\!I$ (for some $j\\!\in\\!\\{1,\ldots,k-1\\}$) all lie in the
same real algebraic extension: $\mathbb{Q}(u_{j})$. Noting that the minimal
polynomial, $p$, of $u_{j}$ has degree $\leq\\!m-1$, Lemmata 2.28 and 3.1 then
tell us that $|p|_{\infty}\\!\leq\\!2^{m-1}|g|_{\infty}|g|_{2}$ (since $p|g$),
and thus

(4) $\displaystyle|p|_{\infty}\leq
2^{m-1}(mB2^{m-1}H^{2m})(\sqrt{m}(mB2^{m-1}H^{2m}))=m^{3/2}8^{m-1}B^{2}H^{4m}.$

So $\log|p|_{2}\\!\leq\\!\log\left(\sqrt{m}\cdot
m^{3/2}B^{2}8^{m-1}H^{4m}\right)$, and thus Landau’s Inequality tells us that
$\deg(p)h(u_{j})\leq\log\left(m^{2}8^{m-1}B^{2}H^{4m}\right)$.
Proposition 2.27 then tells us that $|u_{j}|<1+|g|_{\infty}\leq
1+m2^{m-1}BH^{2m}$. Also,
$h(\gamma_{i,1}u_{j}+\gamma_{i,0})\\!\leq\\!\log(2)+(h(\gamma_{i,1})+h(u_{j}))+h(\gamma_{i,0})$,
thanks to Proposition 2.24. So then,
$\deg(p)h(\gamma_{i,1}u_{j}+\gamma_{i,0})\leq(m-1)\log(2)+2(m-1)\log(H)+\log\\!\left(m^{2}8^{m-1}B^{2}H^{4m}\right)$
$\leq\log\\!\left(m^{2}16^{m-1}B^{2}H^{6m-2}\right)$.
Theorem 2.26 then tells us that

$\displaystyle\log|\varepsilon|$ $\displaystyle>$ $-1.4\cdot
30^{m+3}m^{6.5}(1+\log(m-1))(1+\log(mB))\left(\log\\!\left(m^{2}16^{m-1}B^{2}H^{6m-2}\right)\right)^{m}$
$\displaystyle=$ $-1.4\cdot 30^{3}\cdot
30^{m}m^{6.5}(1+\log(m-1))(1+\log(mB))\log^{m}\\!\left(m^{2}16^{m-1}B^{2}H^{6m-2}\right)$
$\displaystyle=$
$\displaystyle-O\\!\left(30^{m}m^{6.5}(1+\log(m-1))(1+\log(mB))\log^{m}\\!\left(m^{2}16^{m-1}B^{2}H^{6m-2}\right)\right)$
$\displaystyle=$
$\displaystyle-O\\!\left(30^{m}m^{6.5}(2\log(m-1))(2\log(mB))\log^{m}\\!\left(m^{2}16^{m-1}B^{2}H^{6m-2}\right)\right)$
$\displaystyle=$
$\displaystyle-O\\!\left(30^{m}m^{6.5}\log(m-1)\log(mB)\log^{m}\\!\left(m^{2}16^{m-1}B^{2}H^{6m-2}\right)\right).$

Since $m^{6.5}\log(m-1)\\!=\\!O\\!\left(30^{\theta_{1}m}\right)$ and
$m^{2}16^{m-1}\\!=\\!O\\!\left((B^{2}H^{6m-2})^{\theta_{2}}\right)$ for any
$\theta_{1},\theta_{2}\\!>\\!0$, we then obtain
$\displaystyle{\log|\varepsilon|>-O\\!\left(30^{(1+\theta_{1})m}\log(mB)\log^{m}\\!\left(\left(B^{2}H^{6m-2}\right)^{1+\theta_{2}}\right)\right)}$

$\displaystyle\mbox{}\hskip 34.14322pt=$
$\displaystyle-O\\!\left(30^{(1+\theta_{1})m}\log^{m+1}\\!\left(\left(B^{2}H^{6m-2}\right)^{1+\theta_{2}}\right)\right)\hskip
34.14322pt\mbox{}$ $\displaystyle=$
$\displaystyle-O\\!\left(30^{(1+\theta_{1})m}(1+\theta_{2})^{m+1}2^{m+1}\log^{m+1}\\!\left(BH^{3m-1}\right)\right)$
$\displaystyle=-O\\!\left(61^{m}\log^{m+1}\\!\left(BH^{3m-1}\right)\right),$

(picking, say, $\theta_{1}\\!=\\!\log(30.25/30)$ and
$\theta_{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
$\Delta\\!=\\!\min\\{u_{1}-u_{0},u_{k}-u_{k-1}\\}$, i.e.,
$\Delta\\!=\\!|u_{j^{\prime}}-u_{\ell}|$ for some
$j^{\prime}\\!\in\\!\\{1,k-1\\}$ and $\ell\\!\in\\!\\{0,k-1\\}$, by our
earlier definitions. If $\Delta\\!=\\!\infty$ then there is nothing to prove,
so let us assume $\Delta\\!<\\!\infty$. If $u_{j^{\prime}}\\!\in\\!\mathbb{Q}$
then Assertion (3) follows easily from Proposition 2.24, since $u_{\ell}$ has
logarithmic height no greater than $2\log H$ and $u_{j^{\prime}}$ must have
logarithmic height no greater than $O(\log(B)+m\log H)$. So we may assume that
$u_{j^{\prime}}$ is algebraic of degree at least $2$ over $\mathbb{Q}$.

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

(5)
$\displaystyle\frac{\left(|p^{\prime}(u_{j^{\prime}})|+\left|\frac{p^{\prime\prime}(u_{j^{\prime}})}{2!}\right|+\cdots+\left|\frac{p^{(m-1)}(u_{j^{\prime}})}{(m-1)!}\right|\right)^{-1}}{H^{2(m-1)}}.$

We know that $|u_{j^{\prime}}|<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\\!:=\\!\left[-1-m2^{m-1}BH^{2m},1+m2^{m-1}BH^{2m}\right]$.

Noting the easy inequality $\displaystyle{\underset{-t\leq x_{1}\leq
t}{\max}\left|f(x_{1})\right|\leq|f|_{1}\max\left\\{1,|t|^{d}\right\\}}$ for
any $f\\!\in\\!\mathbb{R}[x_{1}]$ of degree $d$ and $t\\!\in\\!\mathbb{R}$ we
then have

(6) $\displaystyle\underset{x_{1}\in J}{\max}|g(x_{1})|$ $\displaystyle\leq$
$\displaystyle|g|_{1}\underset{x_{1}\in
J}{\max}\max\left\\{1,x^{m-1}_{1}\right\\}$ $\displaystyle\leq$ $\displaystyle
m|g|_{\infty}\left(1+m2^{m-1}BH^{2m}\right)^{m-1},$ $\displaystyle\leq$
$\displaystyle m\cdot m2^{m-1}BH^{2m}\left(1+m2^{m-1}BH^{2m}\right)^{m-1},$

and Corollary 2.30 then implies

$\displaystyle|p^{(r)}(u_{j^{\prime}})|$ $\displaystyle\leq$
$\displaystyle\underset{x_{1}\in J}{\max}\left|p^{(r)}(x_{1})\right|$
$\displaystyle\leq$
$\displaystyle\frac{(m-1)^{2}((m-1)^{2}-1^{2})\cdots((m-1)^{2}-(r-1)^{2})}{1\cdot
3\cdots(2r-1)}\cdot|p|_{1}\cdot\left(1+m2^{m-1}BH^{2m}\right)^{m-1},$

since $p$ has degree $\leq\\!m-1$. Since $|p|_{1}\\!\leq\\!m|p|_{\infty}$,
Inequality (4) tells us that $\left|p^{(r)}(u_{j^{\prime}})\right|$ is bounded
from above by
$\displaystyle\frac{(m-1)^{2}((m-1)^{2}-1^{2})\cdots((m-1)^{2}-(r-1)^{2})}{1\cdot
3\cdots(2r-1)}\cdot
m\cdot\left(m^{3/2}8^{m-1}B^{2}H^{4m}\right)\left(1+m2^{m-1}BH^{2m}\right)^{m-1}$

$\displaystyle\leq$
$\displaystyle\binom{(m-1)^{2}}{r}m\cdot\left(m^{3/2}8^{m-1}B^{2}H^{4m}\right)\left(1+m2^{m-1}BH^{2m}\right)^{m-1}$
$\displaystyle\leq$
$\displaystyle\left(\frac{(m-1)^{2}e}{r}\right)^{r}m^{5/2}8^{m-1}B^{2}H^{4m}\left(1+m2^{m-1}BH^{2m}\right)^{m-1},$

where the last inequality follows easily from Stirling’s classical estimate
for the factorial function. So then,
$|p^{\prime}(u_{j^{\prime}})|+\left|\frac{p^{\prime\prime}(u_{j^{\prime}})}{2!}\right|+\cdots+\left|\frac{p^{(m-1)}(u_{j^{\prime}})}{(m-1)!}\right|$
is strictly less than
$\left[(m-1)^{2}e+\frac{((m-1)^{2}e/2)^{2}}{2!}+\cdots+\frac{((m-1)^{2}e/r)^{r}}{r!}\right]m^{5/2}8^{m-1}B^{2}H^{4m}\left(1+m2^{m-1}BH^{2m}\right)^{m-1}$.

Now, by the Maclaurin series for $e^{x}$, the bracketed factor above is
strictly less than $e^{(m-1)^{2}e}$. So then,
$|p^{\prime}(u_{j^{\prime}})|+\left|\frac{p^{\prime\prime}(u_{j^{\prime}})}{2!}\right|+\cdots+\left|\frac{p^{(m-1)}(u_{j^{\prime}})}{(m-1)!}\right|$
is strictly less than

$\displaystyle
e^{(m-1)^{2}e}m^{5/2}8^{m-1}B^{2}H^{4m}\left(1+m2^{m-1}BH^{2m}\right)^{m-1}$
$\displaystyle=$ $\displaystyle
O\\!\left(e^{m(m-1)e}m^{5/2}8^{m-1}B^{2}H^{4m}\left(1+m2^{m-1}BH^{2m}\right)^{m-1}\right)$
$\displaystyle=$ $\displaystyle
O\\!\left(\left(e^{e+\theta_{3}}\right)^{m(m-1)}B^{2}H^{4m}\left(2^{(1+\theta_{4})(m-1)}BH^{2m}\right)^{m}\right)$
$\displaystyle=$ $\displaystyle
O\\!\left(\left(2^{1+\theta_{4}}e^{e+\theta_{3}}\right)^{m(m-1)}B^{m+2}H^{2m^{2}+4m}\right),$

for any $\theta_{3},\theta_{4}\\!>\\!0$. Observing that $2e^{e}\\!<\\!30.31$,
we can then clearly pick $\theta_{3}$ and $\theta_{4}$ to obtain

$\displaystyle|p^{\prime}(u_{j^{\prime}})|+\left|\frac{p^{\prime\prime}(u_{j^{\prime}})}{2!}\right|+\cdots+\left|\frac{p^{(m-1)}(u_{j^{\prime}})}{(m-1)!}\right|$
$\displaystyle=$ $\displaystyle
O\\!\left(31^{m(m-1)}B^{m+2}H^{2m^{2}+4m}\right),$

and thus, combining with Inequality (5),
$\frac{1}{\Delta}\\!=\\!O\\!\left(31^{m(m-1)}B^{m+2}H^{2m^{2}+6m-2}\right)$,
and we obtain Assertion (3) by taking logarithms.

To prove Assertion (4) we merely use the Mean Value Theorem. First, let
$\delta^{\prime}$ be the minimum distance between $u_{j}$ and $\zeta^{\prime}$
where $\zeta^{\prime}$ is any root of $L$. (Recall that $u_{j}$, with
$j\\!\in\\!\\{1,\ldots,k-1\\}$, is a critical point of $L$ corresponding to a
nonzero critical value $\varepsilon$ of $L$.) Clearly,
$\delta\\!\geq\\!2\delta^{\prime}\\!>\\!0$ (thanks to Rolle’s Theorem), so it
is enough to prove a sufficiently good lower bound on $\delta^{\prime}$. Note
in particular that if $\delta^{\prime}\\!>\\!\Delta/2$ then we are done,
thanks to Assertion (3). So let us assume $\delta^{\prime}\\!\leq\\!\Delta/2$.

Recall that, from the proof of Lemma 3.1, we have
$L^{\prime}(u)\\!=\\!g(u)/\prod\limits^{m}_{i=1}(\gamma_{i,1}u+\gamma_{i,0})\nu_{i}$
where $\nu_{i}$ is the least common multiple of the denominators of
$\gamma_{i,1}$ and $\gamma_{i,0}$.

Clearly, if $\gamma_{i,1}\\!\neq\\!0$, then
$|(\gamma_{i,1}u+\gamma_{i,0})\nu_{i}|\\!=\\!\left|u-\frac{-\gamma_{i,0}}{\gamma_{i,1}}\right||\gamma_{i,1}\nu_{i}|\\!>\\!|\gamma_{i,1}\nu_{i}|\Delta/2\\!\geq\\!\Delta/2$
for all $u\\!\in\\!\left[u_{j}-\delta^{\prime},u_{j}+\delta^{\prime}\right]$,
since $\zeta^{\prime}\\!\in\\!I$, $\frac{-\gamma_{i,0}}{\gamma_{i,1}}$ is a
pole of $L$, and $\gamma_{i,1}\nu_{i}$ is a nonzero integer. On the other
hand, if $\gamma_{i,1}\\!=\\!0$, then
$|(\gamma_{i,1}u+\gamma_{i,0})\nu_{i}|\\!=\\!|\gamma_{i,0}\nu_{i}|\\!\geq\\!1$
since $\gamma_{i,0}\nu_{i}$ is a nonzero integer. So then,

(7)
$\displaystyle\prod\limits^{m}_{i=1}(\gamma_{i,1}u+\gamma_{i,0})\nu_{i}>\Delta^{m}/2^{m}\text{
for all
$u\\!\in\\!\left[u_{j}-\delta^{\prime},u_{j}+\delta^{\prime}\right]$.}$

By the Mean Value Theorem, we must have
$|L^{\prime}(\xi)|\\!=\left|\frac{\varepsilon}{\delta^{\prime}}\right|$ for
some $\xi\\!\in\\!\left(u_{j}-\delta^{\prime},u_{j}+\delta^{\prime}\right)$.
So then, thanks to Inequalities (6) and (7), we obtain

$\displaystyle|L^{\prime}(\xi)|$ $\displaystyle=$
$\displaystyle\left|g(\xi)\left/\prod\limits^{m}_{i=1}(\gamma_{i,1}\xi+\gamma_{i,0})\nu_{i}\right.\right|$
$\displaystyle<$ $\displaystyle
m^{2}2^{m-1}BH^{2m}\left(1+m2^{m-1}BH^{2m}\right)^{m-1}\frac{2^{m}}{\Delta^{m}}$
$\displaystyle\leq$ $\displaystyle
m^{2}2^{2m-1}BH^{2m}\left(1+m2^{m-1}BH^{2m}\right)^{m-1}O\\!\left(31^{m(m-1)}B^{m+2}H^{2m^{2}+6m-2}\right)^{m}$

Since $\delta^{\prime}\\!=\\!|\varepsilon/L^{\prime}(\xi)|$ we thus obtain
that $\log\delta^{\prime}=\log|\varepsilon|-\log|L^{\prime}(\xi)|$, which is
then bounded from

below by
$-O\\!\left(61^{m}\log^{m+1}\left(BH^{3m-1}\right)\right)-O\\!\left(\log(m)+m+\log(B)+m\log(H)+m\log\\!\left(m2^{m-1}BH^{2m}\right)\right)$

$-mO\\!\left(m^{2}\log(31)+m\log(B)+m^{2}\log H\right)$,
which reduces to $-O\\!\left(61^{m}\log^{m+1}\left(BH^{3m-1}\right)\right)$.
$\blacksquare$

###  3.1. The Complexity of Approximating Logarithms and Real Roots of
Polynomials

Any real number can be expressed in binary. Since
$2^{\left\lfloor\log_{2}x\right\rfloor}\\!\leq\\!x\\!\leq\\!2^{1+\left\lfloor\log_{2}x\right\rfloor}$
for any $x\\!\in\\!\mathbb{R}_{+}$, it is easy to check that
$1+\left\lfloor\log_{2}x\right\rfloor$ is the number of bits for the integer
part of $x$. It then makes sense to call the binary expansion of $\left\lfloor
2^{\ell-1-\left\lfloor\log_{2}x\right\rfloor}x\right\rfloor$ the $\ell$ most
significant bits of an $x\\!\in\\!\mathbb{R}_{+}$. Clearly, knowing the $\ell$
most significant bits of $x$ means that one knows $x$ within a multiple of
$(1+2^{-\ell})^{\pm 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\\!\in\\!\mathbb{Q}$ of logarithmic
height $h$, and $\ell\\!\in\\!\mathbb{N}$ with $\ell\\!\geq\\!h$, we can
compute $\left\lfloor\log_{2}\max\\{1,\log|x|\\}\right\rfloor$ and the $\ell$
most significant bits of $\log x$ in time $O(\ell\log^{2}\ell)$.
$\blacksquare$

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\\!\left(\ell^{1.585}\right)$ or lower.

Recall that bisection is the ancient technique of approximating a root of a
continuous function $f:[r_{1},r_{2}]\longrightarrow\mathbb{R}$ by the
following trick: If $\mathrm{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 $\left(r_{1},\frac{r_{1}+r_{2}}{2}\right)$ if and only if
$\mathrm{sign}\\!\left(f(r_{1})f\\!\left(\frac{r_{1}+r_{2}}{2}\right)\right)\\!<\\!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 $\mathbb{Z}[x_{1}]$ by
rational numbers.

######  Lemma 3.6.

Suppose $f\\!\in\\!\mathbb{Z}[x_{1}]$ has degree $d$,
$|f|_{\infty}\\!\leq\\!H$, and $\ell\\!\in\\!\mathbb{N}$. Let $\delta(f)$
denote the minimum of $|\zeta_{1}-\zeta_{2}|$ over all distinct real roots
$\zeta_{1},\zeta_{2}$ of $f$. Then, in time
$O\\!\left(d^{6}\log^{2}(H)+d^{4}(d^{2}+\ell)\ell\log^{2}(d\ell\log(dH))\right)$,
we can find a collection of disjoint non-empty open intervals
$\\{J_{i}\\}^{k}_{i=1}$ with the followingproperties:
(a) $k$ is the number of real roots of $f$.
(b) Each $J_{i}$ contains exactly one root of $f$.
(c) The endpoints of all the $J_{i}$ are rational numbers with logarithmic
height
$O(\ell+d^{2}+d\log(dH))$.
(d) All the $J_{i}$ have width no greater than $2^{-\ell}\delta(f)$.

Proof: The case $\ell\\!=\\!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^{\prime})$, 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^{\prime}\\!=\\!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^{\prime})$ bound (in our notation) from [Sag11, Thm. 24].

The case of arbitrary $\ell$ can be derived simply by applying bisection after
using the $\ell\\!=\\!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 $\alpha\\!\in\\!\mathbb{Q}$ has logarithmic height
$L$ then Proposition 2.24 implies that $f(\alpha)$ has height
$O(d\log(H)+d^{2}L)$. So we can correctly find the sign of $f(\alpha)$ 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\delta(f)|\\!=\\!O(d^{2}+d\log(dH))$.
This means that getting $\ell$ additional bits of accuracy beyond the minimum
root separation requires time
$\sum^{\ell}_{i=0}O\\!\left((d^{3}\log(H)+(L+i)d^{4})\log((L+i)d\log
H)\right)$,
where $L\\!=\\!O(d^{2}+d\log(dH))$. Summing up all our time bounds, we get our
stated bound. $\blacksquare$

######  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. $\diamond$

##  4\. Our Main Algorithms and Their Complexity

Our central algorithm for counting roots in ${(\mathbb{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},\ldots,b_{m}$ and rational numbers
$\gamma_{1,1},\gamma_{1,0},\ldots,\gamma_{m,1},\gamma_{m,0},u_{0},u_{\infty}$,
with $m\\!\geq\\!2$, $\gamma_{i,1}u+\gamma_{i,0}\\!>\\!0$ for all
$u\\!\in\\!(u_{0},u_{\infty})$ and $i\\!\in\\!\\{1,\ldots,m\\}$, and
$\det\begin{bmatrix}\gamma_{i,1}&\gamma_{i,0}\\\
\gamma_{j,1}&\gamma_{j,0}\end{bmatrix}\\!\neq\\!0$ for all $i,j$.
Output: The signs of
$\displaystyle{L(u)\\!=\\!\sum\limits^{m}_{i=1}b_{i}\log\left|\gamma_{i,1}u+\gamma_{i,0}\right|}$
at all the critical points of $L$ in $(u_{0},u_{\infty})$.
Description:

  * 0.

Let $B\\!:=\\!\max_{i}|b_{i}|$, $\log
H\\!:=\\!\max\left\\{1,\max_{i,j}h\\!\left(\gamma_{i,j}\right)\right\\}$,
$\mathscr{A}:=\log^{m}\left(m^{2}16^{m-1}B^{2}H^{6m-2}\right)$,

$\displaystyle\mathcal{E}$ $\displaystyle:=$ $\displaystyle 1.4\cdot
m^{6.5}30^{m+3}(1+\log m)(1+\log(mB))\mathscr{A},$ $\displaystyle\mathcal{D}$
$\displaystyle:=$ $\displaystyle
m^{2}e+(m+2)\log\left(8+m2^{m+2}BH^{2m}\right),$

and $\rho\\!:=\\!1.443(\mathcal{D}+\log(12m)+\mathcal{E})$.

  * 1.

Compute the polynomial
$\displaystyle{g(u)\\!:=\\!\sum^{m}_{i=1}{b_{i}\gamma_{i,1}\nu_{i}\left.\prod\limits^{m}_{j=1}(\gamma_{j,1}u+\gamma_{j,0})\nu_{j}\right/((\gamma_{i,1}u+\gamma_{i,0})\nu_{i})}}$,
where $\nu_{i}$ denotes the least common multiple of the denominators of
$\gamma_{i,1}$ and $\gamma_{i,0}$.

  * 2.

Via Lemma 3.6, find respective isolating intervals $J_{1},\ldots,J_{k-1}$ to
the roots $u_{1}\\!<\cdots<\\!u_{k-1}$ of $g$ in $(u_{0},u_{\infty})$ such
that each $J_{i}$ has width no greater than $2^{-\rho}$.

  * 3.

For all $i\\!\in\\!\\{1,\ldots,k-1\\}$ do:

  * 4.

Let $\bar{u}_{i}\\!:=\\!\frac{\sup J_{i}+\inf J_{i}}{2}$.

  * 5.

For all $j\\!\in\\!\\{1,\ldots,m\\}$ do:

  * 6.

Compute, via Theorem 3.5, a rational number $L_{j}$ agreeing with
$\log|\gamma_{j,1}\bar{u_{i}}+\gamma_{j,0}|$
in its first $\left\lceil 1.443\mathcal{E}+\log_{2}(6m)\right\rceil$ most
significant bits.

  * 7.

End For

  * 8.

Let $\mathscr{L}_{i}\\!:=\\!\sum\limits^{m}_{j=1}b_{j}L_{j}$ and
$\theta_{i}\\!:=\\!\mathrm{sign}(\mathscr{L}_{i})$.

  * 9.

If $|\mathscr{L}_{i}|\\!>\\!\frac{1}{2}2^{-1.443\mathcal{E}}$ then

  * 10.

Output “The sign of $L$ at $u_{i}$ is $\theta_{i}$.”

  * 11.

Else

  * 12.

Output “$L(u_{i})\\!=\\!0$.”

  * 13.

End If

  * 14.

End For

######  Lemma 4.2.

Algorithm 4.1 is correct and runs in time $O(\log(B)+m\log H)^{2m+2}$.

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-\frac{1}{x}\leq\log x\leq x-1$ (for all $x\\!>\\!0$), yields
$\frac{s}{v+s}\leq\log(v+s)-\log v\leq\frac{s}{v}$ (for all $v\\!>\\!0$ and
$s\\!>\\!-v$),
upon setting $x\\!=\\!\frac{v+s}{v}$. Setting
$v\\!=\\!\gamma_{j,1}\bar{u}_{j}+\gamma_{j,0}$ and
$s\\!=\\!\gamma_{j,1}(u_{j}-\bar{u}_{j})$, and
assuming$\gamma_{j,1}u_{j}+\gamma_{j,0},\gamma_{j,1}\bar{u}_{j}+\gamma_{j,0}\\!>\\!0$,
we then obtain

(8)
$\displaystyle\frac{(u_{j}-\bar{u}_{j})\gamma_{j,1}}{\gamma_{j,1}u_{j}+\gamma_{j,0}}\leq\log(\gamma_{j,1}u_{j}+\gamma_{j,0})-\log(\gamma_{j,1}\bar{u}_{j}+\gamma_{j,0})\leq\frac{(u_{j}-\bar{u}_{j})\gamma_{j,1}}{\gamma_{j,1}\bar{u}_{j}+\gamma_{j,0}}.$

The proof of Assertion (3) of Lemma 3.4 tells us that
$\frac{|\gamma_{j,1}u_{j}+\gamma_{j,0}|}{|\gamma_{j,1}|}\\!\geq\\!\Delta$.
Since $1/\log 2\\!<\\!1.443$ we have $\Delta\\!>\\!2^{-1.443\mathcal{D}}$,
thanks to the definition of $\mathcal{D}$. So the definition of $s$ tells us
that $|u_{j}-\bar{u}_{j}|\\!\leq\\!\frac{1}{2}2^{-1.443\mathcal{D}}$ is
sufficient to guarantee that
$\frac{|\gamma_{j,1}\bar{u}_{j}+\gamma_{j,0}|}{|\gamma_{j,1}|}\\!\geq\\!\Delta/2$.
So, by Inequality (8), we obtain that $|u_{j}-\bar{u}_{j}|\\!\leq\\!2^{-\rho}$
guarantees
$|\log(\gamma_{i,1}u_{i}+\gamma_{i,0})-\log(\gamma_{i,1}\bar{u}_{i}+\gamma_{i,0})|\\!\leq\\!\frac{1}{6m}2^{-1.443\mathcal{E}}$.
Should $\gamma_{i,1}u+\gamma_{i,0}\\!<\\!0$ we can repeat our preceding
argument, with a sign flip, to obtain that
$|u_{j}-\bar{u}_{j}|\\!\leq\\!2^{-\rho}$ guarantees
$|\log|\gamma_{i,1}u_{i}+\gamma_{i,0}|-\log|\gamma_{i,1}\bar{u}_{i}+\gamma_{i,0}||\\!\leq\\!\frac{1}{6m}2^{-1.443\mathcal{E}}$.
So then, thanks to Step 6 and the Triangle Inequality, we see that our
algorithm computes, for each $i\\!\in\\!\\{1,\ldots,k-1\\}$, a rational
$\mathscr{L}_{i}$ such that
$|L(u_{i})-\mathscr{L}_{i}|\\!\leq\\!\frac{1}{3}2^{-1.443\mathcal{E}}$.

Theorem 2.26 then tells us that $|L(u_{i})|$ is either $0$ or strictly greater
than $2^{-1.443\mathcal{E}}$. So the threshold on $|\mathscr{L}_{i}|$ from
Step 9 indeed correctly distinguishes between $L(u_{i})$ being nonzero or
zero, and the signs of $L(u_{i})$ and $\mathscr{L}_{i}$ also match when
$L(u_{i})\\!\neq\\!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$,
$\mathscr{A}$, $\mathcal{E}$, $\mathcal{D}$, and $\rho$ 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 over-estimate 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,\ell)$ in the statement of Lemma 3.6 by $(m-1,m2^{m-1}BH^{2m},\rho)$.
Noting that $\rho\\!=\\!O(\mathcal{E})$ and
$m^{r},\log^{r}B,\log^{r}H\\!=\\!O(\mathcal{E})$ for any $r\\!>\\!0$, Lemma
3.6 then tells us that Step 2 takes time
$O(m^{4}\mathcal{E}^{2}\log^{2}\mathcal{E})$, which is bounded from above by

$\displaystyle
O\\!\left(m^{17}\log^{2}(m)900^{m}\log^{2}(mB)\right)\cdot\left(O(\log(B)+m\log
H)\right)^{2m}$
$\displaystyle=O\\!\left(901^{m}\log^{2}(mB)\right)\cdot\left(O(\log(B)+m\log
H)\right)^{2m}$ (9) $\displaystyle=O(\log(B)+m\log H)^{2m+2}$

Thanks to Theorem 3.5, a simple over-estimate for the complexity of Step 6 is

$\displaystyle O(m^{2}\log^{2}(mB)\log^{2}(m\log(BH)))\cdot O(\log(B)+m\log
H)^{m},$

so then the time spent in (each run of) Steps 4–7 in total is

$\displaystyle O(m^{3}\log^{2}(mB)\log^{2}(m\log(BH)))\cdot O(\log(B)+m\log
H)^{m}.$

Since $k-1\\!\leq\\!m-1$, Steps 3–14 then take time no greater than

$\displaystyle O(m^{4}\log^{2}(mB)\log^{2}(m\log(BH)))\cdot O(\log(B)+m\log
H)^{m}.$

We thus see, from comparison to Estimate (4), that Step 2 in fact dominates
the asymptotic complexity of our entire algorithm, so our complexity estimate
follows. $\blacksquare$

We can now state our algorithm for counting the positive roots of circuit
systems:

######  Algorithm 4.3.

Input: Polynomials $f_{1},\ldots,f_{n}\\!\in\\!\mathbb{Z}\\!\left[x^{\pm
1}_{1},\ldots,x^{\pm 1}_{n}\right]$ with
$A\\!:=\\!\bigcup_{i}\mathrm{Supp}(f_{i})$ a circuit and $\\#A\\!=\\!n+2$.
Output: The number of roots of $F\\!=\\!(f_{1},\ldots,f_{n})$ in
$\mathbb{R}^{n}_{+}$.
Description:

  * 0.

Find the unique non-degenerate sub-circuit $\Sigma$ of $A$, re-index the
points of $A$ so that $\Sigma\\!=\\!\\{a_{1},\ldots,a_{m},a_{n+1},a_{n+2}\\}$,
translate $a_{1},\ldots,a_{n+1}$ by $-a_{n+2}$, and set
$a_{n+2}\\!:=\\!\mathbf{O}$.

  * 1.

Letting $[c_{i,j}]$ be the coefficient matrix of $F$, check whether all the
$n\times n$ sub-matrices of
$\begin{bmatrix}c_{1,1}&\cdots&c_{1,n}&c_{1,n+2}\\\ \vdots&\ddots&\vdots\\\
c_{n,1}&\cdots&c_{n,n}&c_{n,n+2}\end{bmatrix}$ are non-singular, and whether
$\begin{bmatrix}c_{i,n+1}&c_{i,n+2}\\\ c_{j,n+1}&c_{j,n+2}\end{bmatrix}$ is
non-singular for all $i\\!\neq\\!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\\!=\\!\mathbf{O}$ to a system of equations of the form
$G\\!=\\!\mathbf{O}$, where $G\\!:=\\!(g_{1},\ldots,g_{n})$ and
$g_{i}(x)\\!:=\\!x^{a_{i}}-\gamma_{i,1}x^{a_{n+1}}-\gamma_{i,0}$ for all $i$.

  * 3.

Let $b\\!\in\\!\mathbb{Z}^{(m+2)\times 1}$ be the unique (up to sign) minimal
circuit relation of $\Sigma$, and define
$\displaystyle{L(u)\\!:=\\!b_{m+1}\log|u|+\sum\limits^{m}_{i=1}b_{i}\log|\gamma_{i,1}u+\gamma_{i,0}|}$
and
$\displaystyle{I\\!:=\\!\\{u\\!\in\\!\mathbb{R}_{+}\;|\;\gamma_{i,1}u+\gamma_{i,0}\\!>\\!0\text{
for all }i\\!\in\\!\\{1,\ldots,n\\}\\}}$.

  * 4.

Via Algorithm 4.1 and Proposition 2.20, compute the number, $N$, of roots of
$L$ in $I$, and Output $N$.

######  Lemma 4.4.

Algorithm 4.3 is correct and runs in time $O(n\log(nd)+n^{2}\log H)^{2n+4}$,
where $d$ is the largest absolute value of an entry of $A$ and
$H\\!:=\\!\max_{i}|f_{i}|_{\infty}$.

Proof: Letting $u_{0}\\!:=\\!\inf I$, $u_{\infty}\\!:=\\!u_{k}\\!:=\\!\sup I$,
and letting $u_{1}\\!<\cdots<\\!u_{k-1}$ be the critical points of $L$ in $I$
as before, note that the sign of $\lim_{u\rightarrow u^{+}_{0}}L(u)$ is either
$-b_{m+1}$ (if $u_{0}\\!=\\!0$) or $-b_{i^{\prime}}$ with $i^{\prime}$ the
unique index such that
$u_{0}\\!=\\!-\gamma_{i^{\prime},0}/\gamma_{i^{\prime},1}$. (This index is
unique thanks to Step 1 ensuring the $2\times 2$ minor condition.) Similarly,
$\lim_{u\rightarrow u^{-}_{k}}L(u)$ is simply the sign of
$-b_{i^{\prime\prime}}$ (resp. $b_{1}+\cdots+b_{m+1}$) for some easily
computable unique index $i^{\prime\prime}\\!\in\\!\\{1,\ldots,m+1\\}$ if
$u_{k}\\!<\\!\infty$ (resp. $u_{k}\\!=\\!+\infty$). 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+\omega}\log^{2}(ndH))$. This will not be the dominant part of the
algorithm: Observingthat $h(\gamma_{i,j})\\!=\\!O(n\log(nH))$ and
$h(b_{i})\\!=\\!O(n\log(nd))$ for all $i,j$, Lemma 4.2 then tellsus that
applying Algorithm 4.1 and Proposition 2.20 (with $m\\!\leq\\!n+1$) takes
time$O(n\log(nd)+n^{2}\log(nH))^{2n+4}$. $\blacksquare$

We are now ready to state the analogue of Lemma 4.4 for counting roots in
${(\mathbb{R}^{*})}^{n}$:

######  Lemma 4.5.

Given any $(n+2)$-nomial $n\times n$ system
$F\\!=\\!(f_{1},\ldots,f_{n})\\!\in\\!\mathbb{Z}\\!\left[x^{\pm
1}_{1},\ldots,x^{\pm 1}_{n}\right]^{n}$ supported on a circuit $A$ with
cardinality $n+2$, we can count exactly the number of roots of $F$ in
${(\mathbb{R}^{*})}^{n}$ in time $O(n\log(nd)+n^{2}\log H)^{2n+4}$, where $d$
is the largest absolute value of an entry of $A$ and
$H\\!:=\\!\max_{i}|f_{i}|_{\infty}$.

Proof: The proof is almost identical to that of Lemma 4.4, save that we apply
Corollary 2.23 instead of Proposition 2.20, Lemma 2.21 instead of Lemma 2.16,
and that we use a modified version of Algorithm 4.3.

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 $\Sigma$ of $A$ and underlying
minimal circuit relation
$b\\!\in\\!\mathbb{Z}^{(m+2)\times 1}$, re-index the points of $A$ so that
$\Sigma\\!=\\!\\{a_{1},\ldots,a_{m},a_{n+1},a_{n+2}\\}$ and $b_{m+1}$ is
odd, translate $a_{1},\ldots,a_{n+1}$ by $-a_{n+2}$, and set
$a_{n+2}\\!:=\\!\mathbf{O}$.

3’. Define
$\displaystyle{L(u)\\!:=\\!b_{m+1}\log|u|+\sum\limits^{m}_{i=1}b_{i}\log|\gamma_{i,1}u+\gamma_{i,0}|}$

4’. Via Algorithm 4.1, compute the number $\mathcal{N}$ from Corollary 2.23
and the number of
degenerate roots of $L$ in $\mathbb{R}$. Output their sum.

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}+\cdots+b_{m+1}$ (if the pole is $\pm\infty$).
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\cdot n^{2})$
to compute the signs of $\Lambda(u)$ and the $\Gamma^{\prime}(u_{i})$. This is
negligible compared to the other steps, so our final asymptotic complexity
bound remains the same. $\blacksquare$

######  Remark 4.6.

While we could have simply applied Algorithm 4.3 $2^{n}$ times (once for each
orthant of ${(\mathbb{R}^{*})}^{n}$), our proof above is more practical: It
enables complexity polynomial in $n$ for root counting in
${(\mathbb{R}^{*})}^{n}$ should sufficiently sharp new diophantine estimates
become available (see Remark 1.5 from the introduction). $\diamond$

##  5\. Affine Roots and Proving Theorem 1.1

To conclude, we’ll first need to recall some observations regarding sparse
resultants and roots of $t$-nomial $(n+1)\times n$ (over-determined) systems
on coordinate subspaces. For further details on sparse resultants we refer the
reader to [GKZ94].

######  Proposition 5.1.

If $A\\!\subset\\!\mathbb{Z}^{n}$ is a circuit and $X$ is any coordinate
subspace of $\mathbb{R}^{n}$ then $A\cap X$ is either empty, the vertex set of
a simplex, or a circuit. $\blacksquare$

######  Lemma 5.2.

[GKZ94, Ch. 8] Suppose
$A\\!=\\!\\{a_{1},\ldots,a_{t}\\}\\!\subset\\!\mathbb{Z}^{n}$ has cardinality
$t\\!\leq\\!n+2$ and does not lie in any affine hyperplane, and
$F\\!=\\!(f_{1},\ldots,f_{n+1})$ with
$f_{i}(x)\\!=\\!\sum^{n+1}_{j=1}c_{i,j}x^{a_{j}}$ for all $i$ and the
$c_{i,j}$ algebraically independent indeterminates. Then there is a unique (up
to sign) polynomial
$\Delta_{A}\\!\in\\!\mathbb{Z}\\!\left[c_{i,j}\;|\;(i,j)\\!\in\\!\\{1,\ldots,n\\}\times\\{1,\ldots,t\\}\right]\setminus\\{0\\}$,
of minimal degree, such that $\left[[c_{i,j}]\\!\in\\!\mathbb{C}^{n\times
t}\right.$ and
$\left.\Delta_{A}(\ldots,c_{i,j},\ldots)\\!\neq\\!0\right]\Longrightarrow F$
has no roots in ${(\mathbb{C}^{*})}^{n}$. In particular, if $t\\!=\\!n+1$
(resp. $t\\!=\\!n+2$) then $\Delta_{A}\\!=\\!\det[c_{i,j}]$ (resp.
$\deg\Delta_{A}\\!\leq\\!n\cdot n!V$),  where $V$ is the volume of the convex
hull of $A$, normalized so that the unit $n$-cube has volume $1$.
$\blacksquare$

The polynomial $\Delta_{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:

######  Lemma 5.3.

Suppose $F\\!=\\!(f_{1},\ldots,f_{n})\\!\in\\!\left(\mathbb{C}\\!\left[x^{\pm
1}_{1},\ldots,x^{\pm 1}_{n}\right]\right)^{n}$ is a $t$-nomial $n\times n$
polynomial system supported on a fixed $A\\!\subset\\!\mathbb{Z}^{n}$ and
$\mathrm{Supp}(f_{i})\\!=\\!A$ for all $i$. Let
$\pi_{i}:\mathbb{R}^{n}\longrightarrow\mathbb{R}$ denote the projection
sending $(x_{1},\ldots,x_{n})\mapsto x_{i}$. Then:
1\. For any $i\\!\in\\!\\{1,\ldots,n\\}$ we have that
$\min\pi_{i}(A)\\!>\\!0\Longrightarrow F$ vanishes on all of
$(\mathbb{C}^{*})^{i-1}\times\\{0\\}\times(\mathbb{C}^{*})^{n-i}$.
2\. If $\min\pi_{i}(A)\\!\geq\\!0$ for all $i\\!\in\\!\\{1,\ldots,\ell\\}$ and
no points of $A$ lie on the coordinate subspace
$\\{x_{1}\\!=\cdots=\\!x_{\ell}\\!=\\!0\\}$ then $F$ vanishes on all of
$\\{0\\}^{\ell}\times(\mathbb{C}^{*})^{n-\ell}$.
3\. For any $i\\!\in\\!\\{1,\ldots,n\\}$ we have that
$\min\pi_{i}(A)\\!<\\!0\Longrightarrow F$ has no complex roots in the
coordinate hyperplane $\\{x_{i}\\!=\\!0\\}$.
4\. If $\min\pi_{i}(A)\\!\geq\\!0$ for all $i\\!\in\\!\\{1,\ldots,\ell\\}$ and
$A\cap\\{x_{1}\\!=\\!\cdots=\\!x_{\ell}\\!=\\!0\\}\\!\neq\\!\emptyset$ then
$F$ generically has no roots in
$\\{0\\}^{\ell}\times(\mathbb{C}^{*})^{n-\ell}$.

######  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\times 3$ system

$\displaystyle\left(x_{1}x_{2}+x_{2}x_{3}+x_{3}x_{1}-3x_{1}x_{2}x_{3},\right.$
$\displaystyle\mbox{}x_{1}x_{2}+2x_{2}x_{3}+4x_{3}x_{1}-7x_{1}x_{2}x_{3},$
$\displaystyle\left.x_{1}x_{2}+3x_{2}x_{3}+9x_{3}x_{1}-13x_{1}x_{2}x_{3}\right)$

is 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\pi_{i}(A)\\!=\\!0$ for all $i$, $A$ does not intersect any of
the coordinate axes. Hence the infinitude of real roots for our example.
$\diamond$

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 $\left(\mathbb{C}\\!\left[x^{\pm 1}_{\ell+1},\ldots,x^{\pm
1}_{n}\right]\right)[x_{1},\ldots,x_{\ell}]$: 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},\ldots,x_{\ell})$. 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}\\!=\cdots=\\!x_{\ell}\\!=\\!0$ in $F$ results in such an $F$
generically becoming an (over-determined) $n\times(n-\ell)$ system. In
particular, for $F$ to fail to have roots, it is enough for the first
$n-\ell+1$ polynomials to fail to have a common root. So by Lemma 5.2 we are
done. $\blacksquare$

###  5.1. The Proof of Theorem 1.1

The cases of root counting in $\mathbb{R}^{n}_{+}$ and
${(\mathbb{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 $\mathbb{R}^{n}$, let us first compute $\min\pi_{i}(A)$ for
all $i\\!\in\\!\\{1,\ldots,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},\ldots,A_{n}$ and $A_{1}\cap\cdots\cap A_{n}$ within the
same time bound as well. Since we have already derived how to efficiently
count roots in ${(\mathbb{R}^{*})}^{n}$ and $\mathbb{R}^{n}_{+}$, it suffices
to prove that we can count roots on all the proper coordinate subspaces of
$\mathbb{R}^{n}$ within our stated time bound.

By Assertion (3) of Lemma 5.3, $\min\pi_{i}(A)\\!<\\!0$ for all $i$ implies
that all the roots of $F$ in $\mathbb{R}^{n}$ lie in ${(\mathbb{R}^{*})}^{n}$.
So, without loss of generality, we can re-order variables and assume
$\min\pi_{i}(A)\\!<\\!0$ for all $i\\!\geq\\!\ell+1\\!\geq\\!2$.

By Assertion (1) of Lemma 5.3, if $\min\pi_{i}(A)\\!>\\!0$ for some
$i\\!\in\\!\\{1,\ldots,\ell\\}$ then $F$ has infinitely many real roots. So we
may assume that $\min\pi_{i}(A)\\!=\\!0$ for all
$i\\!\in\\!\\{1,\ldots,\ell\\}$.

Observe now that if $\ell\\!=\\!n$ (i.e., if $\min\pi_{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 $\ell\\!=\\!n$ we may assume that $A_{i}$
is non-empty for all $i$. Since $\mathrm{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 $\mathbf{O}$. Since $F$
vanishes at $\mathbf{O}$ if and only if $A_{1}\cap\cdots\cap A_{n}$ is non-
empty, the case $\ell\\!=\\!n$ is done and we assume now that $\ell\\!<\\!n$.
In other words, we now need only check for roots on the coordinate subspace
$\\{x_{1}\\!=\cdots=\\!x_{\ell}\\!=\\!0\\}$ of $\mathbb{R}^{n}$.

Now, should $A_{1}\cap\cdots\cap A_{\ell}$ be empty, then Assertion (2) of
Lemma 5.3 tells us that $F$ has infinitely many real roots. So we may assume
$A_{1}\cap\cdots\cap A_{\ell}\\!\neq\\!\emptyset$. Since
$\mathrm{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
$\mathbb{R}^{n}$ containing $\\{x_{1}\\!=\cdots=\\!x_{\ell}\\!=\\!0\\}$.

We have thus shown how to count roots in all coordinate subspaces of
$\mathbb{R}^{n}$. In particular, we see that the complexity of counting roots
in $\mathbb{R}^{n}$ is asymptotically the same as our complexity bound for
counting in ${(\mathbb{R}^{*})}^{n}$, since the only additional work is
computing the $\pi_{i}(A)$, the $A_{i}$, $A_{1}\cap\cdots\cap A_{\ell}$, and
$A_{1}\cap\cdots\cap A_{n}$, which takes time neglible compared to our main
bound. $\blacksquare$

A consequence of our preceding proof is that the additional genericity
condition needed to efficiently count roots in $\mathbb{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 $\mathbb{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}+\binom{n}{2}d^{n-2}+\cdots+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
$\left\\{-\left\lceil\frac{n^{2}+n+(d+1)^{n}-1}{2\varepsilon}\right\rceil,\ldots,\left\lceil\frac{n^{2}+n+(d+1)^{n}-1}{2\varepsilon}\right\rceil\right\\}$
is enough to make our additional genericity condition hold with probability
greater than $1-\varepsilon$.

## 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.

## Farewell to a Friend

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.

## References

  * [Ahr99] Timm Ahrendt, “Fast computations of the exponential function,” in proceedings of STACS ’99 (16th annual conference on Theoretical aspects of computer science), pp. 302–312, Springer-Verlag Berlin, 1999.
  * [BS96] Eric Bach and Jeff Shallit, Algorithmic Number Theory, Vol. I: Efficient Algorithms, MIT Press, Cambridge, MA, 1996.
  * [Bak77] Alan Baker, “The Theory of Linear Forms in Logarithms,” in Transcendence Theory: Advances and Applications: proceedings of a conference held at the University of Cambridge, Cambridge, Jan.–Feb., 1976, Academic Press, London, 1977.
  * [Bak98] Alan Baker, “Logarithmic forms and the $abc$-conjecture,” Number theory (Eger, 1996), pp. 37–44, de Gruyter, Berlin, 1998.
  * [BW93] Alan Baker and Gisbert Wustholtz, “Logarithmic forms and group varieties,” J. Reine Angew. Math. 442 (1993), pp. 19–62.
  * [BPR06a] Saugata Basu; Richard Pollack; Marie-Françoise Roy, “Computing the dimension of a semi-algebraic set,” reprinted in J. Math. Sci. (N.Y.) 134 (2006), no. 5, pp. 2346–2353.
  * [BPR06b] Saugata Basu; Richard Pollack; and Marie-Françoise Roy, Algorithms in real algebraic geometry, 2nd edition, Algorithms and Computation in Mathematics, 10, Springer-Verlag, Berlin, 2006
  * [BHNS16] Daniel J. Bates; Jonathan D. Hauenstein; Matthew E. Niemerg; Frank Sottile, “Software for the Gale transform of fewnomial systems and a Descartes rule for fewnomials,” Numer. Algorithms 73 (2016), no. 1, pp. 281–304.
  * [BHSW13] Daniel J. Bates, Jon D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler, Numerically solving polynomial systems with Bertini, Software, Environments, and Tools 25, SIAM, 2013.
  * [BKR86] Michael Ben-Or; Dexter Kozen; and John Reif, “The Complexity of Elementary Algebra and Geometry,” J. Computer and System Sciences 32 (1986), pp. 251–264.
  * [Ber03] Daniel J. Bernstein, “Computing Logarithm Intervals with the Arithmetic-Geometric Mean Iterations,” available from http://cr.yp.to/papers.html  .
  * [BBS06] Benoit Bertrand; Frédéric Bihan; and Frank Sottile, “Polynomial Systems with Few Real Zeroes,” Mathematisches Zeitschrift, 253 (2006), no. 2, pp. 361–385.
  * [Bih11] Frédéric Bihan, Topologie des variétés creuses, Habilitation thesis, Université de Savoie, France, 2011.
  * [BD17] Frédéric Bihan and Alicia Dickenstein, “Descartes’ Rule of Signs for Polynomial Systems Supported on Circuits,” International Mathematics Research Notices, Vol. 2017, Issue 22, November 2017, Pages 6867–6893.
  * [BDF20] Frédéric Bihan; Alicia Dickenstein; Jens Forsgård, “Optimal Descartes’ rule of signs for systems supported on circuits,” Math ArXiV preprint arXiv:2010.09165v1  .
  * [BDG19] Frédéric Bihan; Alicia Dickenstein; and Magalí Giaroli, “Regions of multistationarity in cascades of Goldbeter-Koshland loops,” J. Math. Biol. (2019) Vol. 78(4), pp. 1115–1145.
  * [BDG20a] Frédéric Bihan; Alicia Dickenstein; and Magalí Giaroli, “Lower bounds for positive roots and regions of multistationarity in chemical reaction networks,” J. Algebra (2020), Vol. 542, pp. 367-411.
  * [BDG20b] Frédéric Bihan; Alicia Dickenstein; and Magalí Giaroli, “Sign conditions for the existence of at least one positive solution of a sparse polynomial system,” Advances in Mathematics, to appear, 2020.
  * [BRS09] Frédéric Bihan; J. Maurice Rojas; Casey E. Stella, “Faster Real Feasibility via Circuit Discriminants,” proceedings of International Symposium on Symbolic and Algebraic Computation (ISSAC 2009, July 28–31, Seoul, Korea), pp. 39–46, ACM Press, 2009.
  * [BS07] Frédéric Bihan and Frank Sottile, “New Fewnomial Upper Bounds from Gale Dual Polynomial Systems,” Moscow Mathematical Journal, 7 (2007), no. 3, pp. 387–407.
  * [BCSS98] Lenore Blum; Felipe Cucker; Mike Shub; and Steve Smale, Complexity and Real Computation, Springer-Verlag, 1998.
  * [BG06] Enrico Bombieri and Walter Gubler, Heights in Diophantine Geometry, new mathematical monographs: 4, Cambridge University Press, 2006.
  * [BBK09] Enrico Bombieri; Jean Bourgain; and Sergei Konyagin, “Roots of polynomials in subgroups of $\mathbb{F}^{*}_{p}$ and applications to congruences,” Int. Math. Res. Not. IMRN 2009, no. 5, pp. 802–834.
  * [BB88] John M. Borwein and Peter B. Borwein; “On the Complexity of Familiar Functions and Numbers,” SIAM Review, Vol. 30, No. 4, (Dec., 1988), pp. 589–601.
  * [Bre76] Richard P. Brent, “Fast Multiple-Precision Evaluation of Elementary Functions,” Journal of the Association for Computing Machinery, vol. 23, No. 2, April 1976, pp. 242–251.
  * [BMS06] Yan Bugeaud; Maurice Mignotte; and Samir Siksek, “Classical and modular approaches to exponential Diophantine equations, I, Fibonacci and Lucas perfect powers,” Ann. of Math. (2) 163 (2006), pp. 969–1018.
  * [BET19] Peter Bürgisser, Alperen A. Ergür, and Josué Tonelli-Cueto, “On the Number of Real Zeros of Random Fewnomials,” SIAM Journal on Applied Algebra and Geometry, 3(4), pp. 721–732, 2019.
  * [CFKLLS00] Ran Canetti; John B. Friedlander; Sergey Konyagin; Michael Larsen; Daniel Lieman; and Igor E. Shparlinski, “On the statistical properties of Diffie-Hellman distributions,” Israel J. Math. 120 (2000), pp. 23–46.
  * [Can88] John F. Canny, “Some Algebraic and Geometric Computations in PSPACE,” Proc. 20${}^{\text{\text@underline{th}}}$ ACM Symp. Theory of Computing, Chicago (1988), ACM Press.
  * [CD07] Eduardo Cattani and Alicia Dickenstein, “Counting solutions to binomial complete intersections,” Journal of Complexity 23 (2007), pp. 82–107.
  * [CS16] Venkat Chandrasekaran and Parikshit Shah, “Relative Entropy Relaxations for Signomial Optimization,” SIAM J. Optim., Vol. 26, No. 2, pp. 1147–1173, 2016.
  * [CL14] Tianran Chen and Tien-Yien Li, “Solutions to Systems of Binomial Equations,” Annales Mathematicae Silesianae 28 (2014), pp. 7–34.
  * [CGRW17] Qi Cheng; Shuhong Gao; J. Maurice Rojas; and Daqing Wan, “Sparse Univariate Polynomials with Many Roots Over a Finite Field,” Finite Fields and their Applications, Vol. 46, July 2017, pp. 235–246.
  * [CG84] Alexander L. Chistov and Dima Yu Grigoriev, “Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields,” Lect. Notes Comp. Sci. 176, Springer-Verlag (1984).
  * [CLRS09] Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; and Clifford Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009.
  * [CKMW08] Felipe Cucker, Teresa Krick, Gregorio Malajovich, and Mario Wschebor, “A numerical algorithm for zero counting. I: Complexity and Accuracy,” J. Complexity, Vol. 24 (2008), pp. 582–605.
  * [CKS18] Felipe Cucker, Teresa Krick, Michael Shub, “Computing the homology of real projective sets,” Found. Comput. Math. (2018) 18: 929-970.
  * [DGRM20] Alicia Dickenstein; Magalí Giaroli; Rick Rischter; Mercedes Pérez Millán, “Parameter regions that give rise to $2[n/2]+1$ positive steady states in the $n$-site phosphorylation system,” Mathematical Biosciences and Engineering, 2019, 16(6):7589–7615.
  * [DMST19] Alicia Dickenstein; Mercedes Pérez Millán; Anne Shiu; and Xiaoxian Tang, “Multistationarity in Structured Reaction Networks,” Bulletin of Mathematical Biology (2019) 81(5), 1527-1581.
  * [DKdW18] Mareike Dressler, Adam Kurpisz, and Timo de Wolff, “Optimization over the boolean hypercube via sums of nonnnegative circuit polynomials,” Math ArXiV preprint arXiv:1802.10004 .
  * [DS41] R. J. Duffin and A. C. Schaeffer, “A refinement of an inequality of the brothers Markoff,” Transactions of the American Mathematical Society, 50, pp. 517–528, 1941.
  * [Emi20] Ioannis Z. Emiris, MixedVolume-SparseResultants software package,
https://github.com/iemiris/MixedVolume-SparseResultants  .

  * [EPR19] Alperen A. Ergür, Grigoris Paouris, and J. Maurice Rojas, “Probabilistic Condition Number Estimates for Real Polynomial Systems I: A Broader Family of Distributions,” Foundations of Computational Mathematics, Feb. 2019, Vol. 19, No. 1, pp. 131–157.
  * [EPR20] Alperen A. Ergür, Grigoris Paouris, and J. Maurice Rojas, “Probabilistic Condition Number Estimates for Real Polynomial Systems II: Structure and Smoothed Analysis,” Math ArXiV preprint arXiv:1809.03626  .
  * [For19] Jens Forsgård, “Defective dual varieties or real spectra,” Journal of Algebraic Combinatorics, February 2019, Volume 49, Issue 1, pp. 49–67.
  * [vzGG13] Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013.
  * [GKZ94] Israel M. Gel’fand, Mikhail M. Kapranov, and Andrei V. Zelevinsky, Discriminants, Resultants and Multidimensional Determinants, Birkhäuser, Boston, 1994.
  * [Gra99] David J. Grabiner, “Descartes’ Rule of Signs: Another Construction,” The American Mathematical Monthly, Vol. 106, No. 9 (Nov. 1999), pp. 854–856.
  * [Gre16] Bruno Grenet, “Bounded-degree factors of lacunary multivariate polynomials,” J. Symb. Comput. 75, pp. 171–192, 2016 (ISSAC 2014 special issue).
  * [Har80] Robert M. Hardt, “Semi-Algebraic Local-Triviality in Semi-Algebraic Mappings,” American Journal of Mathematics, Vol. 102, No. 2 (Apr., 1980), pp. 291–302.
  * [HvdH19] David Harvey and Joris van der Hoeven, “Integer multiplication in time $O(n\log n)$,” HAL preprint https://hal.archives-ouvertes.fr/hal-02070778  .
  * [Her51] Charles Hermite, “Sur l’introduction des variables continues dans la théorie des nombres,” J. Reine Angew. Math., 41:191–216, 1851.
  * [HS95] Birkett Huber and Bernd Sturmfels, “A Polyhedral Method for Solving Sparse Polynomial Systems,” Math. Comp. 64 (1995), no. 212, pp. 1541–1555.
  * [Kho80] Askold G. Khovanskiĭ, “A class of systems of transcendental equations,” Dokl. Akad. Nauk SSSR 255 (1980), no. 4, pp. 804–807.
  * [Kho91] Askold G. Khovanskiĭ, Fewnomials, AMS Press, Providence, Rhode Island, 1991.
  * [KPT15a] Pascal Koiran; Natacha Portier; and Sebastian Tavenas, “On the intersection of a sparse curve and a low-degree curve: A polynomial version of the lost theorem,” Discrete and Computational Geometry, 53(1):48-63, 2015.
  * [KPT15b] Pascal Koiran; Natacha Portier; and Sebastian Tavenas, “A Wronskian approach to the real tau-conjecture,” Journal of Symbolic Computation, 68(2):195-214, 2015.
  * [Kro95] Leopold Kronecker, Werke, Vol. 1, Leipzig, Teubner (1895).
  * [Kus77] Anatoly Georgievich Kushnirenko, “Newton Polytopes and the Bézout Theorem,” Functional Analysis and its Applications (translated from Russian), vol. 10, no. 3, July–September (1977), pp. 233–235.
  * [LL11] Tsung-Lin Lee and Tien-Yien Li, “Mixed volume computation in solving polynomial systems,” in Randomization, Relaxation, and Complexity in Polynomial Equation Solving, Contemporary Mathematics, vol. 556, pp. 97–112, AMS Press, 2011.
  * [Leg14] François Legall, “Powers of tensors and fast matrix multiplication,” Proceedings of ISSAC (International Symposium on Symbolic and Algebraic Computation) 2014, ACM Press, pp. 296–303, 2014.
  * [LRW03] Tien-Yien Li; J. Maurice Rojas; and Xiaoshen Wang, “Counting Real Connected Components of Trinomial Curves Intersections and m-nomial Hypersurfaces,” Discrete and Computational Geometry, 30:379–414 (2003).
  * [Lio51] Joseph Liouville, “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,” Journal Math. Pures et Appl., 16 (1851), pp. 133-142.
  * [Mah64] Kurt Mahler, “An inequality for the discriminant of a polynomial,” The Michigan Mathematical Journal, 11(3):257–262, 1964.
  * [Mar89] A. A. Markov, “On a certain problem of D. I. Mendeleiff,” (in Russian) Utcheniya Zapiski Imperatorskoi Akademii Nauk, 62, pp. 1–24, 1889.
  * [Mas85] David W. Masser, “Open Problems,” Prod. Symp. Analytic Number Theory (ed. by W. W. L. Chen), Imperial Coll. London, 1985.
  * [Mat00] E. M. Matveev, “An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers, II”, Izv. Ross. Akad. Nauk Ser. Mat. 64 (2000), pp. 125–180; English transl. in Izv.l Math. 64 (2000), pp. 1217–1269.
  * [Mig82] Maurice Mignotte, “Some Useful Bounds,” Computing, Suppl. 4, pp. 259–263 (1982), Springer Verlag.
  * [Mon20] Pinaki Mondal, “How many zeroes? Counting the number of solutions of systems of polynomials via geometry at infinity,” Math ArXiV preprint 1806.05346
  * [Nes03] Yuri Nesterenko, “Linear forms in logarithms of rational numbers,” Diophantine approximation (Cetraro, 2000), pp. 53–106, Lecture Notes in Math., 1819, Springer, Berlin, 2003.
  * [Nit13]

Abderrahmane Nitaj, The $abc$ Conjecture Home Page,
https://nitaj.users.lmno.cnrs.fr/abc.html

  * [Oes88] Joseph Oesterlé, “Nouvelles approches du ‘Théorème’ de Fermat,” Astérisque 161-2 (1988), pp. 165–186.
  * [PPR19] Grigoris Paouris, Kaitlyn Phillipson, and J. Maurice Rojas, “A Faster Solution to Smale’s 17th Problem I: Real Binomial Systems,” in proceedings of ISSAC 2019 (July 15-18, 2019, Beihang University, Beijing, China), ACM Press, 2019.
  * [PRT09] Philippe Pébay; J. Maurice Rojas; and David C. Thompson, “Optimization and ${\mathbf{NP}}_{\mathbb{R}}$-completeness of certain fewnomials,” proceedings of SNC 2009 (August 3–5, 2009, Kyoto, Japan), pp. 133–142, ACM Press, 2009.
  * [PRS93] Paul Pedersen, Marie-Françoise Roy, and Aviva Szpirglas, “Counting real zeros in the multivariate case,” in proceedings of Computational algebraic geometry (Nice, 1992), pp. 203–224, Progr. Math., 109, Birkhäuser Boston, Boston, MA, 1993.
  * [PR13] Kaitlyn Phillipson and J. Maurice Rojas, “Fewnomial Systems with Many Roots, and an Adelic Tau Conjecture,” in proceedings of Bellairs workshop on tropical and non-Archimedean geometry (May 6–13, 2011, Barbados), Contemporary Mathematics, vol. 605, pp. 45–71, AMS Press, 2013.
  * [Pra04] Victor V. Prasolov, Problems and Theorems in Linear Algebra, translations of mathematical monographs, vol. 134, AMS Press, 2004.
  * [RS02] Qazi Ibadur Rahman and Gerhard Schmeisser, Analytic Theory of Polynomials, London Mathematical Society Monographs 26, Oxford Science Publications, 2002.
  * [Ren92] Jim Renegar, “ On the Computational Complexity and Geometry of the First-Order Theory of the Reals, I–III,” J. Symbolic Comput. 13 (1992), no. 3, pp. 255–352.
  * [Roj99] J. Maurice Rojas, “Solving degenerate sparse polynomial systems faster,” J. Symbolic Comput. 28 (1999), no. 1-2, pp. 155–186.
  * [Roj03] J. Maurice Rojas, “Why Polyhedra Matter in Non-Linear Equation Solving,” Contemporary Mathematics, vol. 334, pp. 293–320, AMS Press, 2003.
  * [Rou99] Fabrice Rouillier, “Solving zero-dimensional systems through the rational univariate representation,” Appl. Algebra Engrg. Comm. Comput. 9 (1999), no. 5, pp. 433–461.
  * [Sag11] Michael Sagraloff, “A General Approach to Isolating Roots of a Bit-stream Polynomial,” Mathematics in Computer Science 4, 481 (2010), Springer-Verlag.
  * [Sal76] Eugene Salamin, “Computation of $\pi$ using arithmetic-geometric mean,” Math. Comput., 30 (1976), pp. 565–570
  * [Sch86] Alexander Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, 1986.
  * [Sch80] Jacob T. Schwartz, “Fast Probabilistic Algorithms for Verification of Polynomial Identities,” J. of the ACM 27, 701–717, 1980.
  * [SL54] David Eugene Smith and Marcia L. Latham, The Geometry of René Descartes, translated from the French and Latin (with a facsimile of Descartes’ 1637 French edition), Dover Publications Inc., New York (1954).
  * [Sto00] Arne Storjohann, “Algorithms for Matrix Canonical Forms,” doctoral dissertation, Swiss Federal Institute of Technology, Zurich, 2000.
  * [V-W12] Virginia Vassilevska-Williams, “Multiplying matrices faster than Coppersmith-Winograd,” Proceedings of STOC (ACM Symposium on Theory of Computation) 2012, ACM Press, pp. 887–898, 2012.
  * [Ver10] Jan Verschelde, “Polynomial Homotopy Continuation with PHCpack”, ACM Communications in Computer Algebra 44(4):217-220, 2010.