40
$\begingroup$

The formal group law associated with a generating function $f(x) = x + \sum_{n=2}^\infty a_n \frac{x^n}{n!}$ is $$f(f^{-1}(x) + f^{-1}(y)).$$ In my thesis, I found a large number of examples of formal group laws that have combinatorial interpretations and thus have nonnegative coefficients. In Sec 9.1 I conjectured the following characterization for positivity of a formal group law:

Conjecture. $f(f^{-1}(x) + f^{-1}(y))$ has nonnegative coefficients if and only if $$\phi(x) = \frac{1}{\frac{d}{dx} f^{-1}(x)}$$ has nonnegative coefficients.

At least one direction is easy: The positivity of the FGL implies positivity of $\phi(x)$.

I have not been able to prove the converse, but there is some evidence. Start with $$\phi(x) = 1 + t_1x + t_2\frac{x^2}{2!} + t_3\frac{x^3}{3!} + \cdots$$ for indeterminates $t_i$ and define $f(x)$ by $f(0) = 0$, $1/(f^{-1})'(x) = \phi(x)$, or equivalently, $f'(x) = f(\phi(x))$. Then we can compute the coefficients of $f(f^{-1}(x) + f^{-1}(y))$ and they seem to all be polynomials with nonnegative coefficients in the variables $t_i$.

Often it is more illuminating to consider the slightly more general symmetric function $$F = f(f^{-1}(x_1) + f^{-1}(x_2) + \cdots).$$ The expansion of $F$ in the monomial basis of the ring of symmetric functions is

\begin{align*} F = m_1 &+ (2t_1)\frac{m_{11}}{2!} + (3t_2)\frac{m_{21}}{3!} + (6t_1^2 + 6t_2)\frac{m_{111}}{3!}\\ &+ (4t_3)\frac{m_{31}}{4!} + (12t_1t_2 + 6t_3)\frac{m_{22}}{4!} + (36t_1t_2 + 12t_3)\frac{m_{211}}{4!} \\ &+ (24t_1^3 + 96t_1t_2 + 24t_3)\frac{m_{1111}}{4!} + (5t_4)\frac{m_{41}}{5!} + (30t_2^2 + 30t_1t_3 + 10t_4)\frac{m_{32}}{5!}\\ &+ (60t_2^2 + 80t_1t_3 + 20t_4)\frac{m_{311}}{5!} + (120t_1^2t_2 + 120t_2^2 + 150t_1t_3 + 30t_4)\frac{m_{221}}{5!}\\ &+ (420t_1^2t_2 + 240t_2^2 + 360t_1t_3 + 60t_4)\frac{m_{2111}}{5!} \\ &+ (120t_1^4 + 1320t_1^2t_2 + 480t_2^2 + 840t_1t_3 + 120t_4)\frac{m_{11111}}{5!}\\ &+ \cdots \end{align*}

Note that $f(x)$ here has a combinatorial interpretation due to Bergeron-Flajolet-Salvy: $f(x)$ is the exponential generating function for increasing trees weighted by their degree sequence in the variables $t_i$. So there is reason to think that there is a combinatorial interpretation of $F$ in terms of increasing trees.

An interesting special case if $\phi(x) = 1 + x^2$, so that $f(x) = \tan(x)$. Then the associated formal group law is a sum of Schur functions of staircase-ribbon shape: $$f(f^{-1}(x_1) + f^{-1}(x_2) + \cdots ) = \sum_{n=1}^\infty s_{\delta_{n} / \delta_{n-2}}$$ where $\delta_n$ is the partition $(n,n-1, n-2, \ldots, 1)$. (See Ardila-Serrano, Prop 3.4.) This can also be interpreted in terms of binary increasing trees.

In many examples given in my thesis I found that there was a combinatorial interpretation of the FGL in terms of chromatic symmetric functions, but I was not able to apply those methods to this more general case.

Edit: Tom Copeland suggested I share some of the Sage code I used to generate these coefficients. Here is a Jupyter notebook in CoCalc that shows the computations.

