# Approximation of analytic function by a fixed number of monomials

This question seems simple but I can't manage to disprove it. Let $$N\in \mathbb{N}$$. We know that by its analyticity that this precise linear combination of monomials $$\sum_{n=0}^K \frac1{n!} x^n$$ converges uniformly to $$g$$ on $$[0,1]$$ and that for $$K$$ large enough $$\max_{x \in [0,1]}\, \|\sum_{n=0}^K \frac1{n!} x^n - \exp(x)\| However, $$K$$ becomes unbounded as a function of $$N$$.

My question: Does there exist a single $$K\in \mathbb{N}$$ for which, for any $$N\in \mathbb{N}$$ always exists $$\alpha_1,\dots,\alpha_K\in [0,1]$$ and $$\beta_1,\dots,\beta_K\in \mathbb{R}$$ such that $$\max_{x \in [0,1]}\, \|\sum_{n=0}^K \beta_n x^{\alpha_n} - \exp(x)\| That is, can we bound the number of these "monomials" required to approximate the function $$\exp$$.

• I am a bit confused - what do you mean by "rational functions" here as $x^a, 0<a<1$ are not rational functions in the usual sense, while they are indeed called monomials in some contexts (even for arbitrary real powers) Feb 9, 2021 at 18:20
• @Conrad I wasn't sure what to call them; note I allow $\alpha$ to be $1$ or $0$. Nevertheless, I changed the terminology as you suggest. Feb 9, 2021 at 18:21
• great - now it's clear and I agree that monomials sounds accurate - definitely an interesting problem Feb 9, 2021 at 18:23
• you start with approximation by combinations of $x^n, n=0,1,2,\ldots$, but then change the range of exponents to $[0,1]$ --- why? Feb 9, 2021 at 22:15

The general description of all continuous functions which are uniform limits of fewnomials seems to be given by the following

Theorem. Fix $$0. The following two properties of a continuous function $$f\in C[a,b]$$ are equivalent:

(i) $$f$$ is log-quasipolynomial, that is, $$f(x)=P(x,\log x)$$ for a certain quasi-polynomial $$P(u,v)=\sum_{i=1}^N c_i u^{\kappa_i} v^{m_i}$$, where $$\kappa_i$$'s are real and $$m_i$$'s non-negative integers;

(ii) $$f$$ is a uniform limit of a sequence of fewnomials (that is, of functions of the form $$f_n(x)=\sum_{k=1}^K \beta_k^{(n)} x^{\alpha_k^{(n)}}$$ with the same $$K$$).

Proof. $$(i)\Rightarrow (ii)$$ follows from $$\log x=\lim n(x^{1/n}-1)$$ uniformly on $$[a,b]$$.

$$(i)\Rightarrow (ii)$$ Induction in $$K$$. Base $$K=0$$, then $$f_n(x)\equiv 0$$ and $$f\equiv 0$$ too.

Induction step from $$K-1$$ to $$K$$. Passing to a subsequence, we may suppose that $$\alpha_K^{(n)}$$ has a limit $$\alpha_K$$ which may be equal to $$+\infty$$, $$-\infty$$ or be a real number.

If, say, $$\alpha_K=\infty$$, we may fix $$c\in (a/b,1)$$ and consider the functions $$g_n(x)=f_n(cx)-c^{\alpha_K^{(n)}}f_n(x)$$ (it has at most $$K-1$$ monomials), they converge to $$f(cx)$$ uniformly on $$[a/c,b]$$. Thus by induction hypothesis $$f(cx)$$ is log-quasipolynomial on $$[a/c,b]$$. In other words, $$f$$ is log-quasipolynomial on $$[a,cb]$$. Such log-quasipolynomials for distinct $$c$$ must be consistent, so $$f$$ is log-quasipolynomial on $$[a,b]$$. Analogously if $$\alpha_K=-\infty$$.

So assume that $$\alpha_K$$ is a real number. Consider the functions $$\tilde{f}_n(x)=x^{-\alpha_K^{(n)}}f_n(x)=\sum_{k=1}^K \beta_k^{(n)} x^{\tilde{\alpha}_k^{(n)}}$$, where $$\tilde{\alpha}_k^{(n)}=\alpha_k^{(n)}-\alpha_K^{(n)}$$. They uniformly on $$[a,b]$$ converge to $$\tilde{f}(x):=x^{-\alpha_K}f(x)$$. If $$\tilde{f}(x)$$ is log-quasipolynomial, then so is $$f$$. Changing notations back (omit tilde), we now on suppose that $$\alpha_K^{(n)}=0$$.

