16
$\begingroup$

Let $f(x)$ be sufficiently regular (e.g. a smooth function or a formal power series in characteristic 0 etc.). In my research the following recursion made a surprising entrance $$ f_1(x) = f(x),\ f_{n+1}(x) = f(x) f'_{n}(x) $$ Thus I would like to understand the sequence $$ \left(f(x) \frac{d}{dx} \right)^n f(x) $$ This looks like a classical question that must have been already studied in dynamical systems, or Weyl algebras (say for $f(x) \in R[x]$, $R$ a commutative ring of characteristic $0$, and the derivation $\partial := f(x) \frac{d}{dx} \in A_1(R)$), or generating functions in combinatorics. But I have been unable to pinpoint it. My question is this:

Is there a known formula in the spirit of the general Leibniz formula which expresses $$ \left(f(x) \frac{d}{dx} \right)^n f(x) $$ in terms of $f$ and its derivatives $f',f'',\dots, f^{(n)}$?

Any references would be also very much appreciated!

$\endgroup$
8
  • 3
    $\begingroup$ Interesting question! Just a few weeks ago, I derived a formula for $\left(f\left(x\right) \dfrac{d}{dx}\right)^n g\left(x\right)$ in terms of $\left(f\left(x\right) \dfrac{d}{dx}\right)^k f\left(x\right)$ (in order to prove an identity of Hochschild). The whole subject has a combinatorial undercurrent of umbral calculus, of which I understand very little. $\endgroup$ Commented Feb 8, 2022 at 0:55
  • 6
    $\begingroup$ One could make a change of variables from $x$ to $z$ where $dz = dx/f(x)$ (i.e. $z$ is an antiderivative of $1/f$) to conjugate $f(x) \frac{d}{dx}$ to $\frac{d}{dz}$, then use the Faa di Bruno formula, but this is a mess, to put it mildly. $\endgroup$
    – Terry Tao
    Commented Feb 8, 2022 at 2:00
  • 4
    $\begingroup$ A bit of experimentation and a FindStat search turns up findstat.org/StatisticsDatabase/St000275 as an apparent match. Here the indexing integer partition (of $n-1$) is the exponents of the derivatives in the term (e.g. for $n=4$ the partition $(1, 1, 1)$ corresponds to $f(Df)^3$, the partition $(2, 1)$ corresponds to $f^2 (Df)(D^2f)$, and the partition $(3)$ corresponds to $f^3(D^3f)$). $\endgroup$ Commented Feb 8, 2022 at 11:24
  • 2
    $\begingroup$ @TomCopeland See my answer now. Unfortunately I probably won't get around to doing much with this in the near future. $\endgroup$ Commented Feb 9, 2022 at 1:28
  • 3
    $\begingroup$ mathoverflow.net/questions/337330/… mathoverflow.net/questions/80828/… $\endgroup$
    – IV_
    Commented Mar 6, 2022 at 14:46

6 Answers 6

8
$\begingroup$

Revamped Feb. 12, 2022:

I posted an answer to this (perennial) question in detail in the old MO-Q "Formula for n-th iteration of dx/dt=B(x)" and pointed out a common conflation of related but distinct number arrays, all related to 'natural growth' of rooted trees (and therefore Lehmer codes, see Adler ref below, p. 12). With decreasing order of refinement, they are

1) OEIS A139002: the Connes-Moscovici weights of the Connes-Moscovici Hopf algebra, enumerating forests of 'naturally-grown' rooted trees (see Hivert et al. in Taylor's answer, eqns. 34 and 36-40)

2) OEIS A139605: coefficients for the Scherk-Comtet partition polynomials, the normal-ordered operator expansion of the diff op $(f(z)\partial_z)^n$ in terms of the derivatives of $f$ and the derivative operator

3) OEIS A145271: the refined Eulerian numbers, coefficients for the expansion of $(f(z)\partial_z)^n \; f(z)$, or, equivalently, $(f(z)\partial_z)^{n+1} \; z$, as a partition polynomial in terms of the derivatives of $f(z)$ (see Hivert et al., eqns. 15-20). This is the expansion the OP, M.G., is addressing.

