show/hide this revision's text 2 Fix as per comments

Edit: The question is whether a particular description first version 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 answer proposed 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 based on the knowability of very large numbers (generous, in that even the theoretical best timeKolmogorov complexity, logarithmic in the size of the numberbut as Scott Aaronson commented, this is not good enough to really describe truly large numbers; very restrictive , in that you might feel that since primes all have rather low complexity: primality not being able very hard to compute design an inefficient test for, the digits n'th prime $p_n$ has complexity at all is enough).

It does seem like saying "the most $10^{10^{10000}}$'th prime" is somehow cheating, though\log n \approx \log\log p_n$. It's too short! It's barely better than saying "It appears that prime, you know which one what I mean"had in mind was more or less what he wrote in his answer.Thus

However, I would like it seems to propose the criterion me that

An enumeration the issue of description complexity is part of what makes the question interesting: extremely large numbers should be expected to have extremely large complexity, for example "the number $2^n - 1$" or "and it is the n'th prime", generates "known" numbers if disparity between the Kolmogorov low complexity of some short description like C(5) and the decimal expansions high complexity of the numbers themselves is polynomial in the complexity digit string of C(5) itself which makes the corresponding descriptionsdescription seem not to be concrete. That is, there exists a polynomial p(c)More generally, depending only one may doubt the knowability of extremely large numbers on the enumeration, such grounds that for a particular description of complexity cthey cannot be written explicitly, as stated in the number it describes has complexity at most p(c)question.

That

So contrary to the claim that C(5) is , not a concrete description is "cheating" if it does not provide any significant information as to the identity of the a numberit specifies. Alas, Kolmogorov complexity seems rather nonconstructive as a criterion.

Note I think that my position due to its low complexity it is then that saying "the numbers C(n)much more concrete than its size would suggest, 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 its base-2 digits are easily listed; most numbers of its magnitude are wholly abstract and their digits in any base 2will never be known. In fact, where C(k + 1I am not entirely sure that a prime-enumerating algorithm which computes C(5) = ..." has basically the same complexity (both are linear in that time polynomial in C(4) (its number of n). On the other handbinary digits), "the n'th prime" is probably cheatingas Scott suggests, since even for $n = 2^k$is actually especially concrete, unless it takes an input significantly smaller than C(5) (note that C(5) is about the complexity of whose digits C(5)'th prime).

That isat most $\log k = \log \log n$, a computation may be efficient without being concrete. In the best way we have spirit of finding $p_n$ is just an exhaustive searchAlastair Litterick's answer, I'd like to suggest that

An algorithm for listing (some infinite family of) primes which is worse than linear efficient in n; $n = 2^{2^k}$ the sense of Scott's answer is even more extremealso "concrete" if the length of its output is superpolynomial in the length of its input.

Of course

More generally, a decent prime-listing algorithm I suppose it would improve this, though probably not enough make sense to be iterated-logarithmic. For this reasonquantify just how much larger the output is, I like Alastair Litterick's answerfor the purposes of probing very distant primes.
show/hide this revision's text 1 [made Community Wiki]

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.

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.