2
$\begingroup$

Given any computable function $f(x)$, is there an algorithm to find a set of coefficients $a_n$, such that
i) $g(x)=\sum_{n=1}^{n=\infty} a_nx^n$ converges for all $x>1$
ii) $g(x)$ eventually dominates $f(x)$

If not, is there a way to approach this boundary from above or below?

1 Answers 1

1

If you take $f$ to be a computable function from $\Bbb Z_{>0}$ to $\Bbb Z_{>0}$, the answer is yes. Define $h:\Bbb Z_{>0}\to \Bbb Z_{>0}$ recursively by $h(1)=f(1)$, $h(n+1)=\max(f(n+1),h(n)+1)$ if $n\ge 1$. Then $g(x):=\sum_{n\ge 1} \frac{x^{h(n)}}{n^{h(n)}}(h(n)+1)$ converges everywhere (by the root test), and for all $m\in \Bbb Z_{>0}$, looking at the $m$th term of the series, $g(m)\ge h(m)+1>f(m).$