Polynomials with and without determinantal representations

The problem of writing real zero polynomials as determinants of linear matrix polynomials has recently attracted a lot of attention. Helton and Vinnikov [9] have proved that any real zero polynomial in two variables has a determinantal representation. Brändén [2] has shown that the result does not extend to arbitrary numbers of variables, disproving the generalized Lax conjecture. We prove that in fact almost no real zero polynomial admits a determinantal representation; there are dimensional differences between the two sets. The result follows from a general upper bound on the size of linear matrix polynomials. We then provide a large class of surprisingly simple explicit real zero polynomials that do not have a determinantal representation. We finally characterize polynomials of which some power has a determinantal representation, in terms of an algebra with involution having a finite dimensional representation. We use the characterization to prove that any quadratic real zero polynomial has a determinantal representation, after taking a high enough power. Taking powers is thereby really necessary in general. The representations emerge explicitly, and we characterize them up to unitary equivalence.     

A Note on Bernoulli Numbers and Shintani Generalized Bernoulli Polynomials

Generalized Bernoulli polynomials were introduced by Shintani in 1976 in order to express the special values at non-positive integers of Dedekind zeta functions for totally real numbers. The coefficients of such polynomials are finite combinations of products of Bernoulli numbers which are difficult to get hold of. On the other hand, Zagier was able to get the explicit formula for the special values in cases of real quadratic number fields.

In this paper, we shall improve Shintani's formula by proving that the special values can be determined by a finite set of polynomials. This provides a convenient way to evaluate the special values of various types of Dedekind functions. Indeed, a much broader class of zeta functions considered by the author [4] admits a similar formula for its special values. As a consequence, we are able to find infinitely many identities among Bernoulli numbers through identities among zeta functions. All these identities are difficult to prove otherwise.

     

The Complexity of Computing the Hilbert Polynomial of Smooth Equidimensional Complex Projective Varieties

We continue the study of counting complexity begun in [13], [14], [15] by proving upper and lower bounds on the complexity of computing the Hilbert polynomial of a homogeneous ideal. We show that the problem of computing the Hilbert polynomial of a smooth equidimensional complex projective variety can be reduced in polynomial time to the problem of counting the number of complex common zeros of a finite set of multivariate polynomials. The reduction is based on a new formula for the coefficients of the Hilbert polynomial of a smooth variety. Moreover, we prove that the more general problem of computing the Hilbert polynomial of a homogeneous ideal is polynomial space hard. This implies polynomial space lower bounds for both the problems of computing the rank and the Euler characteristic of cohomology groups of coherent sheaves on projective space, improving the #P-lower bound in Bach [1].     

Computing Final Polynomials and Final Syzygies Using Buchberger’s Gröbner Bases Method

Final polynomials and final syzygies provide an explicit representation of polynomial identities promised by Hilbert’s Nullstellensatz. Such representations have been studied independently by Bokowski [2,3,4] and Whiteley [23,24] to derive invariant algebraic proofs for statements in geometry. In the present paper we relate these methods to some recent developments in computational algebraic geometry. As the main new result we give an algorithm based on B. Buchberger’s Gröbner bases method for computing final polynomials and final syzygies over the complex numbers. Degree upper bound for final polynomials are derived from theorems of Lazard and Brownawell, and a topological criterion is proved for the existence of final syzygies. The second part of this paper is expository and discusses applications of our algorithm to real projective geometry, invariant theory and matrix theory.     

Zeros of Polynomials on Banach Spaces: The Real Story

Let E be a real Banach space. We show that either E admits a positive definite 2-homogeneous polynomial or every 2-homogeneous polynomial on E has an infinite dimensional subspace on which it is identically zero. Under addition assumptions, we show that such subspaces are non-separable. We examine analogous results for nuclear and absolutely (1,2)-summing 2-homogeneous polynomials and give necessary and sufficient conditions on a compact set K so that C(K) admits a positive definite 2-homogeneous polynomial or a positive definite nuclear 2-homogeneous polynomial.     

Nonlinear subelliptic equations

A finitely generated quadratic module or preordering in the real polynomial ring is called stable, if it admits a certain degree bound on the sums of squares in the representation of polynomials. Stability, first defined explicitly in Powers and Scheiderer (Adv Geom 1, 71–88, 2001), is a very useful property. It often implies that the quadratic module is closed; furthermore, it helps settling the Moment Problem, solves the Membership Problem for quadratic modules and allows applications of methods from optimization to represent nonnegative polynomials. We provide sufficient conditions for finitely generated quadratic modules in real polynomial rings of several variables to be stable. These conditions can be checked easily. For a certain class of semi-algebraic sets, we obtain that the nonexistence of bounded polynomials implies stability of every corresponding quadratic module. As stability often implies the non-solvability of the Moment Problem, this complements the result from Schmüdgen (J Reine Angew Math 558, 225–234, 2003), which uses bounded polynomials to check the solvability of the Moment Problem by dimensional induction. We also use stability to generalize a result on the Invariant Moment Problem from Cimpric et al. (Trans Am Math Soc, to appear).     

