NP-hardness of deciding convexity of quartic polynomials and related problems

We show that unless P = NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic polynomials. We also prove that deciding strict convexity, strong convexity, quasiconvexity, and pseudoconvexity of polynomials of even degree four or higher is strongly NP-hard. By contrast, we show that quasiconvexity and pseudoconvexity of odd degree polynomials can be decided in polynomial time.     

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

Polycyclic–by–finite groups admit a bounded-degree polynomial structure

For a polycyclic-by-finite group , of Hirsch length , an affine (resp. polynomial) structure is a representation of into (resp. , the group of polynomial diffeomorphisms) letting act properly discontinuously on . Recently it was shown by counter-examples that there exist groups (even nilpotent ones) which do not admit an affine structure, thus giving a negative answer to a long-standing question of John Milnor. We prove that every polycyclic-by-finite group admits a polynomial structure, which moreover appears to be of a special (“simple”) type (called ”canonical”) and, as a consequence of this, consists entirely of polynomials of a bounded degree. The construction of this polynomial structure is a special case of an iterated Seifert Fiber Space construction, which can be achieved here because of a very strong and surprising cohomology vanishing theorem. Oblatum 24-VI-1996 & 30-IX-1996     

Jeu de taquin and a monodromy problem for Wronskians of polynomials

The Wronskian associates to d linearly independent polynomials of degree at most n, a non-zero polynomial of degree at most d(n−d). This can be viewed as giving a flat, finite morphism from the Grassmannian Gr(d,n) to projective space of the same dimension. In this paper, we study the monodromy groupoid of this map. When the roots of the Wronskian are real, we show that the monodromy is combinatorially encoded by Schützenberger's jeu de taquin; hence we obtain new geometric interpretations and proofs of a number of results from jeu de taquin theory, including the Littlewood-Richardson rule.     

Resultants and group matrices

In this paper, we study the resultants of polynomials which are the determinants of polynomial matrices, and we show that the determinant of a group matrix can be expressed in terms of an iterated resultant of a system of polynomials in several variables which are explicitly given in terms of first row entries. We also show how to obtain the block triangulation of block group matrices over a finite field.     

On Reduction of Quaternionic Polynomials and Their Identical Equality

We show that any quaternionic polynomial with one variable can be represented in such a way that the number of its terms will be not larger than a certain number depending on the degree of the polynomial. We study also some particular cases where this number can be made even smaller. Then we use the above-mentioned representation to study how to check whether two given quaternionic polynomials with one variable are identically equal. We solve this problem for all linear polynomials and for some types of nonlinear polynomials.     

Growth and homogeneity of matchbox manifolds

A matchbox manifold with one-dimensional leaves which has equicontinuous holonomy dynamics must be a homogeneous space, and so must be homeomorphic to a classical Vietoris solenoid. In this work, we consider the problem, what can be said about a matchbox manifold with equicontinuous holonomy dynamics, and all of whose leaves have at most polynomial growth type? We show that such a space must have a finite covering for which the global holonomy group of its foliation is nilpotent. As a consequence, we show that if the growth type of the leaves is polynomial of degree at most 3, then there exists a finite covering which is homogeneous. If the growth type of the leaves is polynomial of degree at least 4, then there are additional obstructions to homogeneity, which arise from the structure of nilpotent groups.     

Polynomial Processes for Power Prices

ABSTRACT

Polynomial processes have the property that expectations of polynomial functions (of degree n, say) of the future state of the process conditional on the current state are given by polynomials (of degree ≤ n) of the current state. Here we explore the potential of polynomial maps of polynomial processes for modelling energy prices. We focus on the example of Alberta power prices, derive one- and two-factor models for spot prices. We examine their performance in numerical experiments, and demonstrate that the richness of the dynamics they are able to generate makes them well suited for modelling even extreme examples of energy price behaviour.     

Reidemeister torsion and lens surgeries on knots in homology 3-spheres II

We introduce the norm and the order of a polynomial and of a homology lens space. We calculate the norm of the cyclotomic polynomials, and apply it to lens surgery problem for a knot whose Alexander polynomial is the same as an iterated torus knot.     

Bounds for resultants of univariate and bivariate polynomials

The paper considers bounds on the size of the resultant for univariate and bivariate polynomials. For univariate polynomials we also extend the traditional representation of the resultant by the zeros of the argument polynomials to formal resultants, defined as the determinants of the Sylvester matrix for a pair of polynomials whose actual degree may be lower than their formal degree due to vanishing leading coefficients. For bivariate polynomials, the resultant is a univariate polynomial resulting by the elimination of one of the variables, and our main result is a bound on the largest coefficient of this univariate polynomial. We bring a simple example that shows that our bound is attainable and that a previous sharper bound is not correct.     

Monodromy of real isolated singularities

Complex conjugation on complex space permutes the level sets of a real polynomial function and induces involutions on level sets corresponding to real values. For isolated complex hypersurface singularities with real defining equation we show the existence of a monodromy vector field such that complex conjugation intertwines the local monodromy diffeomorphism with its inverse. In particular, it follows that the geometric monodromy is the composition of the involution induced by complex conjugation and another involution. This topological property holds for all isolated complex plane curve singularities. Using real morsifications, we compute the action of complex conjugation and of the other involution on the Milnor fiber of real plane curve singularities.     

Admissibility of kneading sequences and structure of Hubbard trees for quadratic polynomials

Hubbard trees are invariant trees connecting the points of thecritical orbits of post-critically finite polynomials. Douadyand Hubbard showed in the Orsay Notes that they encode all combinatorialproperties of the Julia sets. For quadratic polynomials, onecan describe the dynamics as a subshift on two symbols, anditinerary of the critical value is called the kneading sequence.Whereas every (pre)periodic sequence is realized by an abstractHubbard tree (see the authors’ preprint from 2007), notevery such tree is realized by a quadratic polynomial. In thispaper, we give an Admissibility Condition that describes preciselywhich sequences correspond to quadratic polynomials. We identifythe occurrence of the so-called ‘evil branch points’as the sole obstruction to being realizable. We also show howto derive the properties of periodic (branch) points in thetree (their periods, relative positions, number of arms andwhether they are evil or not) from the kneading sequence.     

带有边集限制的最均匀支撑树问题

本在无向网络中，建立了带有边集限制的最均匀支撑树问题的网络模型．中首先解决最均匀支撑树问题，并给出求无向网络中最均匀支撑树的多项式时间算法；然后，给出了求无向网络中带有边集限制的最小树多项式时间算法；最后，在已解决的两个问题的基础上解决了带有边集限制的最均匀支撑树问题．     

Tutte polynomials for trees

We define two two-variable polynomials for rooted trees and one two-variable polynomial for unrooted trees, all of which are based on the coranknullity formulation of the Tutte polynomial of a graph or matroid. For the rooted polynomials, we show that the polynomial completely determines the rooted tree, i.e., rooted trees T₁ and T₂ are isomorphic if and only if f(T₁) = f(T₂). The corresponding question is open in the unrooted case, although we can reconstruct the degree sequence, number of subtrees of size k for all k, and the number of paths of length k for all k from the (unrooted) polynomial. The key difference between these three polynomials and the standard Tutte polynomial is the rank function used; we use pruning and branching ranks to define the polynomials. We also give a subtree expansion of the polynomials and a deletion-contraction recursion they satisfy.     

Sub-Riemannian vs. Euclidean dimension comparison and fractal geometry on Carnot groups

We solve Gromov's dimension comparison problem for Hausdorff and box counting dimension on Carnot groups equipped with a Carnot-Carathéodory metric and an adapted Euclidean metric. The proofs use sharp covering theorems relating optimal mutual coverings of Euclidean and Carnot-Carathéodory balls, and elements of sub-Riemannian fractal geometry associated to horizontal self-similar iterated function systems on Carnot groups. Inspired by Falconer's work on almost sure dimensions of Euclidean self-affine fractals we show that Carnot-Carathéodory self-similar fractals are almost surely horizontal. As a consequence we obtain explicit dimension formulae for invariant sets of Euclidean iterated function systems of polynomial type. Jet space Carnot groups provide a rich source of examples.     

On 3-monotone approximation by piecewise polynomials

We consider 3-monotone approximation by piecewise polynomials with prescribed knots. A general theorem is proved, which reduces the problem of 3-monotone uniform approximation of a 3-monotone function, to convex local L₁ approximation of the derivative of the function. As the corollary we obtain Jackson-type estimates on the degree of 3-monotone approximation by piecewise polynomials with prescribed knots. Such estimates are well known for monotone and convex approximation, and to the contrary, they in general are not valid for higher orders of monotonicity. Also we show that any convex piecewise polynomial can be modified to be, in addition, interpolatory, while still preserving the degree of the uniform approximation. Alternatively, we show that we may smooth the approximating piecewise polynomials to be twice continuously differentiable, while still being 3-monotone and still keeping the same degree of approximation.     

Direct and inverse polynomial perturbations of hermitian linear functionals

This paper is devoted to the study of direct and inverse (Laurent) polynomial modifications of moment functionals on the unit circle, i.e., associated with hermitian Toeplitz matrices. We present a new approach which allows us to study polynomial modifications of arbitrary degree.The main objective is the characterization of the quasi-definiteness of the functionals involved in the problem in terms of a difference equation relating the corresponding Schur parameters. The results are presented in the general framework of (non-necessarily quasi-definite) hermitian functionals, so that the maximum number of orthogonal polynomials is characterized by the number of consistent steps of an algorithm based on the referred recurrence for the Schur parameters.The non-uniqueness of the inverse problem makes it more interesting than the direct one. Due to this reason, special attention is paid to the inverse modification, showing that different approaches are possible depending on the data about the polynomial modification at hand. These different approaches are translated as different kinds of initial conditions for the related inverse algorithm.Some concrete applications to the study of orthogonal polynomials on the unit circle show the effectiveness of this new approach: an exhaustive and instructive analysis of the functionals coming from a general inverse polynomial perturbation of degree one for the Lebesgue measure; the classification of those pairs of orthogonal polynomials connected by a certain type of linear relation with constant polynomial coefficients; and the determination of those orthogonal polynomials whose associated ones are related to a degree one polynomial modification of the original orthogonality functional.     

Structured eigenvalue condition numbers and linearizations for matrix polynomials

This work is concerned with eigenvalue problems for structured matrix polynomials, including complex symmetric, Hermitian, even, odd, palindromic, and anti-palindromic matrix polynomials. Most numerical approaches to solving such eigenvalue problems proceed by linearizing the matrix polynomial into a matrix pencil of larger size. Recently, linearizations have been classified for which the pencil reflects the structure of the original polynomial. A question of practical importance is whether this process of linearization significantly increases the eigenvalue sensitivity with respect to structured perturbations. For all structures under consideration, we show that this cannot happen if the matrix polynomial is well scaled: there is always a structured linearization for which the structured eigenvalue condition number does not differ much. This implies, for example, that a structure-preserving algorithm applied to the linearization fully benefits from a potentially low structured eigenvalue condition number of the original matrix polynomial.