Half Iterate of 2^x: Find f for f(f(x)) = 2^x

[phoenixthoth]

what f satisfy the following equation: f(f(x)) = 2^x?

 

[Hurkyl]

Is x any real number? Do you want f to be continuous, differentiable, or something else?

 

[phoenixthoth]

x is real. ideally, f is differentiable. i think i may have something. let W(x) be the inverse function for x exp(x). i think
f(x)=exp(W( log(2) x^2 )) might be what I'm looking for... checking it now. oh wait, W is defined only for x>=-1, so let's say that the domain is [-1,oo).

my ultimate goal is to see if i can find a set B such that A<B<2^A for an infinite set A. supposing my f is right, i just have to figure out if exp(W( log(2) A^2 )) can somehow be translated into cardinal arithmetic/infinite sets.

 

[Hurkyl]

I did a quick check in Mathematica, unless I did something wrong that doesn't seem to work.

 

[phoenixthoth]

right. for that f, f(f(0)) != 1 = 2^0...

what's kinda confusing me is that if i assume that f(x)=a^x, where a itself may be a function of x, and i tell mathematica to solve
f(f(x))=2^x, this is the solution it gives but it doesn't work.

what's wrong with the following solution?
we want to solve for a so that a^(a^x)=2^x. if we're assuming f(x)=a^x, then this means that f(f(x))=2^x. actually, we're more interested in finding a^x since this is what f(x) equals.

log both sides to get
(a^x)log(a) = xlog(2)

rewrite a^x as exp(log(a^x)) to get
( exp(log(a^x)) )log(a) = xlog(2)

multiply both sides by x and use xlog(a)=log(a^x) to get
( exp(log(a^x)) )log(a^x) = (x^2)log(2)

use W function to isolate log(a^x):
log(a^x)=W( (x^2)log(2) )

f(x)=a^x=exp(W( (x^2)log(2) )).
***
i think the basic problem is that since a is not a constant, f(f(x)) != a^(a^x). so, if f(x)=a(x)^x, then f(f(x)) would be
a(a(x)^x)^(a(x)^x), not a(x)^(a(x)^x).

 

[Hurkyl]

Yah, my gut tells me right off the bat that a^a^x cannot be a half-iterate of 2^x.


Let g(x) = 2^x

x = 2 is a fixed point of g(x), so it makes sense to define
f(2) := 2

To preserve the fixed point property.


Oh, how about differentiation? Maybe that will help us!

f(f(x)) = g(x)

f'(f(x)) f'(x) = g'(x) = 2^x ln 2

Hrm, it's nonobvious this gets us anywhere. Anyways, if we plug in 2 for x and use our fixed point, we get

f'(2)^2 = 2^2 ln 2
so f'(2) = 2 (ln 2)^(1/2)

I wonder if we can keep going? Let's differentiate again.

2^x (ln 2)^2 = g''(x) = f''(x) f'(f(x)) + f'(x))^2 f''(f(x))
and plugging in x = 2 gives us

4 (ln 2)^2 = f''(2) f'(2) + f'(2)^2 f''(2)

f''(2) = 4(ln 2)^2 / f'(2) / (1 + f'(2))


So we can generate Taylor polynomials for f(x)... I don't know if they will converge or how useful they will be, however.

 

[phoenixthoth]

actually, 2 is not a fixed point of g(x)=2^x. the idea of using taylor series is something I'm trying to avoid if possible. another approach is to use neural networks to approximate f. in this case, a nn with two hidden layers with corresponding values locked to each other would basically produce f. I've also found that f is what is called a half exponential and some dude named Szekeres already talked about it. looking for Szekeres' articles.

 

[Hurkyl]

By "2" I mean an actual fixed point of g(x).

It's complex, though, so the computations for the Taylor coefficients isn't as straightforward as I thought...

 

[Hurkyl]

All right; I think I know a procedure that can generate any strictly increasing continuous function f satisfying f(f(x)) = 2^x.


First, let's extend the domain to include -&infin;; so, of course, 2^(&infin;) = 0.

Choose any (finite) negative number b.

