Search

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

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., 4 pages, minor errors corrected

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., 20 pages

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., 22 pages, 4 figures

Tropical algebra emerges in many fields of mathematics such as algebraic geometry, mathematical physics and combinatorial optimization. In part, its importance is related to the fact that it makes various parameters of mathematical objects computationally accessible. Tropical polynomials play an important role in this, especially for the case of algebraic geometry. On the other hand, many algebraic questions behind tropical polynomials remain open. In this paper we address three basic questions on tropical polynomials closely related to their computational properties: 1. Given a polynomial with a certain support (set of monomials) and a (finite) set of inputs, when is it possible for the polynomial to vanish on all these inputs? 2. A more precise question, given a polynomial with a certain support and a (finite) set of inputs, how many roots can polynomial have on this set of inputs? 3. Given an integer k, for which s there is a set of s inputs such that any non-zero polynomial with at most k monomials has a non-root among these inputs?

Let K be a field and t ≥ 0. Denote by B m ( t, K ) the supremum of the number of roots in K ∗ , counted with multiplicities, that can have 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 B m ( t, L ) ≤ t 2 B m ( t, K ) for any local field L with a non-archimedean valuation v : L → R ∪{∞} such that v | Z 6 =0 ≡ 0 and residue field K , and that B m ( t, K ) ≤ ( t 2 − t +1)( p f − 1) for any finite extension K/ Q p with residual class degree f and ramification index e , assuming that p > t + e . For any finite extension K/ Q p , for p odd, we also show the lower bound B m ( t, K ) ≥ (2 t − 1)( p f − 1), which gives the sharp estimation B m (2 , K ) = 3( p f − 1) for trinomials when p > 2 + e . Fil: Avendaño, Martín. Texas A&M University; Estados Unidos Fil: Krick, Teresa Elena Genoveva. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina

In this paper, the authors study intersections of a special class of curves with algebraic subgroups of the multiplicative group of complex dimension at least 2. They show how results of Khovanskii on fewnomials can be used to derive finiteness results and bounds for the degrees of algebraic points for such intersections from more general results on intersections of curves with non-algebraic subgroups. They thereby generalise their earlier results, and recover in some cases, using different methods, more uniform bounds than those given in related work of Bombieri, Masser and Zannier.

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

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., 23 pages

We introduce several notions of ‘random f-nomials’, 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→∞ for the (normalized) expected distribution of complex zeros of a system of k random f-nomials in m variables (k≤ m). When k = m, for SU(m+ 1) polynomials, the limit is the Monge-Ampere measure of a toric Kahler potential on ℂℙ m obtained by averaging a ‘discrete Legendre transform’ of the Fubini-Study symplectic potential at f points of the unit simplex ∑ ⊂ ℝ

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 sub-quadratic in the sparse size. The best previous complexity bounds were exponential in the size, even for n fixed. Along the way, we partially extend the theory of A-discriminants to real exponents and exponential sums, and find new and natural NPR-complete problems.

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

The aim of this paper is to share with the mathematical community a list of 33 problems that I have found along the years during my research. I believe that it is worth to think about them and, hopefully, it will be possible either to solve some of the problems or to make some substantial progress. Many of them are about planar differential equations but there are also questions about other mathematical aspects: Abel differential equations, difference equations, global asymptotic stability, geometrical questions, problems involving polynomials or some recreational problems with a dynamical component.

