Erdős's Robust Polynomial Interpolation Problem: the Optimal Exponential Scale

We determine the optimal exponential scale in Erdős’s robust polynomial interpolation problem and identify the leading exponential coefficient for Chebyshev–Lobatto grids. Given $C>0$ and $0\le \rho <1$, put $H=C\mathrm{/}(1-\rho )$. We prove that every configuration of $n\ge n_0$ nodes in $[-1,1]$ admits sign data for which every polynomial of degree at most $(1+\epsilon )n$ and uniform norm at most $C$ has error greater than $\rho$ at more than $\epsilon n$ nodes. One may choose $\epsilon \ge e^{-A(1+H)}$ and $n_0\le e^{A(1+H)}$, where $A$ is an absolute constant, and a matching upper bound shows that the exponential order is optimal. For the same obstruction restricted to Chebyshev–Lobatto grids, the optimal parameter ${\epsilon }_{\mathrm{C}\mathrm{h}}(C,\rho )$ satisfies $\log (1\mathrm{/}{\epsilon }_{\mathrm{C}\mathrm{h}}(C,\rho ))=\frac{\pi }{2}H+O(\log (H+1))$ as $H\to \mathrm{\infty }$. The proofs combine finite interpolation estimates in Bernstein spaces with periodic sign constructions and averaging. We also establish obstructions for random signs and stability under angular perturbations of the nodes.