🔢 mathematics

New lower bounds for constant-weight codes via seeded bit-swap tabu search

Este artículo presenta 124 nuevas construcciones para códigos binarios de peso constante utilizando una búsqueda tabú de intercambio de bits con semilla, las cuales mejoran los límites inferiores existentes para $A(n,d,w)$ y, en consecuencia, mejoran los límites inferiores de los números de beso para las dimensiones 32, 33, 34 y 37.

Autores originales: William Echols

Publicado 2026-08-17

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: William Echols

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

Imagina que estás intentando empacar una maleta para un viaje, pero con una regla muy extraña: cada objeto que empaques debe tener exactamente el mismo tamaño, y no dos objetos pueden ser demasiado similares entre sí. Si son demasiado parecidos, podrían confundirse en la oscuridad, causando el caos. En el mundo de la comunicación digital, esta "maleta" es un mensaje, los "objetos" son patrones de ceros y unos (bits), y el "tamaño" es cuántos unos hay en el patrón. Este es el rompecabezas de los códigos de peso constante. Los científicos utilizan estos códigos para enviar datos de manera confiable a través de canales con ruido, como el Wi-Fi o la radio del espacio profundo, asegurando que incluso si algunos bits se desordenan, el receptor pueda determinar qué fue lo que se envió. El objetivo es simple pero increíblemente difícil: meter tantos elementos únicos y distintos en la maleta como sea posible sin que choquen entre sí. Cuanto más grande sea la maleta (más códigos puedas meter), más información podemos enviar a la vez.

Entra William Echols, quien decidió abordar este problema de empaquetado con un giro ingenioso. En lugar de comenzar con una maleta vacía y lanzar objetos al azar, esperando que quepan, utilizó un enfoque "sembrado". Piensa en esto como si: si quieres construir un mejor castillo de Lego, no empiezas desde cero; tomas un castillo excelente ya existente, sacas algunas piezas y las intercambias para ver si puedes hacerlo aún más grande o resistente. Echols utilizó un método computacional llamado búsqueda tabú, que es como un explorador muy obstinado que se niega a volver sobre sus pasos (para evitar quedarse atrapado en bucles) y sigue probando nuevos caminos. Al "sembrar" este explorador con diseños de códigos existentes y de alta calidad, guio su búsqueda para encontrar 124 arreglos de empaquetado nuevos y más grandes que nunca antes habían sido descubiertos. Estos nuevos arreglos mejoran los límites inferiores de cuántos mensajes podemos enviar y también nos ayudan a entender cuántas esferas pueden tocar una esfera central en un espacio de alta dimensión, un concepto conocido como "números de beso" (kissing numbers).

El rompecabezas del empaquetado y la semilla mágica

En el mundo digital, los datos son simplemente una larga cadena de ceros y unos. A veces, para que sean robustos, solo permitimos cadenas que tengan un número específico de unos. Por ejemplo, si decimos que el "peso" es 5, cada cadena debe tener exactamente cinco unos y el resto ceros. Ahora, imagina que tienes una colección de estas cadenas. Para prevenir errores, cada cadena en tu colección debe ser lo suficientemente diferente de todas las demás. Si dos cadenas son demasiado similares, un poco de ruido podría convertir una en la otra, y el receptor se confundiría. La "distancia" entre ellas se mide por cuántos lugares son diferentes.

La gran pregunta en este campo es: ¿Cuál es el número máximo de cadenas que puedes meter en tu colección? Este número máximo se llama $A(n, d, w)$ , donde $n$ es la longitud de la cadena, $d$ es la distancia mínima requerida y $w$ es el número de unos. Durante décadas, matemáticos y científicos de la computación han intentado encontrar las colecciones más grandes para diversos entornos. Han encontrado algunas colecciones excelentes, pero a menudo no saben si han encontrado la más grande de todas. Solo saben que no pueden hacer mejor que un cierto número.

La estrategia "sembrada"

Los intentos previos para encontrar estos números máximos utilizando búsquedas computacionales a menudo se sentían como vagar en un bosque oscuro. Las computadoras comenzaban con conjetzas aleatorias y, aunque a veces encontraban buenos caminos, a menudo se quedaban atrapadas en claros locales que parecían la cima de una montaña, pero que no lo eran. Se detenían allí, pensando que habían encontrado el mejor código posible, cuando un código mucho más grande estaba justo detrás de la siguiente colina.

Echols se dio cuenta de que la clave era dejar de empezar desde cero. Utilizó una técnica de inicialización sembrada. En lugar de generar un punto de partida aleatorio, tomó un código existente de alta calidad (una "semilla") y lo usó para lanzar la búsqueda.

Lo hizo de dos maneras lúdicas:

