most recent 30 from http://mathoverflow.net 2013-05-23T23:04:13Z http://mathoverflow.net/feeds/question/21314 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/21314/an-example-of-a-series-that-is-not-differentially-algebraic Vladimir Dotsenko 2010-04-14T09:09:56Z 2010-04-14T20:20:50Z

<p>Motivated by <a href="http://mathoverflow.net/questions/21290/whats-an-example-of-a-transendental-power-series" rel="nofollow">this question</a>, 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. </p> <p><b>Update:</b> 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?</p> <p><b>Update 2:</b> 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).</p>

http://mathoverflow.net/questions/21314/an-example-of-a-series-that-is-not-differentially-algebraic/21319#21319 Gjergji Zaimi 2010-04-14T10:23:42Z 2010-04-14T10:50:42Z

<p><strike>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, <a href="http://www-math.mit.edu/~rstan/pubs/pubfiles/45.pdf" rel="nofollow">"Differentiably finite power series"</a> </strike></p> <p>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.</p> <p>Another function that was proven not to be D-algebraic is the Gamma function, and this fact is due to Holder.</p>

http://mathoverflow.net/questions/21314/an-example-of-a-series-that-is-not-differentially-algebraic/21321#21321 Bugs Bunny 2010-04-14T10:36:09Z 2010-04-14T10:36:09Z

<p>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.</p>

http://mathoverflow.net/questions/21314/an-example-of-a-series-that-is-not-differentially-algebraic/21333#21333 Felipe Voloch 2010-04-14T12:39:09Z 2010-04-14T12:39:09Z

<p>C. Osgood proved a Liouville type theorem for algebraic differential equations.</p>

http://mathoverflow.net/questions/21314/an-example-of-a-series-that-is-not-differentially-algebraic/21334#21334 Guy Katriel 2010-04-14T12:47:48Z 2010-04-14T12:47:48Z

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

http://mathoverflow.net/questions/21314/an-example-of-a-series-that-is-not-differentially-algebraic/21351#21351 Richard Stanley 2010-04-14T16:07:06Z 2010-04-14T16:07:06Z

<p>In Exercise 6.63(c) of <em>Enumerative Combinatorics</em>, 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?</p>

http://mathoverflow.net/questions/21314/an-example-of-a-series-that-is-not-differentially-algebraic/21356#21356 Martin Rubey 2010-04-14T16:53:52Z 2010-04-14T16:53:52Z

<p>Yet some more examples: the ordinary generating function for the Bell numbers, see <a href="http://kam.mff.cuni.cz/~klazar/bell.pdf" rel="nofollow">Martin Klazar</a>. Or, <a href="http://www.fam.tuwien.ac.at/~sgerhold/pub_files/papers/non-holonomic2.pdf" rel="nofollow">Flajolet, Gerhold, Salvy</a>.</p> <p>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 <a href="http://arxiv.org/abs/0811.2899" rel="nofollow">Bostan, Kauers</a>. Maybe a little bit more philosophical: is it true that "natural" generating functions are either differentially finite or differentially transcendent?</p>