%\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}