Siembra Directa: Tomó un código existente y le añadió una palabra extra, elegida cuidadosamente para causar la menor cantidad de "problemas" (déficit de distancia). Esto creó un punto de partida ligeramente más grande y ligeramente desordenado.
Siembra de Vecindad: Miró códigos para problemas ligeramente diferentes. Por ejemplo, si quería un código de longitud 30, podría tomar un gran código de longitud 29, añadir un cero a cada palabra para hacerlas de longitud 30, y luego usar eso como punto de partida. O bien, podría tomar un código de longitud 31, recortarle un cero y usarlo.

Una vez que tuvo estos puntos de partida "sembrados", ejecutó su búsqueda tabú de intercambio de bits. Imagina esta búsqueda como un juego de sillas musicales donde las sillas son las posiciones de los unos en las cadenas. El algoritmo intercambia bits, tratando de hacer que las cadenas sean más distintas. La parte "tabú" significa que el algoritmo mantiene una memoria de los movimientos que acaba de realizar y se niega a deshacerlos inmediatamente, obligándolo a explorar nuevo territorio en lugar de dar vueltas en círculos.

Los resultados: 124 nuevos descubrimientos

Al utilizar esta inteligente estrategia de siembra, Echols encontró 124 nuevas construcciones que superaron los récords conocidos anteriormente. Estos no son solo mejoras pequeñas; algunos son saltos masivos.

Por ejemplo:

Para un código de longitud 39 con restricciones específicas, el récord anterior era de 1,014 palabras. El nuevo método encontró 1,118 palabras. ¡Eso es una ganancia de 104!
Para la longitud 40, el récord saltó de 1,170 a 1,230.
Para la longitud 56, el número pasó de 2,414 a 2,477.

Estos números representan la cantidad máxima de mensajes únicos que ahora podemos garantizar que se envíen sin confusión para esos entornos específicos. El artículo no afirma que estos sean los máximos absolutos posibles (el verdadero límite matemático), pero demuestra que definitivamente podemos hacer mejor. Eleva el "límite inferior", lo que significa que sabemos con certeza que podemos meter al menos esta cantidad de elementos en la maleta.

Números de beso: Un efecto secundario sorprendente

Aquí es donde la historia se pone aún más interesante. El artículo también aborda un concepto llamado números de beso (kissing numbers). Imagina que tienes una pelota gigante en medio de una habitación. ¿Cuántas otras pelotas del mismo tamaño puedes empacar alrededor de ella de modo que todas toquen la pelota central sin solaparse entre sí? En el espacio 3D, la respuesta es 12. Pero en dimensiones superiores (como 32 o 33 dimensiones), la respuesta es mucho más difícil de encontrar.

Las matemáticas de estos números de beso están profundamente conectadas con los códigos de peso constante que encontró Echols. Debido a que mejoró los códigos para parámetros específicos (específicamente $A(n, 8, 8)$ ), automáticamente mejoró los límites inferiores para los números de beso en las dimensiones 32, 33, 34 y 37.

Por ejemplo, para la dimensión 32 ( $\tau_{32}$ ), la estimación anterior era que al menos 345,408 pelotas podían tocar la pelota central. Con los nuevos códigos, ese número salta a 346,432. Es un aumento de porcentaje pequeño, pero en el mundo de la geometría de alta dimensión, encontrar incluso una pelota más que quepa es una victoria significativa.

La conclusión

William Echols no solo encontró unos pocos códigos mejores; demostró que al ser inteligente sobre cómo iniciar tu búsqueda —usando "semillas" de conocimientos existentes en lugar de empezar a ciegas— puedes encontrar soluciones mucho mejores. El artículo demuestra que es posible lograr 124 mejoras específicas, y nos da un nuevo y más alto suelo para la cantidad de datos que podemos empaquetar de manera confiable en estas cadenas digitales. Es un recordatorio de que, a veces, la mejor manera de avanzar es pararse sobre los hombros de lo que ya sabemos, en lugar de intentar construir todo desde los cimientos.

Resumen Técnico: Nuevos Límites Inferiores para Códigos de Peso Constante mediante Búsqueda Tabú de Intercambio de Bits Sembrada

Planteamiento del Problema
El artículo aborda la construcción de códigos binarios de peso constante, definidos como conjuntos de palabras binarias de longitud $n$ donde cada palabra tiene un peso de Hamming fijo $w$ y una distancia de Hamming mínima de par en par $d$ . El objetivo central es determinar $A(n, d, w)$ , el tamaño máximo de dicho código. Aunque esfuerzos computacionales previos han establecido límites inferiores para diversos conjuntos de parámetros, encontrar límites más fuertes sigue siendo un problema de optimización combinatoria desafiante. Los enfoques de metaheurística existentes, incluyendo la búsqueda tabú estándar, históricamente han producido resultados más débiles que los límites conocidos o que otros algoritmos alternativos.

