A sequence of polynomials with optimal condition number

Beltrán, Carlos; Etayo, Ujué; Marzo, Jordi; Ortega-Cerdà, Joaquim

doi:10.1090/jams/956

A sequence of polynomials with optimal condition number
HTML articles powered by AMS MathViewer

by Carlos Beltrán, Ujué Etayo, Jordi Marzo and Joaquim Ortega-Cerdà

J. Amer. Math. Soc. 34 (2021), 219-244

DOI: https://doi.org/10.1090/jams/956

Published electronically: December 8, 2020

HTML | PDF | Request permission

Abstract:

We find an explicit sequence of univariate polynomials of arbitrary degree with optimal condition number. This solves a problem posed by Michael Shub and Stephen Smale in 1993.

References

Carlos Beltrán, A facility location formulation for stable polynomials and elliptic Fekete points, Found. Comput. Math. 15 (2015), no. 1, 125–157. MR 3303693, DOI 10.1007/s10208-014-9213-0
Carlos Beltrán and Ujué Etayo, The diamond ensemble: a constructive set of spherical points with small logarithmic energy, J. Complexity 59 (2020), 101471, 22. MR 4099902, DOI 10.1016/j.jco.2020.101471
Carlos Beltrán and Luis Miguel Pardo, Fast linear homotopy to find approximate zeros of polynomial systems, Found. Comput. Math. 11 (2011), no. 1, 95–129. MR 2754191, DOI 10.1007/s10208-010-9078-9
Laurent Bétermin and Etienne Sandier, Renormalized energy and asymptotic expansion of optimal logarithmic energy on the sphere, Constr. Approx. 47 (2018), no. 1, 39–74. MR 3742809, DOI 10.1007/s00365-016-9357-z
Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR 1479636, DOI 10.1007/978-1-4612-0701-6
J. S. Brauchart, Optimal logarithmic energy points on the unit sphere, Math. Comp. 77 (2008), no. 263, 1599–1613. MR 2398782, DOI 10.1090/S0025-5718-08-02085-1
J. S. Brauchart, D. P. Hardin, and E. B. Saff, The next-order term for optimal Riesz and logarithmic energy asymptotics on the sphere, Recent advances in orthogonal polynomials, special functions, and their applications, Contemp. Math., vol. 578, Amer. Math. Soc., Providence, RI, 2012, pp. 31–61. MR 2964138, DOI 10.1090/conm/578/11483
Peter Bürgisser and Felipe Cucker, On a problem posed by Steve Smale, Ann. of Math. (2) 174 (2011), no. 3, 1785–1836. MR 2846491, DOI 10.4007/annals.2011.174.3.8
Peter Bürgisser and Felipe Cucker, Condition, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 349, Springer, Heidelberg, 2013. The geometry of numerical algorithms. MR 3098452, DOI 10.1007/978-3-642-38896-5
A. Dubickas, On the maximal product of distances between points on a sphere, Liet. Mat. Rink. 36 (1996), no. 3, 303–312 (English, with English and Lithuanian summaries); English transl., Lithuanian Math. J. 36 (1996), no. 3, 241–248 (1997). MR 1455810, DOI 10.1007/BF02986850
I. S. Gradshteyn and I. M. Ryzhik, Table of integrals, series, and products, 8th ed., Elsevier/Academic Press, Amsterdam, 2015. Translated from the Russian; Translation edited and with a preface by Daniel Zwillinger and Victor Moll; Revised from the seventh edition [MR2360010]. MR 3307944
Pierre Lairez, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, Found. Comput. Math. 17 (2017), no. 5, 1265–1292. MR 3709332, DOI 10.1007/s10208-016-9319-7
Y. I. Lyubarskiĭ and M. Sodin, Analogues of sine type for convex domains, Preprint no. 17, Inst. Low Temperature Phys. Eng., Ukrainian Acad. Sci., Kharkov (Russian). 1 (1986).
Yuriĭ I. Lyubarskiĭ and Kristian Seip, Sampling and interpolation of entire functions and exponential systems in convex domains, Ark. Mat. 32 (1994), no. 1, 157–193. MR 1277924, DOI 10.1007/BF02559527
E. A. Rakhmanov, E. B. Saff, and Y. M. Zhou, Minimal discrete energy on the sphere, Math. Res. Lett. 1 (1994), no. 6, 647–662. MR 1306011, DOI 10.4310/MRL.1994.v1.n6.a3
Etienne Sandier and Sylvia Serfaty, From the Ginzburg-Landau model to vortex lattice problems, Comm. Math. Phys. 313 (2012), no. 3, 635–743. MR 2945619, DOI 10.1007/s00220-012-1508-x
Michael Shub and Steve Smale, Complexity of Bézout’s theorem. I. Geometric aspects, J. Amer. Math. Soc. 6 (1993), no. 2, 459–501. MR 1175980, DOI 10.1090/S0894-0347-1993-1175980-4
M. Shub and S. Smale, Complexity of Bezout’s theorem. II. Volumes and probabilities, Computational algebraic geometry (Nice, 1992) Progr. Math., vol. 109, Birkhäuser Boston, Boston, MA, 1993, pp. 267–285. MR 1230872, DOI 10.1007/978-1-4612-2752-6_{1}9
Michael Shub and Steve Smale, Complexity of Bezout’s theorem. III. Condition number and packing, J. Complexity 9 (1993), no. 1, 4–14. Festschrift for Joseph F. Traub, Part I. MR 1213484, DOI 10.1006/jcom.1993.1002
Steve Smale, Mathematical problems for the next century, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, pp. 271–294. MR 1754783
Stefan, Steinerberger. On the logarithmic energy of points on $\mathbb {S}^2$, arXiv:2001.04630
Gerold Wagner, On the product of distances to a point set on a sphere, J. Austral. Math. Soc. Ser. A 47 (1989), no. 3, 466–482. MR 1018975, DOI 10.1017/S1446788700033206