¿Es cada entero representable como la suma de cuatro cuadrados de Fibonacci?

Question

Teorema de los Cuatro Cuadrados de Lagrange. Todo número entero positivo $N$ puede expresarse como la suma de cuatro cuadrados, es decir,

$$N = a^2 + b^2 + c^2 + d^2.$$

Teorema de Zeckendorf. Todo entero tiene una representación única en la que puede expresarse como la suma de números de Fibonacci no consecutivos, es decir,

$$N = \sum_i F_{c_i}, c_i \in \mathbb{Z}, c_i \ge 2, c_{i+1} \gt c_i + 1,$$

donde $F_k$ es la secuencia de Fibonacci generada por la ecuación de recurrencia $F_{n+2} = F_{n+1} + F_n$ con $F_0 = 0, F_1 = 1$.

Pregunta: ¿Es posible representar también todo número entero positivo como la suma de cuatro cuadrados de Fibonacci?

$$ \begin{align} 0 &= F_0^2 \\ 1 &= F_1^2 \\ 2 &= F_1^2 + F_1^2 \\ 3 &= F_1^2 + F_1^2 + F_1^2 \\ 4 &= F_3^2 \\ 5 &= F_3^2 + F_1^2 \\ 6 &= F_3^2 + F_1^2 + F_1^2 \\ 7 &= F_3^2 + F_1^2 + F_1^2 + F_1^2 \\ 8 &= F_3^2 + F_3^2 \\ 9 &= F_4^2 \\ 10 &= F_4^2 + F_1^2 \\ 11 &= F_4^2 + F_1^2 + F_1^2 \\ 12 &= F_4^2 + F_1^2 + F_1^2 + F_1^2 \\ 13 &= F_4^2 + F_3^2 \\ 14 &= F_4^2 + F_3^2 + F_1^2 \\ 15 &= F_4^2 + F_3^2 + F_1^2 + F_1^2 \\ 16 &= F_3^2 + F_3^2 + F_3^2 + F_3^2 \end{align} $$

Nota que en las sumas anteriores, si tenemos menos de $4$ cuadrados, siempre podemos sumar $F_0^2 = 0^2$ para tener una representación de cuatro cuadrados.

La representación de la suma de cuatro cuadrados de Fibonacci, si existe, no es necesariamente única para un entero. Por ejemplo,

$$ \begin{align} 4 &= F_1^2 + F_1^2 + F_1^2 + F_1^2 \\ &= F_3^2 + F_0^2 + F_0^2 + F_0^2 \end{align} $$

Answer 1

Si $N$ es grande, solo hay alrededor de $\ln N$ cuadrados de Fibonacci por debajo de $N$. Luego hay a lo sumo $(\ln N)^4$ sumas diferentes por debajo de $N$. Esa cantidad eventualmente crece más lentamente que $N$, así que aparecerán brechas.
No sé cuándo será la primera brecha.

Answer 2

Bruteforce da que el primer hueco es $24$: los únicos cuadrados de Fibonacci menores que $24$ son $0, 1, 4, 9$. Necesitamos al menos dos nueves (de lo contrario la suma es como máximo $9 + 3 \cdot 4 = 21$), así que ahora tenemos que representar $6$ como suma de dos números de $0,1,4$. Pero tal suma es o bien $8$, o como máximo $5$. Así que $24$ no es la suma de $4$ cuadrados de Fibonacci.

No es difícil encontrar la representación para los números del 17 al 23.

(pero por supuesto, el argumento de Empy2 es mucho más elegante que esto)

Answer 3

He escrito el enfoque de fuerza bruta en Mathematica y obtengo resultados de hasta 10^9 en cuestión de segundos en mi máquina. Obtuve 12 553 enteros distintos, en el rango de $0$ a $1254718084=4 F_{22}^2$. Sin embargo, excluí F_0 = 0 de él, porque parecía inútil.

Aquí hay un gráfico de registro, donde el eje x muestra el n-ésimo entero y el eje y su valor.

fibonacci = Table[Fibonacci[n]^2, {n, 1, 22}];
reverseFib[n_] := 
 SubsuperscriptBox["F", Position[fibonacci, n][[1, 1]] - 1, 2] // 
  DisplayForm
subsets = 
  Tuples[fibonacci, 1]~Join~Tuples[fibonacci, 2]~Join~
   Tuples[fibonacci, 3]~Join~Tuples[fibonacci, 4];
DeleteDuplicates[
  SortBy[{Total[#], Total[reverseFib /@ #]} & /@ subsets, 
   First]] // TableForm

Dado que la lista es demasiado exhaustiva, la subí a pastebin