$\endgroup$
  • $\begingroup$ Observation: The coefficient of $m_{11 \cdots 1}$ appears to be oeis.org/A145271 . $\endgroup$ – David E Speyer Feb 1 '18 at 15:25
  • $\begingroup$ @DavidESpeyer: Yes, in general, the coefficient of $m_{1^n}$ will be $a_n = [x^n]f(x)$. $\endgroup$ – Jair Taylor Feb 1 '18 at 16:54
  • $\begingroup$ (or $a_n = [x^n/n!]f(x)$ in the exponential notation above.) $\endgroup$ – Jair Taylor Feb 1 '18 at 17:05
  • 1
    $\begingroup$ Jair, in your thesis, part 2. of the definition of contractible species there seems to be a typo, since there are two $\sigma$s.I suppose it should read "so that there is an $\mathcal F$-structure $\omega\in \mathcal F(V\smallsetminus U\cup {v})$ for some $v$ and $\tau\in\mathcal F(U)$ with $\sigma = \omega(v\leftarrow \tau)$"? $\endgroup$ – Pedro Tamaroff Feb 2 '18 at 11:38
  • 2
    $\begingroup$ @JairTaylor: I turned some of the formal group laws in your thesis into statistics on integer partitions, see findstat.org/…. I chose the smaller normalisation, because the numbers become huge. Feel free to add more! Do you have a combinatorial interpretation (in terms of counting objects associated with the integer partition) for the coefficients (suitably normalized) of one of these? $\endgroup$ – Martin Rubey Feb 3 '18 at 12:35
15
+50
$\begingroup$

Given $\phi(x)\in\mathbb{R}[[x]]$, with $\phi(0)=1$, we have defined $g(x):=\int^x_0{dt\over \phi(t)}$, $f:=g^{-1}$ and $$F(x,y)=f\big(g(x)+g(y)\big)=\sum_{n=0}^\infty \psi_n(x) {y^n\over n!}\in\mathbb{R}[[x,y]].$$ Let's write a recursion for the coefficient sequence $\psi_n=\partial_y^nF(x,0)\in\mathbb{R}[[x]]$, solving by series the differential equation satisfied by $F$,

$$\cases{\phi(x)\, F_x(x,y)=\phi(F(x,y))\\ F(x,0)=x\ .}$$

One finds $\psi_0=x$, $\psi_1=\phi,\dots$ . Let's take $\partial_y^n$ at $ {y=0}$ on both sides. Faà di Bruno: $$\partial_y^n\big( \phi\circ F\big)\big|_{y=0}=\Big(\sum_{\alpha\in\operatorname{par}[n]} \phi_y^{(|\alpha|)} (F)\, \prod_{s\in\alpha} \partial_y^{|s|}F \Big) \ \Big|_{y=0} =\sum_{\alpha\in\operatorname{par}[n]} \phi^{(|\alpha|)}(x) \prod_{s\in\alpha} \psi_{|s|}(x) ,$$ (Legenda: The sum is indexed on the set of all partitions of $[n]:=\{1,2,\dots,n\}$, and $|\cdot|$ denotes cardinality. The latter equality comes from $F(x,0)=x$ and $\partial_y^{j}F(x,y)\big|_{y=0}=\psi_j$). Now we isolate the term $\phi'\psi_n$, that corresponds to the partition $\alpha$ into a single class, from the terms of the sum indexed on the set of non-trivial partitions, with $|\alpha|>1$, denoted $\operatorname{par}^*[n]$. Note that each of these terms contains more than one factor $\psi_j$.

$$\phi\psi'_n -\phi' \psi_n =\sum_{\alpha\in\operatorname{par}^*[n]} \phi^{(|\alpha|)} \prod_{s\in\alpha} \psi_{|s|} .$$ Multiplying by the integrating factor $\phi^{-2}$ , and since $\psi_n(0)=0$, for $n>1$ $$ \psi_n(x) =\phi(x)\int_0^x\big(\!\sum_{\alpha\in\operatorname{par}^*[n]} \phi^{(|\alpha|)} \prod_{s\in\alpha} \psi_{|s|}\,\big)\phi^{-2}\ dt .$$

It is now clear by complete induction that for any $n\ge1$, $\psi_n$ is equal to $\phi$ times a series with positive coefficients, proving your conjecture.