Obstructions to determinantal representability

There has recently been ample interest in the question of which sets can be represented by linear matrix inequalities (LMIs). A necessary condition is that the set is rigidly convex, and it has been conjectured that rigid convexity is also sufficient. To this end Helton and Vinnikov conjectured that any real zero polynomial admits a determinantal representation with symmetric matrices. We disprove this conjecture. By relating the question of finding LMI representations to the problem of determining whether a polymatroid is representable over the complex numbers, we find a real zero polynomial such that no power of it admits a determinantal representation. The proof uses recent results of Wagner and Wei on matroids with the half-plane property, and the polymatroids associated to hyperbolic polynomials introduced by Gurvits.     

On the Alexander polynomials of knots with Gordian distance one

We consider a condition on a pair of the Alexander polynomials of knots which are realizable by a pair of knots with Gordian distance one. We show that there are infinitely many mutually disjoint infinite subsets in the set of the Alexander polynomials of knots such that every pair of distinct elements in each subset is not realizable by any pair of knots with Gordian distance one. As one of the subsets, we have an infinite set containing the Alexander polynomials of the trefoil knot and the figure eight knot. We also show that every pair of distinct Alexander polynomials such that one is the Alexander polynomial of a slice knot is realizable by a pair of knots of Gordian distance one, so that every pair of distinct elements in the infinite subset consisting of the Alexander polynomials of slice knots is realizable by a pair of knots with Gordian distance one. These results solve problems given by Y. Nakanishi and by I. Jong.     

Hermitian matrix polynomials with real eigenvalues of definite type. Part I: Classification

The spectral properties of Hermitian matrix polynomials with real eigenvalues have been extensively studied, through classes such as the definite or definitizable pencils, definite, hyperbolic, or quasihyperbolic matrix polynomials, and overdamped or gyroscopically stabilized quadratics. We give a unified treatment of these and related classes that uses the eigenvalue type (or sign characteristic) as a common thread. Equivalent conditions are given for each class in a consistent format. We show that these classes form a hierarchy, all of which are contained in the new class of quasidefinite matrix polynomials. As well as collecting and unifying existing results, we make several new contributions. We propose a new characterization of hyperbolicity in terms of the distribution of the eigenvalue types on the real line. By analyzing their effect on eigenvalue type, we show that homogeneous rotations allow results for matrix polynomials with nonsingular or definite leading coefficient to be translated into results with no such requirement on the leading coefficient, which is important for treating definite and quasidefinite polynomials. We also give a sufficient and necessary condition for a quasihyperbolic matrix polynomial to be strictly isospectral to a real diagonal quasihyperbolic matrix polynomial of the same degree, and show that this condition is always satisfied in the quadratic case and for any hyperbolic matrix polynomial, thereby identifying an important new class of diagonalizable matrix polynomials.     

Orthogonal polynomials with respect to the sum of an arbitrary measure and a Bernstein–Szegö measure

In the present paper we study the orthogonal polynomials with respect to a measure which is the sum of a finite positive Borel measure on [0,2π] and a Bernstein–Szegö measure. We prove that the measure sum belongs to the Szegö class and we obtain several properties about the norms of the orthogonal polynomials, as well as, about the coefficients of the expression which relates the new orthogonal polynomials with the Bernstein–Szegö polynomials. When the Bernstein–Szegö measure corresponds to a polynomial of degree one, we give a nice explicit algebraic expression for the new orthogonal polynomials.     

Banach Spaces Admitting a Separating Polynomial and L P Spaces

 We prove that in a Banach space admitting a separating polynomial, each weakly null normalized sequence has a subsequence which is equivalent to the usual basis of some , p an even integer. We show that for each even integer p, the Schatten class admits a separating polynomial. For a space with a basis admitting a 4-homogeneous separating polynomial, we relate the unconditionality of the basis with the existence of certain type of polynomials defined in terms of infinite symmetric matrices. We find relations between the properties of the entries of these matrices and the geometrical structure of the space. Finally we study the existence of convex 4-homogeneous separating polynomials. Received 3 January 2001     

Banach Spaces Admitting a Separating Polynomial and L P Spaces

 We prove that in a Banach space admitting a separating polynomial, each weakly null normalized sequence has a subsequence which is equivalent to the usual basis of some , p an even integer. We show that for each even integer p, the Schatten class admits a separating polynomial. For a space with a basis admitting a 4-homogeneous separating polynomial, we relate the unconditionality of the basis with the existence of certain type of polynomials defined in terms of infinite symmetric matrices. We find relations between the properties of the entries of these matrices and the geometrical structure of the space. Finally we study the existence of convex 4-homogeneous separating polynomials.     

