4
$\begingroup$

You have probably heard at some point statements like that the twin prime conjecture (namely that $2$ is an infinitely ocurring prime gap) is "probably" or "almost certainly" true. Same goes for a number of other problems in number theory asserting properties that we believe are satisfied by all natural numbers. An argument that seems to give ground to such beliefs is the observation that said conjecture holds up to a certain large number.

My question would be if there some solid argument to think that a given conjecture is "probably" true, given that we know it is true up to some large number (as big as you wish but fixed).

The answer upfront seems to be no, and still the thought is so unavoidable I wonder if someone has thought of an argument to justify it.

EDIT: Do not take the question rigurously. I was looking for a broad take on this. Think for example of the case of the twin prime conjecture. Of course I know there are properties satisfied by numbers only above a given number (for example the property of being bigger than said number). Be imaginative. Tell me results or arguments that you think might relate. Tell me about conjectures where, while not knowing if they hold, this line of thought is somehow justified and why.

EDIT $2$: Case where this question would apply. Let's say we conjecture some property of the natural numbers. About the size of a possible minimum counterexample we are not able to find anything besides that it must be greater than $10^{47}$. At this point the thought might reach our minds that the conjecture is "probably" true. Now, is there any convincing argument that justifies this thought?

$\endgroup$
7
  • 6
    $\begingroup$ I mean the conjecture that all numbers are less than $10^{48}$ is true if you only check up to $10^{47}$! $\endgroup$
    – Pax
    Nov 6, 2015 at 16:44
  • 3
    $\begingroup$ Good question. I think it doesn't have to do with the size but with the exhaustiveness. when people say the twin primes is true up to x. They don't mean they tried all numbers and stopped at x. They mean tried it for certain conditions that were true for all numbers up to x and probably many higher than x but starting at x there are conditions that we don't know how to resolve. But the conditions seem arbitrary and unrelated so we feel that the statement is probably universally true. $\endgroup$
    – fleablood
    Nov 6, 2015 at 16:53
  • 3
    $\begingroup$ Fairly often, the "probably true" assertion is based on more than merely holding at least up to $10^{47}$. Take for example the Goldbach Conjecture. There are heuristic arguments that it should at least be true from some point on, based on detailed technical estimates about the growth in the number of conceivable candidates for $p_1+p_2=2n$ as $n$ becomes very large. So there is reason to believe that counterexamples, if they exist, cannot be very large. $\endgroup$ Nov 6, 2015 at 17:02
  • 5
    $\begingroup$ Relevant: Examples of apparent patterns that eventually fail $\endgroup$
    – MJD
    Nov 6, 2015 at 17:09
  • 1
    $\begingroup$ I think @AndréNicolas has the key point. Unless you have some heuristic, at least, telling you where sporadic "accidental" counterexamples are likely to be found, or how likely any given number is to be an "systematic" counterexample, there's no finite number of checks that should give you any confidence that you've checked far enough. $\endgroup$
    – mjqxxxx
    Nov 6, 2015 at 18:31

8 Answers 8

13
$\begingroup$

No.

In fact, most positive integers are larger than $10^{47}$. An example of a property that is true for integers below $10^{47}$ but not true for integers larger than $10^{47}$ is being smaller than $10^{47}$.

A more apt but common example can be found in number theory. The number of primes up to $x$ is denoted by $\pi(x)$, and is commonly approximated by the logarithmic integral $$\text{Li}(x) = \int_2^x \frac{1}{\ln t}dt$$ Asymptotically, they are equal. It was believed for a long time that $\pi(n) < \text{Li}(n)$ for all $n$ (both Gauss and Riemann conjectured this). But it is not true. The first counterexample is thought to be somewhere around $10^{300}$.

$\endgroup$
3
  • 7
    $\begingroup$ $\pi(n) < \text {Li}(n)$ is a good non-trivial counter-example. But before we had discovered the first counter-example, would it have been an untrue are unreasonable for us to have said "this is probably true"? I guess, the real question is when is it reasonable to make such statements and how large a grain of salt do we take when we say "probably". I have an intuitive feel but I can't formalize. it. $\endgroup$
    – fleablood
    Nov 6, 2015 at 17:35
  • 4
    $\begingroup$ Would it have been untrue? Yes. Is it unreasonable? No, as I mention, two extremely famous and well-regarded mathematicians publically conjectrued that $\pi(n) < \text{Li}(n)$. $\endgroup$
    – davidlowryduda
    Nov 6, 2015 at 22:17
  • 1
    $\begingroup$ Okay, I'm nitpicking but I didn't ask if the statement was untrue. It obviously was, but would the statement "the statement is probably true" have been untrue. If I were to say today "the twin primes conjecture is probably true" would I be correct? If so, were someone to demonstrate tomorrow that it isn't, would that mean I was wrong at the time for having said it was probably true. $\endgroup$
    – fleablood
    Nov 7, 2015 at 7:33
