Polynomial approximation (in $L^1$ norm) at minimal cost Define the cost of a polynomial $\sum_{i=0}^N a_i x^n$ to be $\sum_{i=0}^N |a_i|$. Let $g:[0,1]\to \mathbb{R}$ be a function to be approximated —   say, $g(x)=0$ if $0\leq x < e^{-1}$, $g(x)= 1/x$ if $e^{-1}\leq x\leq 1$. (That function comes up in practical contexts.) We are interested in polynomials $P_+$, $P_-$ such that $P_-(x)\leq g(x)\leq P_+(x)$. We define the tightness $\epsilon(P)$ of $P$ to be $\epsilon(P) = \epsilon = \int_0^1 |P(x)-g(x)| dx$. 


*

*For given $\epsilon>0$ and $N$ what are the polynomials $P_+$, $P_-$ of tightness $\leq \epsilon$ and minimal cost?

*What are those minimal costs $c_+(\epsilon,N)$, $c_-(\epsilon,N)$?

*What if we allow the degree $N$ to be arbitrary? In other words, what are $c_-(\epsilon) = \inf_N c_-(\epsilon,N)$ and $c_+(\epsilon) = \inf_N c_+(\epsilon,N)$?

*Is there a simple way to see the right order of magnitude of $c_+(\epsilon)$ and $c_-(\epsilon)$?


As an alternative, we could allow $P_+(x)$, $P_-(x)$ to be a linear combination of fractional powers $x^r$, $r\geq 1$.
 A: And why is that terribly costly?
@AlexandreEremenko will, probably, have a simpler explanation, but this is how I see it if no pen and paper is allowed.
Let $\varphi$ be the conformal mapping of the horizontal strip $\{|\Im z|<1\}$ to the unit disk such that $\varphi(0)=0$ and the real axis is mapped to $[-1,1]$ so that $-\infty$ goes to $-1$ and $+\infty$ goes to $1$. Suppose $f$ is an analytic function in the unit disk bounded by $M$ and such that $\int_{[-1,1]}|f-H|\le\varepsilon$ where $H(x)=0$ on $(-\infty,0)$ and $H(x)=1$ on $[0,+\infty)$. Consider $F=(f\circ \varphi)\cdot\varphi'$. We have $F$ analytic and dominated by $M|\varphi'|$ in the strip and $\int_{-\infty}^\infty |F-H\varphi'|\le\varepsilon$, whence for every $y>0$, we must have $\left|\int_{-\infty}^\infty F(x)e^{iyx}dx-\int_{0}^\infty \varphi'(x)e^{iyx}dx\right|\le\varepsilon$. Shifting the contour in the first integral to $i+\mathbb R$ and taking into account that $\int_{-\infty}^{\infty}|\varphi'(i+x)|dx=\pi$ (the top line is mapped to the top half-circle), we see that the first integral is at most $\pi Me^{-y}$. On the other hand, the second one is about $i\frac{\phi'(0)}{y}$ for decent size $y$ (shift the contour to the vertical interval $[0,i]$ followed by $i+[1,\infty)$ and use the trivial version of the "Laplace formula"). Thus, we get 
$$
\frac cy\le \varepsilon+\pi Me^{-y} 
$$
Now choose $y=\frac c{2\varepsilon}$, say.
Is there another, possibly simpler example?
Yes, if you want just an $L^1$ approximation but adjusting it to your requirement that the polynomial should stay on one side of the function is a bit cumbersome exercise, so I'll not bother going into it. 
