Lower Bounds by Birkhoff Interpolation
summary
Shows explicit univariate lower bounds for representing polynomials as sums of powers of linear forms, proving linear-size barriers under natural exponent restrictions. Example H2 = (x+1)^{d+1}-x^{d+1} is proven to require ≥ (d-1)/2 terms when exponents are ≤ d; a shifted-powers family with distinct shifts is shown optimal with k at least about (d+2)/4 in that regime. Proof uses Birkhoff interpolation and a Wronskian-style criterion over real polynomials to certify linear independence rather than just shifted-derivative ranks.
AI-written summary · about