13
$\begingroup$

I think everyone's being way too pessimistic. If someone handed me a statement $P(n), n \in \mathbb{N}$ about natural numbers and then showed me that $P(1)$ was true, $P(2)$ was true, $P(3)$ was true, etc. I think for "typical" $P$ I would become convinced that $P(n)$ was true way before $n = 10^{47}$. I mean, I've never seen $10^{47}$ pieces of evidence for anything I believe. I've only seen the sun rise about $10^4$ times and I totally believe that rising is a thing that the sun will keep doing.

Here's something I have in mind for a "typical" example. Letting $F_n$ denote the $n^{th}$ Fibonacci number (with $F_0 = 0, F_1 = 1$), we have

$$F_{n+1} F_{n-1} - F_n^2 = (-1)^n.$$

Or, well, maybe we don't. You might not know how to prove this, but you can verify it for as many values of $n$ as you like. How many values of $n$ do you think it would take before you'd be willing to bet that this is true with probability, say, 99%? I think for me I'd be convinced after something like $10$ examples, let alone $10^{47}$.

Of course there's an important difference between believing that something is probably true and having a proof of it, but there's a reason mathematicians talk about conjectures and not just about theorems: it's frequently possible to become convinced that a mathematical statement is true without being able to prove it, seeing it be true in a lot of examples is an obvious way this could happen, and mathematicians do this kind of reasoning all the time.

$\endgroup$
6
  • 2
    $\begingroup$ "I think everyone's being way too pessimistic" well, that's almost the definition of being a mathematician :-) From a pragmatic point of view it depends on how hard it is to verify the statement. By hand, checking 10 cases might take order of hour. Today it is reasonable to check perhaps thousands of cases by computer. In any case I believe if you can't refute in order of hours you might believe. In order of weeks strongly believe etc. Your mileage may vary.., $\endgroup$
    – dioid
    Nov 6, 2015 at 22:14
  • $\begingroup$ The difference seems to be between a mathematical or logical standard of proof and a standard scientific one. Will the book fall when I drop it? I would bet my life on it. Can I prove it absolute deductive logical certainty from the empirical evidence of all the times it has fallen before? No. $\endgroup$
    – Simon S
    Nov 6, 2015 at 22:45
  • 6
    $\begingroup$ You're 270 years old??? $\endgroup$
    – Asaf Karagila
    Nov 7, 2015 at 9:05
  • 1
    $\begingroup$ @Asaf: oops, off by an order of magnitude. $\endgroup$ Nov 7, 2015 at 17:57
  • 1
    $\begingroup$ And here I was hoping you got to know Euler and Gauss personally. :-P $\endgroup$
    – Asaf Karagila
    Nov 7, 2015 at 18:00
7
$\begingroup$

In some situations you can reasonably assign a "heuristic probability" to certain statements. See for example Terry Tao's blog post "The probabilistic heuristic justification of the ABC conjecture". If such heuristic calculations indicate that the probability of an example with $n \ge N$ is very small, and every $n < N$ has been checked without finding an example, you can take that as strong evidence that there is no such example.

On the other hand, there are cases such as the Wall-Sun-Sun primes. The heuristic calculations indicate that there should be infinitely many, but they should be very rare. Even though none has yet been found (for $n$ up to $2.8 \times 10^{16}$ at last report), I would not bet against the heuristic.

$\endgroup$
6
$\begingroup$

Well, here's a relevant fact:

Let $P(n)$ be a statement such that there exists a Turing machine which will halt and return false exactly when $P(n)$ is false. There exists some $m$, depending on the "complexity" of the Turing machine, such that if $P$ is true from $1$ to $m$, then it is true for all $n$.

