Multivariate Polynomial Minimization and Its Application in Signal Processing

We make a conjecture that the number of isolated local minimum points of a 2n-degree or (2n+1)-degree r-variable polynomial is not greater than n ^r when n 2. We show that this conjecture is the minimal estimate, and is true in several cases. In particular, we show that a cubic polynomial of r variables may have at most one local minimum point though it may have 2^r critical points. We then study the global minimization problem of an even-degree multivariate polynomial whose leading order coefficient tensor is positive definite. We call such a multivariate polynomial a normal multivariate polynomial. By giving a one-variable polynomial majored below a normal multivariate polynomial, we show the existence of a global minimum of a normal multivariate polynomial, and give an upper bound of the norm of the global minimum and a lower bound of the global minimization value. We show that the quartic multivariate polynomial arising from broad-band antenna array signal processing, is a normal polynomial, and give a computable upper bound of the norm of the global minimum and a computable lower bound of the global minimization value of this normal quartic multivariate polynomial. We give some sufficient and necessary conditions for an even order tensor to be positive definite. Several challenging questions remain open.     

On the topology of a generic fibre of a polynomial function

In this work we study the topologies of the fibres of some families of complex polynomial functions with isolated critical points. We consider polynomials with some transversality conditions at infinity and compute explicitly its global Milnor number μ(f). the invariant λ(f) and therefore the Euler characteristic of its generic fibre. We show that under some mild ransversality condition (transversal at infinity) the behavior of f at infinity is good and the topology of the generic fibre is determined by the two homogeneous parts of higher degree of f Finally we study families of polynomials, called two-term polynomials. This polynomials may have atypical values at infinity. Given such a two-term polynomial f we characterize its atypical values by some invariants of f. These polynomials are a source of interesting examples.     

High dimensional polynomial interpolation on sparse grids

We study polynomial interpolation on a d-dimensional cube, where d is large. We suggest to use the least solution at sparse grids with the extrema of the Chebyshev polynomials. The polynomial exactness of this method is almost optimal. Our error bounds show that the method is universal, i.e., almost optimal for many different function spaces. We report on numerical experiments for d = 10 using up to 652 065 interpolation points. This revised version was published online in June 2006 with corrections to the Cover Date.     

Roots of mappings on nonorientable surfaces¶and equations in free groups

Let f:M ₁→M ₂ be a continuous map and c:M ₁→M ₂ a constant map between closed (not necessarily orientable) surfaces. By definition the pair (f,c) has the Wecken property if f can be deformed into a map f' such that the number of coincidence points of (f',c) is the same as the number of essential coincidence classes of (f,c) and, hence, every essential coincidence class consists of exactly one point. When both surfaces are orientable the problem to determine all maps which have the Wecken property was solved in [14]. Let A(f) denote the absolute degree as defined in [6] or [15] and . Here we show that a map f has the Wecken property iff either the Euler characteristic or . In free groups there are solved certain quadratic equations closely related to the root problem. Received: Received: 18 January 2001 / Revised version: 27 November 2001     

On a Polynomial Inequality of Paul Erd s

Let f be a real polynomial having no zeros in the open unit disk. We prove a sharp evaluation from above for the quantity f′_∞/f_p, 0p<∞. The extremal polynomials and the exact constants are given. This extends an inequality of Paul Erd s [7].     

Witten Deformation and Polynomial Differential Forms

As is well known, the Witten deformation d_h of the De Rham complex computes the De Rham cohomology. In this paper, we study the Witten deformation on noncompact manifolds and restrict it on differential forms which behave polynomially near infinity. Such polynomial differential forms naturally appear on manifolds with the cylindrical structure. We prove that the cohomology of the Witten deformation d_h acting on the complex of the polynomially growing forms (depends on h and) can be computed as the cohomology of the negative remote fiber of h. We show that the assumptions of our main theorem are satisfied in a number of interesting special cases, including generic real polynomials on R_n.     

Parametrizing Over ℤ Integral Values of Polynomials Over ℚ

Given a polynomial f ∈ ?[X] such that f(?) ? ?, we investigate whether the set f(?) can be parametrized by a multivariate polynomial with integer coefficients, that is, the existence of g ∈ ?[X ₁,…, X _m ] such that f(?) = g(? ^m ). We offer a necessary and sufficient condition on f for this to be possible. In particular, it turns out that some power of 2 is a common denominator of the coefficients of f, and there exists a rational β with odd numerator and odd prime-power denominator such that f(X) = f(β ?X). Moreover, if f(?) is likewise parametrizable, then this can be done by a polynomial in one or two variables.     

Polynomial Basins of Infinity

We study the projection p: M_d ? B_d{\pi : \mathcal{M}_d \rightarrow \mathcal{B}_d} which sends an affine conjugacy class of polynomial f : \mathbbC ? \mathbbC{f : \mathbb{C} \rightarrow \mathbb{C}} to the holomorphic conjugacy class of the restriction of f to its basin of infinity. When B_d{\mathcal{B}_d} is equipped with a dynamically natural Gromov–Hausdorff topology, the map π becomes continuous and a homeomorphism on the shift locus. Our main result is that all fibers of π are connected. Consequently, quasiconformal and topological basin-of-infinity conjugacy classes are also connected. The key ingredient in the proof is an analysis of model surfaces and model maps, branched covers between translation surfaces which model the local behavior of a polynomial.     

Julia sets and periodic kneading sequences

