Lower bounds by Birkhoff interpolation

详细信息    查看全文

• 作者：Ignacio Garcí ; a-Marco ; ^{iggarcia@ull.es} ; Pascal Koiran ^{pascal.koiran@ens-lyon.fr}
• 关键词：Polynomial interpolation ; Waring problem ; Arithmetic circuit ; Lower bounds ; Real polynomial
• 刊名：Journal of Complexity
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：39
• 期：Complete
• 页码：38-50
• 全文大小：423 K
• 卷排序：39

文摘

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 dd such that the number of powers that are required in such a representation must be at least of order dd. 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”).