The paper by Hivert et al. presented by Peter Taylor addresses item 1 and illustrates item 3; however, there is no discussion of a multinomial-type formula for the refined Eulerian numbers--only eqns. 28 and 35 are given, essentially stating that item 3 is a coarsening/reduction of item 1. As far as I can tell, beyond eqn. 40, Hivert et al. deal with trees in relation to generic statistics generated by various codes and don't come back to the illustration of item 3. The Findstat entry created by Hivert that Taylor links to does give examples of the refined Eulerian numbers generated by the Lehmer code algorithm. This is an algorithm, rather than a formula of the multinomial-type (correct me if I'm mistaken)--formulas that are available for item 1 and for specialized Lagrange inversion partition polynomials (see notes III and IV below) generated from item 3, but not for item 3 directly. Giving the algorithm rather than a formula is analogous to saying a number array counts the number of perfect matchings of the vertices of the n-simplices and giving an algorithm that constructs the matchings and then counts them, or saying the number array enumerates a sum over the non-intersecting dissections of the convex polygons and giving a construction algorithm, without giving a numerical formula in terms of the number of vertices of the constructs. A direct formula for the refined Eulerian numbers is still an open question, I believe.

The paper by Domininci that skbmoore (any relation to eecummings?) cites deals with related but distinct expansions, giving as the most general example the associahedra partition polynomials I point out below. Although very important, this is not the expansion the OP is addressing. (Dominici doesn't address the connections to the associahedra nor flow equations nor does he go into any detail on trees or other combinatorial constructs, giving just a ref. on trees)

Additional refs and further notes:

I) "Set partitions and integrable hierarchies" by Adler presents the first few partition polynomials of the expansion the OP desires on p. 11 and discusses them in the context of 'natural growth' sequences $T_n$. He also alludes to Lehmer codes in the context of $T_n$. Cayley's rooted trees and the related Connes-Moscovici weights are other manifestations of 'natural growth'.

II) OEIS A145271: the partition polynomials for $(g(z)\partial_z)^n g(z)$ with $g(z) = 1/f'(z)$ (so just change notation). I called (unaware of the Hivert et al. paper until now) the coefficients of the polynomials the refined Eulerian numbers since they naturally reduce to the Eulerian numbers A008292, or A123125. My blog post "A Creation Op, Scaled Flows, and Operator Identities" contains detail on related flow functions, p.d.e.s, and more as a prelude to introducing the action of the iterated generalized Lie derivative $q(z)+g(z)\partial_z$. See also the recent MO-Q "How are Sheffer polynomials related to Lie theory?" on connections to the Sheffer polynomials, the core polynomials related to the umbral / finite operator calculus.

III) Particular series reps for $f(z)$ in $g(z) = 1/f'(z)$ of the refined Eulerian partition polynomials lead to the classic Lagrange inversion partition polynomials (LIPs) A134685 for compositional inversion of functions and formal Taylor series / e.g.f.s with $f(z)= a_1 z + a_2 \frac{z^2}{2!}+ a_3 \frac{z^3}{3!}+...$ ; the associahedra LIPs A111785 (renormalized A133437), for formal power series / o.g.f.s with $f(z)= b_1 z + b_2 z^2+ b_3 z^3+...$ ; the LIPs A133932 with the log rep $f(z) = c_1 z + c_2 \frac{z^2}{2}+ c_3 \frac{z^3}{3}+...$ ; and finally, but not least, the noncrossing partition LIPs / free cumulant partition polynomials A134264, so prominent in free probability and related quantum theory and random matrix theory, with $f(z) = z/h(z) = z/( h_1 z + h_2 z^2+ h_3 z^3+...)$. {For more info, see, e.g., my answer to the MO-Q "Important formulas in combinatorics" and the recent posts "Ruling the Inverse Universe, the inviscid Hopf-Burgers evolution equation ..." and "A Taste of Moonshine in Free Moments".}

IV) There are multinomial-type expressions for each numerical coefficient of the normal-ordering expansion of the operator $(g(z)\partial_z)^{n}$ (item 2), which are presented in the MO-Q "Differential operator power coefficients". In addition, direct simple multinomial-type expressions exist for the coefficient of any given partition monomial for all the LIPs listed in III. However, as far as I know, no such multinomial-type formula currently exists for the refined Eulerian numbers even though each full partition polynomial can be calculated independently of the others using the corresponding partition polynomials for the other LIPs in III and the permutahedra partition polynomials of A133314 (or the o.g.f. version A263633) or calculated via a matrix computation presented in the MO-Qs "Сlosed formula for $(g\partial)^n$" and "Expansions of iterated, or nested, derivatives, or vectors--conjectured matrix computation".

V) A noncommutative version of A139605 (link therein) was presented by Kentaro Ihara in "Derivations and automorphisms on non-commutative power series".

VI) Around 1853, when Lie was about ten, Charles Graves published the elegant generalized Taylor shift formula

$$ e^{t \; g(z)\partial_z} H(z) = H[f^{(-1)}(f(z)+t)]$$

and, in the 1850s also, published the operator commutator