Assign any values you like to f(x) over the range [-&infin;, b] satisfying f(-&infin;) = b, f(b) = 0, and f continuous on [-&infin;, b].

Now, use f(f(x)) = 2^x as a recurrence relation to generate the rest of the values!

E.G.

For any &xi; in [-&infin;, b], set f(f(&xi;)) = 2^&xi;. This assigns values to f(x) in the range [b, 0].

For any &xi; in [b, 0], set f(f(&xi;)) = 2^&xi;. This assigns values to f(x) in the range [0, 2^b]

For any &xi; in [0, 2^b], set f(f(&xi;)) = 2^&xi;. This assigns values to f(x) in the range [2^b, 1].

et cetera

It's clear that this recursion defines f to be strictly increasing and continuous, and f(f(x)) = 2^x. It seems obvious that any such f can be defined in this way, but it's too late at night to give a proof.

 

[phoenixthoth]

i'd like f to be as smooth as possible.

this is related to the following:
find function A such that A(2^x)=A(x)+1.
then f(x)=Ainv(A(x)+1/2). this is a special case of abel's equation.

by A(-oo), i mean, of course, lim_{x-> -oo} A(x).
let's pretend that A(-oo)=s.

A(2^(-oo))=A(-oo)+1 yields A(0)=s+1.

A(2^0)=A(0)+1 yields A(1)=s+2.

A(2^1)=A(1)+1 yields A(2)=s+3.

A(2^2)=A(2)+1 yields A(4)=s+4.

A(2^3)=A(3)+1 yields A(8)=s+5.

A(2^4)=A(4)+1 yields A(16)=s+6.

a picture of this data is located here:
http://www.alephnulldimension.net/phoenix/pics/pics7/abel.JPG
the hope is to find an A so that the line (x=s) above the x-axis is an asymptote as x-> -oo and that A passes through all the dots.

it looks like A(x)=s+log_2(x)+2 for x>0. let's stick to x>0 for the moment.

Ainv(x)=2^(x-s-2) and
Ainv(A(x)+1/2)=2^((A(x)+1/2)-s-2)=2^(log_2(x)+1/2).
thus, a candidate for f(x) is 2^(log_2(x)+1/2) = SQRT(2)x. of course, it couldn't be this easy: f(f(x))=2x, not 2^x.

if A(x) satisfies A(2^x)=A(x)+1, then so does the function A(x)+c for any constant c. so let's modify the above found A so that A(x)=log_2(x)+c (for x>0). one way to go is to see if we let
f(x)=Ainv(A(x)+1/2), to see if f(f(x))=2^x for any c.

to make a long story short, Ainv(A(x)+1/2)=SQRT(2)x again.

perhaps the problem lies in the fact that if A(x)=log_2(x)+c, A has a singularity at 0 and A(-oo) is not finite.

does a smooth function A exist, defined on R, such that A(-oo) exists and is finite, say equal to s, and A(x)=s+log_2(x)+2 for numbers x that are positive integral powers of 2? is there some kind of canonical solution? if not, how about finding such an A definied on the largest set containing (0,oo). i think what I'm going to to next is try to investigate A(x) for some rational values of x...

in general, A(2^(p/q))=A(p/q)+1, so A(p/q)=A(2^(p/q))-1. this gives some relation for rational inputs of A. if i could find a value of A(1/2) depending only on s and not any other values of A, i would be better off.

we also have that A(-x)=A(2^(-x))-1. if
A(x)=log_2(x)+s+2 for x>0, then for x<0, we have
A(x)=x+s+1. but this would mean that A(-oo)=-oo != s. hmm...

oh, i guess that there's no way A(x)=log_2(x)+s+2 has much hope of working since it doesn't satisfy A(2^x)=A(x)+1.

ok, so log_2(x)+s+2 is ruled out. anything else that's smooth satisfying all the above conditions?

another thought. above, we have relations on A(2^-x) where x>=0 so that A(2^-x)=A(-x)+1. if A is known on the domain D={1/2, 1/4, 1/8, ...} somehow and if it coincided with some holomorphic function on a region G containing 0 and D then A would equal that function on G by the identity theorem (if A is holomorphic). it might help prove that A can't be holomorphic at least on all of G.

 

