## 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 2010 at 19:54 Do you have an specific mathematical question in mind that this structure might help you solve? – S. Carnahan♦ Apr 16 2010 at 21:16 Scott: yes, guessing a formula for a given sequence. – Martin Rubey Apr 17 2010 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 2010 at 7:39

I am not quite sure whether the question is about a "natural" graded algebra which is infinitely generated, or finitely generated algebras are fine as well. Because there are nice examples of algebras of multiple zeta values, but also of multiple polylogarithms and of finite multiple harmonic sums, as well as the algebra of classical modular forms. The latter gives rise to a certain structure which is presumably richer than the algebra of differential monomials, and I could probably try to explain this point.

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.

-
 Hi Wadim, did you see the answers to mathoverflow.net/questions/22777 on the lattice point close to an intersection? – Will Jagy Apr 30 2010 at 1:20 Yes Will, I follow that question and have realized that your answer is not there any more. I would be happy to see a clear algorithm but for the moment the best answer is still too theoretical to me to be implemented (even I am not the author of the problem). – Wadim Zudilin Apr 30 2010 at 4:03 Wadim, many thanks for your answer! I admit that I accepted without reading all details, to make sure the bounty is properly awarded. Thus, could you expand a bit? In particular, it is not yet clear to me which monomials I should/could consider, and why this set of monomials would be finite if I only consider (say) D and D_2. Already the set of monomials in the usual differentiation operator is infinite, so surely I misunderstood... – Martin Rubey Apr 30 2010 at 11:04 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 2010 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 2010 at 12:10