Si $T(n) = \sum_i T(\lfloor r_i n \rfloor) $ para $n \ge 1$ entonces $T(n)/n \to 0$

Question

Dejemos que $(r_i)_{i=1}^m$ sea una secuencia de reales positivos tal que $\sum_i r_i < 1$ y que $t$ sea un real positivo. Consideremos la secuencia $T(n)$ definido por $T(0) = t$ , $T(n) = \sum_i T(\lfloor r_i n \rfloor) $ para $n \ge 1$ .

Demostrar que $T(n) = o(n)$ , es decir, $\lim_{n \to \infty} \dfrac{T(n)}{n} = 0 $ .

Nota: Esta es una variación de Si $T(n) = un + \sum_i T(\lfloor r_i n \rfloor) $ , demuestran que $T(n) = \Theta(n)$ . Se obtiene fijando $u=0$ allí.

Estoy cerca de una solución y espero tener una en unos días. Si encuentro una, lo publicaré.

Nota: Es fácil demostrar que $T(n) = O(n)$ . El problema es mostrar que $T(n)/n \to 0$ .

Answer 1

Esto es lo que he he podido encontrar.

Demostraré que $T(n)/n$ puede hacerse arbitrariamente pequeño, aunque el número de pasos parece ser exponencial en el recíproco del límite. Más concretamente, para un valor real de $0 < c < 1$ , hay constantes explícitamente computables $A$ y $B$ que dependen de la recurrencia y $B$ también depende de valores iniciales de $T(n)$ tal que $T(n)/n < c$ para $n > (1/c)^A/B$ .

Dejemos que $r = \sum_i r_i$ y $s = 1-r$ para que $0 < s < 1$ . Dejemos que $r_0 = \min_i r_i$ .

Primero demuestro que si $T(k) \le bk$ para $r_0n \le k < n$ entonces $T(n) \le bnr$ para todos los siguientes $n$ .

Supongamos que $T(k) \le bk$ para $r_0n \le k < n $ . Queremos demostrar que $T(n) \le bn $ .

$\begin{align} T(n) &=\sum_i T(\lfloor r_i n \rfloor)\\ &\le \sum_i b r_i n\\ &= n\sum_i b r_i \\ &= nb r\\ \end{align} $

Esto demuestra que el límite de $T(n)/n$ se reduce en un factor de $r$ . El siguiente paso es ver cuándo el límite se reduce en un factor de $r^2$ .

Dejemos que $n_0 = n$ . Queremos encontrar un $n_1$ tal que $r_0 n_1 = n_0$ , de modo que el intervalo de $r_0 n_1$ a $n_1-1$ puede ser la base para otra reducción del límite en un factor de $r$ .

Obviamente, esto se satisface con $n_1 = n_0/r_0$ . Del mismo modo, el establecimiento de $n_2 = n_1/r_0$ permite reducir el límite en un factor de $r^2$ .

Por inducción, si $n_k = n_{k-1}/r_0 = n_0/r_0^k$ , $T(n)/n < b r^k$ para $n > n_k$ .

Dejemos que $s = 1/r_0$ , así que $s > 1$ . reafirmando los resultados anteriores en términos de $s$ , si $n_k = n_{k-1}s = n_0 s^k$ , $T(n)/n < b r^k$ para $n > n_k$ .

Esto demuestra que el límite se reduce en un factor de $r^k$ en $n_0 s^k $ pasos.

Si el límite, a partir de $b$ , debe ser inferior a $c$ , donde $0 < c < 1$ , $b r^k < c$ o $k > \dfrac{\log (c/b)}{\log r}$ (ya que $r < 1$ ).

El número de pasos para que el límite se reduzca a $c$ es por lo tanto

