Ejemplos de errores en los resultados de combinatoria computacional

Question

Me gustaría recopilar ejemplos de errores en los resultados numéricos publicados en combinatoria computacional: donde un resultado (típicamente un Contando de algunos objetos, o un cantidad extrema dentro de una gran clase de objetos), pero más tarde se descubrió que era incorrecta.

Mi motivación aquí es comprender mejor el alcance y, sobre todo, la tipos de errores que se producen, y comprender cuáles serían buenos métodos para evitarlos. Personalmente he visto algunos ejemplos, pero tengo entendido que tales errores son, de hecho, sorprendentemente raros. (Cabe preguntarse si esto se debe a que estos errores ocurren raramente, o a que se advierten raramente). Lo que hace que estos errores sean desagradables es que pueden ser muy difíciles de advertir.

Algunas aclaraciones sobre lo que busco:

1. Debería ser un resultado definitivamente erróneo, no sólo un descuido en un definición o algo así (por ejemplo, olvidarse de decir "oh, queremos decir no vacío").

2. Al parecer, el resultado procede de una gran cantidad de cálculos (vamos digamos que al menos 1 hora de cpu, pero no soy particular), y de la propia publicación, es es casi imposible que el lector se dé cuenta del error, sin por ejemplo, volver a hacer los cálculos.

3. Lo publicado resultado debe ser errónea, no sólo algunos detalles corregibles en su demostración o en los cálculos que condujeron al resultado.

4. La causa del error puede estar en el hardware, error en algoritmo, error de programación, error humano al procesar los resultados, o incluso desconocida. Por favor, mencione si la causa es conocida.

5. Tanto el resultado erróneo como su corrección se recogieron en una publicación científica (libro, revista, actas de congresos; incluso el manuscrito arXiv es válido si cree que es digno de crédito). Esto excluye, por ejemplo, las correcciones de entradas OEIS [principalmente porque son relativamente comunes, y porque su documentación es a menudo bastante escueta, como en "a(4) corregido por mí, eso es todo"].

6. No busco mejoras de límites inferiores, refutaciones de conjeturas, etc., sino correcciones de hechos errores.

Un ejemplo para aclarar lo que busco:

Heitzig y Reinhold (2002) contaron retículos no etiquetados de hasta 18 elementos, y escribieron: "Estamos seguros de que los valores de Koda para $l(12)$ y $l(13)$ están equivocados". Koda (1992) contó 262775 y 2018442, H&R 262776 y 2018305. No se indica la causa de la discrepancia.

Referencia: Heitzig, Jobst; Reinhold, Jürgen , Recuento de redes finitas. Álgebra Univers. 48, nº 1, 43-53 (2002). ZBL1058.05002 .

Para contrastar, aquí tienes otras preguntas de MO sobre errores y cálculo:

• ¿Cómo podemos estar seguros de que los resultados que dependen en gran medida de cálculos exhaustivos son correctos?
• Errores de álgebra computacional
• ¿Cómo puedo corregir un error publicado por alguien?
• Diplomacia a la hora de notificar errores

Solicito que esto sea CW porque obviamente no hay una única respuesta correcta.

Answer 1

(1) En este documento (publicado J. Combinatorial Designs, 15 (2007) 98-119), en la sección de historia a partir de la página 3, citamos muchos errores publicados en el recuento de cuadrados latinos y objetos relacionados. Algunos, pero no todos, se produjeron antes de la era informática, pero requerían un importante cálculo manual.

(2) El número de giros cerrados del caballo en un tablero de ajedrez estándar se publicó por primera vez ici . La respuesta está en el título del artículo, pero desgraciadamente es incorrecta. Para más información, véase el comentario; los autores replicaron posteriormente mi respuesta, por lo que es de suponer que es correcta.

Por supuesto, los errores de programación y los errores administrativos (por ejemplo, juntar incorrectamente los resultados de varias ejecuciones informáticas) son la principal causa de los errores publicados, pero también se producen errores de hardware. He tenido ordenadores individuales en grupos de ordenadores "idénticos" que regularmente daban respuestas que parecían perfectamente razonables pero que eran erróneas.

En los primeros tiempos de la memoria de silicio, el error más común se debía a las partículas alfa procedentes de las impurezas del silicio. Después, a medida que avanzaba la purificación del silicio, los rayos cósmicos se convirtieron en el principal factor de error de las memorias. Ahora creo que el principal problema es que los componentes son tan diminutos que el ruido aleatorio y la inducción cruzada son clave. Además, las memorias con corrección de errores son más caras que las que no la tienen, por lo que normalmente sólo las tienen los ordenadores de gama alta.

Answer 2

Hace unos 20 años, se informó de que el número de grupos de orden 1024 era de 49487365422 en "Un proyecto del milenio: la construcción de pequeños grupos" Esta cifra se repite en otras fuentes. Recientemente, Burrell demostró que el número real es 49487367289 en "Sobre el número de grupos de orden 1024" . La discrepancia se explica en este último documento.

Answer 3

(1) Número de entramados Bravais n-dimensionales: secuencia correcta aquí https://oeis.org/A256413 Secuencia incorrecta https://oeis.org/A004030

Del artículo Opgenorth, J; Plesken, W; Schulz, T, Crystallographic Algorithms and Tables, Acta Crystallogr. A, 54 (1998), 517-531: Existen $1, 5, 14, 64, 189, 841^\dagger$ clases de grado $1, 2, 3, 4, 5, 6$ respectivamente; nota a pie de página: $^\dagger$ La publicación original (Plesken & Hanrath, 1984) enumera $826$ clases. Al preparar las tablas de inclusión de los grupos Bravais, [descubrimos un error].

Errores en el software presentado en ese artículo dieron lugar posteriormente a errores en algunos otros artículos publicados, que fueron citados en las Tablas Internacionales de Cristalografía. Sin embargo, los errores se corrigieron en el software pero no en los artículos publicados, por lo que esto no cuenta.

(2) https://oeis.org/A001393 Series de alta temperatura para la energía libre de Ising de espín-1/2 en una red cúbica simple tridimensional. (Puede definirse de forma combinatoria, como el número de algún tipo de grafos en la red). El artículo G. S. Rushbrooke y J. Eve, High-temperature Ising partition function and related noncrossing polygons for the simple cubic lattice, J. Math. Physics 3 (1962) 185-189, da un séptimo término incorrecto, que ha sido corregido en publicaciones posteriores. Existen otros ejemplos de la misma área.

(3) https://oeis.org/A191783 Números k tales que la k-esfera topológica tiene una única estructura diferenciable hasta el difeomorfismo. (El ejemplo más no combinatorio, pero aún así: cuentan estructuras diferenciables).

El hecho de que $56$ era desconocido cuando se publicó el conocido artículo John W. Milnor, Differential Topology Forty-six Years Later, Notices Amer. Math. Soc. 58 (2011), 804-809 (en el que se cita un trabajo anterior). Esta omisión se corrigió en un trabajo posterior, véase Theorem 1.14 de Guozhen Wang y Zhouli Xu, The triviality of the 61-stem in the stable homotopy groups of spheres, Annals of Mathematics, 186 (2017), 501-580.

(4) https://oeis.org/A105232 Número de politopos n-dimensionales con vértices de {0,1}^n hasta equivalencia combinatoria. En el artículo de revisión Chuanming Zong, What is known about unit cubes, Bull. Amer. Math. Soc., 42 (2005), 181-211, da que el cuarto término es igual a $172$ . Se desconoce el origen de este número (posiblemente no sea resultado de ningún cálculo). De todos modos, la base de datos polyDB da un valor diferente $192$ que se cita en la tesis de Rafael Gillmann, 0/1-Polytopes: Typical and Extremal Properties, sin decir explícitamente que esto contradice a Zong.

Hay otro artículo en coautoría con Zong (investigación, no revisión esta vez), Heling Liu y Chuanming Zong, On the classification of convex lattice polytopes, Adv. Geom., 11 (2011), 711-729, que da un número incorrecto de diferentes clases de politopos lattice convexos bidimensionales que tienen volumen n/2 hasta equivalencia unimodular ( https://oeis.org/A187015 ) para $n=7$ Esto no se corrige explícitamente en publicaciones posteriores, pero se puede deducir el número correcto a partir del conjunto de datos que complementa un artículo de Balletti, y de todos modos este error se puede descubrir a mano, así que esto no cuenta. En realidad, me sorprende que se haya cometido un error tan fácil de descubrir, por lo que sigo dudando de haberlo entendido todo correctamente en este caso.

(5) https://oeis.org/A071880 Número de tipos combinatorios de paralelóedros n-dimensionales.

Del artículo Mathieu Dutour Sikiric, Alexey Garber, Achill Schürmann, Clara Waldmann, The complete classification of five-dimensional Dirichlet-Voronoi polyhedra of translational lattices, Acta Crystallographica A72 (2016), 673-683: Encontramos en total 110244 tipos combinatorios [5-dimensionales] diferentes y superamos así la clasificación parcial según esquemas de subordinación obtenida previamente por [Eng00]. <...> deriva 103769 "tipos combinatorios". Estos tipos no son los verdaderos tipos combinatorios <...>.

(6) No estoy seguro de si las erratas cuentan; sin embargo, no estoy seguro de que sean realmente erratas en este caso. Del artículo Jorge Mago, Anders Schreiber, Marcus Spradlin y Anastasia Volovich, Yangian Invariants and Cluster Adjacency in N=4 Yang-Mills, J. High Energ. Phys. 2019, 99 (relacionado con https://oeis.org/A227205 ): El número de clases cíclicas de racionales N $^k$ Invariantes Yangianas MHV con dependencia no trivial de $n$ torsores de momento se tabuló para varios $k$ y $n$ en la tabla 3 de [9]. Registramos estos números aquí, corrigiendo errores tipográficos en el $(3, 15)$ y $(4, 20)$ entradas. (Sin embargo, dicho artículo [9] sólo se publicó en arXiv).

Answer 4

Los números catalanes tienen una famosa generalización asociada a los grupos de reflexión irreducibles finitos. Según parece, la fórmula $$\operatorname{Catalan}(W)=\prod_{i=1}^n \frac{d_i+h}{d_i}$$ apareció por primera vez en el artículo "Noncrossing partitions for classical reflection groups" (Discrete Math., 1996 ) de Vic Reiner. Toma, $d_1,\dots,d_n$ son los grados invariantes y $h$ es el número de Coxeter.

Creo que la primera aparición de estos números (aunque todavía no con una fórmula uniforme) en tipos generales simplemente enlazados fue en el artículo "Quotients of representation-finite algebras" (Communications Alg., 1987 ) por Gabriel y J.A. de la Peña como el número de "subconjuntos discretos" del álgebra de caminos del carcaj de Dynkin. Ahora se sabe que estos subconjuntos discretos se cuentan por los números catalanes ( referencia que falta por ahora ). Contaron los subconjuntos discretos como los números catalanes

• de tipo $A_n$ correctamente en la página 292 como $\frac{1}{n+2}\binom{2n+2}{n+1}$ ,
• de tipo $D_{n+1}$ correctamente en la página 293 como una fórmula más larga que podría simplificarse en $\binom{2n+2}{n+1}-\binom{2n}{n}$ ,
• de tipos $E_6$ y $E_7$ incorrectamente en la página 294 como $468$ sur $E_6$ y $4159$ sur $E_7$ . Los recuentos correctos habrían sido $833$ en tipo $E_6$ y $4160$ en tipo $E_7$ .
• de tipo $E_8$ correctamente en la página 294 como $25080$ .

Answer 5

El hilo ¿Resultados matemáticos ampliamente aceptados que más tarde se demostraron erróneos? contiene ejemplos combinatorios, por ejemplo

• el par Perko en la enumeración de nudos [ Perko, Kenneth A. jun. , Sobre la clasificación de los nudos Proc. Am. Math. Soc. 45, 262-266 (1974). ZBL0256.55004 .]
• la clasificación de todos los pentágonos convexos que embaldosan el plano [ Kershner, R. B. , Sobre la pavimentación del plano , Am. Math. Mon. 75, 839-844 (1968). ZBL0165.23801 .]
• La afirmación errónea de Frolov de que no existe una serie de 7 números Impares distintos, del 1 al 49, con suma 175 y suma de cuadrados 5775 que utilizó demostrando la no existencia de cuadrados bimágicos de 7º orden [ Frolov, Michel , Igualdades de segundo y tercer grado Bull. Soc. Math. Fr. 20, 69-84 (1892). ZBL24.0176.01 .]
• el número de recorridos del caballero.

En [ Grünbaum, Branko , Un error que perdura Elem. Math. 64, n.º 3, 89-101 (2009). ZBL1176.52002 )]):

• el número de colecciones de 12 líneas y 12 puntos, cada una incidente con tres de las otras
• la enumeración de los politopos simples de 4 dimensiones con ocho facetas
• el número de inclinaciones uniformes del espacio tridimensional.

Encontrará más ejemplos en erratas/corrigenda/retracciones publicadas sobre el terreno aunque es probable que la mayoría no se deban a errores de cálculo. Por ejemplo [ Lam, Clement; Tonchev, Vladimir D. , Clasificación de los diseños afines resolubles (2)-((27,9,4)) J. Stat. Plann. Inference 56, nº 2, 187-202 (1996); corrigendum ibid. 86, 277-278 (2000). ZBL0874.05009 ] contenía una tabla errónea con cálculos de diseño, como se explica en https://doi.org/10.1016/S0378-3758(99)00055-5 .

P.D. Acabo de ver que la pregunta se ha modificado entretanto; ahora está claro que no todos los ejemplos anteriores satisfacen todos los criterios dados. De hecho, si nos fijamos en el conjunto de artículos combinatorios con correcciones/retractaciones/erratas/corrigenda que incluyan software sólo obtenemos 16 resultados, la mayoría de ellos con correcciones no computacionales. Esto corrobora la impresión de que estos casos son relativamente raros. El único ejemplo que puede cumplir todos los criterios entre ellos parece ser [ Cormode, Graham; Jowhari, Hossein , Corrección de errores de: "Una segunda mirada al recuento de triángulos en flujos de grafos" Theor. Comput. Sci. 683, 31-32 (2017). ZBL1370.68121 .], donde el algoritmo necesitó una corrección sustancial que también condujo a un resultado significativamente modificado.