$$[L,R] =LR-RL= 1$$ (e.g., $L=\partial_z$ and $R=z$) from which the Graves-Lie-Pincherle commutator $$[h(L),R] = \frac{dh(L)}{dL} = h'(L)$$

can be inferred and the dual

$$[L,h(R)] = \frac{dh(R)}{dR} = h'(R).$$

For Sheffer polynomial sequences, $p_n(z)$, the lowering/annihilation/destruction op $L$ and the raising/creation op $R$ are defined by $L \; p_n(z) = n \; p_{n-1}(z)$ and $R \; p_n(z) = p_{n+1}(z)$.

Obviously, $R= g(z)\partial_z$ is the raising op for the partition polynomials formed from $(g(z)\partial_z)^n g(z)$, and, with $g(z)=1/f'(z)$,

$$[g(z)\partial_z,f(z)] = 1,$$

implying, similar to the commutator identities above, that

$$[(g(z)\partial_z)^n,f(z)] = n \; (g(z)\partial_z)^{n-1}.$$

Then we have the functional identity

$$[(g(z)\partial_z)^n,f(z)]g(z) =(g(z)\partial_z)^n f(z)g(z) - f(z)(g(z)\partial_z)^n g(z) = n \; (g(z)\partial_z)^{n-1}g(z).$$

Recall the commutator acting on a function as in

$$[\partial_z,H(z)]K(z) = \partial_zH(z)K(z) - H(z)\partial_zK(z)$$

is the Newton-Leibniz formula in disguise

$$\partial_zH(z)K(z) = H(z)\partial_zK(z) + [\partial_z,H(z)]K(z) = H(z)\partial_zK(z) + K(z)\partial_zH(z).$$

$\endgroup$
4
  • $\begingroup$ Btw, considerations of this type start at least with the work of Scherk in the 1820s and one of the Graves brothers, Charles, in the early 1850s. For some history, see this answer to the MO-Q "In splendid isolation" (mathoverflow.net/questions/97512/in-splendid-isolation/…) $\endgroup$ Commented Feb 8, 2022 at 20:04
  • $\begingroup$ Dear @TomCopeland, thank you for the very comprehensive answer and apologies for the delay! I was a bit sick last week and needed more time to go through the wealth of information contained in it. Oddly enough, I don't get any notifications when some of the answers are edited (probably unless they have been accepted), but that's probably not a bug, but by design... $\endgroup$
    – M.G.
    Commented Feb 14, 2022 at 8:52
  • 1
    $\begingroup$ I just scratched the surface. It's an ongoing area of research at the crossroads of several disciplines with a history dating back to Newton. (For a recent contribution, see "Grass tress and forests: Enumeration of Grassmannian trees and forests with applications to the momentum amplituhedron" by Moerman and Williams.) Hope you enjoy exploring it as much as I have and can blissfully navigate around the short-sighted, self-serving, tribal instincts and hubris I often encounter among diverse groups of researchers / editors/ gatekeepers. I think, for MO-Q, "Is this what I would tell my sons?" $\endgroup$ Commented Feb 14, 2022 at 14:49
  • 1
    $\begingroup$ On A139605, see also "Recent Developments in Combinatorial Aspects of Normal Ordering" by Matthias Schork (2021) ecajournal.haifa.ac.il/Volume2021/ECA2021_S2B2.pdf $\endgroup$ Commented Feb 14, 2023 at 17:31
7
$\begingroup$

Suppose that we don't reorder the parts within terms and that we always post-multiply the $f$. So e.g. $$\begin{eqnarray*}f_1 &=& f \\ f_2 &=& (Df)f \\ f_3 &=& (D^2f)ff + (Df)(Df)f \\ f_4 &=& (D^3f)fff + (D^2f)(Df)ff + (D^2f)f(Df)f + (D^2f)(Df)ff + (Df)(D^2f)ff + (Df)(Df)(Df)f\end{eqnarray*}$$etc. Each term of $f_n$ is an ordered product of $n$ subterms which generates $n$ terms in $f_{n+1}$ by the product rule. We can label each term by the sequence of indices of the subterm whose exponent of $D$ increased; then the terms of $f_n$ are labelled by sequences $(a_1, a_2, \ldots, a_{n-1})$ where $1 \le a_i \le i$ and a sequence produces a term $$\prod_{j=1}^n D^{|\{ i\,:\, a_i = j \}|}f$$

But these sequences could equally be interpreted as inversion codes (nomenclature varies; in Wikipedia they're left inversion count vectors, in Mathworld they're inversion vectors) for permutations.