$\begin{align} n_0 s^{\frac{\log (c/b)}{\log r}} &=n_0 \exp(\log s(\log (c)-\log(b))/(\log r)\\ &=n_0 \exp\left(\frac{\log s\log c}{\log r}-\frac{\log s\log b}{\log r}\right)\\ &=n_0 \exp\left(\frac{\log s\log c}{\log r}\right)/K\\ &=n_0 \exp\left(\frac{\log s\log (1/c)}{\log (1/r)}\right)/K\\ &=n_0 (1/c)^{(\log s)/(\log (1/r))}/K\\ \end{align} $

donde $K = \exp\left(\frac{\log s\log b}{\log r}\right) = b^{\log s/\log r} $ .

En estas fórmulas, $c$ es el valor del límite de $T(n)/n$ debe reducirse a (por ejemplo $c=0.01$ ), $r$ y $s$ dependen de de la recurrencia, y $b$ es el límite inicial de $T(n)/n$ .

Por lo tanto, $T(n)/n$ puede hacerse arbitrariamente pequeño, aunque el número de pasos parece ser exponencial en el recíproco del límite.

Answer 2

A continuación se presenta una prueba para un caso especial que no es demasiado complicado, pero que sí se da en situaciones reales. Supongamos que su $r_k$ son todas las potencias enteras inversas de algún número entero positivo $p$ , donde $p\ge 2,$ para que $r_k = 1/p^{q_k}$ con $q_k\ge 1$ y el $q_k$ distinto.

Su recurrencia ahora se ve así: $$ T(n) = \sum_{k=1}^m T(\lfloor n/p^{q_k} \rfloor).$$

Dejemos que $D = \max_{k} q_k$ e introducir $$S(n) = \sum_{k=1}^m S(n-q_k)$$ donde los valores iniciales son $S(n) = T(p^n)$ para $0\le n < D.$ Entonces no es difícil ver que se cumple la siguiente fórmula exacta: $$ T(n) = S(\lfloor\log_p n\rfloor).$$

Ahora $S(n)$ es lineal y homogénea con la ecuación característica $$\lambda^D = \sum_{k=1}^m \lambda^{D-q_k}.$$ Obsérvese que el módulo máximo de las raíces de esta ecuación es estrictamente inferior a dos, porque para $|\lambda|=R$ tenemos $$\left| \sum_{k=1}^m \lambda^{D-q_k} \right| \le \sum_{k=1}^m |\lambda|^{D-q_k} = \sum_{k=1}^m R^{D-q_k} \le \sum_{d=0}^{D-1} R^d = \frac{R^D-1}{R-1}.$$ Pero para $R\ge 2$ tenemos $$ \frac{R^D-1}{R-1} < R^D $$ ya que esto es sólo $$ R^D - 1 < R^{D+1} - R^D \quad\text{or}\quad 2R^D < R^{D+1} + 1,$$ produciendo una contradicción con el hecho de que $\lambda$ se supone que es una raíz (módulo de LHS $>$ RHS en la ecuación original).

Dejemos que $\rho$ sea la raíz con módulo máximo de la ecuación característica. Entonces por la teoría básica de las relaciones de recurrencia el término asintóticamente dominante de la solución de la recurrencia satisface $$S(n) \sim c n^{a-1} \rho^n$$ con $c$ una constante y $a$ la multiplicidad de la raíz. Un fácil argumento de continuidad muestra que, de hecho $\rho$ es real y $1<\rho<2.$ (La raíz $\rho$ no puede corresponder a un par de raíces complejas conjugadas, porque éstas generarían un término trigonométrico fluctuante que, siendo su módulo el mayor, acabaría produciendo un par de valores consecutivos de $S(n)$ con signos diferentes o que uno de ellos sea cero, contradiciendo el hecho de que $S(n)$ se ve fácilmente que es estrictamente creciente).

Esto da como resultado lo siguiente para $T(n):$ $$ T(n) \sim c \lfloor\log_p n\rfloor^{a-1} \rho^{\lfloor\log_p n\rfloor}.$$ Por lo tanto, $$\frac{T(n)}{n} \in \Theta\left( \lfloor\log_p n\rfloor^{a-1} \left(\frac{\rho}{p}\right)^{\lfloor\log_p n\rfloor}\right).$$ Esto demuestra la afirmación de que $T(n)/n\to 0$ porque $\rho/p$ es estrictamente menor que uno y sus potencias positivas desaparecen como $\log_p n$ va al infinito, cancelando el polinomio en $\log_p n$ a lo largo del camino. (El truco era que $\rho<2$ y $p\ge 2.$ )

Anexo I. El lector puede comprobar que $\sum_{k=1}^m \frac{1}{p^{q_k}}$ es efectivamente menor que uno. II. El argumento es válido incluso si el conjunto de raíces con módulo máximo (que es finito) incluyera números complejos, porque el límite de $|\rho|$ sigue manteniéndose.

Answer 3

Tengo una noticia muy emocionante para el Sr. M. Cohen y otros posibles lectores de este hilo. Espero que se vea a menudo porque el resultado es realmente muy bonito. Demostramos que podemos resolver un caso más general que en el primer post utilizando series de Dirichlet y transformadas de Mellin, obteniendo fórmulas exactas para $T(n)$ y para el término asintótico principal.

Supongamos que $r_k = 1/p_k$ para todos $k$ y $\sum_k 1/p_k < 1$ donde el $p_k\ge 2$ son distintos y $k\ge 2$ . Obsérvese que ahora pueden ser enteros arbitrarios en lugar de potencias de un único entero en nuestro primer post. Además, dejemos que $T(0) = 1.$

Ahora bien, evidentemente lo que nos encontramos aquí es un árbol en el que los nodos se ramifican por cada $p_k$ siempre y cuando $n$ no es cero y queremos un recuento de las hojas. La siguiente observación es la clave: la serie finita de Dirichlet en $s$ dado por $$D_l(s) = \left(\sum_k \frac{1}{p_k^s}\right)^l = \sum_q \frac{a_{l,q}}{q^s}$$ codifica perfectamente mediante una biyección todos los caminos de longitud $l$ (es decir, $l$ aristas) de la raíz a una hoja y el multiplicador de $n$ correspondiente a cada camino. Si $q> \lfloor n/p_k \rfloor$ y $q\le n$ y luego añadir un paso a lo largo de $p_k$ produce $a_{l,q}$ valores cero, es decir, hojas.

De ahí que tengamos la siguiente fórmula exacta (exacta para todo $n$ ): $$T(n) = \sum_k \sum_{l=0}^{\lfloor \log_2 n \rfloor} \sum_{\lfloor n/p_k \rfloor < q \le n} a_{l, q}.$$

Ahora observemos que podemos sustituirlo con seguridad por $$T(n) = \sum_k \sum_{l=0}^\infty \sum_{\lfloor n/p_k \rfloor < q \le n} a_{l, q}$$ porque $a_{l,q}$ nunca contribuye cuando $q>n$ y el menor denominador que aparece en el correspondiente $D_l(s)$ es $(\min_k p_k)^{\lfloor \log_2 p_k \rfloor + 1} > n.$

Presentación de la serie de Dirichlet $$D(s) = \sum_{l\ge 0} D_l(s) = \sum_{l\ge 0} \left(\sum_k \frac{1}{p_k^s}\right)^l = \frac{1}{1 - \sum_k \frac{1}{p_k^s}} = \sum_q \frac{a_q}{q^s}$$ obtenemos así $$T(n) = \sum_k\sum_{\lfloor n/p_k \rfloor < q \le n} a_q.$$

Ahora pon $$M(n) = \sum_{q=1}^n a_q$$ para que $$T(n) = \sum_k (M(n) - M(\lfloor n/p_k \rfloor).$$ Evaluaremos $M(n)$ mediante el teorema de Wiener-Ikehara, que es una forma de suma de Mellin. Nótese que por el teorema del valor intermedio $$1-\sum_k \frac{1}{p_k^s}$$ tiene una raíz entre $s>0$ y $s<1$ (estas desigualdades son estrictas). Llamemos a esta raíz $\rho.$ Ahora $$\frac{1}{1-\sum_k \frac{1}{p_k^s}}$$ tiene un polo simple allí con residuos $$\operatorname{Res} \left(\frac{1}{1-\sum_k \frac{1}{p_k^s}}; s=\rho\right) = \frac{1}{\sum_k \frac{\log p_k}{p_k^\rho}}.$$ Por lo tanto, podemos concluir que $$M(n) \sim \left(\sum_k \frac{\log p_k}{p_k^\rho}\right)^{-1} \frac{n^\rho}{\rho}$$ obteniendo finalmente que $$T(n) \sim \left(\sum_k \frac{\log p_k}{p_k^\rho}\right)^{-1} \sum_k\left(\frac{n^\rho}{\rho} - \frac{(n/p_k)^\rho}{\rho}\right)\\ = \left(\sum_k \frac{\log p_k}{p_k^\rho}\right)^{-1} \frac{n^\rho}{\rho}\sum_k\left(1 - (1/p_k)^\rho\right) = (m-1) \left(\sum_k \frac{\log p_k}{p_k^\rho}\right)^{-1} \frac{n^\rho}{\rho}.$$ Esta fórmula asintótica converge muy bien y el cociente entre $T(n)$ y este término principal se convierte en uno muy rápidamente, como muestran los experimentos numéricos. En particular $$\frac{T(n)}{n}\in\Theta(n^{\rho-1})$$ para que $$\frac{T(n)}{n}\to 0$$ tal y como se reclama desde $\rho-1<0.$

Animo a los lectores a que completen los detalles y estoy disponible para preguntas. Gracias a M. Cohen por hacer una pregunta tan maravillosa.

Este es el código de Maple que he utilizado para verificar estas fórmulas.

ex :=
proc(l, n)
option remember;
local k, r, t, ds, cfs, terms, tval, pos;
    if n=0 then return 1 fi;

    r := 0;
    for k from 0 to ilog\[2\](n) do
        if k=0 then
            for t in l do
                if t>n then r := r+1; fi;
            od;
        else
            ds :=
            map(simplify, expand(add(1/l\[q\]^s, q=1..nops(l))^k));
            ds := convert(ds,list);

            cfs := map(t->subs(s=0, t), ds);
            terms := \[seq(ds\[pos\]/cfs\[pos\], pos=1..nops(ds))\];

            for pos to nops(ds) do
                for t in l do
                    tval := op(1, terms\[pos\]);
                    if tval>floor(n/t) and tval<=n then
                        r := r+cfs\[pos\];
                    fi;
                od;
            od;
        fi;

    od;

    r;
end;

T :=
proc(l, n)
option remember;
    local t, r;

    if n=0 then return 1 fi;

    r := 0;
    for t in l do
        r := r+T(l, floor(n/t));
    od;

    r;
end;

rho :=
proc(l)
option remember;
    fsolve(1-add(1/l\[k\]^s, k=1..nops(l)), s);
end;

lterm :=
proc(l, n)
    (nops(l)-1)\*1/
    add(log(l\[k\])/l\[k\]^rho(l), k=1..nops(l))\*n^rho(l)/rho(l);
end;

Answer 4

Presento una adición importante. El código de mi primera respuesta no funciona correctamente cuando algunos de los $p_k$ se repiten aunque las matemáticas sean correctas, y no es tan eficiente. He puesto remedio a este defecto y presento un código que funciona por duplicado $p_k$ y es asombrosamente rápido incluso para argumentos grandes $n$ a $T(n).$ He utilizado este código para verificar la corrección del argumento matemático anterior empíricamente para una serie de conjuntos de $p_k.$

mul\_dir :=
proc(l1, l2)
option remember;
local r, res, t, t1, t2, pos;

    r := \[\];

    for t1 in l1 do
        for t2 in l2 do
            r := \[op(r), \[t1\[1\]\*t2\[1\], t1\[2\]\*t2\[2\]\]\];
        od;
    od;

    r := sort(r, (p1, p2) -> p1\[2\] < p2\[2\]);

    res := \[\]; p := r\[1\];
    for pos from 2 to nops(r) do
        if p\[2\] <> r\[pos\]\[2\] then
            res := \[op(res), p\];
            p := r\[pos\];
        else
            p\[1\] := p\[1\] + r\[pos\]\[1\];
        fi;
    od;

    res := \[op(res), p\];
    res;
end;

ex :=
proc(l, n)
option remember;
local k, r, t, f, ds, cfs, terms, tval, pos;
    if n=0 then return 1 fi;

    r := 0; f:= \[seq(\[1, l\[q\]\], q=1..nops(l))\];
    for k from 0 to ilog\[2\](n) do
        if k=0 then
            ds := \[\[1,1\]\];
        else
            ds := mul\_dir(ds, f);
        fi;

        for pos to nops(ds) do
            for t in l do
                tval := ds\[pos\]\[2\];
                if tval>floor(n/t) and tval<=n then
                    r := r+ds\[pos\]\[1\];
                fi;
            od;
        od;
    od;

    r;
end;

T :=
proc(l, n)
option remember;
    local t, r;

    if n=0 then return 1 fi;

    r := 0;
    for t in l do
        r := r+T(l, floor(n/t));
    od;

    r;
end;

rho :=
proc(l)
option remember;
    fsolve(1-add(1/l\[k\]^s, k=1..nops(l)), s);
end;

lterm :=
proc(l, n)
    (nops(l)-1)\*1/
    add(log(l\[k\])/l\[k\]^rho(l), k=1..nops(l))\*n^rho(l)/rho(l);
end;