Lower Bounds by Birkhoff Interpolation

Abstract : In this paper 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 (also known as "lacunary polynomial interpolation").
Type de document :
Pré-publication, Document de travail
2015
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01172296
Contributeur : Pascal Koiran <>
Soumis le : mardi 7 juillet 2015 - 11:27:52
Dernière modification le : mardi 24 avril 2018 - 13:52:49
Document(s) archivé(s) le : mercredi 26 avril 2017 - 00:45:13

Fichiers

birkhoff.arxiv.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-01172296, version 1
  • ARXIV : 1507.02015

Collections

Citation

Ignacio Garcia-Marco, Pascal Koiran. Lower Bounds by Birkhoff Interpolation. 2015. 〈ensl-01172296〉

Partager

Métriques

Consultations de la notice

43

Téléchargements de fichiers

300