What is a heuristic proof?

Question

I just wonder what does a heuristic proof approach really means. I keep finding it in books and from teachers. I got to the next analogy:

A heuristic proof of a mathematical proof is like pseudo-code for an algorithm.

Not a technical math question but I would like to know. Thanks in advance.

Answer 1

First, I object to the term "heuristic proof." That phrase is a contradiction in terms. Heuristics are not (generally speaking) proof, and proofs generally require more detail and nuance than heuristics. It would be better to use the phrase "heuristic argument."

With that bit of pedantry addressed, it is often (though not always) helpful to look at what lexicographers have determined that word means. In this case, Merriam-Webster suggests that a heuristic is something

involving or serving as an aid to learning, discovery, or problem-solving by experimental and especially trial-and-error methods.

So heuristics are learning or problem-solving tools. In mathematics, heuristics are generally informal arguments that are meant to convince someone that a result is true without necessarily getting into the nitty-gritty of a proof, which might be rather involved. For example, in an elementary calculus class, you will often see an argument for the chain rule that looks something like

The derivative of $f$ with respect to $g$ is denoted by $\frac{\mathrm{d}f}{\mathrm{d}g}$, and the derivative of $g$ with respect to $x$ is denoted by $\frac{\mathrm{d}g}{\mathrm{d}x}$. Thus we have $$\require{cancel} \frac{\mathrm{d}f}{\cancel{\mathrm{d}g}} \cdot \frac{\cancel{\mathrm{d}g}}{\mathrm{d}x} =\frac{\mathrm{d}f}{\mathrm{d}x}. $$ Therefore $\frac{\mathrm{d}}{\mathrm{d}x} (f\circ g)(x) = f'(g(x)) g'(x)$.

This argument is not rigorous, and cannot really be made rigorous without a great deal of explanation (either by way of non-standard analysis, or a very careful $\varepsilon$-$\delta$ argument). However, the notation is suggestive, and the basic result is correct, so it is a useful aid to learning.

Another example is the heuristic argument for the Prime Number Theorem, which (roughly) states that the number of prime numbers less than $N$ is on the order of $N/\log(N)$. An actual proof of the Prime Number Theorem is rather involved, but the following heuristic argument is generally enough to convince someone that it is true:

Suppose that the primes are uniformly randomly distributed among all of the positive integers. Let $P(N)$ denote the probability that $N$ is prime, where $N$ is some sufficiently large number. If $N$ is prime and $M$ is larger than $N$, then $N$ divides $M$ with probability $1/N$ (2 divides every other number, 3 divides every third number, 5 divides every fifth number, and so on). In particular, if is prime, then $N$ divides $N+1$ with probability $1/N$. By the Law of Total Probability $$ P(N+1) = \underbrace{P(N)\left[P(N)\left( 1- \frac{1}{N}\right)\right]}_{(1)} + \underbrace{(1-P(N))P(N)}_{(2)}$$ where (1) if $N$ is prime, then (assuming independence) $N+1$ is prime with probability $P(N+1) \approx P(N)$ and also $N \nmid N+1$, which happens with probability $1-\frac{1}{N}$, and (2) $N$ is not prime with probability $1-P(N)$, but for $N$ large enough, both $N$ and $N+1$ have about the same chance of being prime. Thus $P(N+1) \approx P(N)$. By some basic algebra $$ \frac{P(N+1)}{P(N)} = P(N) \left(1-\frac{1}{N}\right) + (1-P(N)) = 1 - \frac{P(N)}{N}.$$ But we can approximate $P(N+1)$ by $P(N) + P'(N)$ (i.e. $P(x+\Delta x) \approx P(x) + P'(x)$), so this becomes $$ 1 + \frac{P'(N)}{P(N)} = 1 - \frac{P(N)}{N} \implies \frac{P'(N)}{P(N)} = - \frac{P(N)}{N}. $$ This is a first order PDE with general solution $$ P(N) = \frac{1}{C + \log(N)}. $$ In other words, the probability that a randomly chosen integer $N$ is prime is approximately $\frac{1}{\log(N)}$. If $N$ is any positive integer, then there are $N$ positive integers less than or equal to $N$, and so $$ (\text{number of primes up to $N$}) \approx N \cdot \frac{1}{\log(N)}. $$

There are a lot of holes in this argument (there are infinitely many positive integers, yet we have assumed that the probability that a given number is prime is uniform, which is a problem; we have not been very careful with the errors in a number of approximations; etc). In this case, lulu's comment that a heuristic argument is "an informal argument which assumes plausible (but unproven) results" is quite apt---there is a long way to go before we have a real proof.

Indeed, the usual proofs of the Prime Number Theorem are not probabilistic proofs, and attack the problem along other lines. However, most of the authentic proofs are pretty technical, and don't really give any insight into why we might even suspect that the Prime Number Theorem is true in the first place. This heuristic argument should convince us that the theorem might be true, and give us reason to pursue a better proof.