Search

A random polynomial is a polynomial whose coefficients are random variables. A major task in the theory of random polynomials is to examine how the real roots are distributed and correlated in situations where the degree of the polynomial is large. In this dissertation, we investigate two classes of random polynomials that have piqued the interest of researchers in probability theory and mathematical physics: elliptic polynomials and generalized Kac polynomials. Regarding elliptic polynomials, we obtain asymptotic expansions for the variances of the number of real roots on intervals whose endpoints may vary based on the polynomial's degree. Additionally, we provide sharp estimates for the cumulants of these quantities. As applications, we can determine intervals on which the number of real roots satisfies a central limit theorem and a strong law of large numbers. Our next objective is to compute the precise leading asymptotics of the variance of the number of real roots for generalized Kac polynomials whose coefficients have polynomial asymptotics. Examples of this class of random polynomials include Kac polynomials, hyperbolic polynomials, and any linear combinations of their derivatives. Before our work, such variance asymptotics had only been established for the Kac polynomials in the 1970s, thanks to Maslova's influential contribution. Our proof relies on novel asymptotic estimates for the real roots' two-point correlation function, which exposes geometric features in the distribution of real roots for these random polynomials. As a corollary, we establish asymptotic normality for the number of real roots of these random polynomials, extending and enhancing a related result of O. Nguyen and V. Vu. more...

Early in high school algebra, quadratics chosen as examples by teachers and textbooks alike tend to have integer coefficients and to factorise over the integers. This can give the misleading impression that such quadratics are the norm. As students progress into calculus and begin regularly seeing quadratics that are not as ‘nice’, we hope they become disabused of this notion. Indeed, even if the coefficients of the quadratic are integers, the probability that the quadratic factorises over the integers tends to zero as the range from which the integers are drawn grows (see [1]). But what if we ask about a behaviour less restrictive than factorising, say merely having real roots? This is the problem that concerns this Article. more...

We present an optimal version of Descartes’ rule of signs to bound the number of positive real roots of a sparse system of polynomial equations in n variables with $$n+2$$ monomials. This sharp upper bound is given in terms of the sign variation of a sequence associated to the exponents and the coefficients of the system. more...

Polynomials can be used to represent real-world situations, and their roots have real-world meanings when they are real numbers. The fundamental theorem of algebra tells us that every nonconstant polynomial p with complex coefficients has a complex root. However, no analogous result holds for guaranteeing that a real root exists to p if we restrict the coefficients to be real. Let n ≥ 1 and P n be the vector space of all polynomials of degree n or less with real coefficients. In this article, we give explicit forms of polynomials in P n such that all of their roots are real. Furthermore, we present explicit forms of linear transformations on P n which preserve real roots of polynomials in a certain subset of P n . more...

Let $f_n(z) = \sum_{k = 0}^n \varepsilon_k z^k$ be a random polynomial where $\varepsilon_0,\ldots,\varepsilon_n$ are i.i.d. random variables with $\mathbb{E} \varepsilon_1 = 0$ and $\mathbb{E} \varepsilon_1^2 = 1$. Letting $r_1, r_2,\ldots, r_k$ denote the real roots of $f_n$, we show that the point process defined by $\{|r_1| - 1,\ldots, |r_k| - 1 \}$ converges to a non-Poissonian limit on the scale of $n^{-1}$ as $n \to \infty$. Further, we show that for each $\delta > 0$, $f_n$ has a real root within $\Theta_{\delta}(1/n)$ of the unit circle with probability at least $1 - \delta$. This resolves a conjecture of Shepp and Vanderbei from 1995 by confirming its weakest form and refuting its strongest form., Comment: 19 pages more...

Given a nonconvex minimization problem where the objective function is nonlinear and twice differentiable. To gain more information about the objective function, it is essential to obtain all its s... more...

