🔢 mathematics

Carryless Pairing: Additive Pairing in the Fibonacci Basis

Este artículo introduce un mapa de emparejamiento sin acarreo e inyectivo de $\mathbb{N}^2$ a $\mathbb{N}$ que codifica dos números en bandas de índices de Zeckendorf disjuntas separadas por un delimitador, permitiendo la evaluación y la inversión mediante operaciones de soporte aditivo sin multiplicación ni factorización, con la corrección central verificada en Rocq.

Autores originales: Milan Rosko

Publicado 2026-05-12

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Milan Rosko

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

La Gran Idea: Empacar Dos Cajas Sin Romperlas

Imagina que tienes dos cajas de bloques de Lego, etiquetadas como Caja X y Caja Y. Quieres pegarlos juntos en una sola estructura gigante para poder transportarlos como un objeto único, pero también quieres poder separarlos más tarde sin usar pegamento, cinta adhesiva ni herramientas especiales.

La mayoría de las formas de combinar números (como las matemáticas estándar o el código informático) son como usar pegamento. Para separarlos más tarde, a menudo tienes que realizar cálculos complejos, factorizar números o "llevar" dígitos (como cuando $9 + 1 = 10$ en la suma normal, donde el 1 se "lleva" a la siguiente columna). Este artículo propone una nueva forma de combinar números que requiere cero pegamento y cero llevadas.

El Escenario: El "Set de Lego" de Fibonacci

Para entender cómo funciona esto, necesitamos cambiar las reglas de cómo construimos los números. En lugar de usar el sistema decimal estándar (unidades, decenas, centenas), este artículo utiliza la sucesión de Fibonacci ($1, 2, 3, 5, 8, 13, 21...$).

En este sistema, cada número tiene un "plano de Lego" especial llamado representación de Zeckendorf. La regla de oro de este plano es: Nunca puedes usar dos números de Fibonacci consecutivos.

Mal: $5 + 3$ (porque 5 y 3 están uno al lado del otro en la secuencia).
Bien: $5 + 2$ (porque entre 5 y 2 hay un hueco).

Esta regla de "sin consecutivos" es el ingrediente secreto que hace posible todo el truco.

El Truco de Magia: Las Franjas "Par" e "Impar"

El autor, Milan Rosko, inventó un método para empaquetar la Caja X y la Caja Y en un solo número colocándolas en diferentes "barrios" de la sucesión de Fibonacci.

El Barrio Par (Caja X):
El artículo toma el plano del número X y desplaza todas sus piezas de Lego a posiciones de números pares en la sucesión de Fibonacci.
- Analogía: Imagina que X es un conjunto de libros. Los colocamos todos en los estantes numerados con números pares de una biblioteca.
El Delimitador (La Valla):
Antes de poner la Caja Y, necesitamos saber hasta dónde llega X. El artículo calcula una "valla" o delimitador basado en el tamaño de X. Llamemos a esta valla B.
- Analogía: Si X ocupa los estantes del 2 al 10, la valla se construye en el estante 12.
El Barrio Impar (Caja Y):
Ahora, tomamos el plano del número Y y desplazamos sus piezas de Lego a posiciones de números impares, pero solo comenzando después de la valla (B).
- Analogía: Colocamos todos los libros de Y en los estantes numerados con números impares, pero solo en los estantes 13, 15, 17, etc. Dejamos los estantes impares antes de la valla vacíos.

Por Qué Es "Sin Llevadas" (La Mejor Parte)

En matemáticas normales, si sumas dos números, podrías obtener una "llevada" (por ejemplo, $5+5=10$ ). En este sistema de Fibonacci, si sumas dos números que no comparten ningún lugar "consecutivo", no ocurre ninguna llevada.

Como el artículo coloca X en estantes pares y Y en estantes impares (con un hueco en medio), los dos conjuntos de piezas de Lego nunca se tocan.

X está en lugares pares.
Y está en lugares impares (lejos).
No hay dos números consecutivos en la mezcla final.

Resultado: El número combinado ya está en su forma perfecta y "normal". No necesitas hacer ninguna limpieza o matemática para arreglarlo. Es como poner dos piezas de rompecabezas que no se tocan; simplemente encajan perfectamente.

Cómo Desempaquetarlo (Decodificación)

Para recuperar las cajas originales, solo tienes que mirar el número combinado y hacerte dos preguntas simples:

¿Quién está en los estantes pares? (Eso es X).
¿Quién está en los estantes impares después de la valla? (Eso es Y).

