Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
I think you're right, I got confused. The union bound couldn't work for the first version of the question because of factors of $\varepsilon$, but I think it might work here, thought I have to think that through.
Thanks, I didn't thought about that. In this case I guess that the question I really want to ask is: for a fixed $\epsilon$, does there exist $K(\epsilon)$ such that for $k>K(\epsilon)$ the discrepancy is $<\epsilon$ almost surely as $n \to \infty$.
The theorem only applies when $f$ is a polynomial function, not any function. In other words, the theorem assumes that $f$ is represented by some polynomial and proves that it is then (uniquely) represented by a polynomial satisfying the given bounds on the coefficients.
