Examples of errors in computational combinatorics results

Question

I would like to collect examples of errors in published numerical results in computational combinatorics: where a result (typically a counting of some objects, or an extremal quantity within some large class of objects) was published, but later found to be incorrect.

My motivation here is to better understand the extent, and especially, the kinds of errors that happen, and to understand what would be good methods to avoid them. Personally I have seen a few examples, but my understanding is that such errors are in fact surprisingly rare. (One might ask whether this is because these errors happen rarely, or because they are noticed rarely.) What makes such errors nasty is that they may be very difficult to notice.

Some clarifications of what I am after:

1. It should be a definitely erroneous result, not just an oversight in a definition or something like that (e.g. forgetting to say "oh, we mean nonempty").

2. The result apparently comes from a substantial amount of computation (let's say at least 1 cpu hour, but I am not particular), and from the publication itself, it is well nigh impossible for the reader to notice the error, without e.g. doing the computations again.

3. The published result itself should be erroneous, not just some correctable details in its proof or the computations that led to the result.

4. The cause of the error could be in hardware, mistake in algorithm, programming error, human error in processing the results, or even unknown. Please mention if the cause is known.

5. The erroneous result and its correction were both stated in a scientific publication (book, journal, conference proceedings; even arXiv manuscript OK if you think that it is creditable). This excludes e.g. corrections to OEIS entries [mainly because they are relatively common, and because their documentation is often quite terse, as in "a(4) corrected by me, that's it"].

6. I'm not looking for improvements of lower bounds, disproofs of conjectures etc. but corrections of factual errors.

An example to clarify what I am seeking:

Heitzig and Reinhold (2002) counted unlabeled lattices of up to 18 elements, and wrote: "We are sure that Koda’s values for $l(12)$ and $l(13)$ are wrong." Koda (1992) counted 262775 and 2018442, H&R counted 262776 and 2018305. There is no indication of the cause of the discrepancy.

Reference: Heitzig, Jobst; Reinhold, Jürgen, Counting finite lattices., Algebra Univers. 48, No. 1, 43-53 (2002). ZBL1058.05002.

For contrast, here are some other MO questions about errors and computation:

• How can we be sure that results that rely heavily on extensive computations are correct?
• Computer algebra errors
• How do I fix someone's published error?
• Diplomacy when reporting errors

I am requesting this to be CW because obviously there is not a single correct answer.

Answer 1

(1) In this paper (published J. Combinatorial Designs, 15 (2007) 98-119), in the history section starting page 3, we cite many published errors in counting Latin squares and related objects. Some, but not all, were before the computer age but required substantial hand computation.

(2) The number of closed knight's tours on a standard chessboard was first published here. The answer is in the title of the paper, but is unfortunately incorrect. See the comment there for more information — the authors later replicated my answer so it is presumably correct.

Of course programming errors and clerical errors (e.g. putting the results of multiple computer runs together incorrectly) are the main cause of published errors, but hardware errors also occur. I've had individual computers in clusters of "identical" computers that regularly gave answers that looked perfectly reasonable but were wrong.

In the early days of silicon memory, the most common error was due to alpha particles from impurities in the silicon. Then, as silicon purification became more advanced, cosmic rays became the major factor for memory errors. Now I think that the main problem is that the components are so tiny that random noise and cross-induction are key. Also, memory with error-correction is more expensive than memory without so usually only high-end computers have it.

Answer 2

About 20 years ago, the number of groups of order 1024 was reported to be 49487365422 in "A millennium project: constructing small groups", and this number was repeated in other sources. Recently, Burrell showed that the actual number is 49487367289 in "On the number of groups of order 1024". The discrepancy is explained in the latter paper.

Answer 3

(1) Number of n-dimensional Bravais lattices: correct sequence here https://oeis.org/A256413, incorrect sequence here https://oeis.org/A004030

From the paper Opgenorth, J; Plesken, W; Schulz, T, Crystallographic Algorithms and Tables, Acta Crystallogr. A, 54 (1998), 517-531: There are $1, 5, 14, 64, 189, 841^\dagger$ classes of degree $1, 2, 3, 4, 5, 6$, respectively; footnote: $^\dagger$ The original publication (Plesken & Hanrath, 1984) lists $826$ classes. In preparing the inclusion tables for the Bravais groups, we [discovered an error].

Bugs in the software presented in that paper later resulted in errors in some other published papers, which were quoted in the International Tables of Crystallography. However, the errors were corrected in the software but not in the published papers, so this doesn't count.

(2) https://oeis.org/A001393 High temperature series for spin-1/2 Ising free energy on 3-dimensional simple cubic lattice. (Can be defined in the combinatorial way, as the number of some kind of graphs in the lattice.) The paper G. S. Rushbrooke and J. Eve, High-temperature Ising partition function and related noncrossing polygons for the simple cubic lattice, J. Math. Physics 3 (1962) 185-189, gives incorrect 7th term, which has been corrected by later publications. There are other examples from the same area.

(3) https://oeis.org/A191783 Numbers k such that the topological k-sphere has a unique differentiable structure up to diffeomorphism. (The most non-combinatorial example, but still: they count differentiable structures.)

The fact that $56$ is a term of this list was unknown when the well-known paper John W. Milnor, Differential Topology Forty-six Years Later, Notices Amer. Math. Soc. 58 (2011), 804-809 (citing earlier work) was published. This omission was corrected in later work, see Theorem 1.14 from Guozhen Wang and 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 Number of n-dimensional polytopes with vertices from {0,1}^n up to combinatorial equivalence. In the review paper Chuanming Zong, What is known about unit cubes, Bull. Amer. Math. Soc., 42 (2005), 181-211, gives the 4th term to be equal to $172$. The origin of this number is unknown (possibly not a result of any calculation). Anyway, the database polyDB gives different value $192$, which is quoted in Rafael Gillmann' thesis, 0/1-Polytopes: Typical and Extremal Properties, without explicitly saying that this contradicts Zong.

There is another paper coauthored by Zong (research, not review this time), Heling Liu and Chuanming Zong, On the classification of convex lattice polytopes, Adv. Geom., 11 (2011), 711-729, which gives incorrect number of different classes of 2-dimensional convex lattice polytopes having volume n/2 up to unimodular equivalence (https://oeis.org/A187015) for $n=7$; this is not explicitly corrected in later publications, but one can deduce the correct number from the dataset supplementing a paper by Balletti, and anyway this error can be discovered by hand, so this doesn't count. Actually, I am surprised that such an easy-discoverable error has been made, so I still doubt if I understood everything correctly in this case.

(5) https://oeis.org/A071880 Number of combinatorial types of n-dimensional parallelohedra.

From the paper Mathieu Dutour Sikirić, 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: We find in total 110244 different [5-dimensional] combinatorial types and hereby go beyond the partial classification according to subordination schemes previously obtained by [Eng00]. <...> he derives 103769 “combinatorial types”. These types are not the true combinatorial types <...>

(6) Not sure if typos count; however, not sure if they are really typos in this case. From the paper Jorge Mago, Anders Schreiber, Marcus Spradlin and Anastasia Volovich, Yangian Invariants and Cluster Adjacency in N=4 Yang-Mills, J. High Energ. Phys. 2019, 99 (related to https://oeis.org/A227205): The number of cyclic classes of rational N$^k$MHV Yangian invariants with nontrivial dependence on $n$ momentum twistors was tabulated for various $k$ and $n$ in table 3 of [9]. We record these numbers here, correcting typos in the $(3, 15)$ and $(4, 20)$ entries. (The said paper [9] was only posted on arXiv though.)

Answer 4

The Catalan numbers have a famous generalization associated to finite irreducible reflection groups. Afaik, the formula $$\operatorname{Catalan}(W)=\prod_{i=1}^n \frac{d_i+h}{d_i}$$ appeared first in the paper "Noncrossing partitions for classical reflection groups" (Discrete Math., 1996) by Vic Reiner. Here, $d_1,\dots,d_n$ are the invariant degrees and $h$ is the Coxeter number.

I believe the first appearance of these numbers (though not yet with a uniform formula) in general simply-laced types was in the paper "Quotients of representation-finite algebras" (Communications Alg., 1987) by Gabriel and J.A. de la Peña as the number of "discrete subsets" of the path algebra of the Dynkin quiver. These discrete subsets are now known to be counted by the Catalan numbers (reference missing for now). They counted the discrete subsets as the Catalan numbers

• of type $A_n$ correctly on page 292 as $\frac{1}{n+2}\binom{2n+2}{n+1}$,
• of type $D_{n+1}$ correctly on page 293 as some longer formula that could be simplyfied to $\binom{2n+2}{n+1}-\binom{2n}{n}$,
• of types $E_6$ and $E_7$ incorrectly on page 294 as $468$ in $E_6$ and $4159$ in $E_7$. The correct counts would have been $833$ in type $E_6$ and $4160$ in type $E_7$.
• of type $E_8$ correctly on page 294 as $25080$.

Answer 5

The thread Widely accepted mathematical results that were later shown to be wrong? contains combinatorial examples, for example

• the Perko pair in knot enumeration [Perko, Kenneth A. jun., On the classification of knots, Proc. Am. Math. Soc. 45, 262-266 (1974). ZBL0256.55004.]
• the classification of all convex pentagons that tile the plane [Kershner, R. B., On paving the plane, Am. Math. Mon. 75, 839-844 (1968). ZBL0165.23801.]
• Frolov's wrong claim that there is no series of 7 distinct odd numbers, from 1 to 49, with sum 175 and sum of squares 5775 he used proving the non-existence of 7th-order bimagic squares [Frolov, Michel, Equalities of the second and third degree, Bull. Soc. Math. Fr. 20, 69-84 (1892). ZBL24.0176.01.]
• the number of knight's tours.

The following three and more examples are given in [Grünbaum, Branko, An enduring error, Elem. Math. 64, No. 3, 89-101 (2009). ZBL1176.52002)]):

• the number of of collections of 12 lines and 12 points, each incident with three of the others
• the enumeration of 4-dimensional simple polytopes with eight facets
• the number of uniform tilings of three-dimensional space.

More examples might be found by checking published errata/corrigenda/retractions in the field, though most are likely not due to computational errors. For example [Lam, Clement; Tonchev, Vladimir D., Classification of affine resolvable (2)-((27,9,4)) designs, J. Stat. Plann. Inference 56, No. 2, 187-202 (1996); corrigendum ibid. 86, 277-278 (2000). ZBL0874.05009] contained a wrong table with design computations, as explained in https://doi.org/10.1016/S0378-3758(99)00055-5.

P.S. Just saw that the question has been modified inbetween; now it's clear that not all examples above satisfy all given criteria. In fact, if we look into the set of combinatorial papers with corrections/retractions/errata/corrigenda that involve software, we obtain only 16 results, most of which have non-computational corrections. This supports the impression that these cases are relatively rare. The only example that may fulfill all criteria among them seems to be [Cormode, Graham; Jowhari, Hossein, Corrigendum to: “A second look at counting triangles in graph streams”, Theor. Comput. Sci. 683, 31-32 (2017). ZBL1370.68121.], where the algorithm needed a substantial correction which also led to a significantly modified result.

Answer 6

The Ramsey number survey by Radziszowski (Small Ramsey Numbers, revision 16 ) has a couple of footnotes mentioning incorrect values. Unfortunately there is not much information on the cause of or correction of such errors.

On page 6:

(h)
The claim that $R(5, 5) = 50$ posted on the web [Stone] is in error, and despite being shown to be incorrect more than once, this value is still being cited by some authors. The bound $R(3, 13) ≥ 60$ [XieZ] cited in the 1995 version of this survey was shown to be incorrect in [Piw1]. Another incorrect construction for $R(3, 10) ≥ 41$ was described in [DuHu].

On page 25, in the "Cycles versus books" section:

(b)
$R(C_{4},B_{12}) = 21$ [Tse1], $R(C_{4},B_{13}) = 22$, $R(C_{4},B_{14}) = 24$ [Tse2].
$R(C_{4},B_{8}) = 17$ [Tse2] (it was reported incorrectly in [FRS7] to be 16)

---

The [Piw1] reference is:

Piwakowski, Applying Tabu Search to Determine New Ramsey Graphs, Electronic Journal of Combinatorics, http://www.combinatorics.org, #R6, 3(1) (1996), 4 pages.

This paper says (note: [11] in this paper is [XieZ] mentioned by Radziszowski):

Finally, let us note that a better lower bound $R(3,13) ≥ 60$ was claimed in [11]. Unfortunately, the cyclic graph $C_{59}(1,3,5,7,16,25)$ described in that paper as a $(3,13;59)$-Rg contains a number of indepdendent sets of size 13, for example $\{0,2,6,10,14,20,24,28,32,38,42,46,50\}$.

Answer 7

It is well known that the Appel–Haken–Koch proof of the four-color theorem was controversial because of its use of an electronic computer, but it is not as well known that the original proof had many minor errors. Appel and Haken have described their paper as follows.

This leaves the reader to face 50 pages containing text and diagrams, 85 pages filled with almost 2500 additional diagrams, and 400 microfiche pages that contain further diagrams and thousands of individual verifications of claims made in the 24 lemmas in the main sections of text.

As explained in Appel and Haken's 1989 book, Every Planar Map is Four Colorable, in 1981, Ulrich Schmidt wrote a Diplom Thesis at the Technische Hochschule Aachen, which gave a report of his efforts to verify the published proof of the four-color theorem. Most of this work involved going through the vast catalog of diagrams and checking their correctness. In the available time before his thesis was due, Schmidt was able to check only about 40% of the diagrams. In the course of doing so, he found "fourteen errors of degree 1 and one of degree 3." "Degree" here refers to the degree of seriousness, with the degree 3 error being the most serious; Appel and Haken say that the repair of a degree 3 error "usually takes a few days." They devote a page of their book to repairing the degree 3 error found by Schmidt.

The book goes on to describe various other verification efforts, and errors that were uncovered in the process. It doesn't seem that the entire proof has been systematically verified (e.g., Robertson, Seymour, Sanders, and Thomas explicitly say that they produced their own proof, and didn't verify the correctness of the original proof), so there could be one or more degree 3 errors remaining, not to mention less serious errors.

