%\documentstyle{article} \documentclass{amsart}[12pt]\usepackage[cp866]{inputenc}\usepackage[english]{babel} \usepackage{latexsym}\usepackage{amsfonts} \newtheorem{theorem}{Theorem} \newtheorem{example}{Example} \newtheorem{prop}{Proposition} \newtheorem{corollary}{Corollary} \newtheorem{remark}{Remark} \newtheorem{definition}{Definition} \newtheorem{lemma}{Lemma} \newtheorem{conjecture}{Conjecture} \newcommand{\sm}{\setminus} \newcommand{\K}{{\bf K}} \newcommand{\Z}{{\mathbb Z}} \newcommand{\T}{{\bf T}} \newcommand{\R}{{\mathbb R}} \newcommand{\CC}{{\mathbb C}} \begin{document} \title[Topological complexity and genus of real polynomial equations]{Topological complexity and Schwarz genus of general real polynomial equation} \author{V.A.Vassiliev} \address{Steklov Mathematical Institute, Gubkina str. 8, 119991 Moscow Russia \\ and Mathematics Department, Higher School of Economics, Moscow Russia} \email{vva@mi.ras.ru} \thanks{Supported in part by the Russian President's grant No. NSh-8462.2010.1 for support of leading scientific schools} \date{} \dedicatory{To the memory of Vladimir Igorevich Arnold} \begin{abstract} We prove that the minimal number of branchings of arithmetic algorithms of approximate solution of the general real polynomial equation $x^d + a_1 x^{d-1} + \dots + a_{d-1}x +a_d=0$ of odd degree $d$ grows to infinity at least as $\log_2 d$. The same estimate is true for the $\varepsilon$-{\em genus} of the real algebraic function associated with this equation, i.e. for the minimal number of open sets covering the space $\R^d$ of such polynomials in such a way that on any of these sets there exists a continuous function whose value at any point $(a_1, \dots, a_d)$ is approximately (up to some sufficiently small $\varepsilon >0$) equal to one of real roots of the corresponding equation. \medskip \noindent {\sc 2010 Math. Subj. Class.} Primary: 55R80, 12Y05; Secondary: 55S40, 68W30. \smallskip \noindent {\sc Key words and phrases.} Complexity, cross-section, Schwarz genus, ramified covering, 13th Hilbert problem, real polynomial. \end{abstract} \maketitle \section{Definitions, problems, statements and examples} \subsection{Definitions and obvious properties} \begin{definition}[see \cite{smale}] \rm The {\em topological complexity} of an algorithm is the number of its branchings (operators IF). The topological complexity of a computational problem is the minimal topological complexity of algorithms solving it. \end{definition} Continuing \cite{reality}, we study this characteristic of algorithms finding one approximate real root of the general polynomial \begin{equation} \label{maineq} F_a(x) \equiv x^d + a_1 x^{d-1} + \dots + a_{d-1}x +a_d \end{equation} of odd degree with real coefficients $a_i$. The main result of the paper, Theorem \ref{mainth}, states that the topological complexity of this problem grows at least as $\log_2 d$. A major approach to the problems of this kind is due to S.~Smale \cite{smale}, who considered a similar problem for complex polynomials of the form (\ref{maineq}). He has related this problem to the study of a topological characteristic, the {\em Schwarz genus} \cite{schwarz}, of a map of topological spaces associated with the general polynomial (\ref{maineq}). In what follows we will study this characteristic only (for real polynomials), more exactly, its $\varepsilon$-version, see Definition \ref{mdef}. We refer to \cite{smale} concerning the definition of the algorithm used in this problem. Throughout the article, we will assume that $d$ is natural and odd, and consider $\R^d$ as the space of real polynomials (\ref{maineq}) with coordinates $a_i$. For any $T > 0$, denote by $B_T^d$ the subset in $\R^d$ consisting of all polynomials (\ref{maineq}) all whose complex roots lie in the closed disc $\{z||z| \le T\}$ in $\CC^1$. It is easy to see that $B_T^d$ is homeomorphic to a $d$-dimensional closed ball. Let $M^d$ be the hypersurface in $B_T^d \times \R^1$ consisting of all points $(a, x),$ $a \equiv(a_1, \dots, a_d) \in B^d_T$, satisfying the equation $F_a(x) =0$. The obvious projection \begin{equation} \label{proj} M^d \to B_T^d \end{equation} is surjective, proper and has at most $d$ preimages over any point $a$. \begin{definition} \label{mdef} \rm The $\varepsilon$-{\em genus} $G(d, \varepsilon, T)$ of the map (\ref{proj}) is the smallest number $g$ such that the ball $B_T^d$ can be covered by $g$ open sets $U_i,$ $i=1, \dots, g,$ arranged with continuous functions $\varphi_i: U_i \to \R^1$ in such a way that for any $a \in U_i$ the value $\varphi_i(a)$ lies in the $\varepsilon$-neighborhood of some real root of the polynomial $F_a$. \end{definition} \begin{prop} \label{smaleprop} The topological complexity of the problem of finding one approximate $($up to $\epsilon)$ real root of the general equation $F_a(x)=0$, $a \in B^d_T$, is not less than $\max_{\nu>0} G(d, \epsilon+\nu,T)-1$. \end{prop} \noindent {\em Proof} is almost tautological, see \cite{smale}, \cite{vsmale}; note however that it assumes the definition of the algorithm formulated in \cite{smale}, see also \cite{vasbook}. \hfill $\Box$ \medskip The next proposition follows almost immediately from definitions. \begin{prop} \label{trivprop} 1. $G(d,\varepsilon, T)$ does not decrease when $d$ or $T$ grows or $\varepsilon$ decreases. 2. $G(d,\varepsilon, T)$ is invariant under simultaneous dilations of $T$ and $\varepsilon$: $G(d,\varepsilon, T) = G(d, \lambda \varepsilon, \lambda T)$ for any positive $\lambda$. 3. In the definition of numbers $G(d, \varepsilon, T)$ we can replace the ball $B_T^d$ by its boundary $S^{d-1}_T$. 4. The number $G(d,\varepsilon,T)$ is not greater than the similar number defined in almost the same way, only with the ball $B^d_T$ replaced by the intersection of the ball $B^d_{2T}$ with the hyperplane $\{a_1=0\} \subset \R^d$. \end{prop} \noindent {\em Proof}. 1. The monotonicity of $G(d, \varepsilon, T)$ over $T$ and $\varepsilon$ is obvious. To prove the inequality $G(d, \varepsilon, T) \le G(d+2, \varepsilon, T)$, consider the embedding $B^d_T \to B^{d+2}_T$ sending any polynomial $F_a(x)$ to $(x^2+T^2)F_a(x)$. Given any system of $g$ sets $U_i \subset \R^{d+2}$ and functions $\varphi_i: U_i \to \R^1$ proving the inequality $G(d+2, \varepsilon,T)\le g$, this embedding induces from it a similar system proving $G(d,\varepsilon,T) \le g$. 2. Consider the following action of the group $\R^1_+$ on the space of functions $\R^1 \to \R^1:$ any element $\lambda \in \R_+^1$ sends a function $f$ to the function whose value at $x \in \R^1$ is equal to $\lambda^d f(x/\lambda)$. This action preserves the origin $\{x^d\}$ of the space $\R^d;$ in coordinates $a_i$ it is expressed by \begin{equation} \label{qh} \lambda: (a_1, a_2, \dots, a_d) \mapsto (\lambda a_1, \lambda^2 a_2, \dots, \lambda^d a_d). \end{equation} Also, this element $\lambda$ moves any collection of sets $U_i$ and functions $\varphi_i,$ satisfying the definition of the number $G(d,\varepsilon, T),$ into that satisfying the definition of $G(d, \lambda \varepsilon, \lambda T)$. 3. Suppose that we have $g$ open subsets $V_i\subset S^{d-1}_T$, covering $S^{d-1}_T,$ and continuous functions $\psi_i: V_i \to \R^1$ such that for any $a \in V_i$ the value $\psi_i(a)$ is in $\varepsilon$-neighborhood of some root of $F_a$. Then the unions of orbits of points $a \in V_i$ under the action (\ref{qh}) define an open cover $\{\tilde U_i\}$ of the set $B_T^d \setminus 0.$ Let $\tilde \varphi_i: \tilde U_i \to \R^1$ be functions coinciding with $\psi_i$ on $S^{d-1}_T$ and satisfying the homogeneity condition $\tilde \varphi_i(\lambda(a))=\lambda \tilde \varphi_i(a)$, where $\lambda(a)$ is defined by (\ref{qh}). Extend all these functions by $0$ to the point $0$ and continue them to a very small neighborhood of this point in such a way that the values of these continuations are very close to 0. Adding this very small neighborhood to all $\tilde U_i$ we obtain the desired system of open sets and functions proving that $G(d, \varepsilon, T) \le g$. 4. The group of translations in $\R^1$ acts on the space $\R^d$: for any $t \in \R^1$ $\gamma_t(F_a(x)) \equiv F_a(x-t)$. Any orbit of this action intersects once the hyperplane $\R^{d-1} \equiv \{a_1=0\}$, so having an open cover $\{W_i\}$ of some $(d-1)$-dimensional ball $B^d_{T'} \cap \R^{d-1}$ and system of functions $\phi_i: W_i \to \R$ satisfying the condition of Definition \ref{mdef}, we can extend these functions to the functions defined on the unions of orbits passing through the points of $W_i$ and satisfying the relation $\phi_i(\gamma_t(F_a)) \equiv \phi_i(F_a)+t$. If $T' \ge 2T$, then these unions of orbits define an open cover of $B^d_T$, and the (extended) functions $\phi_i$ satisfy the conditions of Definition \ref{mdef}. \hfill $\Box$ \subsection{Main result} \begin{theorem} \label{mainth} $G(2d+1, \varepsilon, 2T+2\varepsilon+\nu) \ge G(d,\varepsilon, T)+1$ for any odd $d$ and positive $T,$ $\varepsilon$ and $\nu$. \end{theorem} This theorem will be proved in Section \ref{proof}. \medskip By statement 2 of Proposition \ref{trivprop}, the number $\lim_{\varepsilon \to +0} G(d,\varepsilon,T)$ does not depend on $T$. Denote it by $G(d)$. \begin{corollary} \label{cor1} 1. $G(2d+1) \ge G(d)+1$ for any odd $d$. 2. If $ d \in [2^m-1, 2^{m+1}-2]$, then $G(d) \ge m.$ \end{corollary} \begin{conjecture} \label{upp} For any odd $d$, $G(d+2) \le G(d)+1$. \end{conjecture} \begin{prop}[see \cite{reality}, \cite{vsmale}] \label{five} 1. $G(5)=2.$ 2. $G(d) \le (d+1)/2$ for any odd $d$. Moreover, the topological complexity of the problem of finding one approximate $($up to arbitrary fixed $\epsilon>0)$ real root of the general equation $F_a(x)-0$, $a \in B^d_T$, does not exceed $(d-1)/2$, see Proposition \ref{smaleprop}. \hfill $\Box$ \end{prop} By Corollary \ref{cor1}, $G(7) \ge 3$; Conjecture \ref{upp} together with Proposition \ref{five}.1 would imply that this estimate is sharp. \subsection{Basic example: $d=3$.} \begin{prop} The equation \begin{equation} \label{exam} x^3 + px +q =0\end{equation} does not allow a continuous function $\R^2_{p,q} \to \R^1$ whose value at any point $(p,q)$ is equal to some root of the corresponding polynomial $($\ref{exam}$)$. Moreover, if $\varepsilon < T/2$ then there is no continuous function on the disc $\R^2_{p,q} \cap B^3_T,$ whose value at any point $(p,q)$ of this disc lies in the $\varepsilon$-neighborhood of the corresponding polynomial $($\ref{exam}$)$. \end{prop} \begin{figure} \unitlength 1.00mm \linethickness{0.4pt} \begin{center} \begin{picture}(60,70) \put(30,60){\oval(60,20)[t]} \put(45,60){\oval(90,10)[bl]} \put(15,60){\oval(90,30)[br]} \put(9.30,10){\oval(18.60,20)[l]} \put(50.70,10){\oval(19,20)[r]} \put(9.30,0){\line(1,0){41.40}} \put(10.70,20){\line(1,0){18.60}} \put(30.700,20){\line(1,0){18.60}} \put(15,50){\line(1,0){30}} \put(15,47.5){\oval(5,5)[l]} \put(45,52.5){\oval(5,5)[r]} \put(10,55){\vector(0,-1){55}} \put(30,55){\vector(0,-1){55}} \put(20,70){\line(0,-1){14.40}} \put(20,54.40){\line(0,-1){3.80}} \put(20,49.40){\line(0,-1){3.80}} \put(20,44.40){\vector(0,-1){24.40}} \put(50,45){\vector(0,-1){45}} \put(10,55){\circle*{1.5}} \put(30,55){\circle*{1.5}} \put(30,50){\circle*{1.5}} \put(50,45){\circle*{1.5}} \put(30,45){\circle*{1.5}} \put(20,70){\circle*{1.5}} \put(62,57){$C$} \put(20,70){\circle*{1.5}} \put(62,10){$S^1(T)$} \end{picture} \caption{The map $I:C \to S^1(T)$ has no continuous cross-sections} \label{fi1} \end{center} \end{figure} \noindent {\em Proof.} Consider the boundary $S^1(T)$ of this disc in $\R^2_{p,q}$ and the subset $C \subset \R^2_{p,q} \times \R^1$ consisting of all triples $(p,q;x)$ such that $(p,q) \in S^1(T)$ and the equation (\ref{exam}) is satisfied. The {\em discriminant curve} in $\R^2_{p,q}$ splits $S^1(T)$ into two open intervals consisting of polynomials having respectively one or three real roots. The obvious projection $C \to S^1(T)$ is topologically situated as is shown in Fig. \ref{fi1}, so it obviously has no continuous cross-sections. Moreover, the segment of $S^1(T),$ whose points are polynomials with $\ge 2$ roots, consists of two halves, filled by polynomials $(x+T)(x-(\frac{1}{2}-t)T)(x-(\frac{1}{2}+t)T)$ and $(x-T)(x+(\frac{1}{2}+t)T)(x+(\frac{1}{2}-t)T)$, $t \in [0,\frac{1}{2}],$ respectively. The desired continuous function on $S^1(T)$, whose value is everywhere in the $\frac{T}{2}$-neighborhood of some real root of the corresponding polynomial, should be equal to $-T$ on the entire first segment, and to $+T$ on the second one. This gives a contradiction at the common point $\{x^3 - T^2 x\}$ of these segments. \hfill $\Box$ \subsection{Another example: the function from Hilbert's 13th problem} The Hilbert's 13th problem, {\em Unm\"oglichkeit der L\"osung der allgemeinen Gleichung 7ten Grades mittelst Functionen von nur 2 Argumenten}, is formulated as follows: \begin{quote} Now it is probable that the root of the equation of the seventh degree is a function of its coefficients which does not belong to this class of functions capable of nomographic construction, i. e., that it cannot be constructed by a finite number of insertions of functions of two arguments. In order to prove this, the proof would be necessary that the equation of the seventh degree \begin{equation}f^7 + x f^3 + y f^2 + z f + 1 = 0 \label{seven} \end{equation} is not solvable with the help of any continuous functions of only two arguments\footnote{Wahrscheinlich ist nun die Wurzel der Gleichung 7ten Grades eine solche Function ihrer Coefficienten, die nicht zu der genannten Klasse nomographisch construirbarer Functionen geh\"ort, d. h. die sich nicht durch eine endliche Anzahl von Einschachtelungen von Functionen zweier Argumente erzeugen l\"a\ss t. Um dieses einzusehen, w\"are der Nachweis daf\"ur n\"otig, da\ss \ die Gleichung 7ten Grades $f^7 + x f^3 + y f^2 + z f + 1 = 0$ nicht, mit H\"ulfe beliebiger stetiger Functionen von nur zwei Argumenten l\"osbar ist.}. \end{quote} \begin{prop} \label{hlb} For any sufficiently small $\varepsilon$, the $\varepsilon$-genus associated with the real algebraic function $\R^3_{x,y,z} \to \R^1$ defined by the equation $($\ref{seven}$)$ is equal to 2 $($in particular, this function does not have continuous cross-sections defined on entire $\R^3_{x,y,z})$. \end{prop} So, ``with the help of any continuous functions of only two arguments'' in the Hilbert's statement should mean something more complicated than just the representation {\bf by} such a superposition function (as it can seem from the preceding text, ``constructed by a finite number of insertions of functions of two arguments''). Of course, in any reasonable (but not in this one) understanding of this statement, the Arnold-Kolmogorov theorem \cite{arn}, \cite{kolm} on representation of any continuous function in three variables by a superposition of two-argument functions is enough to give a negative solution to this problem. \medskip \noindent {\em Proof of Proposition \ref{hlb}.} First, let us prove that this $\varepsilon$-genus is greater than 1, i.e. for sufficiently small $\varepsilon>0$ there is no continuous function $\phi: \R^3 \to \R^1$ such that for any $(x,y,z) \in \R^3$ the value $\phi(x,y,z,)$ is less than $\varepsilon$-distant from some real root of the corresponding polynomial (\ref{seven}). Suppose that such a function $\phi$ does exist. Consider two polynomials $\Phi_0(f)= f^7+1$ and \begin{equation} \Phi_1(f)=f^7 - 14 f^3 -21 f^2 -7 f +1 \equiv (f+1)^3 (f^4 -3 f^3 + 6 f^2 - 10 f + 1), \label{model} \end{equation} and the segment in $\R^3_{x,y,z}$ connecting them. None of polynomials from this segment can have roots in the $\frac{1}{10}$-neighborhood of 0, therefore for $\varepsilon< \frac{1}{10}$ the signs of $\phi(\Phi_0)$ and $\phi(\Phi_1)$ should coincide (and thus be negative, as the unique real root of $\Phi_0$ is equal to $-1$). The polynomial $\Phi_1$ has only one (three-fold) negative root $f=-1$ and two simple positive (and hence not interesting for us) roots. Functions $f$ and $f^2$ additively generate the basis of the local ring of the critical point $\{-1\}$ of $\Phi_1$, hence (see \cite{avg}) the two-parameter family of all functions (\ref{seven}) with $x\equiv -14$ forms a versal unfolding of this critical point. Therefore close to this point this family behaves topologically in the same way as the family (\ref{exam}) behaves at the origin, in particular for sufficiently small $\varepsilon$ it does not admit negative continuous $\varepsilon$-sections defined in a neighborhood of the point (\ref{model}). Now let us prove that the $\varepsilon$-genus of the family (\ref{seven}) is not greater than $2$. The polynomials (\ref{seven}) never have more than three negative roots. Indeed, the number of such roots (taken with multiplicities) always should be odd, but having five negative roots would imply that the third derivative $210 f^4 + 6 x$ of our polynomial has two negative roots. So, the space $\R^3_{x,y,z}$ can be split by the discriminant variety into two open parts $O_1$ and $O_3$, such that the polynomials from these parts have exactly 1 and 3 different negative roots, respectively. The algebraic function (\ref{seven}) defines a single-valued function over $O_1$, which can be uniquely continued to the closure of $O_1$. Further, any continuous extension of this function into entire $\R^3$ is a $\varepsilon$-section of the algebraic function (\ref{seven}) in some open neighborhood $\tilde O_1$ of this closure of $O_1$. On the other hand, in $O_3$ we also have a continuous cross-section of (\ref{seven}), sending any polynomial with three real roots into its greatest root. So, the sets $O_3$ and $\tilde O_1$ form the desired cover of $\R^3$. \hfill $\Box$ \section{Proof of Theorem \ref{mainth}} \label{proof} Consider first the case $d \ge 3$. Denote the number $G(d, \varepsilon,T)$ by $g$. Choose an arbitrary $\nu>0$ and denote $T+2\varepsilon+\nu$ by $\tilde T$. Let $D_-$ and $D_+$ be two closed discs of radius $T$ in $\CC^1$ with centers in the points $-\tilde T$ and $\tilde T$ respectively; in particular they belong to the disc of radius $T+\tilde T$. Now we construct a compact subset in $B_{T+\tilde T}^{2d+1}$ consisting of six parts $J_{-3}, J_{-2}, J_{-1},$ $J_1,$ $J_2, J_3$. $J_{-3}$ consists of all real polynomials of degree $2d+1$ with leading term $x^{2d+1}$, whose $\frac{d+1}{2}$ roots coincide with one another and are equal to $-\tilde T + i \lambda T$ for some $\lambda \in [0,1]$, some other $\frac{d+1}{2}$ roots also coincide with one another and are equal to $-\tilde T - i \lambda T$ with the same $\lambda$, and the remaining $d$ roots lie in $D_+$, and at least one of them on the boundary of $D_+$. In particular, for $\lambda =0$ all these polynomials have the $(d+1)$-fold root $-\tilde T$. This set $J_{-3}$ is naturally homeomorphic to $S_{T}^{d-1} \times [0,1]$: the factor $[0,1]$ is defined by the numbers $\lambda$, and the projection to $S^{d-1}_{T}$ maps any polynomial $f \in J_{-3}$ of degree $2d+1$ to the polynomial of degree $d$, whose roots are obtained from the roots of $f$ placed in $D_+$ by subtracting $\tilde T$. $J_{-2}$ is also naturally homeomorphic to $S_{T}^{d-1} \times [0,1]$, it consists of all real polynomials of degree $2d+1$ with leading term $x^{2d+1}$, whose $d$ roots lie in $D_+$ (and at least one of them on $\partial D_+$), $d$ roots coincide with the point $-\tilde T$, and the remaining root runs over the segment $[-\tilde T,0]$. $J_{-1}$ is naturally homeomorphic to the product $S_{T}^{d-1} \times B_{T}^{d-1}$. It consists of all polynomials $f \in \R^{2d+1}$, some $d$ roots of which lie in $D_+$ (and at least one of them on $\partial D_+$), one root is equal to 0, and remaining $d$ roots lie in $D_-$. The sets $J_1$, $J_2$ and $J_3$ are defined in exactly the same way as $J_{-1}$, $J_{-2}$ and $J_{-3}$ respectively, only up to the symmetry $x \mapsto -x$, permuting $D_+$ and $D_-$, replacing the segment $[-\tilde T,0]$ by $[0,\tilde T]$, etc. Denote by $\Im$ the union $J_{-3} \cup J_{-2} \cup J_{-1} \cup J_1 \cup J_2 \cup J_3$ of all these sets. Let us define a continuous map of the set $\Im$ to the segment $[-3,3]$. The map $J_{-3} \to [-3,-2]$ is defined by the function $\{\lambda \mapsto -2-\lambda\}.$ The map $J_{-2} \to [-2,-1]$ sends any polynomial with a root $\mu \in (-\tilde T,0]$ to $-1 + \frac{\mu}{\tilde T}$, and all polynomials with the $(d+1)$-fold root $-\tilde T$ to $-2$. For any polynomial $F_a \in J_{-1}$ consider all its $d$ roots placed in the disc $D_-$; then take the minimal distance of these points from the boundary of this disc, and send this polynomial to the point in $[-1,0]$ equal to this distance multiplied by $-\frac{1}{T}$. The sets $J_1, J_2$ and $J_3$ are mapped to the segments $[0,1], [1,2]$ and $[2,3]$ in the symmetric way. All these maps are compatible over the intersections of these segments. For instance, the preimages of the point $-2$ under the maps $J_{-3} \to [-3,-2]$ and $J_{-2} \to [-2,-1]$ coincide with one another and with the set $J_{-3} \cap J_{-2}$; similar statements hold for preimages of all other breakpoints $-1, 0, 1,$ and $2$. So these maps can be composed to the single continuous map $\pi: \Im \to [-3,3]$. Now suppose that there are $g \equiv G(d,\varepsilon,T)$ open subsets $U_i \subset \R^{2d+1},$ $i=1, \dots, g$, covering the set $\Im$, and $g$ continuous functions $\varphi_i: U_i \to \R^1$ such that for any $a \in U_i$ the value $\varphi_i(a)$ is in the $\varepsilon$-neighborhood of some real root of the corresponding polynomial $F_a$. Let $\Omega_- \subset [-3,0]$ be the set of all points $t \in [-3,0]$ such that there exist $i \in \{1, \dots, g\}$ and $a \in U_i \cap \pi^{-1}(t)$ for which $\varphi_i(a) \in (-\infty, \varepsilon)$. \begin{lemma} The set $\Omega_-$ is empty. \label{lem2} \end{lemma} \noindent {\em Proof.} Since all $U_i$ are open and functions $\varphi_i$ are continuous, the set $\Omega_-$ is open in $[-3,0]$. Suppose that it is non-empty. Denote its lower bound by $\omega_-$. Then $\omega_- \ge -2$, because the polynomials from the set $\pi^{-1}([-3,2))$ do not have roots in the ray $(-\infty, 2\varepsilon)$. Hence, $\omega_- \not \in \Omega_-$, and the values of all functions $\varphi_i$ at the points of $\pi^{-1}(\omega_-)$ belong to $(\varepsilon + \nu, +\infty)$. Suppose first that $\omega_- \in [-2,-1]$. Then we have the natural homeomorphism $A: \pi^{-1}(\omega_-) \to S^{d-1}_T \subset \R^d$, sending any polynomial $F_a \in \pi^{-1}(\omega_-)$ to the unique real polynomial with leading term $x^d$, all whose roots are obtained by subtracting $\tilde T$ from the roots of $F_a$ placed in $D_+$. Composing all functions $\varphi_i: U_i \cap \pi^{-1}(\omega_-) \to \R^1$ with this homeomorphism, we obtain an open cover of the sphere $S^{d-1}_T$ by the sets $V_i \equiv A(U_i \cap \pi^{-1}(\omega_-))$ and a system of functions $V_i \to \R^1$ satisfying the conditions from the definition of the $\varepsilon$-genus $G(d,\varepsilon,T)$. This $\varepsilon$-genus is equal to $g$, therefore all $g$ sets $U_i$ have non-empty intersections with this fiber $\pi^{-1}(\omega_-)$. By the compactness of $\Im$, we can choose a finite cover of this fiber by small balls in $\Im$, any of which belongs to some of these sets $U_i$, and such that the variation of the corresponding function $\varphi_i$ along any ball is smaller than $\nu$. Then the union of these balls covers also some layer $\pi^{-1}([\omega_- -\delta, \omega_- + \delta])$, $\delta >0.$ So, the values of all functions $\varphi_i$ at all points of this layer belong to $(\varepsilon, +\infty)$, in contradiction with the definition of the set $\Omega_-$ and number $\omega_-$. Now suppose that $\omega_- \in (-1,0)$. In this case $\pi^{-1}(\omega_-)$ is homeomorphic to \begin{equation} \label{prodd} S^{d-1}_T \times S^{d-1}_{T(1+\omega_-)}, \end{equation} where projections of the point $F_a \in J_{-1}$ to two factors are defined by collections of roots of $F_a$ placed in the right-hand and left-hand half-planes of $\CC^1$ (these collections should be moved by $\tilde T$ to the left and to the right respectively). Fix an arbitrary point of the second factor $S^{d-1}_{T(1+\omega_-)},$ e.g. the polynomial $(x+ T(1+\omega_-))^d,$ and consider the subset in $\pi^{-1}(\omega_-)$ homeomorphic to $S^{d-1}_T$ and corresponding to the fiber of the product (\ref{prodd}) over this point. In the same way as in the previous paragraph, we obtain that all $g$ sets $U_i$ should have non-empty intersections with this subset. Again, the union of some finitely many small balls inscribed in these sets $U_i$ and centered at points of this fiber covers also some neighborhood in $J_{-1}$ of this fiber. This neighborhood contains some points, at which the map $\pi$ takes values to the right of $\omega_-$, and we again get a contradiction with the assumption that $\Omega_-$ is not empty. Lemma \ref{lem2} is proved. \medskip Therefore all functions $\varphi_i,$ $i=1, \dots, g$, take only positive values at the points of corresponding sets $U_i \cap \pi^{-1}([-3,0])$. In exactly the same way we prove that all these functions can take only negative values at the points of sets $U_i \cap \pi^{-1}([0,3])$. This gives us a contradiction on the fiber $\pi^{-1}(0)$, and Theorem is proved for $d \ge 3$. Finally, in the case $d=1$ the proof is almost the same, but with missing pieces $J_{-1}$ and $J_1$ of $\Im$, so that we need to consider a map $\pi$ of $\Im$ to the segment $[-2,2]$ (and not $[-3,3]$), sending $J_{-3}$ to $[-2,-1]$, $J_{-2}$ to $[-1,0]$, $J_2$ to $[0,1]$, and $J_3$ to $[1,2]$. \hfill $\Box$ \section{Schwarz type formula for the 0-genus} Along with the $\varepsilon$-genus $G(d,\varepsilon,T)$ we can define the number $G_0(d)$ as the minimal number of open sets covering $\R^d$ (or $B^d_T$), on any of which a continuous function is defined, whose value at the point $a$ is equal {\em exactly} to one of roots of the corresponding polynomial $F_a$. Obviously, $G_0(d) \ge G(d)$. An easy modification of arguments from \cite{schwarz} gives us the following criterion for $G_0(d)$. Define the $m$th power of the map (\ref{proj}) as the map whose fiber over $a \in B^d_T$ is the join of $m$ copies of the collection of real roots of $F_a$. More precisely, the $m$th join $(\R^1)^{\star m}$ of $\R^1$ can be considered as the (naturally topologized) union of $(m-1)$-dimensional simplices, whose vertices are some (maybe repeating) points of $\R^1$. Define the space $M^d_m$ as the union of all pairs $(Y,a) \in (\R^1)^{\star m} \times B^d_T$ where $Y$ is a point of a simplex, all whose vertices are some roots of $F_a$. \begin{prop} For any natural $m$ and odd $d$, $G_0(d) \le m$ if and only if the obvious map $M^d_m \to B^d_T$ has a continuous cross-section. \hfill $\Box$ \end{prop} But, unlike \cite{schwarz}, in our case the latter map is not a fiber bundle. \section{History of the problem} S.~Smale \cite{smale} has studied the topological complexity of algorithms finding approximate values of {\em all} $d$ roots of any complex polynomial of the form (\ref{maineq}). He has rediscovered (under the name {\em covering number}) the {\em Schwarz genus} \cite{schwarz} of fiber bundles, and also some homological lower estimate of this characteristic. In fact, Smale considered a more general situation of arbitrary surjective maps, which is, in particular, the case for the problem considered in the present article. Using the results of Arnold and Fuchs \cite{arnbr}, \cite{fuchs} on the cohomology of the space of complex polynomials without multiple roots, Smale has proved that the topological complexity $\tau(d)$ of this problem grows to infinity when $d$ does; namely, he proved the asymptotic lower bound $\tau(d) > (\log_2d)^{2/3}$. In \cite{smale} I have proved the asymptotically sharp two-sided estimate $\tau(d) \in [d-\min_p(D_p(d)), d-1]$, where $D_p(d)$ is the number of digits in the $p$-adic decomposition of $d$, $p$ a prime number. If $d$ is a power of a prime number, then both bounds are equal to $d-1$. Moreover, in this case even the problem of finding only one approximate root of any complex polynomial of the form (\ref{maineq}) has the same topological complexity: $\tau_1(d)=d-1$. For general $d$ the corresponding lower estimate is much worse: $\tau_1(d)+1$ is not less than the greatest power of a prime dividing $d$; by the asymptotical law of prime numbers, this gives us the asymptotic lower bound $\ln d$. In \cite{reality}, \cite{vsmale} I have noticed that this problem has a non-trivial real analog, namely, that the topological complexity of finding one real root of any real polynomial (\ref{maineq}) of odd degree $d \ge 3$ also is greater than 0. However, until now it was not clear whether the latter topological complexity grows infinitely together with $d$. \begin{thebibliography}{99} \bibitem{arn} V.I.~Arnold, On functions of three variables, Dokl. Akad. Nauk SSSR 114:4 (1957), Engl. transl. in: Amer. Math. Soc. Transl.(2) 28 (1963), 51--54, see also V.I.~Arnold, Collected Works, vol. 1, Springer, 2009. \bibitem{arnbr} V.I.~Arnold, On some topological invariants of algebraic functions, Trudy Moskov. Matem. Obshch. 21 (1970), 27--46, Engl. transl. in Transact. Moscow Math. Soc. 21 (1970), 30--52. \bibitem{avg} V.I.~Arnold, A.N.~Varchenko, S.M.~Gusein-Zade, Singularities of differentiable maps, $\mbox{MCCME}$, Moscow, 2009; Engl. transl. of 1st edition of vol.~1: Birkh\"auser, Basel, 1985. \bibitem{fuchs} D.B.~Fuchs, Cohomology of the braid group mod 2. Funct. Anal. Appl., 4:2 (1970), 62--73. \bibitem{hilb} D.~Hilbert, Mathematische Probleme. Vortrag, gehalten auf dem internationalen Mathematiker-Kongre\ss \ zu Paris 1900, \noindent http://www.mathematik.uni-bielefeld.de/$\ \widetilde {}\,$kersten/hilbert/rede.html \bibitem{kolm} A.N.~Kolmogorov, On the representation of continuous functions of several variables by superpositions of continuous functions of a smaller number of variables, Dokl. Akad. Nauk SSSR 108 (1956), 179--182. \bibitem{schwarz} A.S.~Schwarz, Genus of a Fibre Bundle, Transact. Moscow Math. Soc. 10 (1961), 217--272. \bibitem{smale} S.~Smale, On the topology of algorithms. J. of Complexity 3 (1987), 81--89. \bibitem{fvsmale} V.A.~Vassiliev, Cohomology of braid groups and complexity of algorithms, Funct. Anal. and its Appl., 22:3 (1988), p.~15--24. \bibitem{reality} V.A.~Vassiliev, Topological complexity and reality, Matem. Zametki (Math. Notes), 1996, 60:5, p.~270--280. \bibitem{vsmale} V.A.~Vassiliev, Topological complexity of root-finding algorithms, Proc. of the AMS/SIAM 1995 Summer Seminar; AMS, 1996, p.~831--856. \bibitem{vasbook} V.A.~Vassiliev, Complements of discriminants of smooth maps: topology and applications. 2nd edition. Translations of Math. Monographs, AMS, Providence RI, 1994, ix+268 pp. \end{thebibliography} \end{document}