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

Authors: Carlos Beltrán, Ujué Etayo, Jordi Marzo and Joaquim Ortega-Cerdà
Journal: J. Amer. Math. Soc. 34 (2021), 219-244
MSC (2010): Primary 65Y20
DOI: https://doi.org/10.1090/jams/956
Published electronically: December 8, 2020
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

[1] 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, https://doi.org/10.1007/s10208-014-9213-0
[2] 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, https://doi.org/10.1016/j.jco.2020.101471
[3] 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, https://doi.org/10.1007/s10208-010-9078-9
[4] 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, https://doi.org/10.1007/s00365-016-9357-z
[5] 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
[6] J. S. Brauchart, Optimal logarithmic energy points on the unit sphere, Math. Comp. 77 (2008), no. 263, 1599–1613. MR 2398782, https://doi.org/10.1090/S0025-5718-08-02085-1
[7] 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, https://doi.org/10.1090/conm/578/11483
[8] 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, https://doi.org/10.4007/annals.2011.174.3.8
[9] 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
[10] 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, https://doi.org/10.1007/BF02986850
[11] 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
[12] 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, https://doi.org/10.1007/s10208-016-9319-7
[13] 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).
[14] 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, https://doi.org/10.1007/BF02559527
[15] 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, https://doi.org/10.4310/MRL.1994.v1.n6.a3
[16] 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, https://doi.org/10.1007/s00220-012-1508-x
[17] 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, https://doi.org/10.1090/S0894-0347-1993-1175980-4
[18] 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, https://doi.org/10.1007/978-1-4612-2752-6_19
[19] 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, https://doi.org/10.1006/jcom.1993.1002
[20] Steve Smale, Mathematical problems for the next century, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, pp. 271–294. MR 1754783
[21] Stefan, Steinerberger. On the logarithmic energy of points on $\mathbb{S}^2$ , 2001.04630
[22] 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

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 65Y20

Retrieve articles in all journals with MSC (2010): 65Y20

Additional Information

Carlos Beltrán
Affiliation: Departamento de Matematicas Estadistica y Computacion, University of Cantabria, 39005 Santander, Spain
Email: carlos.beltran@unican.es

Ujué Etayo
Affiliation: Institut für Analyse und Zahlentheorie, Technische Universität Graz , Kopernikusgasse 24/II 8010 Graz, Austria
Email: etayo@math.tugraz.at

Jordi Marzo
Affiliation: Departament de Matemàtiques i Informàtica, Universitat de Barcelona, Gran Via 585, 08007 Barcelona, Spain

Joaquim Ortega-Cerdà
Affiliation: Departament de Matemàtiques i Informàtica, Universitat de Barcelona, Gran Via 585, 08007 Barcelona, Spain

DOI: https://doi.org/10.1090/jams/956
Received by editor(s): March 5, 2019
Received by editor(s) in revised form: March 19, 2020, and March 30, 2020
Published electronically: December 8, 2020
Additional Notes: The first and second authors were partially supported by Ministerio de Economía y Competitividad, Gobierno de España, through grants MTM2017-83816-P and MTM2017-90682-REDT, and by the Banco de Santander and Universidad de Cantabria grant 21.SI01.64658.
The second author was also supported by the Austrian Science Fund FWF project F5503 (part of the Special Research Program (SFB) Quasi-Monte Carlo Methods: Theory and Applications).
The third and fourth authors have been partially supported by grant MTM2017-83499-P by the Ministerio de Economía y Competitividad, Gobierno de España and by the Generalitat de Catalunya (project 2017 SGR 358).
Article copyright: © Copyright 2020 American Mathematical Society