Arnold Mathematical Journal
Problem Contribution

Received: 7 November 2014 / Accepted: 16 March 2015

# Problems Around Polynomials: The Good, The Bad and The Ugly…

Boris Shapiro Department of Mathematics Stockholm University 10691 Stockholm Sweden, shapiro@math.su.se The title of the paper, alluding to the highly recommended spaghetti western by S. Leone, reflects the very personal taste of the author concerning mathematical problems which should be taken with a grain of salt. In his opinion, a “good” problem has an elegant short formulation and is (hopefully) solvable, while a “bad” one looks equally stimulating but seems unaccessible at the moment. Finally, an “ugly” problem apparently has a non inspiringly complicated answer which can hardly stimulate a further development. But one can not really tell until the problem itself has been actually solved! But, in any case, the esthetic feeling about mathematical problems and their solutions has to be taken seriously

### Abstract

The Russian style of formulating mathematical problems means that nobody will be able to simplify your formulation as opposed to the French style which means that nobody will be able to generalize it,—Vladimir Arnold.

#### Keywords

Maxwell’s conjecture, Zeros of exponential polynomials, Zeros of non-negative polynomials, Zeros of tropical polynomial

## 1 Around Maxwell’s Conjecture

In Section 133 of [Maxwell1954], J. C. Maxwell formulated the following claim, but provided it with an incomplete proof (see details in [Gabrielov et al.2007]).

###### Conjecture 1.

(Maxwell, seems bad, no tools). For any system of $N$ isolated fixed point charges in $\mathbb{R}^{3}$, the number of points of equilibrium (assumed finite) of the created electrostatic field

 $E(\bar{x})=\sum_{i=1}^{N}\frac{\xi_{i}(\bar{x}-\bar{x}_{i})}{|\bar{x}-\bar{x}_% {i}|^{3}}$

is at most $(N-1)^{2}$. Here $\xi_{i}$ is a charge placed at $\bar{x}_{i}\in\mathbb{R}^{3}$, and $\bar{x}\in\mathbb{R}^{3}$ is a variable vector.

Some very crude estimate on the maximal number of points of equilibrium is obtained in [Gabrielov et al.2007] using Khovanskii’s fewnomial theory, see [Khovanskii1991]. Conjecture 1 is not settled even for three positive point charges in which case all points of equilibrium lie in the plane spanned by these charges. (Some special cases of three charges are settled in the recent literature, see [Killian2009]; [Peretz2013]; [Wang2012]).

Observe that for charges of different signs in $\mathbb{R}^{3},$ the set of points of equilibrium might make up a space curve. The simplest example of that kind is a 4-tuple of charges placed at the vertices of a square in the $xy$-plane with coordinates $(\pm 1,\pm 1,0)$. If one places unit positive charges at $(1,1,0)$ and $(-1,-1,0)$, and unit negative charges at the two remaining corners, then the set of points of equilibrium coincides with the $z$-axis. The following naive-looking question is not settled either.

###### Conjecture 2.

(Folklore, very irritating). For any set of charges of the same sign in $\mathbb{R}^{n}$, the set of its points of equilibrium is finite.

The next claim is a very special one-dimensional case of a rather general Conjecture 1.7. of [Gabrielov et al.2007] which generalizes the above Conjecture 1 in many ways.

###### Conjecture 3.

(A. Gabrielov, D. Novikov, B. Shapiro, seems good, but no progress). Let $(x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{N},y_{N})$ be a collection of points in $\mathbb{R}^{2}$, $\xi_{1},\xi_{2},\ldots,\xi_{N}$ be arbitrary real charges, and $\alpha\geq 1/2$. Then the rational univariate function

 $\Psi(x)=\sum_{i=1}^{N}\frac{\xi_{i}}{((x-x_{i})^{2}+y_{i}^{2})^{\alpha}},\;\;x% \in\mathbb{R},$

has at most $N$ local maxima on the whole real line.