$\endgroup$
  • 2
    $\begingroup$ These computations look good to me. But why does the last equation have positive coefficients? The $\phi^{-2}(t)$ may have negative coefficients, no? $\endgroup$ – Jair Taylor Feb 9 '18 at 5:13
  • 1
    $\begingroup$ Yes, of course, but by the complete induction hypothesis $\psi_j=\phi \chi_j$ for $1\le j<n$, with $\chi_j$ a formal power series with positive coefficients, and there are at least two factors $\psi_j$ in each product, since it's on $s\in\alpha$ with $|\alpha|>1$... $\endgroup$ – Pietro Majer Feb 9 '18 at 5:37
  • 1
    $\begingroup$ Ah, I see! That makes sense, thanks! It would seem this is proven. Allow me to think through the implications of this a bit and then I'll accept your answer. $\endgroup$ – Jair Taylor Feb 9 '18 at 5:39
  • 1
    $\begingroup$ Computing the first terms of the sequence I got, $\psi_0=x$, $\psi_1=\phi$, $\psi_2=\phi(\phi'-t_1)$, $\psi_3=\phi({\phi'}^2+\phi''\phi-t_2-3t_1\phi''+3t_1t_2)$. The feeling is that $\psi_n$ could be always a polynomial with integer coefficients in $\phi,\phi',\dots,\phi^{(n-1) }$. $\endgroup$ – Pietro Majer Feb 9 '18 at 23:08
  • 2
    $\begingroup$ This all makes sense to me. I think it should lead to a combinatorial interpretation as well. I'll need to think about that. $\endgroup$ – Jair Taylor Feb 10 '18 at 0:10
9
$\begingroup$

This is really just a comment. Your question is equivalent to the following: if we have a formal group law $$ F(x,y) = x + y + \sum_{i,j>0} a_{ij}x^iy^j \in \mathbb{Q}[[x,y]] $$ with $a_{1j}\geq 0$ for all $j$, is it true that $a_{ij}\geq 0$ for all $i$ and $j$? As you say, the coefficients $a_{ij}$ can be expressed as polynomials in the coefficients $a_{1j}$, and these polynomials appear to have nonnegative coefficients, but I have not succeeded in finding a proof of that.

Your thesis is interesting. Your "contractible species" are essentially operads with a kind of nondegeneracy condition that is usually satisfied. I have never seen a connection between operads and formal group laws before, but it seems like a promising direction of investigation, which might be relevant for applications of formal group laws in algebraic topology.

