Looking for a function such that…

There was this question on one of the whiteboards at my company, and I found it intriguing. Maybe it's a dumb thing to ask. Maybe there is a simple answer that I couldn't see. Anyway, here it is:

Does there exist a non-trivial, monotonically increasing function such that $f'(x) = f(f(x))$ (in $\mathbb{R}$)?

I checked a bunch of functions, from elementary to special (gamma, digamma, zeta, Riemann, Lambert ...) and none seems to work (not surprisingly). I managed to convince myself that a function expressible as a power series would not work, regardless of convergence issues, because the derivative lowers the degree of polynomials, when the composition raises it. The Dirac delta or some sort of generalized function looked promising for a while, but the Dirac delta is not monotonically increasing anyway, and I'm not very familiar with generalized functions. I tried to use the Fourier transform on both sides, but it seems the Fourier transform is difficult for f(f(x)) (at least for me). I thought about somehow seeing "taking the derivative" as a differential operator, finding its (infinite) matrix in some basis (which one?), do the same thing to the RHS and show that the 2 matrices could not be identified (reducing the problem to a linear algebra problem) - that didn't work. Nothing on the geometric front either. I thought about trying to prove that there is no such function by deducing a contradiction, but didn't manage that. My hunch is that no such function exists, based on the completely invalid and semi-meaningless idea that differentiation pulls f in one direction, and composition in the other. Any idea?

-
At least for exp(x) I wouldn't say that the derivative works in the opposite direction from composition. –  Bitwise Oct 10 '12 at 2:32
It sounds like you want an analytic solution. I would start by defining f(x) in terms of a Taylor series, composing it with itself, taking the derivative, and trying to match terms. That might give you a solution near zero. I have lost my access to Mathematica or I would try it. –  Ross Millikan Oct 10 '12 at 2:42
Again, I am fully aware that this "hunch" is "invalid" and "semi-meaningless". Although exp(exp(x)) seems to be in another category of complexity than exp(x). At least, it takes more characters to describe exp(exp(x)). Composition seems to have made exp more complex, where differentiation hasn't. Again, doesn't mean much. –  Frank Oct 10 '12 at 2:45
@Ross - I'll take a proof by contradiction. I just played around with as many functions as I could to get a feel for what is going here. –  Frank Oct 10 '12 at 2:48
@Ross - I tried, it doesn't look very promising. Ignoring convergence issues (yeah!) and working first in a neighborhood of zero, the LHS yields a first term of f'(0) while the LHS yields f(f(0)). The higher order derivatives of the RHS and LHS don't seem to yield more information than what you can get by taking successive derivatives of f'(x) = f(f(x)) - which I had tried, and not gotten very far with. Of course, I might be doing this wrong... –  Frank Oct 10 '12 at 2:54

2 Answers

FYI this was problem B5 in the 2010 Putnam exam, so you can find it here: http://amc.maa.org/a-activities/a7-problems/putnamindex.shtml

They had a pretty succinct solution. Suppose $f$ is strictly increasing. Then for for any $y_0$ you can define an inverse funciton $g(y)$ for $y>y_0$ such that $x=g(f(x))$. Differentiating, we get $1=g'(f(x))f'(x)=g(f(x))f(f(x))$, so that $g'(y)=\dfrac{1}{f(y)}$. We know that $g$ obtains arbitrarily large values since it is the inverse function of $f$ and $f$ is defined for all $x$, which means $g(z) - g(y_0) = \displaystyle \int_{y_0}^zg'(y)dy = \int_{y_0}^z\frac{dy}{f(y)}$ must diverge as $z\rightarrow\infty$.

Now all we have to do is show that $f$ is bounded below by a function that causes the integral to converge. For $x>g(y_0)\equiv g_0$, we have $f'(x)>g_0$, so we can assume that for some $\beta$ and $x$ large enough, $f(x)>\beta x$. Iterating this argument, we get that $f(x)>\alpha x^2$ for some $\alpha$ and $x$ large enough. So we can assume that $f(x)$ is asymptotically greater than $\alpha x^2$. But then the integral above converges, contradicting that $g(z$) is unbounded as $z\rightarrow\infty$. Thus, we conclude that $f$ cannot be strictly increasing.

-

Another partial answer...

First of all call $L^+, L^-$ the limits at $\pm\infty$ (which exist by monotonicity). The result I prove is the following:

$\textbf{Partial result.}$ Assume $L^+<\infty$ then $f=0$

We have the following 'obvious' remarks

1. If $f$ is a solution then $f\in C^{\infty}(\mathbb{R})$.

2. Since composition of monotone functions are monotone we have that $f'\geq0$ and is monotone increasing. This also implies $f$ convex.

Now, a continuity argument together with the second remark imply that $L^->-\infty$ (otherwise there is a point with $f'(x)<0$). Now the FTC gives for $x<a$

$$f(a)-f(x)=\int_x^{a} f'(t)dt$$ and letting $x\to -\infty$ and the monotone convergence theorem ($f'\geq0$) we conclude $f'\in L^1(-\infty,0)$. In a similar way we can get that $f'\in L^1(0,\infty)$ whenever $L^+<\infty$. All this together then yields: If $L^+<\infty$ then $f'\in L^1(\mathbb{R})$ and $f'$ continous and monotone, and so

$$\lim_{x\to \pm\infty} f'(x)=0$$

which in turn gives $f'=0$ and so $f$ is constant, but the only possible constant solution is $0$.

Now, in case $L^+=\infty$: Since $f(x)\to \infty$ when $x\to \infty$, we have that $f'$ also blows up. Pick $a\in (0,\infty)$ such that $f'(a)>1$ and $f(a)>1$, then for $x>2a$ we have (integrate twice the inequality $f\geq0$)

$$f(x)\geq xf'(a)+f(a) \geq x$$ Plugging this in the equation gives $f'(x)\geq f(x)$. Gronwall's inequality then gives

$$f(x)\geq e^{x-a}$$ Plugging this in the equation gives again

$$f'(x)\geq f(e^{x-a}) \geq e^{e^{x-a}-a}$$ this we can integrate, and iterate the procedure, but I don't see a helpful estimate being easy to obtain this way.

-
Can you substantiate that f is smooth? You might be right, but it is not so obvious to me. Otherwise, from trying to construct f directly (without success), I "knew" that f has very fast growth, at least faster than exp(x). I checked a bunch of known functions with very fast growth (Ackermann, hyper-exponential...) none of which worked. –  Frank Oct 10 '12 at 14:11
@Frank We know that $f(f(x))$ is smooth, because the composition of smooth functions is smooth, so $f'(x) is too. You can then just differentiate both sides, use the chain rule, and induct. – Potato Oct 10 '12 at 14:35 OK, so we know a few things about f, if it exists: it's smooth, convex, monotonically increasing, and it grows faster than x/2 times an infinite exponential tower of x/2. If it exists. That kind of narrows the possibilities some, I'd say :-) Is Lambert's W going to be helpful? – Frank Oct 10 '12 at 16:03 @Jose27 Following up on your conclusion, I think the infinite exponential tower (iterating exp(exp(exp(....x))) diverges for all values of x in R. Is that enough to show that f indeed does not exist? – Frank Oct 11 '12 at 1:24 @Frank: I've edited, my use of Gronwall's inequality was wrong, and correcting it ruins an 'obvious' blow up (at least I don't see it clearly). To be clear, we still have that$f\to \infty$very fast, but we would like to conclude, as you said, that$f=\infty$for$x\$ big enough. This is not clear from the bound that I obtain. –  Jose27 Oct 11 '12 at 5:18