4 ms·

Well you all heard the challenge. Who has got idle GPUs sitting around? Let's find the smallest base 10 widely digitally delicate prime! In all seriousness tho

Well you all heard the challenge. Who has got idle GPUs sitting around? Let's find the smallest base 10 widely digitally delicate prime! In all seriousness though, it's fascinating that we know this number exists but have no idea what it is. What a treasure hunt..

mpoteat 6y ago
I am unsure whether or not GPUs are good at work involving arbitrary precision numbers. My intuition was that they excelled at doing massively parallel operations for which accuracy is not a high concern. I would probably look into using some sort of large integer sieve if I were trying to search for an example. Thinking about it though, I am even unsure whether it is decidable that N is widely digitally delicate.
- ElderMillennial 6y ago
  Wide integer multiplication works fine on a GPU: Your number is broken up into 32-bit coefficients to 2^32 as a compounding power (sum over a_i * 2^32i) -- and then you can do it as tensor(ish) operations, if you fiddle with carry/mod steps in between to keep the coefficients the right size and partial results properly aligned.
rurp 6y ago
The fact that the existence of a type of number can be proven despite not finding a single example is very interesting and unintuitive to me as a non-mathematician.
- impendia 6y ago
  An example described in the article, and which comes from the same branch of analytic number theory, is Daniel Shiu's result that you can find arbitrarily long strings of primes in "any" arithmetic progression. (By "any" I mean any arithmetic progression a (mod m) where a and m don't share any common prime factor.) So, for example, there is a string of a billion consecutive primes, each of whose decimal expansions ends in a billion ones. In principle you could use the method to find it, possibly the first example would be around 10^(10^10) or so. The gateway to all of this is the quantitative form of Dirichlet's theorem on prime numbers in arithmetic progressions: given coprime a and m, there are infinitely many primes which are a (mod m). (So, in other words, Shiu's result with "just one prime".) In this case, we know asymptotically how many such primes there are, and we can get upper bounds on the error. The proof is highly non-constructive, and uses complex analysis applied to the so-called "L-functions". Using a variety of trickery ("sieve methods", "the circle method", etc.) this can then be leveraged into other interesting results.
- Blikkentrekker 6y ago
  Simple example: 1. We first prove there are infinitely many primes. 2. Assume the number of primes is finite. 3. Thus, there exists a number that is the product of all primes. 4. Thus, there exists a number that is one more than the product of all primes, let us call this number A. 5. A is larger than any prime, thus different from any prime, thus not a prime. 6. Thus, there is at least one prime that A can be divided by. 7. But by it's very definition as the product of all primes + 1, the remainder of dividing this number by any prime is 1. 8. Thus, A is divisible by no prime, and prime. 9. Contradiction follows from assumption 2, thus assumption is false. 10. There are thus infinitely many primes. 11. There are finitely many number below 10^10^10^10^10 12. Thus, there must at exist infinite primes above 10^10^10^10^10 I don't know any of these numbers, but showing that a contradiction can be derived from assuming that such a number not exist is the common way to do it.
- skissane 6y ago
  A (small) minority of mathematicians find it unintuitive too. Intuitionistic mathematics and constructivist mathematics say that if you can't construct an example of it you can't prove it exists. They don't accept a proof that "some X exists such that P(X) is true" as valid unless you can give an example of such an X. "Intuitionist" because it is based on an intuition widely shared by a lot of people, but mostly rejected by modern mathematics.
- tialaramex 6y ago
  In a way numbers are much worse than that. Imagine writing a number down as a decimal fraction, like 2.0 or 4.86. If when you do this, the digits go on forever and no digit (such as a zero or a three) appears much more or less often than the you'd expect at random, that number is called "normal in base 10". If that's true in every base, it's just called "normal". That doesn't sound very normal, probably no numbers you usually think about have these properties, why do mathematicians call them "normal"? Well, the mathematicians have proved that almost all real numbers are normal. It just turns out that we haven't the faintest idea how to find them and we never needed them for anything so we didn't notice how abundant they apparently are. We aren't even sure if some weird numbers we do know about are normal, Pi looks pretty normal, but we can't prove it is.

