% % Lower bounds for some decision problems over C % ===== ====== === ==== ======== ======== ==== = % % Gregorio Malajovich % % gregorio@labma.ufrj.br, gregorio@msri.org % % Jan 22, 1999 % % Lower bounds for some explicit decision problems over the % complex numbers are given. % % This is a LaTeX2e file. \begin{filecontents}{data1.eps} %!PS-Adobe-2.0 EPSF-2.0 %%Title: data1.eps %%Creator: gnuplot 3.5 (pre 3.6) patchlevel beta 340 %%CreationDate: Wed Oct 7 19:15:20 1998 %%DocumentFonts: (atend) %%BoundingBox: 50 50 410 302 %%Orientation: Portrait %%EndComments /gnudict 120 dict def gnudict begin /Color false def /Solid false def /gnulinewidth 5.000 def /userlinewidth gnulinewidth def /vshift -46 def /dl {10 mul} def /hpt_ 31.5 def /vpt_ 31.5 def /hpt hpt_ def /vpt vpt_ def /M {moveto} bind def /L {lineto} bind def /R {rmoveto} bind def /V {rlineto} bind def /vpt2 vpt 2 mul def /hpt2 hpt 2 mul def /Lshow { currentpoint stroke M 0 vshift R show } def /Rshow { currentpoint stroke M dup stringwidth pop neg vshift R show } def /Cshow { currentpoint stroke M dup stringwidth pop -2 div vshift R show } def /UP { dup vpt_ mul /vpt exch def hpt_ mul /hpt exch def /hpt2 hpt 2 mul def /vpt2 vpt 2 mul def } def /DL { Color {setrgbcolor Solid {pop []} if 0 setdash } {pop pop pop Solid {pop []} if 0 setdash} ifelse } def /BL { stroke gnulinewidth 2 mul setlinewidth } def /AL { stroke gnulinewidth 2 div setlinewidth } def /UL { gnulinewidth mul /userlinewidth exch def } def /PL { stroke userlinewidth setlinewidth } def /LTb { BL [] 0 0 0 DL } def /LTa { AL [1 dl 2 dl] 0 setdash 0 0 0 setrgbcolor } def /LT0 { PL [] 0 1 0 DL } def /LT1 { PL [4 dl 2 dl] 0 0 1 DL } def /LT2 { PL [2 dl 3 dl] 1 0 0 DL } def /LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def /LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def /LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def /LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def /LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def /LT8 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 0.5 0.5 0.5 DL } def /Pnt { stroke [] 0 setdash gsave 1 setlinecap M 0 0 V stroke grestore } def /Dia { stroke [] 0 setdash 2 copy vpt add M hpt neg vpt neg V hpt vpt neg V hpt vpt V hpt neg vpt V closepath stroke Pnt } def /Pls { stroke [] 0 setdash vpt sub M 0 vpt2 V currentpoint stroke M hpt neg vpt neg R hpt2 0 V stroke } def /Box { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add M 0 vpt2 neg V hpt2 0 V 0 vpt2 V hpt2 neg 0 V closepath stroke Pnt } def /Crs { stroke [] 0 setdash exch hpt sub exch vpt add M hpt2 vpt2 neg V currentpoint stroke M hpt2 neg 0 R hpt2 vpt2 V stroke } def /TriU { stroke [] 0 setdash 2 copy vpt 1.12 mul add M hpt neg vpt -1.62 mul V hpt 2 mul 0 V hpt neg vpt 1.62 mul V closepath stroke Pnt } def /Star { 2 copy Pls Crs } def /BoxF { stroke [] 0 setdash exch hpt sub exch vpt add M 0 vpt2 neg V hpt2 0 V 0 vpt2 V hpt2 neg 0 V closepath fill } def /TriUF { stroke [] 0 setdash vpt 1.12 mul add M hpt neg vpt -1.62 mul V hpt 2 mul 0 V hpt neg vpt 1.62 mul V closepath fill } def /TriD { stroke [] 0 setdash 2 copy vpt 1.12 mul sub M hpt neg vpt 1.62 mul V hpt 2 mul 0 V hpt neg vpt -1.62 mul V closepath stroke Pnt } def /TriDF { stroke [] 0 setdash vpt 1.12 mul sub M hpt neg vpt 1.62 mul V hpt 2 mul 0 V hpt neg vpt -1.62 mul V closepath fill} def /DiaF { stroke [] 0 setdash vpt add M hpt neg vpt neg V hpt vpt neg V hpt vpt V hpt neg vpt V closepath fill } def /Pent { stroke [] 0 setdash 2 copy gsave translate 0 hpt M 4 {72 rotate 0 hpt L} repeat closepath stroke grestore Pnt } def /PentF { stroke [] 0 setdash gsave translate 0 hpt M 4 {72 rotate 0 hpt L} repeat closepath fill grestore } def /Circle { stroke [] 0 setdash 2 copy hpt 0 360 arc stroke Pnt } def /CircleF { stroke [] 0 setdash hpt 0 360 arc fill } def /C0 { BL [] 0 setdash 2 copy moveto vpt 90 450 arc } bind def /C1 { BL [] 0 setdash 2 copy moveto 2 copy vpt 0 90 arc closepath fill vpt 0 360 arc closepath } bind def /C2 { BL [] 0 setdash 2 copy moveto 2 copy vpt 90 180 arc closepath fill vpt 0 360 arc closepath } bind def /C3 { BL [] 0 setdash 2 copy moveto 2 copy vpt 0 180 arc closepath fill vpt 0 360 arc closepath } bind def /C4 { BL [] 0 setdash 2 copy moveto 2 copy vpt 180 270 arc closepath fill vpt 0 360 arc closepath } bind def /C5 { BL [] 0 setdash 2 copy moveto 2 copy vpt 0 90 arc 2 copy moveto 2 copy vpt 180 270 arc closepath fill vpt 0 360 arc } bind def /C6 { BL [] 0 setdash 2 copy moveto 2 copy vpt 90 270 arc closepath fill vpt 0 360 arc closepath } bind def /C7 { BL [] 0 setdash 2 copy moveto 2 copy vpt 0 270 arc closepath fill vpt 0 360 arc closepath } bind def /C8 { BL [] 0 setdash 2 copy moveto 2 copy vpt 270 360 arc closepath fill vpt 0 360 arc closepath } bind def /C9 { BL [] 0 setdash 2 copy moveto 2 copy vpt 270 450 arc closepath fill vpt 0 360 arc closepath } bind def /C10 { BL [] 0 setdash 2 copy 2 copy moveto vpt 270 360 arc closepath fill 2 copy moveto 2 copy vpt 90 180 arc closepath fill vpt 0 360 arc closepath } bind def /C11 { BL [] 0 setdash 2 copy moveto 2 copy vpt 0 180 arc closepath fill 2 copy moveto 2 copy vpt 270 360 arc closepath fill vpt 0 360 arc closepath } bind def /C12 { BL [] 0 setdash 2 copy moveto 2 copy vpt 180 360 arc closepath fill vpt 0 360 arc closepath } bind def /C13 { BL [] 0 setdash 2 copy moveto 2 copy vpt 0 90 arc closepath fill 2 copy moveto 2 copy vpt 180 360 arc closepath fill vpt 0 360 arc closepath } bind def /C14 { BL [] 0 setdash 2 copy moveto 2 copy vpt 90 360 arc closepath fill vpt 0 360 arc } bind def /C15 { BL [] 0 setdash 2 copy vpt 0 360 arc closepath fill vpt 0 360 arc closepath } bind def /Rec { newpath 4 2 roll moveto 1 index 0 rlineto 0 exch rlineto neg 0 rlineto closepath } bind def /Square { dup Rec } bind def /Bsquare { vpt sub exch vpt sub exch vpt2 Square } bind def /S0 { BL [] 0 setdash 2 copy moveto 0 vpt rlineto BL Bsquare } bind def /S1 { BL [] 0 setdash 2 copy vpt Square fill Bsquare } bind def /S2 { BL [] 0 setdash 2 copy exch vpt sub exch vpt Square fill Bsquare } bind def /S3 { BL [] 0 setdash 2 copy exch vpt sub exch vpt2 vpt Rec fill Bsquare } bind def /S4 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def /S5 { BL [] 0 setdash 2 copy 2 copy vpt Square fill exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def /S6 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill Bsquare } bind def /S7 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill 2 copy vpt Square fill Bsquare } bind def /S8 { BL [] 0 setdash 2 copy vpt sub vpt Square fill Bsquare } bind def /S9 { BL [] 0 setdash 2 copy vpt sub vpt vpt2 Rec fill Bsquare } bind def /S10 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt Square fill Bsquare } bind def /S11 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt2 vpt Rec fill Bsquare } bind def /S12 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill Bsquare } bind def /S13 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill 2 copy vpt Square fill Bsquare } bind def /S14 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill 2 copy exch vpt sub exch vpt Square fill Bsquare } bind def /S15 { BL [] 0 setdash 2 copy Bsquare fill Bsquare } bind def /D0 { gsave translate 45 rotate 0 0 S0 stroke grestore } bind def /D1 { gsave translate 45 rotate 0 0 S1 stroke grestore } bind def /D2 { gsave translate 45 rotate 0 0 S2 stroke grestore } bind def /D3 { gsave translate 45 rotate 0 0 S3 stroke grestore } bind def /D4 { gsave translate 45 rotate 0 0 S4 stroke grestore } bind def /D5 { gsave translate 45 rotate 0 0 S5 stroke grestore } bind def /D6 { gsave translate 45 rotate 0 0 S6 stroke grestore } bind def /D7 { gsave translate 45 rotate 0 0 S7 stroke grestore } bind def /D8 { gsave translate 45 rotate 0 0 S8 stroke grestore } bind def /D9 { gsave translate 45 rotate 0 0 S9 stroke grestore } bind def /D10 { gsave translate 45 rotate 0 0 S10 stroke grestore } bind def /D11 { gsave translate 45 rotate 0 0 S11 stroke grestore } bind def /D12 { gsave translate 45 rotate 0 0 S12 stroke grestore } bind def /D13 { gsave translate 45 rotate 0 0 S13 stroke grestore } bind def /D14 { gsave translate 45 rotate 0 0 S14 stroke grestore } bind def /D15 { gsave translate 45 rotate 0 0 S15 stroke grestore } bind def /DiaE { stroke [] 0 setdash vpt add M hpt neg vpt neg V hpt vpt neg V hpt vpt V hpt neg vpt V closepath stroke } def /BoxE { stroke [] 0 setdash exch hpt sub exch vpt add M 0 vpt2 neg V hpt2 0 V 0 vpt2 V hpt2 neg 0 V closepath stroke } def /TriUE { stroke [] 0 setdash vpt 1.12 mul add M hpt neg vpt -1.62 mul V hpt 2 mul 0 V hpt neg vpt 1.62 mul V closepath stroke } def /TriDE { stroke [] 0 setdash vpt 1.12 mul sub M hpt neg vpt 1.62 mul V hpt 2 mul 0 V hpt neg vpt -1.62 mul V closepath stroke } def /PentE { stroke [] 0 setdash gsave translate 0 hpt M 4 {72 rotate 0 hpt L} repeat closepath stroke grestore } def /CircE { stroke [] 0 setdash hpt 0 360 arc stroke } def /BoxFill { gsave Rec 1 setgray fill grestore } def end %%EndProlog gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray newpath (Helvetica) findfont 140 scalefont setfont LTb 504 350 M 63 0 V 6549 0 R -63 0 V 420 350 M (0) Rshow 504 1000 M 63 0 V 6549 0 R -63 0 V -6633 0 R (10) Rshow 504 1650 M 63 0 V 6549 0 R -63 0 V -6633 0 R (20) Rshow 504 2300 M 63 0 V 6549 0 R -63 0 V -6633 0 R (30) Rshow 504 2950 M 63 0 V 6549 0 R -63 0 V -6633 0 R (40) Rshow 504 3600 M 63 0 V 6549 0 R -63 0 V -6633 0 R (50) Rshow 504 4250 M 63 0 V 6549 0 R -63 0 V -6633 0 R (60) Rshow 504 4900 M 63 0 V 6549 0 R -63 0 V -6633 0 R (70) Rshow 504 350 M 0 63 V 0 4487 R 0 -63 V 504 210 M (0) Cshow 1606 350 M 0 63 V 0 4487 R 0 -63 V 0 -4627 R (1) Cshow 2708 350 M 0 63 V 0 4487 R 0 -63 V 0 -4627 R (2) Cshow 3810 350 M 0 63 V 0 4487 R 0 -63 V 0 -4627 R (3) Cshow 4912 350 M 0 63 V 0 4487 R 0 -63 V 0 -4627 R (4) Cshow 6014 350 M 0 63 V 0 4487 R 0 -63 V 0 -4627 R (5) Cshow 7116 350 M 0 63 V 0 4487 R 0 -63 V 0 -4627 R (6) Cshow LTb 504 350 M 6612 0 V 0 4550 V -6612 0 V 504 350 L 1.000 UP 1.000 UL LT0 6465 4767 M ("lower.data") Rshow 6549 4767 M 399 0 V 504 415 M 1102 65 V 2708 610 L 3810 870 L 1102 520 V 6014 2430 L 7116 4510 L 504 415 Pls 1606 480 Pls 2708 610 Pls 3810 870 Pls 4912 1390 Pls 6014 2430 Pls 7116 4510 Pls 6748 4767 Pls stroke grestore end showpage %%Trailer %%DocumentFonts: Helvetica \end{filecontents} \begin{filecontents}{lower.bib} @INPROCEEDINGS{ AHMMP, AUTHOR= "Mikel Aldaz and Joos Heintz and Guillermo Matera and Jos{\'e} L. Monta{\~n}a and Luis M. Pardo", TITLE= "Combinatorial Hardness Proofs for Polynomial Evaluation", PAGES= "167-175", EDITOR= "Lubos Brim and Jozef Gruska and Jir{\'\i} Zlatuska", BOOKTITLE= "Mathematical Foundations of Computer Science 1998, 23rd International Symposium, MFCS'98, Brno, Czech Republic, August 24-28, 1998", SERIES = "Lecture Notes in Computer Science", VOLUME = "1450", EDITOR = "Springer", YEAR = "1998" } @UNPUBLISHED{AM98, AUTHOR = "Mikel Aldaz-Zarag{\"u}eta and Jos{\'e} Luis Monta{\~n}a-Arnaiz", TITLE = "Combinatorial Proofs for Transcendency of Formal Power Series (Extended abstract)", NOTE = "Universidad Publica de Navarra", MONTH = "May", YEAR = "1998" } @ARTICLE{STRASSEN74, AUTHOR = "Volker Strassen", TITLE = "Polynomials with Rational Coefficients which are Hard to Compute", JOURNAL = "SIAM Journal on Computing", VOLUME = "3", NUMBER = "2", PAGES = "128-149", YEAR = "1974" } @BOOK{BCS, AUTHOR = "Peter Burgisser and Michael Clausen and M. Amin Shokrollahi", TITLE = "Algebraic Complexity Theory", PUBLISHER = "Springer", SERIES = "Grundlehren der mathematischen Wissenchaften 315", ADDRESS = "Berlin", YEAR = "1997" } } @BOOK{LANG86, AUTHOR = "Serge Lang", TITLE = "Algebraic Number Theory", PUBLISHER = "Springer-Verlag", ADDRESS = "New York", YEAR = "1986" } @BOOK{BCSS98, AUTHOR = "Lenore Blum and Felipe Cucker and Mike Shub and Steve Smale", TITLE = "Complexity and Real Computation", PUBLISHER = "Springer", YEAR = "1998" } \end{filecontents} \documentclass{article} \usepackage{amsmath, amssymb, amsthm, amscd} %\usepackage{colordvi} %\usepackage{latexsym} \usepackage{graphics} \newtheorem{theorem} {Theorem} \newtheorem{maintheorem} {Theorem} \newtheorem{lemma} {Lemma} \newtheorem{lowerbound} {Lower bound} \newtheorem{proposition} {Proposition} \newtheorem{corollary} {Corollary} \theoremstyle{definition} \newtheorem{example} {Example} \newtheorem{remark} {Remark} \newtheorem{definition} {Definition} \newtheorem{induction} {Induction Hypothesis} \newtheorem{question} {Question} \newtheorem{problem} {Problem} \renewcommand{\themaintheorem}{\Alph{maintheorem}} \newcommand{\binomial}[2] {{\left(\begin{array}{c}#1\\#2\end{array}\right)}} \newcommand{\pnp} {$\mathcal P \ne \mathcal {NP}$\ } \newcommand{\pisnp} {$\mathcal P = \mathcal {NP}$\ } \newcommand{\qalg} {\mathbb Q^{\mathrm{a}}} \newcommand{\qralg} {\mathbb Q^{\mathrm{ra}}} \newcommand{\syl} {\mathrm{Syl}} \newcommand{\res} {\mathrm{Res}} \newcommand{\size} {\mathrm{Size}} \newcommand{\slashpoly} {\ensuremath{_\mathrm{/poly}}} \newcommand{\ppoly} {\ensuremath{\mathcal P\slashpoly}} \title{Lower bounds for some decision problems over $\mathbb C$} \author{Gregorio Malajovich\footnote{ Departamento de Matem\'atica Aplicada, Universidade Federal do Rio de Janeiro. Caixa Postal 68530, CEP 21945, Rio de Janeiro, RJ, Brasil. e-mail: gregorio@labma.ufrj.br. On leave at MSRI, 1000 Centennial Drive, Berkeley CA 94720-5070. e-mail: gregorio@msri.org }} \date{January 22, 1999} \begin{document} \maketitle \begin{abstract} Lower bounds for some explicit decision problems over the complex numbers are given. \end{abstract} \section{Introduction} This paper is about lower bounds for certain decision problems over $\mathbb C$. (See ~\cite{BCSS98} for the model of computation and for background). In particular, we will provide lower bounds for the complexity of deciding, given $x$, if $p^d(x)=0$ for some explicit polynomials $p^d$. \par A related problem is to give lower bounds for the evaluation of explicit polynomials. This has been an active subject of research since ~\cite{STRASSEN74}. See~\cite{BCS} for modern developments and for bibliographical remarks. More recent results appeared in~\cite{AHMMP} and~\cite{AM98}. \par Most of those bounds use the Ostrowsky model of computation ~(\cite{BCS} page 6): sum and multiplication by an algebraic constant are free, and the complexity of a computation for polynomial $f(x)$ is the number of non-scalar multiplications, i.e., of multiplications of two polynomials in the variable $x$. For instance, Horner rule for a degree $d$ polynomial requires $d$ non-scalar multiplications. \par All those bounds apply trivially to the complexity of evaluating polynomials by a `machine over $\mathbb C$' as defined in~\cite{BCSS98}, or to the (multiplicative-branching) complexity of a computation tree for evaluating the same polynomial. \par Little is known, however, about the application of those bounds to decision problems (Over $\mathbb C$, in the sense of ~\cite{BCSS98}, or by a decision tree as in~\cite{BCS}, Definition (4.19) page 115. In this definition, each node of a computation tree can perform one algebraic operation or comparison, and therefore a natural measure of complexity is the depth of the tree). \par In this paper, only decision problems of the form below will be considered: let $X \subseteq \mathbb N \times \mathbb C$, and let $X_d = \{ x \in \mathbb C : (d,x) \in X \}$. Typically, $d$ is the problem size and $\# X_d \le d$. One can think of $X$ as the disjoint union of the zero-set of a family of polynomials of degree $\le d$, where $d \in \mathbb N$. The two following forms of a decision problem are natural in this setting: \begin{problem} \label{pnu} For any fixed $d$, decide wether $x \in X_d$. \end{problem} \begin{problem} \label{pu} Decide wether $(d,x) \in X$ \end{problem} \medskip \par Problem~\ref{pnu} is non-uniform, in the sense that we allow for a different machine over $\mathbb C$ or a different decision tree to be used for each value of $d$. However, we want a bound on the running time or on the multiplicative complexity of the tree, as a function of $d$. \par Problem~\ref{pu} is uniform. It is harder than Problem~\ref{pnu}, in the sense that it cannot be solved by a decision tree, since $\# X_d$ can be arbitrarily large. It requires a machine over $\mathbb C$, that will eventually branch according to the value of $d$. \par Lower bounds for Problem~\ref{pnu} are also lower bounds for Problem~\ref{pu}. \par A trivial, topological lower bound for Problems~\ref{pnu} and~\ref{pu} when $\# X_d = d$ is $\log_2 d$. Sharper known bounds come from the `Canonical Path' argument, see ~\cite{BCSS98} section 2.5: Let $f$ be a univariate polynomial. The complexity of deciding $f(x)=0$ is bounded below by the minimum of the complexity of evaluating $g(x)$, where $g$ ranges over the non-zero multiples of $f$. \par If one assumes some property of $f$ that propagates to its multiple $g$, then one eventually obtains a sharper, non-trivial lower bounds. \par In Lemma ~\ref{lower1} below, we will give conditions on the roots of $f$ that will provide lower bounds for the evaluation of $g$. Essentially, we will require a subset of the roots to be rapidly growing. This will imply a rapid growth property for the coefficients of $g$. Then, the results of~\cite{AHMMP, AM98} imply a lower bound for the complexity of evaluating $g$. Thus we will be able to construct specific polynomials that are hard to decide in the {\em non-uniform} sense, viz. \begin{lowerbound} \label{low1} The set $X = \{ (d,x) \in \mathbb Z \times \mathbb C : x = 2^{2^{di}}, 0 \le i \le d$, cannot be solved in time polylog($d$) in the setting of Problem~\ref{pnu}. \end{lowerbound} \begin{lowerbound} \label{low2} The set $Y = \{ (d,x) \in \mathbb Z \times \mathbb C : p^{d}(x)=0 \}$, where $p^d(t) = \sum _{i=0}^d 2^{2^{d (d-i)}} t^i$, cannot be decided in time polylog($d$) in the setting of Problem~\ref{pnu}. \end{lowerbound} \par In a more classical computer-science language, we can define the input size of some $(d,x)$ as $\log d$. This means that the integer $d$ is represented in binary notation, while variable $x$ can contain an arbitrary complex number. In that case, `time polylog($d$) in the setting of Problem~\ref{pnu}' can be refrased as $\ppoly$. The lower bounds above become now: $X \not \in \ppoly$ and $Y \not \in \ppoly$. \par Non-uniform lower bounds ~\ref{low1} and ~\ref{low2} can be compared to the following easier, uniform lower bound: \begin{lowerbound}\label{low3} The set $Z = \{ (d,x) \in \mathbb Z \times \mathbb C : q^d(x)=0 \}$, where $q^d(t) = \sum _{i=0}^d 2^{2^i} t^i$, cannot be decided in time polylog($d$) in the setting of Problem~\ref{pu}. \end{lowerbound} \par This means that the set $Z$, where $d$ is represented in binary notation and $x$ is a complex number, does not belong to $\mathcal P$ over $\mathbb C$. \medskip \par This work was written while the author was visiting the Mathematical Sciences Research Institute, Berkeley, CA. Thanks to Pascal Koiran, Jos{\'e} Luis Monta\~na, Luis Pardo and Steve Smale for their suggestions and comments. \section{Background and notations} \begin{definition} Let $K \subset L$ be finite algebraic extensions of $\mathbb Q$. Let $\nu$ be a valuation in $M_K$. Then we extend the notation $\nu$ to $L$ by: \[ \nu(x) = \frac{ \sum_{\mu} n_{\mu} \mu(x) }{\deg[L:K]} \] where the sum ranges over all the valuations $\mu$ of $L$ that are `above' $\nu$, and where $n_{\mu}$ is the `local degree' of $L:K$. The local degree is defined as $n_{\mu} = \deg[ L_{\mu} : K_{\nu} ]$, where $K_{\nu}$ is the completion of $K$ under the metric induced by the absolute value $|.|_{\nu}$. \end{definition} Recall that for $x \in K$, $\deg[L:K] \nu(x) = \sum_{\mu} n_{\mu} \nu(x)$. The case $K = \mathbb Q$ is an immediate consequence of Corollary 2 of Theorem 1 in Chapter II, p. 39 of \cite{LANG86}. \begin{definition} Let $g$ be a polynomial with algebraic coefficients in some extension $K$ of $\mathbb Q$. Let $\nu$ be a valuation in $M_K$. The {\em Newton diagram} of $g$ at $\nu$ is the (lower) convex hull of the set $\{ (i, \nu(g_i)), i=0 \cdots d \}$. \end{definition} The basic property of Newton diagrams used here is the following. \begin{proposition}\label{prop1} Suppose that $\zeta_1, \cdots, \zeta_d$ are the roots of a univariate polynomial $g \in K[x]$. Let the roots of $g$ be ordered so that \[ \nu(\zeta_1) \ge \cdots \ge \nu(\zeta_d) \] and let the increasing sequence $i_j$ assume the values $0$, $d$ and all the values of $i$ where: \[ \nu(\zeta_i) > \nu(\zeta_{i+1}) \] \par Then the sharp corners of the Newton diagram are precisely the points of the form $(i_j, \nu(g_{i_j}))$ for all $j$. \par Moreover, the slope of the segment $[(i_{j-1}, \nu(g_{i_{j-1}})), (i_{j}, \nu(g_{i_{j}}))]$ is precisely $- \nu(\zeta_{i_{j}})$. \end{proposition} \begin{proof}[Proof of Proposition~\ref{prop1}] The proof uses the following property of valuations: $\nu (\sum x_i) \ge \min \nu (x_i)$. Furthermore, when that minimum is attained in only one $x_i$, we have equality. \par Let $i_{j-1} < k < i_j$. Writing \begin{eqnarray*} g_{i_{j-1}} &=& g_d \sigma_{d-i_{j-1}}(\zeta_1, \cdots, \zeta_d) \\ g_{k} &=& g_d \sigma_{d-k}(\zeta_1, \cdots, \zeta_d) \\ g_{i_{j}} &=& g_d \sigma_{d-i_{j}}(\zeta_1, \cdots, \zeta_d) \\ \end{eqnarray*} \par one can pass to the valuation by: \begin{eqnarray*} \nu(g_{i_{j-1}}) &=& \nu(g_d) + \nu(\zeta_{i_{j-1}+1}) + \cdots + \nu(\zeta_d) \\ \nu(g_{k}) &\ge& \nu(g_d) + \nu(\zeta_{k+1}) + \cdots + \nu(\zeta_d) \\ \nu(g_{i_{j}}) &=& \nu(g_d) + \nu(\zeta_{i_{j}+1}) + \cdots + \nu(\zeta_d) \\ \end{eqnarray*} \par Subtracting, one obtains: \begin{eqnarray*} \nu(g_{i_j}) - \nu(g_{i_{j-1}}) &=& -\nu(\zeta_{i_{j-1}+1}) - \cdots - \nu(\zeta_{i_{j}}) \\ &=& - (i_j - i_{j-1}) \nu(\zeta_{i_j}) \\ \nu(g_{i_j}) - \nu(g_{k}) &\le& -\nu(\zeta_{k+1}) - \cdots - \nu(\zeta_{i_{j}}) \\ &\le& - (i_j - k) \nu(\zeta_{i_j}) \\ \end{eqnarray*} \par This concludes the proof. \end{proof} \medskip \par \section{Uniform lower bounds} We can now prove Lower Bound~\ref{low3}. \begin{proof}[Proof of Lower bound~\ref{low3}] \centerline{\resizebox{10cm}{6cm}{\includegraphics{data1.eps}}} The Newton diagram of $q^{d}$ at 2 is $\{ (i, 2^i): 0 \le i \le d\}$. (This latest set is convex, since the points lie on the curve $y=2^x$ and this curve is convex). Therefore, there is a unique root $\zeta$ of $q^{d}$ that minimizes $\nu(\zeta)$. \par Since $q^{d}_{d-1} = (-\sum \zeta_i) q^{d}_d$, where the sum ranges over all the roots, we have: \[ \nu_2 (q^{d}_{d-1}) = \nu_2 (q^{d}_{d}) + \min \nu_2(\zeta_i) = \nu_2 (q^{d}_{d}) + \nu_2(\zeta) \] Replacing by the actual values of the coefficients, one gets: \begin{equation}\label{eq1} \nu_2(\zeta) = -2^{d-1} \end{equation} \medskip \par Now, suppose that there is a machine $M$ that decides $q^{d}(t) = 0$ in time polylog($d$). One can assume without loss of generality that this machine has no constant but $0$ and $1$. Let its running time be bounded by $T=a (\log d)^b$. \par Let us fix $d > 2+T^2$. We will derive a contradiction. \par Let $g$ be the polynomial defining the canonical path (recall that $d$ is fixed now, so this is the path followed by generic $t \in \mathbb C$). It can be computed in time $\le T^2$, so we have the following bounds: \begin{eqnarray*} \deg g &\le 2^{T^2} \\ 0\le \nu_2 (g_p) &\le 2^{T^2} \end{eqnarray*} \par Since $\zeta$ is also a root of $g$, there are coefficients $g_i$ and $g_j$, $i \ne j$, such that: \begin{equation}\label{eq2} (j-i) \nu_2(\zeta) = \nu_2(g_i) - \nu_2 (g_j) \end{equation} \par Thus, $|\nu_2(\zeta)| \le |\nu_2(g_i)|+|\nu_2(g_i)|$. This implies: \[ |\nu_2(\zeta)| \le {2^{1+T^2}} < 2^{d-1} \] Replacing by equation~\ref{eq1}, one obtains $2^{d-1}<2^{d-1}$, a contradiction. \end{proof} \section{Non-uniform lower bounds} \begin{lemma}\label{lower1} Let $g=g(t)$ be a degree $D$ polynomial with algebraic coefficients. Let $\nu$ be a (non-archimedian) valuation of $K=\mathbb Q[g_0, \cdots, g_D]$. Let $\xi_1, \cdots \xi_D$ be the roots of $g$, and assume they are ordered in such way that: \[ \nu(\xi_1) \ge \cdots \ge \nu(\xi_D) \] Suppose that there is a subsequence $\zeta_j = \xi_{i_j+1}$, $j=1 \cdots d$, such that the following holds: \begin{enumerate} \item $\nu(\zeta_d) \ge 1$ \item $\nu(\zeta_{j}) \ge 2 (i_{j+1} - i_{j}) \ \nu(\zeta_{j+1})$, for $0 \le j \le d-1$. \end{enumerate} \medskip \par Then $g$ cannot be evaluated in less than \[ L \ge \sqrt{ \frac{d}{28 \log_2 D+1} } \] multiplications. \end{lemma} \begin{proof}[Proof of Lemma~\ref{lower1}] We can assume without loss of generality that the ordering of the $\xi_i$ satisfies: \[ \cdots \xi_{i_j} < \xi_{i_j+1} = \zeta_j \le \xi_{i_j +2} \cdots \] For $j \in \{1, \cdots , d-1 \}$ we have: \[ \nu ( g_{i_j} ) - \nu (g_{i_{j+1}} ) = \nu(\xi_{i_j+1}) + \cdots + \nu(\xi_{i_{j+1}}) \] Hence, using $\nu(\xi_{i_{j+1}}) > \nu(\zeta_d) \ge 1$: \[ \nu(\zeta_j) \le \nu ( g_{i_j} ) - \nu (g_{i_{j+1}} ) \le (i_{j+1} - i_{j}) \nu (\zeta_j) \] By the same argument, for $j \in \{0, \cdots , d-2\}$: \[ \nu(\zeta_{j+1}) \le \nu ( g_{i_{j+1}} ) - \nu (g_{i_{j+2}} ) \le (i_{j+2} - i_{j+1}) \nu (\zeta_{j+1}) \] \par Hence, \[ \frac{ \nu ( g_{i_j} ) - \nu (g_{i_{j+1}} ) } { \nu ( g_{i_{j+1}} ) - \nu (g_{i_{j+2}} ) } \ge \frac {\nu(\zeta_{j})} {(i_{j+1} - i_{j}) \nu (\zeta_{j+1})} \ge 2 \] \par Set $G_j = \nu(g_{i_j})$ for $j=0, \cdots, d-1$. We know that the $G_j$ are such that $|G_{j+1} - G_j| < \frac{1}{2} |G_j - G_{j-1}|$. Hence \[ \# \{ \sum s_j G_j, s_j \in \{0;1\} \} = 2^d \] \par Hence: \[ \# \{ \nu (\prod_{s \in S} g_{s}) , S \subset \{0, \cdots, D\} \} \ge 2^d \] \par and hence \[ \mu(g) = \# \{ \sum_{S \subset \{0, \cdots, D\}} \theta_S \prod_{s \in S} g_{s} , \theta_S \in \{0;1\} \} \ge 2^{2^d} \] \par By Lemma~1 in~\cite{AHMMP} or by Lemma 4 in~\cite{AM98}, \[ \mu(g) \le 2^{ (D+1)^{28 L^2} } \] and hence, taking logs: \[ (D+1)^{28 L^2} \ge 2^d \] Taking logs again: \[ 28 L^2 \ge \frac{d}{\log_2 D+1} \] and hence: \[ L \ge \sqrt{ \frac{d}{28 \log_2 D+1} } \] \end{proof} \par Note: Lemma~1 in~\cite{AHMMP} is slightly more general than Lemma~4 in~\cite{AM98}. However, using Lemma~4 in~\cite{AM98} it is possible to replace all the appearances of the number 28 in the statement and proof of Lemma~\ref{lower1} above by the number 21. \par \begin{proof}[Proof of Lower Bound~\ref{low2}] We see from its Netwon diagram that the polynomial $p$ has distinct roots $\zeta_1, \cdots \zeta_d$ with: \[ \nu_2 ( \zeta_i ) = 2^{d (d-i+1)} - 2^{d (d-i)} = 2^{d (d-i)} (2^d - 1) \] \par So we have $\nu_2 (\zeta_d) = 2^d - 1 > 1$, and \begin{equation}\label{rationu} \nu_2(\zeta_i) / \nu_2(\zeta_{i+1}) = 2^d \end{equation} \par Assume that there are $a, b$ such that for each $d$, there is a machine $M$ over $\mathbb C$ deciding $p(t)=0$ in time $T= a (\log d)^b$. Its generic path is defined by a polynomial $g(t)$ of degree $\le 2^T$. \par Let us fix $d > 28 (T+1) T^2$. In particular $d \ge T+1$. We are in the conditions of Lemma~\ref{lower1}, where $D=2^T$. From that Lemma, it follows that \[ T \ge \sqrt{ \frac{d}{28 \log_2 2^T +1} } \ge \sqrt{ \frac{d}{28 (T+1)} } \] Hence, \[ 28 T^2 (T+1) \ge d \] contradicting our choice of $d$. \end{proof} Equation ~(\ref{rationu}) holds trivially in the proof of Lower bound~\ref{low1}. The rest of the proof is verbatim the same. \bibliographystyle{plain} \bibliography{lower} \end{document}