Observe that this conjecture is also not settled in the simplest case when $N=3$, $\alpha=1$, and all charges are unit. The author has overwhelming numerical evidence supporting the latter conjecture, but no proof.

## 2 On Real Zeros of Exponential Sums

Consider the space of linear ordinary homogeneous differential equations of order $k$ with constant coefficients, i.e.

 $y^{(k)}+a_{1}y^{(k-1)}+\cdots+a_{k}y=0,$ (2.1)

where $a_{1},\ldots,a_{k}$ are arbitrary complex numbers. The next statement easily follows from the standard facts about the asymptotic zero distribution of exponential sums, see, e.g., [Langer1931].

###### Lemma 1.

Every non-trivial solution of (2.1) has finitely many (probably no) real zeros if and only if any two distinct characteristic roots of (2.1) have distinct real parts.

Denote by $\Omega_{k}$ the set of all equations (2.1) satisfying the conditions of Lemma 1 [it is an open dense subset of $\mathbb{C}^{k}$ with coordinates $(a_{1},\ldots,a_{k})$].

###### Problem 1.

(B. Shapiro, looks bad, but very important). Does there exist an upper bound for the number of real roots valid for all non-trivial solutions of all equations in $\Omega_{k}$?

The latter problem is open already for $k=3$. Observe that there exists a highly non-trivial and, apparently, far from being sharp upper bound for the number of integer zeros of exponential polynomials obtained in [Schmidt1999].

## 3 On Isolated Zeros of Non-negative Polynomials and Sums of Squares

###### Problem 2.

(D. Khavinson, I. Itenberg, B. Shapiro, apparently bad). Find the maximal possible number $\sharp(2k,l)$ of isolated zeros for real non-negative polynomials of degree $2k$ in $l$ variables.

###### Problem 3.

(G. Ottaviani, B. Shapiro, seems good). Find the maximal possible number $\widetilde{\sharp}(2k,l)$ of isolated zeros for real non-negative polynomials of degree $2k$ in $l$ variables, which are representable as the sums of squares of real polynomials of degree at most $k$.

A trivial observation is that $k^{l}\leq\widetilde{\sharp}(2k,l)\leq\sharp(2k,l).$ In the special case $l=2$, both problems were considered in an intriguing paper [Choi et al.1980], where it was proven that $\widetilde{\sharp}(2k,2)=k^{2}$ and $\sharp(2k,2)\leq\frac{3k(k-1)}{2}+1$. The latter inequality is obtained with the help of Petrovskii–Oleinik’s inequality, see [Oleinik and Petrovskii1949].

###### Conjecture 4.

(G. Ottaviani, B. Shapiro, seems good). For any number of variables, $\widetilde{\sharp}(2k,l)=k^{l}$.

On the other hand, it seems difficult even to determine the coefficient of $k^{l}$ of the leading asymptotic term for $\sharp(2k,l)$ when $l$ is fixed and $k\to\infty$. For example, I doubt that $\sharp(2k,2)$ grows asymptotically as ${3k^{2}}/{2}$ when $k\to\infty$.

## 4 Hermite–Biehler Problem

The well-known Hermite–Biehler theorem claims that a univariate monic polynomial $s$ of degree $k$ has all roots in the open upper half-plane if and only if $s=p+iq$. Here $p$ and $q$ are real polynomials of degree $k$ and $k-1$ respectively, with all real, simple, and interlacing roots, and $q$ has a negative leading coefficient.

###### Problem 4.

(S. Fisk, seems bad, see [Fisk2006], p. 575). Given a pair of real polynomials $(p,q),$ give restrictions on the location of the roots of $p+iq$ in terms of the location of the roots of $p$ and $q$.

An example of such results can be found in [Kostov et al.2011]. Closely related important questions are: (i) restrictions on the location of (complex) roots of the Wronskian $W(p,q);$ (ii) description of the real univalent disks for a real rational function $\frac{p}{q}$.

## 5 Mesh-Related questions

