14
$\begingroup$

I'm pretty sure that the sequences like $F_n=\sum_{k=1}^n \frac 1k$ are not traces of elementary functions on positive integers (take any reasonable definition of "elementary" you want, just make sure that all high school formulae are there). However, all proofs of non-elementarity I know make heavy use of differential fields and I do not see what and how to differentiate in this discrete setting. Any ideas, suggestions, or references?

P.S. I posted it on AoPS as well but then decided that there may be a slightly better chance to get an answer here :)

$\endgroup$
3
  • $\begingroup$ Most "elementary sequences" are restriction of holomorphic functions, so you can use ODEs and such on them. $\endgroup$ Dec 3, 2011 at 2:52
  • $\begingroup$ You mean "meromorphic in a neighborhood of the real line". OK, I'm happy with assuming that my elementary function field consists only of such functions (this excludes $\sin(1/x)$, by the way, but we can handle this and other similar stuff later). But how one can derive any ODE from knowing only the values at the positive integers still remains a mystery to me. $\endgroup$
    – fedja
    Dec 3, 2011 at 4:15
  • $\begingroup$ One can prove, for example, that $F_n$ defined above is not a rational function in $n$. $\endgroup$ Dec 3, 2011 at 14:23

1 Answer 1

2
$\begingroup$

I am not sure what you mean by "traces", but there is certainly a theory of non-elementarity in the difference equation setting. One of the canonical early papers is:

MR1187234 (94a:39006) Petkovšek, Marko(SV-LJUB) Hypergeometric solutions of linear recurrences with polynomial coefficients. (English summary) J. Symbolic Comput. 14 (1992), no. 2-3, 243–264.

And there is also Wilf-Zeilberger and the book of Petkovsek and Zeilberger (A=B) which probably covers this in greater detail. The methods are still those of differential algebra.

$\endgroup$
3
  • $\begingroup$ "Trace" here is just a synonym of "restriction" (perhaps, with a possibility that the function is not defined at finitely many integer points). The question is how to show that there exist no elementary function $f$ such that $F_n=f(n)$ for (almost) all $n\in\mathbb N$. I'll surely take a look at the references you mentioned :). $\endgroup$
    – fedja
    Dec 3, 2011 at 13:21
  • $\begingroup$ Petkovsek seems to be far short of what I would really like to see (he cannot even cover $e^{1/x}$ as "elementary"). A=B looks more exciting though it'll certainly take me some time to digest it and to understand if it really leads anywhere near where I want to land. $\endgroup$
    – fedja
    Dec 3, 2011 at 13:56
  • 2
    $\begingroup$ Alas, the definition of "elementary" in "A=B" also seems to be "a finite sum of hypergeometric terms", which results in a beautiful theory but is quite orthogonal to what I'm looking for here. Still it seems a good book to read. Thanks for attracting my attention to it! $\endgroup$
    – fedja
    Dec 3, 2011 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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