Here is a question that is easy to state, but often hard to answer: Is this function nonnegative on this set? When faced with such a question, one often makes appeals to known inequalities. One crafts arguments that are sufficient to establish the nonnegativity of the function, rather than determining the function's precise range of values. This thesis studies sufficient conditions for nonnegativity of signomials and polynomials. Conceptually, signomials may be viewed as generalized polynomials that feature arbitrary real exponents, but with variables restricted to the positive orthant. Our methods leverage efficient algorithms for a type of convex optimization known as relative entropy programming (REP). By virtue of this integration with REP, our methods can help answer questions like the following: Is there some function, in this particular space of functions, that is nonnegative on this set? The ability to answer such questions is extremely useful in applied mathematics. Alternative approaches in this same vein (e.g., methods for polynomials based on semidefinite programming) have been used successfully as convex relaxation frameworks for nonconvex optimization, as mechanisms for analyzing dynamical systems, and even as tools for solving nonlinear partial differential equations. This thesis builds from the sums of arithmetic-geometric exponentials or SAGE approach to signomial nonnegativity. The term "exponential" appears in the SAGE acronym because SAGE parameterizes signomials in terms of exponential functions. Our first round of contributions concern the original SAGE approach. We employ basic techniques in convex analysis and convex geometry to derive structural results for spaces of SAGE signomials and exactness results for SAGE-based REP relaxations of nonconvex signomial optimization problems. We frame our analysis primarily in terms of the coefficients of a signomial's basis expansion rather than in terms of signomials themselves. The effect of this framing is that our results for signomials readily transfer to polynomials. In particular, we are led to define a new concept of SAGE polynomials. For sparse polynomials, this method offers an exponential efficiency improvement relative to certificates of nonnegativity obtained through semidefinite programming. We go on to create the conditional SAGE methodology for exploiting convex substructure in constrained signomial nonnegativity problems. The basic insight here is that since the standard relative entropy representation of SAGE signomials is obtained by a suitable application of convex duality, we are free to add additional convex constraints into the duality argument. In the course of explaining this idea we provide some illustrative examples in signomial optimization and analysis of chemical dynamics. The majority of this thesis is dedicated to exploring fundamental questions surrounding conditional SAGE signomials. We approach these questions through analysis frameworks of sublinear circuits and signomial rings. These sublinear circuits generalize simplicial circuits of affine-linear matroids, and lead to rich modes of analysis for sets that are simultaneously convex in the usual sense and convex under a logarithmic transformation. The concept of signomial rings lets us develop a powerful signomial Positivstellensatz and an elementary signomial moment theory. The Positivstellensatz provides for an effective hierarchy of REP relaxations for approaching the value of a nonconvex signomial minimization problem from below, as well as a first-of-its-kind hierarchy for approaching the same value from above. In parallel with our mathematical work, we have developed the sageopt python package. Sageopt drives all the examples and experiments used throughout this thesis, and has been used by engineers to solve high-degree polynomial optimization problems at scales unattainable by alternative methods. We conclude this thesis with an explanation of how our theoretical results affected sageopt's design.

Consider a system of two polynomial equations in two variables: $$\begin{aligned} F(X,Y)=G(X,Y)=0, \end{aligned}$$F(X,Y)=G(X,Y)=0,where $$F \in \mathbb {R}[X,Y]$$F?R[X,Y] has degree $$d \ge 1$$d?1 and $$G \in \mathbb {R}[X,Y]$$G?R[X,Y] has $$t$$t monomials. We show that the system has only $$O(d^3t+d^2t^3)$$O(d3t+d2t3) real solutions when it has a finite number of real solutions. This is the first polynomial bound for this problem. In particular, the bounds coming from the theory of fewnomials are exponential in $$t$$t, and count only non-degenerate solutions. More generally, we show that if the set of solutions is infinite, it still has at most $$O(d^3t+d^2t^3)$$O(d3t+d2t3) connected components. By contrast, the following question seems to be open: if $$F$$F and $$G$$G have at most $$t$$t monomials, is the number of (non-degenerate) solutions polynomial in $$t$$t? The authors' interest for these problems was sparked by connections between lower bounds in algebraic complexity theory and upper bounds on the number of real roots of "sparse like" polynomials.

