# Expansions of iterated, or nested, derivatives, or vectors--conjectured matrix computation

The entry OEIS A139605 (also related OEIS A145271) has a matrix computation for the partition polynomials that represent the expansions of iterated derivatives, or vectors in differential geometry,

$$(g(x)D_x)^n.$$

The formula section of A139605 contains the matrix formula. Multiply the $$n$$-th diagonal (with $$n=0$$ the main diagonal) of the lower triangular Pascal matrix A007318 by $$g_n = D_x^n g(x)$$ to obtain the matrix $$VP$$ with $$VP_{n,k} = \binom{n}{k}g_{n-k}$$. Then $$(g(x)D)^n = (1, 0, 0,..) [VP \dot \; S]^n (1, D, D^2, ..)^T,$$ where S is the shift matrix A129185, representing differentiation in the divided powers basis $$x^n/n!$$.

Example:

$$(g(x)D_x)^3$$

$$= (1, 0, 0, 0) [VP \dot \; S]^3 (1, D, D^2, D^3)^T$$

$$= \begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & g_0 & 0 & 0 \\ 0 & g_1 & g_0 & 0\\ 0 & g_2 & 2g_1 & g_0 \\ 0 & g_3 & 3g_2 & 3g_1 \end{pmatrix}^3 \begin{pmatrix} 1 \\ D \\ D^2 \\ D^3 \end{pmatrix}$$

$$= [g_0g_1^2 + g_0^2 g_2] D + 3 g_0^2g_1 D^2 + g_0^3D^3$$

And, the pdf Mathemagical Forests gives a diagrammatic method for creating forests of trees through "natural growth" that represent the partition polynomials.

I have either lost a proof of the validity of this formula or got sidetracked before I developed one.

Question:

Can someone prove this conjecture?

Some background:

The refined Eulerian numbers (RENs) of A145271 are related analytically to the compositional inversion of functions and formal generating series and to flow fields generated by tangent vectors. The $$n$$-th row of RENs are the numerical coefficients of the expansion of $$(g(x)\frac{d}{dx})^ng(x)$$ in terms of the monomials in the derivatives of $$g(x)$$, i.e.,

$$g_k=\frac{d^k}{dx^k}g(x).$$

For example,

$$(g(x)\frac{d}{dx})^3g(x) = 1 g_0^1 g_1^3 + 4 g_0^2 g_1^1 g_2^1 + 1 g_0^3 g_3^1.$$

With $$(\omega,x) = (f(x),f^{(-1)}(\omega))$$ and $$g(x) = 1/f^{'}(x)$$,

$$\exp[t g(x)d/dx]x = \exp[td/d\omega]f^{(-1)}(\omega) = f^{(-1)}(t+\omega)=f^{(-1)}(t+f(x)).$$

Evaluated at the origin of $$x$$, this gives the compositional inverse

$$\exp[tg(x)d/dx] x |_{x=0}=f^{(-1)}(t).$$

1) MO-Q Guises of the refined Eulerian numbers generated by tangent vectors

2) MO-Q Important formulas in combinatorics

3) MO-Q Why is there a connection between enumerative geometry and nonlinear waves?

• – Tom Copeland Aug 6 '19 at 17:19
• Nice question. Here is a sketch (please check): Let me use infinite vectors and matrices instead of your finite ones. For each differential operator $E$, let $h_E$ be the infinite column vector $\begin{pmatrix} D^0 E \\ D^1 E \\ D^2 E \\ \cdots \end{pmatrix}$, and let $U$ be your matrix $VP \cdot S$. Then, your claim is that the first entry of the column vector $U^n h_1$ is $\left(gD\right)^n$. Let me claim something stronger: $U^n h_1 = h_{\left(gD\right)^n}$. To prove this, it clearly suffices to show that $U h_E = h_{gDE}$ for each differential operator $E$. How ... – darij grinberg Aug 6 '19 at 18:26
• ... to prove this identity? Well, for each $i$, the $i$-th entry of $Uh_E$ is $\sum\limits_{k=0}^i \dbinom{i}{k} g_{i-k} D^{k+1} E$, while the $i$-th entry of $h_{gDE}$ is $D^i gDE$. We need to prove that these two entries are equal. It is clearly enough to show that $\sum\limits_{k=0}^i \dbinom{i}{k} g_{i-k} D^k = D^i g$. Now, this can be proven by straightforward induction on $i$, like the binomial formula. I want to say it also follows from the binomial formula, but right now I don't see how (probably a simple exercise in the umbral viewpoint). – darij grinberg Aug 6 '19 at 18:28
• @darijgrinberg Would you just paste this into an answer please? – Tom Copeland Aug 6 '19 at 18:56
• @darijgrinberg Very nice. – Tom Copeland Aug 6 '19 at 19:06

