MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 :)

share|cite|improve this question
Most "elementary sequences" are restriction of holomorphic functions, so you can use ODEs and such on them. – Mariano Suárez-Alvarez Dec 3 '11 at 2:52
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. – fedja Dec 3 '11 at 4:15
One can prove, for example, that $F_n$ defined above is not a rational function in $n$. – Gerald Edgar Dec 3 '11 at 14:23

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.

share|cite|improve this answer
"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 :). – fedja Dec 3 '11 at 13:21
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. – fedja Dec 3 '11 at 13:56
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! – fedja Dec 3 '11 at 16:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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