Are there examples of conjectures supported by heuristic arguments that have been finally disproved?

Question

The idea for this comes from the twin prime conjecture, where the heuristic evidence seems just so overwhelming, especially in the light of Zhang's famous result from 2014 about Bounded gaps between primes and its subsequent improvements.

Are there examples of conjectures with some more or less "good" heuristic arguments, but where those arguments have finally not been "strong" enough?

I don't mean heuristic in the sense that some conjecture holds for small numbers, e.g. the fact that $li\ x-\pi (x) $ was thought to be always positive, before Littlewood showed that not only it eventually changes sign, but does so infinitely often later on. So my question is different from the question about eventual counterexamples.

Likewise, the fact that the first $10^{15}$ or so zeros of the zeta function "obey" RH does tell us something, but not a whole lot compared with infinity. So again this is not what I mean by heuristic.

Answer 1

In computational complexity theory, most conjectures that two complexity classes are equal (or not equal, as the case may be) can be relativized to an oracle. Sometimes, as in the case of P = NP, one can obtain contradictory relativizations; i.e., there exists an oracle A such that P^A = NP^A and an oracle B such that P^B ≠ NP^B.

In the case of contradictory relativizations, it is tempting to hypothesize that if, for example, P^B ≠ NP^B for "most" oracles B, then P ≠ NP in the "real" (unrelativized) world. This heuristic was seriously proposed by Bennett and Gill as the "random oracle hypothesis," for a specific precise definition of "most oracles." However, the random oracle hypothesis was disproved by Kurtz. Later, another conjecture was proposed along similar lines: the "generic oracle hypothesis," with a different precise definition of "most oracles." But the generic oracle hypothesis was also disproved, by Foster.

Answer 2

This is extremely common in the field of cryptography. It was popular to design key exchange systems in the 1980s without proof of security, just giving intuitive arguments which were often quite convincing. It turns out a lot of these systems became broken later.

Distributed systems are difficult to have good intuition about because they are complicated objects. However, we have a lot of (wrong) intuition around them because they are physical systems and we think we understand them. Hence, it is easy to make mistakes. There are many cases where systems work contrary to intuition.

One of my favourite examples is bitcoin. The original paper gives an argument about why the system is secure and why the honest strategy is a Nash equilibrium, by illustrating that one particular attack doesn't work in favour of an adversary. This is more than just a hand-wavy argument: It is the full calculation of a particular attack, analytically and with numbers. Furthermore, that particular attack seems the most reasonable thing to do.

However, it was later shown that there are strategies which are better than the honest strategy -- the "selfish mining" attacks. The latter paper describes an alternative attack, quite more complicated, than what the original author envisioned. The attack is contrary to intuition. The bitcoin protocol was later fully analyzed on the backbone paper and it was proven secure for any adversarial strategy. However, the selfish mining strategy remains a better strategy than the honest strategy (and in fact the backbone paper shows a tight bound on this class of attacks), so bitcoin is not incentive-compatible.

Another example around bitcoin-related conjectures is that, as time goes by and coinbase rewards are decreased, fees will make up for the incentives to continue running the blockchain. This notion is so ingrained in the bitcoin community that the bitcoin wiki literally states that "In the future, as the number of new bitcoins miners are allowed to create in each block dwindles, the fees will make up a much more important percentage of mining income." This conjecture has been shown to be false.

Answer 3

I think the OP is looking for answers where there is a heuristic justification, apart from simply a large amount of numerical evidence, that in some instances may break down. For example, "we morally expect objects to behave a certain way, but in this instance, they don't behave quite the way we expect them to."

Cramér's probabilistic model, from the 1930's, is a powerful heuristic for, among others, estimating gaps between prime numbers.

However, Maier's theorem from 1985 states that, for all $\lambda\gt 1$,

$$\frac{\pi(x+(\log x)^\lambda)-\pi(x)}{(\log x)^{\lambda-1}}$$

does not have a limit as $x$ goes to infinity, whereas following the Cramér heuristic, one would have a limit of $1$ for all $\lambda \gt 2$.

Pintz revisits Maier's theorem, studying weaknesses of such probabilistic models with technology available in the '30s. He also hints that there are ways to improve the CM heuristic to correctly predict Maier's limit, but goes on to provide another weakness inherent to all such models that, although smaller, "seems impossible to correct."

Answer 4

It has been conjectured that, for all $n$, there is no interval of length $n$ with more primes in it than the interval between $2$ and $n+1$. You look at a table of primes, and you see how they thin out the higher up you go, and that's evidence, of a sort. But more precisely, we know that the density of the primes among the first $n$ numbers goes to zero as $n$ goes to infinity, so that seems like a heuristic supporting the conjecture.

And the conjecture hasn't actually been disproved, but some 40 years ago, Hensley & Richards proved it contradicted the prime $k$-tuples conjecture, which has what's considered to be stronger supporting evidence. So at least one of two conjectures with heuristic support is false, we just don't have a decision yet on which one.

Answer 5

Ruelle's "heuristic theory of phase transitions" (Comm. Math. Phys., Volume 53, Number 3 (1977), 195-208) turned out to be false in certain Banach spaces of interactions: see my "Generic triviality of phase diagrams in spaces of long-range interactions" (Comm. Math. Phys., Volume 106, Number 3 (1986), 459-466).

Answer 6

I think Hauptvermutung (the "main conjecture" in German) is a good example. It certainly is supported by very plausible heuristic arguments, and nobody had any doubt for half a century.