I have finally written up the proof in detail. It is in my note

Your result is a particular case of Theorem 4.2. More precisely, you get it from Theorem 4.2 if you set $$\mathbb{L}$$ to be the ring of differential operators (whatever kind of differential operators you are considering), $$\mathbb{K}$$ to be the base ring, $$a$$ to be the differentiation operator (which is your $$D$$), $$x$$ to be the "multiplication by $$t$$" operator (you use $$x$$ for what I call $$t$$, but I keep them separate because my ring $$\mathbb{L}$$ doesn't have to contain the polynomial ring $$\mathbb{K}\left[t\right]$$), and $$h$$ to be the identity map.

I derive this from a more general formula (Theorem 2.7), which expresses $$\left(ba\right)^n$$ as a matrix product when $$a$$ and $$b$$ are two arbitrary elements of a noncommutative ring.

I work in a setting that allows the matrices to be finite or infinite as the reader prefers. This is responsible for a lot of the length of the note (as I have to set up an appropriate ring of infinite matrices on which multiplication is defined and associative, but also mess around with partial equalities in the case of finite matrices because the finite version of the shift operator doesn't behave as well as the infinite one). I hope the exposition is not completely wasted; meanwhile I trust you know what to skip and what to skim.

• Nice general algebraic formulation. Yes, please arxiv it and I'll add the ref to several OEIS entries. I wonder how A133314, relating the inverse of the lower triangular matrices to the reciprocal of the e.g f.of the first column, might play into the algebra (related to Appell polynomials, which can be related to a Weyl algebra through their raising and lowering ops.) – Tom Copeland Aug 23 '19 at 12:10
• Two interesting special cases are $g(x) = t + e^x -1$ and $g(x) = (1+cx)(1+dx)$, which will generate the Eulerian polynomials A008292 in $t$ and in the indeterminates $c$ and $d$ through A145271. The matrices are particularly simple in these cases. Might be interesting to explore in your general formulation. – Tom Copeland Aug 26 '19 at 0:09
• @TomCopeland: It's on the arXiv now. – darij grinberg Aug 27 '19 at 5:45
• Thanks, Darij. I linked this question and the arXiv to the associated two main entries in the OEIS and also on my blog with some background notes tcjpn.wordpress.com/2019/09/01/… – Tom Copeland Sep 1 '19 at 18:09
• If we let $a=L$ and $b = g(R)$, where $L$ and $R$ are the lowering and raising ops of a Sheffer polynomial sequence $p_n(x)$, i.e., $L p_n(x)=np_{n-1}(x)$ and $Rp_n(x)=p_{n+1}(x)$; the Pincherle derivative gives the commutator $[L,g(R)]=dg(R)/dR$ and $U_b$ acquires the form of the original formulation with $x$ replaced by $R$ and $D$ by $L$. Should be equivalent since $x$ and $D$ are the raising and lowering ops for the prototypical binomial Sheffer sequence, the powers sequence. – Tom Copeland Sep 1 '19 at 23:43

[This is a copy of Darij Grinberg's answer in the comments above.]

Nice question. Here is a sketch of a proof: Let me use infinite vectors and matrices instead of your finite ones. For each differential operator $$E$$, construct the infinite column vector

$$h_E =\begin{pmatrix} D^0E \\ D^1E \\ D^2E \\ D^3E \\ .. \end{pmatrix}$$

and let

$$U=VP⋅S .$$

Then, your claim is that the first entry of the column vector $$U^nh_1$$ is $$(gD)^n$$. Let me claim something stronger:

$$U^nh_1=h_{(gD)^n}.$$

To prove this, it clearly suffices to show that

$$Uh_E=h_{gDE}$$

for each differential operator $$E$$.

How to prove this identity? Well, for each $$i$$, the $$i$$-th entry of $$Uh_E$$ is given by

$$(Uh_E)_i=\sum_{k=0}^i \binom{i}{k} g_{i−k}D^{k+1}$$

while the $$i$$-th entry of $$h_{gDE}$$ is given by

$$(h_{gDE})_i=D^igDE .$$

We need to prove that these two entries are equal. It is clearly enough to show that

$$\sum_{k=0}^i \binom{i}{k}g_{i−k} D^k = D^i g .$$

Now, this can be proven by straightforward induction on $$i$$, like the binomial formula. I want to say it also follows from the binomial formula, but right now I don't see how (probably a simple exercise in the umbral viewpoint).

• As in my comments above, $$e^{tD}f(x)g(x)= f(t+x)g(t+x)= [e^{tD} f(x)][e^{tD}g(x)] = e^{t(D_1+D_2)}f(x)g(x)$$ where $D_1$ commutes with $D_2$ and acts only on the first function in a product of two functions and $D_2$ acts only on the second as derivatives, so the binomial expansion holds for $$D^n = (D_1+D_2)^n .$$ – Tom Copeland Aug 7 '19 at 21:52
• @darijgrinberg Please just copy this answer and post under your name – Tom Copeland Aug 7 '19 at 21:55

Here is probably something close to my original thinking on the identity.

Taylor series analysis gives us, with $$D_x^k g(x) = \frac{d^k}{dx^k} g(x)= g_k$$,

$$g(t+x) = e^{tD_x}g(x)= \sum_{k \geq 0} g_k\frac{t^k}{k!}.$$

Then

$$g(x+t)g'(x+t)= g(x+t)D_xe^{tD_x}g(x)$$

$$= \sum_{k \geq 0} g_k\frac{t^k}{k!}D_x\sum_{k \geq 0} g_k\frac{t^k}{k!}$$

can be written as a binomial convolution (umbrally, $$e^{a.t}e^{b.t}=e^{(a.+b.)t}$$) in (singly infinite) matrix form in the divided powers basis $$\frac{t^k}{k!}$$ as

$$\begin{pmatrix} g_0 & 0 & 0 & 0 \\ g_1 & g_0 & 0 & 0\\ g_2 & 2g_1 & g_0 & 0\\ g_3 & 3g_2 & 3g_1 & g_0 \end{pmatrix} \begin{pmatrix} g_1\\ g_2 \\ g_3 \\ g_4 \end{pmatrix}$$ $$= \begin{pmatrix} g_0 & 0 & 0 & 0 \\ g_1 & g_0 & 0 & 0\\ g_2 & 2g_1 & g_0 & 0\\ g_3 & 3g_2 & 3g_1 & g_0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 1 \\ D \\ D^2 \\ D^3 \end{pmatrix} g(x)$$

$$= \begin{pmatrix} 0 & g_0 & 0 & 0 \\ 0 & g_1 & g_0 & 0\\ 0 & g_2 & 2g_1 & g_0 \\ 0 & g_3 & 3g_2 & 3g_1 \end{pmatrix} \begin{pmatrix} 1 \\ D \\ D^2 \\ D^3 \end{pmatrix} g(x)$$

Repeating operation $$n$$ times by $$g(x+t)D_x$$ and ultimately setting $$t=0$$, or, equivalently, extracting the first term in the resulting column vector of operators acting on $$g(x)$$, gives us

$$[g(x)D_x]^n .$$

The full repeated (infinite) matrix operator that acts on $$g(x)$$ is a rep in the basis $$\frac{t^k}{k!}$$ of

$$[g(x+t)D_x]^n e^{tD_x}.$$

Letting $$\omega = f(x)$$, $$x = f^{-1}(\omega)$$, and $$g(x) = 1/f'(x)$$, for $$h(x)$$ an arbitrary analytic function,

$$\exp[ug(x+t)D_x]e^{tD_x}h(x)= \exp[u\frac{d}{d(\omega(x+t))}]h(x+t)$$

$$= \exp[u\frac{d}{d(\omega(x+t))}]h[f^{-1}[\omega(x+t)]]= h[f^{-1}[\omega(x+t)+u]]$$

$$= h[f^{-1}[f(x+t)+u]] = e^{tD_x} h[f^{-1}[f(x)+u]]$$

$$= e^{tD_x} \exp[ug(x)D_x] h(x),$$

so (as we might surmise initially), equating coefficients of $$u^n$$,

$$[g(x+t)D_x]^n e^{tD_x} = e^{tD_x} [g(x)D_x]^n,$$

implying the $$m-$$th component of the operator matrix rep, the operator coefficient of $$\frac{t^m}{m!}$$ is

$$D_x^m [g(x)D_x]^n,$$

in agreement with Grinberg's general result.

More simply, the proof follows through a double translation--a similarity transformation;

$$e^{-tD_x} [g(x+t)D_x]^n e^{tD_x} h(x) =[g(x)D_x]^n h(x)$$

since $$D_x = \frac{d}{dx}= \frac{d}{d(x+t)} = D_{x+t}$$.