Balancing Polynomials in the Chebyshev Norm

Abstract

Given $n$ polynomials $p_1,\dots ,p_n$ of degree at most $n$ with $\Vert p_i{\Vert }_{\infty }\le 1$ for $i\in [n]$, we show there exist signs $x_1,\dots ,x_n\in \{-1,1\}$ so that \[\Big\|\sum_{i=1}^n x_i p_i\Big\|_\infty < 30\sqrt{n}, \] where $\Vert p{\Vert }_{\infty }:={\sup }_{|x|\le 1}|p(x)|$. This result extends the Rudin-Shapiro sequence, which gives an upper bound of $O(\sqrt{n})$ for the Chebyshev polynomials $T_1,\dots ,T_n$, and can be seen as a polynomial analogue of Spencer's "six standard deviations" theorem.

Fixed a small error in Lemma 7