Return to Answer

Fix as per comments

Source Link

edited Apr 26, 2011 at 19:47

7.3k
4
37
53

Edit: The question is whether a particular descriptionfirst version of this answer proposed a numbercriterion based on Kolmogorov complexity, but as Scott Aaronson commented, this is "concrete" enoughnot very restrictive since primes all have rather low complexity: primality not being very hard to considerdesign an inefficient test for, the number "known" from it; one could sayn'th prime $p_n$ has complexity at most $\log n \approx \log\log p_n$. It appears that thiswhat I had in mind was more or less what he wrote in his answer.

However, it seems to me that the issue of complexity is accomplished if wepart of what makes the question interesting: extremely large numbers should be expected to have locatedextremely large complexity, and it is the number precisely withindisparity between the linear orderinglow complexity of all numbers. For practical purposes, that means giving a decimal expansion some short description like C(or binary expansion, which is theoretically and computationally equivalent5). Although most and the high complexity of the other answers endorse some criterion like "the algorithm must outputdigit string of C(5) itself which makes the expansion in polynomial time"description seem not to be concrete. More generally, that seems either unnecessarily restrictive or unnecessarily generous depending on your position onone may doubt the knowability of veryextremely large numbers (generous, in that evenon the theoretical best timegrounds that they cannot be written explicitly, logarithmicas stated in the size ofquestion.

So contrary to the number,claim that C(5) is not good enougha concrete description of a number, I think that due to really describe truly large numbers; restrictiveits low complexity it is much more concrete than its size would suggest, and its base-2 digits are easily listed; most numbers of its magnitude are wholly abstract and their digits in that you might feelany base will never be known. In fact, I am not entirely sure that being able to compute thea prime-enumerating algorithm which computes C(5) in time polynomial in C(4) (its number of binary digits at all), as Scott suggests, is enoughactually especially concrete, unless it takes an input significantly smaller than C(5) (note that C(5) is about the C(5)'th prime).

It does seem like saying "the $10^{10^{10000}}$'th prime"That is somehow cheating, though. It's too short! It's barely better than saying "that prime, you know which one I mean"a computation may be efficient without being concrete. Thus In the spirit of Alastair Litterick's answer, I wouldI'd like to propose the criterionsuggest that

An enumeration of description of numbers,algorithm for example "the numberlisting $2^n - 1$" or "the n'th prime", generates "known" numbers if the Kolmogorov complexity of the decimal expansions(some infinite family of the numbers themselves) primes which is polynomialefficient in the complexitysense of the corresponding descriptions. ThatScott's answer is, there exists a polynomial p(c), depending only on also "concrete" if the enumeration, such that for a particular descriptionlength of complexity c,its output is superpolynomial in the number it describes has complexity at most p(c)length of its input.

That isMore generally, a description is "cheating" ifI suppose it does not provide any significant information aswould make sense to the identity of the number it specifies. Alas, Kolmogorov complexity seems rather nonconstructive as a criterion.

Note that my position is then that saying "the numbers C(n), where for all k we define $C(k + 1) = 2^{C(k)} - 1$ and C(0) = 2" is not cheating, since the obvious description "C(n - 1) 1's in base 2, where C(k + 1) = ..." has basically the same complexity (both are linear in that of n). Onquantify just how much larger the other hand, "the n'th prime"output is probably cheating, since even for $n = 2^k$, the complexity of whose digits is at most $\log k = \log \log n$, the best way we havepurposes of finding $p_n$ is just an exhaustive search, which is worse than linear in n; $n = 2^{2^k}$ is even more extreme.

Of course, a decent prime-listing algorithm would improve this, though probably not enough to be iterated-logarithmic. For this reason, I like Alastair Litterick's answerprobing very distant primes.

The question is whether a particular description of a number is "concrete" enough to consider the number "known" from it; one could say that this is accomplished if we have located the number precisely within the linear ordering of all numbers. For practical purposes, that means giving a decimal expansion (or binary expansion, which is theoretically and computationally equivalent). Although most of the other answers endorse some criterion like "the algorithm must output the expansion in polynomial time", that seems either unnecessarily restrictive or unnecessarily generous depending on your position on the knowability of very large numbers (generous, in that even the theoretical best time, logarithmic in the size of the number, is not good enough to really describe truly large numbers; restrictive, in that you might feel that being able to compute the digits at all is enough).

It does seem like saying "the $10^{10^{10000}}$'th prime" is somehow cheating, though. It's too short! It's barely better than saying "that prime, you know which one I mean". Thus, I would like to propose the criterion that

An enumeration of description of numbers, for example "the number $2^n - 1$" or "the n'th prime", generates "known" numbers if the Kolmogorov complexity of the decimal expansions of the numbers themselves is polynomial in the complexity of the corresponding descriptions. That is, there exists a polynomial p(c), depending only on the enumeration, such that for a particular description of complexity c, the number it describes has complexity at most p(c).

That is, a description is "cheating" if it does not provide any significant information as to the identity of the number it specifies. Alas, Kolmogorov complexity seems rather nonconstructive as a criterion.

Note that my position is then that saying "the numbers C(n), where for all k we define $C(k + 1) = 2^{C(k)} - 1$ and C(0) = 2" is not cheating, since the obvious description "C(n - 1) 1's in base 2, where C(k + 1) = ..." has basically the same complexity (both are linear in that of n). On the other hand, "the n'th prime" is probably cheating, since even for $n = 2^k$, the complexity of whose digits is at most $\log k = \log \log n$, the best way we have of finding $p_n$ is just an exhaustive search, which is worse than linear in n; $n = 2^{2^k}$ is even more extreme.

Of course, a decent prime-listing algorithm would improve this, though probably not enough to be iterated-logarithmic. For this reason, I like Alastair Litterick's answer.

Edit: The first version of this answer proposed a criterion based on Kolmogorov complexity, but as Scott Aaronson commented, this is not very restrictive since primes all have rather low complexity: primality not being very hard to design an inefficient test for, the n'th prime $p_n$ has complexity at most $\log n \approx \log\log p_n$. It appears that what I had in mind was more or less what he wrote in his answer.

However, it seems to me that the issue of complexity is part of what makes the question interesting: extremely large numbers should be expected to have extremely large complexity, and it is the disparity between the low complexity of some short description like C(5) and the high complexity of the digit string of C(5) itself which makes the description seem not to be concrete. More generally, one may doubt the knowability of extremely large numbers on the grounds that they cannot be written explicitly, as stated in the question.

So contrary to the claim that C(5) is not a concrete description of a number, I think that due to its low complexity it is much more concrete than its size would suggest, and its base-2 digits are easily listed; most numbers of its magnitude are wholly abstract and their digits in any base will never be known. In fact, I am not entirely sure that a prime-enumerating algorithm which computes C(5) in time polynomial in C(4) (its number of binary digits), as Scott suggests, is actually especially concrete, unless it takes an input significantly smaller than C(5) (note that C(5) is about the C(5)'th prime).

That is, a computation may be efficient without being concrete. In the spirit of Alastair Litterick's answer, I'd like to suggest that

An algorithm for listing (some infinite family of) primes which is efficient in the sense of Scott's answer is also "concrete" if the length of its output is superpolynomial in the length of its input.

More generally, I suppose it would make sense to quantify just how much larger the output is, for the purposes of probing very distant primes.

Post Made Community Wiki

Source Link

created Apr 26, 2011 at 16:27

Ryan Reich

7.3k
4
37
53

An enumeration of description of numbers, for example "the number $2^n - 1$" or "the n'th prime", generates "known" numbers if the Kolmogorov complexity of the decimal expansions of the numbers themselves is polynomial in the complexity of the corresponding descriptions. That is, there exists a polynomial p(c), depending only on the enumeration, such that for a particular description of complexity c, the number it describes has complexity at most p(c).

Note that my position is then that saying "the numbers C(n), where for all k we define $C(k + 1) = 2^{C(k)} - 1$ and C(0) = 2" is not cheating, since the obvious description "C(n - 1) 1's in base 2, where C(k + 1) = ..." has basically the same complexity (both are linear in that of n). On the other hand, "the n'th prime" is probably cheating, since even for $n = 2^k$, the complexity of whose digits is at most $\log k = \log \log n$, the best way we have of finding $p_n$ is just an exhaustive search, which is worse than linear in n; $n = 2^{2^k}$ is even more extreme.

Of course, a decent prime-listing algorithm would improve this, though probably not enough to be iterated-logarithmic. For this reason, I like Alastair Litterick's answer.

Since the question declares itself to be philosophical, I also have some philosophical thoughts on its meaning. These don't address the question in the same way as above.

I think that the word "known" should be taken with a grain of salt even in the case of the current record largest prime, even if it were expressed in base-10 digits. Looking for record-size primes is an activity outside of mathematics, just like astronomers' search for extrasolar planets is outside of geology, though if we ever went to one, we could study it geologically. With a proof in hand that there are infinitely many primes, finding a particular one is useful only if we require specific numbers for some task, like cryptography, whose execution is not even a matter of computer science once it is implemented. This is not to say that the construction of a prime search is not a matter of both mathematics and computer science: for example, testing Mersenne primes is a strategy drawn from mathematics, since it is not known that there are infinitely many of those, and doing the testing efficiently is computer science. However, successful execution of the search is neither.

In contrast, knowing a prime, or anything, requires being able to answer questions about it; better, the questions should not have known general answers. For example, "is the last digit 3?" is a fine question, but that just asks for the residue modulo 10, and Dirichlet's theorem already describes the answer to that question statistically. One might be curious about the Chebyshev bias (which residue class has the most primes up to a certain size) but that can't be settled one way or another by looking at individual examples. On the other hand, even 2 is not fully understood as a prime, since we can't say modulo which primes it is a primitive root (implicitly, for example "the ones which are 5 mod 7"). This, like Mersenne primes, is another list not known to be infinite.

Aside from conjectures about individual primes that can be tested on specific numbers, there are statistical conjectures, similar in nature to Dirichlet's theorem, which are not settled and also can't be settled by a sparse prime search. For example, one might want to know whether a particular prime $p_n$ begins a maximal prime gap (larger than any preceding gap), for which the only possible computation is of an exhaustive list of primes up to and including $p_{n + 1}$.

Suppose, though, that we had an algorithm to generate a list of all primes, in order, giving all n-digit primes in provably polynomial time. We could still not verify the Riemann hypothesis in the form that $$\lvert \pi(x) - \operatorname{Li}(x) \rvert = O(x^{1/2} \log x)$$ unless we had a much deeper understanding of the behavior of that algorithm. Not knowing this, it would be unreasonable to say that the prime numbers are "known" as a set. And I don't think it's too high a standard to say that if all primes are "known", then the prime numbers are known as a whole.

In short, I don't think that any mere list of primes, finite or infinite, can constitute knowledge of its elements.