We construct abstract Julia sets homeomorphic to Julia sets for complex polynomials of the form f _c (z) = z ² + c, having an associated periodic kneading sequence of the form [`(a*)]{\overline{\alpha\ast}} which is not a period n-tupling. We show that there is a single simply-defined space of “itineraries” which contains homeomorphic copies of all such Julia sets in a natural combinatorial way, with dynamical properties which are derivable directly from the combinatorics. This also leads to a natural definition of abstract Julia sets even for those kneading sequences which are not realized by any polynomial f _c , with similar dynamical properties.     

Multivariate discriminant and iterated resultant

In this paper,we study the relationship between iterated resultant and multivariate discriminant.We show that,for generic form f(x_n) with even degree d,if the polynomial is squarefreed after each iteration,the multivariate discriminant △(f) is a factor of the squarefreed iterated resultant.In fact,we find a factor Hp(f,[x_1,...,x_n]) of the squarefreed iterated resultant,and prove that the multivariate discriminant △(f) is a factor of Hp(f,[x_1,...,x_n]).Moreover,we conjecture that Hp(f,[x_1,...,x_n]) = △(f) holds for generic form/,and show that it is true for generic trivariate form f(x,y,z).     

On the generalized critical values of a polynomial mapping

 Let be a polynomial dominant mapping and let deg f _i ≤d. We prove that the set K(f) of generalized critical values of f is contained in the algebraic hypersurface of degree at most D=(d+s(m−1)(d−1)) ⁿ , where . This implies in particular that the set B(f) of bifurcations points of f is contained in the hypersurface of degree at most D=(d+s(m−1)(d−1)) ⁿ . We give also an algorithm to compute the set K(f) effectively. Received: 11 June 2001 / Revised version: 1 July 2002 Published online: 24 January 2003 The author is partially supported by the KBN grant 2 PO3A 017 22. Mathematics Subject Classification (2000): 14D06, 14Q20, 51N10, 51N20, 15A04     

Lower bounds for a polynomial in terms of its coefficients

We determine new sufficient conditions in terms of the coefficients for a polynomial ${f\in \mathbb{R}[\underline{X}]}We determine new sufficient conditions in terms of the coefficients for a polynomial f ? \mathbbR[X]{f\in \mathbb{R}[\underline{X}]} of degree 2d (d ≥ 1) in n ≥ 1 variables to be a sum of squares of polynomials, thereby strengthening results of Fidalgo and Kovacec (Math. Zeitschrift, to appear) and of Lasserre (Arch. Math. 89 (2007) 390–398). Exploiting these results, we determine, for any polynomial f ? \mathbbR[X]{f\in \mathbb{R}[\underline{X}]} of degree 2d whose highest degree term is an interior point in the cone of sums of squares of forms of degree d, a real number r such that f − r is a sum of squares of polynomials. The existence of such a number r was proved earlier by Marshall (Canad. J. Math. 61 (2009) 205–221), but no estimates for r were given. We also determine a lower bound for any polynomial f whose highest degree term is positive definite.     

Low distortion euclidean embeddings of trees

We consider the problem of embedding a certain finite metric space to the Euclidean space, trying to keep the bi-Lipschitz constant as small as possible. We introduce the notationc ₂(X, d) for the least distortion with which the metric space (X, d) may be embedded in a Euclidean space. It is known that if (X, d) is a metric space withn points, thenc ₂(X, d)≤0(logn) and the bound is tight. LetT be a tree withn vertices, andd be the metric induced by it. We show thatc ₂(T, d)≤0(log logn), that is we provide an embeddingf of its vertices to the Euclidean space, such thatd(x, y)≤‖f(x)−f(y) ‖≤c log lognd(x, y) for some constantc. Supported in part by grants from the Israeli Academy of Sciences and the US-Israel Binational Science Foundation. Supported in part by NSF under grants CCR-9215293 and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology.     

Greatest prime factor of a polynomial

It is established that for the greatest prime factor P(x) of the value of an integral irreducible polynomialf(x) of degree n2 for integral x>0 the estimateP(x)>c _f In Inx, x>x ₀ (f) holds, where c _f is a positive value effectively defined by the coefficients of the polynomial.Translated from Matematicheskie Zametki, Vol. 13, No. 4, pp. 515–522, April, 1973.I should like to express my thanks to V. G. Sprindzhuk for his constant attention to the present work.     

Level curves of open polynomial functions on the real plane

Let f : f ² → R be an open polynomial function. Thenf changes sign across V(f) (alternatively around a singular point of V(f)) and the function c : R → N expressing the number f(λ) of connected components of the λ-level curve of f is lower semicontinuous; it has a removable singilarity at every value λ which is critical and is not a real critical value at infinity for f.     

Factorization of Integer-Valued Polynomials with Square-Free Denominator

We describe an algorithm to compute the different factorizations of a given image primitive integer-valued polynomial f(X) = g(X)/d ∈ ?[X], where g ∈ ?[X] and d ∈ ? is square-free, assuming that the factorizations of g(X) in ?[X] and d in ? are known. We translate this problem into a combinatorial one.     

Extrema Constrained by a Family of Curves and Local Extrema

This paper considers the connections between the local extrema of a function f:DR and the local extrema of the restrictions of f to specific subsets of D. In particular, such subsets may be parametrized curves, integral manifolds of a Pfaff system, Pfaff inequations. The paper shows the existence of C ¹ or C ²-curves containing a given sequence of points. Such curves are then exploited to establish the connections between the local extrema of f and the local extrema of f constrained by the family of C ¹ or C ²-curves. Surprisingly, what is true for C ¹-curves fails to be true in part for C ²-curves. Sufficient conditions are given for a point to be a global minimum point of a convex function with respect to a family of curves.     

On the typical rank of real binary forms

We determine the rank of a general real binary form of degree d?=?4 or d?=?5. In the case d?=?5, the possible values of the rank of such general forms are 3, 4, and 5. This is the first reported case, to our knowledge, where more than two typical ranks have been found. We prove that a real binary form of degree d with d real roots has rank?d.