Metodología
El autor propone una modificación al algoritmo de búsqueda tabú de intercambio de bits de Rosin [8] mediante la introducción de una estrategia de inicialización sembrada (seeded initialization). En lugar de inicializar la búsqueda con palabras generadas aleatoriamente, el método realiza un "arranque en caliente" (warm-start) de la búsqueda utilizando palabras de códigos existentes con los mismos parámetros o parámetros adyacentes.

La metodología comprende dos técnicas de siembra principales:

Siembra Directa: Para un $(n, d, w)$ objetivo, el algoritmo utiliza un código $S$ existente con los mismos parámetros. Construye una biblioteca de conjuntos de inicialización mediante la adición de una palabra $v$ a $S$ que minimice la "penalización por déficit de distancia" agregada (la suma de las violaciones de la restricción de distancia mínima). Luego, se ejecuta la búsqueda tabú de intercambio de bits varias veces (hasta $4|E|$ , donde $E$ es el conjunto de palabras de déficit mínimo) utilizando muestras aleatorias de esta biblioteca. Crucialmente, se omite el mecanismo de reinicio para preservar la semilla proporcionada.
Siembra de Vecindad: Esta técnica aprovecha códigos de conjuntos de parámetros adyacentes para fortalecer los certificados.
- Alargamiento (Lengthening): Un certificado existente para $A(n-1, d, w)$ se extiende a una longitud $n$ .
- Acortamiento (Shortening): Un certificado para $A(n+1, d, w)$ se acorta eliminando una coordenada (corte de cero) para formar palabras de longitud $n$ .
  Dado que estos códigos intermedios suelen ser más pequeños que el tamaño objetivo $s$ , el algoritmo los completa con palabras elegidas aleatoriamente de penalización mínima. Aunque esto viola temporalmente la propiedad de distancia mínima, la subsiguiente búsqueda tabú de intercambio de bits repara el conjunto para convertirlo en un código válido.

La implementación evita la intensidad computacional de recomputar el conjunto de déficit mínimo $E$ después de cada inserción; en su lugar, computa $E$ inicialmente y realiza un muestreo uniforme con reemplazo. El algoritmo está diseñado para aplicarse sucesivamente a su propio resultado, variando los métodos de siembra entre iteraciones para escapar de los óptimos locales.

Contribuciones Clave y Resultados
La contribución principal de este trabajo es el descubrimiento de 124 nuevas construcciones que mejoran los límites inferiores existentes para $A(n, d, w)$ . Estos resultados son verificados contra la tabla en línea de Brouwer [2].

Códigos de Peso Constante: La Tabla 1 del artículo detalla las mejoras en una amplia gama de parámetros. Las ganancias notables incluyen:
- $A(39, 8, 7)$ mejorado de 1014 a 1118 (+104).
- $A(40, 8, 7)$ mejorado de 1170 a 1230 (+60).
- $A(56, 6, 5)$ mejorado de 2414 a 2477 (+63).
- También se observan mejoras significativas para parámetros que involucran $d=10$ y diversos pesos.
Números de Beso (Kissing Numbers): Como un corolario directo de los límites inferiores mejorados en $A(n, 8, 8)$ $A (n, 8, 8)$ para $n \in \{32, 33, 34, 37\}$ $n \in {32, 33, 34, 37}$ , el artículo deriva límites inferiores mejorados para los números de beso $\tau_n$ $τ_{n}$ . Específicamente:
- $\tau_{32}$ se mejora de 345,408 a 346,432 (+1,024).
- $\tau_{33}$ se mejora de 360,640 a 362,048 (+1,408).
- $\tau_{34}$ se mejora de 380,868 a 381,124 (+256).
- $\tau_{37}$ se mejora de 494,312 a 496,232 (+1,920).

Significancia y Reivindicaciones
El artículo sostiene que el enfoque de inicialización sembrada propuesto supera eficazmente las limitaciones de las implementaciones previas de búsqueda tabú, que anteriormente habían resultado en límites más débiles. Al utilizar información de conjuntos de parámetros equivalentes y vecinos, el método navega con éxito el espacio de búsqueda para encontrar límites inferiores más fuertes donde la inicialización aleatoria falló. El trabajo sirve como una demostración práctica de que el "arranque en caliente" de las metaheurísticas con semillas de alta calidad derivadas de problemas de codificación relacionados puede producir mejoras inmediatas y verificables en la teoría de la codificación combinatoria. El autor pone los códigos generados a disposición pública para facilitar su posterior verificación e investigación.

El rompecabezas del empaquetado y la semilla mágica

La estrategia "sembrada"

Los resultados: 124 nuevos descubrimientos

Números de beso: Un efecto secundario sorprendente

La conclusión

Más como este