Hacker News Reader

Comment by optimalsolver | Hacker News Reader

Is there a reason we're obsessed with primes beyond aesthetics? Why does this set of numbers garner all the headlines as opposed to some other arbitrary integer sequence like the Recamán numbers [0] ?

If tomorrow someone discovered a closed-form equation for the nth prime, how would mathematics/the world change?

[0] https://en.wikipedia.org/wiki/Recamán%27s_sequence

View on HN

Yes. Just within mathematics prime numbers have a tendency to show up in many fields not obviously related to number theory. As an example: in the study of symmetries (group theory [0]) important to number theory, geometry and even many parts of physics prime numbers help us decompose a complicated symmetry into simpler ones (using Sylow theorems [1].

Prime numbers are also used for cryptography due to their computational properties.

Also I think we have shown using a variant of Galois theory that there can not be a closed from solution for the nth prime.

But there are more headlines about the primes relative to its prevalence in research. I would guess that this is because - they can easily be explained to people - have been studied for thousands of years - open problems still persist

In other parts of research you might need at least an undergraduate degree just to understand the definitions, which makes headlines less sexy.

[0] https://en.wikipedia.org/wiki/Finite_group

[1] https://en.wikipedia.org/wiki/Sylow_theorems

I think it's about the fact that they are a mystery at the heart of maths. You can start describing maths from the unit, the addition and the negative sign. If you start combining those, you get the natural numbers, the integers, ... but even before the natural numbers come the prime numbers. Primes are the most fundamental set of numbers in mathematics, from which you can generate the natural numbers.

But as you say, even after so many years they are still relevant, useful and mysterious. They are on a wildly different category from other sets and numerical series. They are the most central element of maths that we still don't understand. And central means that so many other parts of maths derive from it, and therefore we end up coming across prime numbers everywhere. We use them to analyze so many other parts of maths, but yet they remain elusive to analysis themselves. It's a fundamental, recurrent mystery that's also an extremely useful tool... one of the most beautiful things we know.

> you get the natural numbers, the integers, ... but even before the natural numbers come the prime numbers. Primes are the most fundamental set of numbers in mathematics, from which you can generate the natural numbers.

I don't really see how you can define prime numbers before the natural numbers.

The set of natural numbers contains the prime numbers. The set of prime numbers doesn't contain the natural numbers, but every natural number > 1 can be generated/described as a product of prime numbers (fundamental theorem of arithmetic).

Maybe my terminology was incorrect, I'm not good at maths, but that's what I meant.

> Also I think we have shown using a variant of Galois theory that there can not be a closed from solution for the nth prime.

Do you have a reference? This sounds interesting.

There are, of course, integer polynomials where the set of positive values is precisely the set of primes (think something like x²(y+1)-(z+x)y, but much more complicated) [2].

(This might seem like an interesting fact, but it really is not. All sets of numbers where a computer can decide whether a number belongs to the set have such a polynomial.)

[2] https://en.wikipedia.org/wiki/Formula_for_primes

"Also I think we have shown using a variant of Galois theory that there can not be a closed from solution for the nth prime."

I don't think this is correct. For one, it is not clear what "closed form" would mean in this context. I think a reasonable variant would be "is there a polynomial time algorithm that, given n, outputs the nth prime." While my guess would be that the answer is no, I am certain that this is not known (and probably far, far out of reach).

Anyone else wondering more details:

https://www.quora.com/Is-finding-prime-numbers-in-P-or-NP

Interestingly the Polymath4 project in/around 2009 attempted to find such a polynomial algorithm.

Note that finding "a k-digit prime" is not the same as finding "the kth prime." I don't have any strong feelings either way about whether the former would be possible in polynomial time or not, but I would be pretty shocked if the latter were.

Reply on news.ycombinator.com