4
$\begingroup$

I've encountered several identities in combinatorics that resemble inversion formulas, as shown below,

exp-log-correspondence

Here, $f_i, g_k$, $\forall i,k \in \mathbb{N}$, are coefficients of some formal power series.

I noticed that the coefficients in these sums are in resemblance with coefficients in the power series of $\ln(1+x), \exp{x} -1$, which suggests to me that they are related in some way to Lie group - Lie algebra correspondence.

However, I have not been able to find any discuss any textbook(s) that deal with these identities in full generality. I even don't have a name for such 'classes' of identities. I would really appreciate some resources that deal with this 'particular' form of identities.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ The general form here is "if a sequence $\left(g_0, g_1, g_2, \ldots\right)$ is obtained from a sequence $\left(f_0, f_1, f_2, \ldots\right)$ by some polynomial map $P = \left(P_0, P_1, P_2, \ldots\right)$, then $\left(f_0, f_1, f_2, \ldots\right)$ is in turn obtained from $\left(g_0, g_1, g_2, \ldots\right)$ by a certain polynomial map $Q = \left(Q_0, Q_1, Q_2, \ldots\right)$", right? Such identities are often called inversion formulas (e.g., binomial inversion) when the polynomials in question are linear. As you have noticed, compositionally inverse power series also yield such identities. $\endgroup$
    – darij grinberg
    Commented Sep 1, 2023 at 17:41
  • 1
    $\begingroup$ @SamHopkins Well I'm working with someone(Mahajan) who's a very close collaborator with one of authors in the above mentioned paper, and this paper was one of the reason why I am looking for resources done by other authors on studying this problem. I guess there is not a lot of work being done here! Please let me know if there is some other work that also deals with this problem! Also, thank you for taking your time to research for me, really appreciate it! $\endgroup$
    – total dependent random choice
    Commented Sep 1, 2023 at 18:08
  • 1
    $\begingroup$ Your image seems to be taken from somewhere. Where? $\endgroup$
    – LSpice
    Commented Sep 2, 2023 at 2:05
  • 1
    $\begingroup$ Do you have a link to those or similar lecture notes of your professor? $\endgroup$
    – Tom Copeland
    Commented Sep 2, 2023 at 15:26
  • 1
    $\begingroup$ @TomCopeland I would have to check with my Prof. to see if I can share those :) $\endgroup$
    – total dependent random choice
    Commented Sep 2, 2023 at 17:31

2 Answers 2

Reset to default
12
$\begingroup$

The reason this is called the "exp-log" correspondence is that it can be written in terms of formal power series as follows: write $G(z) = \sum g_n z^n, F(z) = \sum f_n z^n$. We need the additional hypothesis that $f_0 = 0, g_0 = 1$ which doesn't appear to be mentioned. Then

$$G(z) = \exp F(z) \Leftrightarrow F(z) = \log G(z).$$

The significance of this particular relationship between two formal power series goes under the name "the exponential formula" (as far as I know, anyway). Loosely speaking, if $G(z)$ is the exponential generating function of structures of some sort which admit a decomposition into connected components (e.g. graphs of some sort), then $F(z)$ is the exponential generating function of connected structures. More precise statements are possible, e.g. I give one in this blog post in terms of the free symmetric monoidal groupoid on a groupoid.

For a textbook reference you can consult Stanley's Enumerative Combinatorics Vol. II, section 5.1.

Improve this answer
$\endgroup$
1
  • $\begingroup$ So more generally if we have two formal power series $A(x)=\sum_{n \geq 1} a_n x^n$, $B(x) = \sum_{n \geq 1} b_n x^n$ that are compositional inverses $A^{\langle -1 \rangle} = B$, then we get the same formula $g_n = \sum_{(c_1,\ldots,c_k)\models n} a_k f_{c_1} \cdots f_{c_k} \Leftrightarrow f_n = \sum_{(c_1,\ldots,c_k)\models n} b_k g_{c_1} \cdots g_{c_k}$. The case from the question-asker is given by taking $A(x) = e^x - 1$ and $B(x) = \log(x+1)$. $\endgroup$
    – Sam Hopkins
    Commented Sep 4, 2023 at 13:32
3
$\begingroup$

A good starting point for a literature search on this and related types of inversion formulas is OEIS A036040 which will lead you to a slew of general theorems and generalizations as well as explicit concrete examples significant in combinatorics, analysis, algebra, and physics.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .