🔢 mathematics

A Census of New Snake-in-the-Box Records

Este artículo presenta nuevas rutas inducidas más largas (serpientes) en grafos hipercubo para dimensiones 9 a 13, mejorando así los límites inferiores conocidos para el problema de la serpiente en la caja y proporcionando un conjunto de datos de estas rutas de longitud récord verificable por computadora.

Autores originales: Paul Orland, Lucas Fagan, Michele Tarquini, Davide Passaro, Maksymilian Manko, Elli Heyes, Angus Gruen, Giorgi Butbaia, Justin Tan, Sergei Gukov

Publicado 2026-07-17

📖 3 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Paul Orland, Lucas Fagan, Michele Tarquini, Davide Passaro, Maksymilian Manko, Elli Heyes, Angus Gruen, Giorgi Butbaia, Justin Tan, Sergei Gukov

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 intentas navegar por un laberinto gigante y multidimensional hecho enteramente de interruptores de luz. En este mundo, cada habitación es una combinación única de interruptores que están "encendidos" o "apagados". Para moverte de una habitación a la siguiente, solo puedes cambiar exactamente un interruptero. Este es el "hipercubo", una forma que existe en las matemáticas pero que se siente como un laberinto digital. Ahora, imagina que quieres recorrer tantas habitaciones como sea posible sin entrar nunca en una habitación en la que ya hayas estado, y con una regla especial: no puedes tomar un atajo. Si estás en la Habitación A y la Habitación B, y ambas están conectadas a la Habitación C, no puedes saltar de A a B solo porque sean vecinas; debes seguir el camino que iniciaste. Este tipo específico de recorrido se llama "serpiente".

¿Por qué a alguien le importan estas serpientes digitales? Resulta que encontrar la serpiente más larga posible en estos laberintos es crucial para construir mejores códigos de detección de errores. Piensa en estos códigos como las redes de seguridad que evitan que tus mensajes de texto, señales de satélite y datos informáticos se distorsionen cuando viajan a través del universo ruidoso. Cuanto más larga sea la serpiente, más robusto será el código. Durante décadas, los matemáticos han estado compitiendo para encontrar la serpiente más larga posible en laberintos de diferentes tamaños, pero para los laberintos más grandes y complejos, el récord se ha quedado estancado durante mucho tiempo.

Este artículo es una actualización importante de esa carrera. Los autores, un equipo de investigadores, han utilizado potentes ordenadores para encontrar nuevas y más largas serpientes en laberintos de dimensiones 9 a 13. Antes de este trabajo, las mejores serpientes conocidas en estas dimensiones eran las más largas que nadie había visto jamás. El equipo no solo encontró una o dos rutas; encontraron serpientes significativamente más largas, rompiendo los récords anteriores en cada una de las dimensiones que probaron. Por ejemplo, en un laberinto de 9 dimensiones, encontraron una serpiente de 191 pasos, superando el antiguo récord de 190. En el masivo laberinto de 13 dimensiones, llevaron la longitud a 2,922 pasos, sobrepasando el mejor resultado anterior de 2,900.

Los investigadores no se detuvieron solo en encontrar un camino; actuaron como arqueólogos digitales, desenterrando familias enteras de estas serpientes que rompen récords. En el caso de 9 dimensiones, descubrieron 1,311 formas distintas de construir una serpiente de esa nueva longitud récord. También aplicaron sus métodos para encontrar "espirales" más largas (que son como serpientes que regresan al inicio) y "espirales simétricas" (donde la segunda mitad del bucle es un reflejo de la primera). Sus resultados muestran que los límites anteriores no eran el verdadero techo; todavía hay espacio para crecer. Todas estas nuevas y más largas rutas han sido guardadas en un conjunto de datos público, permitiendo que cualquiera verifique las matemáticas o utilice estas nuevas y más largas rutas para construir incluso mejores códigos de detección de errores. Aunque no han resuelto el rompecabezas para todas las dimensiones posibles, han extendido con éxito los límites conocidos de lo que es posible en el laberinto digital, demostrando que con suficiente potencia de cálculo, todavía podemos encontrar nuevas y más largas formas de caminar a través de la oscuridad.

Resumen Técnico: Un Censo de Nuevos Récords de Snake-in-the-Box

Definición del Problema
El artículo aborda el problema "snake-in-the-box", formulado originalmente por Kautz en 1958 en el contexto de los códigos de detección de errores. El problema busca el camino inducido (sin cuerdas) más largo, denominado "snake" (serpiente), dentro del grafo hipercubo $Q_n$ . En $Q_n$ , los vértices representan cadenas binarias de longitud $n$ , y las aristas conectan cadenas que difieren en exactamente una coordenada. Una serpiente se define como una secuencia de vértices distintos donde los vértices consecutivos son adyacentes, y ningún par de vértices no consecutivos es adyacente. La longitud máxima de dicho camino se denota como $a(n)$ .

