Search

Certifying function nonnegativity is a ubiquitous problem in computational mathematics, with especially notable applications in optimization. We study the question of certifying nonnegativity of signomials based on the recently proposed approach of Sums-of-AM/GM-Exponentials (SAGE) decomposition due to the second author and Shah. The existence of a SAGE decomposition is a sufficient condition for nonnegativity of a signomial, and it can be verified by solving a tractable convex relative entropy program. We present new structural properties of SAGE certificates such as a characterization of the extreme rays of the cones associated to these decompositions as well as an appealing form of sparsity preservation. These lead to a number of important consequences such as conditions under which signomial nonnegativity is equivalent to the existence of a SAGE decomposition; our results represent the broadest-known class of nonconvex signomial optimization problems that can be solved efficiently via convex relaxation. The analysis in this paper proceeds by leveraging the interaction between the convex duality underlying SAGE certificates and the face structure of Newton polytopes. After proving our main signomial results, we direct our machinery toward the topic of globally nonnegative polynomials. This leads to (among other things) efficient methods for certifying polynomial nonnegativity, with complexity independent of the degree of a polynomial. [ABSTRACT FROM AUTHOR]

We will give new upper bounds for the number of solutions to the inequalities of the shape \vert F(x,y)\vert \leq h, where F(x,y) is a sparse binary form, with integer coefficients, and h is a sufficiently small integer in terms of the discriminant of the binary form F. Our bounds depend on the number of non-vanishing coefficients of F(x,y). When F is ''really sparse'', we establish a sharp upper bound for the number of solutions that is linear in terms of the number of non-vanishing coefficients. This work will provide affirmative answers to a number of conjectures posed by Mueller and Schmidt in [Trans. Amer. Math. Soc. 303 (1987), pp. 241-255], [Acta Math. 160 (1988), pp. 207-247], in special but important cases. [ABSTRACT FROM AUTHOR]

We introduce an invariant of a finite point configuration A⊂R1+n which we denote the cuspidal form of A. We use this invariant to extend Esterov's characterization of dual-defective point configurations to exponential sums; the dual variety associated with A has codimension at least 2 if and only if A does not contain any iterated circuit. [ABSTRACT FROM AUTHOR]

We prove 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 6 t − 7 . This improves a result by M. Avendaño. Furthermore, we prove that this bound is sharp for t = 3 with the help of Grothendieck's dessins d'enfant. [ABSTRACT FROM AUTHOR]

In 'Random complex fewnomials, I,' the limiting formula of the (normalized) expected distribution of complex zeros of a system of k random m-variate fewnomials where the coefficients are taken from the $${\mathrm {SU}}(m+1)$$ ensemble and the spectra are chosen uniformly at random is determined. We recall this result and show the limiting formula is a ( k, k)-form with continuous coefficients. [ABSTRACT FROM AUTHOR]

We consider the problem of estimating the intersection multiplicity between an algebraic variety and a Pfaffian foliation, at every point of the variety. We show that this multiplicity can be majorized at every point p by the local algebraic multiplicity at p of a suitably constructed algebraic cycle. The construction is based on Gabrièlov's complex analog of the Rolle-Khovanskiĭ lemma. We illustrate the main result by deriving similar uniform estimates for the complexity of the Milnor fiber of a deformation (under a smoothness assumption) and for the order of contact between an algebraic hypersurface and an arbitrary non-singular one-dimensional foliation. We also use the main result to give an alternative geometric proof for a classical multiplicity estimate in the context of commutative group varieties. [ABSTRACT FROM AUTHOR]

Consider a system of two polynomial equations in two variables: where $$F \in \mathbb {R}[X,Y]$$ has degree $$d \ge 1$$ and $$G \in \mathbb {R}[X,Y]$$ has $$t$$ monomials. We show that the system has only $$O(d^3t+d^2t^3)$$ 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$$ , 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)$$ connected components. By contrast, the following question seems to be open: if $$F$$ and $$G$$ have at most $$t$$ monomials, is the number of (non-degenerate) solutions polynomial in $$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. [ABSTRACT FROM AUTHOR]

We give a bound for the number of real solutions to systems of n polynomials in n variables, where the monomials appearing in different polynomials are distinct. This bound is smaller than the fewnomial bound if this structure of the polynomials is not taken into account. [ABSTRACT FROM AUTHOR]

Abstract: We prove that a polynomial with non-zero terms, restricted to a real line , either has at most zeros or vanishes over the whole line. As a consequence, we derive an alternative algorithm for deciding whether a linear polynomial divides a lacunary polynomial , where is a real number field. The number of bit operations performed by the algorithm is polynomial in the number of non-zero terms of , in the logarithm of the degree of , in the degree of the extension and in the logarithmic height of , and . [Copyright &y& Elsevier]

We present a new method for proving non-holonomicity of sequences, which is based on results about the number of zeros of elementary and of analytic functions. Our approach is applicable to sequences that are defined as the values of an elementary function at positive integral arguments. We generalize several recent results, e.g., non-holonomicity of the logarithmic sequence is extended to rational functions involving log n. Moreover, we show that the sequence that arises from evaluating the Riemann zeta function at an increasing integer sequence with bounded gap lengths is not holonomic. [ABSTRACT FROM AUTHOR]

Abstract: 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. [Copyright &y& Elsevier]