By the mesh of a polynomial $p(x)$ with all real simple zeros, we mean the minimal distance between its consecutive roots.

###### Conjecture 5.

(P. Bränden, I. Krasikov, B. Shapiro, hopefully good, see [Brändén et al.2012]). A difference operator $T(p(x))=a_{0}p(x)+a_{1}p(x-1)+\cdots+a_{k}p(x-k)$ with constant coefficients preserves the set of real-rooted polynomials of degree at most $m$, whose mesh is at least 1, if and only if the polynomial $T((x)_{m})$ is real-rooted and has mesh at least one. Here $(x)_{m}=x(x-1)(x-2)\cdots(x-m+1)$ is the $m$th Pochhammer polynomial.

There is an alternative formulation of Conjecture 5 which looks more attractive. Let $\nabla p(x)=p(x+1)-p(x)$ be the forward difference operator, and consider the following product on the space of polynomials of degree at most $d$:

 $(p\bullet q)(x)=\sum_{k=0}^{d}(\nabla^{k}p)(0)\cdot(\nabla^{d-k}q)(x).$

Conjecture 5 is equivalent to

###### Conjecture 6.

If $p$ and $q$ are real-rooted polynomials of degree at most $d$ and mesh $\geq 1$, then so is $p\bullet q$.

## 6 Topology of the Space of Polynomials

The famous Descartes’ rule of signs claims that the number of positive roots of a real univariate polynomial does not exceed the number of sign changes in its sequence of coefficients. For simplicity, let us consider only polynomials with all coefficients non-vanishing. An arbitrary ordered sequence ${\bar{\sigma}}=(\sigma_{0},\sigma_{1},\ldots,\sigma_{d})$ of $\pm$-signs is called a sign pattern. Given a sign pattern ${{\bar{\sigma}}}$ as above, we call the pair of non-negative integers counting sign changes and sign preservations of ${\bar{\sigma}}$ the Descartes’ pair $(p_{\bar{\sigma}},n_{\bar{\sigma}})$ of ${\bar{\sigma}}$. The Descartes’ pair of ${\bar{\sigma}}$ gives upper bounds on the number of positive and negative roots of any polynomial of degree $d$, whose signs of coefficients are given by ${\bar{\sigma}}$ (observe that, for any ${\bar{\sigma}}$, $p_{\bar{\sigma}}+n_{\bar{\sigma}}=d$). To any polynomial $q(x)$ with sign pattern ${\bar{\sigma}},$ we associate the pair $(pos_{q},neg_{q})$ of the numbers of its positive and negative roots (counting multiplicities). Obviously $(pos_{q},neg_{q})$ satisfies the standard restrictions

 $pos_{q}\leq p_{\bar{\sigma}},\;pos_{q}\equiv p_{\bar{\sigma}}(mod\,2),\;neg_{q% }\leq n_{\bar{\sigma}},\;neg_{q}\equiv n_{\bar{\sigma}}(mod\,2).$ (6.1)

We call pairs $(pos,neg)$ satisfying (6.1) admissible for ${\bar{\sigma}}$. It turns out that there exist patterns ${\bar{\sigma}}$ whose admissible pairs $(pos,neg)$ are not all realizable by polynomials with sign pattern ${\bar{\sigma}}$.

###### Problem 5.

(Seems bad, but might be ugly). For a given sign pattern ${\bar{\sigma}},$ which admissible pairs $(pos,neg)$ are realizable by polynomials whose coefficients have signs given by ${\bar{\sigma}}$?

The first non-realizable combination of a sign pattern and a pair $(pos,neg)$ occurs in degree 4, see [Grabiner1999]. Namely (up to the standard $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$-action on the set of all sign patterns), the only non-realizable combination is ${\bar{\sigma}}=(+,+,-,+,+)$ with the pair $(2,0)$. Based on our computer-aided results up to degree 10, we can formulate the following claim.

###### Conjecture 7.

