% % % On the Geometry of Graeffe Iteration % % % by % % % Gregorio Malajovich (gregorio@labma.ufrj.br) % % and % % Jorge P. Zubelli (zubelli@impa.br) % % % Second Revision: August 20, 1999 % % This is a LaTeX2e file. It uses the AMS-LaTeX package. % Several encapsulated postscript follow. TeX is after. % % % \begin{filecontents}{newt1.eps} %% LaTeX2e file `newt1.eps' %% generated by the `filecontents' environment %% from source `graeffe' on 1997/06/14. %% %!PS-Adobe-2.0 EPSF-2.0 %%Creator: gnuplot %%DocumentFonts: Helvetica %%BoundingBox: 50 50 410 302 %%EndComments /gnudict 40 dict def gnudict begin /Color false def /Solid false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 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 /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 /PL { stroke gnulinewidth 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 /P { stroke [] 0 setdash currentlinewidth 2 div sub M 0 currentlinewidth V stroke } def /D { 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 P } def /A { stroke [] 0 setdash vpt sub M 0 vpt2 V currentpoint stroke M hpt neg vpt neg R hpt2 0 V stroke } def /B { 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 P } def /C { 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 /T { 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 P } def /S { 2 copy A C} def end %%EndProlog gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Helvetica findfont 140 scalefont setfont newpath LTa 672 211 M 0 4618 V LTb 672 211 M 63 0 V 6234 0 R -63 0 V 588 211 M (-45) Rshow 672 788 M 63 0 V 6234 0 R -63 0 V 588 788 M (-40) Rshow 672 1366 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-35) Rshow 672 1943 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-30) Rshow 672 2520 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-25) Rshow 672 3097 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-20) Rshow 672 3675 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-15) Rshow 672 4252 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-10) Rshow 672 4829 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-5) Rshow 672 211 M 0 63 V 0 4555 R 0 -63 V 672 71 M (0) Cshow 1302 211 M 0 63 V 0 4555 R 0 -63 V 1302 71 M (2) Cshow 1931 211 M 0 63 V 0 4555 R 0 -63 V 1931 71 M (4) Cshow 2561 211 M 0 63 V 0 4555 R 0 -63 V 2561 71 M (6) Cshow 3191 211 M 0 63 V 0 4555 R 0 -63 V 3191 71 M (8) Cshow 3821 211 M 0 63 V 0 4555 R 0 -63 V 3821 71 M (10) Cshow 4450 211 M 0 63 V 0 4555 R 0 -63 V 4450 71 M (12) Cshow 5080 211 M 0 63 V 0 4555 R 0 -63 V 5080 71 M (14) Cshow 5710 211 M 0 63 V 0 4555 R 0 -63 V 5710 71 M (16) Cshow 6339 211 M 0 63 V 0 4555 R 0 -63 V 6339 71 M (18) Cshow 6969 211 M 0 63 V 0 4555 R 0 -63 V 6969 71 M (20) Cshow 672 211 M 6297 0 V 0 4618 V -6297 0 V 672 211 L 3820 4969 M (Perfidous polynomial of degree 20, before iteration) Cshow LT0 6486 4626 M ("perfidous.20.initial") Rshow 6654 4626 D 672 519 D 987 371 D 1302 318 D 1617 326 D 1931 381 D 2246 473 D 2561 600 D 2876 756 D 3191 940 D 3506 1151 D 3821 1388 D 4135 1649 D 4450 1936 D 4765 2249 D 5080 2587 D 5395 2954 D 5710 3352 D 6024 3785 D 6339 4259 D 6654 4789 D stroke grestore end showpage %%Trailer \end{filecontents} \begin{filecontents}{newt2.eps} %% LaTeX2e file `newt2.eps' %% generated by the `filecontents' environment %% from source `graeffe' on 1997/06/14. %% %!PS-Adobe-2.0 EPSF-2.0 %%Creator: gnuplot %%DocumentFonts: Helvetica %%BoundingBox: 50 50 410 302 %%EndComments /gnudict 40 dict def gnudict begin /Color false def /Solid false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 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 /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 /PL { stroke gnulinewidth 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 /P { stroke [] 0 setdash currentlinewidth 2 div sub M 0 currentlinewidth V stroke } def /D { 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 P } def /A { stroke [] 0 setdash vpt sub M 0 vpt2 V currentpoint stroke M hpt neg vpt neg R hpt2 0 V stroke } def /B { 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 P } def /C { 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 /T { 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 P } def /S { 2 copy A C} def end %%EndProlog gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Helvetica findfont 140 scalefont setfont newpath LTa 672 211 M 0 4618 V LTb 672 211 M 63 0 V 6234 0 R -63 0 V 588 211 M (-45) Rshow 672 724 M 63 0 V 6234 0 R -63 0 V 588 724 M (-40) Rshow 672 1237 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-35) Rshow 672 1750 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-30) Rshow 672 2263 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-25) Rshow 672 2777 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-20) Rshow 672 3290 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-15) Rshow 672 3803 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-10) Rshow 672 4316 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-5) Rshow 672 4829 M 63 0 V 6234 0 R -63 0 V -6318 0 R (0) Rshow 672 211 M 0 63 V 0 4555 R 0 -63 V 672 71 M (0) Cshow 1302 211 M 0 63 V 0 4555 R 0 -63 V 1302 71 M (2) Cshow 1931 211 M 0 63 V 0 4555 R 0 -63 V 1931 71 M (4) Cshow 2561 211 M 0 63 V 0 4555 R 0 -63 V 2561 71 M (6) Cshow 3191 211 M 0 63 V 0 4555 R 0 -63 V 3191 71 M (8) Cshow 3821 211 M 0 63 V 0 4555 R 0 -63 V 3821 71 M (10) Cshow 4450 211 M 0 63 V 0 4555 R 0 -63 V 4450 71 M (12) Cshow 5080 211 M 0 63 V 0 4555 R 0 -63 V 5080 71 M (14) Cshow 5710 211 M 0 63 V 0 4555 R 0 -63 V 5710 71 M (16) Cshow 6339 211 M 0 63 V 0 4555 R 0 -63 V 6339 71 M (18) Cshow 6969 211 M 0 63 V 0 4555 R 0 -63 V 6969 71 M (20) Cshow 672 211 M 6297 0 V 0 4618 V -6297 0 V 672 211 L 3820 4969 M (Perfidous polynomial of degree 20, after iteration) Cshow LT0 6486 4626 M ("perfidous.20.final") Rshow 6654 4626 D 672 484 D 987 484 D 1302 556 D 1617 668 D 1931 811 D 2246 976 D 2561 1160 D 2876 1359 D 3191 1573 D 3506 1798 D 3821 2034 D 4135 2281 D 4450 2536 D 4765 2799 D 5080 3070 D 5395 3348 D 5710 3632 D 6024 3923 D 6339 4219 D 6654 4522 D stroke grestore end showpage %%Trailer \end{filecontents} \begin{filecontents}{newt3.eps} %% LaTeX2e file `newt3.eps' %% generated by the `filecontents' environment %% from source `graeffe' on 1997/06/14. %% %!PS-Adobe-2.0 EPSF-2.0 %%Creator: gnuplot %%DocumentFonts: Helvetica %%BoundingBox: 50 50 410 302 %%EndComments /gnudict 40 dict def gnudict begin /Color false def /Solid false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 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 /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 /PL { stroke gnulinewidth 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 /P { stroke [] 0 setdash currentlinewidth 2 div sub M 0 currentlinewidth V stroke } def /D { 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 P } def /A { stroke [] 0 setdash vpt sub M 0 vpt2 V currentpoint stroke M hpt neg vpt neg R hpt2 0 V stroke } def /B { 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 P } def /C { 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 /T { 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 P } def /S { 2 copy A C} def end %%EndProlog gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Helvetica findfont 140 scalefont setfont newpath LTa 672 4252 M 6297 0 V 672 211 M 0 4618 V LTb 672 211 M 63 0 V 6234 0 R -63 0 V 588 211 M (-350) Rshow 672 788 M 63 0 V 6234 0 R -63 0 V 588 788 M (-300) Rshow 672 1365 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-250) Rshow 672 1943 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-200) Rshow 672 2520 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-150) Rshow 672 3097 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-100) Rshow 672 3674 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-50) Rshow 672 4252 M 63 0 V 6234 0 R -63 0 V -6318 0 R (0) Rshow 672 4829 M 63 0 V 6234 0 R -63 0 V -6318 0 R (50) Rshow 672 211 M 0 63 V 0 4555 R 0 -63 V 672 71 M (0) Cshow 1302 211 M 0 63 V 0 4555 R 0 -63 V 1302 71 M (100) Cshow 1931 211 M 0 63 V 0 4555 R 0 -63 V 1931 71 M (200) Cshow 2561 211 M 0 63 V 0 4555 R 0 -63 V 2561 71 M (300) Cshow 3191 211 M 0 63 V 0 4555 R 0 -63 V 3191 71 M (400) Cshow 3820 211 M 0 63 V 0 4555 R 0 -63 V 3820 71 M (500) Cshow 4450 211 M 0 63 V 0 4555 R 0 -63 V 4450 71 M (600) Cshow 5080 211 M 0 63 V 0 4555 R 0 -63 V 5080 71 M (700) Cshow 5710 211 M 0 63 V 0 4555 R 0 -63 V 5710 71 M (800) Cshow 6339 211 M 0 63 V 0 4555 R 0 -63 V 6339 71 M (900) Cshow 6969 211 M 0 63 V 0 4555 R 0 -63 V 6969 71 M (1000) Cshow 672 211 M 6297 0 V 0 4618 V -6297 0 V 672 211 L 3820 4969 M (Generic polynomial of degree 1000, before iteration) Cshow LT0 6486 4626 M ("generic.1000.initial") Rshow 6654 4626 P 672 4289 P 678 4247 P 685 4212 P 691 4188 P 697 4148 P 703 4126 P 710 4100 P 716 4059 P 722 4034 P 729 4029 P 735 4000 P 741 3959 P 748 3923 P 754 3919 P 760 3889 P 766 3858 P 773 3849 P 779 3802 P 785 3800 P 792 3777 P 798 3735 P 804 3727 P 811 3692 P 817 3671 P 823 3664 P 829 3635 P 836 3605 P 842 3588 P 848 3569 P 855 3548 P 861 3528 P 867 3503 P 874 3492 P 880 3464 P 886 3455 P 892 3426 P 899 3412 P 905 3409 P 911 3374 P 918 3351 P 924 3335 P 930 3320 P 936 3296 P 943 3287 P 949 3261 P 955 3245 P 962 3231 P 968 3212 P 974 3221 P 981 3176 P 987 3180 P 993 3169 P 999 3134 P 1006 3125 P 1012 3110 P 1018 3080 P 1025 3064 P 1031 3058 P 1037 3100 P 1044 3017 P 1050 2995 P 1056 3025 P 1062 2963 P 1069 2973 P 1075 2932 P 1081 2941 P 1088 2902 P 1094 2891 P 1100 2869 P 1106 2862 P 1113 2844 P 1119 2830 P 1125 2809 P 1132 2799 P 1138 2780 P 1144 2770 P 1151 2755 P 1157 2749 P 1163 2743 P 1169 2714 P 1176 2694 P 1182 2689 P 1188 2668 P 1195 2656 P 1201 2647 P 1207 2633 P 1214 2620 P 1220 2610 P 1226 2590 P 1232 2575 P 1239 2574 P 1245 2544 P 1251 2560 P 1258 2528 P 1264 2508 P 1270 2536 P 1277 2484 P 1283 2472 P 1289 2463 P 1295 2453 P 1302 2433 P 1308 2436 P 1314 2404 P 1321 2393 P 1327 2400 P 1333 2381 P 1339 2354 P 1346 2343 P 1352 2335 P 1358 2327 P 1365 2306 P 1371 2294 P 1377 2283 P 1384 2283 P 1390 2264 P 1396 2246 P 1402 2244 P 1409 2227 P 1415 2219 P 1421 2215 P 1428 2200 P 1434 2202 P 1440 2164 P 1447 2157 P 1453 2166 P 1459 2159 P 1465 2135 P 1472 2108 P 1478 2102 P 1484 2109 P 1491 2074 P 1497 2065 P 1503 2056 P 1510 2050 P 1516 2056 P 1522 2024 P 1528 2011 P 1535 2016 P 1541 1992 P 1547 1993 P 1554 1975 P 1560 1966 P 1566 1960 P 1572 1939 P 1579 1935 P 1585 1926 P 1591 1910 P 1598 1896 P 1604 1886 P 1610 1895 P 1617 1868 P 1623 1858 P 1629 1846 P 1635 1840 P 1642 1830 P 1648 1846 P 1654 1817 P 1661 1804 P 1667 1803 P 1673 1778 P 1680 1803 P 1686 1764 P 1692 1790 P 1698 1745 P 1705 1735 P 1711 1733 P 1717 1713 P 1724 1732 P 1730 1695 P 1736 1686 P 1742 1679 P 1749 1668 P 1755 1659 P 1761 1649 P 1768 1652 P 1774 1646 P 1780 1625 P 1787 1617 P 1793 1626 P 1799 1594 P 1805 1591 P 1812 1588 P 1818 1571 P 1824 1594 P 1831 1581 P 1837 1551 P 1843 1533 P 1850 1536 P 1856 1515 P 1862 1507 P 1868 1511 P 1875 1500 P 1881 1488 P 1887 1493 P 1894 1470 P 1900 1465 P 1906 1458 P 1913 1451 P 1919 1458 P 1925 1429 P 1931 1424 P 1938 1431 P 1944 1429 P 1950 1441 P 1957 1391 P 1963 1393 P 1969 1392 P 1975 1384 P 1982 1358 P 1988 1353 P 1994 1368 P 2001 1345 P 2007 1352 P 2013 1334 P 2020 1329 P 2026 1303 P 2032 1301 P 2038 1290 P 2045 1282 P 2051 1280 P 2057 1265 P 2064 1260 P 2070 1278 P 2076 1254 P 2083 1247 P 2089 1234 P 2095 1245 P 2101 1219 P 2108 1214 P 2114 1221 P 2120 1194 P 2127 1205 P 2133 1181 P 2139 1178 P 2145 1168 P 2152 1176 P 2158 1154 P 2164 1150 P 2171 1148 P 2177 1139 P 2183 1129 P 2190 1128 P 2196 1126 P 2202 1116 P 2208 1099 P 2215 1097 P 2221 1097 P 2227 1098 P 2234 1075 P 2240 1073 P 2246 1065 P 2253 1073 P 2259 1048 P 2265 1053 P 2271 1046 P 2278 1030 P 2284 1048 P 2290 1017 P 2297 1012 P 2303 1028 P 2309 1010 P 2316 1003 P 2322 990 P 2328 988 P 2334 975 P 2341 977 P 2347 973 P 2353 969 P 2360 952 P 2366 947 P 2372 952 P 2378 940 P 2385 928 P 2391 932 P 2397 920 P 2404 918 P 2410 909 P 2416 922 P 2423 937 P 2429 907 P 2435 921 P 2441 887 P 2448 888 P 2454 894 P 2460 869 P 2467 878 P 2473 877 P 2479 847 P 2486 886 P 2492 860 P 2498 837 P 2504 827 P 2511 829 P 2517 824 P 2523 812 P 2530 807 P 2536 825 P 2542 806 P 2549 806 P 2555 790 P 2561 788 P 2567 778 P 2574 780 P 2580 782 P 2586 767 P 2593 759 P 2599 763 P 2605 765 P 2611 744 P 2618 750 P 2624 740 P 2630 776 P 2637 731 P 2643 726 P 2649 720 P 2656 711 P 2662 719 P 2668 723 P 2674 720 P 2681 700 P 2687 709 P 2693 692 P 2700 681 P 2706 683 P 2712 699 P 2719 671 P 2725 663 P 2731 660 P 2737 658 P 2744 658 P 2750 656 P 2756 643 P 2763 640 P 2769 645 P 2775 631 P 2781 627 P 2788 625 P 2794 637 P 2800 627 P 2807 614 P 2813 616 P 2819 620 P 2826 600 P 2832 624 P 2838 592 P 2844 592 P 2851 585 P 2857 580 P 2863 591 P 2870 612 P 2876 580 P 2882 600 P 2889 562 P 2895 564 P 2901 561 P 2907 564 P 2914 559 P 2920 589 P 2926 547 P 2933 539 P 2939 537 P 2945 537 P 2952 530 P 2958 544 P 2964 541 P 2970 526 P 2977 524 P 2983 533 P 2989 519 P 2996 508 P 3002 527 P 3008 506 P 3014 501 P 3021 531 P 3027 518 P 3033 492 P 3040 516 P 3046 508 P 3052 480 P 3059 497 P 3065 517 P 3071 477 P 3077 481 P 3084 465 P 3090 486 P 3096 470 P 3103 467 P 3109 454 P 3115 455 P 3122 451 P 3128 449 P 3134 444 P 3140 450 P 3147 462 P 3153 437 P 3159 435 P 3166 479 P 3172 434 P 3178 435 P 3185 434 P 3191 440 P 3197 423 P 3203 431 P 3210 415 P 3216 432 P 3222 423 P 3229 411 P 3235 410 P 3241 421 P 3247 415 P 3254 401 P 3260 401 P 3266 412 P 3273 430 P 3279 399 P 3285 408 P 3292 395 P 3298 394 P 3304 408 P 3310 387 P 3317 404 P 3323 419 P 3329 392 P 3336 419 P 3342 387 P 3348 374 P 3355 384 P 3361 372 P 3367 400 P 3373 377 P 3380 387 P 3386 361 P 3392 365 P 3399 407 P 3405 379 P 3411 364 P 3417 356 P 3424 389 P 3430 381 P 3436 355 P 3443 348 P 3449 348 P 3455 376 P 3462 344 P 3468 351 P 3474 359 P 3480 343 P 3487 340 P 3493 342 P 3499 339 P 3506 374 P 3512 354 P 3518 344 P 3525 338 P 3531 331 P 3537 331 P 3543 350 P 3550 330 P 3556 329 P 3562 325 P 3569 334 P 3575 331 P 3581 324 P 3588 324 P 3594 329 P 3600 323 P 3606 321 P 3613 319 P 3619 329 P 3625 339 P 3632 322 P 3638 318 P 3644 317 P 3650 318 P 3657 332 P 3663 339 P 3669 333 P 3676 331 P 3682 312 P 3688 312 P 3695 355 P 3701 328 P 3707 311 P 3713 328 P 3720 310 P 3726 311 P 3732 311 P 3739 310 P 3745 310 P 3751 322 P 3758 311 P 3764 309 P 3770 310 P 3776 325 P 3783 313 P 3789 310 P 3795 312 P 3802 306 P 3808 307 P 3814 343 P 3820 324 P 3827 317 P 3833 307 P 3839 306 P 3846 344 P 3852 306 P 3858 312 P 3865 306 P 3871 341 P 3877 306 P 3883 311 P 3890 319 P 3896 324 P 3902 333 P 3909 319 P 3915 320 P 3921 346 P 3928 312 P 3934 316 P 3940 351 P 3946 320 P 3953 329 P 3959 324 P 3965 321 P 3972 318 P 3978 324 P 3984 356 P 3991 335 P 3997 319 P 4003 319 P 4009 328 P 4016 327 P 4022 328 P 4028 345 P 4035 349 P 4041 339 P 4047 327 P 4053 330 P 4060 323 P 4066 333 P 4072 333 P 4079 326 P 4085 357 P 4091 335 P 4098 331 P 4104 343 P 4110 332 P 4116 373 P 4123 367 P 4129 334 P 4135 344 P 4142 338 P 4148 351 P 4154 341 P 4161 342 P 4167 343 P 4173 371 P 4179 354 P 4186 346 P 4192 363 P 4198 353 P 4205 352 P 4211 378 P 4217 359 P 4224 362 P 4230 357 P 4236 361 P 4242 366 P 4249 372 P 4255 365 P 4261 386 P 4268 368 P 4274 381 P 4280 380 P 4286 386 P 4293 376 P 4299 385 P 4305 378 P 4312 389 P 4318 409 P 4324 389 P 4331 384 P 4337 428 P 4343 415 P 4349 393 P 4356 389 P 4362 394 P 4368 395 P 4375 397 P 4381 435 P 4387 408 P 4394 403 P 4400 408 P 4406 407 P 4412 416 P 4419 414 P 4425 420 P 4431 426 P 4438 425 P 4444 430 P 4450 428 P 4456 434 P 4463 436 P 4469 446 P 4475 434 P 4482 434 P 4488 438 P 4494 443 P 4501 446 P 4507 456 P 4513 453 P 4519 483 P 4526 465 P 4532 465 P 4538 467 P 4545 464 P 4551 473 P 4557 466 P 4564 489 P 4570 496 P 4576 535 P 4582 480 P 4589 492 P 4595 482 P 4601 493 P 4608 494 P 4614 519 P 4620 505 P 4627 511 P 4633 500 P 4639 513 P 4645 513 P 4652 511 P 4658 513 P 4664 518 P 4671 536 P 4677 538 P 4683 593 P 4689 541 P 4696 540 P 4702 536 P 4708 552 P 4715 550 P 4721 552 P 4727 553 P 4734 570 P 4740 556 P 4746 559 P 4752 575 P 4759 583 P 4765 586 P 4771 576 P 4778 578 P 4784 583 P 4790 591 P 4797 589 P 4803 594 P 4809 603 P 4815 601 P 4822 613 P 4828 610 P 4834 649 P 4841 619 P 4847 655 P 4853 625 P 4860 627 P 4866 635 P 4872 636 P 4878 637 P 4885 645 P 4891 650 P 4897 650 P 4904 695 P 4910 689 P 4916 690 P 4922 670 P 4929 670 P 4935 687 P 4941 684 P 4948 685 P 4954 690 P 4960 703 P 4967 703 P 4973 707 P 4979 724 P 4985 723 P 4992 720 P 4998 731 P 5004 730 P 5011 742 P 5017 732 P 5023 737 P 5030 750 P 5036 757 P 5042 758 P 5048 756 P 5055 775 P 5061 776 P 5067 780 P 5074 790 P 5080 786 P 5086 799 P 5092 806 P 5099 798 P 5105 831 P 5111 820 P 5118 827 P 5124 827 P 5130 849 P 5137 826 P 5143 840 P 5149 837 P 5155 848 P 5162 853 P 5168 877 P 5174 859 P 5181 869 P 5187 887 P 5193 878 P 5200 884 P 5206 889 P 5212 898 P 5218 901 P 5225 905 P 5231 922 P 5237 911 P 5244 940 P 5250 933 P 5256 936 P 5263 943 P 5269 954 P 5275 949 P 5281 954 P 5288 958 P 5294 1004 P 5300 994 P 5307 981 P 5313 994 P 5319 989 P 5325 997 P 5332 1022 P 5338 1013 P 5344 1027 P 5351 1031 P 5357 1029 P 5363 1051 P 5370 1051 P 5376 1055 P 5382 1047 P 5388 1054 P 5395 1074 P 5401 1090 P 5407 1092 P 5414 1080 P 5420 1120 P 5426 1108 P 5433 1104 P 5439 1117 P 5445 1112 P 5451 1121 P 5458 1126 P 5464 1132 P 5470 1139 P 5477 1151 P 5483 1164 P 5489 1159 P 5496 1166 P 5502 1173 P 5508 1193 P 5514 1190 P 5521 1211 P 5527 1201 P 5533 1244 P 5540 1232 P 5546 1229 P 5552 1243 P 5558 1235 P 5565 1253 P 5571 1258 P 5577 1260 P 5584 1267 P 5590 1278 P 5596 1284 P 5603 1344 P 5609 1295 P 5615 1304 P 5621 1317 P 5628 1319 P 5634 1328 P 5640 1332 P 5647 1340 P 5653 1347 P 5659 1357 P 5666 1381 P 5672 1379 P 5678 1405 P 5684 1397 P 5691 1396 P 5697 1408 P 5703 1409 P 5710 1421 P 5716 1453 P 5722 1454 P 5728 1442 P 5735 1477 P 5741 1460 P 5747 1467 P 5754 1483 P 5760 1496 P 5766 1505 P 5773 1526 P 5779 1508 P 5785 1516 P 5791 1526 P 5798 1535 P 5804 1558 P 5810 1552 P 5817 1589 P 5823 1568 P 5829 1576 P 5836 1586 P 5842 1621 P 5848 1620 P 5854 1642 P 5861 1636 P 5867 1644 P 5873 1650 P 5880 1660 P 5886 1665 P 5892 1678 P 5899 1718 P 5905 1687 P 5911 1694 P 5917 1716 P 5924 1718 P 5930 1721 P 5936 1733 P 5943 1740 P 5949 1762 P 5955 1791 P 5961 1781 P 5968 1780 P 5974 1803 P 5980 1798 P 5987 1824 P 5993 1820 P 5999 1874 P 6006 1843 P 6012 1883 P 6018 1870 P 6024 1869 P 6031 1909 P 6037 1891 P 6043 1899 P 6050 1921 P 6056 1916 P 6062 1929 P 6069 1940 P 6075 1955 P 6081 1961 P 6087 1970 P 6094 1995 P 6100 2002 P 6106 2002 P 6113 2009 P 6119 2025 P 6125 2041 P 6131 2046 P 6138 2061 P 6144 2068 P 6150 2111 P 6157 2095 P 6163 2107 P 6169 2136 P 6176 2149 P 6182 2139 P 6188 2141 P 6194 2154 P 6201 2164 P 6207 2201 P 6213 2196 P 6220 2202 P 6226 2212 P 6232 2231 P 6239 2235 P 6245 2247 P 6251 2278 P 6257 2283 P 6264 2281 P 6270 2293 P 6276 2311 P 6283 2318 P 6289 2332 P 6295 2357 P 6302 2363 P 6308 2376 P 6314 2383 P 6320 2397 P 6327 2403 P 6333 2415 P 6339 2431 P 6346 2440 P 6352 2464 P 6358 2472 P 6364 2484 P 6371 2500 P 6377 2514 P 6383 2518 P 6390 2580 P 6396 2547 P 6402 2574 P 6409 2588 P 6415 2598 P 6421 2598 P 6427 2629 P 6434 2627 P 6440 2655 P 6446 2655 P 6453 2684 P 6459 2682 P 6465 2703 P 6472 2709 P 6478 2729 P 6484 2740 P 6490 2751 P 6497 2770 P 6503 2798 P 6509 2801 P 6516 2823 P 6522 2833 P 6528 2845 P 6535 2854 P 6541 2871 P 6547 2920 P 6553 2918 P 6560 2939 P 6566 2935 P 6572 2972 P 6579 2971 P 6585 2986 P 6591 2995 P 6597 3028 P 6604 3043 P 6610 3054 P 6616 3060 P 6623 3086 P 6629 3089 P 6635 3139 P 6642 3143 P 6648 3145 P 6654 3157 P 6660 3190 P 6667 3201 P 6673 3214 P 6679 3259 P 6686 3284 P 6692 3265 P 6698 3298 P 6705 3310 P 6711 3319 P 6717 3370 P 6723 3354 P 6730 3382 P 6736 3405 P 6742 3425 P 6749 3444 P 6755 3502 P 6761 3474 P 6767 3499 P 6774 3529 P 6780 3530 P 6786 3547 P 6793 3567 P 6799 3585 P 6805 3604 P 6812 3628 P 6818 3669 P 6824 3673 P 6830 3713 P 6837 3728 P 6843 3743 P 6849 3756 P 6856 3780 P 6862 3831 P 6868 3829 P 6875 3858 P 6881 3875 P 6887 3914 P 6893 3960 P 6900 3984 P 6906 3994 P 6912 4027 P 6919 4029 P 6925 4073 P 6931 4086 P 6938 4116 P 6944 4155 P 6950 4190 P 6956 4230 P 6963 4247 P stroke grestore end showpage %%Trailer \end{filecontents} \begin{filecontents}{newt4.eps} %% LaTeX2e file `newt4.eps' %% generated by the `filecontents' environment %% from source `graeffe' on 1997/06/14. %% %!PS-Adobe-2.0 EPSF-2.0 %%Creator: gnuplot %%DocumentFonts: Helvetica %%BoundingBox: 50 50 410 302 %%EndComments /gnudict 40 dict def gnudict begin /Color false def /Solid false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 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 /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 /PL { stroke gnulinewidth 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 /P { stroke [] 0 setdash currentlinewidth 2 div sub M 0 currentlinewidth V stroke } def /D { 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 P } def /A { stroke [] 0 setdash vpt sub M 0 vpt2 V currentpoint stroke M hpt neg vpt neg R hpt2 0 V stroke } def /B { 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 P } def /C { 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 /T { 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 P } def /S { 2 copy A C} def end %%EndProlog gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Helvetica findfont 140 scalefont setfont newpath LTa 672 4252 M 6297 0 V 672 211 M 0 4618 V LTb 672 211 M 63 0 V 6234 0 R -63 0 V 588 211 M (-350) Rshow 672 788 M 63 0 V 6234 0 R -63 0 V 588 788 M (-300) Rshow 672 1365 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-250) Rshow 672 1943 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-200) Rshow 672 2520 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-150) Rshow 672 3097 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-100) Rshow 672 3674 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-50) Rshow 672 4252 M 63 0 V 6234 0 R -63 0 V -6318 0 R (0) Rshow 672 4829 M 63 0 V 6234 0 R -63 0 V -6318 0 R (50) Rshow 672 211 M 0 63 V 0 4555 R 0 -63 V 672 71 M (0) Cshow 1302 211 M 0 63 V 0 4555 R 0 -63 V 1302 71 M (100) Cshow 1931 211 M 0 63 V 0 4555 R 0 -63 V 1931 71 M (200) Cshow 2561 211 M 0 63 V 0 4555 R 0 -63 V 2561 71 M (300) Cshow 3191 211 M 0 63 V 0 4555 R 0 -63 V 3191 71 M (400) Cshow 3820 211 M 0 63 V 0 4555 R 0 -63 V 3820 71 M (500) Cshow 4450 211 M 0 63 V 0 4555 R 0 -63 V 4450 71 M (600) Cshow 5080 211 M 0 63 V 0 4555 R 0 -63 V 5080 71 M (700) Cshow 5710 211 M 0 63 V 0 4555 R 0 -63 V 5710 71 M (800) Cshow 6339 211 M 0 63 V 0 4555 R 0 -63 V 6339 71 M (900) Cshow 6969 211 M 0 63 V 0 4555 R 0 -63 V 6969 71 M (1000) Cshow 672 211 M 6297 0 V 0 4618 V -6297 0 V 672 211 L 3820 4969 M (Generic polynomial of degree 1000, after iteration) Cshow LT0 6486 4626 M ("generic.1000.final") Rshow 6654 4626 P 672 4289 P 678 4244 P 685 4209 P 691 4175 P 697 4143 P 703 4113 P 710 4084 P 716 4055 P 722 4027 P 729 3999 P 735 3972 P 741 3946 P 748 3920 P 754 3895 P 760 3870 P 766 3846 P 773 3822 P 779 3798 P 785 3775 P 792 3752 P 798 3730 P 804 3708 P 811 3685 P 817 3663 P 823 3642 P 829 3620 P 836 3599 P 842 3578 P 848 3557 P 855 3536 P 861 3516 P 867 3496 P 874 3476 P 880 3456 P 886 3436 P 892 3417 P 899 3398 P 905 3379 P 911 3360 P 918 3341 P 924 3323 P 930 3305 P 936 3287 P 943 3269 P 949 3251 P 955 3234 P 962 3217 P 968 3200 P 974 3183 P 981 3166 P 987 3149 P 993 3133 P 999 3116 P 1006 3100 P 1012 3083 P 1018 3067 P 1025 3050 P 1031 3034 P 1037 3018 P 1044 3001 P 1050 2985 P 1056 2969 P 1062 2953 P 1069 2937 P 1075 2921 P 1081 2906 P 1088 2890 P 1094 2875 P 1100 2859 P 1106 2844 P 1113 2829 P 1119 2814 P 1125 2799 P 1132 2784 P 1138 2770 P 1144 2755 P 1151 2741 P 1157 2726 P 1163 2712 P 1169 2698 P 1176 2685 P 1182 2671 P 1188 2657 P 1195 2643 P 1201 2629 P 1207 2616 P 1214 2602 P 1220 2589 P 1226 2575 P 1232 2562 P 1239 2548 P 1245 2535 P 1251 2522 P 1258 2508 P 1264 2495 P 1270 2482 P 1277 2469 P 1283 2456 P 1289 2443 P 1295 2430 P 1302 2418 P 1308 2405 P 1314 2392 P 1321 2380 P 1327 2368 P 1333 2355 P 1339 2343 P 1346 2331 P 1352 2319 P 1358 2307 P 1365 2295 P 1371 2283 P 1377 2271 P 1384 2260 P 1390 2248 P 1396 2236 P 1402 2224 P 1409 2213 P 1415 2201 P 1421 2189 P 1428 2178 P 1434 2166 P 1440 2155 P 1447 2143 P 1453 2132 P 1459 2120 P 1465 2109 P 1472 2098 P 1478 2087 P 1484 2076 P 1491 2065 P 1497 2054 P 1503 2043 P 1510 2032 P 1516 2021 P 1522 2010 P 1528 2000 P 1535 1989 P 1541 1978 P 1547 1968 P 1554 1957 P 1560 1947 P 1566 1936 P 1572 1926 P 1579 1916 P 1585 1905 P 1591 1895 P 1598 1885 P 1604 1875 P 1610 1865 P 1617 1855 P 1623 1845 P 1629 1835 P 1635 1825 P 1642 1815 P 1648 1805 P 1654 1795 P 1661 1786 P 1667 1776 P 1673 1767 P 1680 1757 P 1686 1748 P 1692 1738 P 1698 1729 P 1705 1720 P 1711 1710 P 1717 1701 P 1724 1692 P 1730 1682 P 1736 1673 P 1742 1664 P 1749 1655 P 1755 1645 P 1761 1636 P 1768 1627 P 1774 1618 P 1780 1610 P 1787 1601 P 1793 1592 P 1799 1583 P 1805 1574 P 1812 1566 P 1818 1557 P 1824 1548 P 1831 1540 P 1837 1531 P 1843 1523 P 1850 1514 P 1856 1506 P 1862 1497 P 1868 1489 P 1875 1481 P 1881 1472 P 1887 1464 P 1894 1456 P 1900 1448 P 1906 1440 P 1913 1432 P 1919 1424 P 1925 1416 P 1931 1408 P 1938 1400 P 1944 1392 P 1950 1384 P 1957 1376 P 1963 1369 P 1969 1361 P 1975 1353 P 1982 1345 P 1988 1337 P 1994 1330 P 2001 1322 P 2007 1314 P 2013 1307 P 2020 1299 P 2026 1292 P 2032 1284 P 2038 1277 P 2045 1270 P 2051 1262 P 2057 1255 P 2064 1247 P 2070 1240 P 2076 1233 P 2083 1226 P 2089 1218 P 2095 1211 P 2101 1204 P 2108 1197 P 2114 1190 P 2120 1183 P 2127 1176 P 2133 1169 P 2139 1162 P 2145 1155 P 2152 1148 P 2158 1142 P 2164 1135 P 2171 1128 P 2177 1121 P 2183 1115 P 2190 1108 P 2196 1101 P 2202 1095 P 2208 1088 P 2215 1081 P 2221 1075 P 2227 1068 P 2234 1062 P 2240 1055 P 2246 1049 P 2253 1043 P 2259 1037 P 2265 1030 P 2271 1024 P 2278 1018 P 2284 1012 P 2290 1006 P 2297 1000 P 2303 994 P 2309 988 P 2316 982 P 2322 976 P 2328 970 P 2334 964 P 2341 958 P 2347 952 P 2353 947 P 2360 941 P 2366 935 P 2372 929 P 2378 923 P 2385 918 P 2391 912 P 2397 906 P 2404 901 P 2410 895 P 2416 890 P 2423 884 P 2429 879 P 2435 873 P 2441 868 P 2448 863 P 2454 857 P 2460 852 P 2467 846 P 2473 841 P 2479 836 P 2486 831 P 2492 826 P 2498 820 P 2504 815 P 2511 810 P 2517 805 P 2523 800 P 2530 795 P 2536 790 P 2542 785 P 2549 780 P 2555 775 P 2561 770 P 2567 765 P 2574 760 P 2580 756 P 2586 751 P 2593 746 P 2599 741 P 2605 736 P 2611 732 P 2618 727 P 2624 722 P 2630 718 P 2637 713 P 2643 709 P 2649 704 P 2656 699 P 2662 695 P 2668 690 P 2674 686 P 2681 681 P 2687 677 P 2693 672 P 2700 668 P 2706 664 P 2712 659 P 2719 655 P 2725 650 P 2731 646 P 2737 642 P 2744 637 P 2750 633 P 2756 629 P 2763 625 P 2769 621 P 2775 617 P 2781 613 P 2788 609 P 2794 605 P 2800 601 P 2807 598 P 2813 594 P 2819 590 P 2826 586 P 2832 582 P 2838 579 P 2844 575 P 2851 571 P 2857 568 P 2863 564 P 2870 561 P 2876 557 P 2882 554 P 2889 550 P 2895 547 P 2901 544 P 2907 540 P 2914 537 P 2920 533 P 2926 530 P 2933 527 P 2939 524 P 2945 521 P 2952 517 P 2958 514 P 2964 511 P 2970 508 P 2977 505 P 2983 502 P 2989 499 P 2996 495 P 3002 492 P 3008 489 P 3014 486 P 3021 483 P 3027 480 P 3033 477 P 3040 474 P 3046 471 P 3052 469 P 3059 466 P 3065 463 P 3071 460 P 3077 457 P 3084 454 P 3090 451 P 3096 449 P 3103 446 P 3109 443 P 3115 441 P 3122 438 P 3128 435 P 3134 433 P 3140 430 P 3147 428 P 3153 425 P 3159 423 P 3166 420 P 3172 418 P 3178 415 P 3185 413 P 3191 411 P 3197 408 P 3203 406 P 3210 404 P 3216 402 P 3222 399 P 3229 397 P 3235 395 P 3241 393 P 3247 391 P 3254 388 P 3260 386 P 3266 384 P 3273 382 P 3279 380 P 3285 378 P 3292 376 P 3298 374 P 3304 373 P 3310 371 P 3317 369 P 3323 367 P 3329 365 P 3336 363 P 3342 362 P 3348 360 P 3355 358 P 3361 356 P 3367 355 P 3373 353 P 3380 351 P 3386 350 P 3392 348 P 3399 347 P 3405 345 P 3411 343 P 3417 342 P 3424 340 P 3430 339 P 3436 337 P 3443 336 P 3449 334 P 3455 333 P 3462 332 P 3468 330 P 3474 329 P 3480 327 P 3487 326 P 3493 325 P 3499 324 P 3506 322 P 3512 321 P 3518 320 P 3525 319 P 3531 318 P 3537 317 P 3543 316 P 3550 315 P 3556 314 P 3562 313 P 3569 312 P 3575 311 P 3581 310 P 3588 309 P 3594 308 P 3600 307 P 3606 306 P 3613 305 P 3619 305 P 3625 304 P 3632 303 P 3638 302 P 3644 302 P 3650 301 P 3657 300 P 3663 300 P 3669 299 P 3676 299 P 3682 298 P 3688 298 P 3695 297 P 3701 297 P 3707 296 P 3713 296 P 3720 296 P 3726 295 P 3732 295 P 3739 295 P 3745 294 P 3751 294 P 3758 294 P 3764 294 P 3770 293 P 3776 293 P 3783 293 P 3789 293 P 3795 293 P 3802 293 P 3808 293 P 3814 293 P 3820 292 P 3827 292 P 3833 293 P 3839 293 P 3846 293 P 3852 293 P 3858 293 P 3865 294 P 3871 294 P 3877 294 P 3883 295 P 3890 295 P 3896 295 P 3902 296 P 3909 296 P 3915 297 P 3921 297 P 3928 298 P 3934 298 P 3940 299 P 3946 299 P 3953 300 P 3959 300 P 3965 301 P 3972 302 P 3978 302 P 3984 303 P 3991 304 P 3997 304 P 4003 305 P 4009 306 P 4016 307 P 4022 307 P 4028 308 P 4035 309 P 4041 310 P 4047 310 P 4053 311 P 4060 312 P 4066 313 P 4072 314 P 4079 314 P 4085 315 P 4091 316 P 4098 317 P 4104 318 P 4110 319 P 4116 320 P 4123 321 P 4129 322 P 4135 323 P 4142 324 P 4148 326 P 4154 327 P 4161 328 P 4167 329 P 4173 330 P 4179 332 P 4186 333 P 4192 334 P 4198 336 P 4205 337 P 4211 339 P 4217 340 P 4224 342 P 4230 343 P 4236 345 P 4242 346 P 4249 348 P 4255 349 P 4261 351 P 4268 352 P 4274 354 P 4280 356 P 4286 357 P 4293 359 P 4299 361 P 4305 362 P 4312 364 P 4318 366 P 4324 368 P 4331 370 P 4337 371 P 4343 373 P 4349 375 P 4356 377 P 4362 379 P 4368 381 P 4375 383 P 4381 385 P 4387 387 P 4394 389 P 4400 392 P 4406 394 P 4412 396 P 4419 398 P 4425 400 P 4431 403 P 4438 405 P 4444 407 P 4450 409 P 4456 412 P 4463 414 P 4469 417 P 4475 419 P 4482 422 P 4488 424 P 4494 427 P 4501 429 P 4507 432 P 4513 435 P 4519 437 P 4526 440 P 4532 443 P 4538 445 P 4545 448 P 4551 451 P 4557 454 P 4564 456 P 4570 459 P 4576 462 P 4582 465 P 4589 468 P 4595 471 P 4601 474 P 4608 477 P 4614 480 P 4620 483 P 4627 486 P 4633 488 P 4639 491 P 4645 494 P 4652 497 P 4658 501 P 4664 504 P 4671 507 P 4677 510 P 4683 513 P 4689 516 P 4696 519 P 4702 522 P 4708 526 P 4715 529 P 4721 532 P 4727 536 P 4734 539 P 4740 543 P 4746 546 P 4752 550 P 4759 553 P 4765 557 P 4771 560 P 4778 564 P 4784 568 P 4790 571 P 4797 575 P 4803 578 P 4809 582 P 4815 586 P 4822 590 P 4828 593 P 4834 597 P 4841 601 P 4847 605 P 4853 609 P 4860 613 P 4866 617 P 4872 621 P 4878 625 P 4885 630 P 4891 634 P 4897 638 P 4904 642 P 4910 646 P 4916 651 P 4922 655 P 4929 659 P 4935 664 P 4941 668 P 4948 672 P 4954 677 P 4960 681 P 4967 686 P 4973 690 P 4979 695 P 4985 699 P 4992 704 P 4998 708 P 5004 713 P 5011 718 P 5017 722 P 5023 727 P 5030 732 P 5036 736 P 5042 741 P 5048 746 P 5055 750 P 5061 755 P 5067 760 P 5074 765 P 5080 770 P 5086 774 P 5092 779 P 5099 784 P 5105 789 P 5111 794 P 5118 799 P 5124 804 P 5130 809 P 5137 814 P 5143 819 P 5149 824 P 5155 829 P 5162 835 P 5168 840 P 5174 845 P 5181 851 P 5187 856 P 5193 861 P 5200 867 P 5206 872 P 5212 878 P 5218 883 P 5225 889 P 5231 894 P 5237 900 P 5244 906 P 5250 912 P 5256 917 P 5263 923 P 5269 929 P 5275 935 P 5281 940 P 5288 946 P 5294 952 P 5300 958 P 5307 964 P 5313 970 P 5319 976 P 5325 982 P 5332 988 P 5338 994 P 5344 1000 P 5351 1006 P 5357 1012 P 5363 1018 P 5370 1024 P 5376 1030 P 5382 1036 P 5388 1042 P 5395 1049 P 5401 1055 P 5407 1061 P 5414 1067 P 5420 1074 P 5426 1080 P 5433 1086 P 5439 1093 P 5445 1099 P 5451 1106 P 5458 1112 P 5464 1119 P 5470 1125 P 5477 1132 P 5483 1139 P 5489 1145 P 5496 1152 P 5502 1159 P 5508 1166 P 5514 1173 P 5521 1180 P 5527 1187 P 5533 1194 P 5540 1201 P 5546 1209 P 5552 1216 P 5558 1223 P 5565 1230 P 5571 1237 P 5577 1245 P 5584 1252 P 5590 1260 P 5596 1267 P 5603 1274 P 5609 1282 P 5615 1289 P 5621 1297 P 5628 1304 P 5634 1312 P 5640 1320 P 5647 1327 P 5653 1335 P 5659 1343 P 5666 1351 P 5672 1358 P 5678 1366 P 5684 1374 P 5691 1382 P 5697 1390 P 5703 1397 P 5710 1405 P 5716 1413 P 5722 1421 P 5728 1429 P 5735 1437 P 5741 1446 P 5747 1454 P 5754 1462 P 5760 1470 P 5766 1478 P 5773 1487 P 5779 1495 P 5785 1504 P 5791 1513 P 5798 1521 P 5804 1530 P 5810 1539 P 5817 1548 P 5823 1557 P 5829 1565 P 5836 1574 P 5842 1583 P 5848 1592 P 5854 1601 P 5861 1610 P 5867 1619 P 5873 1628 P 5880 1637 P 5886 1646 P 5892 1655 P 5899 1664 P 5905 1674 P 5911 1683 P 5917 1692 P 5924 1702 P 5930 1711 P 5936 1720 P 5943 1730 P 5949 1739 P 5955 1749 P 5961 1758 P 5968 1768 P 5974 1777 P 5980 1787 P 5987 1796 P 5993 1806 P 5999 1816 P 6006 1825 P 6012 1835 P 6018 1845 P 6024 1855 P 6031 1865 P 6037 1875 P 6043 1885 P 6050 1895 P 6056 1905 P 6062 1915 P 6069 1926 P 6075 1936 P 6081 1946 P 6087 1957 P 6094 1967 P 6100 1978 P 6106 1988 P 6113 1999 P 6119 2010 P 6125 2021 P 6131 2031 P 6138 2042 P 6144 2053 P 6150 2064 P 6157 2075 P 6163 2086 P 6169 2097 P 6176 2108 P 6182 2120 P 6188 2131 P 6194 2142 P 6201 2154 P 6207 2165 P 6213 2176 P 6220 2188 P 6226 2199 P 6232 2211 P 6239 2223 P 6245 2234 P 6251 2246 P 6257 2258 P 6264 2270 P 6270 2282 P 6276 2293 P 6283 2305 P 6289 2317 P 6295 2329 P 6302 2342 P 6308 2354 P 6314 2367 P 6320 2379 P 6327 2392 P 6333 2404 P 6339 2417 P 6346 2429 P 6352 2442 P 6358 2455 P 6364 2468 P 6371 2481 P 6377 2495 P 6383 2508 P 6390 2521 P 6396 2535 P 6402 2548 P 6409 2562 P 6415 2575 P 6421 2589 P 6427 2602 P 6434 2616 P 6440 2630 P 6446 2643 P 6453 2657 P 6459 2671 P 6465 2686 P 6472 2700 P 6478 2714 P 6484 2728 P 6490 2743 P 6497 2757 P 6503 2772 P 6509 2787 P 6516 2801 P 6522 2816 P 6528 2831 P 6535 2846 P 6541 2861 P 6547 2877 P 6553 2892 P 6560 2907 P 6566 2923 P 6572 2938 P 6579 2954 P 6585 2970 P 6591 2986 P 6597 3002 P 6604 3018 P 6610 3034 P 6616 3050 P 6623 3067 P 6629 3083 P 6635 3100 P 6642 3117 P 6648 3134 P 6654 3151 P 6660 3169 P 6667 3186 P 6673 3203 P 6679 3221 P 6686 3239 P 6692 3256 P 6698 3274 P 6705 3292 P 6711 3310 P 6717 3329 P 6723 3347 P 6730 3365 P 6736 3384 P 6742 3403 P 6749 3422 P 6755 3441 P 6761 3460 P 6767 3479 P 6774 3498 P 6780 3518 P 6786 3537 P 6793 3557 P 6799 3576 P 6805 3597 P 6812 3618 P 6818 3639 P 6824 3661 P 6830 3683 P 6837 3705 P 6843 3728 P 6849 3751 P 6856 3774 P 6862 3798 P 6868 3822 P 6875 3847 P 6881 3872 P 6887 3897 P 6893 3922 P 6900 3947 P 6906 3973 P 6912 3999 P 6919 4026 P 6925 4054 P 6931 4082 P 6938 4113 P 6944 4143 P 6950 4177 P 6956 4212 P 6963 4248 P stroke grestore end showpage %%Trailer \end{filecontents} \begin{filecontents}{newt5.eps} %% LaTeX2e file `newt5.eps' %% generated by the `filecontents' environment %% from source `graeffe' on 1997/06/14. %% %!PS-Adobe-2.0 EPSF-2.0 %%Creator: gnuplot %%DocumentFonts: Helvetica %%BoundingBox: 50 50 410 302 %%EndComments /gnudict 40 dict def gnudict begin /Color false def /Solid false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 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 /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 /PL { stroke gnulinewidth 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 /P { stroke [] 0 setdash currentlinewidth 2 div sub M 20 currentlinewidth V stroke } def /D { 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 P } def /A { stroke [] 0 setdash vpt sub M 0 vpt2 V currentpoint stroke M hpt neg vpt neg R hpt2 0 V stroke } def /B { 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 P } def /C { 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 /T { 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 P } def /S { 2 copy A C} def end %%EndProlog gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Helvetica findfont 140 scalefont setfont newpath LTa 672 2777 M 6297 0 V 4870 211 M 0 4618 V LTb 672 211 M 63 0 V 6234 0 R -63 0 V 588 211 M (-25) Rshow 672 724 M 63 0 V 6234 0 R -63 0 V 588 724 M (-20) Rshow 672 1237 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-15) Rshow 672 1750 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-10) Rshow 672 2263 M 63 0 V 6234 0 R -63 0 V -6318 0 R (-5) Rshow 672 2777 M 63 0 V 6234 0 R -63 0 V -6318 0 R (0) Rshow 672 3290 M 63 0 V 6234 0 R -63 0 V -6318 0 R (5) Rshow 672 3803 M 63 0 V 6234 0 R -63 0 V -6318 0 R (10) Rshow 672 4316 M 63 0 V 6234 0 R -63 0 V -6318 0 R (15) Rshow 672 4829 M 63 0 V 6234 0 R -63 0 V -6318 0 R (20) Rshow 672 211 M 0 63 V 0 4555 R 0 -63 V 672 71 M (-30) Cshow 1372 211 M 0 63 V 0 4555 R 0 -63 V 1372 71 M (-25) Cshow 2071 211 M 0 63 V 0 4555 R 0 -63 V 2071 71 M (-20) Cshow 2771 211 M 0 63 V 0 4555 R 0 -63 V 2771 71 M (-15) Cshow 3471 211 M 0 63 V 0 4555 R 0 -63 V 3471 71 M (-10) Cshow 4170 211 M 0 63 V 0 4555 R 0 -63 V 4170 71 M (-5) Cshow 4870 211 M 0 63 V 0 4555 R 0 -63 V 4870 71 M (0) Cshow 5570 211 M 0 63 V 0 4555 R 0 -63 V 5570 71 M (5) Cshow 6269 211 M 0 63 V 0 4555 R 0 -63 V 6269 71 M (10) Cshow 6969 211 M 0 63 V 0 4555 R 0 -63 V 6969 71 M (15) Cshow 672 211 M 6297 0 V 0 4618 V -6297 0 V 672 211 L 3820 4969 M (Zeros of a generic polynomial of degree 1000) Cshow LT0 6486 4626 M ("generic.1000.zeros") Rshow 6654 4626 P 4867 2776 P 4877 2776 P 4863 2775 P 4873 2783 P 4864 2783 P 4880 2773 P 4867 2768 P 4878 2770 P 4880 2781 P 4870 2787 P 4861 2768 P 4855 2778 P 4859 2785 P 4878 2787 P 4876 2765 P 4887 2775 P 4853 2771 P 4888 2780 P 4887 2783 P 4868 2791 P 4862 2790 P 4852 2784 P 4863 2762 P 4869 2761 P 4887 2767 P 4859 2763 P 4849 2782 P 4881 2762 P 4850 2767 P 4852 2765 P 4876 2794 P 4846 2773 P 4895 2775 P 4893 2769 P 4850 2789 P 4858 2794 P 4884 2794 P 4891 2790 P 4842 2779 P 4885 2759 P 4882 2757 P 4870 2755 P 4868 2798 P 4841 2771 P 4854 2757 P 4892 2793 P 4846 2761 P 4873 2753 P 4902 2775 P 4847 2794 P 4902 2770 P 4898 2763 P 4903 2781 P 4860 2800 P 4887 2798 P 4902 2785 P 4861 2753 P 4898 2791 P 4841 2790 P 4895 2759 P 4872 2802 P 4836 2783 P 4835 2775 P 4834 2777 P 4882 2801 P 4840 2762 P 4880 2751 P 4849 2799 P 4892 2755 P 4855 2751 P 4834 2786 P 4834 2767 P 4869 2805 P 4907 2786 P 4844 2754 P 4909 2768 P 4894 2801 P 4911 2782 P 4848 2751 P 4911 2771 P 4861 2807 P 4853 2805 P 4906 2760 P 4881 2807 P 4908 2791 P 4878 2746 P 4893 2750 P 4857 2746 P 4834 2795 P 4845 2803 P 4830 2763 P 4863 2745 P 4902 2754 P 4837 2799 P 4870 2810 P 4915 2776 P 4825 2783 P 4870 2743 P 4906 2798 P 4901 2802 P 4913 2764 P 4889 2745 P 4827 2791 P 4825 2763 P 4822 2773 P 4918 2781 P 4884 2742 P 4860 2812 P 4844 2745 P 4918 2786 P 4821 2770 P 4832 2753 P 4911 2797 P 4899 2746 P 4838 2805 P 4863 2740 P 4873 2739 P 4869 2814 P 4892 2810 P 4819 2777 P 4822 2789 P 4828 2755 P 4912 2755 P 4837 2747 P 4884 2813 P 4828 2799 P 4845 2811 P 4890 2813 P 4924 2773 P 4904 2807 P 4855 2738 P 4861 2816 P 4818 2765 P 4917 2756 P 4923 2765 P 4913 2751 P 4898 2812 P 4903 2744 P 4877 2736 P 4926 2781 P 4845 2739 P 4815 2787 P 4813 2772 P 4922 2795 P 4813 2779 P 4822 2754 P 4900 2740 P 4884 2818 P 4822 2801 P 4829 2807 P 4875 2820 P 4842 2815 P 4853 2818 P 4833 2743 P 4827 2746 P 4905 2813 P 4815 2758 P 4919 2803 P 4889 2734 P 4846 2735 P 4832 2812 P 4868 2822 P 4929 2764 P 4928 2794 P 4886 2732 P 4931 2787 P 4933 2776 P 4920 2749 P 4923 2801 P 4810 2789 P 4871 2730 P 4913 2743 P 4813 2798 P 4908 2814 P 4855 2823 P 4898 2819 P 4883 2823 P 4815 2751 P 4857 2730 P 4935 2770 P 4898 2733 P 4817 2806 P 4827 2740 P 4932 2760 P 4804 2767 P 4862 2728 P 4803 2783 P 4920 2810 P 4913 2814 P 4929 2800 P 4842 2822 P 4932 2756 P 4843 2730 P 4847 2824 P 4835 2732 P 4879 2726 P 4808 2752 P 4893 2728 P 4833 2820 P 4804 2758 P 4805 2796 P 4928 2747 P 4879 2828 P 4940 2783 P 4937 2793 P 4801 2766 P 4918 2738 P 4799 2776 P 4801 2789 P 4814 2810 P 4911 2733 P 4798 2782 P 4943 2775 P 4817 2740 P 4902 2825 P 4931 2806 P 4916 2819 P 4821 2817 P 4940 2760 P 4874 2722 P 4862 2831 P 4853 2724 P 4872 2831 P 4860 2722 P 4858 2831 P 4795 2772 P 4936 2750 P 4807 2808 P 4824 2821 P 4833 2825 P 4944 2790 P 4942 2757 P 4828 2729 P 4931 2742 P 4899 2829 P 4948 2778 P 4813 2815 P 4811 2739 P 4801 2803 P 4908 2726 P 4923 2734 P 4842 2722 P 4935 2810 P 4944 2796 P 4804 2745 P 4898 2722 P 4890 2833 P 4950 2781 P 4861 2718 P 4854 2835 P 4845 2833 P 4887 2718 P 4791 2791 P 4944 2802 P 4794 2754 P 4928 2820 P 4788 2766 P 4834 2722 P 4951 2764 P 4809 2735 P 4817 2729 P 4907 2721 P 4891 2836 P 4875 2715 P 4934 2737 P 4824 2829 P 4793 2802 P 4791 2754 P 4920 2826 P 4916 2724 P 4910 2831 P 4896 2836 P 4889 2715 P 4810 2731 P 4811 2823 P 4944 2743 P 4879 2840 P 4789 2799 P 4954 2760 P 4859 2713 P 4828 2720 P 4867 2841 P 4783 2786 P 4782 2774 P 4837 2837 P 4930 2729 P 4956 2793 P 4944 2813 P 4922 2830 P 4959 2771 P 4789 2805 P 4952 2749 P 4795 2740 P 4954 2800 P 4796 2814 P 4902 2714 P 4854 2842 P 4960 2765 P 4779 2782 P 4961 2780 P 4848 2711 P 4814 2723 P 4780 2764 P 4790 2743 P 4938 2822 P 4798 2819 P 4919 2719 P 4878 2709 P 4784 2749 P 4892 2843 P 4928 2722 P 4779 2793 P 4841 2842 P 4864 2708 P 4776 2770 P 4948 2738 P 4826 2838 P 4819 2835 P 4963 2789 P 4965 2771 P 4940 2730 P 4835 2712 P 4807 2830 P 4870 2847 P 4779 2756 P 4821 2716 P 4802 2727 P 4915 2839 P 4939 2826 P 4887 2707 P 4964 2759 P 4794 2822 P 4836 2709 P 4934 2832 P 4957 2812 P 4954 2736 P 4850 2705 P 4951 2820 P 4905 2845 P 4853 2849 P 4917 2711 P 4899 2706 P 4971 2781 P 4883 2850 P 4768 2779 P 4775 2805 P 4770 2796 P 4780 2813 P 4772 2753 P 4941 2721 P 4873 2852 P 4875 2701 P 4963 2742 P 4788 2729 P 4767 2788 P 4836 2849 P 4961 2814 P 4931 2839 P 4973 2795 P 4800 2835 P 4803 2717 P 4782 2820 P 4779 2737 P 4793 2723 P 4971 2802 P 4773 2809 P 4763 2771 P 4815 2709 P 4863 2698 P 4773 2743 P 4974 2756 P 4939 2838 P 4952 2725 P 4817 2846 P 4921 2706 P 4922 2846 P 4764 2760 P 4850 2698 P 4856 2856 P 4935 2712 P 4952 2829 P 4970 2744 P 4957 2826 P 4977 2794 P 4890 2697 P 4980 2772 P 4905 2853 P 4808 2844 P 4887 2857 P 4824 2851 P 4897 2697 P 4981 2763 P 4818 2704 P 4757 2781 P 4787 2833 P 4950 2835 P 4830 2699 P 4763 2806 P 4896 2858 P 4978 2803 P 4761 2752 P 4971 2737 P 4977 2745 P 4777 2726 P 4985 2773 P 4846 2859 P 4789 2716 P 4925 2851 P 4922 2853 P 4973 2816 P 4875 2691 P 4828 2857 P 4882 2862 P 4920 2698 P 4861 2863 P 4754 2759 P 4792 2842 P 4840 2692 P 4915 2696 P 4887 2690 P 4759 2744 P 4948 2710 P 4941 2847 P 4766 2733 P 4750 2775 P 4807 2702 P 4805 2851 P 4972 2729 P 4907 2692 P 4988 2755 P 4752 2798 P 4992 2780 P 4793 2707 P 4968 2723 P 4990 2793 P 4915 2860 P 4750 2794 P 4933 2699 P 4864 2686 P 4985 2808 P 4777 2836 P 4979 2818 P 4973 2827 P 4854 2686 P 4758 2815 P 4960 2714 P 4821 2692 P 4757 2737 P 4764 2826 P 4946 2703 P 4833 2865 P 4907 2866 P 4847 2868 P 4997 2786 P 4848 2685 P 4785 2707 P 4997 2783 P 4793 2851 P 4767 2833 P 4775 2713 P 4965 2712 P 4819 2864 P 4747 2806 P 4765 2721 P 4741 2767 P 4997 2756 P 4741 2764 P 4829 2686 P 4867 2872 P 4960 2846 P 4990 2738 P 4884 2873 P 4799 2859 P 4994 2743 P 4991 2816 P 4948 2697 P 4736 2782 P 4757 2831 P 4739 2755 P 4798 2693 P 4938 2691 P 4899 2680 P 4736 2790 P 4810 2866 P 4745 2738 P 4933 2865 P 4903 2873 P 4974 2841 P 4889 2678 P 4868 2676 P 4778 2851 P 4986 2830 P 4749 2824 P 4869 2877 P 4955 2857 P 4849 2877 P 4765 2843 P 4980 2714 P 4922 2682 P 5008 2764 P 5009 2769 P 4923 2873 P 4967 2853 P 4807 2683 P 5006 2808 P 4752 2718 P 4786 2692 P 4891 2880 P 4744 2725 P 4946 2866 P 4774 2697 P 4995 2723 P 4988 2714 P 4730 2803 P 4759 2707 P 5010 2807 P 5012 2752 P 4730 2746 P 5004 2734 P 4733 2816 P 4724 2759 P 5005 2821 P 4918 2879 P 4974 2854 P 4893 2669 P 4992 2838 P 4821 2674 P 4876 2668 P 4974 2698 P 4722 2789 P 4721 2773 P 4848 2668 P 4786 2867 P 5019 2782 P 4806 2677 P 4865 2886 P 4834 2883 P 4845 2885 P 5018 2794 P 4967 2693 P 4837 2669 P 4818 2880 P 4873 2887 P 4902 2667 P 4933 2675 P 4914 2669 P 4798 2876 P 4947 2680 P 4952 2871 P 4753 2849 P 5006 2723 P 5018 2744 P 5025 2771 P 4730 2728 P 4846 2664 P 4929 2670 P 4899 2890 P 4767 2864 P 4963 2683 P 4816 2668 P 4738 2841 P 4727 2826 P 4788 2677 P 4815 2886 P 4998 2845 P 4711 2781 P 4723 2823 P 5028 2759 P 4765 2866 P 4791 2879 P 4916 2890 P 5020 2820 P 4861 2659 P 4714 2807 P 4756 2693 P 4978 2865 P 4981 2689 P 4989 2858 P 4753 2860 P 4759 2688 P 4766 2684 P 4707 2762 P 4737 2706 P 5020 2726 P 5003 2704 P 4709 2746 P 5029 2813 P 5035 2798 P 4713 2735 P 4944 2887 P 4898 2898 P 4701 2781 P 5038 2789 P 4854 2900 P 4719 2719 P 4888 2653 P 4961 2882 P 4701 2791 P 4723 2841 P 5021 2836 P 5042 2782 P 5037 2745 P 4698 2761 P 5019 2842 P 4727 2704 P 4870 2904 P 4868 2649 P 4926 2655 P 4995 2687 P 4829 2902 P 4701 2812 P 4794 2893 P 4786 2663 P 4988 2874 P 5035 2824 P 4937 2898 P 5018 2703 P 4819 2651 P 4974 2670 P 4782 2891 P 4844 2646 P 4956 2661 P 4907 2647 P 4943 2656 P 4718 2706 P 5043 2738 P 4771 2666 P 5048 2754 P 4725 2856 P 4736 2687 P 4699 2821 P 4789 2657 P 4764 2885 P 4916 2906 P 4969 2889 P 4884 2910 P 5035 2718 P 4703 2833 P 4986 2672 P 4698 2728 P 4848 2641 P 4803 2905 P 5021 2857 P 5018 2692 P 4731 2869 P 4707 2846 P 4886 2638 P 4821 2642 P 4689 2735 P 4835 2914 P 4859 2916 P 4711 2854 P 4755 2664 P 5057 2805 P 5061 2767 P 4741 2881 P 4679 2760 P 4678 2796 P 4676 2774 P 4904 2917 P 4768 2898 P 4995 2888 P 4957 2907 P 4785 2645 P 5049 2714 P 5068 2787 P 4721 2680 P 5050 2840 P 4961 2646 P 5055 2833 P 5010 2883 P 5028 2869 P 5073 2775 P 4694 2702 P 5000 2662 P 4973 2906 P 5010 2668 P 5038 2861 P 4861 2926 P 4666 2781 P 4835 2924 P 5073 2757 P 4930 2632 P 5070 2739 P 4811 2631 P 5066 2827 P 4670 2819 P 4677 2718 P 4898 2624 P 4736 2658 P 4727 2889 P 5064 2718 P 5046 2693 P 4834 2624 P 4990 2650 P 4910 2929 P 5005 2896 P 4695 2689 P 5080 2796 P 4662 2744 P 4917 2625 P 4792 2923 P 4876 2620 P 4702 2874 P 4657 2761 P 4928 2928 P 5035 2675 P 5066 2710 P 4954 2630 P 5082 2745 P 4820 2931 P 4673 2706 P 4710 2665 P 4656 2820 P 4652 2812 P 4761 2634 P 4949 2930 P 4988 2915 P 4730 2904 P 4875 2940 P 4676 2858 P 5071 2852 P 4761 2923 P 5042 2885 P 4966 2929 P 4743 2637 P 4793 2935 P 4716 2651 P 4791 2618 P 4867 2607 P 4905 2609 P 5042 2663 P 4701 2892 P 4640 2796 P 5095 2819 P 4737 2918 P 5104 2774 P 5075 2692 P 5104 2793 P 4655 2847 P 4636 2754 P 4645 2724 P 4961 2617 P 4994 2629 P 4846 2603 P 4667 2686 P 5063 2878 P 4818 2606 P 4833 2949 P 4933 2945 P 5025 2912 P 4637 2732 P 4885 2953 P 5015 2635 P 5100 2720 P 4759 2618 P 4776 2941 P 5061 2666 P 4626 2786 P 4646 2851 P 5103 2835 P 4794 2950 P 4620 2768 P 4660 2676 P 4685 2652 P 4713 2922 P 4901 2591 P 5122 2745 P 4662 2886 P 4645 2868 P 5096 2686 P 4696 2637 P 4807 2592 P 5055 2909 P 4873 2968 P 5005 2941 P 4979 2602 P 4747 2607 P 5133 2794 P 4977 2954 P 4667 2903 P 4953 2591 P 5102 2873 P 5118 2849 P 4923 2968 P 5055 2633 P 4615 2840 P 5139 2759 P 4616 2707 P 5030 2938 P 5091 2895 P 4731 2950 P 4868 2575 P 4780 2586 P 5047 2622 P 4855 2978 P 5133 2835 P 4679 2923 P 4595 2796 P 4595 2751 P 4927 2576 P 4657 2643 P 5144 2731 P 4833 2572 P 4604 2708 P 4600 2838 P 5124 2682 P 5140 2709 P 4720 2596 P 5152 2823 P 5011 2588 P 4884 2560 P 5092 2921 P 5167 2756 P 4606 2674 P 4785 2987 P 5144 2865 P 5059 2947 P 4812 2993 P 4881 2998 P 4695 2596 P 4752 2981 P 4985 2982 P 5111 2640 P 4975 2567 P 5075 2611 P 4947 2995 P 4628 2638 P 4590 2872 P 4913 3002 P 5066 2599 P 4563 2735 P 5118 2916 P 5183 2794 P 4769 2558 P 4555 2801 P 4848 3008 P 4591 2665 P 4561 2833 P 4592 2890 P 4723 2984 P 5026 2572 P 5171 2694 P 5138 2646 P 4647 2948 P 5022 2986 P 4608 2916 P 4683 2973 P 4939 2542 P 4543 2766 P 5194 2822 P 4639 2603 P 5201 2746 P 4783 2537 P 5098 2961 P 5173 2892 P 4531 2811 P 5169 2654 P 4604 2618 P 4866 2523 P 4610 2946 P 4770 3022 P 4737 2539 P 4904 2519 P 4965 3026 P 4543 2878 P 4681 2556 P 5002 2533 P 4813 2515 P 4653 2990 P 5169 2927 P 4733 3025 P 4513 2717 P 4891 3046 P 4536 2893 P 5234 2721 P 5039 3019 P 5106 2565 P 4512 2694 P 4567 2615 P 5226 2863 P 4523 2656 P 5253 2794 P 4983 3047 P 5082 3013 P 4845 3059 P 4483 2763 P 5249 2846 P 5151 2577 P 5179 2954 P 4723 2509 P 5193 2607 P 5136 2993 P 5252 2675 P 4672 2514 P 4708 3053 P 4461 2809 P 4607 2541 P 5002 2487 P 5055 2501 P 4958 2476 P 4546 2971 P 5293 2806 P 4764 3084 P 5024 3079 P 4447 2677 P 4493 2602 P 4450 2886 P 4871 2449 P 4884 3105 P 5298 2678 P 5220 2567 P 4552 3013 P 4780 2450 P 4623 3058 P 5289 2917 P 4461 2935 P 5332 2718 P 5326 2863 P 5137 2491 P 5297 2620 P 5149 3061 P 4382 2814 P 5204 2513 P 4384 2706 P 4719 2430 P 5253 3010 P 4502 2529 P 4452 2567 P 4365 2740 P 4619 3104 P 5391 2750 P 4803 2396 P 4926 2390 P 5070 2413 P 4894 3169 P 4389 2594 P 4938 3172 P 4574 2440 P 4705 3162 P 5361 2970 P 4350 2943 P 4650 2388 P 5063 3174 P 4375 2998 P 5373 2563 P 5193 3149 P 4406 3069 P 5472 2883 P 4258 2845 P 5317 2460 P 5067 2340 P 5376 3058 P 4440 3128 P 5493 2648 P 5522 2763 P 4789 2297 P 5355 3107 P 5517 2912 P 4758 3267 P 4229 2610 P 4505 3204 P 4413 2394 P 5246 3226 P 4253 2498 P 4549 2299 P 5520 2537 P 4129 2799 P 5249 2307 P 4894 3329 P 5092 3305 P 4905 2215 P 4162 2992 P 5458 2349 P 4591 3383 P 5731 2638 P 4223 2309 P 3956 2659 P 4227 3307 P 5032 2065 P 3925 3081 P 5844 3054 P 5234 3559 P 5726 3318 P 4308 2014 P 4743 1897 P 5502 2004 P 4024 3436 P 4812 3698 P 6049 3109 P 5879 2069 P 3425 2702 P 6303 2296 P 3506 2172 P 6807 2973 P 5903 3996 P 3946 4582 P 5623 710 P 1832 2278 P 1200 3114 P stroke grestore end showpage %%Trailer \end{filecontents} \begin{filecontents}{res1.eps} %% LaTeX2e file `res1.eps' %% generated by the `filecontents' environment %% from source `graeffe' on 1997/06/14. %% %!PS-Adobe-2.0 EPSF-2.0 %%Creator: gnuplot %%DocumentFonts: Helvetica %%BoundingBox: 50 50 410 302 %%EndComments /gnudict 40 dict def gnudict begin /Color false def /Solid false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 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 /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 /PL { stroke gnulinewidth 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 /P { stroke [] 0 setdash currentlinewidth 2 div sub M 20 currentlinewidth V stroke } def /D { 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 P } def /A { stroke [] 0 setdash vpt sub M 0 vpt2 V currentpoint stroke M hpt neg vpt neg R hpt2 0 V stroke } def /B { 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 P } def /C { 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 /T { 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 P } def /S { 2 copy A C} def end %%EndProlog gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Helvetica findfont 140 scalefont setfont newpath LTa LTb 672 211 M 63 0 V 6234 0 R -63 0 V 588 211 M (0.1) Rshow 672 674 M 31 0 V 6266 0 R -31 0 V 672 945 M 31 0 V 6266 0 R -31 0 V 672 1138 M 31 0 V 6266 0 R -31 0 V 672 1287 M 31 0 V 6266 0 R -31 0 V 672 1409 M 31 0 V 6266 0 R -31 0 V 672 1512 M 31 0 V 6266 0 R -31 0 V 672 1601 M 31 0 V 6266 0 R -31 0 V 672 1680 M 31 0 V 6266 0 R -31 0 V 672 1750 M 63 0 V 6234 0 R -63 0 V -6318 0 R (1) Rshow 672 2214 M 31 0 V 6266 0 R -31 0 V 672 2485 M 31 0 V 6266 0 R -31 0 V 672 2677 M 31 0 V 6266 0 R -31 0 V 672 2826 M 31 0 V 6266 0 R -31 0 V 672 2948 M 31 0 V 6266 0 R -31 0 V 672 3051 M 31 0 V 6266 0 R -31 0 V 672 3140 M 31 0 V 6266 0 R -31 0 V 672 3219 M 31 0 V 6266 0 R -31 0 V 672 3290 M 63 0 V 6234 0 R -63 0 V -6318 0 R (10) Rshow 672 3753 M 31 0 V 6266 0 R -31 0 V 672 4024 M 31 0 V 6266 0 R -31 0 V 672 4216 M 31 0 V 6266 0 R -31 0 V 672 4366 M 31 0 V 6266 0 R -31 0 V 672 4488 M 31 0 V 6266 0 R -31 0 V 672 4591 M 31 0 V 6266 0 R -31 0 V 672 4680 M 31 0 V 6266 0 R -31 0 V 672 4759 M 31 0 V 6266 0 R -31 0 V 672 4829 M 63 0 V 6234 0 R -63 0 V -6318 0 R (100) Rshow 672 211 M 0 63 V 0 4555 R 0 -63 V 672 71 M (10) Cshow 1620 211 M 0 31 V 0 4587 R 0 -31 V 2174 211 M 0 31 V 0 4587 R 0 -31 V 2568 211 M 0 31 V 0 4587 R 0 -31 V 2873 211 M 0 31 V 0 4587 R 0 -31 V 3122 211 M 0 31 V 0 4587 R 0 -31 V 3333 211 M 0 31 V 0 4587 R 0 -31 V 3515 211 M 0 31 V 0 4587 R 0 -31 V 3676 211 M 0 31 V 0 4587 R 0 -31 V 3821 211 M 0 63 V 0 4555 R 0 -63 V 3821 71 M (100) Cshow 4768 211 M 0 31 V 0 4587 R 0 -31 V 5323 211 M 0 31 V 0 4587 R 0 -31 V 5716 211 M 0 31 V 0 4587 R 0 -31 V 6021 211 M 0 31 V 0 4587 R 0 -31 V 6271 211 M 0 31 V 0 4587 R 0 -31 V 6481 211 M 0 31 V 0 4587 R 0 -31 V 6664 211 M 0 31 V 0 4587 R 0 -31 V 6825 211 M 0 31 V 0 4587 R 0 -31 V 6969 211 M 0 63 V 0 4555 R 0 -63 V 6969 71 M (1000) Cshow 672 211 M 6297 0 V 0 4618 V -6297 0 V 672 211 L 3820 4969 M (Time \(s\) for solving real polynomials) Cshow LT0 6486 4626 M ("rtiming") Rshow 6654 4626 P 3820 1657 P 3820 1650 P 3820 1634 P 3820 1657 P 3820 1634 P 3820 1687 P 3820 1680 P 3820 1642 P 3820 1665 P 3820 1650 P 4768 2536 P 4768 2530 P 4768 2513 P 4768 2524 P 4768 2551 P 4768 2536 P 4768 2524 P 4768 2538 P 4768 2559 P 4768 2534 P 5323 3055 P 5323 3059 P 5323 3055 P 5323 3062 P 5323 3055 P 5323 3059 P 5323 3056 P 5323 3060 P 5323 3066 P 5323 3052 P 5716 3448 P 5716 3443 P 5716 3446 P 5716 3444 P 5716 3466 P 5716 3445 P 5716 3440 P 5716 3436 P 5716 3439 P 5716 3435 P 6021 3756 P 6021 3731 P 6021 3732 P 6021 3719 P 6021 3734 P 6021 3740 P 6021 3746 P 6021 3724 P 6021 3722 P 6021 3725 P 6271 3961 P 6271 3968 P 6271 3967 P 6271 3960 P 6271 3976 P 6271 3963 P 6271 3977 P 6271 3980 P 6271 3974 P 6271 3975 P 6481 4173 P 6481 4192 P 6481 4197 P 6481 4178 P 6481 4163 P 6481 4162 P 6481 4172 P 6481 4164 P 6481 4168 P 6481 4163 P 6664 4352 P 6664 4343 P 6664 4347 P 6664 4347 P 6664 4349 P 6664 4348 P 6664 4346 P 6664 4364 P 6664 4360 P 6664 4348 P 6825 4503 P 6825 4548 P 6825 4498 P 6825 4498 P 6825 4499 P 6825 4495 P 6825 4499 P 6825 4505 P 6825 4504 P 6825 4496 P 6969 4640 P 6969 4640 P 6969 4644 P 6969 4661 P 6969 4647 P 6969 4639 P 6969 4638 P 6969 4639 P 6969 4655 P 6969 4642 P stroke grestore end showpage %%Trailer \end{filecontents} \begin{filecontents}{res2.eps} %% LaTeX2e file `res2.eps' %% generated by the `filecontents' environment %% from source `graeffe' on 1997/06/14. %% %!PS-Adobe-2.0 EPSF-2.0 %%Creator: gnuplot %%DocumentFonts: Helvetica %%BoundingBox: 50 50 410 302 %%EndComments /gnudict 40 dict def gnudict begin /Color false def /Solid false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 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 /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 /PL { stroke gnulinewidth 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 /P { stroke [] 0 setdash currentlinewidth 2 div sub M 20 currentlinewidth V stroke } def /D { 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 P } def /A { stroke [] 0 setdash vpt sub M 0 vpt2 V currentpoint stroke M hpt neg vpt neg R hpt2 0 V stroke } def /B { 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 P } def /C { 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 /T { 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 P } def /S { 2 copy A C} def end %%EndProlog gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Helvetica findfont 140 scalefont setfont newpath LTa LTb 672 211 M 63 0 V 6234 0 R -63 0 V 588 211 M (1) Rshow 672 674 M 31 0 V 6266 0 R -31 0 V 672 945 M 31 0 V 6266 0 R -31 0 V 672 1138 M 31 0 V 6266 0 R -31 0 V 672 1287 M 31 0 V 6266 0 R -31 0 V 672 1409 M 31 0 V 6266 0 R -31 0 V 672 1512 M 31 0 V 6266 0 R -31 0 V 672 1601 M 31 0 V 6266 0 R -31 0 V 672 1680 M 31 0 V 6266 0 R -31 0 V 672 1750 M 63 0 V 6234 0 R -63 0 V -6318 0 R (10) Rshow 672 2214 M 31 0 V 6266 0 R -31 0 V 672 2485 M 31 0 V 6266 0 R -31 0 V 672 2677 M 31 0 V 6266 0 R -31 0 V 672 2826 M 31 0 V 6266 0 R -31 0 V 672 2948 M 31 0 V 6266 0 R -31 0 V 672 3051 M 31 0 V 6266 0 R -31 0 V 672 3140 M 31 0 V 6266 0 R -31 0 V 672 3219 M 31 0 V 6266 0 R -31 0 V 672 3290 M 63 0 V 6234 0 R -63 0 V -6318 0 R (100) Rshow 672 3753 M 31 0 V 6266 0 R -31 0 V 672 4024 M 31 0 V 6266 0 R -31 0 V 672 4216 M 31 0 V 6266 0 R -31 0 V 672 4366 M 31 0 V 6266 0 R -31 0 V 672 4488 M 31 0 V 6266 0 R -31 0 V 672 4591 M 31 0 V 6266 0 R -31 0 V 672 4680 M 31 0 V 6266 0 R -31 0 V 672 4759 M 31 0 V 6266 0 R -31 0 V 672 4829 M 63 0 V 6234 0 R -63 0 V -6318 0 R (1000) Rshow 672 211 M 0 63 V 0 4555 R 0 -63 V 672 71 M (10) Cshow 1620 211 M 0 31 V 0 4587 R 0 -31 V 2174 211 M 0 31 V 0 4587 R 0 -31 V 2568 211 M 0 31 V 0 4587 R 0 -31 V 2873 211 M 0 31 V 0 4587 R 0 -31 V 3122 211 M 0 31 V 0 4587 R 0 -31 V 3333 211 M 0 31 V 0 4587 R 0 -31 V 3515 211 M 0 31 V 0 4587 R 0 -31 V 3676 211 M 0 31 V 0 4587 R 0 -31 V 3821 211 M 0 63 V 0 4555 R 0 -63 V 3821 71 M (100) Cshow 4768 211 M 0 31 V 0 4587 R 0 -31 V 5323 211 M 0 31 V 0 4587 R 0 -31 V 5716 211 M 0 31 V 0 4587 R 0 -31 V 6021 211 M 0 31 V 0 4587 R 0 -31 V 6271 211 M 0 31 V 0 4587 R 0 -31 V 6481 211 M 0 31 V 0 4587 R 0 -31 V 6664 211 M 0 31 V 0 4587 R 0 -31 V 6825 211 M 0 31 V 0 4587 R 0 -31 V 6969 211 M 0 63 V 0 4555 R 0 -63 V 6969 71 M (1000) Cshow 672 211 M 6297 0 V 0 4618 V -6297 0 V 672 211 L 3820 4969 M (Time \(s\) for solving complex polynomials) Cshow LT0 6486 4626 M ("ctiming") Rshow 6654 4626 P 3820 316 P 3820 355 P 3820 299 P 3820 299 P 3820 322 P 3820 344 P 3820 310 P 3820 304 P 3820 338 P 3820 386 P 4768 1186 P 4768 1211 P 4768 1181 P 4768 1158 P 4768 1186 P 4768 1186 P 4768 1233 P 4768 1186 P 4768 1255 P 4768 1151 P 5323 1737 P 5323 1705 P 5323 1769 P 5323 1834 P 5323 1727 P 5323 1710 P 5323 1834 P 5323 1701 P 5323 1759 P 5323 1703 P 5716 2111 P 5716 2087 P 5716 2233 P 5716 2107 P 5716 2110 P 5716 2137 P 5716 2162 P 5716 2057 P 5716 2054 P 5716 2083 P 6021 2383 P 6021 2411 P 6021 2384 P 6021 2433 P 6021 2406 P 6021 2383 P 6021 2483 P 6021 2350 P 6021 2430 P 6021 2408 P 6271 2608 P 6271 2601 P 6271 2606 P 6271 2606 P 6271 2628 P 6271 2727 P 6271 2603 P 6271 2602 P 6271 2604 P 6271 2657 P 6481 2795 P 6481 2847 P 6481 2962 P 6481 2945 P 6481 2766 P 6481 2829 P 6481 2821 P 6481 2770 P 6481 2848 P 6481 2820 P 6664 2982 P 6664 2927 P 6664 2981 P 6664 3110 P 6664 2956 P 6664 2988 P 6664 2993 P 6664 3063 P 6664 2986 P 6664 3049 P 6825 3131 P 6825 3102 P 6825 3180 P 6825 3127 P 6825 3075 P 6825 3158 P 6825 3101 P 6825 3153 P 6825 3181 P 6825 3129 P 6969 3289 P 6969 3283 P 6969 3229 P 6969 3311 P 6969 3288 P 6969 3321 P 6969 3360 P 6969 3312 P 6969 3357 P 6969 3290 P stroke grestore end showpage %%Trailer \end{filecontents} \begin{filecontents}{res3.eps} %% LaTeX2e file `res3.eps' %% generated by the `filecontents' environment %% from source `graeffe' on 1997/06/14. %% %!PS-Adobe-2.0 EPSF-2.0 %%Creator: gnuplot %%DocumentFonts: Helvetica %%BoundingBox: 50 50 410 302 %%EndComments /gnudict 40 dict def gnudict begin /Color false def /Solid false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 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 /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 /PL { stroke gnulinewidth 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 /P { stroke [] 0 setdash currentlinewidth 2 div sub M 20 currentlinewidth V stroke } def /D { 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 P } def /A { stroke [] 0 setdash vpt sub M 0 vpt2 V currentpoint stroke M hpt neg vpt neg R hpt2 0 V stroke } def /B { 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 P } def /C { 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 /T { 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 P } def /S { 2 copy A C} def end %%EndProlog gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Helvetica findfont 140 scalefont setfont newpath LTa LTb 672 211 M 63 0 V 6234 0 R -63 0 V 588 211 M (1e-07) Rshow 672 489 M 31 0 V 6266 0 R -31 0 V 672 857 M 31 0 V 6266 0 R -31 0 V 672 1045 M 31 0 V 6266 0 R -31 0 V 672 1135 M 63 0 V 6234 0 R -63 0 V -6318 0 R (1e-06) Rshow 672 1413 M 31 0 V 6266 0 R -31 0 V 672 1780 M 31 0 V 6266 0 R -31 0 V 672 1969 M 31 0 V 6266 0 R -31 0 V 672 2058 M 63 0 V 6234 0 R -63 0 V -6318 0 R (1e-05) Rshow 672 2336 M 31 0 V 6266 0 R -31 0 V 672 2704 M 31 0 V 6266 0 R -31 0 V 672 2892 M 31 0 V 6266 0 R -31 0 V 672 2982 M 63 0 V 6234 0 R -63 0 V -6318 0 R (0.0001) Rshow 672 3260 M 31 0 V 6266 0 R -31 0 V 672 3627 M 31 0 V 6266 0 R -31 0 V 672 3816 M 31 0 V 6266 0 R -31 0 V 672 3905 M 63 0 V 6234 0 R -63 0 V -6318 0 R (0.001) Rshow 672 4183 M 31 0 V 6266 0 R -31 0 V 672 4551 M 31 0 V 6266 0 R -31 0 V 672 4739 M 31 0 V 6266 0 R -31 0 V 672 4829 M 63 0 V 6234 0 R -63 0 V -6318 0 R (0.01) Rshow 672 211 M 0 63 V 0 4555 R 0 -63 V 672 71 M (10) Cshow 1620 211 M 0 31 V 0 4587 R 0 -31 V 2174 211 M 0 31 V 0 4587 R 0 -31 V 2568 211 M 0 31 V 0 4587 R 0 -31 V 2873 211 M 0 31 V 0 4587 R 0 -31 V 3122 211 M 0 31 V 0 4587 R 0 -31 V 3333 211 M 0 31 V 0 4587 R 0 -31 V 3515 211 M 0 31 V 0 4587 R 0 -31 V 3676 211 M 0 31 V 0 4587 R 0 -31 V 3821 211 M 0 63 V 0 4555 R 0 -63 V 3821 71 M (100) Cshow 4768 211 M 0 31 V 0 4587 R 0 -31 V 5323 211 M 0 31 V 0 4587 R 0 -31 V 5716 211 M 0 31 V 0 4587 R 0 -31 V 6021 211 M 0 31 V 0 4587 R 0 -31 V 6271 211 M 0 31 V 0 4587 R 0 -31 V 6481 211 M 0 31 V 0 4587 R 0 -31 V 6664 211 M 0 31 V 0 4587 R 0 -31 V 6825 211 M 0 31 V 0 4587 R 0 -31 V 6969 211 M 0 63 V 0 4555 R 0 -63 V 6969 71 M (1000) Cshow 672 211 M 6297 0 V 0 4618 V -6297 0 V 672 211 L 3820 4969 M (Moduli separation of real polynomials) Cshow LT0 6486 4626 M ("rsep") Rshow 6654 4626 P 3820 2840 P 3820 3271 P 3820 3362 P 3820 4038 P 3820 2955 P 3820 4189 P 3820 3886 P 3820 2633 P 3820 2806 P 3820 3065 P 4768 3206 P 4768 2818 P 4768 3529 P 4768 2838 P 4768 3231 P 4768 3416 P 4768 3012 P 4768 2939 P 4768 3046 P 4768 2872 P 5323 2169 P 5323 2200 P 5323 3139 P 5323 3595 P 5323 3168 P 5323 3133 P 5323 3182 P 5323 1757 P 5323 2405 P 5323 3213 P 5716 2085 P 5716 2327 P 5716 2613 P 5716 2531 P 5716 1656 P 5716 3181 P 5716 2590 P 5716 2856 P 5716 1359 P 5716 2631 P 6021 2354 P 6021 2713 P 6021 1957 P 6021 794 P 6021 1577 P 6021 2408 P 6021 2610 P 6021 1176 P 6021 2691 P 6021 2709 P 6271 2534 P 6271 1745 P 6271 2351 P 6271 1922 P 6271 2365 P 6271 1817 P 6271 2474 P 6271 1782 P 6271 2537 P 6271 2685 P 6481 2404 P 6481 2763 P 6481 1977 P 6481 2333 P 6481 1776 P 6481 1718 P 6481 1609 P 6481 2719 P 6481 2279 P 6481 2119 P 6664 2228 P 6664 2099 P 6664 1452 P 6664 2148 P 6664 1747 P 6664 2717 P 6664 2327 P 6664 2064 P 6664 2030 P 6664 2284 P 6825 2023 P 6825 2105 P 6825 1448 P 6825 1101 P 6825 1956 P 6825 236 P 6825 2173 P 6825 2243 P 6825 1898 P 6825 2019 P 6969 1932 P 6969 2660 P 6969 1696 P 6969 2389 P 6969 1800 P 6969 1877 P 6969 1666 P 6969 2316 P 6969 1618 P 6969 1759 P stroke grestore end showpage %%Trailer \end{filecontents} \begin{filecontents}{res4.eps} %% LaTeX2e file `res4.eps' %% generated by the `filecontents' environment %% from source `graeffe' on 1997/06/14. %% %!PS-Adobe-2.0 EPSF-2.0 %%Creator: gnuplot %%DocumentFonts: Helvetica %%BoundingBox: 50 50 410 302 %%EndComments /gnudict 40 dict def gnudict begin /Color false def /Solid false def /gnulinewidth 5.000 def /vshift -46 def /dl {10 mul} def /hpt 31.5 def /vpt 31.5 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 /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 /PL { stroke gnulinewidth 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 /P { stroke [] 0 setdash currentlinewidth 2 div sub M 20 currentlinewidth V stroke } def /D { 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 P } def /A { stroke [] 0 setdash vpt sub M 0 vpt2 V currentpoint stroke M hpt neg vpt neg R hpt2 0 V stroke } def /B { 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 P } def /C { 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 /T { 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 P } def /S { 2 copy A C} def end %%EndProlog gnudict begin gsave 50 50 translate 0.050 0.050 scale 0 setgray /Helvetica findfont 140 scalefont setfont newpath LTa LTb 672 211 M 63 0 V 6234 0 R -63 0 V 588 211 M (1e-08) Rshow 672 489 M 31 0 V 6266 0 R -31 0 V 672 857 M 31 0 V 6266 0 R -31 0 V 672 1045 M 31 0 V 6266 0 R -31 0 V 672 1135 M 63 0 V 6234 0 R -63 0 V -6318 0 R (1e-07) Rshow 672 1413 M 31 0 V 6266 0 R -31 0 V 672 1780 M 31 0 V 6266 0 R -31 0 V 672 1969 M 31 0 V 6266 0 R -31 0 V 672 2058 M 63 0 V 6234 0 R -63 0 V -6318 0 R (1e-06) Rshow 672 2336 M 31 0 V 6266 0 R -31 0 V 672 2704 M 31 0 V 6266 0 R -31 0 V 672 2892 M 31 0 V 6266 0 R -31 0 V 672 2982 M 63 0 V 6234 0 R -63 0 V -6318 0 R (1e-05) Rshow 672 3260 M 31 0 V 6266 0 R -31 0 V 672 3627 M 31 0 V 6266 0 R -31 0 V 672 3816 M 31 0 V 6266 0 R -31 0 V 672 3905 M 63 0 V 6234 0 R -63 0 V -6318 0 R (0.0001) Rshow 672 4183 M 31 0 V 6266 0 R -31 0 V 672 4551 M 31 0 V 6266 0 R -31 0 V 672 4739 M 31 0 V 6266 0 R -31 0 V 672 4829 M 63 0 V 6234 0 R -63 0 V -6318 0 R (0.001) Rshow 672 211 M 0 63 V 0 4555 R 0 -63 V 672 71 M (10) Cshow 1620 211 M 0 31 V 0 4587 R 0 -31 V 2174 211 M 0 31 V 0 4587 R 0 -31 V 2568 211 M 0 31 V 0 4587 R 0 -31 V 2873 211 M 0 31 V 0 4587 R 0 -31 V 3122 211 M 0 31 V 0 4587 R 0 -31 V 3333 211 M 0 31 V 0 4587 R 0 -31 V 3515 211 M 0 31 V 0 4587 R 0 -31 V 3676 211 M 0 31 V 0 4587 R 0 -31 V 3821 211 M 0 63 V 0 4555 R 0 -63 V 3821 71 M (100) Cshow 4768 211 M 0 31 V 0 4587 R 0 -31 V 5323 211 M 0 31 V 0 4587 R 0 -31 V 5716 211 M 0 31 V 0 4587 R 0 -31 V 6021 211 M 0 31 V 0 4587 R 0 -31 V 6271 211 M 0 31 V 0 4587 R 0 -31 V 6481 211 M 0 31 V 0 4587 R 0 -31 V 6664 211 M 0 31 V 0 4587 R 0 -31 V 6825 211 M 0 31 V 0 4587 R 0 -31 V 6969 211 M 0 63 V 0 4555 R 0 -63 V 6969 71 M (1000) Cshow 672 211 M 6297 0 V 0 4618 V -6297 0 V 672 211 L 3820 4969 M (Moduli separation of complex polynomials) Cshow LT0 6486 4626 M ("csep") Rshow 6654 4626 P 3820 4322 P 3820 3333 P 3820 4294 P 3820 4325 P 3820 3937 P 3820 4188 P 3820 4105 P 3820 4236 P 3820 4084 P 3820 3434 P 4768 3691 P 4768 3321 P 4768 3786 P 4768 3863 P 4768 4014 P 4768 3942 P 4768 3228 P 4768 4060 P 4768 3208 P 4768 4042 P 5323 3328 P 5323 3597 P 5323 3336 P 5323 3083 P 5323 3724 P 5323 3828 P 5323 2231 P 5323 3320 P 5323 2945 P 5323 3606 P 5716 3199 P 5716 2854 P 5716 1337 P 5716 2824 P 5716 2914 P 5716 2654 P 5716 2464 P 5716 3397 P 5716 2949 P 5716 2957 P 6021 2817 P 6021 2073 P 6021 2763 P 6021 2385 P 6021 2717 P 6021 2946 P 6021 2007 P 6021 3103 P 6021 2126 P 6021 2658 P 6271 3001 P 6271 3000 P 6271 3090 P 6271 2672 P 6271 2278 P 6271 1259 P 6271 2765 P 6271 2882 P 6271 2821 P 6271 2152 P 6481 3147 P 6481 2225 P 6481 696 P 6481 904 P 6481 3040 P 6481 2622 P 6481 2593 P 6481 2817 P 6481 2453 P 6481 2965 P 6664 2659 P 6664 2910 P 6664 2393 P 6664 1182 P 6664 2784 P 6664 2149 P 6664 2644 P 6664 1541 P 6664 1994 P 6664 1966 P 6825 2543 P 6825 2503 P 6825 2106 P 6825 2715 P 6825 3058 P 6825 2043 P 6825 2689 P 6825 2397 P 6825 2069 P 6825 2549 P 6969 2365 P 6969 1969 P 6969 2762 P 6969 1752 P 6969 2170 P 6969 1682 P 6969 1395 P 6969 1732 P 6969 1279 P 6969 1961 P stroke grestore end showpage %%Trailer \end{filecontents} \documentclass[12pt]{article} \usepackage{amscd} \usepackage{amssymb} \usepackage{amsthm} \usepackage{amsmath} \usepackage{graphics} \newcommand{\zz}{ {\zeta} } \newcommand{\bigo}{ {\mathcal{O}} } \newcommand{\littleo}{ {\mathrm{o}} } \newcommand{\binomial}[2]{\left(\begin{array}{c}{#1}\\{#2}\end{array}\right)} \newcommand{\pol}[1]{{\mathcal P}_{#1}} \newcommand{\vol}{\mathbf Vol\ } \newcommand{\ppol}[1]{{\mathbb P}{\cal P}_{#1}} \newcommand{\bydef}{\stackrel{\mbox{\scriptsize def}}{=}} \newtheorem* {main}{Main Result} \newtheorem {theorem} {Theorem} \newtheorem*{theoquo} {Theorem} \newtheorem {lemma} {Lemma} \newtheorem*{lemma*} {Lemma} \newtheorem {proposition} {Proposition} \theoremstyle{definition} \newtheorem {definition}{Definition} \newtheorem {axiom}{Axiom} \newtheorem {notice}{Important Note} \newtheorem {remark}{Remark} \newtheorem {example}{Example} \newlength{\gnat} \settowidth{\gnat}{$\square$} \newcommand{\newsquare}[1]{{\square \hspace{-\gnat} {\makebox[\gnat]{\raisebox{.25ex}{#1}}}}} \newcommand{\checkedbox}{\newsquare{\checkmark}} \newcommand{\renplus}[1]{{\boxplus_{#1}}} \newcommand{\renminus}[1]{{\boxminus_{#1}}} \newcommand{\rentimes}[1]{\boxtimes} % \newcommand{\renplus}[1]{\fbox{\small $+$}_{#1}} % \newcommand{\rentimes}[1]{\fbox{\small $\times$}_{#1}} % \newcommand{\rendiv}[1]{{\square_{#1}}} \newcommand{\rendiv}[1]{{\newsquare{:}}} \newcommand{\renpow}[2]{\ ^{\fbox{\tiny $#2$}}} \newcommand{\renscal}[2]{\fbox{\tiny $#2$}_{#1}} \newcommand{\bigrenplus}[1]{{\fbox{+}}_{#1}} \newcommand{\RT}[2]{{\mathbb R}^{#1} \times {\mathbb T}^{#2} } \newcommand{\orb}{{\mathrm{orb}}} \newcommand{\smthg}{{ Lipschitz with constant $C_{k}$ }} \newcommand{\dist}{{ \mathrm{d}}} % \newcommand{\smthg}{local diffeomorphism with derivative bounded in norm by $C_{k}$} %\newcommand{\newtext}[2]{\marginpar{ {\typeout{MARGINPAR #2 Page \arabic{page}}}\tiny #2}{\boldmath \bf \large{#1}}} %\newcommand{\oldtext}[1]{[{\tiny {#1}}]} %\newcommand{\newtext}[2]{\marginpar{ {\typeout{MARGINPAR #2 Page \arabic{page}}}\tiny #2}{#1}} %\newcommand{\oldtext}[1]{} \newcommand{\newtext}[2]{{#1}} \newcommand{\oldtext}[1]{} % Since we don't know how to hyphenate Graeffe, we just don't. \hyphenation {Graeffe} \title{On the Geometry of Graeffe Iteration} \author{Gregorio Malajovich\\ {\small \em Dep. de Matem\'atica Aplicada, Universidade Federal do Rio de Janeiro}\\ {\small \em Caixa Postal 68530, Rio de Janeiro, RJ, 21945 -- BRASIL}\\ {\small \em gregorio@labma.ufrj.br, http://www.labma.ufrj.br/\~{}gregorio} \\ \and Jorge P. Zubelli\\ {\small \em IMPA}\\ {\small \em Estrada Dona Castorina 110, Rio de Janeiro, RJ, 22460-320, BRASIL}\\ {\small \em zubelli@impa.br, http://www.impa.br/\~{}zubelli}\\} \date{Second revision, Aug 26, 1999} \begin{document} \maketitle \begin{abstract} A new version of the Graeffe algorithm for finding all the roots of univariate complex polynomials is proposed. It is obtained from the classical algorithm by a process analogous to renormalization of dynamical systems. \par This iteration is called Renormalized Graeffe Iteration. It is globally convergent, with probability 1. All quantities involved in the computation are bounded, once the initial polynomial is given (with probability 1). This implies remarkable stability properties for the new algorithm, thus overcoming known limitations of the classical Graeffe algorithm. \par If we start with a degree-$d$ polynomial, each renormalized Graeffe iteration costs $\bigo(d^2)$ arithmetic operations, with memory $\bigo(d)$. \par A probabilistic global complexity bound is given. The case of univariate real polynomials is briefly discussed. \par A numerical implementation of the algorithm presented herein allowed us to solve random polynomials of degree up to 1000. \end{abstract} \newpage \vspace{\stretch{1}} \ \\ \tableofcontents \vspace{\stretch{1}} \newpage \section{Introduction} \label{Sec1} \par {\em Graeffe Iteration} was \oldtext{certainly} \newtext{one of}{A6\S 2(2)} the most prestigious XIX century algorithm for finding roots of polynomials. At that time, computations were performed by hand, by people payed specifically to perform those computations. They were called {\em calculateurs}~\cite{OSTROWSKII} or {\em computers}~\cite{BABBAGE}. \par Let $f$ be a univariate polynomial, of degree $d$. Its Graeffe iterate is defined as: \begin{equation} Gf(x) = (-1)^d f(\sqrt{x}) f(-\sqrt{x}) \end{equation} \par This defines a many-to-one mapping in the space of all degree-$d$ polynomials (real or complex, as wish). The effect of this mapping is to square each root of $f$. \par After a few Graeffe iterations, the roots of $G^k f$ have (hopefully) incommensurate moduli. This is not true for \newtext{complex-}{A5(1)}conjugate roots, which can be worked out in a different way. \par Assume, for simplicity, that $f$ is a complex polynomial, with no two roots of the same modulus. Then, $G^k f$ can be written \begin{equation} G^k f(x) = \sum_{i=0}^d a^{(k)}_i x^i \end{equation} where $a^{(k)}_i$ is given by the \oldtext{$d-i$-symmetric} \newtext{$(d-i)$-th symmetric}{A7(1)} function of the roots of $G^k f$. Therefore, $a^{(k)}_i$ is dominated by: \begin{equation} (-1)^{d-i} {\zeta_1}^{2^k} {\zeta_2}^{2^k} \dots {\zeta_{d-i}}^{2^k} \end{equation} where $\zeta_1$, \dots, $\zeta_d$ are the roots of $f$ ordered with decreasing modulus. (A more rigorous statement of this will appear in Section~ \ref{Sec4}) \par Therefore, $-a^{(k)}_{i-1} / a^{(k)}_{i}$ is a good approximation for ${\zeta_{d-i+1}}^{2^k}$. \par \oldtext{Hence, we can easily obtain $|\zeta_i|$ for all $i$. There are many classical algorithms to recover the actual value of $\zeta_i$.} \newtext{Hence it is computationally easy to approximate $|\zeta_i|$ for all $i$. Although we also obtain $\arg \zeta_i \mod 2^{1-k} \pi$, we will discard this information in this paper to avoid additional complications. There are many classical algorithms to recover the actual value of $\zeta_i$. }{A5(2-3)} See Pan~\cite{PAN} for a discussion. \footnote{Added in the revised version: We deal with this issue in ~\cite{TANGRA}.} \medskip \par \oldtext{In this note, we claim that Graeffe iteration (after a suitable change of coordinates) is a globally convergent algorithm with probability $1$ (Theorem~1 below).} \newtext{In this note, we apply a suitable non-uniform change of coordinates (renormalization) to the Graeffe iteration operator, to make it `convergent' with probability $1$. \par The algorithm obtained by this change of coordinates will be called {\em Renormalized Graeffe Iteration}. We use the following systems of coordinates for each iterate $G^{k} f$ of the Graeffe method applied to $f$: % $f$, $Gf$, $G^2f$, $\cdots$, $G^k(f)$, $\cdots$: The coefficients of $G^k(f)$ and all related intermediate computations will be represented in scaled polar coordinates, where a complex number $w$ is represented by `magnitude' $2^{-k} \log_2 |w|$ and `argument' $\arg w \in [-\pi, \pi]$. Calculations will always be performed `in coordinates'. The `magnitude' variables of $G^k f$ `in coordinates' will converge with probability~1 (Theorem~\ref{th1} below). \par The precise construction of the Renormalized Graeffe Operator is postponed to Section~\ref{Sec2}. \medskip }{A2\S -1, A5(4-5) and B\S 3} \par We also claim that the Renormalized Graeffe algorithm compares well with available numerical software or theoretical algorithms. \newtext{\par However, in this paper, we are considering a modified problem: our algorithm is designed to find the absolute values of the roots, not the actual roots. Therefore we will compare its complexity to the complexity of finding the absolute value of the roots by other existing algorithms. \par In \cite{TANGRA}, we explain how to modify this algorithm to obtain the actual roots, without endangering the complexity estimates. \par } {A2(1)} The algorithm presented here has arithmetic complexity $\bigo(d^{2})$ for each iteration, and memory size $\bigo(d)$, where $d$ is the degree of the polynomial. %\newtext{The number of steps for obtaining an accurate value of the % roots is $O(\log d)$, see Theorem~\ref{th2} below.}{A2(2)} \par \oldtext{Complexity}\newtext{The number of iterations}{A2(2)} will be bounded also in terms of a probability of failure (Theorem~\ref{th2} below). \oldtext{This will be possible due to} \newtext{The authors personally believe that this is only possible due to}{A5(6)} the clean mathematical structure of Graeffe iteration. Our bound improves previous probabilistic bounds \newtext{(in the sense of probability of success)}{A7(2)} on the complexity of solving polynomials. (See Renegar~ \cite{RENEGAR} and Shub-Smale~\cite{BEZIV}). \par Also, our algorithm compares well with practical software, like for instance the algorithm in Matlab (running time $\bigo(d^{3})$ and memory $\bigo(d^{2})$). \newtext{Instead, Renormalized Graeffe Iteration seems to run in time $\bigo(d^2)$. It also} {A2(2)} \oldtext{Renormalized Graeffe iteration} seems much more stable, for \newtext{most (in a probabilistic sense)}{A3\S 1} \oldtext{generic} complex polynomials of degree, say, 1000. (See Section~\ref{Sec6} for a discussion of preliminary experimental results). \par \newtext{In order to compare with deterministic algorithms one should bear in mind that the algorithm presented here is probabilistic and may be quite slow on a set of non-zero measure. Also, the complexity of deterministic algorithms such as \cite{NEFF-REIF,PAN,SCHONHAGE0,SCHONHAGE} can be given in terms of number of arithmetic operations or in number of bit operations. % The authors of this paper We believe that estimates of the order of $\bigo(d^{1+\alpha})$, $\alpha >0$ in the number of operations are made at the expense of a large increase in the working precision, of the order of $\bigo(d^{2+\alpha})$ bits. However, this is not a lower bound and it may as well happen that those algorithms can work with substantially smaller precision on a large set of inputs. \par In comparison, our Renormalized Graeffe Iteration was designed for floating-point arithmetic (our results assume an arbitrary, but fixed floating-point precision).}{A2(3--5)} \oldtext{ In order to compare it with theoretical algorithms of arithmetic complexity $\bigo(d^{1+\alpha})$, $\alpha >0$, (see \cite{NEFF-REIF,PAN,SCHONHAGE0,SCHONHAGE}) one has to keep in mind that the bit complexity of those fast algorithms is (crudely) $\bigo(d^{3+\alpha})$, since they require at least $\bigo(d^{2+\alpha})$ bits of precision (We are omitting here several factors). In comparison, our Renormalized Graeffe Iteration is, by construction, suitable to usual floating-point arithmetic. } However, the details of the rounding-off analysis of renormalized Graeffe iteration will not be discussed in this paper. \par Instead, some preliminary numerical results are presented in Section~\ref{Sec6}. They support the \newtext{empirical}{A5(7)} fact that \oldtext{generic} \newtext{typical random}{A3\S 1} degree 1000 polynomials can be solved within a precision of \oldtext{64} \newtext{64}{A5(7)} bits of mantissa \newtext{(IEEE 854 long double)}{A5(7)}. We expect a factor of a \oldtext{polylog of $d$} \newtext{polynomial in $\log d$}{A5(8)} bits of mantissa to be \oldtext{necessary} \newtext{sufficient}{A5(8)} in general, with probability 1. (This is a conjecture). \newtext{ \par The result in Theorem~\ref{theo1} holds for ``reasonable'' probability distributions on the space of polynomials. By reasonable, we mean all probabilities with bounded Radon-Nikodym derivative with respect to Lebesgue probability in the projectivization of coefficient space. }{Changed.} \begin{theorem} \label{th1} There is \oldtext{(we construct)} a renormalization of the Graeffe iteration, such that if $f$ is a \oldtext{generic} degree-$d$ polynomial (in a measure theoretical sense) then \newtext{with probability 1}{A3\S 1} this renormalized Graeffe iteration produces $d+1$ sequences, each one converging to some $h_i$, s.t. $\log |\zeta_{i}| = h_i - h_{i+1}$, and \oldtext{$\zeta_{i}$ is a root} \newtext{$\zeta_1$, $\cdots$, $\zeta_d$ are roots}{A5(10)} of $f$. Moreover, each iteration can be performed in $\bigo(d^2)$ arithmetical operations and all iterations can be performed with memory $\bigo(d)$. \label{theo1} \end{theorem} \par \newtext{ This theorem is constructive, in the sense that an explicit construction of the renormalized Graeffe iteration will be given.}{A5(9)} \par In Section~\ref{Sec2}, we discuss the precise meaning of renormalization in our context. Its main consequence, will be to produce an algorithm operating on a bounded set of numbers. This solves the main stability problem of classical Graeffe iteration that prevented it from finding all roots at once. See for example Henrici's comments on \oldtext{Graeffe~\cite{HENRICI}} \newtext{FFT-based Graeffe iteration~\cite{HENRICI} (Vol~III, last paragraph of p. 69)}{A5(11)}. \oldtext{ \par The definition of renormalization will outlaw, for instance, the following fast but unstable algorithm: Perform $k$ steps of Graeffe using FFT-based polynomial multiplication, where $k$ is given in Theorem~\ref{th2} } \newtext{ The definition of renormalization will outlaw FFT-based Graeffe iteration. Indeed, although FFT is known to be stable with respect to vector norms, it is not component-wise stable with respect to the relative error. This means that some of the coefficients of the $k$-th Graeffe iterate may have a large relative error, and hence some of the roots will be extremely inaccurate. This may be disastrous if one wants to retrieve all the roots at the same time.}{B\S 2(1)} \medskip \par % \par The result in Theorem~\ref{theo1} holds for ``reasonable'' % probability distributions on the space of polynomials. By % reasonable, we mean all absolutely continuous probability % distributions % with respect to Lebesgue probability in coefficient space. \newtext{ \begin{theorem}\label{th2} Let $f$ be a random complex polynomial of degree $d$. Let $b \ge 1 + \log_2 d$. Then, with probability $1-\delta$, $k$ steps of the Renormalized Graeffe Iteration will approximate the $\log |\zeta_i|$'s with relative precision $2^{-b}$, where \[ k \ge c_1 + c_2 \log_2 b - c_3 \log_2 \delta \] and $c_2$, $c_3$ are universal constants. The constant $c_1$ depends on the choice of the probability distribution, and on $d$. \end{theorem} Whenever speaking of random polynomials, we like to consider the normally invariant probability density introduced by Kostlan~\cite{KOSTLAN} (See also Section~\ref{Sec5}). However, the above mentioned result is true for any reasonable probability distribution. The experimental results in figure~\ref{results4} support the conjecture that, under Kostlan's probability distribution, we can fix \[ c_1 = c_4 \log_2 d \] where $c_4 \approx 2$ is a universal constant. }{} \par \newtext{}{LARGE SECTION DELETED} \medskip \par We will briefly discuss the real case, and how to deal with \newtext{complex-}{A5(1)}conjugate roots or roots with same modulus in Section ~\ref{Sec4}. % from now on old % and of bounded number % range will be explained in Section~\ref{explains}. % The model of computation is {\em idealized} IEEE % floating point arithmetic. This means we assume % that we have a large enough number of bits of mantissa % and exponent. However, we do require this number of bits % to be finite, given any input. % This model allows approximate and transcendental operations. \medskip \par {\bf Historical remarks}. The Graeffe iteration was developed independently by Dandelin (1826), by Graeffe (1837) and by Lobachevsky (1834). We call it Graeffe iteration to conform with most of the literature. See Householder~\cite{HOUSEHOLDER} for early references and priority questions. See Dedieu~\cite{DEDIEU} for an application of Graeffe \newtext{'s}{A7(4)} algorithm. % SEM A FOTO DO GRAEFFE E DO DANDELIN FICAMOS TENDENCIOSOS! % \marginpar{ \special{psfile=lobatchevskii.ps voffset=-200 hoffset=-160 vscale=60 hscale=60 } % \ \\ {\tiny N.I.Lobachevsky}} \par Important theoretical results were obtained by Ostrowskii~\cite{OSTROWSKII} in 1940. Also, by that time, numerical analysis books mentioned Graeffe iteration as the preferred algorithm for zero-finding (see e.g. Uspensky ~\cite{USPENSKII} \newtext{Page 318}{A6\S 2(1)}. For another early \oldtext{computational} \newtext{computer implemented}{A7(5)} algorithm, see Bareiss~\cite{BAREISS1,BAREISS2} and also Blish and Curry~\cite{BC}). \par With the advent of digital computing, the practical use of Graeffe iteration seems to have been forgotten. Most popular zero-finding algorithms seem to be based now on QR iteration (Matlab) or in a several steps, root-finding plus deflation scheme. (e.g. Jenkins and Traub \cite{JENKINS-TRAUB}). \oldtext{However} \newtext{See, however,}{} Cardinal~\cite{CARDINAL}, Edelman and Murakami~\cite{EDELMAN-MURAKAMI}, Emiris, Galligo and Lombardi ~\cite{EGH}, and Toh and Trefethen~\cite{TREFETHEN-TOH}. \par In a more theoretical perspective, Graeffe iteration is considered as a sort of pre-conditioning for polynomial splitting. Splitting a polynomial means factorizing it into one factor with \oldtext{very}\newtext{}{A6\S 2(1)} large roots, and another with \oldtext{very} small roots. Splitting is used to obtain extremely fast theoretical algorithms (see Sch\"onhage~\cite{SCHONHAGE0, SCHONHAGE}, \newtext{Kirrinnis~\cite{KIRRINIS}, Neff and Reif~\cite{NEFF-REIF},}{A7(6)} Bini and Pan~\cite{BP2}, Mourrain and Pan~\cite{MP}, Pan~\cite{PAN2,PAN3,PAN}, Pan et \oldtext{alli} \newtext{al.}{A7(7)}~\cite{PANETALLI}, Malajovich and Zubelli ~\cite{SPLITTING}). The main practical difficulty for those algorithms seems to be the large precision required by Graeffe iteration. Also, those algorithms are quite close to known lower bounds on \oldtext{arithmetic} \newtext{topological}{A5(15)} complexity (See Vassiliev~\cite{VASSILIEV}). For a related lower bound see Novak and Wo\'zniakowski~\cite{NW}. \par An important paper by Grau in 1963~\cite{GRAU} laid some of the bases for a version of Graeffe iteration adapted to digital computers. He identified the problem of the increasing {\em numerical range}. During Graeffe iteration, some of the coefficients can become so large that the floating point system cannot accommodate them anymore. \par While most of the literature suggests to find one root at a time and then use deflation, disregarding some stability problems (See e.g. Henrici~\cite{HENRICI}), Grau proposed a globally convergent algorithm. Grau's algorithm would involve only bounded quantities. \par As far as we know, that paper was completely forgotten. The algorithm suggested by Grau has complexity $\bigo(d^2)$ and memory usage of $\bigo(d^2)$. It may be considered as the precursor of the one we shall introduce below. \section{Iterative Algorithms and Renormalization} \label{Sec2} \par In this paper, we will produce a version of Graeffe iteration that has {\em bounded} numerical range, for most input polynomials. The crucial concept in the construction of this algorithm is the idea of {\em renormalization.} \medskip \par Renormalization is a tool used in understanding the qualitative behavior of iterative phenomena that range over different scales. A \oldtext{very}\newtext{}{A6\S 2(1)} rich theory of renormalization exists for one-dimensional dynamical systems. See Feigenbaum~\cite{FEIGENBAUM}, McMullen~\cite{MCMULLEN}, and De Melo-Strien~\cite{MELO_STRIEN}. As for the multi-dimensional case see Palis-Takens~\cite{G_D}. \par \oldtext{ Although we do not want to propose a general theory of renormalization of iterative algorithms, we may illustrate what renormalization means by a well-known example and then give some tentative definitions. } \newtext{We shall illustrate what we mean by renormalization in the setting of iterative algorithms by a well-known example and then proceed with the definitions}{A5(16)} \par \begin{example} Let $f: \mathbb C \rightarrow \mathbb C$ be a smooth function. \oldtext{$\mathbb C \rightarrow \mathbb C$} Newton iteration associates to a point $x$ the point $N(x) = x - f(x) / f'(x)$. The sequence of Newton iterates converges to a zero of $f$, provided that $x$ is picked close enough to a non-degenerate zero. \par We assume now that $f(x) = 0 + f'(0) x + \text{h.o.t.}$ \newtext{}{B\S 4(3)}, and that $f'(0) \ne 0$. We will consider now the renormalization of the {\em iterative algorithm} (or mapping) $x \mapsto N(x)$. Although we are dealing here with a simple example (the answer is always $0$), its renormalization will have some of the main features of the renormalized Graeffe iteration, yet to be defined. \par \oldtext{Therefore, we should} \newtext{The basic idea, therefore, is to}{for clarity} look at Newton iteration with a variable {\em microscope} of variable lens. \oldtext{In our example we are performing Newton iteration $N$ of a univariate polynomial $f$ with a root located at the origin.}\newtext{}{A5(17)} We look at the mapping: \begin{equation} N_{\epsilon} = h_{\epsilon ^{-2}} \circ N \circ h_{\epsilon } \end{equation} where $h_{\epsilon}$ means the homothety of ratio $\epsilon$. \par When $\epsilon$ tends to zero, $N_{\epsilon}$ tends to the map: $y \mapsto \gamma y^2$, defined from the disk $D(|\gamma^{-1}|)$ of radius $|\gamma^{-1}|$ onto itself. Here, $\gamma$ is a parameter chosen equal to \oldtext{$f^{(2)}(0) / f'(0)$} \newtext{$f^{(2)}(0) / 2 f'(0)$}{B\S 4(4)}. (Proof of this fact: Taylor's Theorem. The choice of the radius $|\gamma|^{-1}$ makes the limiting map surjective). \end{example} \par This process (which we call renormalization) gives us qualitative information on the dynamics of Newton iteration near a root. We can summarize this information in an {\em eventually commutative} diagram (commutative in the limit): \oldtext{ \begin{equation} \begin{CD} D(|\gamma^{-1}|\epsilon) @>\left({h_{\epsilon}}\right)^{-1} >> D(|\gamma^{-1}|) \\ @V{N}VV @VV{y \mapsto \gamma y^2}V \\ D(|\gamma^{-1}|\epsilon^{-2}) @>{\left(h_{\epsilon} \right)}^2>> D(|\gamma^{-1}| ) \end{CD} \end{equation}} \newtext{ \begin{equation} \begin{CD} D(|\gamma^{-1}|\epsilon) & \ni & x @>\left({h_{\epsilon}}\right)^{-1} >> y & \in & D(|\gamma^{-1}|) \\ & & @V{N}VV @VV{y \mapsto \gamma y^2}V \\ D(|\gamma^{-1}|\epsilon^{-2}) & \ni & N(x) @>{\left(h_{\epsilon} \right)}^{-2}>> \gamma y^2 & \in & D(|\gamma^{-1}| ) \end{CD} \end{equation}}{A3\S 3(1) and A6\S 1(18)} \par In the example above, the homothety $\left(h_{\epsilon} \right)^{-1}$ is generating the renormalization group. In general, we want to consider renormalizations that lead to a commutative diagram, on the limit: \begin{equation} \begin{CD} y @>R>> R(y)\\ @VGVV @VV{G^R}V \\ G(y) @>>R^2> R^2(G(y)) \end{CD} \end{equation} \par Above, $G$ is the original algorithm (possibly after \oldtext{eventually}\newtext{}{A7(8)} some uniform change of coordinates). We denote by $R$ the renormalization map, and by $G^R$ the renormalized version of our iteration. Usually, $G^R$ depends on a renormalization parameter. However, we want $G^R$ to converge to a limiting map, with a simple dynamics. Moreover, computation of $G^R$ should be `stable', in a \oldtext{very} \newtext{}{A6\S 2(2)} precise sense. \medskip \par This suggests the following heuristics, in the case of Graeffe iteration: we would like to consider a polynomial $f$ represented by its roots. More precisely, a polynomial $f$ can be represented by the vector $(\log |\zeta_i|, \arg(\zeta_i))$ $\in$ $\mathbb R^d \times \mathbb T^d$, where $\zeta_i$ is the $i$-th root of $f$, and $\mathbb T$ denotes the additive group $\mathbb R / 2 \pi \mathbb Z$. In that case, Graeffe iteration is just multiplication by 2. \par Renormalization would be a division by 2 of the log of the radii of the roots. We would have: \oldtext{ \begin{equation} %\label{CDlim} \begin{CD} \mathbb R^d \times \mathbb T^d @>R^k>> \mathbb R^d \times \mathbb T^d \\ @V{\times 2}VV @VV(r,\theta)\mapsto(r,2\theta)V\\ \mathbb R^d \times \mathbb T^d @>>R^{k+1}> \mathbb R^d \times \mathbb T^d \end{CD} \end{equation} } \newtext{ \begin{equation} \label{CDlim} \begin{CD} \mathbb R^d \times \mathbb T^d & \ni & (\log |\zeta_i|, \arg \zeta_i) @>R^k>> (r,\theta) & \in & \mathbb R^d \times \mathbb T^d \\ & & @V{\times 2}VV @VV(r,\theta)\mapsto(r,2\theta)V\\ \mathbb R^d \times \mathbb T^d & \ni & (2 \log |\zeta_i|, 2 \arg \zeta_i \mod 2\pi) @>>R^{k+1}> (r, 2 \theta \mod 2 \pi) & \in & \mathbb R^d \times \mathbb T^d \end{CD} \end{equation} }{A3\S 3(1)} \par Therefore, the limit of the renormalized map should be the map: $(r,\theta) \mapsto (r,2 \theta)$. Of course, we do not know in advance the roots of the polynomial. Instead, we will produce a chain of commutative diagrams `converging' to diagram~(\ref{CDlim}). In order to do that, let us assume that a polynomial \begin{equation} a_0 + a_1 x + a_2 x^2 + \dots + a_d x^d \end{equation} is represented by the vector \newtext{ \begin{equation} (\hat a_i, \alpha_i) = \left( \log \left| a_i \right|, \arg( a_i) \right) \end{equation} }{A6\S 1(19)} \newtext{ In this paper, for clarity of exposition, we will ignore the case where some of the $a_i$ is zero. We can do that because most of our results hold `with probability 1'. In practice, polynomials with a zero coefficient do arise. See Section ~\ref{Sec6} for implementation comments. }{B\S 4(5,6)} \par If the operator $G$ represents Graeffe iteration in this new system of coordinates, we will have: \oldtext{ \begin{equation} % \label{cd} \begin{CD} @VVV @VVV \\ G^k (f) \in \mathbb R^{d+1} \times \mathbb T^{d+1} @>R^k>> (\hat a^k, \alpha^k) \in \mathbb R^{d+1} \times \mathbb T^{d+1} \\ @V{G}VV @VV(G^{R,k})V \\ G^{k+1}(f) \in \mathbb R^{d+1} \times \mathbb T^{d+1} @>>R^{k+1}> (\hat a^{k+1}, \alpha^{k+1}) \in \mathbb R^{d+1} \times \mathbb T^{d+1} \\ @VVV @VVV \end{CD} \end{equation} } \newtext{ \begin{equation} \label{cd} \begin{CD} & & @VVV @VVV \\ \mathbb R^{d+1} \times \mathbb T^{d+1} & \ni & G^k (f) @>R^k>> (\hat a^k, \alpha^k) & \in & \mathbb R^{d+1} \times \mathbb T^{d+1} \\ & & @V{G}VV @VV(G_k)V \\ \mathbb R^{d+1} \times \mathbb T^{d+1} & \ni & G^{k+1}(f) @>>R^{k+1}> (\hat a^{k+1}, \alpha^{k+1}) & \in & \mathbb R^{d+1} \times \mathbb T^{d+1} \\ & & @VVV @VVV \end{CD} \end{equation} }{A3\S 3(1,6)} \newtext{ \par Above, $\hat a^k = (\hat a_0^k, \cdots, \hat a_d^k)$ and $\alpha^k = (\alpha_0^k, \cdots, \alpha_d^k)$. Also, $k$ is a superscript, not an exponent. However, $R^{k}$ denotes the $k$-th iterate of $R$.}{A6\S 1(20)} \medskip \par In this diagram, $R$ maps $(r,\theta)$ into $(r/2, \theta)$. Although this defines \oldtext{$G^{R,k}$} \newtext{$G_k$}{A3\S 3(6)} as a mapping, the algorithmic construction of \oldtext{$G^{R,k}$} \newtext{$G_k$}{A3\S 3(6)} is postponed to Section ~\ref{Sec3}. On the limit, \oldtext{$G^{R,k}$} \newtext{$G_k$}{A3\S 3(6)} `converges' to the mapping: \oldtext{$a, \theta \mapsto a, 2 \theta$} \newtext{$(a, \theta) \mapsto (a, 2 \theta)$}{B\S 4(7)}. This will \oldtext{assure}\newtext{ensure}{A6\S 1(21)} that $\lim \hat a^k$ exists. We will \oldtext{claim}\newtext{show}{A6\S 1(21)} that this limit satisfies \oldtext{(generically)} \newtext{with probability 1}{A3\S 1} \[ \lim_{k \rightarrow \infty} \hat a^k_j - \lim_{k \rightarrow \infty} \hat a^k_{j+1} = \log |\zeta_{d-j}| \] where $\zeta_{d-j}$ is the \oldtext{$d-j$-th} \newtext{$(d-j)$-th}{A7(10)} root of the original polynomial, the roots being ordered by decreasing modulus.. \par Also, by using the renormalized Graeffe iteration \oldtext{$G^{R,k}$} \newtext{$G_k$}{A3\S 3(6)} instead of the classical Graeffe iteration $G$, we will be able to bound all the intermediate calculations to a compact, depending on the input $f$. This will imply several stability results. \medskip \par In order to define formally what we mean by a renormalized algorithm, we need to state the conditions that we expect \oldtext{$G^{R,k}$} \newtext{$G_k$}{A3\S 3(6)} to satisfy. These conditions will define a class of algorithms, that we call renormalized iterative algorithms. Some examples: usual Newton, renormalized Newton, all reasonable algorithms based on a contraction principle and, of course, Renormalized Graeffe Iteration (To be constructed). \medskip \par Before defining what we mean by a renormalized algorithm, we will briefly discuss the notion of algorithm. There are many possible definitions (See Blum, Cucker, Shub and Smale~\cite{BCSS}). \begin{definition} \label{itealg} An iterative algorithm $M$ is a Blum-Shub-Smale (BSS) machine over ${\mathbb R}$, modified as follows: \begin{enumerate} \item If the input is in ${\mathbb R}^{l}\times {\mathbb T}^{m}$ for a pair \oldtext {$(l,k)$} \newtext{$(l,m)$}{A7(11) and B\S 4(8)} , then the output is in ${\mathbb R}^{l}\times {\mathbb T}^{m}$. The integer $l+m$ is called the input size. If the input is denoted by $x$, the output is denoted $M(x)$, and $M^k $ means the composition $M\circ M \circ \cdots $\newtext{$\circ$}{A7(12)}$M$ \newtext{\par Also, we say that the iterative algorithm `computes' the function $x \mapsto \lim_{k \rightarrow \infty} M^k(x)$}{Avoid confusion between iterate and limit.} \item Computation nodes are allowed to perform \newtext{the following}{A4\S 1(1)} elementary functions\oldtext{, i.e.}\newtext{:}{} polynomial evaluation, \newtext{absolute value,}{} (real) logarithms, (real) exponential, sine, cosine, rational functions, and compositions of those. \item $M_{\epsilon}(x)$ will denote the result of approximating $M(x)$ by allowing each operation with non-integer parameters to be performed with relative precision $\epsilon$. (This is also known in numerical analysis as the $(1+\epsilon)$ property.) \newtext{The parameter $\epsilon$ is allowed to vary in $(0, \frac{1}{2})$.} {A4\S 1(2)} The machine is supposed to ``know" $\epsilon$. \newtext{This means that the value of $\epsilon$ can be used in intermediate calculations.} {A4\S 1(2)} Also, the approximation is performed by some prescribed algorithm. (e.g., IEEE arithmetic with $- \log_2 \epsilon$ bits of mantissa). \item \newtext{For all $\epsilon$,}{A4\S 1(2)} the arithmetic complexity of $M$ applied to the input $x$ is the number of \oldtext{arithmetic operations,} elementary function evaluations \newtext{(from the list of item~1)}{A4\S 1(1)} and branchings performed with input $x$. We require the arithmetic complexity of the approximate algorithm \oldtext{ $M_{\epsilon}(x)$ to be the same as the arithmetic complexity of the original algorithm $M(x)$. } \newtext{ $M_{\epsilon}$ applied to the input $x$ to be the same as the arithmetic complexity of the original algorithm $M$ applied to input $x$. }{A3\S 3(3)} \end{enumerate} \end{definition} \begin{remark} Item~1 will allow us to distinguish between real and angular variables, the latter one being defined modulo $2\pi$. This will simplify notation when we speak of the distance between points in ${\mathbb R}^{l}\times {\mathbb T}^{m}$. \newtext{Let $\dist$ be that distance.}{A4\S 1(7)} \end{remark} \newtext{ \begin{remark} It has been argued that the outcome of a branching node would not be well-defined in the presence of numerical error. This is not true in the definition above. The branching nodes of the machine $M$ can be assumed, without loss of generality, to branch on queries of the form $y>0$ or $y \ge 0$ or $y = 0$. When the machine $M$ gets replaced by $M_{\epsilon}$, the branching nodes stay formally the same. The value of $y$, however, is contaminated with a certain numerical error. It is still a perfectly defined real number, and it may be compared to zero. Thus, the branching nodes branch `correctly', for a slightly perturbed input. \par This would lead to disastrous results if an approximate machine enters a `loop' due to numerical errors. Item 4 in the definition above is there to preclude that sort of loop, by ensuring that the arithmetic complexity of each iteration does not depend on the working precision. \oldtext{ This is the case for all iterative algorithms that the authors know about.} \end{remark}}{A4\S 1(3) and B\S 2(3,4)} \newtext{ \begin{definition} A function $\varphi$ can be computed in {\em finite time} if and only if there is a BSS machine over $\mathbb R$ modified as above items 2, 3 and 4, that computes $\varphi$. \end{definition} }{Define the notion finite time precisley.} One consequence of the previous definition is the following: suppose a certain function $\varphi$ can be computed in finite time. Then, its branching set is given by a finite set of equations. Outside the branching set, $\varphi$ can be written (locally) as a composition of elementary functions. Moreover, only a finite number of such compositions may appear, one corresponding to each set of possible branchings. \medskip \par A few definitions \oldtext{that will be used in the sequel } are in order now. In the sequel we will need to use algorithms depending effectively on a parameter $k \in \mathbb N$. \oldtext{ Let $M$ be an iterative algorithm, with input $(f,k)$, where the parameter $k$ will keep track of iterations. We write $M_{k}(f)=M(f,k)$.} \newtext{ Those will be given by a machine $M$ with two inputs, say $k$ and $f$. However, we will denote the output as $M_k(f)$ and we will write $M_k$ for each of the input-output mappings obtained by restricting that machine to some fixed value of $k$. Also, in that situation we will speak explicitly of the algorithm $(M_k)_{k \in \mathbb N}$ or $M_k$ for short. \par }{A4\S 1(5)} \par The sequence $\left( M_{k} \right)_{k=1}^{\infty}$ can be considered \newtext{as a sequence of mappings}{Syntax.} from $\RT{l}{m}$ into itself. The orbit of $f$ by the sequence $\left( M_{k} \right)_{k=1}^{\infty}$ is the set \[ \orb f \bydef \left( f, M_{1}(f),M_{2}\circ M_{1}(f),\dots \right) \subset \RT{l}{m} \mbox{ .} \] This set should be understood as the orbit of $f$ by the non-autonomous dynamical system $M_k$ (Not the semi-group !) The closure of $\orb f$ will be denoted by $\overline{\orb f}$. We shall say that a subset of $\RT{l}{m}$ \oldtext{is generic} \newtext{has full-measure}{A3\S 1} if its complement is contained in a set of null measure. \newtext{We say that some property is true almost everywhere (a.e.) if that property is true in a full-measure set.}{} We can now define a {\em renormalized algorithm} and make precise our concept of renormalization: \begin{definition} \label{defren2} The algorithm \newtext{$(M_k)_{k \in \mathbb N}$ (or $M_k$ for short)}{A4\S 1(5)}\oldtext{$M_k$} is said to be a {\em renormalized iterative algorithm to compute} \oldtext{$\varphi(f): \RT{l}{m} \rightarrow {\mathbb R}^{s}$} \newtext{$\varphi : \RT{l}{m} \rightarrow {\mathbb R}^{s}$, $f \mapsto \varphi(f)$}{A3\S 3(4)}, where $0\le s \le l$, if, and only if, it satisfies the Axioms 1 through 4 below. \end{definition} \begin{axiom}[Consistency] % Axiom 1 For almost every $f\in {\mathbb R}^{l} \times {\mathbb T}^m$ we have \oldtext{ \[ \lim_{k\rightarrow \infty} \pi \circ M_{k}\circ M_{k-1}\circ \cdots \circ M_{1}(f) = \varphi(f) \] } \newtext{ \[ \lim_{k\rightarrow \infty} \left( \pi \circ M_{k}\circ M_{k-1}\circ \cdots \circ M_{1} \right)(f) = \varphi(f) \]}{A3\S 3(5)} where $\pi$ is the projection of $\RT{l}{m}$ onto the first $s$ coordinates of ${\mathbb R}^{l}$. \end{axiom} \begin{axiom}[Arithmetic Complexity] % Axiom 2 The arithmetic complexity of \oldtext{$M_{k}(f)$} \newtext{$M_k$ with input $f$}{A3\S 3(4)} is bounded in terms of the size \newtext{$l+m$}{Clarity.} of $f$, independently of $k$ and the coefficients of $f$. \end{axiom} \begin{axiom}[Propagation] % Axiom 3 For \oldtext{generic $f\in \RT{l}{m}$ } \newtext{almost every $f \in \RT{l}{m}$,}{A3\S 1} there exists a compact neighborhood $V \subset \RT{l}{m}$ of $\orb f$ (under $\{ M_{k} \}$) and \oldtext{$C \ge 1$}\newtext{C}{A4\S 1(6)} such that $M_{k}|_{V}$ is \smthg % with constant $C_{k}$ and eventually $C_{k}0$} we have that \newtext{for sufficiently small $\epsilon>0$}{} \[ \dist \left( M_{k,\epsilon} \circ \cdots \circ M_{1,\epsilon} (f) , M_{k} \circ \cdots \circ M_{1} (f) \right) < k A^k B \epsilon \mbox{ . } \] \newtext{Here, $A$ and $B$, depend on $f$, but not on $k$.}{} \oldtext{Moreover, one can take} \newtext{In particular, that will be true for values of $\epsilon$ of the form}{} \[ \epsilon \le \frac{\rho}{kA^kB} \mbox{ ,} \] where $\rho$ is defined below. \end{lemma} As an immediate consequence of Lemma~\ref{lemE} we have that \[ \| \left( \pi \circ M_{k,\epsilon} \circ \cdots \circ M_{1,\epsilon} )(f) - ( \pi \circ M_{k} \circ \cdots \circ M_{1} )(f) \right) \|_2 < k A^k B \epsilon \mbox{ .} \] \begin{proof}[Proof of Lemma~\ref{lemE}] We now describe the construction of the constants in the statement of Lemma~\ref{lemE}. Combining Axioms 3 and 4, there exists a compact neighborhood $W$ of $\orb f$ such that: \begin{enumerate} \item Every mapping $M_{k}$ is Lipschitz on $W$. Moreover, there exists a constant $A$ such that for every $k$, the norm of the Lipschitz constant of $M_{k}$ is uniformly bounded by \oldtext{$A = \sup C_k$} \newtext{$A = \max \left( 1, \sup_k C_k \right)$,}{A4\S 1(6)} $C_k$ as in Axiom~3. \item \oldtext{For $g\in W$, there exists} \newtext{There exists}{A3\S 2(1)} $\epsilon_{0}$ such that $\forall \epsilon < \epsilon_{0}$ we have \[ {\dist}(M_{k,\epsilon}(g),M_{k}(g)) < \epsilon B \mbox{ ,} \hspace{1cm} \forall g \in W \mbox{ .} \] We then define $\rho$ as the minimum of $\epsilon_{0}$ and the distance of $\orb f$ to the boundary of $W$. \end{enumerate} We may now conclude the proof of Lemma~\ref{lemE}. Set \[ g=(M_{k-1}\circ \dots \circ M_{1})(f) \mbox{ ,} \] and \[ h=(M_{k-1,\epsilon} \circ \dots \circ M_{1,\epsilon})(f) \mbox{ .} \] In that case, we want to bound \[ \dist(M_{k,\epsilon}(h),M_{k}(g)) \le \dist (M_{k,\epsilon}(h),M_{k}(h)) + \dist(M_{k}(h),M_{k}(g)) \] If $h\in W$, one can bound \[ \dist(M_{k}(h),M_{k,\epsilon}(h)) \le B\epsilon \] and \[ \dist(M_{k}(h),M_{k}(g)) \le A \ \dist(g,h) \mbox{ .} \] By induction, \[ \dist(g,h) \le (k-1) A^{k-1} B \epsilon \mbox{ ,} \] and hence \[ \dist(M_{k,\epsilon} (h), M_{k}(g) )\le k A^{k} B \epsilon \mbox{ .} \] The condition \[ \epsilon < \frac{\rho}{k A^{k} B} \] guarantees that $h \in W$. \end{proof} \medskip \par If we use a Turing machine model (or any other classical discrete complexity model), we can perform all the operations of $M$ in finite precision, and obtain: \begin{lemma} \label{lemT} Let $M$ be a renormalized iterative algorithm. \oldtext{ Fix a generic} \newtext{For almost every $f$, assume that the truncation error is bounded by}{A3\S 1} \oldtext{ \[ \| \pi \left( M_{k} \circ \cdots \circ M_{1} \right) (f) - \varphi(f) \|_2 \] } \newtext{ \[ \| \left( \pi \circ M_{k} \circ \cdots \circ M_{1} \right) (f) - \varphi(f) \|_2 < E^{2^{k}} \mbox{ ,} \] where $ E = E(f) \in (0,1) $.}{A3\S 3(5)} \oldtext{ is bounded by $E^{2^{k}}$} Then, the \oldtext{Turing} complexity of approximating $\varphi(f)$ with precision $\delta$ is $\bigo((\log_{2} \frac{1}{\delta})^{1+\alpha})$ where $\alpha > 0 $ is arbitrarily \newtext{ small.}{} \end{lemma} \newtext{ It is assumed above that the cost of arithmetic with $l$ bits of mantissa is $O(l^{1+\alpha})$, for all $\alpha > 0$. See~\cite{BP} pp~78-79 for a sharper bound on the complexity of long integer multiplication.}{A6\S 1(22)} \begin{proof}[Proof of Lemma~\ref{lemT}] \par Let \[ k = \left\lceil \log_2 \frac{-\log_2 \frac{\delta}{2}}{-\log_2 E} \right\rceil \mbox{ ,} \] so that \[ E^{2^k} \le \frac{\delta}{2} \mbox{ .} \] Choose $\epsilon$ so that Lemma~\ref{lemE} holds, i.e., $\epsilon < \rho/k A^k B$, and such that $k A^k B \epsilon < \delta/2$. This can be done for \oldtext{ \[ \epsilon \in \littleo \left( \frac{\delta}{\log_2 \log_2 \delta^{-1} (\log_2 \delta^{-1})^ {\log_2 A}} \right) \subset \littleo (\delta^{1 + \alpha}) \] } \newtext{ \[ \epsilon < c_1 \delta (\log \delta^{-1})^{c_2} \] for some constants $c_1$ and $c_2$ dependent of $f$. }{} The total cost of computing $M_k$ is $\bigo \left( a (\log_2 \epsilon^{-1})^{1 + \alpha} \right)$, where $a$ is the arithmetic complexity of the algorithm and $\alpha$ is arbitrarily small. \oldtext{Hence,} \newtext{Since $f$ is fixed, $a$ is a constant and $k < \log_2 \log_2 \delta^{-1}$}{} the total cost is \[ \bigo \left( (\log_2 \delta^{-1})^{1+\alpha}\right) \] \newtext{for all $\alpha$ arbitrarily small.}{} \end{proof} \medskip \par The complexity bound of Lemma~\ref{lemT} is non-uniform in $f$. It is also non-effective, in the sense that we give no procedure to estimate $k$ and \oldtext{$m$}\newtext{$\epsilon$}{} without the knowledge of $\rho$, $B$ and $A$. Indeed, those quantities may depend on $f$. It \newtext{would be of some interest}{} to bound those quantities in a probabilistic setting, similar to Theorem~\ref{th2}. \begin{definition} Let $M$ be an iterative algorithm to compute \oldtext{$\Phi(F)$} \newtext{$\Phi: F \mapsto \Phi(F)$,}{A3\S 3(4)} \newtext{i.e., $\lim_{n \rightarrow \infty} M^n(F) = \Phi(F)$). }{A4\S1 (8)} We say that $M_k$ is a renormalization of $M$ if \begin{enumerate} \item $M_k$ is a renormalized iterative algorithm to compute $\varphi(f)$. \item There are functions $\psi$ and $\eta$, defined almost everywhere and computable in finite time, such that the diagram \[ \begin{CD} F @>\psi>> \psi(F) \\ @V{\Phi}VV @VV{\varphi}V\\ \Phi(F) @<\eta<< \varphi(\psi(F)) \end{CD} \] commutes. \item There is a function $R$, computable in finite time, so that the diagrams: \[ \begin{CD} F @>R^k \circ \psi>> R^k(\psi(F)) \\ @V{M}VV @VV{M_k}V \\ M(F) @>R^{k+1} \circ \psi>> R^{k+1}(\psi(M(F))) \\ \end{CD} \] commute. \end{enumerate} \end{definition} Theorem~\ref{th1} can be stated now in a more concise way: Let \oldtext{$z(f)$}\newtext{$\zz: f \mapsto \zz(f)$}{A3\S 3(4)} be the function that associates, to any univariate degree $d$ polynomial $f$, its roots $\zeta_1 , \dots , \zeta_d$ ordered by decreasing modulus. We have the following: \begin{theoquo} There is \oldtext{(we construct)} a renormalization of the Graeffe iteration to compute $|\zeta(f)|=\left( |\zeta_1(f)|, \dots, |\zeta_d(f)|\right)$. Each iteration has arithmetic complexity $\bigo(d^2)$ and needs memory $\bigo(d)$. \end{theoquo} \section{Recurrence Relations and the Renormalization of Graeffe} \label{Sec3} It is time to construct the renormalized Graeffe \oldtext{operator} \newtext{iteration}{A7(3)}. Let $f(x) = f_0 + f_1 x + \dots + f_d x^d$. Let $h = Gf$ be its Graeffe iterate. The coefficients of $h$ can be written as~: \begin{equation} \label{g1} h_i = (-1)^d \sum _{\substack{ 0\le i-j \le d \\ 0\le i+j \le d \\ }} (-1)^{i-j} f_{i-j} f_{i+j} \end{equation} \par For convenience, we rewrite (\ref{g1}) as: \begin{equation} \label{g2} h_i = (-1)^{d+i} {f_{i}}^2 + 2 \sum _{ 1\le j \le \min(i,d-i)} (-1)^{d+i-j} f_{i-j} f_{i+j} \end{equation} \medskip \par The next step is to write those equations in terms of the log of the coefficients. More precisely, we will have to deal with the following two quantities: \begin{equation} \label{g7} f^{\log}_i \bydef \log \left| f_i \right| \end{equation} \begin{equation} \label{g8} f^{\arg}_i \bydef \arg f_i \end{equation} \medskip \par It is possible now to construct the renormalized Graeffe \oldtext{operator} \newtext{iteration}{A7(3)} \oldtext{$G^{R,k}$} \newtext{$G_k$}{A3\S 3(6)}. Recall from diagram (\ref{cd}) that this \oldtext{operator} \newtext{iteration}{A7(3)} will map $2^{-k} f^{\log}$ and $f^{\arg}$ into $2^{-k-1} h^{\log}$ and $h^{\arg}$. \par For that purpose, we introduce the notation: \par %JPZ \centerline{ %JPZ \begin{tabular}{ll} %JPZ $f^{k}$ & ($2^{-k} f^{\log},f^{\arg})$ \\ %JPZ $h^{k+1}$ & ($2^{-k-1} h^{\log},h^{\arg})$ \\ %JPZ $c^{k+1}$ & ($2^{-k-1} c^{\log},c^{\arg})$ %JPZ \end{tabular} %JPZ } \begin{equation} \label{defren} \left\{ \begin{array}{lll} f^{k} & \bydef & (2^{-k} f^{\log},f^{\arg}) \\ h^{k+1} & \bydef & (2^{-k-1} h^{\log},h^{\arg}) \\ \end{array} \right. \end{equation} We also introduce operators: \begin{eqnarray} (x,\alpha) \rentimes{k} (y, \beta) &\bydef& (x + y, \alpha + \beta) \\ (x,\alpha) \renpow{k}{\lambda} &\bydef& (\lambda x , \lambda \alpha) \\ \renscal{k}{z} (x,\alpha) &\bydef& (x + 2^{-k} \log |z|, \alpha + \arg z) \end{eqnarray} and \begin{small} \begin{eqnarray} (x,\alpha) \renplus{k} (y, \beta) &\bydef& \left( 2^{-k} \log \left| e^{i \alpha + 2^k x} + e^{i \beta + 2^k y} \right| , \arg \left( e^{i \alpha + 2^k x} + e^{i \beta + 2^k y} \right) \right) \label{deflast} \end{eqnarray} \end{small}\newtext{}{A6\S 1(24) Added parenthesis} \par We remark that the purpose of the sub-index $k$ in the above formulae is to keep track of the degree of the renormalization. For operations which do not change, we omitted the sub-index. \newtext{The operator $\renscal{k}{z}$ stands for the multiplication of a renormalized value by a (non-renormalized) constant $z$}{A6\S 1(23)} \par Also, binary renormalized operations are defined for operands with the same renormalization index. Therefore, one should first convert $f_i^k$ to $f_i^{k+1}$ before attempting to \oldtext{to}\newtext{}{B\S 4(9)} `multiply' it with a factor of renormalization index of order $k+1$. This conversion will be implicit in the formulae below. \par Equation~(\ref{g2}) becomes: \begin{small} \begin{equation} \label{g666} {h_i}^{k+1} = \left( \renscal{k+1}{ s_{i0}} \left({f_i}^k \right) \renpow{k+1}{2} \right) \renplus{k+1} \left( \renscal{k+1}{2} % {\substack {{\bigrenplus{k+1}}\\ % \text{\scriptsize $1 \le j \le \min(i, d-i)$} \\}} \overset{\min(i, d-i)}{\underset{j=1}{\ \ \ \ \bigrenplus{k+1}} } \left( \renscal{k+1}{s_{ij}} {f_{i-j}}^k \rentimes{k+1} {f_{i+j}}^k \right) \right) \mbox{ ,} \end{equation} \end{small} where $s_{ij}= (-1)^{d+i-j}$. \newtext{Recall that above, $k$ is a superscript, not an exponent.}{A6\S 2(3)} The `renormalized operations' above are \oldtext{very} \newtext{}{A6\S 2(1)} easy to implement in terms of the classical ones. The most delicate being the renormalized sum, so we give here our preferred algorithm \begin{example} \label{ex2} How to compute the `Renormalized sum': \[ (c,\gamma) := (a,\alpha) \renplus{k} (b,\beta) \]\newtext{}{A7(13)} \begin{tt} \begin{tabbing} \ \ \ \ \= \\ \> If $a > b$, \= do: \\ \> \>$ s = \exp{i\alpha} + \exp{ (i \beta + 2^{k} (b-a)) } $ \\ \> \>$ c = a + 2^{-k} \ln |s| $ \\ \> \>$ \gamma = \arg(s) $ \\ \> else \\ \> \> $ s = \exp{i\beta} + \exp{ (i \alpha + 2^{k} (a-b)) }$ \\ \> \>$ c = b + 2^{-k} \ln |s| $ \\ \> \>$ \gamma = \arg(s) $ \\ \> endif\\ \end{tabbing} \end{tt} \end{example} \oldtext{$ c = a + 2^{-k} \ln |s| $} We remark that in the above formula, the complex arithmetic operations can be performed in terms of real elementary ones. Moreover, in numerical implementations if $k$ is large enough, as compared to $\epsilon$, it may be faster to approximate $(c,\gamma)$ with $(a,\alpha)$ \newtext{or $(b,\beta)$, whichever is larger}{A7(14)}. \medskip \par In order to finish the proof of Theorem~\ref{th1}, we still need a few remarks about the renormalized Graeffe \oldtext{operator} \newtext{iteration, which}{A7(3)} we just constructed. Clearly, in order to compute formula~(\ref{g666}), we only need memory space of the order $\bigo(d)$ \newtext{and time of the order $\bigo(d^2)$}{A6\S 1(25)}. \par When $k \rightarrow \infty$, the quantities $|f^k_{i}|$ are all convergent. \medskip \par If $G_k$ is the renormalized Graeffe iteration, we define $G_{\infty}$ as the limit of $G_k$ when $k$ goes to infinity. This means that renormalized sums $\renplus{k}$ are replaced by their limit $\renplus{\infty}$, where: \[ (a, \alpha) \renplus{\infty} (b, \beta) = \left\{ \begin{array}{ll} (a, \alpha) & \text{if } a>b \\ (b, \beta) & \text{if } a 0$.} \newtext{ For almost every $f$ and any $\delta>0$,}{A3\S 1} there exist a compact neighborhood $W \subseteq \mathbb R^l \times \mathbb T^m$ of $\text{orb} (f)$ and an integer $k_0$ such that, $G_k$ is a local diffeomorphism $W \rightarrow G_k(W)$, and such that for $k_0 \le k \le \infty$, the derivative of $G_k$ is bounded by $2+\delta$ } \begin{proof}[Proof of Lemma~\ref{technical}] The proof is divided in several steps. \begin{itemize} \item [Step 1:]For any $j \in \mathbb N$, there is a \oldtext{generic} \newtext{full-measure set}{A3\S 1} $U_j$ such that $G_j \circ \cdots \circ G_1$ is well-defined, and a local diffeomorphism in $U_j$. Hence, there is a \oldtext{generic} \newtext{full-measure set}{A3\S 1} $U_{j,k}$ such that \oldtext{ $G_k$ is well-defined and a local diffeomorphism near $G_j \circ \cdots \circ G_1 (f)$.} \newtext{$G_k \circ \left( G_j \circ \cdots \circ G_1 \right)$ is defined on $U_{j,k}$ and for all $f \in U_{j,k}$ there is a neighborhood $V_f$ of $G_j \circ \cdots \circ G_1 (f)$ such that $G_k$ is a diffeomorphism $V_f \rightarrow G_k(V_f)$.} {A3\S 2(2)} \item [Step 2:]Let $U_{\infty}$ be the set of all $f$ such that \oldtext{ $G_k(f)$ is a local diffeomorphism in $(\pi ^{-1} \circ \varphi) (f)$, for $k$ large enough.} \newtext{$G_k$ is a diffeomorphism near $(\pi ^{-1} \circ \varphi) (f)$ for all values of $k$ that are large enough.}{A4\S 1(9)} Then $U_\infty$ contains the set of complex polynomials without roots of the same modulus. Hence $U_\infty$ \oldtext{is generic.} \newtext{has full measure.}{A3\S 1} \item [Step 3:]Let $U = U_\infty \cap \left( \bigcap_j U_j \right) \cap \left( \bigcap_{jk} U_{jk} \right)$. Then $U$ \oldtext{is generic.} \newtext{has full measure}{A3\S 1}. Moreover, let $f \in U$. Then $G_k$ is a local diffeomorphism with derivative \newtext{of norm} {This is more precise.} $< 2+\delta / 2$ in an open neighborhood $V_k(g)$ of every $g \in \overline{\text{orb} f}$, for all $k \ge k_0 (g)$. \newtext{Indeed, if we write $G_k = G_{\infty} + \left( G_k - G_{\infty} \right)$, we can make the $C^1$ norm of the second term arbitrarily small, namely less than $\delta /2$. We know that the norm of the derivative of $G_{\infty}$ is precisely 2, hence the bound $2+\delta / 2$ }{A4\S 2(1)} In the particular case $\delta = \infty$ we can set $k_0 = 1$. \item [Step 4:]Since $G_k \rightarrow G_{\infty}$ \oldtext{in a locally $C^1$ sense}\newtext{pointwise in the $C^1$ topology and }{A4\S 2(2)} for $g$ almost everywhere, we can assume that $\bigcap_{k \ge k_0} V_k(g)$ contains an open ball $V(g)$ of center $g$, where $G_k$ is a local diffeomorphism with derivative bounded by $2+\delta / 2$. \item [Step 5:]Since $\overline {\text{orb}(f)}$ is compact, the union $\bigcup_{g \in \overline{\text{orb}(f)}} V(g)$ has a finite sub-cover $\bigcup_{g \in \Gamma} V(g)$, and we set $W = \bigcup_{g \in \Gamma} \overline{V(g)}$. Then we set $k_0 = \max_{g \in \Gamma} k_0(g)$, and we obtain that for any $k \ge k_0$, $G_k$ is a local diffeomorphism in $W$, with derivative of norm bounded by $2 + \delta$. \end{itemize} \end{proof} \medskip \par The proof that our algorithm satisfies Axiom 4 is divided in two parts \newtext{, dealing (respectively) with small and large values of $k$} {For clarity.}. \oldtext{ \begin{lemma*} % \label{lp1} For a.e. $g$ given, $|G_{k,\epsilon}(g) - G_{k}(g) | < B \epsilon$, where $B$ depends on $g$ and $k$, and $\epsilon$ is small enough. \end{lemma*} \begin{lemma*} % \marginpar{This Lemma and its proof need to be rewritten.} % \label{lp2} For a.e. $g$ given, there is $k_0$ such that for any $k > k_0$ \[ \dist \left(G_{k,\epsilon}(g) , G_{k}(g) \right) < B \epsilon \] where $B$ depends on $\varphi(g)$ only. \end{lemma*} } \newtext{ \begin{lemma} \label{lp1} For almost every $f$ and for all $k$, there exist an open neighborhood $U$ containing $f$ and $B>0$ such that for all $g \in U$ and for all $\epsilon$ small enough \[ \dist \left(G_{k,\epsilon}(g) - G_{k}(g) \right) < B \epsilon \mbox{ .} \] \end{lemma} \begin{lemma} \label{lp2} For almost every $f$, there exist $k_0$, $B>0$, and an open neighborhood $U$ containing $f$, such that for all $g \in U$ and $k \ge k_0$, for all $\epsilon$ small enough, \oldtext{ \[ |G_{k,\epsilon}(g) - G_{k}(g) | < B \epsilon \] For a.e. $g$ given, there is $k_0$ such that for any $k > k_0$ } \[ \dist \left(G_{k,\epsilon}(g) , G_{k}(g) \right) < B \epsilon \] \end{lemma} }{Restated for clarity and also A3\S 3(7).} \medskip \par \oldtext{Since $G_k$ is an almost everywhere local diffeomorphism, and hence the preimage of a zero measure set has zero measure,} Lemmas~\ref{lp1} and \ref{lp2} together imply that for almost all \oldtext{$g$} \newtext{$f$, there is a neighborhood $U$ containing $f$ such that for all $g \in U$}{}, \[ \dist \left( G_{k,\epsilon}(g) , G_{k}(g) \right) < B \epsilon \] independently of $k$. \par \oldtext{ This result can be extended to an open neighborhood of any $g$ generic.} Since \oldtext{(generically)} $\text{orb}(f)$ is defined \newtext{for almost every $f$}{A3\S 1} and admits a compact neighborhood $V$, we can select a finite subcover of those neighborhoods, and hence find a finite $B$ valid for all $g \in V$. Therefore, our algorithm satisfies Axiom 4. \medskip \par \begin{proof}[Proof of Lemma~\ref{lp1}:] Our iteration $G_k$ can be written in terms of the following real operations: $+$, $-$, $\cos$, $\sin$, $\arctan$, multiplication by $2^k$, by $2^{-k}$, absolute value, $\exp$, $\log$. \par The set of inputs such that a `log of zero' or an `absolute value of zero' occurs has zero measure. \oldtext{Therefore, if $g$ is generic,} \newtext{Therefore, for almost every $f$,}{A3\S 1} $G_k(f)$ is computed by a composition of analytic functions. Also, \oldtext{if $g$ is generic} \newtext{for almost every $f$,}{A3\S 1} none of the output values is zero. \par Therefore, for every intermediate quantity $x_l$, the derivative of any output $y_m$ with respect to $x_l$ is finite (say $\le D_{lm}$). \oldtext{ Therefore, a relative perturbation of $\epsilon$ in $x$ leads to a perturbation of $xD\epsilon$ in $y$. Thus, we set $B = \sum D_{lm}x_l$ and we are done. } \newtext{ Therefore, a relative perturbation of $\epsilon$ in $x_l$ leads to a perturbation of size $|x_l| D_{lm}\epsilon$ in $y_m$. Thus, we set $B = \frac{1}{2} \sum_{l,m} D_{lm}|x_l|$. By continuity, a perturbation of $\epsilon$ in each intermediate value $x_l$ leads to a perturbation smaller than $B \epsilon$, for input $g$ in a certain neighborhood of $f$. }{A6\S 1(27)} \end{proof} \medskip \par \begin{proof}[Proof of Lemma~\ref{lp2}:] \oldtext{ We claim that there is a full-measure set $W$ such that if $\varphi(g) \in W$, then there are $k_0$ and $B$ such that \[ \dist \left( G_{k,\epsilon}(g) , G_{k}(g) \right) < B \epsilon \] for $k > k_0$. Since $\varphi ^{-1}$ maps zero measure sets into zero measure sets, Lemma~\ref{lp2} will be true in the full-measure set $\varphi^{-1}(W) \cap W'$. where $W'$ is the set of $g$ such that $G_k \circ \dots \circ G_1 \rightarrow \varphi(g)$. According to Axiom 1, the set $W'$ has full measure. } \newtext{ Let $W$ be the set of all $f$ such that $G_{\infty}(f)$ is well-defined. Recall that \[ \begin{array}{lccll} \renplus{\infty} : & (a,\alpha), (b,\beta) & \mapsto & (a,\alpha) & \text{if } a>b \\ &&& (b,\beta) & \text{if } b>a \end{array} \] and that the operator $\renplus{\infty}$ is not defined for $a=b$. Therefore, $W$ is open and has full measure.}{Clarity.} \oldtext{ \par In order to prove our claim, we consider the `limit' iteration $G_{\infty}$, where $\renplus{k}$ was replaced by $\renplus{\infty}$: \[ \begin{array}{lccll} \renplus{\infty} : & (a,\alpha), (b,\beta) & \mapsto & (a,\alpha) & \text{if } a>b \\ &&& (b,\beta) & \text{if } b>a \end{array} \] \par The operator $\renplus{\infty}$ is not defined for $a=b$. In the same way, we replace all the other renormalized operators by their limit values. Wherever defined, $G_{\infty}$ fixes scalar quantities, and doubles angles. \par Let $W$ be the domain of definition of $G_{\infty}$. Clearly, $W$ is open and has full measure.} \newtext{ Let $f \in W$ and $U$ be a small connected neighborhood containing $f$. Let $g \in U$, then by taking $U$ small enough and $k$ large enough, we can guarantee that $G_k(g)$ and $G_{k,\epsilon}(g)$ are well-defined. Since $U$ is connected, all the branching outcomes in the computation of $G_k(g)$ and $G_{k,\epsilon}$ are the same, hence $G_k$ restricted to $U$ is a composition of locally analytic functions. We can assume without loss of generality that all derivatives are bounded, hence there is a constant $B$ such that \[ \dist \left(G_{k,\epsilon}(g) , G_{k}(g) \right) < B \epsilon \] for $\epsilon$ small enough, but still independent of the choice of $g$. }{Fixes A3\S 3(7). The following remarks are no more relevant: A3\S 3(8), A6\S 1(28), A6\S 1(30), A3\S 2(3)} \oldtext{ For $y \in W$, there is $k$ such that every operation $\renplus{k}$ can be replaced by $\renplus{\infty}$, with relative error $\epsilon$. Indeed, for $k$ large enough, \[ s = \left| 1 + e^{i(\beta - \alpha) + 2^k (b-a)} \right| \ , \ a > b \] is bounded away from zero, so that $2^{-k} \log s$ can be made smaller than $|a| \epsilon$. The error in the angle may be estimated the same way. \par This last property holds in an open neighborhood $U$ of $y$, $U \subset W$. Once we take $k > k_0$, with $k_0$ large enough, $(G_k \circ \dots \circ G_1) (f) \in U$. Since all of our operators $\renplus{k}$ and $\rentimes{k}$ are locally Lipschitz in $W$, there is $B$ s.t. for $\epsilon$ small enough, for all $z \in U$, $\| G_{k \epsilon}(z) - G_k(z) \|$ is uniformly bounded by $B \epsilon$} \end{proof} \medskip \par \oldtext{ \begin{proof}[End of the proof of Theorem~\ref{th1}:] We define: \begin{eqnarray*} \psi(f_0, \cdots, f_d) &=& \left( \log|f_0|, \cdots, \log|f_d| ; \arg|f_0|, \cdots, \arg|f_d| \right) \\ \eta(r_0, \cdots, r_d ; a_0, \cdots, a_d) &=& \left( \exp {(r_0-r_1)}, \cdots, \exp {(r_{d-1} - r_d)} \right) \\ R(r_0, \cdots, r_d ; a_0, \cdots, a_d) &=& \left( \frac{r_0}{2}, \cdots, \frac{r_d}{2} ; a_0, \cdots, a_d \right) \\ \end{eqnarray*} \medskip \par We define $\Phi$ as the function that associates to a polynomial $f$ the values $|\zeta_1|, \dots, |zeta_d|$ where $\zeta_i$ are the roots of $f$, ordered by decreasing modulus. \par Then we set \[ \varphi = \eta^{-1} \circ \Phi \circ \psi^{-1} \] \medskip \par With the definitions above, $G^{R,k}$ is indeed a renormalization of the classical Graeffe algorithm to compute $\Phi$. \end{proof} } \newtext{This concludes the proof of Proposition~\ref{prop1} and hence of Theorem~\ref{th1}}{A6\S 1(26)} \section{Probability of Success} \label{Sec5} \oldtext{MOST OF THIS SECTION WAS REWRITTEN FROM SCRATCH} Through this section, $\|.\|_d$ will denote Weyl's unitary invariant norm (\cite{WEYL} ~III--7, pp~137--140) in the space $\mathcal P_d$ of complex polynomials of degree at most $d$ (See~\cite{BCSS}). If $f(x) = \sum_{i=0}^d f_i x^i$, then \[ \| f \|_d = \sqrt{ \sum_{i=0}^d \frac{|f_i|}{\binomial{d}{i}}} \] \par This norm is invariant under the following action of the group $U(2)$ of unitary $2\times 2$ matrices: if $\varphi = \left[ \begin{array}{cc} \alpha & \beta \\ \gamma & \delta \end{array} \right]$ is unitary, define \[ f^{\varphi} (y) = (\gamma y + \delta)^d f\left( \frac{\alpha y + \beta} {\gamma y + \delta} \right) \] Thus, $\| f^{\varphi} \|_d = \| f \|$. (See Ch.~12, Th.~1 of \cite{BCSS}.) This is in some sense the most `natural' norm in the space of all polynomials. \newtext{More information about that norm, its associated probability distribution and its applications can be found in}{A5(14)} \cite{BD,DEDIEU2,DEDIEU3,KOSTLAN,TCS,SPLITTING,BEZI,BEZII,BEZIII, BEZIV, BEZV}. Let $\mathbb P \mathcal P_d$ be the projectivization of normed complex vector space $(\mathcal P_d, \|.\|_d)$. We can define the `sine' distance in $\mathbb P \mathcal P_d$ by: \[ d_{\mathbb P} (f,g) = \min_{\lambda \in \mathbb C} \frac{\|f - \lambda g\|} {\|f\|} = \sin \varrho(f,g) \] where $\varrho$ is the usual Riemann metric in $\mathbb P \mathcal P_d$. Also, there is a natural volume form in $\mathbb P \mathcal P_d$. Normal invariant distributed polynomials in $\mathcal P_d$ correspond to uniformly distributed `polynomials' in $\mathbb P \mathcal P_d$. Let $f$ be a random polynomial (in any of the two equivalent senses above). Then we may consider its roots $\zeta_1, \cdots, \zeta_d$ as random variables. The joint distribution of $\zeta_1, \cdots, \zeta_d$ was studied by Kostlan in ~\cite{KOSTLAN}. However, the result below will rely on elementary estimates: \begin{lemma} \label{lem6} Let $f$ be random in the sense above. The probability that \[ \min_{|\zeta_i|>|\zeta_j|} \frac{|\zeta_i|}{|\zeta_j|} > 1+\epsilon \] is larger than $1-M \epsilon$, where $M$ is a positive constant depending on $d$. \end{lemma} This result is also true if we chose $f$ random with respect to any other probability distribution \oldtext{ that is absolutely continuous with respect to the volume form of $\mathbb P \mathcal P_d$.} \newtext{with bounded Radon-Nikodym derivative with respect to the volume form in $\mathbb P \mathcal P_d$.}{Precise definition.} The constant $M$ will have to be multiplied by the maximum of the Radon-Nikodym derivative of the new distribution with respect to the volume form. Lemma~\ref{lem6} will be a consequence of the `Condition Number Theorem' below. Let \[ \rho(f) = \min_{|\zeta_i| < |\zeta_j|} 1 - \frac{|\zeta_i|}{|\zeta_j|} \] We will interpret $\rho(f)^{-1}$ as a condition number. Let $\Sigma_G$ be the locus of ill-posed problems, i.e., the set of polynomials such that $|\zeta_i| = |\zeta_j|$ for some $i \ne j$. Then, \begin{theorem}[Condition Number Theorem for Graeffe Iteration]\label{cnt} \[ \rho(f) \ge \frac{ d_{\mathbb P} (f, \Sigma_G) }{\sqrt{d}} \] \end{theorem} Therefore, the probability that $\rho(f)>\epsilon$ is no less than $1 - \vol V_{\epsilon \sqrt{d}} \Sigma_G$ where $V_{\epsilon \sqrt{d}}$ denotes an $\epsilon \sqrt{d}$-neighborhood. This volume is of $O(\epsilon \sqrt{d} ) \le M \epsilon$. \begin{lemma}\label {norms1} Let $f(x) = (x-\zeta_1) g(x) \in \mathcal P_d$, where $g \in \mathcal P_{d-1}$. Then \[ \| g \|_{d-1} \le \sqrt{ \frac{d}{1+|\zeta_1|^2}} \| f \|_d \] \end{lemma} \begin{proof}[Proof of Lemma~\ref{norms1}] We start with the easy case and assume that $\zeta_1=0$. Set $g(x) = \sum_{i=0}^{d-1} g_i x^i$. Then, $f(x) = \sum_{i=1}^{d} g_{i-1} x^i$. Now, \[ \|g\|_{d-1}^2 = \sum _{i=0}^{d-1} \frac{|g_i|^2}{\binomial{d-1}{i}} = \sum _{i=1}^{d} \frac{|g_{i-1}|^2}{\binomial{d-1}{i-1}} = \sum _{i=1}^{d} \frac{d}{i} \frac{|g_{i-1}|^2}{\binomial{d}{i}} \le d \|f\|_d ^2 \] and hence $\|g\|_{d-1} \le \sqrt{d} \|f\|_d$. For the general case, we will use $U(2)$-invariance of $\|.\|_d$ and $\|.\|_{d-1}$. Let $\varphi$ be a convenient unitary matrix: \[ \varphi = \frac{1}{\sqrt{1+|\zeta_1|^2}} \left[ \begin{array}{cc} 1 & \zeta_1 \\ - \bar{\zeta_1} & 1 \end{array} \right] \] Set $f^{\varphi} = f \circ \varphi$ and $g^{\varphi} = g \circ \varphi$. The choice of $\varphi$ has the particularity that $f^{\varphi}(0) = f(\zeta_1) = 0$. We can compute $f^{\varphi}$ in terms of $g^{\varphi}$: \[ f^{\varphi}(y) = \sqrt{1 + |\zeta_1|^2 } \ y \ g^{\varphi} (y) \] Using the easy case, \[ \| \sqrt{1 + |\zeta_1|^2 } g^{\varphi} \|_{d-1} \le \sqrt{d} \|f^{\varphi}\|_d \] By $U(2)$-invariance, \begin{eqnarray*} \| g \|_{d-1} &=& \| g^{\varphi} \| _{d-1} \\ &=& \frac{1}{ \sqrt{1 + |\zeta_1|^2 }} \| \sqrt{1 + |\zeta_1|^2 } g^{\varphi} \| _{d-1} \\ &\le& \frac{\sqrt{d}}{ \sqrt{1 + |\zeta_1|^2 }} \| f^{\varphi} \|_d \\ &=& \frac{\sqrt{d}}{ \sqrt{1 + |\zeta_1|^2 }} \| f \|_d \end{eqnarray*} \end{proof} \begin{lemma} \label{norms2} Let $g \in \mathcal P_{d-1}$. Then $\|g\|_d \le \|g\|_{d-1}$. \end{lemma} \begin{proof}[Proof of Lemma~\ref{norms2}] \[ \|g\|_d^2 = \sum_{i=0}^{d-1} \frac{|g_i|^2}{\binomial{d}{i}} = \sum_{i=0}^{d-1} \frac{d-i}{d} \frac{|g_i|^2}{\binomial{d-1}{i}} \le \|g\|_{d-1}^2 \] \end{proof} Putting Lemma~\ref{norms1} and Lemma~\ref{norms2} together, \begin{lemma}\label {norms3} Let $f(x) = (x-\zeta_1) g(x) \in \mathcal P_d$, where $g \in \mathcal P_{d-1}$. Then \[ \| g \|_{d} \le \frac{\sqrt{d}}{\sqrt{1+|\zeta_1|^2}} \| f \|_d \] \end{lemma} \begin{proof}[Proof of Theorem~\ref{cnt}] Let $f(x) = (x-\zeta_1) (x-\zeta_2) \cdots (x-\zeta_d)$ and order the $\zeta_i$'s such that \[ \rho(f) = \min_{|\zeta_i| < |\zeta_j|} 1- \frac{|\zeta_i|}{|\zeta_j|} = 1 - \frac{|\zeta_2|}{|\zeta_1|} \] Define $h(z) = (x - \zeta_1 (1-\rho)) (x-\zeta_2) \cdots (x-\zeta_d) \in \Sigma_G$. Then \begin{eqnarray*} \|f - h\|_d &=& \| \zeta_1 \rho (x-\zeta_2) \cdots (x-\zeta_d) \|_d \\ &=& |\zeta_1| \rho \| (x-\zeta_2) \cdots (x-\zeta_d) \|_d\\ &\le& |\zeta_1| \rho \frac{\sqrt{d}}{\sqrt{1+|\zeta_1|^2}} \|f\|_d \end{eqnarray*} Hence, \[ \frac{\|f-h\|_d}{\|f\|_d} \le \frac{|\zeta_1|}{\sqrt{1+|\zeta_1|^2}} \rho \sqrt{d} \le \rho \sqrt{d} \] Hence, \[ d_{\mathbb P} (f, \Sigma_G) \le \rho \sqrt{d} \] \end{proof} \begin{proof}[Proof of Theorem~\ref{th2}] We set $\delta = M \epsilon$, where $M$ is the constant such that the volume of an $\epsilon \sqrt{d}$ neighborhood of $\Sigma_G$ is less than $M \epsilon$. With probability larger than $1-\delta$, \[ \max_{|\zeta_{i}| < |\zeta_{j}|} \frac{|\zeta_{i}|}{|\zeta_{j}|} > 1 - \epsilon \mbox{ .} \] \par We now use the fact that, for any $N > (\log 2) / \epsilon$, we have $(1-\epsilon)^N < 1/2$. We set $k_1 = 1 + \lceil \log_2 \epsilon^{-1} \rceil$ and using $N=2^{k_1}$ in the previous formula, we obtain: \[ \max_{|\zeta_{i}| < |\zeta_{j}|} \frac{|\zeta_{i}|^{2^{k_1}}}{|\zeta_{j}|^{2^{k_1}}} < (1-\epsilon)^{2^{k_1}} < \frac{1}{2} \mbox{ .} \] \par An extra $1+\log_2 b$ iterations ensures that \[ \max_{|\zeta_{i}| < |\zeta_{j}|} \frac{|\zeta_{i}|^{2^{k}}}{|\zeta_{j}|^{2^{k}}} < 2^{-1-b} \mbox{ ,} \] provided that \[ k = k_1 + 1 + \log_2 b \mbox{ .} \] We claim that we have in this case that the sum \[ \sum_{i_1 < \dots < i_r} \zeta_{i_1}^{2^{k}}\dots \zeta_{i_r}^{2^{k}}= \zeta_{1}^{2^{k}} \dots \zeta_{r}^{2^{k}} (1+\varepsilon) \mbox{ ,} \] where \[| \varepsilon |< 2^{-b} \mbox{ .} \] Indeed, assume we have reordered the roots so that $|\zeta_1| > \dots > |\zeta_{d}| $. It then follows that \[ | \zeta_{i_1}^{2^k} \dots \zeta_{i_r}^{2^k} | < |\zeta_{1}^{2^k} \dots \zeta_{r}^{2^k}| 2^{-(1+b)(i_1+\dots + i_{r}- r (r+1)/2)} \mbox{ .} \] \oldtext{ Now, let \[ {\cal S}_{k} = \{(i_1,\dots,i_n) \ \ | \ \ i_1 + \dots + i_n - n(n+1)/2 =k \} \mbox{ .} \] Note that ${\cal S}_{0}=\{(1,\dots,n)\}$, and ${\cal S}_{1}=\{(1,\dots,n-1,n+1)\}$. Also, ${\cal S}_{2}=\{(1,\dots,n-1,n+2) ; (1,\dots,n-2,n,n+1)\}$ But, $\#{\cal S}_{i+1} \le d \# {\cal S}_i$, and hence \[ \sum_{i\ge 1} 2^{-b i}\#{\cal S}_i \le 2^{-b} (1+2 2^{-b} + 2 d 2^{-b} + 2 d^2 2^{-2b}\dots ) \le 2^{-b+1}\mbox{ ,} \] under the assumption that $d \le 2^b$. This concludes the proof of Theorem~\ref{th2}. } \newtext{ Now, for $r$ fixed, let \[ {\cal S}_{k} = \{(i_1,\dots,i_r) \ \ | \ i_1 < \cdots < i_r \text{ and } i_1 + \dots i_r - r(r+1)/2 =k \} \mbox{ .} \] Note that ${\cal S}_{0}=\{(1,\dots,r)\}$, and ${\cal S}_{1}=\{(1,\dots,r-1,r+1)\}$. Also, ${\cal S}_{2}=\{(1,\dots,r-1,r+2) ; (1,\dots,r-2,r,r+1)\}$ \par In general, every multi-index $i_1 < \cdots < i_r$ may be obtained by starting from $1<2< \cdots