Buena cota superior (asintótica) para la recurrencia sobre divisores

Question

Estoy buscando un buen límite superior (asintótico) para la siguiente relación de recurrencia ( $T(0) = 1)$ :

$$ T(n) = \left[ \sum_{1\leq d<n, d|n} T(d) \right] + 1 $$

Nótese que la recursión es sólo para los divisores $d < n$ para asegurar la terminación*.

Lo que tengo hasta ahora: Se puede encontrar un límite superior por el hecho de que $\sigma_0(n) \leq \sqrt{n}$ y $d \leq n/2$ :

$$ T(n) \leq \sqrt{n} T(n/2) + 1 \\ $$ Es fácil ver que $T(n) = O(n^{\log_2(n)/2})$ (y esto se puede mejorar aún más por el hecho de que $\sigma_0(n) \leq n^{1.5379 \log2/\log\log n }$ ).

Cuando la computación de plano $T(n)$ para todos $n$ hasta $10^6$ Me he dado cuenta de que $T(n) \leq n^2 + 1$ .

Sin embargo, no veo cómo se puede derivar este límite (o cómo se puede demostrar que $T(n) = \omega(n^c)$ para alguna constante $c$ ). Obviamente, hay que hacer algo mejor que estimar $T(d) \leq T(n/2)$ para todos los divisores de $n$ ya que aquí es donde el $\log n$ en el exponente viene.

*Pregunta de bonificación: Estoy utilizando la terminología de la informática aquí. ¿Cuál es la forma correcta (matemática)? ¿Es la recursión anterior una finita y sería una recursión con $T(n)$ en el lado derecho sea un infinito?

Answer 1

He aquí algunas observaciones que podrían dar pie a conjeturas y a una investigación más profunda por parte de un experto, algo más de lo que cabría en un comentario.

Supongamos que tenemos $T(1) = 1$ y $$T(n) = 1 + \sum_{d|n,\; d<n} T(d).$$

Entonces podemos hacer una afirmación sobre el orden medio de $T(n)$ utilizando el Teorema de Wiener-Ikehara . Para ello necesitamos la forma cerrada de $$L(s) = \sum_{n\ge 1} \frac{T(n)}{n^s}.$$ La recurrencia da como resultado $$2 T(n) = 1 + \sum_{d|n} T(d)$$ lo que implica $$2 L(s) = \zeta(s) + L(s)\zeta(s)$$ o $$ L(s) = \frac{\zeta(s)}{2-\zeta(s)}.$$

Los experimentos numéricos (que requieren confirmación/refutación) parecen indicar que el polo dominante de $L(s)$ está en $$\rho = 1.72864723899818361813510301029769,$$ que es simple y que el residuo tiene el valor $$c = \mathrm{Res}\left(L(s); s=\rho\right) = 2\times 0.5500100054.$$

El teorema de Wiener-Ikehara dice entonces que $$\sum_{n\le x} T(n) \sim c \frac{x^\rho}{\rho} \quad\text{i.e. that the average order is}\quad \frac{1}{x} \sum_{n\le x} T(n) \sim c \frac{x^{\rho-1}}{\rho}.$$

La precisión de esta fórmula es excepcional. Por ejemplo, cuando $x=1000$ el valor exacto es $97.227$ mientras que la fórmula da $97.641,$ de manera similar para $x=6000$ el valor exacto es $359.9451$ mientras que la fórmula da $360.2746.$

Por cierto, esta secuencia es OEIS A067824 .