Secuencias de Fibonacci-esque módulo $1$: ¿cuál es el infimo más grande posible?

Question

Deje que una secuencia infinita $S$ sea una "secuencia tipo Fibonacci" si, para todo $n \geq 3, S(n) = S(n-1) + S(n-2).$ Podemos reducir $S$ módulo $1$ para obtener una "secuencia Fibonacci reducida." Estas secuencias pueden contener el elemento $0$, pero no el elemento $1$. Por ejemplo, la secuencia $0.2, 0.6, 0.8, 0.4, 0.2, 0.6, 0.8, 0.4, ...$ es una secuencia Fibonacci reducida con ínfimo $0.2.$ ¿Cuál es el ínfimo más grande posible de una secuencia Fibonacci reducida? ¿Qué pasa con las secuencias Fibonacci reducidas que solo contienen números racionales?

En una de las respuestas, se presentó una secuencia de secuencias Fibonacci reducidas con ínfimos aproximándose a $\frac{1}{3}$.

La secuencia Fibonacci reducida $\frac{19104}{64079}, \frac{39071}{64079}, \color{red}{\frac{58175}{64079}}, \frac{33167}{64079}, \frac{27263}{64079}, \color{red}{\frac{60430}{64079}}, \frac{23614}{64079}, \frac{19965}{64079}, \frac{43579}{64079}, \color{red}{\frac{63544}{64079}}, \frac{43044}{64079}, \frac{42509}{64079}, \frac{21474}{64079}, \color{red}{\frac{63983}{64079}}, \frac{21378}{64079}, \frac{21282}{64079}, \frac{42660}{64079}, \color{red}{\frac{63942}{64079}}, \frac{42523}{64079}, \frac{42386}{64079}, \frac{20830}{64079}, \color{red}{\frac{63216}{64079}}, \frac{19967}{64079}, \frac{19104}{64079}, \frac{39071}{64079}, …$ que contiene solo números racionales, tiene un ínfimo de $\frac{19104}{64079}$ y un periodo de $23.$ Es el mejor hasta el denominador de $75000$.

Los casos mejor conocidos son los que están en esta conjetura que hice.

He resaltado todos los elementos "grandes" (por encima de tres veces el ínfimo) en rojo, ya que parecen tener un patrón, apareciendo cada $3$ o $4$ números, y este patrón parece valer la pena analizar.

Conjeturo que para irracionales, el límite es $\frac{1}{3},$ y para racionales, el límite es $\frac{2}{3\sqrt{5}}.$

Answer 1

Esto proporciona un límite mejorado en la respuesta cuando se permiten valores irracionales.

Sea $\phi=\tfrac{1+\sqrt 5}2$ la razón áurea. Sea $S(1)=\tfrac 1 3+x$ y $S(2)=\tfrac 1 3 - \tfrac x \phi$.

Entonces $$ S(3)= \tfrac 2 3 + x(1-\tfrac 1\phi) = \tfrac 2 3 + x \phi^{-2}\\ S(4)=1+x(1-\tfrac 2\phi )=1-x \phi^{-3}\\ S(5)=\tfrac 5 3 +x(2-\tfrac 3\phi )=\tfrac 5 3+x \phi^{-4} $$

Como puedes ver, el término de $x$ sigue disminuyendo.

Debido a que el período es par, los términos que están cerca de los enteros (por ejemplo $S(4)$) siempre tienen un coeficiente negativo en $x$ -- así que cuando reduces módulo 1, nunca obtienes términos cerca de 0, solo términos cerca de 1/3, 2/3, y ligeramente por debajo de 1.

Puedes establecer $x$ tan pequeño como quieras para acercarte al infimo tanto como desees a 1/3.

Answer 2

Teorema $1$: Toda secuencia reducida de Fibonacci contiene términos menores que $\frac{1}{2}$.

Prueba: Procedemos a demostrar esto por contradicción. Sea $S$ una secuencia reducida de Fibonacci sin elementos menores que $\frac{1}{2}.$ Sea $m$ el menor entero positivo tal que S contiene elementos menores que $1 - \frac{1}{2^m}.$ Sea $a_n$ el primer elemento menor que $1 - \frac{1}{2^m}.$ Dado que todos los elementos son mayores que $\frac{1}{2}, a_n + a_{n+1} > 1,$ entonces $a_{n+2} = a_n + a_{n+1} - 1,$ lo cual es menor que $a_n$. Del mismo modo, $a_{n+3}$ también es menor que $a_n$. Por lo tanto, $a_{n+4} = a_{n+2} + a_{n+3} - 1 \leq 2a_n - 1 \leq 2 - \frac{2}{2^m} - 1 = 1 - \frac{1}{2^{m-1}},$ entonces $a_{n+4} \leq 1 - \frac{1}{2^{m-1}}.$ Esto contradice el hecho de que $m$ es el entero positivo más pequeño con la propiedad anterior. Así queda demostrado.

Teorema $2$: Toda secuencia reducida de Fibonacci consistente únicamente de números racionales es periódica, y por lo tanto tiene un elemento más pequeño.

Prueba: Sea $d$ el denominador común de los dos primeros términos. Dado que los términos siguientes son sumas de términos anteriores, todos tienen denominador común $d.$ Por lo tanto, toda la secuencia tiene denominador común $d.$ Cada par de términos consecutivos está precedido por un par único (o no está precedido por ningún par). Dado que solo hay un número finito de opciones para los pares de elementos consecutivos, alguno de ellos debe repetirse en algún momento. Si el primer par repetido es diferente al par inicial, entonces tiene dos posibles pares precedentes, lo cual es imposible. Por lo tanto, el primer par que se repite es el par inicial. Dado que cada par está seguido por un par único, la secuencia sigue repitiendo el mismo ciclo de pares. Esto significa que la secuencia es periódica, por lo que cada elemento aparece infinitas veces. Dado que contiene un número finito de elementos únicos, tiene un elemento más pequeño.

Teorema $3$: Toda secuencia reducida de Fibonacci consistente únicamente de números racionales contiene infinitos términos mayores que tres veces el ínfimo de la secuencia ("elementos grandes").

Prueba: Sea $S$ una secuencia reducida de Fibonacci. Sea $a_n$ la primera ocurrencia del elemento más pequeño tal que $n \geq 3.$ Esto existe por el Teorema $2.$

Caso $1$: $a_{n+1} < a_n.$

Esto contradice el hecho de que $a_n$ es el elemento más pequeño.

Caso $2$: $a_n \leq a_{n+1} < 2a_n.$

En este caso, $a_{n-1} = a_{n+1} - a_n < 2a_n - a_n < a_n,$ lo cual contradice el hecho de que $a_n$ es el elemento más pequeño.

Caso $3$: $a_{n+1} \geq 2a_n$ y $a_n \geq \frac{1}{3}.$

En este caso, dado que $a_n \geq \frac{1}{3}, 3a_n \geq 1,$ entonces $a_{n+1} + a_n \geq 1.$ Por lo tanto, $a_{n+2} = a_n + a_{n+1} - 1,$ lo cual es menor que $a_n,$ contradiciendo el hecho de que $a_n$ es el elemento más pequeño. Así queda demostrado.

Caso $4$: $a_{n+1} \geq 2a_n$ y $a_n < \frac{1}{3}.$

En este caso, por un razonamiento similar al anterior, $a_{n+2}$ es un elemento grande. Por lo tanto, hay un elemento grande. Según el Teorema $2$, esto implica que hay infinitos elementos grandes.

Parece que una variación de la demostración del Teorema $4$ puede ser utilizada para demostrarlo también para irracionales.

Answer 3

Esto puede que no contribuya demasiado, pero puedo demostrar que el mínimo no puede ser $1/3$.

Supongamos que el mínimo es $1/3$. Para algún $x$, los primeros $11$ términos $a_1,a_2,\dotsc,a_{11}$ en la secuencia son $$ {1\over3},\ {1\over3}+x,\ {2\over3}+x,\ 2x,\ {2\over3}+3x,\ {2\over3}+5x,\ {1\over3}+8x,\ 13x,\ {1\over3}+21x,\ {1\over3}+34x,\ {2\over3}+55x $$ donde todos los términos se entienden que se reducen módulo uno.

De $a_2=(1/3)+x$ deducimos que $0\le x<2/3$.

De $a_3=(2/3)+x$ deducimos que $0\le x<1/3$.

De $a_4=2x$ deducimos que $1/6\le x<1/3$.

De $a_5=(2/3)+3x$ deducimos que $2/9\le x<1/3$.

De $a_6=(2/3)+5x$ deducimos que $2/9\le x<4/15$.

Pausamos para notar que tenemos una desigualdad estricta $x<4/15$; eso será importante.

De $a_7=(1/3)+8x$ deducimos que $1/4\le x<4/15$.

De $a_8=13x$ deducimos que $10/39\le x<4/15$.

De $a_9=(1/3)+21x$ deducimos que $10/39\le x<4/15$ (así que no hay mejora en $a_8$).

De $a_{10}=(1/3)+34x$ deducimos que $9/34\le x<4/15$.

De $a_{11}=(2/3)+55x$ deducimos que $4/15\le x<4/15$, ¡contradicción!

Desafortunadamente, esto solo descarta $1/3$, no descarta ningún número alrededor de $1/3$.

Answer 4

Familia conjeturada de secuencias racionales que alcanzan (en el límite) el ínfimo $\frac{2}{3\sqrt{5}}$:

Usaremos el indexado estándar de los números de Fibonacci: es decir, $F_0 = 0$ y $F_1 = 1$. Definimos $L_n$ como $F_{n-1} + F_{n+1}$.

Conjeturo (basado en evidencia empírica) que la secuencia reducida de Fibonacci comenzando con $\frac{2F_{8n-1} - 2}{3L_{8n-1}}$ y $\frac{F_{8n+2}-F_{8n-5} + 1}{3L_{8n-1}}$ para $n \geq 1$ tiene ínfimo $\frac{2F_{8n-1} - 2}{3L_{8n-1}}$. Esto se acerca a $\frac{2}{3\sqrt{5}}$ cuando $n \rightarrow \infty$.

Answer 5

Aquí está el programa de Python que utilicé para encontrar el límite inferior de los números racionales presentados en la publicación principal (ahora obsoleta):

import math

target = 203/682 # el mejor anterior

def reduce(i,n):
    if i < n:
        return i
    else:
        return i - n

def checksuccess(n):
    b = math.floor(target*n) + 1
    for i in range(b, n//2 - 1):
        for j in range(2*i+1, n):
            current_1 = i
            current_2 = j
            while current_1 != -1:
                if current_2 < i:
                    break
                elif current_2 == i and reduce(current_1 + i, n) == j:
                    print(i,j,n)
                    break
                else:
                    current_2 = current_1 + current_2
                    current_1 = current_2 - current_1
                    current_2 = reduce(current_2, n)
            else:
                continue
    return 0

for i in range(1000, 10000):
    checksuccess(i)
    if i % 100 == 0:
        print(i)

Encuentra secuencias de números racionales con denominadores entre $1000$ y $10000$ que hacen un mejor trabajo que la secuencia $\frac{203}{682}, \frac{416}{682}, \color{red}{\frac{619}{682}}, \frac{353}{682}, \frac{290}{682}, \color{red}{\frac{643}{682}}, \frac{251}{682}, \frac{212}{682}, \frac{463}{682}, \color{red}{\frac{675}{682}}, \frac{456}{682}, \frac{449}{682}, \frac{223}{682}, \color{red}{\frac{672}{682}}, \frac{213}{682}, \frac{203}{682}, \frac{416}{682} ...,$ el mejor anterior. También imprime su progreso cada $100$ denominadores que completa.

Nuevamente, he resaltado los términos en rojo para encontrar el patrón.