We revisit a classical result of Coppersmith and Shparlinski [CS00] showing bounds on how well polynomials can approximate the discrete log function. They showed that for any univariate polynomial $f(X) \in \mathbb{F}_p[X]$ with $\deg(f) \leq D$, we have:
$$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = dlog(x) \}| \leq \sqrt{2 D p}.$$
We show two improvements:

(1) For all $D$, we improve the upper bound above to $(1+o(1)) \cdot \sqrt{Dp}$. In particular, we give nontrivial upper bounds on the approximation even for $D > p/2$. This new upper bound is the Johnson bound from the theory of list-decoding of error-correcting codes, and in fact our proof uses a connection to that problem, as well as other combinatorial ideas.

(2) For $D = 1$, where both the above bounds are $O(\sqrt{p})$, we give an asymptotically improved upper bound of $O(p^{2/5})$. This is based on the sum-product phenomenon of additive combinatorics.

We also improve the [CS00] bounds on the number of points of the form $(x, dlog(x)) \in \mathbb{F}_p^2$ that any bivariate polynomial $Q(X,Y) \in \mathbb{F}_p[X,Y]$ with $\deg(Q) \leq D$ can vanish on, with our new bounds approaching the analogue of the Johnson bound for this problem.