15
$\begingroup$

Motivated by this question, I remembered a question I was curious about sometime which I am sure has some easy and nice example for it as well, which I just can't think of for some reason. I want an example of a power series that is not differentially algebraic. A differential algebraic power series is a series $f(t)$ satisfying an equation $P(t,f(t),f'(t),\ldots,f^{(k)}(t))=0$ for some $k$ and some polynomial $P$ in $k+2$ variables.

Update: examples in the comments below ($\sum t^{n^n}$, $\sum t^{2^n}$) make me ask a refinement (of a sort) for the original question: these examples are reminiscent of all those Liouville-flavoured examples of transcendental numbers, - I wonder if there is a Liouville-flavoured proof, stating that if the polynomial P is of given (multi)degree, some inequality holds that is obviously impossible for the series above?

Update 2: there are quite a few examples now, and I am tempted to accept the $\sum t^{n^n}$ answer since the example itself is easy and it came together with an easy explanation. I wonder what are other general approaches besides the ones that are exhibited in answers here (looking at p-adic norms of coefficients and looking at powers of $t$ with nonzero coefficients).

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Vladimir, you can take any function, for example the gamma function, which does not satisfy an algebraic differential equation over $\mathbb C(t)$ and expand it into a power series at some point. $\endgroup$
    – Wadim Zudilin
    Commented Apr 14, 2010 at 12:22
  • $\begingroup$ And the proof for gamma has to be explained in Gelfond's book "Ischislenie konechnyh raznostej". $\endgroup$
    – Wadim Zudilin
    Commented Apr 14, 2010 at 12:25
  • $\begingroup$ Wadim: sure, I was rather curious about what are simple and natural methods to check it for a function. I guess two methods are explained in answers below: that Thue-Siegel-Roth-type theorem and the p-adic approach. I don't have Gelfond's book in proximity. Could you give a hint on how Gamma is handled? $\endgroup$
    – Vladimir Dotsenko
    Commented Apr 14, 2010 at 16:28
  • 1
    $\begingroup$ @Vladimir: I found the book (in djvu) but could not find the theorem there. I have to explore more. As far as I remember a similar result was shown for Riemann's zeta. As for Osgood's results, I wouldn't recommend them for study: I believe the proofs there are simply wrong. Gregory Chudnovsky later gave a much better exposition of the Siegel-Roth for solutions of differential equations. This argument indeed provides one with an explicit construction of functions which are not "differential algebraic". $\endgroup$
    – Wadim Zudilin
    Commented Apr 16, 2010 at 10:22
  • 1
    $\begingroup$ However the functions so constructed are "unnatural" and the method does not work for known examples, like gamma and zeta. A concrete series for which the non-existence of algebraic differential equation over $\mathbb C(q)$ remains open (as far as I know) is $\sum_{n\ge1}\tau(n)q^n$ where $\tau(n)$ is the number of divisors of $n$. A very similar function $\sum_{n\ge1}\sigma(n)q^n$ where $\sigma(n)$ denores the sum of divisors satisfies an algebraic DE... $\endgroup$
    – Wadim Zudilin
    Commented Apr 16, 2010 at 10:26

6 Answers 6

Reset to default
7
$\begingroup$

You'd be better off in characteristic zero, for $f^{(p)}(t)=0$ in characteristic $p$. Then the sea of zeroes example $\sum_n t^{n^n}$ will do the trick. For large enough $n$, there will be a cluster of non-zeroes in degrees $kn^n-m$ for small (and bounded) $k$ and $m$, "reachable" only by products of $(t^{n^n})^{(s)}$, the same $n$, bounded $s$. Their vanishing will give infinitely many linear relations on the coefficients of $P$, which you can explicitly write down and see that there are no nonzero solutions on coefficients.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Sounds like a plan indeed. This example, as well as the example in the other comment (with $2^n$'s - it probably works for a similar reason) makes me think of all those Liouville-flavoured examples of transcendental numbers, - I think I might make an update to my question with another question arising from that! $\endgroup$
    – Vladimir Dotsenko
    Commented Apr 14, 2010 at 11:23
7
$\begingroup$

In Exercise 6.63(c) of Enumerative Combinatorics, vol. 2, I raise the question of whether one can ever have $\sum b_i x^{n_i}$ differentially algebraic (DA) (over $\mathbb{C}$) if $b_i\neq 0$ and $\lim_{i\to \infty}i^2/n_i=0$. In particular, is $\sum x^{n^3}$ DA?