Real polynomial systems are ubiquitous in many areas of pure and applied mathematics. A. Khovanskii provided a fewnomial upper bound on the number of non-degenerate positive solutions of a real polynomial system of n equations in n variables that depends only on the number of monomials appearing in the equations. The latter bound was recently improved by F. Bihan and F. Sottile, but the resulting bound still has room for improvement, even in some simple cases.The aim of this work is to tackle three main problems in Fewnomial theory. Consider a family of real polynomial systems with a given structure (for instance, supports or number of monomials). One problem is to find good upper bounds for their numbers of real (or positive) solutions. Another problem is to construct systems whose numbers of real (or positive) solutions are close to the best known upper bound. When a sharp upper bound is known, what can be said about reaching it?In this thesis, we refine a result by M. Avendaño by proving that the number of real intersection points of a real line with a real plane curve defined by a polynomial with at most t monomials is either infinite or does not exceed 6t -7. Furthermore, we prove that our bound is sharp for t=3 using Grothendieck's real dessins d'enfant. This shows that the maximal number of real intersection points of a real line with a real plane trinomial curve is eleven.We then consider the problem of estimating the maximal number of transversal positive intersection points of a trinomial plane curve and a t-nomial plane curve. T-Y Li, J.-M. Rojas and X. Wang showed that this number is bounded by 2^t-2, and recently P. Koiran, N. Portier and S. Tavenas proved the upper bound 2t^3/3 +5t. We provide the upper bound 3*2 {t-2} - 1 that is sharp for t=3 and is the tightest for t=4,...,9. This is achieved using the notion of real dessins d'enfant. Moreover, we study closely the case t=3 and give a restriction on the supports of systems reaching the sharp bound five.A circuit is a set of n+2 points in mathbb{R} n that is minimally affinely dependent. It is known that a system supported on a circuit has at most n+1 non-degenerate positive solutions, and that this bound is sharp. We use real dessins d'enfant and Viro's combinatorial patchworking to give a full characterization of circuits supporting polynomial systems with the maximal number of non-degenerate positive solutions.We consider polynomial systems of two equations in two variables with a total of five distinct monomials. This is one of the simplest cases where the sharp upper bound on the number of non-degenerate positive solutions is not known. F. Bihan and F. Sottile proved that this sharp bound is not greater than fifteen. On the other hand, the best examples had only five non-degenerate positive solutions. We consider polynomial systems as before, but defined over the field of real generalized locally convergent Puiseux series. The images by the valuation map of the solutions of such a system are intersection points of two plane tropical curves. Using non-transversal intersections of plane tropical curves, we obtain a construction of a real polynomial system as above having seven non-degenerate positive solutions., Les systèmes polynomiaux réels sont omniprésents dans de nombreux domaines des mathématiques pures et appliquées. A. Khovanskii a fourni une borne fewnomiale supérieure sur le nombre de solutions positives non-dégénérées d'un système polynomial réel de n équations à n variables qui ne dépend que du nombre de monômes apparaissant dans les équations. Cette dernière borne a été récemment améliorée par F. Bihan et F. Sottile, mais la borne résultante peut être encore améliorée, même dans certains cas simples.Le but de ce travail est d'aborder trois problèmes importants dans la théorie des Fewnomials. Considérons une famille de systèmes polynomiaux réels avec une structure donnée (par exemple, support ou le nombre de monômes). Un problème est de trouver de bonnes bornes supérieures pour leurs nombres de solutions réelles (ou positives). Un autre problème est de construire des systèmes dont le nombre de solutions réelles (ou positives) sont proches de la meilleure borne supérieure connue. Lorsqu'une borne supérieure optimale est bien connue, qu'est ce qu'on peut dire dans le cas où elle est atteinte?Dans cette thèse, nous affinons un résultat de M. Avendaño en démontrant que le nombre de points d'intersection réels d'une droite réelle avec une courbe réelle plane définie par un polynôme avec au plus t monômes est soit infini ou ne dépasse pas 6t -7. En outre, on montre que notre borne est optimale pour t=3 en utilisant les dessins d'enfant réels de Grothendieck. Cela montre que le nombre maximal de points d'intersection réels d'une droite réelle avec une courbe trinomiale réelle plane est onze.Nous considérons ensuite le problème de l'estimation du nombre maximal de points d'intersection transverses positifs d'une courbe plane trinomiale et d'une courbe plane t-nomiale. T-Y Li, J.-M. Rojas et X. Wang ont montré que ce nombre est borné par 2 t - 2, et récemment P. Koiran, N. Portier et S. Tavenas ont trouvé la borne supérieure 2t 3/3 +5t. Nous fournissons la borne supérieure 3*2 (t-2) - 1 qui est optimale pour t = 3 et est la plus petite pour t=4,...,9. Ceci est réalisé en utilisant la notion de dessins d'enfant réels. De plus, nous étudions en détail le cas t = 3 et nous donnons une restriction sur les supports des systèmes atteignant la borne optimale cinq.Un circuit est un ensemble de n+ 2 points dans mathbb{R}^n qui sont minimalement affinement dépendants. Il est connu qu'un système supporté sur un circuit a au plus n+1 solutions positives non dégénérées, et que cette borne est optimale. Nous utilisons les dessins d'enfant réels et le patchwork combinatoire de Viro pour donner une caractérisation complète des circuits supportant des systèmes polynomiaux avec le nombre maximal de solutions positives non dégénérées.Nous considérons des systèmes polynomiaux de deux équations à deux variables avec cinq monômes distincts au total. Ceci est l'un des cas les plus simples où la borne supérieure optimale sur le nombre de solutions positives non dégénérées n'est pas connue. F. Bihan et F. Sottile ont prouvé que cette borne optimale est majorée par quinze. D'autre part, les meilleurs exemples avaient seulement cinq solutions positives non dégénérées.Nous considérons des systèmes polynomiaux comme avant, mais défini sur le corps des séries de Puiseux réelles généralisées et localement convergentes. Les images par l'application de valuation des solutions d'un tel système sont des points d'intersection de deux courbes tropicales planes. En utilisant des intersections non transverses des courbes tropicales planes, on obtient une construction d'un système polynomial réel comme ci-dessus ayant sept solutions positives non dégénérées.

We prove that a polynomial f ∈ R [x, y] with t non-zero terms, restricted to a real line y = a x + b, either has at most 6 t - 4 zeros or vanishes over the whole line. As a consequence, we derive an alternative algorithm for deciding whether a linear polynomial y - a x - b ∈ K [x, y] divides a lacunary polynomial f ∈ K [x, y], where K is a real number field. The number of bit operations performed by the algorithm is polynomial in the number of non-zero terms of f, in the logarithm of the degree of f, in the degree of the extension K / Q and in the logarithmic height of a, b and f. © 2009 Elsevier Ltd. All rights reserved. Fil:Avendaño, M. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

In this Note we give a proof of a generalized version of the classical Budan–Fourier theorem, interpreting sign variations in the derivatives in terms of virtual roots.

We give new positive and negative results (some conditional) on speeding up computational algebraic geometry over the reals: (1) A new and sharper upper bound on the number of connected components of a semialgebraic set. Our bound is novel in that it is stated in terms of the volumes of certain polytopes and, for a large class of inputs, beats the best previous bounds by a factor exponential in the number of variables. (2) A new algorithm for approximating the real roots of certain sparse polynomial systems. Two features of our algorithm are (a) arithmetic complexity polylogarithmic in the degree of the underlying complex variety (as opposed to the super-linear dependence in earlier algorithms) and (b) a simple and efficient generalization to certain univariate exponential sums. (3) Detecting whether a real algebraic surface (given as the common zero set of some input straight-line programs) is not smooth can be done in polynomial time within the classical Turing model (resp. BSS model over C) only if P=NP (resp. NP, This is the final journal version which will appear in Journal of Complexity. More typos are corrected, and a new section is added where the bounds here are compared to an earlier result of Benedetti, Loeser, and Risler. The LaTeX source needs the ajour.cls macro file to compile

A real polynomial system with support $\calW \subset \Z^n$ is called {\it maximally positive} if all its complex solutions are positive solutions. A support $\calW$ having $n+2$ elements is called a circuit. We previously showed that the number of non-degenerate positive solutions of a system supported on a circuit $\calW \subset\Z^n$ is at most $m(\calW)+1$, where $m(\calW) \leq n$ is the degeneracy index of $\calW$. We prove that if a circuit $\calW \subset \Z^n$ supports a maximally positive system with the maximal number $m(\calW)+1$ of non-degenerate positive solutions, then it is unique up to the obvious action of the group of invertible integer affine transformations of $\Z^n$. In the general case, we prove that any maximally positive system supported on a circuit can be obtained from another one having the maximal number of positive solutions by means of some elementary transformations. As a consequence, we get for each $n$ and up to the above action a finite list of circuits $\calW \subset \Z^n$ which can support maximally positive polynomial systems. We observe that the coefficients of the primitive affine relation of such circuit have absolute value $1$ or $2$ and make a conjecture in the general case for supports of maximally positive systems.

Thèse diffusée initialement dans le cadre d'un projet pilote des Presses de l'Université de Montréal/Centre d'édition numérique UdeM (1997-2008) avec l'autorisation de l'auteur.

Consider a random system $\mathfrak{f}_1(x)=0,\ldots,\mathfrak{f}_n(x)=0$ of $n$ random real polynomials in $n$ variables, where each $\mathfrak{f}_k$ has a prescribed set of exponent vectors in a set $A_k\subseteq \mathbb{Z}^n$ of size $t_k$. Assuming that the coefficients of the $\mathfrak{f}_k$ are independent Gaussian of any variance, we prove that the expected number of zeros of the random system in the positive orthant is bounded from above by $4^{-n} \prod_{k=1}^n t_k(t_k-1)$. Our results hold with much more flexible assumptions than any available result in the literature, and yield stronger estimates in the specific cases considered earlier by (B\"urgisser, 2023) [arXiv:2301.00273] and (B\"urgisser, Erg\"ur, Tonelli-Cueto, 2019) [arXiv:1811.09425]. In this sense, our results mark a new milestone in flexibility for the theory of random real fewnomials., Comment: 26 pages

Let [inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="01i" /] be any number field or p-adic field and consider F :=( f 1 , . . . , f k ) where f 1 , . . . , f k ∈ [inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="02i" /][ x 1 , . . . , x n ] and no more than μ distinct exponent vectors occur in the monomial term expansions of the f i . We prove that F has no more than 1 + ( C n (μ - n ) 3 log (μ - n )) n geometrically isolated roots in [inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="03i" /] n , where C is an explicit and effectively computable constant depending only on [inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="04i" /]. This gives a significantly sharper arithmetic analogue of Khovanski's Theorem on Real Fewnomials and a higher-dimensional generalization of an earlier result of Hendrik W. Lenstra, Jr. for the special case of a single univariate polynomial. We also present some further refinements of our new bounds and a higher-dimensional generalization of a bound of Lipshitz on p -adic complex roots. Connections to non-Archimedean amoebae and computational complexity (including additive complexity and solving for the geometrically isolated rational roots) are discussed along the way. We thus provide the foundations for an effective arithmetic analogue of fewnomial theory.

In this paper we study homoclinic loops in ℝ3 which are nondegenerate in the sense of Sil’nikov ([21]) and with real principal eigenvalues in 1∶1 resonance, i.e. homoclinic loops which have thestrong inclination property and which are tangent to the principal eigenvectors. We are interested here in the higher codimensional cases. It is known that the dynamics of such systems is given by a 1-dimensional map. Using the ideas exposed in [5], we are able to show that, as for the “nontwisted” loops (cf. [17]), this 1-dimensional map admits a nice asymptotic expansion allowing to treat homoclinic loop bifurcations of arbitrarily high codimension and to exhibit an explicit bound for the number of isolated periodic solutions generated under small perturbations. The computations of the bound rely on derivation-division algorithms and Khovanskii’s fewnomials theory.

In this paper we prove a single exponential upper bound on the number of possible homotopy types of the fibres of a Pfaffian map, in terms of the format of its graph. In particular we show that if a semi-algebraic set $S \subset {\R}^{m+n}$, where $\R$ is a real closed field, is defined by a Boolean formula with $s$ polynomials of degrees less than $d$, and $\pi: {\R}^{m+n} \to {\R}^n$ is the projection on a subspace, then the number of different homotopy types of fibres of $\pi$ does not exceed $s^{2(m+1)n}(2^m nd)^{O(nm)}$. As applications of our main results we prove single exponential bounds on the number of homotopy types of semi-algebraic sets defined by fewnomials, and by polynomials with bounded additive complexity. We also prove single exponential upper bounds on the radii of balls guaranteeing local contractibility for semi-algebraic sets defined by polynomials with integer coefficients., Comment: Improved combinatorial complexity

Gabrielov introduced the notion of relative closure of a Pfaffian couple as an alternative construction of the o-minimal structure generated by Khovanskii's Pfaffian functions. In this paper, use the notion of format (or complexity) of a Pfaffian couple to derive explicit upper-bounds for the homology of its relative closure. Keywords: Pfaffian functions, fewnomials, o-minimal structures, Betti numbers., Comment: 12 pages, 1 figure. v3: Proofs and bounds have been slightly improved

Pfaffian functions, introduced by Khovanskii in late 70s, are analytic functions satisfying triangular systems of first order partial differential equations with polynomial coefficients. They include for instance algebraic and elementary transcendental functions in the appropriate domains, iterated exponentials, and fewnomials. A simple example, due to Osgood, shows that the first order theory of reals expanded by restricted Pfaffian functions does not admit quantifier elimination. On the other hand, Gabrielov and Wilkie proved (non-constructively) that this theory is model complete, i.e., one type of quantifiers can be eliminated. The talk will explain some ideas behind recent algorithms for this quantifier simplification which are based on effective cylindrical cell decompositions of sub-Pfaffian sets. Complexities of these algorithms are essentially the same as the ones which existed for a particular case of semialgebraic sets.

Polynomials in one variable Grobner bases of zero-dimensional ideals Bernstein's theorem and fewnomials Resultants Primary decomposition Polynomial systems in economics Sums of squares Polynomial systems in statistics Tropical algebraic geometry Linear partial differential equations with constant coefficients Bibliography Index.

We prove that any pair of bivariate trinomials has at most 5 isolated roots in the positive quadrant. The best previous upper bounds independent of the polynomial degrees were much larger, e.g., 248832 (for just the non-degenerate roots) via a famous general result of Khovanski. Our bound is sharp, allows real exponents, allows degeneracies, and extends to certain systems of n-variate fewnomials, giving improvements over earlier bounds by a factor exponential in the number of monomials. We also derive analogous sharpened bounds on the number of connected components of the real zero set of a single n-variate m-nomial., Comment: 27 pages, 2 figures. Extensive revision of math.CO/0008069. To appear in Discrete and Computational Geometry. Technique from main theorem (Theorem 1) now pushed as far as it will go. In particular, Theorem 1 now covers certain fewnomial systems of type (n+1,...,n+1,m) and certain non-sparse fewnomial systems. Also, a new result on counting non-compact connected components of fewnomial hypersurfaces (Theorem 3) has been added

We prove that any pair of bivariate trinomials has at most 5 isolated roots in the positive quadrant. The best previous upper bounds independent of the polynomial degrees counted only non-degenerate roots and even then gave much larger bounds, e.g., 248832 via a famous general result of Khovanski. Our bound is sharp, allows real exponents, and extends to certain systems of n-variate fewnomials, giving improvements over earlier bounds by a factor exponential in the number of monomials. We also derive new bounds on the number of real connected components of fewnomial hypersurfaces., 18 pages, submitted for publication. Further streamlining and clarifications made. There is also a new figure illustrating the optimality of a variant of Rolles' Theorem we use

Suppose L is any finite algebraic extension of either the ordinary rational numbers or the p-adic rational numbers. Also let g_1,...,g_k be polynomials in n variables, with coefficients in L, such that the total number of monomial terms appearing in at least one g_i is exactly m. We prove that the maximum number of isolated roots of G:=(g_1,...,g_k) in L^n is finite and depends solely on (m,n,L), i.e., is independent of the degrees of the g_i. We thus obtain an arithmetic analogue of Khovanski's Theorem on Fewnomials, extending earlier work of Denef, Van den Dries, Lipshitz, and Lenstra., Comment: 6 pages; 1 figure (file=5adic.ps); needs my mildly hacked versions of amsart.cls and jams-l.cls, which are included. This is the final version and removes all ramification hypotheses, quotes some more explicit bounds for the benefit of the reader, streamlines some proofs, and corrects some more typos