Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals

This paper studies the representation of a positive polynomial f(x) on a noncompact semialgebraic set S={x∈Rⁿ:g₁(x)≥0,…,g_s(x)≥0} modulo its KKT (Karush-Kuhn-Tucker) ideal. Under the assumption that the minimum value of f(x) on S is attained at some KKT point, we show that f(x) can be represented as sum of squares (SOS) of polynomials modulo the KKT ideal if f(x)>0 on S; furthermore, when the KKT ideal is radical, we argue that f(x) can be represented as a sum of squares (SOS) of polynomials modulo the KKT ideal if f(x)≥0 on S. This is a generalization of results in [J. Nie, J. Demmel, B. Sturmfels, Minimizing polynomials via sum of squares over the gradient ideal, Mathematical Programming (in press)], which discusses the SOS representations of nonnegative polynomials over gradient ideals.     

Effective Nullstellensatz for arbitrary ideals

Let f _i be polynomials in n variables without a common zero. Hilbert’s Nullstellensatz says that there are polynomials g _i such that ∑g _i f _i =1. The effective versions of this result bound the degrees of the g _i in terms of the degrees of the f _j . The aim of this paper is to generalize this to the case when the f _i are replaced by arbitrary ideals. Applications to the Bézout theorem, to Łojasiewicz–type inequalities and to deformation theory are also discussed. Received August 24, 1998 / final version received June 21, 1999     

An algorithm for primary decomposition in polynomial rings over the integers

We present an algorithm to compute a primary decomposition of an ideal in a polynomial ring over the integers. For this purpose we use algorithms for primary decomposition in polynomial rings over the rationals, resp. over finite fields, and the idea of Shimoyama-Yokoyama, resp. Eisenbud-Hunecke-Vasconcelos, to extract primary ideals from pseudo-primary ideals. A parallelized version of the algorithm is implemented in Singular. Examples and timings are given at the end of the article.     

Global residues for sparse polynomial systems

We consider families of sparse Laurent polynomials f₁,…,f_n with a finite set of common zeros Z_f in the torus Tⁿ=(C−{0})ⁿ. The global residue assigns to every Laurent polynomial g the sum of its Grothendieck residues over Z_f. We present a new symbolic algorithm for computing the global residue as a rational function of the coefficients of the f_i when the Newton polytopes of the f_i are full-dimensional. Our results have consequences in sparse polynomial interpolation and lattice point enumeration in Minkowski sums of polytopes.     

Sum of degrees of irreducible factors for polynomials in several variables

New lower bounds are given for the sum of degrees of simple and distinct irreducible factors of the polynomial f₁+?+fn, where fi(1?i?n) are pairwise relatively prime polynomials of several variables with coefficients in C.     

Polynomials orthogonal on the semicircle,II