El artículo también considera estructuras relacionadas: "coils" (espirales o bobinas, que son ciclos inducidos en $Q_n$ ) con longitud máxima $b(n)$ , y "symmetric coils" (espirales simétricas, que son espirales donde la segunda mitad del ciclo refleja a la primera mediante una operación XOR fija) con longitud máxima $c(n)$ . Aunque los valores exactos para $a(n)$ y $b(n)$ se conocen para dimensiones $n \le 8$ , y $c(n)$ se conoce para $n \le 7$ , el problema permanece sin resolver para $n \ge 9$ (y $n \ge 8$ para espirales simétricas), donde solo se han establecido límites inferiores mediante diversas búsquedas computacionales.

Metodología y Enfoque
Los autores emplean esfuerzos computacionales sostenidos para buscar serpientes, espirales y espirales simétricas más largas en las dimensiones 9 a 13. El artículo no detalla una arquitectura algorítmica novedosa específica en el texto proporcionado, pero posiciona su trabajo como un avance sobre métodos previos, que han incluido algoritmos genéticos, búsquedas evolutivas basadas en poblaciones, construcciones basadas en permutaciones y búsquedas de árboles de Monte Carlo.

El enfoque de los autores se centra en generar y verificar caminos de longitud récord. Utilizan una notación estándar donde una serpiente se representa mediante una secuencia de transición: la lista ordenada de índices de coordenadas invertidas a lo largo del camino. Para asegurar la validez de sus hallazgos, los autores proporcionan un conjunto de datos verificable por computadora. También realizan un censo del espacio de soluciones, contando el número de serpientes inequivalentes encontradas en longitudes récord. La equivalencia se determina por las simetrías de $Q_n$ , que incluyen $n!$ permutaciones de coordenadas, $2^n$ traslaciones (XOR) y la reversión del camino.

Contribuciones Clave y Resultados
La contribución principal del artículo es el establecimiento de nuevos límites inferiores para $a(n)$ , $b(n)$ y $c(n)$ en las dimensiones 9 a 13, superando todos los récords conocidos anteriormente.

Longitudes de Serpientes ( $a(n)$ ): Los autores presentan serpientes más largas que las mejores conocidas previamente en cada dimensión de la 9 a la 13.
- $n=9$ : Una nueva longitud de 191 (mejorando la anterior de 190). Los autores identificaron 1,311 serpientes inequivalentes de esta longitud.
- $n=10$ : Una nueva longitud de 379 (mejorando la anterior de 376).
- $n=11$ : Una nueva longitud de 746 (mejorando la anterior de 737).
- $n=12$ : Una nueva longitud de 1,476 (mejorando la anterior de 1,465).
- $n=13$ : Una nueva longitud de 2,922 (mejorando la anterior de 2,900).
- Las mejoras oscilan entre +1 y +22 respecto a los récords anteriores.
Longitudes de Espirales ( $b(n)$ ): El artículo reporta límites inferiores mejorados para las espirales más largas en las dimensiones 9, 10 y 11, con nuevas longitudes de 192, 374 y 732, respectivamente.
Longitudes de Espirales Simétricas ( $c(n)$ ): Se proporcionan límites inferiores mejorados para las dimensiones 10 y 11, con longitudes de 370 y 726.

Los autores proporcionan un ejemplo concreto de una serpiente de longitud 191 en $Q_9$ , listando su secuencia de transición completa. Observan que, entre millones de serpientes de longitud 191 muestreadas, se encontraron exactamente 131 clases de simetría para $n=9$ , lo que lleva a la conjetura de que no existen otras clases, aunque no realizan tal afirmación de completitud para $n \ge 10$ .

Significancia y Reivindicaciones
El artículo reclama significancia principalmente a través del avance empírico de los límites conocidos para el problema snake-in-the-box. Al proporcionar serpientes que son estrictamente más largas que cualquier otra conocida previamente en las dimensiones 9 a 13, los autores han estrechado los límites inferiores de la longitud máxima posible de caminos inducidos en hipercubos.

El trabajo sirve como un "censo" de estos nuevos récords, ofreciendo un conjunto de datos exhaustivo que incluye las secuencias de transición específicas para todas las serpientes de longitud récord encontradas. Este conjunto de datos se pone a disposición pública en un formato verificable por computadora, permitiendo la verificación independiente de los resultados. Los autores enmarcan su trabajo como una continuación de la línea computacional establecida por investigadores previos (como Ace, Echols, Meyerson y otros), empujando la frontera de lo que es computacionalmente alcanzable en este problema de optimización combinatoria sin pretender haber resuelto el problema para estas dimensiones o haber probado la optimalidad de sus nuevos límites.

Más como este