Search

We consider positive solutions to parametrized systems of generalized polynomial equations (with real exponents and positive parameters). By a fundamental result obtained in parallel work, polynomial systems are determined by geometric objects, rather than matrices: a polytope $P$ (arising from the coefficient matrix) and two subspaces representing monomial differences and dependencies (arising from the exponent matrix). The dimension of the latter subspace, the monomial dependency $d$, is crucial. Indeed, we rewrite $\textit{polynomial}$ equations in terms of $d$ $\textit{binomial}$ equations on the coefficient polytope $P$, involving $d$ monomials in the parameters. We further study the solution set on $P$ using methods from analysis such as sign-characteristic functions and Wronskians. In this work, we present first applications to fewnomial systems through five (classes of) examples. In particular, we study (i) $n$ trinomials involving ${n+2}$ monomials in $n$ variables, having dependency $d=1$, and (ii) one trinomial and one $t$-nomial (with $t\ge3$) in two variables, having $d=t-1\ge2$. For (i), we bound the number of positive solutions using the number of roots of a univariate polynomial of degree at most $n$. We also show that this number is always less than or equal to the number of sign changes in an optimal Descartes' rule given in Bihan et al. (2021). For (ii), we improve upper bounds given in Li et al. (2003) and Koiran et al. (2015). Further, for two trinomials ($t=3$), we refine the known upper bound of five in terms of the exponents, and we find an example with five positive solutions that is even simpler than the smallest "Haas system"., Comment: author note: this manuscript and arXiv:2306.13916 are parallel works; there is overlap in the outline of the underlying theory, required for a self-contained presentation. more specifically, in this manuscript, we apply results from arXiv:2306.13916

Let $\mathcal{C}_d\subset \mathbb{C}^{d+1}$ be the space of non-singular, univariate polynomials of degree $d$. The Vi\`{e}te map $\mathscr{V} : \mathcal{C}_d \rightarrow Sym_d(\mathbb{C})$ sends a polynomial to its unordered set of roots. It is a classical fact that the induced map $\mathscr{V}_*$ at the level of fundamental groups realises an isomorphism between $\pi_1(\mathcal{C}_d)$ and the Artin braid group $B_d$. For fewnomials, or equivalently for the intersection $\mathcal{C}$ of $\mathcal{C}_d$ with a collection of coordinate hyperplanes in $\mathbb{C}^{d+1}$, the image of the map $\mathscr{V} _* : \pi_1(\mathcal{C}) \rightarrow B_d$ is not known in general. In the present paper, we show that the map $\mathscr{V} _*$ is surjective provided that the support of the corresponding polynomials spans $\mathbb{Z}$ as an affine lattice. If the support spans a strict sublattice of index $b$, we show that the image of $\mathscr{V} _*$ is the expected wreath product of $\mathbb{Z}/b\mathbb{Z}$ with $B_{d/b}$. From these results, we derive an application to the computation of the braid monodromy for collections of univariate polynomials depending on a common set of parameters., Comment: 18 pages, 7 figures. Version 3: we fixed a gap in the proof of Proposition 4.1

Consider a system $f_1(x)=0,\ldots,f_n(x)=0$ of $n$ random real polynomials in $n$ variables, where each $f_i$ has a prescribed set of terms described by a set $A\subseteq \mathbb{N}^n$ of cardinality $t$. Assuming that the coefficients of the $f_i$ are independent Gaussians of any variance, we prove that the expected number of zeros of the random system in the positive orthant is bounded from above by $\frac{1}{2^{n-1}}\binom{t}{n}$., Comment: 9 pages. 2nd version: Fixed an error in the proof of Corollary 2.2, which led to changes in some of the constants. Added a missing reference. Added proof of better bound for the univariate case. 3rd version: Improvement of the statement of the main theorem

We prove that the $L^2$ bound of an oscillatory integral associated with a polynomial depends only on the number of monomials that this polynomial consists of., Comment: 4 pages, minor errors corrected

We give a Descartes'-like bound on the number of positive solutions to a system of fewnomials that holds when its exponent vectors are not in convex position and a sign condition is satisfied. This was discovered while developing algorithms and software for computing the Gale transform of a fewnomial system, which is our main goal. This software is a component of a package we are developing for Khovanskii-Rolle continuation, which is a numerical algorithm to compute the real solutions to a system of fewnomials., Comment: 22 pages, 4 figures

An old conjecture of Erd\H{o}s and R\'enyi, proved by Schinzel, predicted a bound for the number of terms of a polynomial $g(x) \in \mathbb{C}[x]$ when its square $g(x)^2$ has a given number of terms. Further conjectures and results arose, but some fundamental questions remained open. In this paper, with methods which appear to be new, we achieve a final result in this direction for completely general algebraic equations $f(x,g(x))=0$, where $f(x,y)$ is monic of arbitrary degree in $y$, and has boundedly many terms in $x$: we prove that the number of terms of such a $g(x)$ is necessarily bounded. This includes the previous results as extremely special cases. We shall interpret polynomials with boundedly many terms as the restrictions to 1-parameter subgroups or cosets of regular functions of bounded degree on a given torus $\mathbb{G}_{\mathrm{m}}^l$. Such a viewpoint shall lead to some best-possible corollaries in the context of finite covers of $\mathbb{G}_{\mathrm{m}}^l$, concerning the structure of their integral points over function fields (in the spirit of conjectures of Vojta) and a Bertini-type irreducibility theorem above algebraic multiplicative cosets. A further natural reading occurs in non-standard arithmetic, where our result translates into an algebraic and integral-closedness statement inside the ring of non-standard polynomials., Comment: 25 pages; new proof based on resolution of singularities, corrections to Theorem 1.5 and further clarifications; to appear in J. Amer. Math. Soc

In "Random complex fewnomials, I," B. Shiffman and S. Zelditch determine the limiting formula as N goes to infinity of the (normalized) expected distribution of complex zeros of a system of k random n-nomials in m variables where the coefficients are taken from the SU(m+1) ensemble and the spectra are chosen uniformly at random. We recall their result and show the limiting formula is a (k,k)-form with continuous coefficients.

We introduce several notions of `random fewnomials', i.e. random polynomials with a fixed number f of monomials of degree N. The f exponents are chosen at random and then the coefficients are chosen to be Gaussian random, mainly from the SU(m + 1) ensemble. The results give limiting formulas as N goes to infinity for the expected distribution of complex zeros of a system of k random fewnomials in m variables. When k = m, for SU(m + 1) polynomials, the limit is the Monge-Ampere measure of a toric Kaehler potential on CP^m obtained by averaging a `discrete Legendre transform' of the Fubini-Study symplectic potential at f points of the unit simplex in R^m., Comment: 23 pages

