35
$\begingroup$

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:

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

$\endgroup$
7
  • 1
    $\begingroup$ What about incorrect claims of bounds? The specific example I'm thinking of fails 5 because the correction was only published in OEIS, but the published paper contained the first few terms of a sequence and "the next term being larger than [Y]" where the next term was in fact considerably smaller than Y. $\endgroup$ Jan 11, 2023 at 12:50
  • 1
    $\begingroup$ @Peter: I would be interested in incorrect bounds as well! (But not about correct claims that have simply been improved later...) The key thing I am looking for is dependence on substantial computation, and the following opacity of the published claims, as in "you have to believe us, because we computed it". $\endgroup$ Jan 11, 2023 at 13:36
  • $\begingroup$ Perhaps not combinatorics per se, but see Computing $\pi(x)$: the Meissel-Lehmer method, by Lagarias, Odlyzko, and Miller. It was a running joke that the largest value of every published table of values of $\pi(x)$ would be wrong, until Lagarias, Odlyzko, and Miller "broke the curse." $\endgroup$ Jan 13, 2023 at 2:12
  • 1
    $\begingroup$ Again this is not exactly computational combinatorics but rather enumerative geometry. Famously, the calculation of the number of twisted cubics on a generic quintic hypersurface was done in two different ways, one via "physics methods" that were (at the time) nonrigorous, and one via conventional mathematical methods. Initially the two answers disagreed. It turned out that the "rigorous" mathematical calculation was wrong because of a bug in the program. $\endgroup$ Jan 13, 2023 at 2:34
  • 2
    $\begingroup$ @Jean Marie Becker: Sorry for being unclear, that's just MathOverflow slang for "community wiki", basically meaning that votes do not affect reputation (and some other details). Big-list questions are typically made such (it seems). $\endgroup$ Jan 13, 2023 at 7:42

8 Answers 8

21
$\begingroup$

(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.

$\endgroup$
3
  • 2
    $\begingroup$ Thanks! The history of errors with Latin squares is astonishing. About hardware errors, I believe you are referring to the posets of up to 16 points. Fortunately, that case does not qualify here, because you caught the errors before publication. $\endgroup$ Jan 11, 2023 at 14:35
  • $\begingroup$ I wonder if this "hardware part" is really correct. From my experience, the software on two computes is never really "identical", and errors can arise from all sorts of things, even tiny variations in the version or configuration of the operating system. $\endgroup$ Jan 13, 2023 at 14:30
  • 2
    $\begingroup$ My example was of a single computer which gave the right answer almost always but once in every few hundred runs it gave the wrong answer. Same computer, same hardware, same OS, same executable, same input. None of the other 100 nodes in the cluster had that problem. A hardware issue for sure. $\endgroup$ Jan 14, 2023 at 4:28
15
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Even more groups are 2-groups than we thought! $\endgroup$
    – LSpice
    Jan 13, 2023 at 1:53
  • $\begingroup$ Yeah, that old number always seemed a tad low. $\endgroup$ Dec 4, 2023 at 8:30
9
$\begingroup$

(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.)

$\endgroup$
2
  • 2
    $\begingroup$ I didn't know that all answers to a community wiki question are also CW. Sad... $\endgroup$ Jan 11, 2023 at 21:38
  • 1
    $\begingroup$ Thank you for your extensive answer. I think that reputable arXiv manuscripts count as "scientific publications" here & have updated my question to allow them. $\endgroup$ Jan 12, 2023 at 9:27
7
$\begingroup$

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$.
$\endgroup$
2
  • 1
    $\begingroup$ Do you know why the $E_6$ count was so dramatically wrong? $\endgroup$
    – LSpice
    Jan 13, 2023 at 1:55
  • 1
    $\begingroup$ @LSpice No, I can only guess that they did not actually count all objects by hand but used structural symmetries of which they might have missed some to take into account in type $E_6$. $\endgroup$ Jan 13, 2023 at 7:13
7
$\begingroup$

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

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.

$\endgroup$
2
  • $\begingroup$ Just to clarify: I did not make the criteria stricter at any point. My only modification was to allow more, namely, also arXiv manuscripts. $\endgroup$ Jan 15, 2023 at 14:58
  • $\begingroup$ According to Jason Parsley, in addition to the famous Perko pair, there are errors in the tables in John H. Conway's paper, An enumeration of knots and links, and some of their algebraic properties. However, I have not been able to locate any more details about what exactly the errors were. $\endgroup$ Jan 19, 2023 at 23:27
4
$\begingroup$

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\}$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$
  • 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.