Generalizing previous work [2], we study complex polynomials {π _k },π _k (z)=z ^k +?, orthogonal with respect to a complex-valued inner product (f,g)=∫ ₀ ^π f(e ^iθ)g(e ^iθ)w(e ^iθ)dθ. Under suitable assumptions on the “weight function”w, we show that these polynomials exist whenever Re ∫ ₀ ^π w(e ^iθ)dθ≠0, and we express them in terms of the real polynomials orthogonal with respect to the weight functionw(x). We also obtain the basic three-term recurrence relation. A detailed study is made of the polynomials {π _k } in the case of the Jacobi weight functionw(z)=(1?z)^α(1+z)^β, α>?1, and its special case \(\alpha = \beta = \lambda - \tfrac{1}{2}\) (Gegenbauer weight). We show, in particular, that for Gegenbauer weights the zeros ofπ _n are all simple and, ifn≥2, contained in the interior of the upper unit half disc. We strongly suspect that the same holds true for arbitrary Jacobi weights. Finally, for the Gegenbauer weight, we obtain a linear second-order differential equation forπ _n (z). It has regular singular points atz=1, ?1, ∞ (like Gegenbauer's equation) and an additional regular singular point on the negative imaginary axis, which depends onn.     

Solving polynomial optimization problems via the truncated tangency variety and sums of squares

Let f,g_i,i=1,…,l,h_j,j=1,…,m, be polynomials on Rⁿ and S?{x∈Rⁿ∣g_i(x)=0,i=1,…,l,h_j(x)≥0,j=1,…,m}. This paper proposes a method for finding the global infimum of the polynomial f on the semialgebraic set S via sum of squares relaxation over its truncated tangency variety, even in the case where the polynomial f does not attain its infimum on S. Under a constraint qualification condition, it is demonstrated that: (i) The infimum of f on S and on its truncated tangency variety coincide; and (ii) A sums of squares certificate for nonnegativity of f on its truncated tangency variety. These facts imply that we can find a natural sequence of semidefinite programs whose optimal values converge, monotonically increasing to the infimum of f on S.     

Determination of the limits for multivariate rational functions

The purpose of this paper is to solve the problem of determining the limits of multivariate rational functions.It is essential to decide whether or not limxˉ→0f g=0 for two non-zero polynomials f,g∈R[x1,...,xn]with f(0,...,0)=g(0,...,0)=0.For two such polynomials f and g,we establish two necessary and sufcient conditions for the rational functionf g to have its limit 0 at the origin.Based on these theoretic results,we present an algorithm for deciding whether or not lim(x1,...,xn)→(0,...,0)f g=0,where f,g∈R[x1,...,xn]are two non-zero polynomials.The design of our algorithm involves two existing algorithms:one for computing the rational univariate representations of a complete chain of polynomials,another for catching strictly critical points in a real algebraic variety.The two algorithms are based on the well-known Wu’s method.With the aid of the computer algebraic system Maple,our algorithm has been made into a general program.In the final section of this paper,several examples are given to illustrate the efectiveness of our algorithm.     

A criterion for the primeness of ideals generated by polynomials with separated variables

Proving primeness of an idealI=〈f ₁, …,f _m〉 in a polynomial ringR=K[X ₁, …,X _n]ofn indeterminates over an algebraically closed fieldK is a difficult task in general. Although there are straightforward algorithms that decide whetherI is prime or not, they are prohibitively lengthy if the number of indeterminates or the degrees of thef _iare large. In this paper we will give an easy criterion for the primeness ofI if thef _iare polynomials with separated variables, i.e. no mixed monomials occur in thef _i. The work on this paper was done while the author was a MINERVA fellow at Tel Aviv University.     

Non-Commutative Polynomial Solutions to Partial Differential Equations

This paper extends the notion of a differential equation to the space of polynomials p in non-commutative variables x = (x ₁, . . . , x _g ). The directional derivative D[p, x _i , h] of p in x _i is a polynomial in x and a non-commuting variable h. When all variables commute, D[p, x _i , h] is equal to h?p/?x _i . This paper classifies all non-commutative polynomial solutions to a special class of partial differential equations, including the non-commutative extension of Laplace??s equation. Of interest also are non-commutative subharmonic polynomials. A non-commutative polynomial is subharmonic if its non-commutative Laplacian takes positive-semidefinite matrix values whenever matrices X ₁, . . . , X _g , H are substituted for the variables x ₁, . . . , x _g , h. This paper shows that a homogeneous subharmonic polynomial which is bounded below is a harmonic polynomial??that is, a non-commutative solution to Laplace??s equation??plus a sum of squares of harmonic polynomials.     

Polynomial Cunningham chains

A sequence of prime numbers p₁,p₂,p₃,…, such that pi=2pi−1+? for all i, is called a Cunningham chain of the first or second kind, depending on whether ?=1 or −1 respectively. If k is the smallest positive integer such that 2pk+? is composite, then we say the chain has length k. It is conjectured that there are infinitely many Cunningham chains of length k for every positive integer k. A sequence of polynomials f₁(x),f₂(x),… in Z[x], such that f₁(x) has positive leading coefficient, each fi(x) is irreducible in Q[x] and fi(x)=xfi−1(x)+? for all i, is defined to be a polynomial Cunningham chain of the first or second kind, depending on whether ?=1 or −1 respectively. If k is the least positive integer such that fk+1(x) is reducible in Q[x], then we say the chain has length k. In this article, for polynomial Cunningham chains of both kinds, we prove that there are infinitely many chains of length k and, unlike the situation in the integers, that there are infinitely many chains of infinite length, by explicitly giving infinitely many polynomials f₁(x), such that fk+1(x) is the only term in the sequence that is reducible.     

On the power-free values of polynomials in two variables: II

The following theorem is proved. Suppose that for integers r,s?2, f(x,y) is an inhomogeneous polynomial of degree r with rational integral coefficients that is irreducible over the rationals, that is not a polynomial in a linear combination of x and y, that has no fixed sth power divisors other than 1, and that is a product of linear factors over some extension field of the rationals. Then, if N(X) denote the number of integers m,n of magnitude not exceeding X for which f(m,n) is sth power-free, the asymptotic formula

     

Strong coprimality and strong irreducibility of Alexander polynomials

A polynomial f(t) with rational coefficients is strongly irreducible if f(tk) is irreducible for all positive integers k. Likewise, two polynomials f and g are strongly coprime if f(tk) and g(tl) are relatively prime for all positive integers k and l. We provide some sufficient conditions for strong irreducibility and prove that the Alexander polynomials of twist knots are pairwise strongly coprime and that most of them are strongly irreducible. We apply these results to describe the structure of the subgroup of the rational knot concordance group generated by the twist knots and to provide an explicit set of knots which represent linearly independent elements deep in the solvable filtration of the knot concordance group.     

Additive edge labelings

Let G=(V,E) be a graph and d a positive integer. We study the following problem: for which labelings f_E:E→Z_d is there a labeling f_V:V→Z_d such that , for every edge (i,j)∈E? We also explore the connections of the equivalent multiplicative version to toric ideals. We derive a polynomial algorithm to answer these questions and to obtain all possible solutions.     

A note on the circuit polynomials and characteristic polynomials of wheels and ladders

Let G be a graph. The circuit polynomial of G is the polynomial Σ Π_αw_α, where w_α is a weight given to the circuit α in G, Π_αw_α is the weight of a spanning subgraph of G, consisting of circuits, nodes and edges, and the summation is taken over all such spanning subgraphs in G. The circuit polynomial of a graph is a generalization of its characteristic polynomial. The characteristic polynomials of wheels and ladders are deduced from their corresponding circuit polynomials.     

Complexity of Bezout’s Theorem VII: Distance Estimates in the Condition Metric

We study geometric properties of the solution variety for the problem of approximating solutions of systems of polynomial equations. We prove that given the two pairs (f _i ,ζ _i ), i=1,2, there exist a short path joining them such that the complexity of following the path is bounded by the logarithm of the condition number of the problems. Research was partially supported by MTM2007-62799 and by an NSERC discovery grant.     

Density testing in a contaminated sample

We study non-parametric tests for checking parametric hypotheses about a multivariate density f of independent identically distributed random vectors Z₁,Z₂,… which are observed under additional noise with density ψ. The tests we propose are an extension of the test due to Bickel and Rosenblatt [On some global measures of the deviations of density function estimates, Ann. Statist. 1 (1973) 1071-1095] and are based on a comparison of a nonparametric deconvolution estimator and the smoothed version of a parametric fit of the density f of the variables of interest Z_i. In an example the loss of efficiency is highlighted when the test is based on the convolved (but observable) density g=f*ψ instead on the initial density of interest f.     

Some properties of bivariate Bernstein-Schoenberg operators

The bivariate Bernstein-Schoenberg operatorV _T of degreem, introduced in [5], is a spline approximation operator that generalizes the Bernstein polynomial operatorB _m . It is shown here that for a convex functionf,f≤V _T (f)≤B _m (f). This result is then used to show that for a twice differentiable functiong, the asymptotic error limm(V _T (g)-g) depends only on the asymptotic error for quadratic polynomials. The latter is evaluated explicitly in the special circumstances thatV _T is, in a sense, asymptotically close toB _m .     

Polynomial differential systems having a given Darbouxian first integral

The Darbouxian theory of integrability allows to determine when a polynomial differential system in has a first integral of the kind f₁^λ₁?f_p^λ_pexp(g/h) where f_i, g and h are polynomials in , and for i=1,…,p. The functions of this form are called Darbouxian functions. Here, we solve the inverse problem, i.e. we characterize the polynomial vector fields in having a given Darbouxian function as a first integral.On the other hand, using information about the degree of the invariant algebraic curves of a polynomial vector field, we improve the conditions for the existence of an integrating factor in the Darbouxian theory of integrability.     

Linear-time certifying algorithms for near-graphical sequences

A sequence 〈d₁,d₂,…,d_n〉 of non-negative integers is graphical if it is the degree sequence of some graph, that is, there exists a graph G on n vertices whose ith vertex has degree d_i, for 1≤i≤n. The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs.If H=(V,E) is a graph and g and f are integer-valued functions on the vertex set V, then a (g,f)-factor of H is a subgraph G=(V,F) of H whose degree at each vertex v∈V lies in the interval [g(v),f(v)]. Thus, a (0,1)-factor is just a matching of H and a (1, 1)-factor is a perfect matching of H. If H is complete then a (g,f)-factor realizes a degree sequence that is consistent with the sequence of intervals 〈[g(v₁),f(v₁)],[g(v₂),f(v₂)],…,[g(v_n),f(v_n)]〉.Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of “near-graphical”. We do this in the context of minimally deficient (g,f)-factors of complete graphs. Our main result is a simple linear-time greedy algorithm for constructing minimally deficient (g,f)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing (f,f)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdös-Gallai characterization of (f,f)-factors in complete graphs) at no additional cost.