mpoteat 6y ago

I am unsure whether or not GPUs are good at work involving arbitrary precision numbers. My intuition was that they excelled at doing massively parallel operations for which accuracy is not a high concern. I would probably look into using some sort of large integer sieve if I were trying to search for an example. Thinking about it though, I am even unsure whether it is decidable that N is widely digitally delicate.

ElderMillennial 6y ago
Wide integer multiplication works fine on a GPU: Your number is broken up into 32-bit coefficients to 2^32 as a compounding power (sum over a_i * 2^32i) -- and then you can do it as tensor(ish) operations, if you fiddle with carry/mod steps in between to keep the coefficients the right size and partial results properly aligned.

rurp 6y ago

The fact that the existence of a type of number can be proven despite not finding a single example is very interesting and unintuitive to me as a non-mathematician.

impendia 6y ago
An example described in the article, and which comes from the same branch of analytic number theory, is Daniel Shiu's result that you can find arbitrarily long strings of primes in "any" arithmetic progression. (By "any" I mean any arithmetic progression a (mod m) where a and m don't share any common prime factor.) So, for example, there is a string of a billion consecutive primes, each of whose decimal expansions ends in a billion ones. In principle you could use the method to find it, possibly the first example would be around 10^(10^10) or so. The gateway to all of this is the quantitative form of Dirichlet's theorem on prime numbers in arithmetic progressions: given coprime a and m, there are infinitely many primes which are a (mod m). (So, in other words, Shiu's result with "just one prime".) In this case, we know asymptotically how many such primes there are, and we can get upper bounds on the error. The proof is highly non-constructive, and uses complex analysis applied to the so-called "L-functions". Using a variety of trickery ("sieve methods", "the circle method", etc.) this can then be leveraged into other interesting results.
Blikkentrekker 6y ago
Simple example: 1. We first prove there are infinitely many primes. 2. Assume the number of primes is finite. 3. Thus, there exists a number that is the product of all primes. 4. Thus, there exists a number that is one more than the product of all primes, let us call this number A. 5. A is larger than any prime, thus different from any prime, thus not a prime. 6. Thus, there is at least one prime that A can be divided by. 7. But by it's very definition as the product of all primes + 1, the remainder of dividing this number by any prime is 1. 8. Thus, A is divisible by no prime, and prime. 9. Contradiction follows from assumption 2, thus assumption is false. 10. There are thus infinitely many primes. 11. There are finitely many number below 10^10^10^10^10 12. Thus, there must at exist infinite primes above 10^10^10^10^10 I don't know any of these numbers, but showing that a contradiction can be derived from assuming that such a number not exist is the common way to do it.
skissane 6y ago
A (small) minority of mathematicians find it unintuitive too. Intuitionistic mathematics and constructivist mathematics say that if you can't construct an example of it you can't prove it exists. They don't accept a proof that "some X exists such that P(X) is true" as valid unless you can give an example of such an X. "Intuitionist" because it is based on an intuition widely shared by a lot of people, but mostly rejected by modern mathematics.
tialaramex 6y ago
In a way numbers are much worse than that. Imagine writing a number down as a decimal fraction, like 2.0 or 4.86. If when you do this, the digits go on forever and no digit (such as a zero or a three) appears much more or less often than the you'd expect at random, that number is called "normal in base 10". If that's true in every base, it's just called "normal". That doesn't sound very normal, probably no numbers you usually think about have these properties, why do mathematicians call them "normal"? Well, the mathematicians have proved that almost all real numbers are normal. It just turns out that we haven't the faintest idea how to find them and we never needed them for anything so we didn't notice how abundant they apparently are. We aren't even sure if some weird numbers we do know about are normal, Pi looks pretty normal, but we can't prove it is.