On lower bounds for the complexity of polynomials and their multiples

We prove a theorem giving arbitrarily long explicit sequences x(1),..., x(s ), of algebraic numbers such that any nonzero polynomial f(X) satisfying f( x(1)) = = f(x(s),) = 0 has nonscalar complexity > C root s for some positiv e constant C independent of s. A similar result is shown for rapidly growin g rational sequences.