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

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.

• The question in your title seems subtly different than the question in the box. Is Maier's theorem an example of what you are looking for? Cramér's heuristic breaks down here. – Mark S Aug 16 at 18:58
• @MarkS : Why not post Maier's theorem as an answer? – Timothy Chow Aug 17 at 1:26
• @JoelDavidHamkins I guess that is just the MO policy/tradition for "big-list" questions. Now of course you, more than anybody else here, may feel free to use your privilege of "un-CW-ing" what some other mod made CW. But anyway, supposedly not many people will post an answer only because of getting some virtual reward for that. Sure I agree that such a reward is always nice for one's ego, but there are rewards which are far more precious in life. :) :) – Wolfgang Aug 17 at 9:36

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 PA = NPA and an oracle B such that PB ≠ NPB.

In the case of contradictory relativizations, it is tempting to hypothesize that if, for example, PB ≠ NPB 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.

• What is different between this and recent result polynomial hierarchy is infinite with respect to a random oracle result? – Freeman. Aug 17 at 12:36
• In 2015, Rossman, Servedio, Tan strengthened Yao and Hastad's theorem (PH is infinite relative to some oracle) to "PH is infinite relative to a random oracle." Because the random oracle hypothesis is false in general, the Rossman et al. theorem does not provide as strong evidence for "PH is infinite" as it might otherwise, but it is still a stronger result than Yao and Hastad's theorem. – Timothy Chow Aug 17 at 14:07

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.

• I read recently someone's observation that it is extremely easy for one to conceive of cryptosystems that oneself could never conceive of breaking. Truer words have never BitToken. – PrimeRibeyeDeal Aug 17 at 17:23
• Groan! (which is high praise for a pun) – Brian Hopkins Aug 20 at 14:15

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

• Is there an improved heuristic model that predicts Maier's theorem? – YCor Aug 17 at 21:08

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.

• Off topic, but I was struck by the line in the linked paper: "It was necessary to go into machine language in order to handle a sequence of 10^5 bits without taking too much computer time and memory space". How things change... – Yemon Choi Aug 18 at 17:06
• Maybe this decreasing prime density conjecture is false just because you encounter more prime powers in [2,n+1] than in other intervals of length n : the prime powers 4, 8, 9, 16, 25, 27, 32, 49 all appear before 50 so it may not be that surprising that some translate of such an interval actually contains more primes. – Sylvain JULIEN Aug 18 at 17:33
• And as a matter of fact, adding 100 to the previous numbers yields the three primes 109, 127 and 149. – Sylvain JULIEN Aug 18 at 17:38

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

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.

• What are those "very plausible heuristic arguments"? – Wojowu Aug 18 at 10:28
• Edwin Moise in his well known paper "Affine structures ..." (Annals of Math,1952) for this sort of arguments makes a reference to "Zur Topologie der Mannigfaltigkeiten", G Nöbeling, Monatshefte für Mathematik und Physik, 1935. I can't say much more for I could not read it even if I had it (I am not very good at German). On the undergrad level, it is plausible at least for manifolds because continuous maps can be approximated by piecewise linear ones. Of course, today we know that this logic is wrong. – Alex Gavrilov Aug 18 at 11:10