If we now allow grouping of equal terms we get that the coefficient of $\prod_i (D^i f)^{b_i}$ is the number of permutations on $n-1$ elements whose left inversion count vector contains each $i$ with multiplicity $b_i$.

The description of the FindStat statistic which I linked earlier in comments is

Number of permutations whose sorted list of non zero multiplicities of the Lehmer code is the given partition.

but its reference Hivert, F., Novelli, J.-C., Thibon, J.-Y. Multivariate generalizations of the Foata-Schützenberger equidistribution mentions some equivalent descriptions. The same coefficients also appear in section 3.1 in the context of a different process relating to a differential equation, and attributed to Cayley. (The publishers are, ridiculously, asking 47€ for access to an 1857 paper, so I haven't been able to follow up the reference).

$\endgroup$
4
  • 3
    $\begingroup$ I put a copy of the Cayley paper on my website. $\endgroup$ Commented Feb 8, 2022 at 16:28
  • 1
    $\begingroup$ I had trouble decades ago understanding Cayley's paper, which is reffed by Comtet in his 1970s classic on Lie derivatives and partition / regular polynomials, so I considered the simplest case in a set of notes "Mathemagical Forests" and again later in "Lagrange a la Lah" with simple illustrations. $\endgroup$ Commented Feb 8, 2022 at 19:56
  • $\begingroup$ Dear @PeterTaylor, thank you very much for the to-the-point answer! This is exactly the kind of description I was looking for. I don't think I would have ever guessed to look for "left inversion count vectors". $\endgroup$
    – M.G.
    Commented Feb 14, 2022 at 8:56
  • $\begingroup$ The MO user and OEIS editor Peter Luschny created the OEIS entry oeis.org/A355777 (his variant of my entry A145271) in July 2022 on the relation of A145271 to Lehmer codes, of course without reference to your work here nor Adler's noted in my answer. $\endgroup$ Commented Sep 1, 2022 at 3:52
5
$\begingroup$

In the paper 'Nested Derivatives:' A simple method for computing series expansions of inverse function' by D. Dominici, with arXiv version https://arxiv.org/pdf/math/0501052.pdf

has something very close to what the OP wants. Define $$ \cal{D}^0[f](x) = 1$$ $$ \cal{D}^n[f](x) = \frac{d}{dx}\big(f(x)\cal{D}^{n-1}[f](x)\big) $$

The only difference is that the OP has an additional multiplication by $f$ at the end of the chain of operations. That paper has some closed-form formulas for select $f$ and is oriented towards inverse functions.

$\endgroup$
7
  • $\begingroup$ @TomCopeland Tom, I just read through the Integer Sequences A145271 as you indicated, and it does have many other references. I will keep it in mind should I return to problems that need this treatment, so thank you for bringing it to my attention. I do see the phrase 'nested derivative' in a one of your posts. I won't remove my answer, since I didn't see the paper I sourced, though your reference list is much more comprehensive. $\endgroup$
    – skbmoore
    Commented Feb 8, 2022 at 18:55
  • $\begingroup$ Search on Dominici via the OEIS search line. Peter Bala often refs the paper in his contributions on related machinations. Btw, the use of this type of relation probably goes back to Newton--he derived the first few Lagrange inversion partition polynomials associated with the refined Euler characteristic partition polynomials of the associahedra 300 years before the polytopes were constructed. $\endgroup$ Commented Feb 8, 2022 at 19:26
  • $\begingroup$ @TomCopeland I'm a physicist who plays in combinatorics some, so the Newton connection is really interesting. I believe my first exposure to these kinds of operations were with fermion and boson algebras, but that was long ago. $\endgroup$
    – skbmoore
    Commented Feb 8, 2022 at 19:40
  • 1
    $\begingroup$ You might enjoy "Grass tress and forests: Enumeration of Grassmannian trees and forests with applications to the momentum amplituhedron" by Moerman and Williams. (However, they neglect for whatever reasons, to explicitly reference several pertinent entries in the OEIS, choosing to note only one. Foata euphemistically referred to the 'ecoles'--rather than 'tribus'--bostonienne, californienne, lotharingienne, quebecoise, viennoise. ) $\endgroup$ Commented Feb 14, 2022 at 15:14
  • 1
    $\begingroup$ But more closely related to the boson/fermion correspondence are the refs in my notes "A Creation Op, Scaled Flow, and Operator Identities" tcjpn.wordpress.com/2022/02/02/a-creation-op. $\endgroup$ Commented Feb 14, 2022 at 15:24
3
$\begingroup$

This, too, is not an answer, just a preview of a paper I probably won't be writing for a while (one of only 9 papers on my immediate to-do list).

It so happens I derived a related formula a few weeks ago when proving an apocryphal identity of Hochschild. The formula needs some preliminary definitions, and unfortunately my notations are different from the OP's, but I hope it is of some use. Note that, while I am able to prove everything I claim, I am not fluent in its combinatorial background (umbral calculus, in particular).

The general setup will be as follows:

We fix a commutative ring $R$. Let $d:R\rightarrow R$ be a derivation (i.e., a $\mathbb{Z}$-linear map satisfying $d\left( ab\right) =d\left( a\right) \cdot b+a\cdot d\left( b\right) $ for all $a,b\in R$). Let $a\in R$ be an element. Let $L_{a}$ be the map $R\rightarrow R,\ r\mapsto ar$ (known as "left multiplication by $a$", but can just as well be called "right multiplication by $a$" since $R$ is commutative). Note that $L_{a}\circ d$ is a derivation (commonly denoted by $ad$), but $d\circ L_{a}$ is not (in general).

For each nonnegative integer $n$, we define the following:

  • Let $\left[ n\right] $ be the set $\left\{ 1,2,\ldots,n\right\} $.

  • A set partition of $\left[ n\right] $ means a set $P$ of subsets of $\left[ n\right] $ (called the blocks of $P$) such that each element of $\left[ n\right] $ belongs to exactly one block of $P$.

  • Let $\operatorname*{SP}\left( n\right) $ denote the set of all set partitions of $\left[ n\right] $. For instance, \begin{align*} \operatorname*{SP}\left( 3\right) & ={\Large \{}\left\{ \left\{ 1,2,3\right\} \right\} ,\ \ \ \left\{ \left\{ 1\right\} ,\left\{ 2,3\right\} \right\} ,\ \ \ \left\{ \left\{ 2\right\} ,\left\{ 1,3\right\} \right\} ,\\ & \ \ \ \ \ \ \left\{ \left\{ 3\right\} ,\left\{ 1,2\right\} \right\} ,\ \ \ \left\{ \left\{ 1\right\} ,\left\{ 2\right\} ,\left\{ 3\right\} \right\} {\Large \}}. \end{align*} Note that $\left\vert \operatorname*{SP}\left( n\right) \right\vert $ is the $n$-th Bell number $B_{n}$.

  • If $P=\left\{ P_{1},P_{2},\ldots,P_{k}\right\} $ is a set partition of $\left[ n\right] $ (with $P_{1},P_{2},\ldots,P_{k}$ being distinct), then we set $\ell\left( P\right) :=k$ and \begin{align*} b_{P}:=\prod_{i=1}^{k}\left( d\circ L_{a}\right) ^{\left\vert P_{i} \right\vert -1}\left( 1\right) . \end{align*}

For example, if $n=5$ and $P=\left\{ \left\{ 1,4\right\} ,\left\{ 2,3,5\right\} \right\} $, then \begin{align*} b_{P}=\underbrace{\left( d\circ L_{a}\right) ^{2-1}\left( 1\right) }_{\substack{=\left( d\circ L_{a}\right) \left( 1\right) \\=d\left( a\right) }}\cdot\underbrace{\left( d\circ L_{a}\right) ^{3-1}\left( 1\right) }_{\substack{=\left( d\circ L_{a}\right) ^{2}\left( 1\right) \\=d\left( ad\left( a\right) \right) }}=d\left( a\right) \cdot d\left( ad\left( a\right) \right) . \end{align*} Of course, $b_{P}$ depends only on the sizes of the blocks of $P$.

Now, my formulas claim that each integer $m\geq0$ and each $w\in R$ satisfy \begin{equation} \left( d\circ L_{a}\right) ^{m}\left( w\right) =\sum_{P\in \operatorname*{SP}\left( m+1\right) }b_{P}\cdot a^{\ell\left( P\right) -1}\cdot d^{\ell\left( P\right) -1}\left( w\right) \label{darij1.eq.damw} \tag{1} \end{equation} and \begin{equation} \left( L_{a}\circ d\right) ^{m}\left( w\right) =\sum_{P\in \operatorname*{SP}\left( m\right) }b_{P}\cdot a^{\ell\left( P\right) }\cdot d^{\ell\left( P\right) }\left( w\right) . \label{darij1.eq.admw} \tag{2} \end{equation}

For instance, for $m=2$, these two formulas become \begin{align*} \left( d\circ L_{a}\right) ^{2}\left( w\right) & =\underbrace{b_{\left\{ \left\{ 1,2,3\right\} \right\} }}_{=\left( d\circ L_{a}\right) ^{2}\left( 1\right) }\cdot\underbrace{a^{1-1}}_{=1} \cdot\underbrace{d^{1-1}\left( w\right) }_{=w}\\ & \ \ \ \ \ \ \ \ \ \ +\underbrace{b_{\left\{ \left\{ 1\right\} ,\left\{ 2,3\right\} \right\} }}_{\substack{=\left( d\circ L_{a}\right) ^{0}\left( 1\right) \cdot\left( d\circ L_{a}\right) ^{1}\left( 1\right) \\=\left( d\circ L_{a}\right) ^{1}\left( 1\right) }}\cdot\underbrace{a^{2-1}} _{=a}\cdot\underbrace{d^{2-1}}_{=d}\left( w\right) \\ & \ \ \ \ \ \ \ \ \ \ +\underbrace{b_{\left\{ \left\{ 2\right\} ,\left\{ 1,3\right\} \right\} }}_{\substack{=\left( d\circ L_{a}\right) ^{0}\left( 1\right) \cdot\left( d\circ L_{a}\right) ^{1}\left( 1\right) \\=\left( d\circ L_{a}\right) ^{1}\left( 1\right) }}\cdot\underbrace{a^{2-1}} _{=a}\cdot\underbrace{d^{2-1}}_{=d}\left( w\right) \\ & \ \ \ \ \ \ \ \ \ \ +\underbrace{b_{\left\{ \left\{ 3\right\} ,\left\{ 1,2\right\} \right\} }}_{\substack{=\left( d\circ L_{a}\right) ^{0}\left( 1\right) \cdot\left( d\circ L_{a}\right) ^{1}\left( 1\right) \\=\left( d\circ L_{a}\right) ^{1}\left( 1\right) }}\cdot\underbrace{a^{2-1}} _{=a}\cdot\underbrace{d^{2-1}}_{=d}\left( w\right) \\ & \ \ \ \ \ \ \ \ \ \ +\underbrace{b_{\left\{ \left\{ 1\right\} ,\left\{ 2\right\} ,\left\{ 3\right\} \right\} }}_{\substack{=\left( d\circ L_{a}\right) ^{0}\left( 1\right) \cdot\left( d\circ L_{a}\right) ^{0}\left( 1\right) \cdot\left( d\circ L_{a}\right) ^{0}\left( 1\right) \\=1}}\cdot\underbrace{a^{3-1}}_{=a^{2}}\cdot\underbrace{d^{3-1}}_{=d^{2} }\left( w\right) \\ & =\left( d\circ L_{a}\right) ^{2}\left( 1\right) \cdot w+3\cdot\left( d\circ L_{a}\right) ^{1}\left( 1\right) \cdot ad\left( w\right) +a^{2}\cdot d^{2}\left( w\right) \end{align*} and \begin{align*} \left( L_{a}\circ d\right) ^{2}\left( w\right) & =b_{\left\{ \left\{ 1,2\right\} \right\} }\cdot a^{1-1}\cdot d^{1-1}\left( w\right) +b_{\left\{ \left\{ 1\right\} ,\left\{ 2\right\} \right\} }\cdot a^{2-1}\cdot d^{2-1}\left( w\right) \\ & =\left( d\circ L_{a}\right) \left( 1\right) +ad\left( w\right) ; \end{align*} both are easily verified.

The right hand sides of the formulas \eqref{darij1.eq.damw} and \eqref{darij1.eq.admw} can be rewritten in terms of exponential Bell polynomials. As a result, the formulas take the forms (I hope I got them right) \begin{equation} \left( d\circ L_{a}\right) ^{m}\left( w\right) =\sum_{k=0}^{m} B_{m+1,k+1}\left( u_{0},u_{1},u_{2},\ldots\right) \cdot a^{k}\cdot d^{k}\left( w\right) \nonumber \end{equation} and \begin{align*} \left( L_{a}\circ d\right) ^{m}\left( w\right) =\sum_{k=0}^{m} B_{m,k}\left( u_{0},u_{1},u_{2},\ldots\right) \cdot a^{k}\cdot d^{k}\left( w\right) , \end{align*} where \begin{align*} u_{i}:=\left( d\circ L_{a}\right) ^{i}\left( 1\right) \ \ \ \ \ \ \ \ \ \ \text{for each integer }i\geq0. \end{align*}

Proving the formulas is fairly easy. You can show \eqref{darij1.eq.damw} by induction on $m$ (using the Leibniz rule and the easy observation that a set partition $P\in\operatorname*{SP}\left( m\right) $ with $\ell\left( P\right) =k$ can be obtained from exactly $k+1$ different set partitions $P^{\prime}\in\operatorname*{SP}\left( m+1\right) $ by removing the element $m+1$). Then, \eqref{darij1.eq.admw} follows by applying \eqref{darij1.eq.damw} to $m-1$ and $d\left( w\right) $ instead of $m$ and $w$ (and multiplying the result by $a$). There are probably some more essential ways to prove the formulas -- in particular, the uncanny similarity to Faa di Bruno's formula cries out for an explanation -- but I am happy enough with the induction.

To see why this all is related to the OP, let $R$ be the ring of functions, and let $a=f\left( x\right) $ and $d=\dfrac{d}{dx}$. Not sure if the results are of much use, though.

Now, what is the connection to Hochschild? Let $p$ be a prime number, and let $w\in R$ be such that $pw=0$. (Usually, one just considers the case when $p=0$ in $R$, but all we need is $pw=0$.) Applying \eqref{darij1.eq.damw} to $m=p-1$, we obtain \begin{equation} \left( d\circ L_{a}\right) ^{p-1}\left( w\right) =\sum_{P\in \operatorname*{SP}\left( p\right) }b_{P}\cdot a^{\ell\left( P\right) -1}\cdot d^{\ell\left( P\right) -1}\left( w\right) . \label{darij1.eq.p-1} \tag{3} \end{equation} However, the cyclic group $\mathbb{Z}/p$ acts on the set $\operatorname*{SP} \left( p\right) $ (by cyclically rotating each number in each block -- i.e., the element $\overline{1}\in\mathbb{Z}/p$ sends a set partition $\left\{ \left\{ a_{1},a_{2},\ldots,a_{k}\right\} ,\left\{ b_{1},b_{2} ,\ldots,b_{\ell}\right\} ,\ldots,\left\{ g_{1},g_{2},\ldots,g_{r}\right\} \right\} $ to $\left\{ \left\{ a_{1}+1,a_{2}+1,\ldots,a_{k}+1\right\} ,\left\{ b_{1}+1,b_{2}+1,\ldots,b_{\ell}+1\right\} ,\ldots,\left\{ g_{1}+1,g_{2}+1,\ldots,g_{r}+1\right\} \right\} $, where addition happens modulo $p$). This action splits $\operatorname*{SP}\left( p\right) $ into orbits of sizes $1$ and $p$. Each orbit of size $p$ contributes a total of $0$ to the right hand side of \eqref{darij1.eq.p-1}, because the $p$ addends corresponding to the entries of this orbit are all equal and contain a $w$ (so summing them $p$ times yields $0$ since $pw=0$). What remains are the addends corresponding to the orbits of size $1$. These orbits are the ones of the set partitions $\left\{ \left\{ 1,2,\ldots,p\right\} \right\} $ and $\left\{ \left\{ 1\right\} ,\left\{ 2\right\} ,\ldots,\left\{ p\right\} \right\} $. The corresponding addends are $\left( d\circ L_{a}\right) ^{p-1}\left( 1\right) \cdot a^{1-1}\cdot d^{1-1}\left( w\right) =\left( d\circ L_{a}\right) ^{p-1}\left( 1\right) \cdot w$ and $\underbrace{\left( \left( d\circ L_{a}\right) ^{1-1}\right) ^{p}}_{=1^{p}=1}\cdot a^{p-1}\cdot d^{p-1}\left( w\right) =a^{p-1}\cdot d^{p-1}\left( w\right) $. Thus, \eqref{darij1.eq.p-1} simplifies to \begin{equation} \left( d\circ L_{a}\right) ^{p-1}\left( w\right) =\left( d\circ L_{a}\right) ^{p-1}\left( 1\right) \cdot w+a^{p-1}\cdot d^{p-1}\left( w\right) . \label{darij1.eq.hoch1} \tag{4} \end{equation} If we apply this to $d\left( w\right) $ instead of $w$, and multiply the result by $a$, we obtain \begin{equation} \left( L_{a}\circ d\right) ^{p}\left( w\right) =\left( d\circ L_{a}\right) ^{p-1}\left( 1\right) \cdot ad\left( w\right) +a^{p}\cdot d^{p}\left( w\right) . \label{darij1.eq.hoch2} \tag{5} \end{equation} In particular, if $p=0$ in $R$, then we thus have \begin{align*} \left( L_{a}\circ d\right) ^{p} & =\underbrace{\left( d\circ L_{a}\right) ^{p-1}\left( 1\right) \cdot a}_{=\left( L_{a}\circ d\right) ^{p-1}\left( a\right) }d+a^{p}\cdot d^{p}\\ & =\left( L_{a}\circ d\right) ^{p-1}\left( a\right) \cdot d+a^{p}\cdot d^{p} \end{align*} as maps $R\rightarrow R$. This is Proposition 1.1 in Andrzej Nowicki, Integral derivations, Journal of Algebra 110(1):262-276 (another scan at https://doi.org/10.1016/0021-8693(87)90045-7 ), where it is credited to Hochschild. Something similar does indeed appear as Lemma 1 in a 1955 paper by Hochschild, with a vague sketch of a proof I never decided whether to trust; the modern statement seems to have been first made by Cartier in Questions de rationalité des diviseurs en géométrie algébrique (see (43) therein). I am not sure if a complete proof without holes has ever appeared in the literature.

Note that this is not the same as that other Hochschild identity, which is (42) in Cartier's op.cit. and doesn't seem to appear in Hochschild's work at all. But the latter identity, too, can be proved combinatorially using a $\mathbb{Z}/p$-action :)

$\endgroup$
1
  • 1
    $\begingroup$ Dear Darij, thank you for taking the time to write up your formulas and the accompanying explanations. It could turn out even more useful than anticipated. $\endgroup$
    – M.G.
    Commented Feb 14, 2022 at 8:43
2
$\begingroup$

While not pretending to answer the OP, the following is too long to fit in a comment while it might contain elements of interest to the poster.

If $f$ is a convergent object (smooth or analytic), then you encounter these quantities while computing the flow of the vector field $X(x):=f(x)\frac{\partial}{\partial x}$. According to the well-known Lie formula, one has for small $t\in (\mathbb{R},0)$ (or $t\in (\mathbb{C},0)$ according to your setting) that the solution to the differential equation $$\dot{x}(t)=f(x(t))~~,~x(0)=x_*$$ satisfies $$x(t)=\left(\sum_{n\geq 0}\frac{t^n}{n!}X\cdot^n x\right)|_{x:=x_*}.$$ The time-independent term $X\cdot^n x$ is given by the application of $f(x)\frac{d}{dx}$ $n$ times to the identity function $x\mapsto x$.

More generally, for a function $g$ you have $$g(x(t))=\left(\sum_{n\geq 0}\frac{t^n}{n!}X\cdot^ng(x)\right)|_{x:=x_*}.$$ So the sought quantities $\left(f(x)\frac{d}{dx}\right)^nf(x)$ are basically the coefficients of the series expansion of $f(x(\bullet))$ where $x(\bullet)$ is the flow of the vector field/derivation $X$ with initial value $x(0)=x$ (sorry for the loose notations here). Because for each fixed $t$ the change of variables $x_*\mapsto x(t)$ is a symmetry of $X$, one has finally $$f(x(t))=f(x_*)\times \frac{dx(t)}{dx_*}.$$

In case $f$ is a formal object, the flow $x(t)$ might only be defined for $t$ in a discrete lattice of $\mathbb{R}$ (or $\mathbb{C}$), or just only for $t:=0$.

$\endgroup$
4
  • $\begingroup$ Your flow equations and more are given with refs in the pertinent OEIS entry and the links/refs in my answer and comments (the basic flow equations predate Lie). $\endgroup$ Commented Feb 9, 2022 at 18:54
  • $\begingroup$ Dear Loïc, thank you for taking the time to write up this relation! The "loose notations" are a non-issue :-) $\endgroup$
    – M.G.
    Commented Feb 14, 2022 at 8:45
  • $\begingroup$ What does $t \in (\mathbb R, 0)$ (as opposed to $t \in \mathbb R$) mean? $\endgroup$
    – LSpice
    Commented May 19, 2023 at 14:38
  • 1
    $\begingroup$ @LSpice: it means $t$ belongs to some (probably small) neighborhood of $0$ in $\mathbb{R}$. $\endgroup$ Commented May 19, 2023 at 14:47
2
$\begingroup$

It also related to the so-called elementary differentials which appear in the algebraic setting for Runge-Kutta methods. See for example the related chapter in the book Hairer, Wanner and Lubich.

$\endgroup$
3
  • $\begingroup$ Yes, some history on this is in the link to my comment to my answer. $\endgroup$ Commented Feb 8, 2022 at 21:02
  • 1
    $\begingroup$ That's a long book :) Anything more precise? $\endgroup$ Commented Feb 9, 2022 at 1:32
  • $\begingroup$ @darijgrinberg, Refs to shorter treatments of Butcher series and the Runge-Kutta method are given in the essentially duplicate MO-Q to which I link in my answer. $\endgroup$ Commented Feb 12, 2022 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.