4 ms·

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

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 https://en.wikipedia.org/wiki/Recamán%27s_sequence

Jtsummers 5y ago
Your original link 404'd on me (you seem to have replaced it with a different one though). Here's the working Wikipedia link: https://en.wikipedia.org/wiki/Recamán%27s_sequence https://en.wikipedia.org/wiki/Recamán%27s_sequence
- optimalsolver 5y ago
  Thanks. I've edited the link.
X6S1x6Okd1st 5y ago
I'm not sure about a closed-form equation for the nth prime, but if integer factorization can be done in linear time then much of applied cryptography needs to be replaced.
- JJMcJ 5y ago
  None is known. Can't be a polynomial.
johnday 5y ago
The prime numbers are critical in cryptography. Almost all of our current digital security infrastructure is based on the concept of multiplying large numbers together modulo suitably big prime numbers. Any major step towards understanding them (such as a closed-form equation for primes) would have major mathematical knock-on effects which may or may not undermine these methods, or provide us with a basis for even stronger cryptographic mechanisms to make use of in the future.
- whatshisface 5y ago
  >Almost all of our current digital security infrastructure is based on the concept of multiplying large numbers together modulo suitably big prime numbers. That's not true of elliptic curves.
  - barbegal 5y ago
    Elliptic curve cryptography uses modulo of large prime numbers. Curve25519 uses 2^255 - 19 for example
kmill 5y ago
There are two main operations for whole numbers: addition and multiplication. A basic question is what are the "atoms". With respect to addition, the atom is 1, since every number can be written as a sum of 1's, and 1 isn't itself a nontrivial sum. With respect to multiplication, the atoms are the primes, where primes aren't nontrivial products. A cool thing about breaking a number into multiplicative atoms (the "prime decomposition") is that to multiply two numbers, you can just add up however many copies there are of each atom. Primes turn multiplication into addition in this way. In other words, each prime defines a sort of logarithm that measures the amount of that prime in a number, and knowing the "coordinate" in prime space is enough to determine the original number. Then one might wonder what is the relationship between primes and addition. When you add two numbers, the prime decomposition of the result seems to be dramatically different from the decompositions of the summands. But there are patterns, like how the sum of even numbers is even. The abc conjecture[1] has to do with one of these patterns. The relative order of the primes also is saying something about the relationship between addition and multiplication, since addition underlies how you compare two numbers. There are old results about the density of the primes as if they were following a random distribution. I'm not sure if there's any deep structure that Recamán's sequence has anything to do with. All that seems to be interesting about it is that it evades our capabilities of determining whether every number eventually appears. The Collatz conjecture is similar in this way, though it is further complicated by the fact that it mixes the structures of multiplication and addition. [1] https://en.wikipedia.org/wiki/Abc_conjecture https://en.wikipedia.org/wiki/Abc_conjecture Going deeper, in algebraic geometry, what you do is take various number systems (called "rings" -- the integers are an example of a ring) and pretend each element is a function that measures some scalar quantity about an associated space. It's a bold and wild idea. There is a process by which you can figure out what the points of this associated space are, and, at least for the integers, there is one point for each prime. If you think about an integer n as a function defined on this space, then the evaluation of n at the point p ends up being equal to n mod p. All I'm trying to say by bringing this up is that primes are not just aesthetic, they have deep significance, with many analogs in other kinds of mathematics.
jordigh 5y ago
> If tomorrow someone discovered a closed-form equation for the nth prime, how would mathematics/the world change? Btw, that kind of exists. There's a formula that produces nothing but prime numbers. It basically encodes sieving, and it coincidentally uses every letter of the English alphabet. https://en.wikipedia.org/wiki/Formula_for_primes#Formula_based_on_a_system_of_Diophantine_equations https://en.wikipedia.org/wiki/Formula_for_primes#Formula_bas...
mannerheim 5y ago
Beyond cryptography, there is the fundamental theorem of arithmetic, which plays an important role in encoding Gödel numbers in Gödel's theorem. In algebra, the integers mod p are a finite field (addition, subtraction, multiplication, and division are defined) if and only if p is prime. Primality in algebra also exists in a more general form with prime ideals. An ideal is the set of elements of a commutative ring in which any element of the ideal multiplied by any element of the ring is still in the ideal; there is a sort of 'closed' property. Even numbers form an ideal because if you multiply any number by an even number, you get an even number. For a prime ideal, if ab is in the ideal, a is in the ideal or b is (similar to how if a prime number divides ab, it divides a or b). They have a number of interesting properties. For example, for a ring homomorphism (a function from one ring to another that preserves relationships between elements of the two rings), the pre-image of a prime ideal is also a prime ideal.
MrStonedOne 5y ago
prime numbers let you abstract away parts of math that would normally require bruteforce to solve in the human mind. Remember finding the common denominator in school, or reducing fractions to their lowest form. both require guess work to do the normally taught way, but both can be achieved using prime factorization in a "set" way that resolves to a solution. I struggled in grade school to do fractions purely because of reducing and common denominators, but ended up tutoring people how to do them in college pre-algebra because thats when I learned about prime factors and what you can do with them. If i had learned algebra before basic fractions i likely wouldn't had needed to dropout of high school and get a ged.