Again, we fix $$c\in (a/b,1)$$ and consider the functions $$g_n(x)=f_n(cx)-f_n(x)$$. They converge to $$f(cx)-f(x)$$ uniformly on $$[a/c,b]$$. By induction hypothesis $$f(cx)-f(x)$$ is a log-quasipolynomial on $$[a/c,b]$$. Any log-quasipolynomial may be represented as $$H(cx)-H(x)$$ for another log-quasipolynomial $$H$$. So we may write $$f(cx)-f(x)=H_c(cx)-H_c(x)$$ for a log-quasipolynomial $$H_c$$. We may assume additionally $$H_c(b)=f(b)$$. Note that $$H_c(cx)-H_c(x)=f(cx)-f(x)=\sum_{j=0}^{m-1} f(c^{(j+1)/m}x)-f(c^{j/m}x)=H_{c^{1/m}}(cx)-H_{c^{1/m}}(x),$$ thus $$p(x):=H_c(x)-H_{c^{1/m}}(x)$$ satisfies $$p(b)=0$$ and $$p(cx)=p(x)$$ for $$x\in [a/c,b]$$. This yields $$H_c\equiv H_{c^{1/m}}$$. If $$c_1,c_2$$ are rational powers of 2, then there exist positive integers $$m_1,m_2$$ such that $$c_1^{1/m_1}=c_2^{1/m_2}$$. Thus $$H_{c}=:H$$ does not depend on $$c$$ on a dense set $$D\subset [a/b,1]$$ of values of $$c$$'s. So the function $$f(x)-H(x)=:F(x)$$ satisfies $$F(b)=0$$, $$F(x)=F(cx)$$ for $$c\in D$$. Since $$F$$ is continuous, this yields $$F\equiv 0$$ and $$f=H$$. $$\square$$

Of course $$\exp(x)$$ is not log-quasipolynomial on an interval (for instance, because it grows faster at infinity, and if two functions which are analytic on the right half-plane coincide on an interval, they do coincide on the whole half-plane).

• Do you happen to know a reference to this theorem? Feb 12, 2021 at 8:41
• No I do not. Though I doubt a lot that it is new. Possibly you may ask Khovansky who wrote a book on fewnomials. Feb 12, 2021 at 9:48

Edit later - as per comments from @Eremenko and @Pinelis, there is a flaw in the argument and the solution works only if we assume that $$\beta_{k,N}$$ are bounded since that doesn't follow easily as I first thought (for example one can note that $$|N\sqrt x- Nx^{1/2+1/N^2}| \le C\log N/N, 1 \ge x \ge 1/N^4$$ and $$|N\sqrt x- Nx^{1/2+1/N^2}| \le C/N, 0 \le x \le 1/N^4$$, so even for the stronger approximation on the full $$[0,1]$$ interval, if there is one such, we can introduce two extra terms with the betas going to infinity that don't affect the approximation)

(Partial solution) I think the answer is no by a convergence argument. We will show that no such approximation is possible even on the subinterval $$[1/2,1]$$ and that will definitely imply the result

Let's assume there are sequences $$f_N(x)=\sum_{k=1}^K \beta_{k,N}x^{\alpha_{k,N}}$$ with parameters $$\alpha_{k,N}, \beta_{k,N}, k=1,..K, 0 \le \alpha_{k,N} \le 1$$, st $$||f_N(x)-e^x||_{\infty} \le 1/N$$ (where $$||.||_{\infty}$$ is the supremum norm on continuous functions on $$[1/2,1]$$ say).

Assuming $$|\beta_{k,N}| \le C$$ for all $$k=1,..K, N \ge 1$$, one can extract a subsequence for which all respective parameters converge to some parameters $$\alpha_{k}, \beta_{k}, k=1,K$$ and then (by renumbering) we need to show:

1: If $$\alpha_{k,N}\to \alpha_k, \beta_{k,N} \to \beta_k, N \to \infty, k=1,..K$$ then $$||f_N-f||_{\infty} \to 0$$ where $$f$$ is constructed with data $$\alpha_k, \beta_k$$

2: $$\exp x \ne f$$ for any data as above

For 1, the only thing which is not immediately obvious is to show that $$||x^{\alpha_n}-x^{\alpha}||_{\infty} \to 0$$ when $$\alpha_n \to \alpha, 0 \le \alpha_n \le 1$$ and by the mean value theorem for fixed $$1/2 \le x<1$$ we have $$|x^{\alpha_n}-x^{\alpha}|=x^{c_n}|\alpha_n-\alpha||\log x|$$ for some $$c_n \in [0,1]$$. But now since we are on $$[1/2,1], |\log x|$$ is uniformly bounded in $$x$$ as is obviously $$x^c, 0 \le c \le 1$$ so the norm convergence is clear.

For 2, assume $$\exp x=\sum_{k=1}^K \beta_kx^{\alpha_k}, x \in [1/2,1]$$. Then we can for example extend analytically both sides on say $$\Re z >0$$ using the principal branch of the logarithm for RHS and then by analytic continuation the identity is valid everywhere on $$\Re z >0$$ which is obviously not possible when $$x \to \infty$$

• Thank you Conrad; this has been extremely insightful! Feb 9, 2021 at 19:21
• Happy to be of help Feb 9, 2021 at 19:31
• How did you get $|\beta_{k,N}|\le K+3$? Feb 9, 2021 at 19:38
• I did not understand how you bounded $|\beta_k|$ "using triangle inequality", and what if we remove the assumption that $\alpha_k$ are bounded? Feb 9, 2021 at 20:38
• @Pinelis - edited to note that indeed I was wrong to deduce boundness Feb 9, 2021 at 22:05