Some Complexity Results for Polynomial Ideals

In this paper, we survey some of our new results on the complexity of a number of problems related to polynomial ideals. We consider multivariate polynomials over some ring, like the integers or the rationals. For instance, a polynomial ideal membership problem is a (w+ 1)-tupleP= (f,g₁,g₂, …g_wwherefand theg_iare multivariate polynomials, and the problem is to determine whetherfis in the ideal generated by theg_i. For polynomials over the integers or rationals, this problem is known to be exponential space complete. We discuss further complexity results for problems related to polynomial ideals, like the word and subword problems for commutative semigroups, a quantitative version of Hilbert's Nullstellensatz in a complexity theoretic version, and problems concerning the computation of reduced polynomials and Gröbner bases.     

A characterization of linear polynomials

We give a characterization of linear polynomials over a number field k as the only non-constant polynomials f for which the equation f(x)=g(y) has a k-rational solution for each polynomial g over k.     

On the irreducibility of a class of polynomials,III

This work is a continuation and extension of our earlier articles on irreducible polynomials. We investigate the irreducibility of polynomials of the form g(f(x)) over an arbitrary but fixed totally real algebraic number field $\text{L}$, where g(x) and f(x) are monic polynomials with integer coefficients in $\text{L}$, g is irreducible over $\text{L}$ and its splitting field is a totally imaginary quadratic extension of a totally real number field. A consequence of our main result is as follows. If g is fixed then, apart from certain exceptions f of bounded degree, g(f(x)) is irreducible over $\text{L}$ for all f having distinct roots in a given totally real number field.     

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.     

Bounds for the variance of functions of random variables by orthogonal polynomials and Bhattacharya bounds

Upper and lower bounds for the variance of a function g of a random variable X are obtained by expanding g in a series of orthogonal polynomials associated with the distribution of X or by using the convergence of Bhattacharya bounds for exponential families of distribution.     

Picard-Lefschetz monodromy of products

Let f and g be reduced homogeneous polynomials in separate sets of variables. We establish a simple formula that relates the eigenspace decomposition of the monodromy operator on the Milnor fiber cohomology of fg to that of f and g separately. We use a relation between local systems and Milnor fiber cohomology that has been established by D. Cohen and A. Suciu.     

Zeros of the sum of polynomials

It is given an upper bound for the number of simple and distinct zeros of the polynomial f+g, where f and g are relatively prime polynomials with complex coefficients.     

On some classes of polynomials with nonnegative coefficients and a given factor

For a given real polynomial f without positive roots we study polynomials g of lowest degree such that the product gf has positive (nonnegative, respectively) coefficients. We show that for quadratic f with negative linear coefficient every such g must have positive coefficients and exhibit an easy procedure for the determination of g. If f has only integer coefficients we show that g with integer coefficients can be found. Furthermore, for some classes of polynomials f we give upper (lower, respectively) bounds for the degrees of g.     

Quasi-GCD computations

For univariate polynomials with real or complex coefficients and a given error bound ? > 0, h is called a quasi-gcd of f and g, if h is an ?-approximate divisor of f and of g and if any (exact) common divisor of f, g is an approximate divisor of h. Extended quasi-gcd computation means to find such h and additional cofactors u, ν such that | uf + νg ? h | < ? | h | holds. Suitable “pivoting” leads to a numerically stable version of Euclid's algorithm for solving this task. Further refinements by a divide-and-conquer technique and by means of fast algorithms for polynomial arithmetic then yield the worst case upper bound O(n² lg n(lg(1/?) + n lg n)) of “pointer time” for nth-degree polynomials. In the particular case of integer polynomials, however, an immediate reduction to fast integer gcd computation is recommended, instead.     

Prime and composite Laurent polynomials

In the paper [J. Ritt, Prime and composite polynomials, Trans. Amer. Math. Soc. 23 (1922) 51-66] Ritt constructed the theory of functional decompositions of polynomials with complex coefficients. In particular, he described explicitly polynomial solutions of the functional equation f(p(z))=g(q(z)). In this paper we study the equation above in the case where f,g,p,q are holomorphic functions on compact Riemann surfaces. We also construct a self-contained theory of functional decompositions of rational functions with at most two poles generalizing the Ritt theory. In particular, we give new proofs of the theorems of Ritt and of the theorem of Bilu and Tichy.     

On the characteristic polynomial of the adjacency matrix of the subdivision graph of a graph

The characteristic polynomial of the adjacency matrix of the subdivision graph G is related to the characteristic polynomials of the adjacency matrices of g and its line graph.     

Noncommutative convexity arises from linear matrix inequalities

This paper concerns polynomials in g noncommutative variables x=(x₁,…,xg), inverses of such polynomials, and more generally noncommutative “rational expressions” with real coefficients which are formally symmetric and “analytic near 0.” The focus is on rational expressions r=r(x) which are “matrix convex” near 0; i.e., those rational expressions r for which there is an ?>0 such that if X=(X₁,…,Xg) is a g-tuple of n×n symmetric matrices satisfying

     

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.     

Integer valued polynomials over function fields

Let A be an integrally closed subring of a function field K defined over a finite field. In this paper we investigate whether the subring of K[X], consisting of those polynomials ƒ with ƒ[A]⊂A, has an A-basis {g_i: i ∈ ℤZ_≥0}, with deg (g_i) = i.     

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.     

Rational functions over finite fields having continued fraction expansions with linear partial quotients

Let F be a finite field with q elements and let g be a polynomial in F[X] with positive degree less than or equal to q/2. We prove that there exists a polynomial f∈F[X], coprime to g and of degree less than g, such that all of the partial quotients in the continued fraction of g/f have degree 1. This result, bounding the size of the partial quotients, is related to a function field equivalent of Zaremba's conjecture and improves on a result of Blackburn [S.R. Blackburn, Orthogonal sequences of polynomials over arbitrary fields, J. Number Theory 6 (1998) 99-111]. If we further require g to be irreducible then we can loosen the degree restriction on g to deg(g)?q.     

A composition formula for squares of Hermite polynomials and its generalizations

We prove a general formula which, with appropriately chosen parameters, gives a composition formula for squares of Gould–Hopper polynomials g²_n(x,h), and hence also for Hermite polynomials. Our main tool is the classical Mehler formula, but with imaginary arguments. To cite this article: P. Graczyk, A. Nowak, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

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.     

Irreducibility Results for Compositions of Polynomials with Integer Coefficients

We obtain explicit upper bounds for the number of irreducible factors for a class of polynomials of the form f ○ g, where f,g are polynomials with integer coefficients, in terms of the prime factorization of the leading coefficients of f and g, the degrees of f and g, and the size of coefficients of f. In particular, some irreducibility results are given for this class of compositions of polynomials.     

Cocharacters of Bilinear Mappings and Graded Matrices

Let M _k (F) be the algebra of k ×k matrices over a field F of characteristic 0. If G is any group, we endow M _k (F) with the elementary grading induced by the k-tuple (1,...,1,g) where g?∈?G, g ²?≠?1. Then the graded identities of M _k (F) depending only on variables of homogeneous degree g and g ^???1 are obtained by a natural translation of the identities of bilinear mappings (see Bahturin and Drensky, Linear Algebra Appl 369:95–112, 2003). Here we study such identities by means of the representation theory of the symmetric group. We act with two copies of the symmetric group on a space of multilinear graded polynomials of homogeneous degree g and g ^???1 and we find an explicit decomposition of the corresponding graded cocharacter into irreducibles.