(J. Forsgård, V. Kostov, B. Sh, hopefully good, see [Forsgård et al.2015]) . For an arbitrary sign pattern ${\bar{\sigma}}$, the only type of pairs $(pos,neg)$ which can be non-realizable has either $pos$ or $neg$ vanishing. In other words, for any sign pattern ${\bar{\sigma}}$, each pair $(pos,neg)$, satisfying (6.1) with positive $pos$ and $neg$, is realizable.

## 7 Tropical Geometry

###### Conjecture 8.

(J. Forsgård, B. Shapiro, seems good, see [Forsgård and Shapiro2015]). Let $f(z)=\sum_{k=0}^{n}a_{k}z^{k}$ be a polynomial with positive coefficients, and consider the related (weighted) tropical polynomial

 $f_{trop}(x)=\max_{k}\left(\operatorname{Log}(a_{k})+kx+\operatorname{Log}{n% \choose k}\right).$

Then the number of real zeros of $f(z)$ does not exceed the number of points in the tropical variety defined by $f_{trop}$, i.e., the number of corners of the continuous piecewise-linear function $f_{trop}(x),\;x\in\mathbb{R}$.

###### Conjecture 9.

(J. Forsgård, B. Shapiro, seems good, see [Forsgård and Shapiro2015]). Let $f(z)=\sum_{k=0}^{n}a_{k}z^{k}$ be a polynomial with positive coefficients. Consider the differences

 $\tilde{c}_{k}=(k+1)a_{k}^{2}-ka_{k-1}a_{k+1},$

where $a_{-1}=a_{n+1}=0$. Let $0=k_{1}<k_{2}<\cdots<k_{m}=n$ be the sequence of all indices such that $\tilde{c}_{k_{i}}$ is positive, and let $v(f)$ be the number of changes in the sequence $\{k_{i}\mod 2\}_{i=0}^{m}$. Then the number of real zeros of $f(z)$ does not exceed $v(f)$.

###### Conjecture 10.

(J. Forsgård, B. Shapiro, seems good, see [Forsgård and Shapiro2015]). Let $f(z)=\sum_{k=0}^{n}a_{k}z^{k}$ be a polynomial with positive coefficients. Consider the differences

 $c_{k}=a_{k}^{2}-a_{k-1}a_{k+1},$

where $a_{-1}=a_{n+1}=0$. Let $0=k_{1}<k_{2}<\cdots<k_{m}=n$ be the sequence of all indices such that $c_{k_{i}}$ is non-negative, and let $v(f)$ be the number of changes in the sequence $\{k_{i}\mod 2\}_{i=0}^{m}$. Then the number of real zeros of $f(z)$ does not exceed $v(f)$.

Observe that polynomials with all positive coefficients have no positive real roots.

## 8 Polynomial-Like Functions

Consider a smooth function $f$ with $n$ distinct real zeros $x_{1}^{(0)}<x_{2}^{(0)}<\cdots<x_{n}^{(0)}$ in some interval $I\subseteq\mathbb{R}$. Then, by Rolle’s theorem, $f^{\prime}$ has at least $n-1$ zeros, $f^{\prime\prime}$ has at least $n-2$ zeros,…, $f^{(n-1)}$ has at least one zero in the open interval $(x_{1}^{(0)},x_{n}^{(0)})$. We are interested in smooth functions $f$ with $n$ real simple zeros in $I$ such that for all $i=1,\ldots,n$ the $i$th derivative $f^{(i)}$ has exactly $n-i$ real simple zeros in $I$ denoted by $x^{(i)}_{1}<x_{2}^{(i)}<\cdots<x_{n-i}^{(i)}.$ Note, in particular, that $f^{(n)}$ is non-vanishing on $I$.

###### Definition 1.

A smooth function $f$ defined on an interval $I$ is called polynomial-like of degree $n$, if $f^{(n)}$ does not vanish on $I$. A polynomial-like function of degree $n$ on $I$ with $n$ simple real zeros is called real-rooted.

