2

Forgive the perhaps poor phrasing. This example is lifted from Scott Aaronson's Why Philosophers Should Care About Complexity Theory (pg. 9-10) and it poses an interesting question. Consider the two statements:

  1. 2^(43112609)-1 is prime.

We say this value is a "known" prime because we can prove it selects a unique positive integer and it's prime - but this is also true of:

  1. p' is the first prime larger than 2^(43112609)-1.

Most people's intuition suggests that 2^(43112609)-1 is a "known" prime whereas p' is "not known" - despite the fact we know p' exists and is prime (and we could, in principle, compute it).

(Aaaronson gives computational complexity reasons for the distinction, but that bypasses the issue since I suspect most of us would still have the known/unknown distinction even if p' could be computed in polynomial steps).

My question is, is the distinction just social, or is there a meaningful difference between the two expressions? Or is there an obvious distinction I'm missing? If it's not obvious, is there any writings on related problems or relevant writings on this question available?

  • Mathematicians distinguish explicit and implicit definitions. Explicit definition gives a construction of the object defined from ones already constructed, which 2^(43112609)-1 is an abbreviated way to do. Implicit definition only imposes a condition that the object has to satisfy without any construction of it (one may even be able to prove that such an object exists and is unique). Arguably, "the first prime larger than" is such an implicit condition. – Conifold Aug 25 '17 at 0:19
2

Let's restate the two expressions as

  1. p = 2n - 1 is prime
  2. p' is the first prime larger than 2n - 1

For small values of n, most people would say that both p and p' are known since we can readily compute the value of p'. However, as your example shows, this is not the case for larger values of n.

The question is: where does one draw the line? If both p and p' are known for n, but p' is unknown for n+1, what's so special about n.

This seemingly paradoxical situation is normally associated with vague predicates (wikipedia link). (For a more philosophical treatment see Vagueness (wikipedia link)).

So one distinction between the two statements may be that statement 2 is a vague predicate while statement 1 is not.

  • Some nit-picking: 2^n - 1 is not always prime. 16 - 1 = 3*5, 64 - 1 = 3*3*7. – Heinrich Aug 25 '17 at 11:38
  • @Heinrich That's right. Of course it is not always prime. A predicate is either true or false, depending on the value of the variables - in this case n. – Nick R Aug 25 '17 at 13:48
1

There are boundary cases where one may argue whether some number is "known" or not, but this is not one of them. Note that the number 2^(43112609)-1 is represented in binary by 43112609 consecutive 1's. That is: all binary digits of this number are known (and we don't need a lengthy computation to figure them out). Of course, you could insist of getting to know all decimal digits of this number, but mathematically there is nothing that warrants such a distingished position of the decimal encoding compared to the binary one.

On the other hand, we know barely nothing about p', except that it exists and that there are (rather expensive) ways to compute it.

0

There are (at least) four different meanings of "to be known" with respect to numbers.

1) All bits or digits representing the number can be given in some system.

2) All bits or digits representing the number can in principle (i.e. with unlimited time and memory space) be given in some system.

3) The numerical value can in principle be determined to every desired precision, but with an error larger than zero.

4) Two well-educated mathematicians understand the same by a phrase defining a number.

Examples:

The prime number 2^(43112609)-1 is of the first kind.

The next larger prime number is of the second kind.

The square root of 2 is of the third kind.

There are different variants for the fourth kind:

The greatest twin of prime numbers or the smallest odd perfect number. (Two mathematicians understand that these numbers perhaps do not exist.)

The second even prime number or the smallest positive fraction. (Two mathematicians understand that these numbers do not exist.)

Note: If transfinite set theory is true, then there are completely undefinable numbers, and they constitute the overwhelming majority of numbers.

0

Objects are said to be in scope when they are known. The former is a declaration the latter a method.

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.