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)\|<N^{-1}. $$ 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)\|<N^{-1}. $$ That is, can we bound the number of these "monomials" required to approximate the function $\exp$.

  • $\begingroup$ 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) $\endgroup$
    – Conrad
    Feb 9 at 18:20
  • $\begingroup$ @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. $\endgroup$ Feb 9 at 18:21
  • 1
    $\begingroup$ great - now it's clear and I agree that monomials sounds accurate - definitely an interesting problem $\endgroup$
    – Conrad
    Feb 9 at 18:23
  • $\begingroup$ 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? $\endgroup$ Feb 9 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<a<b$. 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).

  • $\begingroup$ Do you happen to know a reference to this theorem? $\endgroup$ Feb 12 at 8:41
  • $\begingroup$ No I do not. Though I doubt a lot that it is new. Possibly you may ask Khovansky who wrote a book on fewnomials. $\endgroup$ Feb 12 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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.