$\endgroup$
  • $\begingroup$ Yes, you can formulate it this way. Actually, noticing that experimentally was what originally lead me to this conjecture. I do think contractible species are related to operads, but I wasn't aware of them when I wrote this. $\endgroup$ – Jair Taylor Feb 1 '18 at 17:01
  • 1
    $\begingroup$ Perhaps you would be interested in Petersen's answer to mathoverflow.net/questions/259374/…. $\endgroup$ – Tom Copeland Feb 2 '18 at 16:30
  • $\begingroup$ @JairTaylor and Neil: From every contractible species $X$, you should be able to produce two shuffle operads (I haven't realized how to define composition here), one $X^C$, depending on connected components of hypergraphs of structures, and another $X^M$ depending on minimal edge sets on hypergraphs of structures, and it seems you main theorem rests on the fact that $X^M$ is a free right $X^C$-module over $X$. In fact, the arrows $A_n\to B_n$ for $n\in\mathbb N$ assemble to give a weighted bijection $X\circ X^C \to X^M$, and what remains to verify is this is a map of right $X^C$-modules. $\endgroup$ – Pedro Tamaroff Feb 4 '18 at 20:58
  • $\begingroup$ (The catch here is to understand how $X^M$ and $X^C$ naturally become shuffle operads, and show $X^M$ becomes a right $X^C$-module. This seems to depend on understanding how minimal edge sets and connected components of hypergraphs change upon the operadic composition one can obviously endow $X$ with, using the operations defined in the thesis.) $\endgroup$ – Pedro Tamaroff Feb 4 '18 at 21:01
  • 1
    $\begingroup$ @PedroTamaroff If you think you know the right way to re-write the definitions in terms of operads and prove Theorem 2.1 using this language I'd be interested to see it. $\endgroup$ – Jair Taylor Feb 4 '18 at 22:24
6
$\begingroup$

An equivalent problem is to show the positivity of the connection factors $c^1_{i,j}$ in the expansions

$$p_i(t)p_j(t) = \sum^{i+j}_{n=1}\; c^n_{i,j}p_n(t),$$

where $p_n(t)$ are cycle index partition polynomials of the symmetric groups (A036039) with the indeterminates $x_n = (-1)^{n-1}h_{n-1}t \;$ and $h_n$ are the complete homogeneous symmetric polynomials with all of their indeterminates positive. The $c^1_{i,j}$ are essentially the coefficients of the FGL expansion Strickland displays. With $(a.)^n = a_n = f^{(n)}(0)\; $ and $\phi_n= n!t_n = e_n$, the elementary symmetric polynomials,

$$c^1_{j,k} = p_j(a.)p_k(a.)= p_j(t)p_k(t)|_{t^n=a_n}.$$

Jair, in your Sage computations, if the coefficients of f(x) are expressed as its Taylor series coefficients, i.e., they are normalized by the factorials, it is easier to recognize them as A145271, the refined Eulerian numbers. Same for your polynomials p, and if the coefficients of p are grouped together by powers of t and expressed as the elementary symmetric polynomials/functions $e_n=n!t_n=n!\phi_n \;$, it is easy to see they are signed A036039 with the appropriate determinates given above, e.g., $3! p_3 = 2(e_1^2-e_2)t - 3e_1t^2+t^3 = 2h_2t-3h_1t^2+t^3$.

See "Formal group laws and binomial Sheffer sequences" for details and examples.

Edit (Feb. 8, 2018):

The computations seem better characterized in terms of $f^{-1}(x)= x - (c_2x^2+c_3x^3+\cdots)$. Then $f(x)=e^{a.x}, \;$ where $a_n/n!$ are the refined face polynomials of the Stasheff associahedra (positive coefficients of A133437) and $p_n(t)$ are the refined Lah / Laguerre polynomials of A130561 with indeterminates $(x_1,x_2,x_3,..)= (t,-c_2t,-c_3t,..)\;,$ related to the elementary Schur polynomials. Then again $p_n(a.)=0$ and $c^1_{j,k}=p_j(a.)p_k(a.).$

Edit (Feb. 12, 2018):

Further to a conjecture by Majer,

$$f[f^{-1}(x)+f^{-1}(y)]=\exp[f^{-1}(y) \cdot \phi(x)D_x]x = \exp[y \cdot p.(\phi(x)D_x)]x,$$

so

$$\psi_n(x) = p_n(\phi(x)D_x)x.$$

The iterated infinitesimal generator is given in terms of $t_n$ by A139605 (the Comtet A polynomials), which acting on $x$ gives A145271 (the refined Eulerian polynomials, call them $a_n(x)$) all with integer coefficients. The polynomials $p_n(x)$ may be expressed as the the refined Stirling polynomials of the first kind (cycle index polynomials for $S_n$), noted above, or as numerous other composition partition polynomials. Then indeed we have the integer coefficients as Majer feels for

$$\psi_n(x) = p_n(a.(x))$$

with $\psi_n(0)=\delta_{n-1}.$

These polynomials and operators can be represented as various combinatoric structures, so with nice combinatorial interpretations of compositions can the ultimate constructs.

Edit (Apr 9, 2018): Here's an excerpt from an email to me from Nigel Ray in 2014 concerning Rota's interest in this topic:

"I'm afraid that "Extensions of UC (I)" long predates latex, but here's a link to the Advances

http://www.sciencedirect.com/science/article/pii/0001870886900654

(so long as you have permission). It was Gian-Carlo Rota who suggested I write this up, when I bumped into him one day in Berkeley - he was intrigued by the connection with formal group laws. When I got the chance to explain this to him in more detail (I think it was in Boston) he homed in on the fact that it explained the unresolved question he had always had with binomial sequences - namely how to express their products as linear combinations of themselves. I still think of UC as "formal group laws via Hurwitz Series" (ie divided formal power series), and hope there remains scope for developing that viewpoint."

$\endgroup$
  • $\begingroup$ The FGL for $\phi(x)=(1+ax)(1+bx)= 1+e_1x+e_2x^2$ is given in the OEIS entry for the Eulerian numbers oeis.org/A008292 in my 2014 formulas. $\endgroup$ – Tom Copeland Feb 2 '18 at 16:21
  • $\begingroup$ Corrected $x_1=h_0t=t$. $\endgroup$ – Tom Copeland Feb 3 '18 at 15:33
  • 1
    $\begingroup$ The last expression for $\psi_n$ is an umbral composition, which can be related to multiplication of lower triangular matrices with diagonal elements all ones, so ultimate combinatorial interpretations would be related to umbral composition of structures, interestingly. $\endgroup$ – Tom Copeland Feb 12 '18 at 22:01
  • $\begingroup$ @Jair Taylor, btw, positivity is not necessary for combinatorial interpretations; e.g., recall the Euler formula, see mathoverflow.net/questions/272583/… and the ref to Hope monoids there in my comments, and note interpretations of the Vandermonde determinant. Negative signs seem to point to topological combinatorial interpretations. $\endgroup$ – Tom Copeland Feb 25 '18 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.