Tetration FAQ Discussion

[Gottfried]

Code:

-- What is a fixpoint?

We use the iteration-paradigm:
a is a fixpoint if (<op>,b,a)°h = a  for all h

Examples:

  --- iterated addition ----------------------------------------------------
  (+,b,a)°h = a      no fixpoints a, except for base b=0

       a + 0 + 0 + ... + 0 = a

  polynomial expression:
    f_b(x)   = b + x
    f_b°h(a) = b*h + a   ==> if b=0 then any a is a fixpoint
      [for extension to the ring of powerseries see matrix-approach]
  
  
  
--- iterated multiplication ----------------------------------------------------
(*,b,a)°h = a      a = 0          for all bases b
                    a = arbitrary  for base b=1
                    
       0 * b * b * ... * b = 0
       a * 1 * 1 * ... * 1 = a

  polynomial expression:
    f_b(x)   = 0 + b*x
    f_b°h(a) = a*b^h    ==> if b=1      then  any a is a fixpoint
                        ==> for other b then  a=0   is a fixpoint
      [for extension to the ring of powerseries see matrix-approach]


--- iterated exponentiation ----------------------------------------------------
(^,b,a)°h = a      b = a^(1/a)    for all a<>0
                                   multiple a for the same b
                                  
       b^a = (a^(1/a))^a = a^1 = a
      
  Series expression:
    f_b(x)  = 1 + log(b)*x + log(b)^2*x^2/2! + ...
    f_b°h(a)     ==> if log(b) = log(a)/a   then  a is a fixpoint

    using b=a^(1/a) :
    f_b(a) = 1 + log(a)*(a/a) + log(a)^2*(a/a)^2/2! + ...
               = exp(log(a))
               = a
      [see also: matrix-approach]

       [see also: <literature>]

--- iterated decremented exponentiation ----------------------------------------
  (dxp,b,a)°h = a   a = 0   for all bases b
                    a = <multiple values>   for all bases b
                    
       b^0 - 1 = 0
      
       [see also: <literature>]
      
--------------------------------------------------------------------------------

The aspect of fixpoints is an important tool for adapting
powerseries with constant term to enable fractional iterations.
[see fixpoint-shift]

===================================================================================

-- What is a "repelling"/"attracting" fixpoint?

   For an iterable function f(x) the fixpoint is given (if it exists)
   by
      f°h(a) = a
   for any h.
   If a is unknown, then we may try to *find* it simply by iteration,
   beginning with a suitable init-value a0:
              a0
     f(a0)  = a1
     f(a1)  = a2 = f°2(a0)
     f(a2)  = a3 = f°3(a0)
        ...
   If this converges to a fixed value a, then we have
     f(a)   = a  = f°inf(a0)

   and a is an attracting fixpoint.

   For instance, Euler showed, that - using b=sqrt(2) and f(x) = b^x - the sequence
    b^1, b^b^1,... or
    f°1(1),f°2(1),f°3(1),...
    converges to 2 so that
     f(2) = 2
   Since the fixpoint could be find by iteration with a different initial
   value, a=2 is an attracting fixpoint of f(x)
  
  
   But he also discussed, that another fixpoint is a=4, such that f(4) = 4.
   However, this fixpoint cannot be found by iteration from another
   initial value; if the difference delta from delta = 4 - a0 greater than
   zero, the iteration leads to increasing delta - the iteration either
   converges to a=2 (the attractin fixpoint) or diverges.
  
   So in this case, a=4 is called a "repelling" fixpoint.

   In general,
    if |f'(a)| < 1  then a is an attracting fixpoint
    if |f'(a)| > 1  then a is a  repelling fixpoint

===================================================================================