By an odd coincidence, I stumbled upon a second question in as many weeks about power series, and once again the only way I know how to prove the result is by complex methods; once again, I am leaving it here as a challenge to any interested readers, and I would be particularly interested in knowing of a proof that was not based on complex analysis (or thinly disguised versions thereof), or for a reference to previous literature where something like this identity has occured. (I suspect for instance that something like this may have shown up before in free probability, based on the answer to part (ii) of the problem.)
Here is a purely algebraic form of the problem:
Problem 1 Let
be a formal function of one variable
. Suppose that
is the formal function defined by
where we use
to denote the
-fold derivative of
with respect to the variable
.
- (i) Show that
can be formally recovered from
by the formula
- (ii) There is a remarkable further formal identity relating
with
that does not explicitly involve any infinite summation. What is this identity?
To rigorously formulate part (i) of this problem, one could work in the commutative differential ring of formal infinite series generated by polynomial combinations of and its derivatives (with no constant term). Part (ii) is a bit trickier to formulate in this abstract ring; the identity in question is easier to state if
are formal power series, or (even better) convergent power series, as it involves operations such as composition or inversion that can be more easily defined in those latter settings.
To illustrate Problem 1(i), let us compute up to third order in , using
to denote any quantity involving four or more factors of
and its derivatives, and similarly for other exponents than
. Then we have
and hence
multiplying, we have
and
and hence after a lot of canceling
Thus Problem 1(i) holds up to errors of at least. In principle one can continue verifying Problem 1(i) to increasingly high order in
, but the computations rapidly become quite lengthy, and I do not know of a direct way to ensure that one always obtains the required cancellation at the end of the computation.
Problem 1(i) can also be posed in formal power series: if
is a formal power series with no constant term with complex coefficients with
, then one can verify that the series
makes sense as a formal power series with no constant term, thus
For instance it is not difficult to show that . If one further has
, then it turns out that
as formal power series. Currently the only way I know how to show this is by first proving the claim for power series with a positive radius of convergence using the Cauchy integral formula, but even this is a bit tricky unless one has managed to guess the identity in (ii) first. (In fact, the way I discovered this problem was by first trying to solve (a variant of) the identity in (ii) by Taylor expansion in the course of attacking another problem, and obtaining the transform in Problem 1 as a consequence.)
The transform that takes to
resembles both the exponential function
and Taylor’s formula
but does not seem to be directly connected to either (this is more apparent once one knows the identity in (ii)).
37 comments
Comments feed for this article
23 October, 2016 at 9:47 pm
Paata Ivanishvili
Apparently this formal identity should be related to Lambert W function because for $F(z)=exp(az)$ we have $G(z)=exp(az)*(-W(-a)/a)$
23 October, 2016 at 10:24 pm
Anonymous
In the first line of the problem, is “formal function” means “formal power series”? (and a similar question about the meaning of “k-fold derivative” of a formal function).
[See the first paragraph after Problem 1, as well as the discussion afterwards for a version of the problem using formal power series instead of formal functions. -T.]
23 October, 2016 at 11:23 pm
Terence Tao
Turns out that the result is extremely classical – it is a corollary of the Lagrange reversion theorem, which I was not aware of until after I had posted the problem (actually I found out about this theorem after following up on the previous comment and reading up on the W-function). Ah well. I still think it is a nice challenge to try to prove it without complex methods.
24 October, 2016 at 3:53 am
Anonymous
Using the above Wikipedia article (with
), the solution
to the equation
(with given function
) is given by
(where the function
is as defined by the formal series in the problem statement). Hence
which implies the required identity
, as well as the equivalent “dual” identity
(which may explain the remarkable similarity between the two expansions.)
25 October, 2016 at 5:24 am
David Renfrew
This relationship does show up in free probability. It is satisfied when G is the Stieltjes transform of a probability measure and F is the Stieltjes transform of the free convolution of that probability measure with the semicircle distribution.
I’m not sure if it shows up in the way you presented the problem, but it does show up as in the comment above, using the analytic subordination properties of free convolution.
2 November, 2016 at 12:20 pm
Tom Copeland
I wrote up a derivation involving the Laplace transform at my website. Since this has so many connections to a variety of combinatoric structures and operational calculus that interest me, could you either write up your derivation here or send me a copy?
3 November, 2016 at 6:20 pm
Terence Tao
Here is a sketch of my original argument, working formally for simplicity (ignoring issues of convergence, branches of logarithm, etc.). Given a function
(with say
and
small), we may formally find a function
such that the maps
and
invert each other. Next, take some
and consider the quantity
Using the Cauchy integral formula one can write this as
for a suitable contour
. Summing the series formally, we get
Making the somewhat prescient change of variables
, so that
and hence
, and shifting contours, this becomes
By change of variables and shifting contours we (formally) have
so the above simplifies to
which after integration by parts becomes
and hence by the Cauchy integral formula we have
A similar argument (replacing
with
throughout) gives
One can carry out the entire argument in the ring of formal Laurent series, using the residue of such series as a substitute for contour integration; this then becomes quite close to Hermite’s proof of the Lagrange inversion formula using residues of formal Laurent series.
1 December, 2016 at 3:41 pm
Tom Copeland
I) There’s a simpler derivation by resdues by Jacob Lurie in http://mathoverflow.net/questions/60478/hirzebruchs-motivation-of-the-todd-class/219616#219616, mirroring one by Hirzebruch.
II) The expansion comprised of the reduced derivatives can be formed umbrally for each order from the multinomial expansion OEIS A036038. E.g.,
umbrally reduced by erasing subscripts and lowering exponents becomes
.
III) The partition expansion is given in http://oeis.org/A248927 with
and are the Hadamard products by partition of A036038 and A134264, which enumerates noncrossing partitions and provides another inversion formula. E.g., to the next order the numerical coefficients for the distinct partitions are (1,3,6)(1,3,1)=(1,9,6).
24 October, 2016 at 12:27 am
Anonymous
It seems that this identity should be of the form
or of the more general form
for some explicit(!) analytic function
(which may contain even higher derivatives of
and
). Therefore, for each known(!) such function
, one may express formally (using formal derivations) the function
(as a solution of this identity) by a power series involving
and its derivatives, and vice versa (i.e.
as a power series in terms of
and its derivatives).
(representing the identity), a possible approach is to express the coefficients of the (given) expression of
(as a power series in
and its derivatives) in terms of the (unknown) coefficients of
(as a power series in
) and then to solve the resulting equations for the coefficients of
.
In order to find the explicit form of the function
24 October, 2016 at 3:20 am
gninrepoli
From this identity?
– Bernoulli number
24 October, 2016 at 6:12 am
Jean-Bernard Zuber
It would be interesting to see how Lagrange proved his formula. Presumably not by using Cauchy integral ! There is an alternative proof, of combinatorial nature, making use of differential operators defined by formal power series. See at the end of the following note
https://www.dropbox.com/s/hb1stepdxpu9h1u/lagrange_e.pdf?dl=0
24 October, 2016 at 7:50 am
igessel
You can find Lagrange’s paper online at http://gallica.bnf.fr/ark:/12148/bpt6k229222d/f6.
24 October, 2016 at 6:26 am
igessel
The “Lagrange reversion formula” (this term isn’t used anywhere except in the Wikpedia article) is equivalent to the well-known Lagrange inversion formula, which has many formal power series proofs. See, for example, my survey paper on Lagrange inversion at https://arxiv.org/abs/1609.05988, especially formula (2.6.2). Note that
and
are compositional inverses. (Presumably this is the identity in (ii).)
31 October, 2016 at 12:23 pm
Tom Copeland
The inverse relation certainly holds for
, generating an o.g.f. for the Catalan numbers
with the inverse o.g.f.
.
30 October, 2016 at 2:35 am
Anonymous
“(ii) There is a remarkable further formal identity relating {F(z)} with {G(z)} that does not explicitly involve any infinite summation. What is this identity?”
What is that identity? I didn’t find it on Wikipedia nor Lagrange’s paper.
30 October, 2016 at 7:17 am
Tatenda
Dear Dr. Tao, i’m Tatenda Isaac Kubalalika, a very ambitious and deeply passionate prospective undergraduate student from Zimbabwe, whose academic progress has terribly been halted by an acute lack of funds. I know this post might not be too suitable here, but i would kindly beg you to bare with me. I initially thought of emailing you but then i thought you will probably be too busy.
Below is what really seems to be an explanation of why the nontrivial zeros of the Riemann zeta function should all lie on the critical line Re(s)=1/2 :
Consider the derivative of log xi(s) with respect to s, where xi(s) is the Riemann xi function for the variable s. We shall denote by p the nontrivial zero of xi(s).
This derivative at s=1 is given by:
(d/ds) log xi(s) = B + the sum over all p of 1/p and 1/(1-p) = 0.023…
where B is a constant.
For this infinite sum, it is necessary that each zero be paired with its conjugate.We claim that the conjugate of each p is indeed 1-p. Otherwise, if the conjugate of p was, say q, then the conjugate of 1-p would be 1-q,
and the above equation would become:
(d/ds) log xi(s) = B + the sum over all p of 1/p and 1/(1-p) + the sum over all q of 1/q and 1/(1-q)
Let A be the real part of the sum over all p of 1/p and 1/(1-p). Then observe that the real part of the sum over all q of 1/q and 1/(1-q) is also A, so that the real part of (d/ds) log xi(s) would be
(real part of B) + A = (real part of B) + 2A
which yields A=0. But this is evidently false from the known numerical value of this derivative. And we reach a contradiction
Therefore, it follows that each p is a conjugate of 1-p, which requires the real part of each p yo be 1/2.
Remark: Due to the overwhelming number of unsuccessful attempted solutions to this problem, the author understands that most people would be exceedingly skeptical of the above argument. However, we urge the reader to patiently go over each step of the above argument, and pass a conclusion of their own.
30 October, 2016 at 11:51 am
Jhon Manugal
I don’t have much to say after Ira Gessel’s response.
http://mathoverflow.net/questions/32099/what-is-lagrange-inversion-good-for
One can solve
and you get an answer
. Doesn’t thing thing have the full
Galois group?
30 October, 2016 at 8:11 pm
Anonymous
One can verify (e.g. by the ratio test) that this series converges IFF
and that the equation has multiple root IFF
(which determines the radius of convergence.)
30 October, 2016 at 11:53 am
Jhon Manugal
I meant to add my derivation of the chain rule… here is
30 October, 2016 at 1:52 pm
Tom Copeland
Lagrange inversion is also called series reversion. Relations to free probability and noncrossing partitions are noted in OEIS A134264 (follow the links in Manugal’s reply).
30 October, 2016 at 2:31 pm
Tom Copeland
It is interesting, but not surprising, to see
1) how many academics use and contribute to the On-line Encyclopedia of Integer Sequences, yet do not reference it in much of their writings
2) how many academics fail to check the OEIS for info on integer sequences they stumble across, which includes matrices/tables related to partition polynomials, such as those for series reversion.
30 October, 2016 at 4:38 pm
Tom Copeland
Related to http://oeis.org/A248927.
1 November, 2016 at 7:29 am
The Lagrange Reversion Theorem and the Lagrange Inversion Formula | Shadows of Simplicity
[…] The lead to the connection between the OEIS entries and the LRT was Terry Tao’s post Another Problem about Power Series. […]
2 November, 2016 at 2:57 am
Eulogio Garcia
A solution to the problema may be next.
In algebraic expression
and
if we have:
and
We can determine
from
for it.
9 November, 2016 at 6:07 am
Sergei
Respected(dear) Terence Tao! My appearance on horizon not accidental. I for a long time preparation at contact from you. By me there is five rough notebooks and approximate two hundred flat paper pages of bleach on Russian language and (of separate parts) collapsible(format A4) draft or design of big absolute number field. I nobody else no trust in,except you, therefore I be inactive, no undertake nexts steps for publication. Tower of Erdesh- that big book, not yet writing,quantity floors(page’s) in which I not know. Yet I know, how to write that book, not admit not a (single) one floor(page). Yes, that perhaps reckless, if you no believe. Who such Tom Copeland?? I know, how to fill up(fill out) matrix’s sections with partitions in OEIS of integer sequences. Thanks! Sergei.
9 November, 2016 at 12:15 pm
david
You just take a derivative of G(x), and put one derivative inside each term in the series. You then pull out the first term, change n+1=k in the rest of the series and see that G'(x) = F'(x)(1+G(x)). Isn’t that right? It is easy from there.
[Unfortunately this doesn’t work, because the factor
is trapped inside a
-fold derivative and can’t easily be extricated from the series. -T.]
10 November, 2016 at 7:42 am
David
Darn.
22 November, 2016 at 8:40 pm
An integration approach to the Toeplitz square peg problem | What's new
[…] higher and higher order to try to evade this obstruction (this, incidentally, was when I discovered this cute application of Lagrange reversion) but no matter how high an accuracy I went (I think I ended up expanding to sixth order in a […]
24 November, 2016 at 12:23 pm
Sergei
Dear Terence Tao! I want proceed(with) our discussion by last subject of problem formal power series. First, what attract draw me attention, that identity F(z) and G(z). I can answer on that question. So that: F(z)=G(z) or G(z)=F(z). If extract(cancel) (z), that which receive(get) G=F or GF. In result we have two halfs of ending close field GF(q), where (q)- quatity of elements(field of Galua). If for example (q)=9, what we receive: GF(9)- that one half of field without taking into consideration symmetry, where is critical line, GF(9)=>GF(18)- that already field pattern(whole field), where critical line transform into axis line. In result identity F(z) and G(z)- that aspiration for supersymmetry. Further series O(F’) (extent 4) indispensable replace by O(1,3)- that line operator or group of Lorens, able preserve beginning of coordinates, and present group of transformations in space of Minkovki. In lasts notes of discussion evident developed alternative of proof, more distant. Thanks! Sergei.
30 November, 2016 at 3:10 am
gavinwraith
It seems to me that the Lagrange reversion formula is a formal consequence of the fact that in the free noncommutative ring generated by D and X satisfying DX-XD=1 we have an automorphism given by rotation through 90 degrees in the X,D plane: i.e. (D,X)=>(X,-D).
If T(f,a) is defined to be X+\sigma_k(a^k/k!.D^(k-1)(F(X)^k)) do we not have T(T(f,a),b)=T(f,a+b)?
Please excuse the tattered non-LaTeX.
30 November, 2016 at 9:02 am
Terence Tao
The formal translations
do obey the group action property
, but as noted in the main post, this is not quite the operation involved in this power series problem because
is also raised to a power inside the derivatives.
2 January, 2017 at 7:45 pm
Richard Stanley
Here is a combinatorial interpretation of
. Let
. Then
, where (a)
is
-gon, (b)
, where
has
regions with
sides, and (c)
is the
(i.e.,
plus the number of
, where now
.
the set of all ways to draw a set of nonintersecting diagonals in a
convex
total number of edges of
diagonals). If one allows curved diagonals so that any number of
diagonals can exist between two vertices, thereby creating some
regions with two edges, then the formula becomes
Example. The coefficient of
in
is
. Thus for instance there are
.
five ways to draw diagonals in a pentagon to create one triangle and
one quadrilateral. The number of diagonals is 1, so the total number
of edges is 6. This gives the term
6 January, 2017 at 5:05 pm
Tom Copeland
This is essentially http://oeis.org/A133437 and http://oeis.org/A111785 with the interpretation given in the referenced link therein “Polygonal dissections and series reversion” by Schuetz and Whieldon (http://arxiv.org/abs/1401.7194)–all related to the Stasheff associahedra, isn’t it? In which case you are missing some signs.
6 January, 2017 at 5:14 pm
Tom Copeland
Or, somehow $a_1$ should be replaced by $1+a_1$ in the final formula?
7 January, 2017 at 7:06 pm
Tom Copeland
Richard Stanley, can you give me a Web-accessible ref on details of the combinatorics?
7 February, 2017 at 4:07 pm
Xinrong Ma
Dear Tao, your result is a direct consequence of the Lagrange inversion formula.
29 May, 2017 at 7:12 pm
Anonymous
When teaching Mathematical Analysis several years ago, I did some research on the Lagrange inversion formula. There are two popular proofs: one is given by Laplace, by using the implicit function theorem; the other one is given by Hermite, by using the Cauchy integral formula. One can find both of them in Goursat’s “A Course in Mathematical Analysis” (yes, I know it has been 113-years-old, but still very good, containing a lot of interesting things).
However, both of them are not the “best” one, because this formula can appear in Mathematical Analysis I, but both methods use higher knowledges. Finally, I find a “brute force” method, without using any “higher” knowledge: prove Faà di Bruno’s formula first, which is a “Mathematical Analysis I” theorem, and can be proved by induction; then prove the Lagrange inversion formula by using Faà di Bruno’s formula. It is complicated, but doesn’t depend on the implicit function theorem or the Cauchy integral formula or any other knowledges that can not proved in Mathematical Analysis I.