This question is the continuation of the previous one. In the article about the integration of analytical polynomial - time computable function $f(x)$ with the Taylor series $$f(x) = \sum_{n=0}^{\infty} \frac{f^{(n)}(a)}{n!}(x-a)^n $$ two constants: $c$ (page 44) and $M$ (page 50) are mentioned to have properties that $$\lvert a_n \rvert < 2^{cn}$$ $$2^c \geq R$$ And $$\lvert a_n \rvert \leq \frac{M}{R^n}$$ where $R$ is the radius of convergence. The questions: as I see, we have to find a constant $c$ in order to build an algorithm, is it right? Is there a way to find it? Is it unique? Same questions (excluding the first one) are for M.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The article gives an existence proof of an algorithm, but does not say anything about effectively using that algorithm. In practice, given an arbitrary real analytic function $f$ one cannot determine the value of $c$ short of actually calculating the series $a_n$.
The numbers $c$ and $M$ are certainly not unique, as $c+1$ and $M+1$ both satisfy the required conditions equally well.
Note that the requirement $R \leq 2^c$ is almost trivial: since we are interested in functions on $[-1,1]$ implicitly $R \leq 1$. So as long as $c$ is selected $\geq 0$ the requirement $R \leq 2^c$ always holds. For the "existence" of an algorithm it is therefore not necessary to impose $R \leq 2^c$. Though I am wondering whether $R \leq 2^c$ is a misstatement in the paper...
I think it may be better to think of Theorem 2 as the following:
Given a sequence of real numbers $a_n$ bounded by $2^{cn}$, such that the power series $f(z) = \sum a_n z^n$ has non-zero radius of convergence, and such that the resulting $f$ is polynomial-time computable, then the sequence $a_n$ is polynomial-time computable. Furthermore, the polynomial used in Definition 2 (for polynomial-time computability of a sequence) depends only on the constant $c$ and the polynomial used in Definition 3 (for the polynomial-time computability of the function $f$).
