f(f(x))=exp(x)-1 y otras funciones "justo en el medio" entre la lineal y la exponencial

Question

La pregunta es sobre la función f(x) de modo que f(f(x))=exp (x)-1.

La pregunta es abierta y se debatió hace poco en el hilo de comentarios del blog de Aaronson aquí http://scottaaronson.com/blog/?p=263

La tasa de crecimiento de la función f (a medida que x va al infinito) es mayor que la lineal (lineal significa O(x)), polinómica (significa exp (O(log x))), cuasi-polinómica (significa exp(exp O(log x)) cuasi-polinómica, etc. Por otra parte, la función f es subexponencial (incluso en el sentido de CS f(x)=exp (o(x))), subsubexponencial (f(x)=exp (o(log x)) subsubexponencial y así sucesivamente.

¿Qué se puede decir de f(x) y de otras funciones con ese comportamiento de crecimiento intermedio? ¿Puede representarse este comportamiento de crecimiento intermedio mediante funciones analíticas? ¿Es esta función f(x) u otras funciones con tal crecimiento intermedio relevantes para alguna matemática interesante? (Parece que bastantes matemáticos y otros científicos interesantes han pensado en esta función/crecimiento intermedio).

Preguntas relacionadas con el MO:

• resolver $f(f(x))=g(x)$
• Cómo resolver $f(f(x)) = \cos(x)$ ?
• ¿Tiene la función exponencial una raíz cuadrada?
• Funciones de forma cerrada con crecimiento semiexponencial
• $f\circ f=g$ revisitado
• La no convergencia de f(f(x))=exp(x)-1 y los árboles enraizados etiquetados
• La ecuación funcional $f(f(x))=x+f(x)^2$
• Funciones racionales con un iterado común
• Suavidad en el método de Ecalle para iterados fraccionarios .

Answer 1

Considere $g(x)=e^x-1$ . Entonces $g^n(x)= x+\frac{1}{2!}n x^2+\frac{1}{3!} \left(\frac{3 n^2}{2}-\frac{n}{2}\right) x^3+\frac{1}{4!} \left(3 n^3-\frac{5 n^2}{2}+\frac{n}{2}\right) x^4 $ $+\frac{1}{5!} \left(\frac{15 n^4}{2}-\frac{65 n^3}{6}+5 n^2-\frac{2 n}{3}\right) x^5 $

$ +\frac{1}{6!} \left(\frac{45 n^5}{2}-\frac{385 n^4}{8}+\frac{445 n^3}{12}-\frac{91 n^2}{8}+\frac{11 n}{12}\right) x^6 $

$ +\frac{1}{7!}\left(\frac{315 n^6}{4}-\frac{1827 n^5}{8}+\frac{6125 n^4}{24}-\frac{1043 n^3}{8}+\frac{637 n^2}{24}-\frac{3 n}{4}\right) x^7 + \cdots$

Tenga en cuenta que $g^0(x)=x, g^1(x)=e^x-1$ y que

$g^\frac{1}{2}(x)=x+\frac{x ^2}{4}+ \frac{x^3}{48} +\frac{x^5}{3840}-\frac{7 x^6}{92160} +\frac{x^7}{645120}$ que es consistente con lo que obtuvo Greg Kuperburg. Un programa matemático simbólico también confirmará que $g^m(g^n(x))=g^{m+n}(x) +O(x^8)$

Ver La ecuación de Euler-Arnold para más información.

Answer 2

Se puede encontrar el medio iterado de una función a partir de iterados enteros conocidos utilizando, por ejemplo, las series de Newton:

$$f^{[1/2]}(x)=\sum_{m=0}^{\infty} \binom {1/2}m \sum_{k=0}^m\binom mk(-1)^{m-k}f^{[k]}(x)$$

Esto no converge para $f(x)=a^x$ donde $a>e^{1/e}$ pero como tu función es algo diferente puedes probar este método.

Actualización. Aquí hay un gráfico para $x<0$ :

     (fuente)

Para los positivos $x$ parece que la fórmula no converge en su mayoría.

Answer 3

Me gustaría responder al post de Anixx del 3 de noviembre de 2010, pero no veo cómo podría adjuntarlo correctamente a su comentario, lo siento. Para la comparación de la fórmula de Newton para el medio iterado y la fórmula en la versión de D.Geisler (que se puede obtener utilizando matriz-logaritmo en la matriz de Bell para exp(x)-1) y para más general b^x-1 por diagonalización escribí un artículo en mi página web, ver

http://go.helms-net.de/math/tetdocs/BinomialDiagonalization.htm

Muestra que el método Newton necesita más términos que el método de diagonalización y reduce el intervalo. Parece heurísticamente, que la fórmula de Newton converge a la del método de diagonalización y que el método de diagonalización está "inmediatamente" en el centro de ese intervalo de estrechamiento (dando una aproximación precisa muy pronto)

---

En los comentarios anteriores se mencionó, que I.Baker demostró el radio cero de convergencia de las potencias formales para los iterados fraccionarios de exp(x)-1 . En 2008 he hecho un pequeño estudio de esa propiedad de las potencias formales implicadas y he analizado la tasa de crecimiento de los coeficientes. Una explicación está en

http://go.helms-net.de/math/tetdocs/CoefficientsForUTetration.htm

(Acabo de actualizar la versión anterior)

Hay más ejemplos numéricos en

http://go.helms-net.de/math/tetdocs/htmltable_utetrationFractionalIteration.htm

Me gustaría mencionar, que existe el concepto de suma de series divergentes, asignando valores significativos para tales expresiones, por ejemplo también para la "serie de Euler" 1!x - 2!x^2 + 3!x^3 - 4!x^4 + ... - ... que también tiene radio de convergencia cero. El uso de un método de suma basado en las medias de Noerlund parece permitir aproximar los valores de las iteraciones fraccionarias de exp(x)-1 que son consistentes con la suposición de aditividad de las alturas de iteración

---

[actualización 24.2.2016]
Tengo una propuesta para la tasa de crecimiento de los coeficientes en la serie de potencias para el medio iterado $d°^{0.5}(x) $ donde $d(x) = \exp(x)-1$ .
Mirando la primera 1024 coeficientes $d_{k=0..1023} $ de esta media iteración parece una estimación sensata $$a_{k=3..1023} = {2\over2^k}{ (k-3)! 3!\over (2 \pi)^k }$$ y $ c_k = { d_k \over a_k} $ parece estar limitada por la inspección de esa primera 1024 coeficientes (véase la línea horizontal roja).
Además, las cuatro secuencias parciales $ \{c_{4j}\} \; ,\; \{c_{4j+1} \} \; ,\; \{c_{4j+2} \} \; ,\; \{c_{4j+3}\} $ parecen tener una forma sinusoidal con una frecuencia que depende aproximadamente de $ \log_2(k)$ .
Aquí hay una imagen para que cuatro secuencias parciales de la $ \{ c_k \} $ : (en la imagen he utilizado $1/a_k$ en lugar de $a_k$ para la leyenda, lo siento, lo actualizaré cuando tenga tiempo)

Los pares de secuencias ( $(c_0,c_2)$ y $(c_1,c_3)$ ) parecen ser complementarios en signo pero complementarios en amplitud. Aquí está la imagen, cuando la segunda secuencia de un par tiene el signo invertido:

---

Quizás sea interesante el "logaritmo iterativo" $\lambda(x)$ (o "logaritmo de iteración", como lo denominó G. Szekeres debido a P. L. Walker (véase más adelante $[1]$ ) que también resulta del logaritmo matricial de la matriz de Carleman para $d(x)$ ) tiene una estructura muy similar de secuencias divergentes de coeficientes. Aquí está la fórmula análoga $ c_k ={ \lambda_k\over a_k}$ utilizados y las cuatro secuencias parciales graficadas:

$[1]$ en Peter L. Walker , El exponencial de iteración de $e^x-1$ , Proc. Amer. Math. Soc. 110 (1990), no. 3, 611--620.)

---

[actualización 24.2.2016, 2] Aquí hay un trozo de código en Pari/GP con el que he podido encontrar los coeficientes de la serie de potencias formal para $d° \,^{0.5}(x)$ (para 1024 términos utilizados precisión interna de 1200 dígitos y necesitaba unos 2200 sec. Sólo 0.5 seg para 128 términos, 1.5 seg para 256 términos en los que utilicé sólo la precisión inferior de 200 y 400 dígitos internos, respectivamente)

\\ Pari/GP
\\ make Carlemanmatrix D for d(x)=exp(x)-1
\\ and its squareroot D05 for d°0.5 (x)
\\ Coefficients for power series in 2nd column (D[,2],D05[,2])
\\ make D, D05 as global variables to avoid huge stack-allocation

{makemat_Dsqrt(dim=n,flg=1)=local(rs,cs); 
   \\ set flg = 1 (integer) for exact rational computation; DON'T for dim>128
   \\ set flg = 1.0 (real)  for real computation with "precision" digits

   D = matid(dim);rs=cs=dim; \\ set number of rows, cols from "dim"
   for(c=2,cs,
        for(r=c,rs,
              D[r,c] = flg *  (c-1)/(r-1)*(D[r-1,c-1] + D[r-1,c])
      ));

   D05=matrix(rs,cs,r,c,if(r==c,sqrt(D[r,r])));\\ this could simply be matid(dim)
   for(d=1,rs-1,
        for(r=d+1,rs,
             c=r-d;
             D05[r,c] = (D[r,c]-sum(k=c+1,r-1,D05[r,k]*D05[k,c]))
                       /(D05[c,c]+D05[r,r])
       ););
  return(Str("results are in global matrices D and D05, size ",rs,"x",cs));}
 \\============== end of routine ==========================================

default(realprecision,200);default(format,"g0.12")
gettime();print(makemat_Dsqrt(128,1.0));print(gettime()/1000.0," secs");
 \\ output:
 results are in global matrices D and D05, size 128x128
 0.562000000000 secs

default(realprecision,400);default(format,"g0.12")
gettime();print(makemat_Dsqrt(256,1.0));print(gettime()/1000.0," secs");
 \\ output:
 results are in global matrices D and D05, size 256x256
 1.54400000000 secs

default(realprecision,1200);default(format,"g0.12")
gettime();print(makemat_Dsqrt(1024,1.0));print(gettime()/1000.0," secs");
 \\ output:
 results are in global matrices D and D05, size 1024x1024
 2322.88700000 secs

Answer 4

Y esta es otra construcción.

Dejemos que $\sigma(x)=\exp(x)-1$ De este documento http://arxiv.org/abs/0812.4047 sabemos que

$$\exp(\sigma^{[p]}(t))=\sum_{n=0}^{\infty}B_n^p\frac{t^n}{n!}$$

donde $B_n^p$ son los números de Bell de orden p-ésimo.

Así que para encontrar $\sigma^{[1/2]}(t)$ tenemos que generalizar los números de Bell al orden fraccionario. Podemos hacerlo fácilmente por inducción como sigue:

$$A_0^x=1$$ $$A_{n+1}^x=\sum_{k=0}^{x-1} A_n^x\star A_n^k$$

Y luego $$B_n^x=A_{n-1}^{x+1}$$

donde $f(n)\star g(n)$ es la convolución binomial descrita por David Knuth:

$$f(n)\star g(n)=\sum_{k=0}^n \binom nkf(n-k)g(k)$$

Para obtener el valor para cualquier real x, podemos observar que la parte derecha en $A_{n+1}^x=\sum_{k=0}^{x-1} A_n^x\star A_n^k$ es un polinomio de x y k de grado n-1 y coeficientes enteros y podemos tomar la suma indefinida del mismo simbólicamente siguiendo la regla

$$\sum_x ax^n=\frac{a B_{n+1}(x)}{n+1}$$

Où $B_a(x)$ son los polinomios de Bernoulli.

Answer 5

En el blog de Scott Aaronson, di un argumento que $e^z+z-1$ debe tener una raíz cuadrada compositiva analítica. La diferencia importante entre esta función y $e^z-1$ era que el punto fijo en $0$ tiene derivación $>1$ no $=1$ . Esto debería advertirnos de que los argumentos basados en la tasa de crecimiento cerca del infinito son inadecuados. (¡O bien debería señalar que mi argumento estaba roto!)

Vea los comentarios más abajo, puede que mi argumento se haya roto. Pero, si es así, ¡quiero averiguar por qué!

ACTUALIZACIÓN: De acuerdo, ahora estoy buscando algunos datos empíricos. Deja que $e(z)=e^z+z-1$ . Mi argumento era que debería haber una analítica e invertible $u$ (cerca de 0) tal que $u(e(z)) = 2 u(z)$ . Si tal $u$ existe, entonces $u^{-1}(2^{1/2} u(z))$ debe tener la propiedad deseada.

Lo bueno de la ecuación $u(e(z)) = 2 u(z)$ es que es lineal en los coeficientes de $u$ . Aquí están los 10 primeros coeficientes, calculados con aritmética exacta.

{1, -(1/4), 1/18, -(1/96), 17/10800, -(47/267840), 4069/354352320, -(24907/102863416320), 475411/2893033584000, -(108314387/ 1314080143488000)}

Y las versiones numéricas de lo anterior

{1., -0.25, 0.0555556, -0.0104167, 0.00157407, -0.000175478, 0.0000114829, -2.42137*10^-7, 1.6433*10^-7, -8.2426*10^-8}

Parece que están convergiendo rápidamente.

Subiendo un poco más, sucede algo impar. Computé los primeros 20 términos, de $u$ , todavía utilizando la aritmética exacta, y calculé los cocientes de los términos sucesivos. Sólo daré datos numéricos, porque las fracciones son enormes.

{-0.25, -0.222222, -0.1875, -0.151111, -0.11148, -0.065438, -0.0210867, -0.678665, -0.50159, -0.155914, 0.12897, -0.691029, -0.153086, 0.158892, -0.657229, -0.165837, 0.119535, -0.806045, -0.191576}

Así que los ratios suelen ser pequeños, pero de vez en cuando saltan a más de 0,5. Eso no es una prueba contra la convergencia, pero sugiere la necesidad de tener cuidado (¡o la posibilidad de un error!)

Por otro lado, también intenté calcular el $k$ -raíces de los términos sucesivos, y el comportamiento era mucho más suave:

{1., 0.5, 0.381571, 0.319472, 0.275046, 0.236612, 0.196922, 0.148939, 0.176275, 0.195707, 0.191704, 0.185475, 0.205223, 0.200971, 0.197848, 0.213264, 0.210132, 0.203648, 0.218941, 0.217484}

De nuevo, esto es exacto hasta el punto de tomar una $k$ -raíz de un número racional.

ACTUALIZACIÓN: Vale, he ido a intentar repetir el cálculo de Ekhad, y creo que Michael Lugo ha encontrado el error. Dejemos que $f(f(z)) = e^z+z-1$ . Acabo de hacer los primeros 5 términos, y tengo:

Coeficientes de $f$ : {Sqrt[2], 1/4 (2 - Sqrt[2]), 1/36 (-9 + 7 Sqrt[2]), 1/288 (47 - 33 Sqrt[2]), (-4350 + 3071 Sqrt[2])/43200}

Tabla de $|f_i|^{1/i}$ : {1.41421, 0.382683, 0.292347, 0.184117, 0.174302}

Tabla de $(i! |f_i|)^{1/i}$ : {1.41421, 0.541196, 0.53123, 0.407517, 0.454086}

Fíjate que mi segunda tabla, no la primera, coincide con Ekhad. Pero mi primera tabla es lo que hay que calcular.