Skip to main content
Post Made Community Wiki
Source Link
Johan Wästlund
  • 5.5k
  • 3
  • 28
  • 35

I don't think in principle a sharp line can be drawn between "known" primes such as $2^{43112609}-1$ (the current record), and on the other hand "unknown" but well-defined ones like the first prime larger than a given number.

As has already been pointed out, the current record prime is still small enough to count as known according to the naive idea that we know its decimal representation. It has a few million digits, and finding them requires little extra computer time compared to testing primality in the first place.

If this situation changes due to new methods for primality testing of huge numbers (say whose digits cannot even be stored in all the world's computer memory), I guess we will fall back on an intuitive notion of when a number is known.

It will be difficult to come up with a sharp definition of known-ness in terms of computational complexity, since one can find an $n$ digit prime in polynomial time (albeit not provably deterministically) and naturally the record primes will be in the range where the degree (or even the constant) of the polynomial is crucial.

Speculating about future development of number theory and primality testing, I think the consensus is that if $C(5)$ is proved prime tomorrow, it will go to the top of the list, whereas if someone establishes that $C(n)$ is prime for every $n$, the conclusion will be that infinitely many primes are known explicitly.

Another possibility is improved primality testing of general numbers. If arbitrary numbers could be tested for primality as efficiently as Mersenne numbers, then possibly the new world record primes would consist of fancy patterns of digits, spiced with secret encodings of geek humor.

The situation is in principle different for the record twin primes. The current record is $65516468355\cdot 2^{333333}\pm 1$, and as far as I understand, it is not rigorously known that there are any larger twin primes at all. If someone proved with some sort of sieve that an interval of larger numbers must contain a twin prime pair, then I guess the list of record twin primes would split into "explicitly" and "theoretically" known pairs.