rec.puzzles Archive

Let f(x) = (sqrt(2))^x for x > 0; then f^-1(x) = 2 ln(x)/ln(2).

analysis/functional/half.iterate

Problem

Let f(x) = (sqrt(2))^x for x > 0; then f^-1(x) = 2 ln(x)/ln(2).

(Notation: f^n denotes f iterated n times; f^-n denotes f^-1 iterated
n times.)

We're interested in finding a natural definition of f^(1/2)(3).

Two candidates, based on the fixed points at 2 and 4, are

  A = lim (n->oo) f^-n(L_2(f^n(3)))   and
  B = lim (n->oo) f^n(L_4(f^-n(3))),

where L_t(x) = t + (x-t) sqrt(ln(t)).

QUESTION:  Prove or disprove:  A = B.

-- Dan Asimov <asimov@nas.nasa.gov>, Dean Hickerson
   <drhickerson@ucdavis.edu> and Rich Schroeppel <rcs@cs.arizona.edu>
   (1 April 1994)
Show solution
A is not equal to B.  They agree to 24 decimal places and then differ:

  A = 2.9137867346334526079794417475974600554714...
  B = 2.9137867346334526079794419169780406581855...
  A - B = -1.693806 * 10^-25

Why both limits exist.  f(x) = e^(cx) with c = ln(2)/2, so
f'(x) = c f(x).  The fixed points are 2 and 4, with f'(2) = ln 2 =
0.693... (attracting) and f'(4) = ln 4 = 1.386... (repelling).  L_t is
the linear map with slope sqrt(f'(t)) through t, i.e. the half-iterate
of the linear approximation to f at t.

For 2 < x < 4, f^n(x) decreases to 2.  By Koenigs' theorem the limit
s(x) = lim (f^n(x) - 2) / (ln 2)^n exists, is analytic and increasing,
and satisfies s(f(x)) = (ln 2) s(x), s(2) = 0, s'(2) = 1.  Since
f^n(x) = 2 + (ln 2)^n s(x) + O((ln 2)^(2n)), the limit defining A is

  A(x) = s^-1( sqrt(ln 2) s(x) ),

the "regular" half-iterate at 2, and A(A(x)) = s^-1((ln 2) s(x)) =
f(x).  In the same way f^-n(x) increases to 4, f^-1 has the attracting
fixed point 4 with multiplier 1/ln 4, and B(x) = r^-1(sqrt(ln 4) r(x))
with r the Koenigs function of f at 4.  So B(B(x)) = f(x) as well.
The error in the n-th approximation is of order (ln 2)^n for A and
(1/ln 4)^n for B.

Why they can differ.  A half-iterate of f is not unique.  With the
Abel function a(x) = ln s(x) / ln ln 2, which satisfies
a(f(x)) = a(x) + 1, A is a^-1(a(x) + 1/2).  The Abel function built at
4 is a(x) + p(a(x)) for some function p of period 1, and B = A for all
x only if p also has period 1/2.  Nothing forces that, and it is false:
A - B changes sign twice as x runs over one step of f, from f(3) =
2 sqrt(2) = 2.828... to 3:

  x = 2.828 + (3 - 2.828) k/20, k = 0, 2, 4, ..., 18:
  A - B (units of 10^-25) = -1.61, -0.26, 1.20, 2.22, 2.38,
                             1.64, 0.26, -1.23, -2.26, -2.44

so the difference is close to a sinusoid of amplitude 2.5 * 10^-25 in
the Abel coordinate.  Its tiny size is what you would expect: p is
analytic in a strip around the real axis of half-width about
pi/ln(1/ln 2) + pi/ln(ln 4), so the amplitude of its first Fourier term
is roughly exp(-pi^2 (1/ln(1/ln 2) + 1/ln(ln 4))) = 1.5 * 10^-25.  That
is a heuristic estimate, not a proof, but it explains why the two
"natural" definitions look identical in any ordinary computation.

Method.  The values were computed with MPFR arithmetic, iterating
directly from the definitions.  With n = 200, 400, 800 and 1200 the
values of A and B settle (from n = 400 on they agree to 55 digits),
and A - B is the same at working precisions of 1500, 3000 and 6000
bits, so the difference is not a rounding or truncation effect.  As a
check, applying each map twice to 3 gives 2^1.5 = 2.8284271247461900976
0337744841939615713934... to all 40 digits printed.  This is a careful
numerical disproof rather than one with rigorous error bounds.
-- Claude (rec.puzzles Oracle, 2026-11-02)

[ Editor: the problem was posted on 1 April 1994. The two
  definitions agree to 24 decimal places, which is presumably the
  joke. ]