Heuristically false conjectures

I was very surprised when I first encountered the Mertens conjecture. Define

$$M(n) = \sum_{k=1}^n \mu(k)$$

The Mertens conjecture was that $|M(n)| < \sqrt{n}$ for $n>1$, in contrast to the Riemann Hypothesis, which is equivalent to $M(n) = O(n^{\frac12 + \epsilon})$ .

The reason I found this conjecture surprising is that it fails heuristically if you assume the Mobius function is randomly $\pm1$ or $0$. The analogue fails with probability $1$ for a random $-1,0,1$ sequence where the nonzero terms have positive density. The law of the iterated logarithm suggests that counterexamples are large but occur with probability 1. So, it doesn't seem surprising that it's false, and that the first counterexamples are uncomfortably large.

There are many heuristics you can use to conjecture that the digits of $\pi$, the distribution of primes, zeros of $\zeta$ etc. seem random. I believe random matrix theory in physics started when people asked whether the properties of particular high-dimensional matrices were special or just what you would expect of random matrices. Sometimes the right random model isn't obvious, and it's not clear to me when to say that an heuristic is reasonable.

On the other hand, if you conjecture that all naturally arising transcendentals have simple continued fractions which appear random, then you would be wrong, since $e = [2;1,2,1,1,4,1,1,6,...,1,1,2n,...]$, and a few numbers algebraically related to $e$ have similar simple continued fraction expansions.

What other plausible conjectures or proven results can be framed as heuristically false according to a reasonable probability model?

• I think that for someone armed with a knowledge of modern probability theorem -- especially, Kolmogorov's Law of the Iterated Logarithm -- Mertens' Conjecture is wildly _im_plausible, and thus I too am not surprised that it is false. I think it's a good example of how "probabilistically naive" a good 19th century mathematician could be. As for the continued fraction expansion for $e$, that's a shocking result -- the first time someone told me this, I thought they were putting me on -- but I don't see how it contradicts any probabilistic model. ... – Pete L. Clark Jan 16 '10 at 18:11
• ... In fact, in the branches of mathematics that I know best (number theory, especially), the biggest tool for making plausible conjectures is finding some reasonable probabilistic model. For instance, the idea that the values of the Mobius function should be (very close to) IID random variables is the most persuasive argument I know for the Riemann hypothesis. – Pete L. Clark Jan 16 '10 at 18:17
• The situation with $M(x)$ is a bit more subtle than that. Reliance on Khinchine's Law of the iterated logarithm for random walks (which is what is relevant here) would lead to the conclusion that $M(x) = o(\sqrt{x}\log\log(x))$ is false. But those who have considered this question recently (Kotnik and van de Lune, and Ng) offer evidence that $M(x) = O(\sqrt{x}(\log\log\log(x))^b)$ for some positive $b$. On probabilistic grounds this is just as "wildly implausible" as the Mertens Conjecture. – engelbrekt Jan 16 '10 at 19:53
• Mertens did hand calculations, and made his conjecture on the basis of that. He would have known of Stieltjes' claim in the Comptes Rendus to have proved $M(x)/\sqrt{x}$ bounded, though I doubt he would have known of Stieltjes' opinion expressed in a letter to Hermite that $|M(x)| \leq \sqrt{x}$. Shortly after Mertens, von Sterneck developed formulas that enabled him to push hand calculations up to 150.000. Von Sterneck was actually the first to see the growth of $M(x)$ from a probabilistic angle, though he compared with the Central Limit Theorem rather than the Law of the Iterated Logarithm. – engelbrekt Jan 16 '10 at 23:16
• $log\log(x)$ is exponentially large compared with $\log\log\log(x)$ ... I don't think that Mertens was unreasonable in making his conjecture. He was a very competent analytic number theorist within the limitations of his time, when the unreliability of computational evidence in analytic number theory was as yet unsuspected. Only with Littlewood's 1914 disproof of $\pi(x) < \mathrm{li}(x)$ did the pitfalls become clear. This inequality had, for the time, superb computational support. – engelbrekt Jan 16 '10 at 23:30

I think this example fits, in 1985 H. Maier disproved a very reasonable conjecture on the distribution of prime numbers in short intervals. The probabilistic approach had been thoroughly examined by Harald Cramer. Nice paper by Andrew Granville including this episode in (mathematical) detail, page 23 (or 13 out of 18 in the pdf):

www.dms.umontreal.ca/~andrew/PDF/cramer.pdf

• That's a nice exposition by Granville of subtly differing heuristics on the primes. I'd love to see more examples. – Douglas Zare Jan 19 '10 at 15:33
• The second Hardy-Littlewood conjecture (widely believed to be false) is in a similar spirit: en.wikipedia.org/wiki/… – Terry Tao Jan 23 '10 at 5:44
• Interesting, thanks. It's surprising that there are admissible prime constellations that dense. – Douglas Zare Jan 30 '10 at 20:08