Como las reglas son tan estrictas (sin tocarse, huecos específicos), no hay confusión. Siempre puedes decir exactamente qué pieza pertenece a X y cuál a Y.

Limitaciones Importantes (La Parte "No Sobreyectiva")

El artículo admite que este método no crea un código para cada número posible.

Analogía: Imagina un estacionamiento donde los coches (números) solo pueden estacionarse en lugares específicos. Si intentas estacionar un coche en un lugar que viola la regla de "no tocarse" o la regla de "la valla", ese lugar queda vacío.
El artículo llama a esto inyectivo pero no sobreyectivo.
- Inyectivo: Cada par de (X, Y) obtiene un código único. Ningún par produce el mismo número.
- No Sobreyectivo: Algunos números en el mundo no pueden formarse con este método. Si eliges un número al azar, podría no ser un par "empaquetado" válido.

Sin embargo, el artículo proporciona una prueba simple: Si intentas desempaquetar un número y luego lo reempaquetas, y obtienes exactamente el mismo número de vuelta, entonces era un par válido. Si el número cambia, no era un par válido desde el principio.

¿Por Qué Importa Esto? (El "Por Qué")

El autor no está tratando de hacer una calculadora más rápida para tu teléfono. La motivación es más profunda, arraigada en la lógica y los fundamentos matemáticos:

Suma Pura: La mayoría de las formas de combinar números dependen de la multiplicación o la división compleja (como descomponer un número en factores primos). Este método depende solo de la suma y de verificar posiciones.
Sistemas Matemáticos Débiles: En algunos sistemas de lógica muy básicos (donde no se permite usar la multiplicación), no se puede probar que puedes combinar dos números y recuperarlos. Este artículo muestra una forma de hacerlo usando solo suma simple, lo que ayuda a los matemáticos a comprender los requisitos mínimos absolutos necesarios para que la lógica funcione.
Verificación de Pruebas: Como el proceso es tan simple (solo mirar posiciones y sumar), es muy fácil para una computadora verificar que las matemáticas son correctas sin confundirse.

Resumen en Una Frase

Este artículo presenta una forma ingeniosa de combinar dos números en uno utilizando la sucesión de Fibonacci, donde los dos números viven en "zonas" separadas y que no se tocan, de modo que pueden sumarse sin matemáticas desordenadas y separarse simplemente mirando dónde están sentados.

Resumen Técnico: Emparejamiento sin Acarreo en la Base de Fibonacci

Enunciado del Problema
El artículo aborda la construcción de una función de emparejamiento $\pi: \mathbb{N}^2 \to \mathbb{N}$ que opera estrictamente dentro de las restricciones aditivas de la base de Zeckendorf (Fibonacci). Los esquemas de emparejamiento tradicionales a menudo dependen del entrelazamiento posicional de dígitos (por ejemplo, códigos Z-order/Morton) o de operaciones aritméticas que involucran multiplicación y factorización de números primos (por ejemplo, numeración de Gödel, emparejamiento de Cantor). El autor busca un mecanismo donde la codificación y decodificación de un par $(x, y)$ dependan únicamente de la extracción de soporte y operaciones aditivas, evitando la multiplicación, la exponenciación y la necesidad de pasos de propagación de "acarreo" o normalización durante la combinación de datos. Esto está motivado por el deseo de apoyar argumentos de incompletitud e investigaciones de teoría de la prueba en sustratos aritméticos débiles (como $I\Delta_0$ ) donde la multiplicación no se asume o es costosa.

Metodología
La solución propuesta, denominada Emparejamiento sin Acarreo ( $\pi_{CL}$ ), codifica dos números naturales en "bandas" disjuntas de índices de Fibonacci basadas en sus soportes de Zeckendorf.

Representación de Zeckendorf: Todo número natural $n$ se representa de manera única como una suma de números de Fibonacci no consecutivos $F_k$ (donde $k \ge 2$ ). El conjunto de índices se denota $Z(n)$ .
Construcción del Delimitador: Para un par $(x, y)$ , el algoritmo primero calcula el rango $r(x)$ , definido como el índice más pequeño tal que $F_{r(x)} > x$ . Un delimitador $B(x)$ se establece en $2r(x)$ .
Separación de Bandas:
- Banda Par (para $x$ ): Los índices del soporte de $x$ , $Z(x)$ , se mapean a índices pares mediante $e \mapsto 2e$ . Estos se colocan en el rango $[4, 2r(x))$ .
- Banda Impar (para $y$ ): Los índices del soporte de $y$ , $Z(y)$ , se mapean a índices impares mediante $j \mapsto B(x) + (2j - 1)$ . Estos se colocan estrictamente por encima del delimitador $B(x)$ .
Invariante sin Acarreo: Dado que $Z(x)$ no contiene enteros consecutivos, los índices pares mapeados tienen huecos de al menos 4. De manera similar, los índices impares mapeados tienen huecos de al menos 4. Crucialmente, el delimitador $B(x)$ asegura que el índice par más alto utilizado por $x$ sea estrictamente menor que el índice impar más bajo utilizado por $y$ . En consecuencia, la unión de estos dos conjuntos de índices no contiene enteros consecutivos.
Codificación: El valor codificado es la suma de los números de Fibonacci correspondientes a la unión de estos índices. Dado que el soporte no contiene índices consecutivos, el resultado está automáticamente en forma normal de Zeckendorf; no se requiere propagación de acarreo.

