12
$\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$
11
  • $\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
    Commented Mar 12, 2013 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$ Commented Mar 12, 2013 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
    Commented Mar 12, 2013 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
    Commented Mar 12, 2013 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
    Commented Mar 12, 2013 at 2:10

3 Answers 3

5
$\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.

$\endgroup$
1
  • $\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$ Commented Jul 17, 2013 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.

$\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 ...

$\endgroup$

You must log in to answer this question.

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