Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials

We improve some lower bounds which have been obtained by Strassen and Lipton. In particular there exist polynomials of degree n with 0–1 coefficients that cannot be evaluated with less than $\text{n}\text{/(4}\text{log}\text{n)}$ nonscalar multiplications/divisions. The evaluation of p(x) $\text{∑}\text{δ=0}\text{n}\text{e}{}^{\mathrm{<mtext>2\pi i</mtext><mtext>2\delta </mtext>}}\text{x}{}^{\mathrm{\delta }}$ requires at least $\text{n}\text{(12}\text{log}\text{n)}$ multiplications/divisions and at least $\text{n/(8}\text{log}\text{n)}$ nonscalar multiplications/divisions. We specify polynomials with algebraic coefficients that require $\text{1}\text{2}\text{n}$ multiplications/divisions.