Approximation with one-bit polynomials in Bernstein form

We prove various approximation theorems with polynomials whose coefficients with respect to the Bernstein basis of a given order are all integers. In the extreme, we draw the coefficients from the set $\{ \pm 1\}$ only. We show that for any Lipschitz function $f:[0,1] \to [-1,1]$ and for any positive integer $n$, there are signs $\sigma_0,\dots,\sigma_n \in \{\pm 1\}$ such that $$\left |f(x) - \sum_{k=0}^n \sigma_k \, \binom{n}{k} x^k (1-x)^{n-k} \right | \leq \frac{C (1+|f|_{\mathrm{Lip}})}{1+\sqrt{nx(1-x)}} ~\mbox{ for all } x \in [0,1].$$ These polynomial approximations are not constrained by saturation of Bernstein polynomials, and we show that higher accuracy is indeed achievable for smooth functions: If $f$ has a Lipschitz $(s{-}1)$st derivative, then accuracy of order $O(n^{-s/2})$ is achievable with $\pm 1$ coefficients provided $\|f \|_\infty < 1$, and accuracy of order $O(n^{-s})$ is achievable with unrestricted integer coefficients. Our approximations are constructive in nature.