Revista de la
Unión Matemática Argentina
The Newman algorithm for constructing polynomials with restricted coefficients and many real roots
Markus Jacob and Fedor Nazarov

Volume 68, no. 2 (2025), pp. 745–759    

Published online (final version): October 13, 2025

https://doi.org/10.33044/revuma.4883

Download PDF

Abstract

Under certain natural sufficient conditions on the sequence of uniformly bounded closed sets $E_k\subset\mathbb{R}$ of admissible coefficients, we construct a polynomial $P_n(x)=1+\sum_{k=1}^n\varepsilon_k x^k$, $\varepsilon_k\in E_k$, with at least $c\sqrt n$ distinct roots in $[0,1]$, 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.

References

  1. P. Borwein, Computational excursions in analysis and number theory, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC 10, Springer, New York, 2002.  DOI  MR  Zbl
  2. P. Borwein and T. Erdélyi, The $L_p$ version of Newman's inequality for lacunary polynomials, Proc. Amer. Math. Soc. 124 no. 1 (1996), 101–109.  DOI  MR  Zbl
  3. P. Borwein, T. Erdélyi, and G. Kós, Littlewood-type problems on $[0,1]$, Proc. London Math. Soc. (3) 79 no. 1 (1999), 22–46.  DOI  MR  Zbl
  4. T. Erdélyi, Extensions of the Bloch–Pólya theorem on the number of real zeros of polynomials, J. Théor. Nombres Bordeaux 20 no. 2 (2008), 281–287.  DOI  MR  Zbl
  5. D. Ivanov, Number of real roots of 0,1 polynomial, MathOverflow, 2024. Available at https://mathoverflow.net/q/461631.