We completely determine the structure constants between real root vectors in a rank 2 Kac–Moody algebra g . Our description is computationally efficient, even in the rank 2 hyperbolic case where the coefficients of roots on the root lattice grow exponentially with height. Our approach is to extend Carter's method of finding structure constants from those on extraspecial pairs to the rank 2 Kac–Moody case. We also determine all commutator relations involving only real root vectors in all rank 2 Kac-Moody algebras. The generalized Cartan matrix of g is of the form H ( a , b ) = ( 2 − b − a 2 ) where a , b ∈ Z and a b ≥ 4 . If a b = 4 , then g is of affine type. If a b > 4 , then g is of hyperbolic type. Explicit knowledge of the root strings is needed, as well as a characterization of the pairs of real roots whose sums are real. We prove that if a and b are both greater than one, then no sum of real roots can be a real root. We determine the root strings between real roots β , γ in H ( a , 1 ) , a ≥ 5 and we determine the sets ( Z ≥ 0 α + Z ≥ 0 β ) ∩ Δ re ( H ( a , b ) ) . One of our tools is a characterization of the root subsystems generated by a subset of roots. We classify these subsystems in rank 2 Kac–Moody root systems. We prove that every rank two infinite root system contains an infinite family of non-isomorphic symmetric rank 2 hyperbolic root subsystems H ( k , k ) for certain k ≥ 3 , generated by either two short or two long simple roots. We also prove that a non-symmetric hyperbolic root systems H ( a , b ) with a ≠ b and a b > 5 also contains an infinite family of non-isomorphic non-symmetric rank 2 hyperbolic root subsystems H ( a l , b l ) , for certain positive integers l. more...

In this study, some results are given concerning the behavior of the solutions for linear delay integro-differential equations. These results are obtained by the use of two distinct real roots of the corresponding characteristic equation. more...