Now, this $m$ is basically a busy beaver number. The problem with this truth is threefold: firstly, $m$ is extraordinarily large (since lower bounds aren't hard to prove). Secondly, no given theory can put upper bounds on $m$ for complex enough Turing machines (since that would solve the halting problem). Lastly, not all statements $P$ are like this - for instance, it is not obvious how one could check whether, in the Collatz conjecture, a given $n$ eventually iterates to $1$. You can check whether it enters a cycle, but if it diverges, you can keep iterating forever and never know the ultimate fate of the number.


As is noted in Robert Israel's comments, we can make the same argument for statements $P$ in general; that is:

Let $P(n)$ be a statement. Then, depending on the "complexity" of it, if it is true for all $1$ to $m$ it is true for all $n$.

Where your notion "complexity" must have that only finitely many statements are of any given complexity (so, the number of characters needed to express it in some finite alphabet works). Then, each false statement $P$ has some minimum $m$ for which it is false. Taking the maximum of all these minimal $m$ over the set statements with counterexamples yields the above truth. However, the outlook here is even more bleak: this $m$ grows at least as fast as the last one. We couldn't prove (let alone compute) all upper bounds for $m$ before, so the situation now is even worse.

$\endgroup$
6
  • $\begingroup$ I think you also need that the Turing Machine doesn't return false if $P(n)$ is true. $\endgroup$
    – TonyK
    Nov 6, 2015 at 18:12
  • $\begingroup$ @TonyK Thanks. I've edited clarified this point. $\endgroup$ Nov 6, 2015 at 19:21
  • 1
    $\begingroup$ You don't need a Turing machine, just the law of the excluded middle. Either $P(n)$ is true for all $n$, in which case any $m$ will do, or there is some $n$ such that $P(n)$ is false, in which case take the first $m$ for which $P(m)$ is false. $\endgroup$ Nov 6, 2015 at 19:28
  • $\begingroup$ The real point here is that $m$ is not computable, even if you know a Turing machine that does what you describe. $\endgroup$ Nov 6, 2015 at 19:29
  • $\begingroup$ @RobertIsrael I added something to that effect. I'm not well-versed with logic, but it concerns me that this new $m$ is presumably dependent on the model*, but the old one is not (I think?). (*For instance, I believe if we work in ZFC, the statement $2^{\aleph_n}=\aleph_{n+1}$ could fail at arbitrary $n$ consistently, or be true everywhere - I can't think of a good statement from PA that has similar problems). Of course, we're probably not that interested in what non-standard models do, so it's mostly okay. $\endgroup$ Nov 6, 2015 at 20:01
4
$\begingroup$

There is no real reason to thing this. For example, here is a property that is true for all numbers up to $10^{50}$:

All numbers up to $10^{50}$ are smaller than $10^{51}.$

Or, if you want something more fancy,

All composite numbers smaller than $10^{50}$ have a prime divisor that is smaller than $10^{25}$.

You can think of infinitely many properties that will be true "up to" any number, but that does in no way mean that they are true in general.

$\endgroup$
2
$\begingroup$

We can't, because even though $10^{47}$ is a large number by everyday standards, there are still infinity many integers for which the result isn't known. Or to put it another way, the ratio of the number of remaining integers to $10^{47}$ is infinitely large; thus the proportion of integers for which the proposition is proved true is zero.

$\endgroup$
1
$\begingroup$

What should "probably true" mean? In order to exclude the trivial counterexamples a la $\forall n\colon n<10^{47}$, let us consider statements that have remained an open problem for a "significant time" (actually, zero seconds would be significant enough for those contrived counterexamples) and that were tested for a large range of numbers before an accepted proof (or disproof) emerged. Someone who observes that $P(n)$ holds for all $n$ they test may scratch their head look more intensely for the proof (or disproof) before publishing the numerical observation - and be it to avoid a facepalm experience. Such results cannot be counted because we can hardly tell after the fact if and how far the author had tested small cases (though typically way less than $10^{47}$).

So to obtain an estimate how likely a statement that is true for all $n<10^{47}$ is really true, we might summarize all historical cases of comparable nature:

  • What statements do we know that have been settled by now and that had significantly before that been tested up to a certain limit without finding a counterexample?
  • What percentage of these results were ultimately proven true/false/independent?

Unfortunately, I guess that we would almost only come up with few well-known cases:

  • a negative case is "$\pi(n)<\operatorname{Li}(n)$" as mentioned elsewhere
  • a positive case is Bertrand's postulate: it was tested up to $n=3000000$ by Bertrand before Chebyshev found a proof

Based on only these two data points our desired probability would be estimated to $\frac12$, thus not very encouraging. Any volunteers to solve Goldbach's conjecture to change the estimate to $\frac 23$ (or - heaven forbid - to $\frac13$)?

$\endgroup$
1
  • $\begingroup$ That's an interesting approach. $\endgroup$
    – Anguepa
    Nov 10, 2015 at 14:39
-1
$\begingroup$

$10^{10^{47}}$ have all digits at zero starting from unity up to the $10^{47th}$. Still, I advice you to verify one more step ;-)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .