The Newman algorithm for constructing polynomials with restricted coefficients and many real roots

Under certain natural sufficient conditions on the sequence of uniformly bounded closed sets E k ⊂ R of admissible coefficients, we construct a polynomial Pn(which matches the classical upper bound up to the value of the constant c > 0. Our sufficient conditions cover the Littlewood (E k = {-1, 1}) and Newman (E k = {0, (-1) k }) polynomials and are also necessary for the existence of such polynomials with arbitrarily many roots in the case when the sequence E k is periodic.1.