19
$\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$
  • 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$ – Theo Bendit Jul 18 '15 at 7:28
  • 1
    $\begingroup$ Yes I did. I've been making little errors like this all week :-( $\endgroup$ – Theo Bendit Jul 18 '15 at 7:44
  • 3
    $\begingroup$ the power series's radius of convergence is zero though. $\endgroup$ – mercio Jul 18 '15 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$ – Henning Makholm Jul 18 '15 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$ – Henning Makholm Jul 18 '15 at 20:02
16
$\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$

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.