Improve this answer
$\endgroup$
4
$\begingroup$

Yet some more examples: the ordinary generating function for the Bell numbers, see Martin Klazar. Or, Flajolet, Gerhold, Salvy.

I think it would be nice to have some kind of survey of results and methods. In combinatorics, I frequently encounter generating functions that do not seem to be differentially algebraic, but I have no idea how to prove that. An example would be the generating functions for walks in the quarter plane with certain step sets, see Bostan, Kauers. Maybe a little bit more philosophical: is it true that "natural" generating functions are either differentially finite or differentially transcendent?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the links! "is it true that "natural" generating functions are either differentially finite or differentially transcendent?" I would not think so - see the sec(t) example mentioned above - if that is not "natural" enough, think of up-down permutations... $\endgroup$
    – Vladimir Dotsenko
    Commented Apr 14, 2010 at 20:12
  • $\begingroup$ Yes, there are some examples. Two more are integer partitions and n^n/n!. But it seems that there are not "too many" (meaning: naturally occurring, whatever that means)... $\endgroup$
    – Martin Rubey
    Commented Apr 15, 2010 at 13:01
3
$\begingroup$

I've always seen the canonical example for this to be $\sec x$. For this and more examples, see R. Stanley's excellent article on the subject, "Differentiably finite power series"

Oops, above I am referring to D-finite, power series, but you are referring to D-algebraic power series. It is proved in "A gap theorem for power series solutions of algebraic differential equations" by L. Lipshitz and L. Rubel that $$\sum_{n=0}^{\infty}x^{2^n}$$ is not D-algebraic.

Another function that was proven not to be D-algebraic is the Gamma function, and this fact is due to Holder.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I am sorry but I don't understand. It clearly satisfies $(1/f)^{''}+1/f=0$ which you can multiply by $f^4$ to get a polynomial differential equation. $\endgroup$
    – Bugs Bunny
    Commented Apr 14, 2010 at 10:40
  • $\begingroup$ Very true! I realized that I had misread the question, right after I posted that answer. $\endgroup$
    – Gjergji Zaimi
    Commented Apr 14, 2010 at 10:55
  • $\begingroup$ I updated the original question with an additional one motivated by your first example, and an example from the other comment. Do you by any chance know how the proof for Gamma goes? What intuition of Gamma should one use? $\endgroup$
    – Vladimir Dotsenko
    Commented Apr 14, 2010 at 11:29
  • 1
    $\begingroup$ For the gamma function, you can check out fe.math.kobe-u.ac.jp/FE/Free/vol19/fe19-1-7.pdf $\endgroup$
    – Gjergji Zaimi
    Commented Apr 14, 2010 at 20:27
  • $\begingroup$ Ah okay, so the property of Gamma that is crucial is that for $g(t)=Gamma'(t)/Gamma(t)$ satisfies $g(t+1)-g(t)=h(t)$ where $h$ is a rational function (some additional properties $h$ has to have are in the paper, just wanted to extract a highlight). $\endgroup$
    – Vladimir Dotsenko
    Commented Apr 14, 2010 at 20:38
3
$\begingroup$

C. Osgood proved a Liouville type theorem for algebraic differential equations.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot, that was really helpful! My search brought up an even stronger result, in the spirit of Thue-Siegel-Roth: MR048568 Osgood, Charles F. Concerning a possible ``Thue-Siegel-Roth theorem'' for algebraic differential equations. Number theory and algebra, pp. 223--234. Academic Press, New York, 1977. $\endgroup$
    – Vladimir Dotsenko
    Commented Apr 14, 2010 at 16:18
3
$\begingroup$

An example is given by $$f(t)=\sum_{n=1}^\infty \frac{(n-1)!}{n^n}t^n$$ see http://arxiv.org/abs/math.CA/0210472

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ In case someone is curious about the method: the authors refer to the paper MR0604044, Sibuya, Yasutaka; Sperber, Steven, Arithmetic properties of power series solutions of algebraic differential equations. Ann. of Math. (2) 113 (1981), no. 1, 111--157. There for a series whose coefficients are algebraic numbers it is proved that if it is differentially algebraic, then it is convergent in some neighborhood of zero w.r.t. every non-Archimedean valuation. $\endgroup$
    – Vladimir Dotsenko
    Commented Apr 14, 2010 at 16:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .