# Iterates of $f_b(x) = x - \log_b(x)$ - for $\log(b) \approx 0.399$: convergence to accumulation points or chaos?

In a previous question I arrived at the family of functions (depending on a real parameter b for the base of exponentiation/logarithm): $$f(x) = x - \log_b(x) \qquad \qquad b \gt 0$$ with the question whether, and if: to what, iterations converge if started at, say, $x_0=3$.

Let for convenience $\beta$ denote $\beta = \log(b)$ .

I find empirically, that for $\beta \ge 1$ $$\lim_{h \to \infty} f^{\circ h}(x_0) = 1$$ where the convergence is monotonuously from above. For some $\eta_1 \approx 0.498 \lt \beta \lt 1$ the limit is still $1$ but it converges from above and below $1$

For a range of smaller bases $b=\exp(\beta)$ with $\eta_2 \approx 0.3999 \lt \beta \lt 0.498 \approx \eta_1$ we get convergences to sets of accumulation points, with set lengthes $12,24,48,96, ???$ which might possibly extend to multiples of $12$ (or even of $3$) with arbitrary powers of $2$ .

Finally, for $\beta \lt \eta_2$ it seems, that there is no more convergence, and the sequence of iterates produces numbers which look quite random.

Q1: Can we approximate the values of the $\eta$'s more precise? Are there analytical descriptions for them?
Q2: Are the possible set-lengthes for the accumulation points indeed $12 \cdot 2^k$ ?

Examples: For $\beta = 0.41$ ,$b \approx 1.50681778511$ I get after 1000 initial iterations the following sequence of further iterates (read along rows)

  ...
0.264550328299,  3.50777903235,  0.446844683843,  2.41158665503,
0.264550328299,  3.50777903235,  0.446844683843,  2.41158665503,
0.264550328299,  3.50777903235,  0.446844683843,  2.41158665503,
0.264550328299,  3.50777903235,  0.446844683843,  2.41158665503,
0.264550328299,  3.50777903235,  0.446844683843,  2.41158665503,
0.264550328299,  3.50777903235,  0.446844683843,  2.41158665503,
0.264550328299,  3.50777903235,  0.446844683843,  2.41158665503,
0.264550328299,  3.50777903235,  0.446844683843,  2.41158665503,
...


The four different values are what I call "accumulation points" and the set-length for this base is just 4 .

[update] Although the question Q2 has been resolved/handled - here is the table to which I have referred when I was talking about sets of accumulation-points. However I had not noticed, that the cardinalities of the sets of accumulation-points are also depending on the starting value $x_0$ besides the parameter for the exponential base $b \lt \sqrt e$ and can be arbitrarily created. Initial value for this table was in all cases $x_0=3$: $$\begin{array}{l|l} \log(b) & \text{"set-length" or } \\ & \small \text{"No. of accumulation-points"} \\ \hline\\ 0.4 & 12 \\ 0.3999 & 24 \\ 0.39988 & 24 \\ 0.39987 & 24 \\ 0.399865 & 48 \\ 0.39986 & 48 \\ 0.399858 & 96 \\ 0.399857 & 96\\ 0.39985 & \small \text{-no sufficient convergence } \\ & \small \text{ achieved in 100000 iterations-}\\ \end{array}$$

-
As explained on the other page, $\eta_1=1/2=0.5000\ldots$ and the convergence indeed holds (with mathematical proof). // I do not understand what it is you call "convergences to sets of accumulation points". –  Did Jul 17 '13 at 10:37
@Did: if I decrease $\beta$ to some smaller value, the iterations of $f_b(x)$ do not converge to one fixpoint, but begin to cycle over a set of values (I think that are called "accumulation-points"). I added one example to my question –  Gottfried Helms Jul 17 '13 at 10:44
Sorry but I still do not get why you mention cycles of lengthes multiples of 12. For $1/\beta=2.2$ (thus $\beta\lt\eta_1=0.5$), W|A tells me $(0.466079,2.14556)$ is a 2-cycle. –  Did Jul 17 '13 at 10:53
In fact, for every $0\lt\beta\lt0.5$ there is exactly one 2-cycle. –  Did Jul 17 '13 at 11:02
@did: I really don't know what happens here. For instance, I take the basis b by $\beta = 0.4$ and calculate with internal precision in Pari/GP of 200 and also 800 digits, beginning at $x_0=3$ I get the 12 different accumulation-points over which the sequence of iterates eventually cycles as $\small \begin{array} {} 0.209280993485 & 4.11947465240 & 0.580160543207 & 1.94128658098 \\ 0.282909232637 & 3.43948214643 & 0.351179843367 & 2.96732187454 \\ 0.248172323862 & 3.73225212344 & 0.439722528704 & 2.49375094764 \end{array}$ –  Gottfried Helms Jul 17 '13 at 11:19

One important point in the system is $b=\sqrt{e}$, as was pointed out by Gottfried. For $b>\sqrt{e}$, there is a stable attracting fixed point for $f(x)=x-\log_b(x)$, and that fixed point is x=1. For $1.518120456732599974768513856<b<\sqrt{e}$, the fixed point in the neighborhood of one is repelling, and iterates starting in the neighborhood of one (but not equal to one) settle into a two cycle orbit. This value, $\approx1.5181$ is the next critical point in iterating f(x), and for bases less than that value, the system once again bifurcates.

Two cycle boundary base, where f(f(z0+delta))=z0-delta
b=1.518120456732599974768513856, with two-cycle fixed point values
If b is any smaller, the fixed points settle into a four cycle orbit
z0            0.3467994474160251099023657636
f(z0)         2.883510938240876275139117018
f(f(z0))      0.3467994474160251099023657636


For $1.499042192220287185464351750<b<1.518120456732599974768513856$, the fixed point starting in the neighborhood of one settles into a four cycle orbit. Below that point, the system would settle into an eight cycle orbit. I didn't calculate the next bifurcation point, where the eight cycle orbits become sixteen cycle orbits. As I understand complex dynamics, there is an infinite sequence of these power of two bifurcations, with each region smaller than the previous bifurcation region. This is Mandelbrot like behavior, though I wouldn't presume to know how to make a "Mandelbrot" like complex graph for Gottfried's function.

Four cycle boundary base, where f(f(f(f(z0+delta))))=z0-delta
b=1.499042192220287185464351750, with four-cycle fixed point values
If b is any smaller, the fixed points settle into an eight cycle orbit
z0            0.4802675808315708379198177213
f(z0)         2.291937799458985333070087006
f(f(z0))      0.2431639774409501127511516471
f(f(f(f(z0))) 3.736067056308005100926684146
f^5(z0)       0.4802675808315708379198177213


Gottfried looked at $b=\exp(0.4)$, which has a twelve cycle fixed point. This is a region of stability, that is actually past the infinite sequence of bifurcations, akin to a mini-Mandelbrot in the Mandelbrot set. Before getting to the mini-Mandelbrot region, you have to get past the infinite sequence of bifurcations, where chaos occurs, which seems to be near $b=\exp(0.4015293)$. For example, $b=\exp(0.4015295)$ is in the 512-cycle region, which is very close to the chaotic boundary.

edited with images updated. See this answer, How to figure out the starting point for this Mandelbrot? which has the ideal $z_0=1/\log(b)$ as the starting point for iterating f(x). Here is the main Mandelbrot "bug" generated from Gottfried's iterated function. Gridlines for the Mandelbrot image are 1/10, with the function varying from 1.425 to 1.725. You can see the main bifurcation line at $\exp(0.5)\approx1.65$. It looks like stackexchange resized the image, but if you right click, you can view the original at 750x500.

The algorithm I used works pretty well, with the $z_0$ starting point. Unfortunately, it appears that stackexchange edited out the exif comments from the .jpg files. Here is a zoom in, from 1.491 to 1.519, with grid lines of 1/100, showing the 8x bifurcation region. On the left, you can just make out Gottfried's region at 1.4918.

Here is the tip, from 1.44 to 1.50, with grid lines of 1/100. You can see several of the mini-mandelbrots.

Here is the biggest mini-mandelbrot, from 1.452 to 1.4544, with grid lines of 1/1000. This mini-mandelbrot has a main bulb with a 3-cycle, as compared with the 12-cycle from the mini-mandelbrot in Gottfried's question.

Finally, here is the amazing wide view, showing the infinite spiral, of radius $\exp(0.5)$, with the real values ranging from +/-1.66, and the imaginary maximum at 1.66 as well. Everywhere outside of this infinite circular spiral, the fixed attracting point is 1. The very larger black region in the center of the spiral between -0.6 and +1 is a computation artifact, where the base is close to zero. This is because the function escapes to +infinity instead of -infinity, so the algorithm incorrectly regards this as a stable fixed point region.

Here is a link to the pari-gp code. http://www.sheltx.com/pari/gottfried.gp

-
Wow. That's a surprising discussion - I had given up for further investigation of structure in the chaos... If we allow complex values for $x$ we might possibly be able to draw some Mandelbrot-analogon here? –  Gottfried Helms Jul 18 '13 at 20:38
$b=\exp(0.4015293271157)=1.494107931063626148066389010$ has a 262144, or $2^{18}$ cycle, or 18 bifurcations. So that's extremely extremely close to the chaos point; it took a lot of brute force computation to find this point. I don't know what the equivalent of the Mandelbrot "escape to infinity" equation would be, which would be required to make a Mandelbrot plot. Otherwise all you have are the cyclical fixed points. Also, why, when you multiply all of these 262144 fixed points together, why is their product 1? –  Sheldon L Jul 18 '13 at 22:33
Hmm, I found that not only the change in the base modifies the fixpoint-cycles but even the change of the initial values keeping the same base modifies them. So probably every cycle length occurs with every base in that range $0 \lt \log(b) \lt \frac12$ . I've added a new answer showing a table where I kept the base constant –  Gottfried Helms Jul 19 '13 at 9:03
"escape to infinity" does occur, which means one can imagine drawing a "Mandelbrot" of Gottfried's function. I tried b=1.501549+0.17699i. This base is above and to the left of the 4x bifurcation bulb. I started with z=1.01, iterating $f(z)=z-\log_b(z)$ Sure enough, the iterates of f(x) do escape to negative infinity. It seems that if f(x) gets to approximately negative 1, than the iterates of f(x) get arbitrarily large and negative. –  Sheldon L Jul 19 '13 at 15:09
The Julia set for iterating f(z) starting at z seems to be well defined and well behaved. The Mandelbrot set is much trickier. My initial idea of starting at z=1.01 doesn't always work, since z=1.01 may escape, but z=1+0.01i might not. So, right now, I'm generating some Mandelbrots plots using both initial points 1.01 and 1+0.01i. It only counts as escaping if they both escape. In the worst case, you may have to try an entire circle around 1, but two points seems to work pretty well.... A single point doesn't work that well. –  Sheldon L Jul 20 '13 at 23:17

did has given the answer for $\eta$ downto $\frac 12$ in the other thread, which is surely sufficient for questions Q1 to Q3 there.

For question Q1 & Q2 here it seems heuristically, that the problem statement has a false premise: the number of accumulation-points depends on the initial-value for $x_0$ as well and not only on the parameter for the base. Moreover, using Newton-Raphson I can find arbitrary cycle-lengthes for any base $1 \lt b \lt \sqrt e$ if I also extend the range for x to the complex numbers.

If I denote $f_b(x,m)$ for the m'th iterate of $f_b(x)$ (which defines then the cycle-length for an eventually cyclic trajectory) then for any m I can find $x= f_b(x,m)$ using Newton-Raphson by $$x_{k+1} = x_k - { f_b(x_k,m)-x_k\over f_b(x_k,m)'-1 }$$, where possibly $x$ is then complex.

So using base $b=\exp(0.4)$ I find for example (with k such that the k'th iterate $x_k$ is convergent to a handful of leading decimals) $$\small \begin{array} {l|l|l|llllll} & \text{m:cycle} \\ x_0& \text{length} & x_k & \text{sequential } & \text{values} \\ \hline \\ 0.2 & 1 & 1 & 1&1&1&1&\ldots \\ 0.2 & 2 & 0.306442378456 & 0.306442& 3.26326& 0.306442& 3.26326&\ldots \\ 0.2 & 3 & 0.0462856 & 0.0462856 & 7.33793 & 2.31467 & 0.0462856 & \ldots\\ & & + 0.0280356i & + 0.0280356 i & - 1.33348 i &- 0.884073 i & + 0.0280356 i & \ldots\\ 0.2 & 4 & 0.227918 &0.227918 & 3.92484& 0.506526& 2.20697& \\ & & &0.227918 & 3.92484& 0.506526& 2.20697& \ldots \\ & \vdots & \vdots & \end{array}$$

and so on. This puts the whole subject with which I've dealt in question Q2 far away from that things with which I'm concerned in the initial problem and becomes thus uninteresting for me at the moment. I'll simply take it as given, that for bases $b \lt \sqrt e$ a meaningful evaluation for the infinite product as described in my previous question is not existent.

-

This is not an answer, only additional data for clarification. I kept the base constant (here I used: $b = \exp(0.3)$) and was able to find cycles of lengthes 2 to 16 with the help of Newton-Raphson. The resp. start-values simply follow one from the other, I started initially with $x_0=0.3$ for cycle-length 2 and used then for the cycle-length 3 the first found cyclic fixpoint as new start-value and so on. The list of the first 16 "first-cyclic-fixpoints"/"start-values" to 30 dec places is at the end.

Cycle-lengthes 2-6:

$\qquad \qquad \small \begin{array} {} 1 & 2 & 3 & 4 & 5 & 6 & \leftarrow \text{cyclelengthes } m\\ \hline . & 0.159041 & 0.0724444 & 0.107726 & 0.0921493 & 0.0987509 & \downarrow \text{trajectories}\\ . & 6.28768 & 8.82223 & 7.53494 & 8.03997 & 7.81593 \\ . & . & 1.56465 & 0.803103 & 1.09188 & 0.962052 \\ . & . & . & 1.53401 & 0.798869 & 1.09101 \\ . & . & . & . & 1.54740 & 0.800668 \\ . & . & . & . & . & 1.54170 \\ . & . & . & . & . & . \\ . & 0.159041 & 0.0724444 & 0.107726 & 0.0921493 & 0.0987509 \\ . & 6.28768 & 8.82223 & 7.53494 & 8.03997 & 7.81593 \\ . & . & 1.56465 & 0.803103 & 1.09188 & 0.962052 \\ . & . & . & 1.53401 & 0.798869 & 1.09101 \\ . & . & . & . & 1.54740 & 0.800668 \\ . & . & . & . & . & 1.54170 \\ . & . & . & . & . & . \end{array}$

Cycle-lengthes 7-12:

$\qquad \qquad \small \begin{array} {} 7 & 8 & 9 & 10 & 11 & 12 & \leftarrow \text{cyclelengthes } m\\ \hline 0.0959073 & 0.0971234 & 0.0966017 & 0.0968252 & 0.0967294 & 0.0967705 \\ 7.91049 & 7.86970 & 7.88713 & 7.87965 & 7.88286 & 7.88148 \\ 1.01652 & 0.992967 & 1.00302 & 0.998706 & 1.00055 & 0.999762 \\ 0.961899 & 1.01649 & 0.992962 & 1.00302 & 0.998706 & 1.00055 \\ 1.09138 & 0.961965 & 1.01651 & 0.992964 & 1.00302 & 0.998706 \\ 0.799894 & 1.09122 & 0.961937 & 1.01650 & 0.992963 & 1.00302 \\ 1.54415 & 0.800225 & 1.09129 & 0.961949 & 1.01650 & 0.992963 \\ . & 1.54310 & 0.800083 & 1.09126 & 0.961943 & 1.01650 \\ . & . & 1.54355 & 0.800144 & 1.09128 & 0.961946 \\ . & . & . & 1.54336 & 0.800118 & 1.09127 \\ . & . & . & . & 1.54344 & 0.800129 \\ . & . & . & . & . & 1.54340 \\ . & . & . & . & . & . \\ 0.0959073 & 0.0971234 & 0.0966017 & 0.0968252 & 0.0967294 & 0.0967705 \\ 7.91049 & 7.86970 & 7.88713 & 7.87965 & 7.88286 & 7.88148 \\ 1.01652 & 0.992967 & 1.00302 & 0.998706 & 1.00055 & 0.999762 \\ 0.961899 & 1.01649 & 0.992962 & 1.00302 & 0.998706 & 1.00055 \\ 1.09138 & 0.961965 & 1.01651 & 0.992964 & 1.00302 & 0.998706 \\ 0.799894 & 1.09122 & 0.961937 & 1.01650 & 0.992963 & 1.00302 \\ 1.54415 & 0.800225 & 1.09129 & 0.961949 & 1.01650 & 0.992963 \\ . & 1.54310 & 0.800083 & 1.09126 & 0.961943 & 1.01650 \\ . & . & 1.54355 & 0.800144 & 1.09128 & 0.961946 \\ . & . & . & 1.54336 & 0.800118 & 1.09127 \\ . & . & . & . & 1.54344 & 0.800129 \\ . & . & . & . & . & 1.54340 \\ . & . & . & . & . & . \end{array}$

Cycle-lengthes 13-16:

$\qquad \qquad \small \begin{array} {} 13 & 14 & 15 & 16 & \leftarrow \text{cyclelengthes } m\\ \hline 0.0967529 & 0.0967604 & 0.0967572 & 0.0967586 \\ 7.88207 & 7.88182 & 7.88193 & 7.88188 \\ 1.00010 & 0.999956 & 1.00002 & 0.999992 \\ 0.999762 & 1.00010 & 0.999956 & 1.00002 \\ 1.00055 & 0.999762 & 1.00010 & 0.999956 \\ 0.998706 & 1.00055 & 0.999762 & 1.00010 \\ 1.00302 & 0.998706 & 1.00055 & 0.999762 \\ 0.992963 & 1.00302 & 0.998706 & 1.00055 \\ 1.01650 & 0.992963 & 1.00302 & 0.998706 \\ 0.961945 & 1.01650 & 0.992963 & 1.00302 \\ 1.09127 & 0.961945 & 1.01650 & 0.992963 \\ 0.800124 & 1.09127 & 0.961945 & 1.01650 \\ 1.54342 & 0.800126 & 1.09127 & 0.961945 \\ . & 1.54341 & 0.800125 & 1.09127 \\ . & . & 1.54341 & 0.800126 \\ . & . & . & 1.54341 \\ 0.0967529 & 0.0967604 & 0.0967572 & 0.0967586 \\ 7.88207 & 7.88182 & 7.88193 & 7.88188 \\ 1.00010 & 0.999956 & 1.00002 & 0.999992 \\ 0.999762 & 1.00010 & 0.999956 & 1.00002 \\ 1.00055 & 0.999762 & 1.00010 & 0.999956 \\ 0.998706 & 1.00055 & 0.999762 & 1.00010 \\ 1.00302 & 0.998706 & 1.00055 & 0.999762 \\ 0.992963 & 1.00302 & 0.998706 & 1.00055 \\ 1.01650 & 0.992963 & 1.00302 & 0.998706 \\ 0.961945 & 1.01650 & 0.992963 & 1.00302 \\ 1.09127 & 0.961945 & 1.01650 & 0.992963 \\ 0.800124 & 1.09127 & 0.961945 & 1.01650 \\ 1.54342 & 0.800126 & 1.09127 & 0.961945 \\ . & 1.54341 & 0.800125 & 1.09127 \\ . & . & 1.54341 & 0.800126 \\ . & . & . & 1.54341 \end{array}$

The cyclic fixpoints for each cycle-length m to 30 dec digits are also the starting points for the Newton-Raphson-procedure of the next cycle-length $m+1$ . Interestingly this scheme produces alternating bounds for narrowing intervals, giving this reordered table:

$\qquad \qquad \small \begin{array} {r|l} m & \text{first cyclic fixpoint } = x_0 \text{ for next cyclelength} \\ \hline \\ 2 & 0.159041084882895574495955752175 \\ 4 & 0.107726043781343669667867086903 \\ 6 & 0.0987509046403918254103678692724 \\ 8 & 0.0971233874469226325765131094510 \\ 10 & 0.0968252004874207495824556555046 \\ 12 & 0.0967704568098497621845207951468 \\ 14 & 0.0967604027054928413243617832173 \\ 16 & 0.0967585560621788196164841502410 \\ \vdots & \vdots \\ 15 & 0.0967571710855825604696049846966 \\ 13 & 0.0967528623017882811913815895871 \\ 11 & 0.0967294042250856722089645206781 \\ 9 & 0.0966017134595652725208751239797 \\ 7 & 0.0959072648993569832837545208329 \\ 5 & 0.0921492817018520819559288645547 \\ 3 & 0.0724443866103568737821362424132 \\ \end{array}$

The set of cyclic fixpoints for consecutive cycle-lengthes as found here shows a nice regularity if reordered appropriately. I've sorted them in an excel-spreadsheet, such that the cyclelengthes are indicating the columns and are ordered, that the narrowing intervals become visible. In the greyed middle column I think we'll get in the limit the "chaos" points where cyclicitiness is lost (infinite cycle length). And also I ordered the rows to focus the systematic appearance. Everything could possibly even better displayed in terms of differences to the fixpoint 1. Here is the bitmap

-
Are these attracting or repelling cycles? A repelling cycle would be a cycle, that if perturbed slightly, goes away upon iterating f(x). An attracting cycle is more interesting, in that it is stable. A small perturbation maintains the attracting cycle. Attracting cycles have to have a |slope|<1, parabolic cycles have |slope|=1, and repelling cycles have |slope|>1. I suspect each real base has only one attracting cycle. –  Sheldon L Jul 19 '13 at 10:30
@Sheldon: I've not yet done a true analysis; however I know, that Newton-Raphson can approximate to fixpoints even if they're repelling. I've also tried small perbutations and then iterated, and it looks much as if the errors increase, so I assume, they're in fact repelling. Unfortunately, the inverse-function, built from Lambert's W, seems to be not much helpful, at least not in my iterative Pari/GP-implementation from wikipedia: iterations went quickly to the fixpoint 1 ... –  Gottfried Helms Jul 19 '13 at 10:37
Of course, one is always a fixed point for f(x). The bifurcations are just the change from an attracting fixed point orbit, to a repelling fixed point orbit. In the sense that your original function multiplicative product iterated f(x), it seems that attracting fixed point orbits are more relevant. –  Sheldon L Jul 19 '13 at 11:58