20
$\begingroup$

The exponential generating function counting the number of graphs on $n$ labeled vertices satisfies (and is defined by) the equations $$ F'(x) = F(2x) \; \; ; \; \; F(0) = 1 $$ Is there some closed form or other nice description of this function? Does it have a name?


Of course, the series itself does not converge for any nonzero $x$, but like the Lambert W function (counting trees) it has combinatorial meaning. And the Lambert W function has a nice description as the inverse of $x e^x$; maybe there is a similar description of $F$?

$\endgroup$
12
  • 2
    $\begingroup$ Well, if the function is analytic at $0$, then its Maclaurin series is $$\sum \frac{2^{n(n-1)/2}}{n!},$$from repeated differentiation at $x = 0$, but I'm guessing you knew this. $\endgroup$ Jul 18, 2015 at 7:28
  • 1
    $\begingroup$ Yes I did. I've been making little errors like this all week :-( $\endgroup$ Jul 18, 2015 at 7:44
  • 3
    $\begingroup$ the power series's radius of convergence is zero though. $\endgroup$
    – mercio
    Jul 18, 2015 at 8:20
  • 3
    $\begingroup$ Hmm.. if we set $H(t)=F(\frac{1}{\log 2}2^{-t})$ then $H$ satisfies the delay differential equation $H'(t)=-2^{-t}H(t-1)$, which looks like it has many different solutions with $\lim_{t\to\infty}H(t)=1$ $\endgroup$ Jul 18, 2015 at 10:37
  • 1
    $\begingroup$ @6005: I don't. I just have the heuristic argument that you can choose $H$ freely on, say, the interval $[1,2]$ making sure the $H'(2)=-\frac12H(1)$, and then integrate the values of $H(t)$ up to $t=\infty$ numerically. Because of the $2^{-t}$ factor it should end up with a horizontal asymptote, which will be nonzero unless you're pretty unlucky. Then scale everything such that the limit is $1$ instead (the equation is linear after all). $\endgroup$ Jul 18, 2015 at 20:02

1 Answer 1

18
$\begingroup$

There are infinitely many differentiable functions $F\colon [0,\infty)\to\mathbb{R}$ that satisfy $$ F'(x)=F(2x)\qquad\text{and}\qquad F(0)=1. $$ We will follow the argument outlined by @HenningMakholm in the comments. First, consider the substitution $G(x) = F\left(\dfrac{2^x}{\log 2}\right)$. Plugging this into the above equation gives $$ G\,'(x) = 2^x G(x+1)\qquad\text{and}\qquad \lim_{x\to-\infty} G(x)=1. $$ This delay differential equation has a large number of solutions. Roughly speaking, one can choose any function for $G$ on $[0,1]$, and then define $$ G(x) = 2^{1-x}G\,'(x-1)\tag*{(1)} $$ recursively for $x> 1$, and $$ G(x) = G(0) - \int_{x+1}^1 2^{u-1} G(u)\,du\tag*{(2)} $$ recursively for $x<0$. (See this question for a simpler example of this kind of solution.)

Obstacles and Boundary Conditions

There are two obstacles to this construction:

  1. If $G$ is $C^n$ on the interval $(0,1)$, then $G$ will be $C^{n-1}$ on $(1,2)$ by equation (1), and then $C^{n-2}$ on $(2,3)$, and so forth. Thus, if we want $G$ to be everywhere defined, we must start with a $C^\infty$ function on $[0,1]$.

  2. If we start with an arbitrary $C^\infty$ function on $[0,1]$ and then switch to definition (1) for $x>1$, we must make sure that $G$ is $C^\infty$ at $x=1$, i.e. the the left and right hand derivatives of every order match up at this point.

For the second obstacle, repeatedly differentiating the equation $G(x+1)=2^{-x}G\,'(x)$ gives the sequence of equations $$ G^{(n)}(x+1) \;=\; \sum_{i=0}^n \binom{n}{i}(-\log 2)^{n-i}\,2^{-x}\, G^{(i+1)}(x) $$ and plugging in $x=0$ yields $$ G^{(n)}(1) \;=\; \sum_{i=0}^n \binom{n}{i}(-\log 2)^{n-i}\, G^{(i+1)}(0). $$ These are the boundary conditions that $G$ must satisfy on the interval $[0,1]$, but it is not hard to find $C^\infty$ functions that satisfy these, e.g. any bump function that satisfies $$ G^{(n)}(0) = G^{(n)}(1) = 0\;\;\text{ for all }n\geq 1 \qquad\text{and}\qquad G(1)=0. $$

The Limit as $x\to-\infty$

For negative values of $x$, the function $G(x)$ is defined by the integral equation $$ G(x) = G(0) - \int_{x+1}^1 2^{u-1} G(u)\,du\tag*{(2)} $$ If we assume that $G(x)\geq 0$ for $x\in [0,1]$ and, say, that $$ \int_0^1 2^{u-1} G(u)\,du \;<\; \frac{G(0)}{10} $$ then $\frac{9}{10}G(0) \leq G(x) \leq G(0)$ for all $x\in[-1,0]$. It follows recursively that $$ G(0) \;\geq\; G(x) \;\geq\; \left(\frac{9}{10} - \frac{1}{\log 4}\right)G(0) \;>\; 0 $$ for all $x<-1$, since \begin{align*} G(x) \;&=\; G(0)-\int_{x+1}^1 2^{u-1}G(u)\,du \\ &=\; G(0) - \int_0^1 2^{u-1}G(u)\,du - \int_{x+1}^0 2^{u-1}G(u)\,du \\ &\geq\; G(0) - \frac{G(0)}{10} - \int_{-\infty}^0 2^{u-1}G(0)\,du \\ &=\; \left(\frac{9}{10} - \frac{1}{\log 4}\right)G(0). \end{align*} Then $G$ is monotone on $(-\infty,0)$, so $\displaystyle\lim_{x\to-\infty} G(x)$ exists and is positive. Scaling $G$ linearly, we can arrange for this limit to be $1$.

$\endgroup$
0

You must log in to answer this question.

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