Just run across this question, and am surprised that the first example that came to mind was not mentioned:

Fermat's "Last Theorem" is heuristically true for $n > 3$, but heuristically false for $n=3$ which is one of the easier cases to prove.

if $0 < x \leq y < z \in (M/2,M]$ then $|x^n + y^n - z^n| < M^n$. There are about $cM^3$ candidates $(x,y,z)$ in this range for some $c>0$ (as it happens $c=7/48$), producing values of $\Delta := x^n+y^n-z^n$ spread out on the interval $(-M^n,M^n)$ according to some fixed distribution $w_n(r) dr$ on $(-1,1)$ scaled by a factor $M^n$ (i.e., for any $r_1,r_2$ with $-1 \leq r_1 \leq r_2 \leq 1$ the fraction of $\Delta$ values in $(r_1 M^n, r_2 M^n)$ approaches $\int_{r_1}^{r_2} w_n(r) dr$ as $M \rightarrow \infty$).

This suggests that any given value of $\Delta$, such as $0$, will arise about $c w_n(0) M^{3-n}$ times. Taking $M=2^k=2,4,8,16,\ldots$ and summing over positive integers $k$ yields a rapidly divergent sum for $n<3$, a barely divergent one for $n=3$, and a rapidly convergent sum for $n>3$.

Specifically, we expect the number of solutions of $x^n+y^n=z^n$ with $z \leq M$ to grow as $M^{3-n}$ for $n<3$ (which is true and easy), to grow as $\log M$ for $n=3$ (which is false), and to be finite for $n>3$ (which is true for relatively prime $x,y,z$ and very hard to prove [Faltings]).

More generally, this kind of analysis suggests that for $m \geq 3$ the equation $x_1^n + x_2^n + \cdots + x_{m-1}^n = x_m^n$ should have lots of solutions for $n<m$, infinitely but only logarithmically many for $n=m$, and finitely many for $n>m$. In particular, Euler's conjecture that there are no solutions for $m=n$ is heuristically false for all $m$. So far it is known to be false only for $m=4$ and $m=5$.

Generalization in a different direction suggests that any cubic plane curve $C: P(x,y,z)=0$ should have infinitely many rational points. This is known to be true for some $C$ and false for others; and when true the number of points of height up to $M$ grows as $\log^{r/2} M$ for some integer $r>0$ (the rank of the elliptic curve), which may equal $2$ as the heuristic predicts but doesn't have to. The rank is predicted by the celebrated conjecture of Birch and Swinnerton-Dyer, which in effect refines the heuristic by accounting for the distribution of values of $P(x,y,z)$ not just "at the archimedean place" (how big is it?) but also "at finite places" (is $P$ a multiple of $p^e$?).

The same refinement is available for equations in more variables, such as Euler's generalization of the Fermat equation; but this does not change the conclusion (except for equations such as $x_1^4 + 3 x_2^4 + 9 x_3^4 = 27 x_4^4$, which have no solutions at all for congruence reasons), though in the borderline case $m=n$ the expected power of $\log M$ might rise.

Warning: there are subtler obstructions that may prevent a surface from having rational points even when the heuristic leads us to expect plentiful solutions and there are no congruence conditions that contradict this guess. An example is the Cassels-Guy cubic $5x^3 + 9y^3 + 10z^3 + 12w^3 = 0$, with no nonzero rational solutions $(x,y,z,w)$:

Cassels, J.W.S, and Guy, M.J.T.: On the Hasse principle for cubic surfaces, Mathematika 13 (1966), 111--120.

This is quite elementary, but surprised me when I first saw it, and I still think it's remarkable.

The number of pairs of integers $(x, y)$ such that $x^2 + y^2 \leq n$ is asymptotically $\pi n$, since they are the lattice points inside a circle of radius $\sqrt{n}$. Therefore the average number of ways of writing a positive integer as a sum of two squares is $\pi$. Or $\pi/8$ if we regard solutions as the same when they differ only in signs or the order of the terms.

One would therefore expect a positive proportion of the natural numbers to have a representation as a sum of two squares. Not a $\pi/8$-fraction, since some integers have several representations, but some slightly smaller positive density, since identities like $4^2 + 7^2 = 1^2 + 8^2$ look pretty much like random coincidences.

But actually almost no numbers are sums of two squares. Whenever the prime factorization of $n$ contains some prime $p\equiv 3$ (mod 4) to an odd power, $n$ cannot be a sum of two squares, as is easily seen by considering the equation modulo powers of $p$. And by Dirichlet's theorem, almost all numbers have some such prime to power 1 in their factorization.

