Found and corrected a mistake on someone's else paper -- praxis?

Question

3-4 months ago I found a big mistake in a theorem's proof of a paper that had just been published (stats/cs community). I immediately notified the authors, who claimed to be aware of the mistake but admitted not knowing how to fix it.

This week I noticed that the authors didn't notify the community of the mistake (no updates on their arxiv paper, nothing on the author's websites, etc), even though the paper got a good visibility and already has quite a few citations. I went to check whether the mistake breaks the theorem, and found out that:

1 - the theorem statement is incorrect

2 - however, the statement holds under reasonable assumptions, but the proof requires a different technique (I have a full proof for that)

How should I proceed in this case? This theorem specifically is the main result of the paper, so I wouldn't be comfortable just sending them the corrected proof+statement and not getting properly recognized (e.g. only an acknowledgement). Should I write a short report on post it on arxiv? Send the proof under the requirement that I be added as a co-author? What is the praxis in this case?

EDIT:

Thanks for all the replies so far. I've contacted my advisor and have finished writing a short report (~4 pages) on the matter. I'm yet to decide whether I should contact the authors before posting the report, and whether a merger would be a good idea -- as some people said, it is a huge red flag that they admitted to be aware of the mistake and never took action, so I am not certain that I would like to be associated with the authors in a collaboration level.

1) The paper has already been published in a conference and its journal proceedings. I've contacted the authors after acceptance but before the proceedings were published, and they took no action.

2) The paper proposes a new algorithm B and states that it has the same running time as algorithm A, a classic method in the field, while having smaller memory cost and being easy to implement. The main theorem roughly states that T(B) = O(T(A)), which is wrong as for some inputs T(B) = infinity. The technical mistake is subtle and involves upper-bounding an infinite series, which in reality can diverge to infinity. I've ran the algorithm on a simple instance where it does not halt nor makes any progress.

3) It can be shown that, for some input distributions, T(B) = O(T(A)). The technical argument is a bit different from what they initially presented. Unfortunately, I think that for these distributions it can be shown that A has an even smaller memory cost than B, but I am not sure.

Answer 1

Edited: OP mentioned that the paper has been published in conference (not just on ArXiv as was implied by phrasing).

This can be tricky.

The main thing is that you get due credit, and that the scientific community is aware of the mistake.

If the mistake is in a key theorem that is the basis for the entire paper, then the authors should retract the paper. As unpleasant as this may be, it is the only ethical and fair thing to do. If the authors aren't doing this of their own volition, then you should (I would argue that you are in fact ethically obliged to do so!):

1. Make 100% sure that you are right in your claim. It's not entirely clear whether the theorem is "dead in the water" i.e. the claim is demonstrably false (via a counterexample that you've constructed), or that the claim might be true, but their proof is wrong, and you couldn't have come up with a proof either. If you have a counterexample, then you've really managed to kill the paper. Otherwise it's still an open problem (not a bad thing, just a different scenario).
2. Consulting with your advisor/senior member of the community, contact the conference program chairs to inform them of the mistake. You should let them know where the paper is wrong; you can also mention that you have a correction that you're keeping to yourself, but you are not obliged to provide it. A paper with a wrong proof should never appear in any conference.

This paper should not be published. If it was published in a high-profile ML conference (ICML/NeurIPS/COLT etc.), then the organizers can be trusted to take it from there.

You must understand though that if you go and report this to the organizers without the authors being on board, then this may result in some unpleasant interactions with them in the future (to be fair, the authors brought this upon themselves by not owning up, but still - people have egos and pride).

Next up, The ideal scenario is that you email the authors, the authors agree to working with you, adopt your proof technique and add you as a coauthor (assuming you’ve corrected an important theorem). This is assuming that the authors are being reasonable and don’t have a fragile ego.

To make that happen you’ll need to phrase the email carefully “I think that I can show that Theorem 1 holds under some minor assumptions, can you take a look at my proof? I’d love to collaborate with you on a future version of the paper” or something like that.

If that doesn’t happen (radio silence after you email them or worse: them saying they had already thought of this idea or some other nonsense), you need to get your credit somehow (e.g. by getting a supervisor/mentor to intervene). You could concurrently start writing your own version and upload to ArXiv (so it’s publicly timestamped), referencing the original.

Most cases I’ve seen followed a merger of authors but there are some distasteful instances, be prepared and be pleasant and you’ll be fine!

Answer 2

I have not been in such situation. However, I do not see what is the problem for you to write a paper complementing or correcting the previous paper? Isn't this how science works?

In my opinion, it is very toxic culture in academia to consider such thing as inappropriate. Those previous auathors are humans. Assuming good faith, that was what they knew and what was to the best of their knowledge, and to the best of the reviewers' knowledge, at the time of their publication. You got something, great, you have the right to get the credit for it. I feel it is unfair that you inform the authors offline. You should write it, and publish it too.

Also, we should not forget that you might be wrong too! I do not mean to offend anyone. But if we remember that we are all humans and have limitations in our knowledge about exploring this world, we would take these issues in a more relaxed way.

Answer 3

If you think that you have found the proof of a paper, or you can (with evidence) notify the community of the wrong/improper/incomplete proof, you can itself publish it as a research article.

For example, look at the following comment (to be) published in IEEE Trans. on Wireless Communication: Comments on “Coverage Analysis of Multiuser Visible Light Communication Networks”

Linke can be found here

Answer 4

(From comments from the OP)

In a very high level, the theorem is on the running time of an algorithm, and I found one instance where the algorithm does not halt. Under mild assumptions on the input it can be shown that the asymptotic running time is the same as what they originally claimed.

As someone who works on statistical algorithms, it's my opinion that you found an error in their paper, but I have trouble believing this is the entirety of their paper; I've never read a paper that just proves "Such and such algorithm is O(nk)" and that's it. But I could be mistaken; perhaps this paper was supposed to provide a proof that a well known heurestic algorithm actually had strong theoretical backing?

Anyways, if this false claim was not the entirety of their work, I would guess that their paper is not so broken that it should be retracted, especially since it sounds like you've come up with a set of conditions for which the statement will hold true. But it is worth noting the mistake and correcting it within the academic literature. As such, I would guess that it is very reasonable to write a follow up paper to the journal that essentially says something like the following:

In the paper Previous Work, it was stated that the algorithm would display quadratic convergence under conditions X. We demonstrate that, in fact, the algorithm can fail to converge under X and Z, and provide the necessary conditions X and Y for which the quadratic convergence rate is recovered.

If the authors of Previous Work did not help you write up this new paper, there is no need to share authorship with them, although it was very polite of you it point it out to them.

In fact, as a very relevant example, the very famous 1977 EM algorithm paper had an issue in its convergence proof, which was corrected in 1983 by a different author.