# beyond differentially algebraic power series

In a recent question, we learned about the existence of functions that do not satisfy any algebraic differential equation.

One nice property of such equations is that there is a good way to enumerate a basis: we can produce the stream of "monomials" $\left(\prod_i D^{\lambda_i-1}f(x)\right)_\lambda$, where $D$ is the differentiation operator and $\lambda=(\lambda_1,\lambda_2,\dots)$ runs over the integer partitions in lexicographic order: $$1, f(x), f(x)^2, f'(x), f(x)^3, f(x)f'(x), f''(x), f(x)^4, f(x)^2f'(x),\dots$$

I'm wondering: is there a "natural" class of equations, more general than ADEs, that has a similar basis. (Natural meaning: equations that specify many functions occurring in "nature")? Or, alternatively, just another class of equations.

I realise this is vague, please bear with me...

edit: I should add that I'm aware of "algebraic recurrences" (i.e., shift instead of differentiation) and "Mahler-type functional equations" (i.e., $f(x^{k+1})$ instead of $f(x)^{(k)}$).

Martin Klazar mentions that a few interesting sequences (eg. the ordinary generating function for Bell numbers) satisfy functional equations of the form $$p_1(x)f(x)=p_2(x)+p_3(x)f(\frac{x}{1-x}),$$ with polynomials p1, p2, p3 (and concludes that they are not differentially algebraic), but I'm not sure how common such equations are.

edit: the motivation for this question comes from the desire of being able to guess a formula (or recurrence, differential or functional equation) for a given sequence (of numbers or polynomials, etc.), as pioneered be GFUN, see also Section 7 in my preprint with Waldek Hebisch.

For example, given the first few (say 100) terms of the sequence, we compute it's (truncated) generating function $f_1 := f(x)$, and also $f_2 := f(x)^2, f_3 := f'(x), f_4 := f(x)^3, f_5 := f(x)f'(x), f_6 := f''(x), f_7 := f(x)^4, f_8 := f(x)^2f'(x), \dots$. We fix the maximal degree, say $N$ of the coefficient polynomials $p_1, p_2, \dots, p_m$, and then try to solve the linear system of equations obtained by equating coefficients in $$ord(p_1 f_1 + \dots + p_m f_m)\geq\sigma$$ for large sigma. If we get a solution, and the given sequence is somehow naturally defined, chances are good that the equation holds for all terms of the sequence.

-
Well, you can replace D with any family of linear operators satisfying some kind of product rule, right? I'm not really sure what this kind of generality gets you except perhaps in the theory of sequences of binomial type, etc. –  Qiaochu Yuan Apr 16 '10 at 19:54
Do you have an specific mathematical question in mind that this structure might help you solve? –  S. Carnahan Apr 16 '10 at 21:16
Scott: yes, guessing a formula for a given sequence. –  Martin Rubey Apr 17 '10 at 6:20
@Qiaochu: sorry for answering late - I thought I did, but it seems that I pressed the wrong button... So, here goes: Actually, I don't think I absolutely need any specific properties of the operator, although such properties are of course nice to have. What do you have in mind with sequences of binomial type? –  Martin Rubey Apr 23 '10 at 7:39

The Eisenstein series $E_2=1-24\sum_{n=1}\sigma_1(n)q^n$, $E_4=1+240\sum_{n=1}\sigma_3(n)q^n$ and $E_6=1-504\sum_{n=1}\sigma_5(n)q^n$, where $\sigma_k(n)=\sum_{d\mid n}d^k$, generate a differentially stable ring over $\mathbb Q$ with respect to the differentiation $D=q\dfrac{d}{dq}$ (a result usually attributed to Ramanujan). The weights $2,4,6$ are assigned to $E_2,E_4,E_6$ respectively, and $D$ increases the weight by $2$. The graded ring $\mathbb Q[E_2,E_4,E_6]$ possesses an additional structure coming from the functional equations for replacing $q$ by $q^k$ where $k$ is a positive integer, although it's very hard to write down the structure explicitly. Let me call the corresponding scale operators (substitutions $q^k$ for $q$) $D_k$. They do not change weights.
The counterpart consists of the infinite family $F_{2m+1}(q)=\sum_{n=1}^\infty\sigma_{2m}(n)q^n$, $m=0,1,2,\dots$, which are known to be linearly independent over $\mathbb Q$ and even over the field of meromorphic functions on $\mathbb C$. We can formally assign the weight $2m+1$ to each $F_{2m+1}(q)$, although there could be reasons to normalize them in a way used for the Eisenstein series. Again, the differential operator $D$ increases weights by 2, and the open problem here is to show that the $F_{2m+1}(q)$ are all algebraically differentially independent over $\mathbb C$ (or $\mathbb Q$). An expanded version of the problem is to show that the ring of all $D$- and $D_k$-monomials have no nontrivial relations at all. In a sense this includes both the algebraic differential structure from the problem, as well as all kind of Mahler-type equations. If one restricts to considering $D$- and $D_2$-monomials (or $D_k$ monomials for a finite set of $k$'s), the corresponding set of monomials of finite weight will be finite.
Martin, I was finally surprised by the prize... The set of differrence-differential monomials in a fixed weight will be finite (if the set of operators is finite); in your starting example $|\lambda|$ could be such a weight. The most natural (to me!) example, the ring of quasimodular forms $\mathbb Q[E_2,E_4,E_6]$, has a different grading. I am trying to write down explicitly those $E_j(q^2)$ by means of $E_j(q)$ (for seeing how $D_2$ acts) but it seems to be nontrivial enough. After submitting the answer I've realized that multiple zeta values might be a better example. –  Wadim Zudilin Apr 30 '10 at 11:54
In the case of $F_{2m+1}(q)$ I am probably to speculative in adding $D_k$'s: already $D$ gives a rich structure. If we assign weight $2k+2m+1$ to each $D^kF_{2m+1}(q)$, then the set of monomials $D^{k_1}F_{2m_1+1}\dots D^{k_s}F_{2m_s+1}$ of given weight is finite, so one may introduce their ordering. In your example you have a single function which does not satisfy an algebraic differential equation, while here (sorry, presumably) no relations between all those monomials could be possible. Maybe, this is more concrete... –  Wadim Zudilin Apr 30 '10 at 12:10