Jensen's Inequality for polynomials with concentration at low degrees

Summary We give a generalization of Jensen's Inequality, valid for polynomials having some concentration at low degrees. We investigate the constants involved, both from a theoretical and a numerical point of view.     

On roots of polynomials with positive coefficients

We prove that an algebraic number α is a root of a polynomial with positive rational coefficients if and only if none of its conjugates is a nonnegative real number. This settles a recent conjecture of Kuba.     

On the roots of cauchy polynomials

We discuss the butterfly-shaped region M_n in the complex plane which is defined as the set of all the roots of all normalized Cauchy polynomials of degree n. Besides the geometric structure, e.g. that the set M_n \sb {1} is star-shaped with respect to the origin, some results concerning the boundary of M_n are presented.     

On roots of quaternion polynomials

The topological structure of the zero-sets of quaternion polynomials is discussed. As was earlier proved by the author, such a zero-set consists of several points and two-dimensional spheres with centers on the real line. We also show that one can define multiplicities of components of each type in such way that their sum is equal to the algebraic degree of the polynomial considered. Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 59, Algebra and Geometry, 2008.     

On roots of random polynomials

We study the distribution of the complex roots of random polynomials of degree with i.i.d. coefficients. Using techniques related to Rice's treatment of the real roots question, we derive, under appropriate moment and regularity conditions, an exact formula for the average density of this distribution, which yields appropriate limit average densities. Further, using a different technique, we prove limit distribution results for coefficients in the domain of attraction of the stable law.

     

On asymptotics of the uniform norm of polynomials with zeros at the roots of unity

The work is related to the problem by P. Erds about the estimation of the numbers

On the real roots of Euler polynomials

We show how are located the positive roots of the Euler polynomiale _n of degreen. We give an upper bound and a lower bound for the greatest root. This permits to determine an integerv _(n) such that the number of positive roots ofE _n is eitherv _(n) orv _(n) +2. We also study the behaviour of ther-th positive root ofE _n asn tends to infinity.     

On the number of integer polynomials with multiplicatively dependent roots

We give some counting results on integer polynomials of fixed degree and bounded height whose distinct non-zero roots are multiplicatively dependent. These include sharp lower bounds, upper bounds and asymptotic formulas for various cases, although in general there is a logarithmic gap between lower and upper bounds.     

On the roots of Wiener polynomials of graphs

The Wiener polynomial of a connected graph $G$ is defined as $W(G;x)=\sum x^{d(u,v)}$, where $d(u,v)$ denotes the distance between $u$ and $v$, and the sum is taken over all unordered pairs of distinct vertices of $G$. We examine the nature and location of the roots of Wiener polynomials of graphs, and in particular trees. We show that while the maximum modulus among all roots of Wiener polynomials of graphs of order $n$ is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)?1$, the maximum modulus among all roots of Wiener polynomials of trees of order $n$ grows linearly in $n$. We prove that the closure of the collection of real roots of Wiener polynomials of all graphs is precisely $(?\infty ,0]$, while in the case of trees, it contains $(?\infty ,?1]$. Finally, we demonstrate that the imaginary parts and (positive) real parts of roots of Wiener polynomials can be arbitrarily large.     

On the cost of computing roots of polynomials

Recently Smale has obtained probabilistic estimates of the cost of computing a zero of a polynomial using a global version of Newton's method. Roughly speaking, his result says that, with the exception of a set of polynomials where the method fails or is very slow, the cost grows as a polynomial in the degree. He also asked whether similar results hold for PL homotopy methods. This paper gives such a result for a special algorithm of the PL homotopy type devised by Kuhn. Its main result asserts that the cost of computing some zero of a polynomial of degreen to an accuracy of ε (measured by the number of evaluations of the polynomial) grows no faster than O(n ³ log₂(n/ε)). This is a worst case analysis and holds for all polynomials without exception. This work was supported, in part, by National Science Foundation Grant MCS79-10027 and, in part, by a fellowship of the Guggenheim Foundation.     

On the concentration of multivariate polynomials with small expectation

Let t₁,…,t_n be independent, but not necessarily identical, {0, 1} random variables. We prove a general large deviation bound for multivariate polynomials (in t₁,…,t_n) with small expectation [order O(polylog(n))]. Few applications in random graphs and combinatorial number theory will be discussed. Our result is closely related to a classical result of Janson [Random Struct Algorithms 1 (1990), 221–230]. Both of them can be applied in similar situations. On the other hand, our result is symmetric, while Janson's inequality only deals with the lower tail probability. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 344–363, 2000     

On the roots of the orthogonal polynomials and residual polynomials associated with a conjugate gradient method

In this paper we explore two sets of polynomials, the orthogonal polynomials and the residual polynomials, associated with a preconditioned conjugate gradient iteration for the solution of the linear system Ax = b. In the context of preconditioning by the matrix C, we show that the roots of the orthogonal polynomials, also known as generalized Ritz values, are the eigenvalues of an orthogonal section of the matrix C A while the roots of the residual polynomials, also known as pseudo-Ritz values (or roots of kernel polynomials), are the reciprocals of the eigenvalues of an orthogonal section of the matrix (C A)^?1. When C A is selfadjoint positive definite, this distinction is minimal, but for the indefinite or nonselfadjoint case this distinction becomes important. We use these two sets of roots to form possibly nonconvex regions in the complex plane that describe the spectrum of C A.     

On the regularity of the roots of hyperbolic polynomials

We prove that a hyperbolic monic polynomial whose coefficients are functions of class C ^r of a parameter t admits roots of class C ¹ in t, if r is the maximal multiplicity of the roots as t varies. Moreover, if the coefficients are functions of t of class C ^2r , then the roots may be chosen two times differentiable at every point in t. This improves, among others, previous results of Bronšteĭn, Mandai, Wakabayashi and Kriegl, Losik and Michor.     

On maps preserving zeros of Lie polynomials of small degrees

We describe maps preserving zeros of multilinear Lie polynomials of degrees 3 and 4 on prime algebras and matrices over unital algebras. In particular, our theorems generalize several results related to commutativity preserving maps.