11
$\begingroup$

[update]: I made the question more precise, more general and added a follow up question

Considering the iteration of functions (with focus on the iterated exponentiation) I'm looking, whether some function which I want to iterate can -hopefully with some advantage- itself be expressed by iterations of a -so to say- "more basic" function.

Fo example I assume a function $f(x)$ such that

$ \qquad \displaystyle \exp(x) = x \cdot f^{\circ 1}(x)\cdot f^{\circ 2}(x)\cdot f^{\circ 3}(x)\cdots $
$\qquad \qquad$ (where the circle-notation means iteration, and $f^{\circ 0}=x, f^{\circ 1}(x)=f(x)$)

and first I ask: what does this function $f(x)$ look like?

What I'm doing is this substitution: $$ \small \begin{array} {lrll} 1.& \exp(x) & = &x & \cdot f^{\circ 1}(x) & \cdot f^{\circ 2}(x) & \cdot f^{\circ 3}(x) & \cdots \\ 2.& \exp(f(x))&= && f^{\circ 1}(x) & \cdot f^{\circ 2}(x) & \cdot f^{\circ 3}(x) & \cdots \\ \\ \\ 3.& {\exp(f(x))\over \exp(x) } & = & \frac 1x \\ \\ & \exp(f(x)) & = & &{ \exp(x) \over x} \\ \\ \\ 4. & f(x)&=& x & - \log(x) \end{array} $$ $ \qquad \qquad $ (From 1. and 4. I know, that x is now restricted to $x \gt 0$)

As some comments point out, the construction of the function $f(x)$ is underdetermined; so in step $3.$ numerator and denominator can have a common factor $c$ such that we'll have
$$ \small \begin{array} {lrll} 1a.& \exp(x)\cdot c & = &x & \cdot f^{\circ 1}(x) & \cdot f^{\circ 2}(x) & \cdot f^{\circ 3}(x) & \cdots \\ 2a.& \exp(f(x)) \cdot c&= && f^{\circ 1}(x) & \cdot f^{\circ 2}(x) & \cdot f^{\circ 3}(x) & \cdots \end{array} $$

If I do now the computation with some example $x$ by $$ y = x \cdot f^{\circ 1}(x)\cdot f^{\circ 2}(x)\cdot f^{\circ 3}(x)\cdots $$ I get for all tested $x>0$ the result $$ y = \exp(x) / \exp(1) $$ such that indeed a cofactor $c$ occurs and that it is precisely $1 / \exp(1)$

Q1: Where does this additional factor in the empirical evaluation come from? Where have the above analytical steps missed some crucial information?

The question can made more precise:
Q2: How does the empiricial computation determine, that the cofactor $c$ is just $1/\exp(1)$ ?