Two-Orthogonal Polynomial Sequences as Eigenfunctions of a Third-Order Differential Operator

This paper presents functional identities fulfilled by the forms of the dual sequence of polynomial eigenfunctions of certain differential operators, belonging to the class of the two-orthogonal polynomial sequences. For a specific third-order lowering operator, the correspondent matrix differential identity is deduced, proving that the resultant polynomial sequence is a classical polynomial sequence in the Hahn’s sense. As an example, the vectorial relation fulfilled by the tuple of functionals (u ₀, u ₁) of a two-orthogonal polynomial sequences analogous to the classical Laguerre polynomials is given, treated in a work of Ben Cheikh and Douak.     

Completely positive reformulations for polynomial optimization

Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well established body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution schemes for quadratic polynomial optimization problems have been designed by drawing on conic programming tools, and the extensively studied cones of completely positive and of copositive matrices. In particular, this approach has been applied to solve key combinatorial optimization problems. Along this line of research, we consider polynomial optimization problems that are not necessarily quadratic. For this purpose, we use a natural extension of the cone of completely positive matrices; namely, the cone of completely positive tensors. We provide a general characterization of the class of polynomial optimization problems that can be formulated as a conic program over the cone of completely positive tensors. As a consequence of this characterization, it follows that recent related results for quadratic problems can be further strengthened and generalized to higher order polynomial optimization problems. Also, we show that the conditions underlying the characterization are conceptually the same, regardless of the degree of the polynomials defining the problem. To illustrate our results, we discuss in further detail special and relevant instances of polynomial optimization problems.     

Combinatorial Expansions of Kazhdan-Lusztig Polynomials

We introduce two related families of polynomials, easily computableby simple recursions into which any Kazhdan–Lusztig (andinverse Kazhdan–Lusztig) polynomial of any Coxeter groupcan be expanded linearly, and we give combinatorial interpretationsto the coefficients in these expansions. This yields a combinatorialrule for computing the Kazhdan–Lusztig polynomials interms of paths in a directed graph, and a completely combinatorialreformulation of the nonnegativity conjecture [15, p. 166].     

The bivariate Ising polynomial of a graph

In this paper we discuss the two variable Ising polynomials in a graph theoretical setting. This polynomial has its origin in physics as the partition function of the Ising model with an external field. We prove some basic properties of the Ising polynomial and demonstrate that it encodes a large amount of combinatorial information about a graph. We also give examples which prove that certain properties, such as the chromatic number, are not determined by the Ising polynomial. Finally we prove that there exist large families of non-isomorphic planar triangulations with identical Ising polynomial.     

多项式稳定性判据对代数方程求根的应用及其数值试验

一、引言 已有许多方法可以求多项式的根,其中多数属于迭代法.这类方法的缺点是收敛性依赖于初始近似的选择(求复根还没有大范围收敛的迭代法).另一类方法是先求根的模或实部,然后再设法求同模或等实部的根,如根平方——结式法,按分布理论求根等就属于这一类.这类方法不存在收敛性问题,但也有其不足之处.如根平方——结点法的缺点除了有可能将良态多项式变为病态多项式之外,求结式也增加了计算的复杂性.采用单精度运算的数值试验结果表明,这个方法求解的精度比某些迭代法低.     

A series solution for nonlinear differential equations using delta operators

In this paper, we shall generalize our previous results [1] to the case of series expansion in powers of several polynomials. For this, we shall extend the ideas of delta operators and their basic polynomial sequences, introduced in conjunction with the algebra (over a field of characteristic zero) of all polynomials in one variable [2] to the algebra (over a field of characteristic zero) of all polynomials in n indeterminates. We apply this technique to derive the formal power series expansion of the input-output map describing a nonlinear system with polynomial inputs.     

On the colored Tutte polynomial of a graph of bounded treewidth

We observe that a formula given by Negami [Polynomial invariants of graphs, Trans. Amer. Math. Soc. 299 (1987) 601-622] for the Tutte polynomial of a k-sum of two graphs generalizes to a colored Tutte polynomial. Consequently, an algorithm of Andrzejak [An algorithm for the Tutte polynomials of graphs of bounded treewidth, Discrete Math. 190 (1998) 39-54] may be directly adapted to compute the colored Tutte polynomial of a graph of bounded treewidth in polynomial time. This result has also been proven by Makowsky [Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Discrete Appl. Math. 145 (2005) 276-290], using a different algorithm based on logical techniques.