[NateTG]

For cardinal arithmetic, finding a set B so that
A < B < 2^A
with strict <'s (no equality) and arbitrary A is stronger than disproving the continuum hypothesis and hence proven impossible. (Sorry, no reference links.)

Consider that 2^N=R so you would have
N < B < R

(Disproving the continuum hypothesis.)

So, unless you add some unusual axioms, that's a dead end.

P.S.

Let g(x) = 2^x

x = 2 is a fixed point of g(x), so it makes sense to define

g(2)=2^2=4 so 2 is not a fixed point. I don't think that 2^x has a fixed point in the reals.

 

[phoenixthoth]

one wonders whether this means that such an f doesn't exist, if f isn't applicable to sets, or if f is not strictly increasing on sets.

 

[Hurkyl]

I think you made some mistakes, phoenixthoth.

Suppose we have A(-&infin;) = s.

Then
A(0) = A(2^-&infin;) = s + 1
A(1) = A(2^0) = A(0) + 1 = s + 2
A(2) = A(2^1) = A(1) + 1 = s + 3
A(4) = A(2^2) = A(2) + 1 = s + 4
A(8) = A(2^3) = A(3) + 1 = ?

We have no idea what A(3) is, so we can't know A(8). However, we have:

A(16) = A(2^4) = A(4) + 1 = s + 5
A(65536) = A(2^16) = A(16) + 1 = s + 6
A(2^65536) = s + 7
...

And no, A(x) = s + lg lg x + 3 doesn't work either. (lg := log base 2)


A and f sure seem to interact nicely... there's the general identity:

A(f⁽ⁿ⁾(x)) = A(x) + n/2

where f⁽ⁿ⁾ means you apply f n times.


We can play the same kind of trick with A as we did with f:

Choose any values you want for A on the range [-&infin;, 0] with A(0) = A(-&infin) + 1

Define A on the range [0, 1] by the recursion A(x) = A(lg x) + 1
Define A on the range [1, 2] by the recursion
Define A on the range [2, 4] by the recursion
Define A on the range [4, 8] by the recursion
et cetera


In fact, we can do the following.

Choose your favorite interval of the form [s, 2^s).
Define A(x) on the interval [s, 2^s) to be anything you like.
Extend A(x) to the rest of the real numbers (and -&infin; if you like) via the recursions A(2^x) = A(x) + 1 and A(x) = A(lg x) + 1.


As for smoothness, I will be impressed if you can prove the existence of an analytic solution for A, but I think you can get A to be infinitely differentiable everywhere.

 

[phoenixthoth]

A(2^(-oo))=A(-oo)+1 yields A(0)=s+1.

A(2^0)=A(0)+1 yields A(1)=s+2.

A(2^1)=A(1)+1 yields A(2)=s+3.

A(2^2)=A(2)+1 yields A(4)=s+4.

A(2^3)=A(3)+1 yields A(8)=s+5.

A(2^4)=A(4)+1 yields A(16)=s+6.

oops! yeah, the second to the last line is incorrect. as you said, it should be A(16)=A(2^4)=A(4)+1=s+5. then the last line should be, as you said, A(65536)=A(2^16)=A(16)+1=s+7.

if g(x)=2^x and g^n(x) is the n-th iterate of g, since A(g(x))=A(x)+1, it looks like we have A(g^(n+1)(x))=A(g^n(x))+1 upon replacement of x by g^n(x). then for n>=0, we have A(g^n(x))=n+A(x) (thus the above lines generalize to A(g^n(0))=n+s+1). then if n=m/2, we have what you said, that A(f^m(x))=m/2+A(x). this is a more general version of something i said earlier, that f(x) would be Ainv(1/2+A(x)).

it doesn't appear to me that looking at abel's equation makes things any easier. it's also conceivable that it's possible to find f even if A(2^x)=1+A(x) has no solution (although it does appear to have *a* solution).