By Rolle’s theorem, $n$ is the maximal possible number of real zeros in $I$ for a polynomial-like function of degree $n$. An obvious example of a real-rooted polynomial-like function of degree $n$ on $\mathbb{R}$ is a usual real polynomial of degree $n$ with all real and distinct zeros. Observe also that if a polynomial-like function $f$ of degree $n$ is real-rooted on $I$, then for all $i<n$ its derivatives $f^{(i)}$ are also real-rooted of degree $n-i$ on the same interval. In the above notation, the following system of inequalities holds:

### References

• [Brändén et al.2012] Brändén, P., Krasikov, I., Shapiro, B.: Elements of Pólya–Schur theory in finite diffrence setting (2012).
• [Choi et al.1980] Choi, M.-D., Lam, T.-Y., Reznick, B.: Real zeros of positive definite forms. I. Math. Z. 171, 1–26 (1980)
• [De Loera and McAllister2003] De Loera, J.A., McAllister, T.B.: Vertices of Gelfand–Tsetlin polytopes (2003).
• [Fisk2006] Fisk, S.: Polynomials, roots, and interlacing (2006).
• [Forsgård et al.2015] Forsgård, J., Kostov, Vl., Shapiro, B.: Could René Descartes have known this? (2015).
• [Forsgård and Shapiro2015] Forsgård, J.: Shapiro, B.: Discriminant amoebas, complex zero decreasing sequences, and the Karlin problem (2015). (In preparation)
• [Gabrielov et al.2007] Gabrielov, A., Novikov, D., Shapiro, B.: Mystery of point charges. Proc. Lond. Math. Soc. (3) 95(2), 443–472 (2007)
• [Grabiner1999] Grabiner, D.J.: Descartes’ rule of signs: another construction. Am. Math. Mon. 106, 854–856 (1999)
• [Jensen1913] Jensen, J.L.W.V.: Recherches sur la théorie des équations. Acta Math. 36, 181–195 (1913)
• [Khovanskii1991] Khovanskii, A.G.: Fewnomials. In: AMS Translated Monographs, vol. 88, pp. viii+139. USA (1991)
• [Killian2009] Killian, K.: A remark on Maxwell’s conjecture for planar charges. Complex Var. Elliptic Equations 54(12), 1073–1078 (2009)
• [Kostov et al.2011] Kostov, V., Shapiro, B., Tyaglov, M.: Maximal univalent disks of real rational functions and Hermite–Biehler polynomials. Proc. Am. Math. Soc. 139(5), 1625–1635 (2011)
• [Langer1931] Langer, R.E.: On the zeros of exponential sums and integrals. Bull. Am. Math. Soc. 37, 213–239 (1931)
• [Maxwell1954] Maxwell, J.C.: A treatise on electricity and magnetism. In: Republication of the 3rd revised edition, vol. 1. Dover Publ. Inc., (1954)
• [Oleinik and Petrovskii1949] Oleinik, O.A., Petrovskii, I.G.: On the topology of real algebraic hypersurfaces (Russian). Izv. Acad. Nauk SSSR 13, 389–402 (1949). [English transl.: Am. Math. Soc. Transl. 7, 399–417 (1962)]
• [Peretz2013] Peretz, R.: Application of the argument principle to Maxwell’s conjecture for three point charges. Complex Var. Elliptic Equations 58(5), 1–11 (2013)
• [Schmidt1999] Schmidt, W.M.: The zero multiplicity of linear recurrence sequences. Acta Math. 182, 243–282 (1999)
• [Shapiro and Shapiro2012] Shapiro, B., Shapiro, M.: A few riddles behind Rolle’s theorem. Am. Math. Mon. 119(9), 787–793 (2012)
• [Tyaglov2011] Tyaglov, M.: On the number of real critical points of logarithmic derivatives and the Hawaii conjecture. J. Anal. Math. 114, 1–62 (2011)
• [Wang2012] Wang, Y.: Equilibrium points of potential fields produced by positive point charges. http://ccs.math.ucsb.edu/senior-thesis/YifeiWang (2012)