Answer 8

• A regular map of type $\{ 3, 6 \}$ is one for which every vertex has degree $6$ and every face has degree $3$. Define $\chi(v)$ to be the number of regular maps (up to isomorphism) of type $\{ 3, 6 \}$ on the torus, with $v$ vertices.

  In [1], Altshuler lists the values of $\chi(v)$ for $1 \leq v \leq 24$ in Table 1. In particular, the value of $\chi(16)$ is given to be $16$. In [2], Bernstein, Sloane and Wright report that the correct value should be $9$ (see the values of $f(N)$ in their Table 1). The sequence for $\chi(v)$ is listed in the OEIS as A003051.

  I would guess that this "error" is due to a typo.

  (In the same paper [1], another couple of minor "errors": On page 213, $\nu(84, 3) = 1$, not $2$. The only such map is $T^{84,3}_{5}$. And, on page 214, $\nu_1(84,2) = 1$, not $2$. The only such map is $T^{84,2}_{8}$.)

• Regarding the colorability of the $6$-regular graphs considered above by Altshuler, in [3] Collins and Hutchinson say that direct computation shows that the $(m \times 1; 5)$ grids are not $4$-colorable only for $m = 10$, $11$, $13$, $17$, $18$ and $25$. However, they missed the value $m = 9$. This missing value is covered by one of the cases listed in [4] by Yeh and Zhu, namely $G = G_n[1,r,r+1]$ for $n = 2r + 3$ and $r = 3$, in their Theorem 7, but this fix is not explicitly noted in the paper.

  I do not know the source of this "error"; since the $(m \times 1; 5)$ grids are multigraphs for $m < 9$, it could simply be that Collins and Hutchinson did not perform a direct computation for $m \leq 9$, and so they missed the case $m = 9$.

References

1. Altshuler, Amos, Construction and enumeration of regular maps on the torus, Discrete Math. 4, 201–217 (1973). Zbl 0253.05117.

2. Bernstein, M.; Sloane, N. J. A.; Wright, Paul E., On sublattices of the hexagonal lattice, Discrete Math. 170, No. 1–3, 29–39 (1997). Zbl 0872.94009.

3. Collins, Karen L.; Hutchinson, Joan P., Four-coloring six-regular graphs on the torus, Hansen, Pierre (ed.) et al., Graph colouring and applications. Papers of the CRM workshop, Montréal, Canada, May 5–9, 1997. Providence, RI: American Mathematical Society. CRM Proc. Lect. Notes. 23, 21–34 (1999). Zbl 0944.05044.

4. Yeh, Hong-Gwa; Zhu, Xuding, $4$-colorable $6$-regular toroidal graphs., Discrete Math. 273, No. 1–3, 261–274 (2003). Zbl 1034.05024.