The prime number theorem (PNT) says that an integer $n$ is prime with probability $\frac{1}{\ln n}$.

Using only PNT, it's conceivable that each integer upto $10^{10^{10}}$ is non-prime. However using other methods this is found not to be the case.

Is there a theorem analogous to PNT such that each integer is assigned a definite positive probability to satisfy a property $P(n)$, but no integer that satisfy $P(n)$ is known?

However if we sum the probabilities, and it sums to $1$, does it prove the existence of such an integer? And also such that there are no other (then probabilistic) methods to prove the existence of an integer that satisfy $P(n)$. And must it necessarily prove the existence of an infinite such integers (that satisfy $P(n)$)?

  • 8
    $\begingroup$ Are you sure you didn't left out some tags? :-) $\endgroup$ – Asaf Karagila Oct 30 '11 at 17:29

It doesn't really make sense to assign a definite probability (other than 0 or 1) to each integer having some (specific) property. Each integer either has a property or it hasn't.

It can sometimes be productive to pretend that such a probability can be assigned, in what is usually known as a "heuristic" argument. Such arguments can help getting an idea of whether it is reasonable to expect to be able to prove something, if an exact analysis appears to be hard. But it is not itself a proof technique that meets the requirements of mathematical rigor, and it is never possible to prove (because it is never true) that some non-trivial function $f:\mathbb N\to [0,1]$ always gives an actual probability for its argument to have a certain definite property.

What one can talk about rigorously is the asymptotic density of numbers with the property, which is close to the intuitive-but-flawed concept of a definite probability for each integer. More generally, we can talk about the growth rate of the number of integers below $n$ with the given probability.

For example, if we prove that there are infinitely many integers with the property $P(n)$, we can express this as saying that the $P$-counting function grows faster than any constant function. (That does not sound like much, but it is at least something). Number theory contains various examples of properties where it is known that infinitely many examples exist but no concrete example has been found. An example are points where the difference between the prime-counting function and the logarithmic integral changes sign.

Another (somewhat contrived) example would be $P(n)\equiv$ "$n$ is a prime $>2^{2^{26}}$".

It's an interesting question what the largest non-contrived example is of a lower bound such that a natural property is known to have at least this density but no actual examples are known.

Depending on you standards on contrivance, the answer may be that even properties with an asymptotic density of 100% can have no known example, such as $P(n)\equiv$ "no Turing machine with $42$ states, when started on a blank tape, halts with exactly $n$ 1 squares on the final tape".

  • $\begingroup$ I dont think its that simple (ref first sentence). What if P(n)=There are exactly n twin primes. Isnt it conceivable that that both P(10^10^10^10) is true aswell as P(10^10^10^10+2) ? Or how about P(n)=Omega constant for hlating probabilities agree with the decimal expansion of pi on exactly n places, the decimals agreeing on place n is likely independent events, and it might be impossible to prove it isnt, so then we could assign a probability 1/10 that the decimals at some point agree. $\endgroup$ – TROLLHUNTER Oct 30 '11 at 17:57
  • $\begingroup$ My point was: If P(n) is not provable or disprovable, then what does "Each integer either has a property or it hasn't" mean? We have only heuristics then $\endgroup$ – TROLLHUNTER Oct 30 '11 at 19:42
  • $\begingroup$ Unless you're an intuitionist, $\forall n.P(n)\wedge \neg P(n)$ is always a theorem. We may not know what the probability of $P(n)$ being true is, but we do know it is either $1$ or $0$. Truth and provability are two different things; something can be true even if it isn't provable. $\endgroup$ – Henning Makholm Oct 30 '11 at 21:05
  • $\begingroup$ @Henning, a related post is here. $\endgroup$ – Did Nov 1 '11 at 10:35
  • 1
    $\begingroup$ @Henning: Don't you mean $\forall n ( P(n) \vee \neg P(n) )$? =) $\endgroup$ – user21820 Jan 4 '12 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.