• Interesting example. It can be explained by refining the heuristic to account for the distribution of sums-of-two-squares at finite places as well as the archimedean place. (I'm not sure how Dirichlet's theorem applies: there are infinite sets $S$ of primes for which $\prod_{p\in S} ((p-1)/p)$ converges to a positive number. But one can give an analytic argument using the positivity of $L(1,\chi_4) = 1 - \frac13 + \frac15 - \frac17 + - \cdots$.) – Noam D. Elkies Jul 30 '12 at 14:46
• If you'll accept another minor correction, you want to consider $x^2+y^2=n$ modulo $p$, not modulo $4$, to get a contradiction. I agree that this is a very nice example. It is sort of a minimal version of Noam's example, in that an archimedean estimate predicts infinitely many solutions when there are actually finitely many for non-archimedean reasons, but it is simpler in that the non-archimedean reasons are elementary number theory rather than BSD. – David E Speyer Jul 30 '12 at 15:07
• Regarding Dirichlet: The "probability" that $n$ has an even number of factors $p$ (for instance none) is $p/(p+1)$. So the probability that every prime $p\equiv 3$ (mod 4) occurs to an even power is $\Pi_{p\equiv 3\,(4)} (p/(p+1))$, which is zero. This is a particularly simple case of Dirichlet's theorem that follows, as pointed out by Noam, from the fact that $1-1/3+1/5-1/7+\dots$ is nonzero. – Johan Wästlund Jul 30 '12 at 15:41
• Dirichlet proved that there are infinitely many primes in such a progression. Did he prove that the sum of their reciprocals diverges? That's not too hard given what he did (and yes, the $3 \bmod 4$ case is particularly easy) but I don't know whether he stated the result. – Noam D. Elkies Jul 30 '12 at 19:28
• [I took the liberty of carrying out D.Speyer's suggestion; since the valuation of $n$ at $p$ is allowed to be any odd number, I made it "modulo powers of $p$"] – Noam D. Elkies Aug 2 '12 at 8:51

CS theory has a slew of these examples. In particular, take any problem which is known to be in $RP$, but its membership in $P$ is (currently) unknown.

Example: is it possible, using walks consisting of polynomially many steps, to estimate the volume of a convex body?

In the terminology of your question, the answer is 'yes' if you say that random steps are a reasonable model of the steps made by a smart algorithm. On the other hand, a deterministic method of choosing the steps is unknown.

(PS the reference on this particular problem is "A random polynomial-time algorithm for approximating the volume of convex bodies" by Dyer, Frieze, Kannan.)

• Re "take any problem which is known to be in RP, but its membership in NP is (currently) unknown": as RP is (known to be) contained in NP, you probably mean P? – aorq Jan 16 '10 at 16:04
• @Anonymous Rex, YES, thank you, also have you thought about using the dinosaur from qwantz.com as your avatar? hopefully i don't get banned from mathoverflow for the non-mathematical nature of this comment. i'll point out that maybe the problem i should have given is the primality testing one, where the deterministic solution was found apparently by derandomizing some other randomized strategy for it (but not the miller-rabin primality test). – Matus Telgarsky Jan 16 '10 at 16:39
• Re qwantz: Although I like dinosaur comics, I tried to find a T. Rex that was in the public domain, as best as I could ascertain. – aorq Jan 16 '10 at 17:09
• How is this an answer to the original question? As far as I can see, here the probabilistic model suggests the answer is “yes”, and the most plausible conjecture is that the true answer is also “yes” (and more generally, P = RP, using the Nisan–Wigderson generator). So, here the plausible conjecture is heuristically true, or am I missing something? – Emil Jeřábek Jun 7 '11 at 10:32

The Alon-Tarsi Conjecture states that the number of even Latin squares is not equal to the number of odd Latin squares for even $n$. Although, it can be shown that the gcd of these two numbers grows super-exponentially with $n$ (i.e. these two numbers have many common divisors). Moreover, it seems that they're asymptotic (using an heuristic argument).

• Could you elaborate on the heuristic argument? If f(n) and g(n) are two random functions which grow rapidly, then f(n)-g(n) should not often equal 0. So, it's not yet clear to me how this conjecture is heuristically false. – Douglas Zare Jan 23 '10 at 5:24
• Well, I think it's peculiar. Ln(even)-Ln(odd) share a super-exponential divisor, are likely to be asymptotic and are actually equal for odd n. These are properties of sequences that are equal. The heuristic argument is basically trying to find a trade in a Latin square (i.e. edit only a certain small section of the matrix, while preserving the Latin property) -- typically, there will be lots of switches available (but trying to show that almost all Latin squares admit such a switch is difficult). See Wanless "Cycle switches in Latin squares" 2004 for more details. – Douglas S. Stones Feb 25 '10 at 22:05