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

Question

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).$$

See also

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?

Answer 1

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

• Darij Grinberg, Commutators, matrices and an identity of Copeland, also available as arXiv:1908.09179v1.

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.

Answer 2

[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).

Answer 3

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

Edit 1/26/2024, changing notation and belatedly filling in some steps for clarification:

Taylor series analysis gives us, with, e.g., $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, with the diff op $G_{x,t} = g(x+t)D_x$ and suitable analytic function $f(x)$,

$$G_{x,t} e^{tD_x} \; f(x) = g(x+t)D_xe^{tD_x}f(x) $$

$$ =g(x+t)f'(x+t)= \sum_{j \geq 0} g_j\frac{t^j}{j!}D_x\sum_{k \geq 0} f_k\frac{t^k}{k!}$$

$$ = e^{a.t}e^{b.t}=e^{(a.+b.)t}$$

with, umbrally, $(a.)^k = a_k = g_k$ and $b_k = D_xf_k = f_{k+1}.$

This represents a binomial convolution; that is,

$$(a.+b.)^n = \sum_{k=0}^n \binom{n}{k}a_kb_{n-k},$$

so it can be expressed in (infinite) matrix form in the divided powers basis $\frac{t^k}{k!}$ as the binomial convolution

$$G_{x,t} e^{tD_x} \; f(x) \to \begin{pmatrix} g_0 & 0 & 0 & 0 & \cdots\\ g_1 & g_0 & 0 & 0 & \cdots\\ g_2 & 2g_1 & g_0 & 0 & \cdots\\ g_3 & 3g_2 & 3g_1 & g_0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix} \begin{pmatrix} f_1\\ f_2 \\ f_3 \\ f_4 \\ \vdots \end{pmatrix} $$ $$ = \begin{pmatrix} g_0 & 0 & 0 & 0 & \cdots\\ g_1 & g_0 & 0 & 0 & \cdots\\ g_2 & 2g_1 & g_0 & 0 & \cdots\\ g_3 & 3g_2 & 3g_1 & g_0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 & 0 & \cdots \\ 0 & 0 & 1 & 0 & \cdots \\ 0 & 0 & 0 & 1 & \cdots \\ 0 & 0 & 0 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix} \begin{pmatrix} 1 \\ D \\ D^2 \\ D^3 \\ \vdots \end{pmatrix} f(x)$$

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

$$ = [G_{x,t}]\begin{pmatrix} 1 \\ D \\ D^2 \\ D^3 \\ \vdots \end{pmatrix} f(x) = [G_{x,t}][f].$$

Then iterating gives the equivalent reps

$$G_{x,t}^n e^{tD_x}\; f(x) \leftrightarrow [G_{x,t}]^n [f],$$

where $[G_{x,t}]$ represents the action of $g(x+t)D_x$,

and setting $t=0$ in the diff op rep gives

$$G_{x,0}^n \; f(x) =(g(x)D_x)^n \; f(x),$$

which is equal to the first component of the vector $[G_{x,t}]^n [f]$, as illustrated in my question.

Now consider the operational calculus of flow fields and compositional inversion to obtain a characterization of the action of $G_{x,t}^n$.

Letting $\omega = h(x)$; $x = h^{-1}(\omega)$, the compositional inverse of $h(x)$; $g(x) = 1/h'(x)$; and $f(x)$ be a suitable analytic function (analytic in some circle about $x$ complex), then $g(x)D_x$ is a Lie infinitesimal generator / vector giving the flow equation (see the first two OEIS links in the question)

$$e^{tg(x)D_x} f(x) = \exp \left [ t \frac{1}{h'(x)}\frac{d}{dx} \right ]f(x) = \exp \left [ t\frac{d}{d\omega} \right ]f(h^{-1}(\omega)) = f(h^{-1}(\omega+t)) = f(h^{-1}(h(x)+t)) .$$

Consequently,

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

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

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

$$ = e^{tD_x} \exp[ug(x)D_x] f(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 pair of inverse translations--the conjugation

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

since $W'(x+t) = \frac{d}{dx} W(x+t)= \frac{d}{dt} W(x+t) = \frac{d}{d(x+t)}W(x+t) $

for $W(x)$ suitably analytic and $x$ and $t$ mutually independent.

Added 1/31/2024:

In other words, with $t$ fixed, $|t|$ sufficiently small, and $\sigma = x+t$,

$$ \frac{\partial}{\partial x } = \frac{ \partial (x+t)}{\partial x} \frac{ \partial}{\partial (x+t)} = \frac{ \partial \sigma}{\partial x} \frac{ \partial}{\partial \sigma} = \frac{ \partial}{\partial \sigma},$$

so

$$(g(x+t)\partial_x)^n e^{t\partial_x}f(x) = (g(x+t)\partial_x)^n f(x+t) $$

$$ = (g(\sigma)\partial_\sigma)^n f(\sigma) = (g(x)\partial_x)^n f(x) |_{x \to \sigma=x+t} = e^{t\partial_x}(g(x)\partial_x)^n f(x) $$