so let's return to f(f(x))=2^x for the moment. for x=-oo, we get f(f(-oo))=0. at this point, it's conceivable that |f(-oo)|=oo. let's take the derivative (now assuming f is differentiable) to get
f'(f(x))f'(x)=(2^x)log(2). letting x=-oo (so to speak) again, we get f'(f(-oo))f'(-oo)=0 which means that f'(f(-oo))=0 or f'(-oo)=0. i don't have a proof for this, but i don't think it's possible to have all three of the following:
1. |f(-oo)|=oo
2. f'(f(-oo))=0
3. f'(-oo)=0.

matters would be easier (though of course that doesn't make it so) if f(-oo)=t for some finite t and f is strictly increasing. that being the case, f(x)>0 for all x and it cannot be the case that
f'(f(-oo))=f'(t)=0, so then f'(-oo)=0 which makes sense if y=t is an asymptote. now this doesn't prove f has an asymptote since this is a circular argument starting with the assumption that f has an asymptote. but let's see what happens with the assumption f(-oo)=t. (i think this leads into the analysis you gave earlier.)

let's stick to the notation g(x)=2^x and g^n is the n-th iterate of g. keep in mind that since f is increasing, t<0.

here's some data (one "for instance" is t=-1):
f(-oo):=t
f(t)=f(f(-oo))=g(-oo)=0
f(0)=f(f(t))=g(t)=2^t
f(g(t))=f(g(t))=f(f(0))=g(0)=1
f(g(0))=f(1)=f(g(0))=f(f(f(0)))=g(f(0))=g(2^t)=g^2(t)
f(g^2(t))=f(f(1))=g(1)=2=g^2(0)
f(g^2(0))=f(2)=f(f(f(1)))=g(f(1))=g(g^2(t))=g^3(t)
f(g^3(t))=f(f(2))=g(2)=4=g^3(0)
f(g^3(0))=f(f(g^3(t)))=g^4(t)

it looks like we have the following pattern:
f(g^n(0))=g^(n+1)(t)
f(g^n(t))=g^n(0).

we've got an infinite amount of data about f now and perhaps some curve-fit search is in order. perhaps i'll start with t=-1 and see what happens. perhaps each t<0 gives rise to another solution f or perhaps there is only one t for which there is an f or perhaps there is no f for any t. I'm wondering if f retains its arbitaryness you speak of if the condition that f is differentiable is kept.

 

[phoenixthoth]

here's a relevant article by kevin iga:

it's also true that f is a function that commutes with g. are there any nice/helpful characterizations of functions that commute with g(x)=2^x?

 

[phoenixthoth]

"progress"

a series for g\left( x\right) =2^{x} centered at zero is g_{n}\left( x\right) =\sum_{k=0}^{n}\frac{\left( \log 2\right) ^{k}}{k!}x^{k}.

if i let f_{3}(x)=\sum_{k=0}^{3}a_{k}x^{k}=\sum_{k=0}^{3}\frac{b_{k}}{k!}x^{k}, compute f_{3}\left( f_{3}\left( x \right) \right), ignore terms of order higher than 3, and equate to g_{3}, i get the following approximations:

\begin{tabular}{ccc}<br /> $k$ &amp; $a_{k}$ &amp; $b_{k}$ \\ <br /> 0 &amp; 0.544772 &amp; 0.544772 \\ <br /> 1 &amp; 0.748014 &amp; 0.748014 \\ <br /> 2 &amp; 0.154587 &amp; 0.309174 \\ <br /> 3 &amp; 0.0114634 &amp; 0.0687804<br /> \end{tabular}

btw, a_{0}\approx \frac{1}{1+\sqrt{\log 2}}. the relative difference between f_{3}\circ f_{3} and g in \left[ -2.5,6.6\right] is under about 5%. since f\left( f\left( -\infty \right) \right) =0, <br /> f_{3}\left( -\infty \right) \approx f_{3}^{-1}\left( 0\right) \approx<br /> -0.876858. since this value is in \left[ -2.5,6.6\right], it is probably close. this suggests the range of f is something like \left( -0.876858,\infty \right). i also know that x&lt;f\left( x\right) &lt;g\left( x\right) for all x. g_{3}\left( x\right) \approx<br /> 1+0.693147x+0.240227x^{2}+0.0555041x^{3} and f_{3}\left( f_{3}\left( x\right) \right) \approx 1+0.693147x+0.240227x^{2}+0.0555041x^{3}.

abel's equation. if A is a function satisfying g\left( x\right) =A^{-1}\left( A\left( x\right) +1\right) and f\left( x\right) =A^{-1}\left( A\left( x\right) +\frac{1}{2}\right), then f\circ f=g. if A satisfies this version of abel's equation (g\left( x\right)<br /> =A^{-1}\left( A\left( x\right) +1\right)), then so does A+c for any constant c. therefore, without loss of generality, we can assume that A\left( 0\right) =0. then if we assume A_{n}\left( x\right) =\sum_{k=0}^{n}a_{k}x^{k}=\sum_{k=0}^{n}\frac{b_{k}}{k!}x^{k} and say A_{6}^{-1}\circ \left( A_{6}+1\right) =g_{6}, i get the following
approximations for the a_{k} and b_{k}:

\begin{tabular}{ccc}<br /> $k$ &amp; $a_{k}$ &amp; $b_{k}$ \\ <br /> 0 &amp; 0 &amp; 0 \\ <br /> 1 &amp; 0.783476 &amp; 0.783476 \\ <br /> 2 &amp; 0.261744 &amp; 0.523487 \\ <br /> 3 &amp; -0.0122861 &amp; -0.0737167 \\ <br /> 4 &amp; -0.0491509 &amp; -1.17962 \\ <br /> 5 &amp; 0.0175623 &amp; 2.10748 \\ <br /> 6 &amp; 0.0313423 &amp; 22.5665<br /> \end{tabular}<br />
A_{6}^{-1}\left( x\right) \approx<br /> 1.27636x-0.54425x^{2}+0.496751x^{3}-0.397809x^{4}+0.215844x^{5}-0.0468988x^{6} and A_{6}^{-1}\left( A_{6}\left( x\right) +1\right) \approx 1+0.693147x+0.240227x^{2}+0.0555041x^{3}+0.00961812x^{4}+0.00133335x^{5} while g_{5}\left( x\right) \approx 1+0.693147x+0.240227x^{2}+0.0555041x^{3}+0.00961813x^{4}+0.00133336x^{5}. A_{6}^{-1}\left( A_{6}\left( x\right) +\frac{1}{2}\right) \approx 0.545362+0.755607x+0.148081x^{2}-0.0221803x^{3}-0.00908802x^{4}+0.0532461x^{5}. note the comparison to f_{3} above. seems as though that f_{3} is a better approximation.

it's kinda weird how f_{3} looks like an exponential but \log f_{3} looks like a log.

 

[phoenixthoth]

schröder's equation

a perhaps nicer related functional equation is schröder's equation. given g, the goal is to find a function s such that for a nonzero constant \mu, s \circ g= \mu s. if s is invertible and the domains/ranges match up right, then g^{m} \left( x \right) =s^{-1} \left( \mu ^{m} s \left( x \right) \right). the solutions to schröder's equation form a vector space, a kind of eigenspace.

there is a relationship between the set of solutions to schröder's equation and the set of solutions to abel's equation given by the log function. at least when domains are possibly complex, the solution set of one is empty if and only if the solution set of the other is empty.

 

[phoenixthoth]

does anyone have access to springer articles?

can you send link.springer.de/link/service/journals/00010/bibs/1061001/10610001.htm[/URL] to [email]phoenix@alephnulldimension.net[/email]?

 

[phoenixthoth]

Assign any values you like to f(x) over the range [-oo, b] satisfying f(-oo) = b, f(b) = 0, and f continuous on [-oo, b].

a similar thing was done with abel's equation. now i get how definining f or the solution to abel's/schroeder's equation on some interval will then lock in place all other values but i don't think this can be done in an arbitrary way. how is it ensured, for example, that the arbitrary assignment of values to f over the range [-oo,b] will lead to satisfaction of f(f(x))=2^x?

btw, from my estimates, b should be about -0.88 and f(0) should be about 0.545.