The other day while discussing math, and primes specifically, the following question came to mind, and I figured I'd ask it here to see what people's opinions on it might be.
Main Question: Suppose that tomorrow someone proves that some function always generates (concrete) primes for any input. How should this affect lists such as the Largest Known Primes?
Let me give a little more detail to demonstrate why I feel this question is not entirely trivial or fanciful.
Firstly, the requirement that the function be able to concretely generate primes is meant to avoid 'stupid' examples such as Nextprime(n) which, given a 'largest known prime' P, yields a larger prime Nextprime(P). Note however that the definition of Nextprime does not actually explicitly state what this prime is, any implementation of it (in Maple or Mathematica for example) simply loops through the integers bigger than the input, testing each for primality in some fashion.
On the other hand, one candidate for such a function might be the Catalan sequence defined by:
$C(0) = 2$, $C(n+1) = 2^{C(n)}-1$
Although $C(5) = 2^{170141183460469231731687303715884105727}-1$ is far too large to test by current methods (with rougly $10^{30}$ times as many digits as the current largest known prime), and although the current consensus is that $C(5)$ is likely composite, it does not seem entirely out of the realm of possibility that someone might eventually find some very clever way of showing $C(5)$ is prime, or even that $C(n)$ is always prime, or perhaps some other concretely defined sequence.
The point is this: once one knows that every element of a sequence is prime, does this entirely negate things like the list of largest known primes? Or does the fact that $C(n)$ for $n\geq 5$ has too many digits to ever calculate all of them (instead only being able to calculate the first few or last few digits) mean that even if they were somehow proven prime it would not technically be 'known'?
Note also that in the realm of finite simple groups the analogous question is already tough to decide since there are infinite families of such groups known, but concrete descriptions (such as generators and relations or character tables) are not always available or even computable within reasonable time constraints. Likewise one could pose analogous questions in other branches (largest volume manifolds with certain constraints, etc.)
Anyhow, it seems like a reasonable question for serious mathematicians to consider, so I just want to hear what other's opinions are on the subject (and if anyone can think of a better title, feel free to suggest).
Best Answer
First of all, I don't think the idea that "knowing a prime requires knowing its decimal expansion" accords well with mathematical practice. Unless I'm mistaken, the largest known primes are all Mersenne primes, and (for good reason!) are almost always written in the form p=2k-1, not by their decimal expansions. Granted, the currently-known Mersennes are small enough that one could calculate their decimal expansions in Maple or Mathematica, if for some reason one wanted to. But even if that weren't the case (say, if k had 10,000 digits), I'd still be perfectly happy to describe p=2k-1 as a "known prime," provided someone knew both k and a proof that p was prime.
On the other hand, similar to what you suggested with your "NextPrime" function, what about
p := the 1010^10000th prime number ?
Certainly p exists, and one can even write a program to output it. But is p therefore "known"? Saying so seems to stretch the meaning of the word "known" beyond recognition.
Trying to arrive at some principled criterion that separates the two examples above, here's the best that I came up with:
An n-digit prime number p is "known" if there's a known algorithm to output the digits of p that runs in poly(n) time (together with a proof that the algorithm does indeed output a prime number and halt in poly(n) steps).
(Strictly speaking, the above definition covers "known-ness" for infinite families of primes, rather than individual primes -- since once you fix p, you can always output it in O(1) time. But this is a standard caveat.)
As far as I can see, the above definition correctly captures the intuition that a prime p is "known" if we know a closed-form formula for p (which can be evaluated in polynomial time), but not if we merely know a non-constructive definition of p (for which it takes exponential time to determine which p we're talking about).
A very interesting test case for my definition is
p := the first prime larger than 1010^10000.
According to my definition, the above prime is currently "unknown", but will become "known" if someone proves the conjecture that the spacing between two consecutive n-digit primes never exceeds q(n) for some fixed polynomial q.
If you accept my definition, then a "function that always generates primes" almost certainly would trivialize largest-prime contests, since presumably it would give a deterministic way to generate n-digit primes in nO(1) time, for n as large as you like (which is not something that we currently have).
Now, maybe there are cases where my definition fails to match up with "intuitive knowability" -- if so, I look forward to seeing counterexamples!