Contribuciones Clave

Dispositivo Puramente Aditivo: El artículo define un mapa de emparejamiento $\pi_{CL}$ y un mapa de inversión unpair que operan exclusivamente sobre soportes de Zeckendorf utilizando adición y escaneos acotados. No se utiliza multiplicación ni factorización.
Inyectividad y Decidibilidad: Se demuestra que el mapa es inyectivo. Aunque no es sobreyectivo, la pertenencia a la imagen es decidible mediante una "prueba de punto fijo": un número $n$ está en la imagen si y solo si $\pi_{CL}(\text{unpair}(n)) = n$ .
Canonización en un Paso: El artículo introduce una función de canonización $can(n) = \pi_{CL}(\text{unpair}(n))$ . Esta función mapea cualquier número natural a su representante único en la imagen de $\pi_{CL}$ en un solo paso.
Lema de Estabilidad: El artículo establece que modificar la segunda coordenada $y$ (agregando o eliminando un índice de su soporte) resulta en un cambio local en el valor codificado (agregando o restando un número de Fibonacci específico), siempre que $x$ permanezca fijo.
Mecanización: Todos los teoremas centrales de corrección (inversión e inyectividad) están mecanizados en Rocq (anteriormente Coq), utilizando el lenguaje de especificación Gallina. La formalización incluye pruebas de la existencia y unicidad de soportes de Zeckendorf, asegurando que el dispositivo de emparejamiento no dependa de axiomas no demostrados con respecto a la interfaz de soporte.

Resultados

Corrección: El Teorema 6.0.1 demuestra que unpair $\circ$ $\pi_{CL}$ es la función identidad en $\mathbb{N}^2$ .
No Sobreyectividad: El mapa no es sobreyectivo; muchos números naturales (por ejemplo, 6) no corresponden a pares válidos bajo este esquema porque sus soportes de Zeckendorf no se alinean con las restricciones específicas de paridad y delimitador.
Complejidad: El costo del emparejamiento y desemparejamiento está dominado por el paso de extracción de soporte (típicamente $O(r(n))$ para un escaneo voraz). El artículo señala que estas son observaciones informales en lugar de teoremas de complejidad certificados.
Comparación: A diferencia de la numeración de Gödel (que requiere factorización) o el emparejamiento de Cantor (que requiere multiplicación y raíces cuadradas), $\pi_{CL}$ opera puramente de forma aditiva. A diferencia del orden Z (que entrelaza posiciones binarias fijas), $\pi_{CL}$ desplaza la posición del segundo operando basándose en el rango del primero, creando un delimitador dinámico.

Significado y Afirmaciones
El artículo sitúa esta construcción como una herramienta para la matemática inversa y el estudio de sustratos aritméticos débiles. Al proporcionar una función de emparejamiento que evita la multiplicación, el autor sugiere que podría ser útil para investigar argumentos de consistencia y demostrabilidad en sistemas donde la multiplicación no está disponible o está restringida (haciendo referencia a Buss, 1997; Friedman, 1976).

El autor declara explícitamente modestia respecto a las implicaciones más amplias:

El artículo no afirma derivar la propia interfaz de soporte de Zeckendorf a partir de principios de solo adición, conjeturando que tal derivación podría no existir.
No afirma una caracterización de forma cerrada simple de la imagen de $\pi_{CL}$ ; el procedimiento de decisión es la prueba de punto fijo basada en soporte.
La contribución principal es la construcción explícita de un dispositivo "sin acarreo" y la verificación de sus propiedades, haciendo que la imagen y su estructura geométrica sean directamente inspeccionables para el análisis teórico.

El trabajo se presenta como un dispositivo aritmético fundamental en lugar de una estructura de datos práctica para la computación general, enfatizando su utilidad teórica en lógica y teoría de la prueba.