(The comments of @Eric Wong adress this questions, but I've not yet made it explicite)


In reviewing my own question, a generalization is possible in that I can use any base $b$ with $\log(b)\ge 1$ such that

$ \qquad \displaystyle {b^x \over b} = x \cdot f_b^{\circ 1}(x)\cdot f_b^{\circ 2}(x)\cdot f_b^{\circ 3}(x)\cdots $

and the constant $c$ comes always out to equal $1/b$ such that we might as well write
$ \qquad \displaystyle b^{x-1} = x \cdot f_b^{\circ 1}(x)\cdot f_b^{\circ 2}(x)\cdot f_b^{\circ 3}(x)\cdots $

Q3: Can Eric's comment made be more explicite such that it shall work for all that bases?


I observe, that for $\eta < \log(b) <1$ with $\eta \lt 0.39996 $ the sequence of iterates of the functions $f_b(x)$ either approach $1$ alternating from below and above or don't approach $1$ at all but approach distinct accumulation-points... That observation is important here, because for such bases $b$ the above productformula does not work correctly, because we get sometimes no convergence to a single fixpoint. But due to the remark of @did I moved that question into a separate thread
A code snippet using Pari/GP:

f(x) = x-log(x)  \\ define the function 

x0=1.5
     \\  = 1.50000000000
[tmp=x0,pr=1]              \\ initialize
for(k=1,64,pr *= tmp;tmp = f(tmp));   pr   \\ compute 64 terms, show result
      \\ = 1.64872127070

exp(x0)        \\ show expected value
       \\ = 4.48168907034

pr*exp(1)      \\ show, how it matches
       \\  = 4.48168907034


Here is an example which shows the type of convergence; I use $x_0=1.5$ and internal precision of 200 decimal digits. Then we get the terms of the partial product as $$ \small \begin{array} {r|r} x_k=f^{\circ k}(x) & (x_k-1) \\ \hline 1.50000000000 & 0.500000000000 \\ 1.09453489189 & 0.0945348918918 \\ 1.00420537512 & 0.00420537512103 \\ 1.00000881788 & 0.00000881787694501 \\ 1.00000000004 & 3.88772483656E-11 \\ 1.00000000000 & 7.55720220223E-22 \\ 1.00000000000 & 2.85556525627E-43 \\ 1.00000000000 & 4.07712646640E-86 \\ 1.00000000000 & 8.31148011150E-172 \\ 1.00000000000 & 1.020640763E-202 \\ 1.00000000000 & 1.020640763E-202 \\ \cdots & \cdots \end{array} $$

$\endgroup$
  • $\begingroup$ I don't follow how you got $y=\exp(x)/\exp(1)$. If all you do is substitute $y=\exp(x)$ in the above calculation of course you should arrive at the same conclusion. Could you elaborate on how you arrived at this result? $\endgroup$ – nullUser Mar 12 '13 at 1:28
  • $\begingroup$ @nullUser: eqn. 2 comes from eqn. 1 just by inserting $f^{\circ 1}(x)$ instead of $x$, which is simply $f^{\circ 0}(x)$. Then all the infinite product "shifts" one position to the right $\endgroup$ – Gottfried Helms Mar 12 '13 at 1:31
  • $\begingroup$ I understand that part. I follow the calculations all the way through $f(x)=x-\log(x)$. But then you claim that if $y = x f \cdots$ then $y=\exp(x)/\exp(1)$ which does not follow from any of the previousq calculations. $\endgroup$ – nullUser Mar 12 '13 at 1:33
  • 4
    $\begingroup$ I'd also like to see this derived, but I wouldn't call it an extra factor. Notice that your calculation to deduce $f(x)$ goes through exactly the same for $\exp(x) = C\cdot x \cdot f(x) \cdot f(f(x)) \cdots$. In other words, the original assumption overdetermines $f(x)$. $\endgroup$ – Erick Wong Mar 12 '13 at 1:42
  • 1
    $\begingroup$ To answer my own question, I suppose it converges simply because when $x = 1+\epsilon$, $x - \ln x \approx 1 + \tfrac12\epsilon^2$, so the product is very rapidly convergent once the terms approach $1$. $\endgroup$ – Erick Wong Mar 12 '13 at 2:10
4
$\begingroup$

Say that $f$ solves $(\ast)$ for $g$ if $g(x)=x\cdot f(x)\cdot f\circ f(x)\cdot f\circ f\circ f(x)\cdots$, in the sense that the product in the RHS converges and that its value is $g(x)$, for every positive $x$.

The computations in the post and in some comments show that, if $f$ solves $(\ast)$ for $g:x\mapsto c\mathrm e^x$ for some positive $c$ then $f:x\mapsto x-\log x$, and that $f:x\mapsto x-\log x$ indeed solves $(\ast)$ for $g:x\mapsto\mathrm e^{x-1}$ and not for any other $g:x\mapsto c\mathrm e^x$.

More generally, note that if $f$ solves $(\ast)$ for $g$ then $g(f(x))=f(x)\cdot f\circ f(x)\cdot f\circ f\circ f(x)\cdots$ hence $$ x\cdot g(f(x))=g(x). $$ Assuming that $g$ is invertible, for example because $g$ is increasing, we consider the function $Tg$ defined by $$ Tg(x)=g^{-1}(g(x)/x). $$ Then the only possible solution of $(\ast)$ is $f=Tg$, in particular $f$ is unique and such that $f(1)=1$ when it exists. Thus, for $(\ast)$ to have solutions, one must assume that $g(1)=1$.

Assume furthermore that $g'(1)$ exists, thus, $g(1+\varepsilon)=1+g'(1)\varepsilon+o(\varepsilon)$ when $\varepsilon\to0$. Then $Tg(1+\varepsilon)=1+\eta$ with $g'(1)\eta+o(\eta)=(g'(1)-1)\varepsilon+o(\varepsilon)$. If $g'(1)\lt1/2$, the point $1$ is repulsive for $f$ hence the product in the RHS of $(\ast)$ diverges and $(\ast)$ has no solution. If $g'(1)\gt1/2$, the ratio $(g'(1)-1)/g'(1)$ is in $(-1,1)$ hence the infinite product converges and $(\ast)$ has the unique solution $Tg$.

In the specific case when $g(x)=\mathrm e^{x-1}$, then $g'(1)=1$ hence $(\ast)$ has a unique solution $f=Tg$ and one knows that $Tg:x\mapsto x-\log x$.

In the specific case when $g(x)=b^{x-1}$ for some positive $b$, then $g'(1)=\log b$ hence $(\ast)$ has a unique solution $f=Tg$ when $b\gt\sqrt{\mathrm e}$ and one knows that $Tg:x\mapsto x-\log_b x$, and $(\ast)$ has no solution when $b\lt\sqrt{\mathrm e}$.

In the limit regime $b=\sqrt{e}$, a more careful analysis of the sequences $(x_n)$ defined by $1+x_{n+1}=Tg(1+x_n)$ shows that $(x_n)$ is ultimately alternated (decreasing in modulus and alternatively positive and negative for every $n$ large enough), thus the infinite product $\prod\limits_n(1+x_n)$ converges and $(\ast)$ has a unique solution $f=Tg:x\mapsto x-2\log x$ in this case too.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice, thank you! Especially for the arguments about the bases $1 \lt b \lt \sqrt e$ and $\sqrt e \le b \le e$ at which I'll look deeper in the afternoon. (replacing old comment because of funny typos ...) $\endgroup$ – Gottfried Helms Jul 17 '13 at 18:14
1
$\begingroup$

The constant c from (1a) is canceled out in step (3). The constant c must be calculated after f(x) is obtained. One way is numerically. Other way is algebraically, but I don't know yet how to.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Not a complete answer, but possibly a start... We may observe, that for $x=0$ the lhs is nonzero, so in the rhs the infinite product is $0 \cdot f(0) \cdot \ldots$ and the $f^{\circ k}(0)$ must account for that zero-cofactor. Now if we have $f(x) = x - \log(x)$ then this is indeed infinite at zero - but this option might be the/one reason for the problem.

If we reformulate the function f(x) such that $$ \exp(x) = (x+1) \cdot f^{ \circ 1}(x+1) \cdot \ldots $$ then at x=0 we have on the rhs a product of all ones, which is what "we would like" and we could rewrite $$ \exp(x-1) = {\exp(x) \over e } = x \cdot f^{ \circ 1}(x) \cdot \ldots $$ and get the relation, which we actually find empirically.
However, I think that argument must be made stronger and more formal - as far as my thoughts go it is merely a hint.
[update]: Also, changing the function this way, such that $g(x) = (x+1) + \log(1+x)$ crashes the infinite product, it becomes badly divergent...

Additionally, this reminds me of a similar-looking effect, namely the incomplete gamma function , where the ratio of the incomplete gammas at x and at x+1 behave like the gamma itself, but have an additional constant term -for instance $\frac 1e$-, which is also expressed by some integral. However - this is only a vague feeling of being related in a way, I cannot really formalize ...

| cite | improve this answer | |
$\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.