Relationship between the composition of two real functions and their approximation polynomials (Weierstrass approximation theorem)

Question

Consider two continuous real valued functions $f$, and $g$ over the interval $[a,b]$. For a given $\epsilon > 0$, for each function the we can use the Weierstrass approximation theorem to express the function as polynomials $f \approx \mathcal{P}_f$ and $g \approx \mathcal{P}_g$, such that $\lvert f - \mathcal{P}_f\lvert < \epsilon$ and $\lvert g - \mathcal{P}_g\lvert < \epsilon$, over the interval $[a,b]$. Is there anything we can say about the approximating the composition of the two functions $f \circ g$, i.e., $\mathcal{P}_{f\circ g}$ where $\lvert f\circ g - \mathcal{P}_{f\circ g}\rvert < \epsilon$ on the interval $[a,b]$. In other words, is there any relation between $\mathcal{P}_{f\circ g}$, $\mathcal{P}_f$, and $\mathcal{P}_g$?

In particular, I am interested if from $\deg(\mathcal{P}_f)$ and $\deg(\mathcal{P}_g)$ we can say anything about $\deg(\mathcal{P}_{f\circ g})$. I can appreciate that $\deg(\mathcal{P}_f) + \deg(\mathcal{P}_g)$ may be greater than $\deg(\mathcal{P}_{f\circ g})$; as the composition may conspire to cancel out higher terms (e.g., $g \ll f$, such that $\mathcal{P}_f$ has ''overfit'' $f$ to achieve $\epsilon$ in the composition.) However, I cannot see if one can guarantee that this is the upper limit, i.e., $$\deg(\mathcal{P}_{f\circ g}) \leq \deg(\mathcal{P}_f) + \deg(\mathcal{P}_g)?$$

Edit: An example that the component degree sum is larger can be seen from $f(x) = 1+x$, and $g(x) = (1+x)^{-1}$. Both have approximating polynomials greater than degree zero, while the composition's approximating polynomial is trivially degree zero.

Is there a counter-example to the suggestion inequality, i.e., where

$$deg(\mathcal{P}_{f\circ g}) > \deg(\mathcal{P}_f) + \deg(\mathcal{P}_g)?$$

Answer 1

Here's an example of something you might try in this general direction. Assume WLOG $[a,b]=[0,1]$.

Consider the Bernstein polynomial proof of Weierstrass's theorem. The estimates say that the Bernstein polynomial of degree $d$ corresponding to $f$ evaluated at $x$ will differ from $f(x)$ by no more than $\varepsilon' + R g(\delta,d)$, where

• $R$ is a bound on the length of the range of $f$. (You could take to be $2M$ where $M$ is a bound on $|f|$ if you want).
• $\delta$ and $\varepsilon'$ are related so that $|f(x)-f(y)|<\varepsilon'$ whenever $|x-y|<\delta$, i.e. $\delta(\varepsilon')$ is a uniform modulus of continuity for $f$
• $g(\delta,d)$ is any upper bound on the probability that a binomial random variable with $d$ trials differs from its mean by more than $d\delta$, which must hold for all possible success probabilities in $[0,1]$.

One such bound is the Hoeffding inequality which gives you $g(\delta,d)=2e^{-2\delta^2 d}$.

If you now further assume that $f$ is Lipschitz with constant $L$, then

$$\varepsilon' + 2R e^{-2 \frac{\varepsilon'^2}{L^2} d}$$

is an error bound for any $\varepsilon'>0$. Thus to have an error no more than $\varepsilon$, it suffices to have $d \geq \frac{L^2}{2 \varepsilon'^2} \log \left ( \frac{2R}{\varepsilon-\varepsilon'} \right )$ for some $\varepsilon' \in (0,\varepsilon)$. In particular by taking $\varepsilon'=\varepsilon/2$ you find that $d \geq \frac{2L^2}{\varepsilon^2} \log \left ( \frac{4R}{\varepsilon} \right )$ is sufficient. (The optimal expression is a big ugly mess with the Lambert W function.)

You can repeat this analysis with $f \circ g$ by noting that $f \circ g$ will be Lipschitz with constant $L_f L_g$ and its range is contained in that of $f$.