Jtsummers 5y ago

Your original link 404'd on me (you seem to have replaced it with a different one though). Here's the working Wikipedia link: https://en.wikipedia.org/wiki/Recamán%27s_sequence https://en.wikipedia.org/wiki/Recamán%27s_sequence

optimalsolver 5y ago
Thanks. I've edited the link.

X6S1x6Okd1st 5y ago

I'm not sure about a closed-form equation for the nth prime, but if integer factorization can be done in linear time then much of applied cryptography needs to be replaced.

JJMcJ 5y ago
None is known. Can't be a polynomial.

johnday 5y ago

The prime numbers are critical in cryptography. Almost all of our current digital security infrastructure is based on the concept of multiplying large numbers together modulo suitably big prime numbers. Any major step towards understanding them (such as a closed-form equation for primes) would have major mathematical knock-on effects which may or may not undermine these methods, or provide us with a basis for even stronger cryptographic mechanisms to make use of in the future.

whatshisface 5y ago
>Almost all of our current digital security infrastructure is based on the concept of multiplying large numbers together modulo suitably big prime numbers. That's not true of elliptic curves.
- barbegal 5y ago
  Elliptic curve cryptography uses modulo of large prime numbers. Curve25519 uses 2^255 - 19 for example

kmill 5y ago

There are two main operations for whole numbers: addition and multiplication. A basic question is what are the "atoms". With respect to addition, the atom is 1, since every number can be written as a sum of 1's, and 1 isn't itself a nontrivial sum. With respect to multiplication, the atoms are the primes, where primes aren't nontrivial products. A cool thing about breaking a number into multiplicative atoms (the "prime decomposition") is that to multiply two numbers, you can just add up however many copies there are of each atom. Primes turn multiplication into addition in this way. In other words, each prime defines a sort of logarithm that measures the amount of that prime in a number, and knowing the "coordinate" in prime space is enough to determine the original number. Then one might wonder what is the relationship between primes and addition. When you add two numbers, the prime decomposition of the result seems to be dramatically different from the decompositions of the summands. But there are patterns, like how the sum of even numbers is even. The abc conjecture[1] has to do with one of these patterns. The relative order of the primes also is saying something about the relationship between addition and multiplication, since addition underlies how you compare two numbers. There are old results about the density of the primes as if they were following a random distribution. I'm not sure if there's any deep structure that Recamán's sequence has anything to do with. All that seems to be interesting about it is that it evades our capabilities of determining whether every number eventually appears. The Collatz conjecture is similar in this way, though it is further complicated by the fact that it mixes the structures of multiplication and addition. [1] https://en.wikipedia.org/wiki/Abc_conjecture https://en.wikipedia.org/wiki/Abc_conjecture Going deeper, in algebraic geometry, what you do is take various number systems (called "rings" -- the integers are an example of a ring) and pretend each element is a function that measures some scalar quantity about an associated space. It's a bold and wild idea. There is a process by which you can figure out what the points of this associated space are, and, at least for the integers, there is one point for each prime. If you think about an integer n as a function defined on this space, then the evaluation of n at the point p ends up being equal to n mod p. All I'm trying to say by bringing this up is that primes are not just aesthetic, they have deep significance, with many analogs in other kinds of mathematics.

jordigh 5y ago

> If tomorrow someone discovered a closed-form equation for the nth prime, how would mathematics/the world change? Btw, that kind of exists. There's a formula that produces nothing but prime numbers. It basically encodes sieving, and it coincidentally uses every letter of the English alphabet. https://en.wikipedia.org/wiki/Formula_for_primes#Formula_based_on_a_system_of_Diophantine_equations https://en.wikipedia.org/wiki/Formula_for_primes#Formula_bas...

mannerheim 5y ago

Beyond cryptography, there is the fundamental theorem of arithmetic, which plays an important role in encoding Gödel numbers in Gödel's theorem. In algebra, the integers mod p are a finite field (addition, subtraction, multiplication, and division are defined) if and only if p is prime. Primality in algebra also exists in a more general form with prime ideals. An ideal is the set of elements of a commutative ring in which any element of the ideal multiplied by any element of the ring is still in the ideal; there is a sort of 'closed' property. Even numbers form an ideal because if you multiply any number by an even number, you get an even number. For a prime ideal, if ab is in the ideal, a is in the ideal or b is (similar to how if a prime number divides ab, it divides a or b). They have a number of interesting properties. For example, for a ring homomorphism (a function from one ring to another that preserves relationships between elements of the two rings), the pre-image of a prime ideal is also a prime ideal.

MrStonedOne 5y ago

prime numbers let you abstract away parts of math that would normally require bruteforce to solve in the human mind. Remember finding the common denominator in school, or reducing fractions to their lowest form. both require guess work to do the normally taught way, but both can be achieved using prime factorization in a "set" way that resolves to a solution. I struggled in grade school to do fractions purely because of reducing and common denominators, but ended up tutoring people how to do them in college pre-algebra because thats when I learned about prime factors and what you can do with them. If i had learned algebra before basic fractions i likely wouldn't had needed to dropout of high school and get a ged.