How many irreducible polynomials have real roots which, when expressed as simple continued fractions, all have common tails? We show how to identify all such polynomials (they have degree at most s... more...

We establish a Sturm–Liouville theorem for quadratic operator pencils with matrix-valued potentials counting their unstable real roots, with applications to stability of waves. Such pencils arise, for example, in reduction of eigenvalue systems to higher-order scalar problems. more...

We consider an m × m real symmetric matrix M a ( x ) with a 1 , … , a m on the main diagonal and x in all off-diagonal positions, where m ≥ 2 and a = ( a 1 , … , a m ) is a given m-tuple of positive real numbers. We study the extremal problem of finding the minimum and maximum of x where M a ( x ) is positive semidefinite. We show that the polynomial det ⁡ M a ( x ) in variable x has only real roots with a unique negative root and that M a ( x ) is positive semidefinite (resp. definite) if and only if x lies in the closed (resp. open) interval determined by the negative and smallest positive roots. It is further shown that the negative and smallest positive root maps over m-tuples of positive real numbers contract the Thompson metric and induce new multivariate means of positive real numbers satisfying the monotonicity, homogeneity, joint concavity and super-multiplicativity. In particular, the smallest positive root map extends to such a mean of infinite variable of positive real numbers that realizes the limits for decreasing sequences, and it eventually gives rise to a shift invariant mean of bounded sequences. more...

Hyperbolic polynomials are real multivariate polynomials with only real roots along a fixed pencil of lines. Testing whether a given polynomial is hyperbolic is a difficult task in general. We examine different ways of translating hyperbolicity into nonnegativity conditions, which can then be tested via sum-of-squares relaxations., 12 pages, 1 figure; minor changes in Section 2 and a few corrections more...

The loading of a crack-like defect in mode II is considered. In contrast to the classical representation of a crack in the form of a mathematical cut, the proposed model defines a crack in the form of a physical cut with a characteristic linear size. The mental continuation of a physical cut in a solid forms an interaction layer. It is significant that the stress-strain state of the layer does not introduce a singularity to the crack model. The product of the increment of the specific free energy in the face square element of the layer by the linear size determines its energy product. The object of the study is a double-cantilever sample, and the subject of study is the energy product in the face element of the interaction layer. The external load of the cantilevers leads to their horizontal antisymmetric displacements, which form uniform shear deformations in the interaction layer. From the equilibrium conditions of the cantilevers in the variation form, taking into account the hypothesis of axial deformation homogeneity and their reduction, a system of differential equations is obtained, which relates the stress state in the layer and the cantilevers. The solution of the characteristic equation of the system is investigated for various ratios of layer thickness and cantilevers. It is shown that when the relationship is less than a certain value, depending on the Poisson's ratio, real roots take place. In the framework of the real roots of the characteristic equation, an analytical solution of the problem is obtained. Subject to the neglect of compression cantilevers found a simplified solution. The deformations in the layer are determined taking into account the compression of the consoles and without it. The analysis of the dependence of the energy product on the relationship of the thickness of the layer and cantilevers. It is shown that with a thickness ratio of 10-6 or less, the energy product practically does not change its value. Accounting for the compression of cantilevers gives a difference in the values of the energy product of the order of 20 % in relation to the simplified solution of the problem. more...

The root-finding problem has wide applications in geometric processing and computer graphics. Previous rational cubic clipping methods are either of convergence rate 7/k with O(n2) complexity, or of convergence rate 5/k with linear complexity, where n and k are degree of the given polynomial and the multiplicity of the root, respectively. This paper presents an improved rational cubic clipping of linear complexity, which can achieve convergence rate 7/k, or a better one 7 / ( k − 1 ) for a multiple root such that k ≥ 2. Numerical examples illustrate both efficiency and convergence rate of the new method. more...

International audience; In this paper, we study the problem of computing the $\mathcal{L}\infty$- norm of finite-dimensional linear time-invariant systems. This problemis first reduced to the computation of the maximal x-projection of the real solutions $(x, y)$ of a bivariate polynomial system $\sum=\{P,{\frac{\partial{P}}{\partial{y}}}\}$, with ${P} \in \mathbb{Z}[x, y]$. Then, we use standard computer algebra methods to solve the problem. In this paper, we alternatively study a method based on rational univariate representations, a method based on root separation, and finally a method first based on the sign variation of the leading coefficients of the signed subresultant sequence and then based on the identification of an isolating interval for the maximal $x$-projection of the real solutions of $\sum$. more...

Given a polynomial $p$ of degree $d$ and a bound $\kappa$ on a condition number of $p$, we present the first root-finding algorithms that return all its real and complex roots with a number of bit operations quasi-linear in $d \log^2(\kappa)$. More precisely, several condition numbers can be defined depending on the norm chosen on the coefficients of the polynomial. Let $p(x) = \sum\_{k=0}^d a\_k x^k = \sum\_{k=0}^d \sqrt{\binom d k} b\_k x^k$. We call the condition number associated with a perturbation of the $a\_k$ the hyperbolic condition number $\kappa\_h$, and the one associated with a perturbation of the $b\_k$ the elliptic condition number $\kappa\_e$. For each of these condition numbers, we present algorithms that find the real and the complex roots of $p$ in $O\left(d\log^2(d\kappa)\ \text{polylog}(\log(d\kappa))\right)$ bit operations.Our algorithms are well suited for random polynomials since $\kappa\_h$ (resp. $\kappa\_e$) is bounded by a polynomial in $d$ with high probability if the $a\_k$ (resp. the $b\_k$) are independent, centered Gaussian variables of variance $1$. more...

Koiran’s real \(\tau \)-conjecture asserts that if a non-zero real univariate polynomial f can be written as \(\sum _{i=1}^{k}\prod _{j=1}^m\,f_{ij}\), where each \(f_{ij}\) contains at most t monomials, then the number of distinct real roots of f is polynomially bounded in kmt. Assuming the conjecture with parameter \(m=\omega (1)\), one can show that \({\mathsf {VP}}\ne {\mathsf {VNP}}\) (i.e. symbolic permanent requires superpolynomial-size circuit). In this paper, we propose a \(\tau \)-conjecture for sum-of-squares (SOS) model (equivalently, \(m=2\)). more...

Given rational univariate polynomials f and g such that gcd(f, g) and f / gcd(f, g) are relatively prime, we show that g is non-negative on all the real roots of f if and only if g is a sum of squares of rational polynomials modulo f. We complete our study by exhibiting an algorithm that produces a certificate that a polynomial g is non-negative on the real roots of a non-zero polynomial f , when the above assumption is satisfied., Comment: Revista de la Union Matematica Argentina, 2022 more...

We present a method for proving that Jensen polynomials associated with functions in the $$\delta $$-Laguerre-Polya class have all real roots, and demonstrate how it can be used to construct new functions belonging to the Laguerre–Polya class. As an application, we confirm a conjecture of Ono, which asserts that the Jensen polynomials associated with the first term of the Hardy–Ramanujan–Rademacher series formula for the partition function are always hyperbolic. more...

We study the distribution of the discriminant D(P) of polynomials P from the class Pn(Q) of all integer polynomials of degree n and height at most Q. We evaluate the asymptotic number of polynomials P ∈ Pn(Q) having all real roots and satisfying the inequality |D(P)| ≤ X as Q→∞and X/Q2n−2→ 0. more...

Much attention has been focused in recent years on the following algebraic problem arising from applications: which chemical reaction networks, when taken with mass-action kinetics, admit multiple positive steady states? The interest behind this question is in steady states that are stable. As a step toward this difficult question, here we address the question of multiple nondegenerate positive steady states. Mathematically, this asks whether certain families of parametrized, real, sparse polynomial systems ever admit multiple positive real roots that are simple. Our main results settle this problem for certain types of small networks, and our techniques point the way forward for larger networks., Revision; final version; 17 pages; 1 figure; 1 table. This work builds on arXiv:1603.06441 more...

Schroder’s formulae of the first (S1) and second (S2) kind of order m of convergence are generalizations of Newton’s ( m = 2 ) and Halley’s (S2, m = 3 ) iterative formulae for finding zeros of functions. Davies and Dawson show that for entire functions with only real zeros, Halley’s formula converges globally and monotonically to their zeros, independently of the initial value on the real line. We show that the S2 formulae of odd order ≥ 5 enjoy the same convergence feature for polynomials with only real zeros. Numerical examples illustrate this. We illustrate no monotonic convergence of the S1 formulae and of the S2 formulae of even order. more...

In Machchhar and Elber (2016) , an algorithm is presented for computing all real roots of univariate scalar Bernstein polynomials by subdividing the polynomial at a known root and then factoring out the root from the polynomial, resulting in a reduction in problem complexity. This short report presents a speed-up over Machchhar and Elber (2016) , by circumventing the need for subdividing the polynomial each time a root is discovered, an O ( n 2 ) process, where n is the order of the polynomial. The subdivision step is substituted for by a polynomial division. This alternative also has some drawbacks which are discussed as well. more...

The initiation of iterations and the encounters of all of its solutions are two of the main problems that are derived from iterative methods. These are produced within feasible regions where the problem lies. This paper provides an algorithm to solve both for the general case of nonlinear systems of p unknowns and q equations. Furthermore, some examples of this algorithm implementation are also introduced. more...

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 $\binom{n}{2}-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., Comment: 17 pages, 9 figures more...

Athanasiadis [‘A survey of subdivisions and local $h$-vectors’, in The Mathematical Legacy of Richard P. Stanley (American Mathematical Society, Providence, RI, 2017), 39–51] asked whether the local $h$-polynomials of type $A$ cluster subdivisions have only real zeros. We confirm this conjecture and prove that the local $h$-polynomials for all the Cartan–Killing types have only real roots. Our proofs use multiplier sequences and Chebyshev polynomials of the second kind. more...

We construct lump solutions of the Kadomtsev–Petviashvili-I equation using Grammian determinants in the spirit of the works by Ohta and Yang. We show that the peak locations depend on the real roots of the Wronskian of the orthogonal polynomials for the asymptotic behaviors in some particular cases. We also prove that if the time goes to −∞, then all the peak locations are on a vertical line, while if the time goes to ∞, then they are all on a horizontal line, i.e., a π/2 rotation is observed after interaction. more...

In this paper we introduce some Christoffel–Darboux type identities for independence polynomials. As an application, we give a new proof of a theorem of Chudnovsky and Seymour, which states that the independence polynomial of a claw-free graph has only real roots. Another application is related to a conjecture of Merrifield and Simmons. more...