Lower bounds by birkhoff interpolation
- IGNACIO GARCÍA-MARCO
- PASCAL KOIRAN
ISSN: 1132-6360
Argitalpen urtea: 2018
Zenbakien izenburua: Proceedings of the XVI EACA Zaragoza Encuentros de Algebra Computacional y Aplicaciones
Zenbakia: 43
Orrialdeak: 95-98
Mota: Artikulua
Beste argitalpen batzuk: Monografías de la Real Academia de Ciencias Exactas, Físicas, Químicas y Naturales de Zaragoza
Laburpena
In this work we give lower bounds for the representation of real univariate polynomials as sums of powers of degree 1 polynomials. We present two families of polynomials of degree d such that the number of powers that are required in such a representation must be at least of order d. This is clearly optimal up to a constant factor. Previous lower bounds for this problem were only of order Ω(√ d), and were obtained from arguments based on Wronskian determinants and "shifted derivatives". We obtain this improvement thanks to a new lower bound method based on Birkhoff interpolation.