We derive new bounds of fewnomial type for the number of real solutions to systems of polynomials that have structure intermediate between fewnomials and generic (dense) polynomials. This uses a modified version of Gale duality for polynomial systems. We also use stratified Morse theory to bound the total Betti number of a hypersurface defined by such a dense fewnomial. These bounds contain and generalize previous bounds for ordinary fewnomials obtained by Bates, Bertrand, Bihan, and Sottile., Comment: 20 pages

Let K be a field and t>=0. Denote by Bm(t,K) the maximum number of non-zero roots in K, counted with multiplicities, of a non-zero polynomial in K[x] with at most t+1 monomial terms. We prove, using an unified approach based on Vandermonde determinants, that Bm(t,L)<=t^2 Bm(t,K) for any local field L with a non-archimedean valuation v such that v(n)=0 for all non-zero integer n and residue field K, and that Bm(t,K)<=(t^2-t+1)(p^f-1) for any finite extension K/Qp with residual class degree f and ramification index e, assuming that p>t+e. For any finite extension K/Qp, for p odd, we also show the lower bound Bm(t,K)>=(2t-1)(p^f-1), which gives the sharp estimation Bm(2,K)=3(p^f-1) for trinomials when p>2+e.

We give a high precision polynomial-time approximation scheme for the supremum of any honest n-variate (n+2)-nomial with a constant term, allowing real exponents as well as real coefficients. Our complexity bounds count field operations and inequality checks, and are polynomial in n and the logarithm of a certain condition number. For the special case of polynomials (i.e., integer exponents), the log of our condition number is quadratic in the sparse encoding. The best previous complexity bounds were exponential in the sparse encoding, even for n fixed. Along the way, we extend the theory of A-discriminants to real exponents and certain exponential sums, and find new and natural NP_R-complete problems., Comment: 9 pages, 7 figures (3 of them tiny). This is close to the final conference proceedings version

Let f be a degree D univariate polynomial with real coefficients and exactly m monomial terms. We show that in the special case m=3 we can approximate within eps all the roots of f in the interval [0,R] using just O(log(D)log(Dlog(R/eps))) arithmetic operations. In particular, we can count the number of roots in any bounded interval using just O(log^2 D) arithmetic operations. Our speed-ups are significant and near-optimal: The asymptotically sharpest previous complexity upper bounds for both problems were super-linear in D, while our algorithm has complexity close to the respective complexity lower bounds. We also discuss conditions under which our algorithms can be extended to general m, and a connection to a real analogue of Smale's 17th Problem., Comment: 19 pages, 1 encapsulated postscript figure. Major revision correcting many typos and minor errors. Additional discussion on connection to Smale's 17th Problem and some new references are included