48

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.

Martin Sleziak
  • 4,608
Wolfgang
  • 13,193
  • 4
    https://en.wikipedia.org/wiki/List_of_disproved_mathematical_ideas – Steve Huntsman Aug 16 '18 at 18:44
  • 6
    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 '18 at 18:58
  • One might argue for Smale's discovery of sphere eversion, though I wouldn't personally make this argument, and only mention it here because it seems at least tangentially relevant. https://en.wikipedia.org/wiki/Sphere_eversion – Steve Huntsman Aug 16 '18 at 18:59
  • 1
    @MarkS yes that fits it. In this case the conjecture would have been the negation of Maier's theorem. I just meant to reword the title somewhat in the box to avoid a dumb repetition... – Wolfgang Aug 16 '18 at 21:17
  • 5
    See also https://mathoverflow.net/questions/30149/ – j.c. Aug 16 '18 at 22:01
  • 1
    Why is this question community wiki? My opinion is that MO has an interest in rewarding those with the knowledge to answer sophisticated questions like this. – Joel David Hamkins Aug 16 '18 at 22:33
  • 5
    @MarkS : Why not post Maier's theorem as an answer? – Timothy Chow Aug 17 '18 at 01:26
  • 4
    @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 '18 at 09:36
  • 1
    @Wolfgang I don't believe Joel can un-CW, ever since the move to join the SE network. But the current approach on the MO mod team is to treat questions that call for examples quantifying over all fields of mathematics as "big-list" and to make them CW. This is consistent with what we've been doing for years anyway (as you seem to know). – Todd Trimble Aug 18 '18 at 17:27

6 Answers6

34

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.

Timothy Chow
  • 78,129
  • What is different between this and recent result polynomial hierarchy is infinite with respect to a random oracle result? – Turbo Aug 17 '18 at 12:36
  • 4
    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 '18 at 14:07
31

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.

dionyziz
  • 101
24

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

Mark S
  • 2,143
  • 7
    Is there an improved heuristic model that predicts Maier's theorem? – YCor Aug 17 '18 at 21:08
  • @YCor I think that your question is very good. – user142929 Jan 02 '20 at 19:02
  • 2
    There is a chance that the random sieving model recently proposed by Banks, Ford and myself at https://arxiv.org/abs/1908.08613 may achieve this, although we have not analyzed this (our focus was instead on large prime gaps than on Maier-type theorems). – Terry Tao Jul 31 '20 at 01:55
22

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.

j.c.
  • 13,490
Gerry Myerson
  • 39,024
  • 3
    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 '18 at 17:06
  • 2
    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 '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 '18 at 17:38
13

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

Robert Israel
  • 53,594
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.

Mark S
  • 2,143
Alex Gavrilov
  • 6,851
  • What are those "very plausible heuristic arguments"? – Wojowu Aug 18 '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 '18 at 11:10
  • 3
    https://mathoverflow.net/questions/51531/theorems-that-are-obvious-but-hard-to-prove/51652#51652 – Alex Gavrilov Aug 18 '18 at 11:25