14 ms·
Mathematicians Discover Prime Conspiracy (2016)
- dang 7y agoDiscussed at the time: https://news.ycombinator.com/item?id=11282480 https://news.ycombinator.com/item?id=11282480
- Terr_ 7y agoLOL, after posting my other reply I visited your link... and I just realized I repeated myself from 3 years ago. I'm not sure how to feel about that reminder of age.
- shul 7y ago.. or a reminder of consistency ?
- kristiandupont 7y agoTwo days ago I found an elaborate response to something I was researching on Reddit, only to discover at the bottom that I was the person who wrote it, 5 years ago. It's a weird feeling indeed!
- Already__Taken 7y agoI've been getting stack overflow answers every blue moon to my node proxy settings question for nearly 10 years. Weird feeling, it's nice to know we exist after we look away.
- Terr_ 7y agoI wonder if it's a some extension or variation on Benford's Law [0]. [0] https://en.wikipedia.org/wiki/Benford%27s_law https://en.wikipedia.org/wiki/Benford%27s_law
- lancebeet 7y ago>This conspiracy among prime numbers seems, at first glance, to violate a longstanding assumption in number theory: that prime numbers behave much like random numbers. Most mathematicians would have assumed, Granville and Ono agreed, that a prime should have an equal chance of being followed by a prime ending in 1, 3, 7 or 9 (the four possible endings for all prime numbers except 2 and 5). This seems like an odd assumption to me. Surely sexy primes are more common than twin primes, so at least for primes that are near each other there should be a higher probability for certain sequences of final digits. This is obviously not proof in itself, but it would certainly make me hesitate to assume there is an equal probability in the general case.
- soVeryTired 7y ago> Surely sexy primes are more common than twin primes, so at least for primes that are near each other there should be a higher probability for certain sequences of final digits. I think that's conjectural, but prime constellations are also conjectured to be a negligible fraction of primes as a whole, much as primes are a negligible fraction of integers (asymptotically). I think twin primes are conjectured to be distributed as n / (log n) ^2, while primes are n / (log n). Besides, even if (p, p + 6) is significantly more common than (p, p + 2), if the final digit of p is uniformly distributed among 1, 3, 7, and 9, I don't think the statistics as a whole are affected.
- blackrock 7y agoI always wondered if prime numbers can be used as the basis of a compression algorithm. Where you describe how to get your number, in relation to how it can be factored using prime numbers. You cut up your data into chunks, and then find the prime factors of each chunk. Now you have a list of arithmetic descriptions to describe your data, and you can use Huffman to compress the descriptions. Of course, this would be computationally intensive, for both the compressor, and the extractor, but it may save on the payload size, to allow for efficient data transfer. And while we still use Huffman’s algorithm, I wonder if advanced aliens may have discovered this technique for data compression. This is more of a sci-fi fantasy algorithm, than anything actually mathematically sound.
- Simon_says 7y agoThe prime factors of a number takes (about) the same amount of space to list as the number itself.
- saagarjha 7y agoNotably, even listing the ordinal index of the prime (e.g. that a number is the product of the first, fifth, and tenth primes) takes about the same amount of space as well due to the prime number theorem.
- yholio 7y ago> the average gap between consecutive prime numbers among the first N integers is roughly log(N) So if you are compressing exceptionally large numbers, say, a whole video file, which is likely to contain very long factors, you could shave log2(log(N)) bits for each factor of length N. Seems like the most impractical compression algorithm imaginable.
- Normal_gaussian 7y agoI would assume the intent is to use the fact that most numbers use the same prime factors as the encoding advantage. As in, you're transforming a list of dissimilar numbers into a list of similar ones.
- krick 7y ago> If Alice tosses a coin until she sees a head followed by a tail, and Bob tosses a coin until he sees two heads in a row, then on average, Alice will require four tosses while Bob will require six tosses (try this at home!), even though head-tail and head-head have an equal chance of appearing after two coin tosses. Ok, I verified on 10 000 tosses, it works, but I cannot see why. Can somebody explain? Edit: nevermind, it can be found in the previous discussion.
- vegizombie 7y agoFor anyone else interested, the way this was explained to me a while ago was to look at the failure mode after an H. For Alice, her failure for HT is HH, therefore her next flip can land on T, completing the sequence. For Bob, his failure mode is HT, so he now needs to flip a H before he can try for the 2nd H.
- boi4 7y agoRelated: https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm
- natmaka 7y agoRelated and well-known by software developers: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-sea...
- air7 7y agoI find number theory to be closer to a natural, investigative science akin to Physics rather than pure math such as calculus. IANAM, but I doubt there was ever a modern calculus theorem that was hinted by a brute force search. One can argue that Calculus is "made up" and thus research in this field is finding deeper logical consequences for the initial axioms, while natural numbers just "have properties" and research is Number Theory is trying to uncover these properties by brute force and later trying to prove them, arguably quite unsuccessfully so far. It's an interesting tidbit in the philosophical question of "Does math exist only in our head?"
- qubex 7y agoYour intuition is not all that wrong, but it’s not entirely correct either. Number Theory is basically the exploration of the deep consequences of a set of (ultimately arbitrary but apparently obvious) axioms. The exploration of those consequences arises from the fact that they are ultimately too plentiful, ramified, and incompletely provable (per Godel’s Incompleteness Theorems & Turing’s Halting Problem).
- rumanator 7y ago> Number Theory is basically the exploration of the deep consequences of a set of (ultimately arbitrary but apparently obvious) axioms. Isn't that true for all fields of pure math?
- chess93 7y agoAlmost all fields of pure math use a much stronger set of axioms called ZF and essentially everyone also accepts the axiom of choice (making it ZFC). The axioms in ZF are reasonable but the axiom of choice is surprisingly controversial for an axiom. There are some unintuitive consequences of the axiom but even more unintuitive consequences without it or with the negation of it. Number theory uses a much smaller set of axioms. It should be stated that most mathematicians don't really mind the logical foundations of their work when they are actually working in the same way that most programmers don't worry about assembly language or transistors.
- joantune 7y agoI wonder what the implications are for cryptography - given the heavy reliance on 'random' prime numbers but one would have to delve into this - and from the top of my head there are no algorithms that make you pick 'two consecutive' primes - so the implications - if any - aren't obvious - anyone here has some more light or other angles to shed into this?
- foo101 7y agoWhy would this have any implications on cryptography? This does not make factoring an RSA modules any easier.
- joantune 7y agoWell, in RSA you have to choose two prime numbers, multiply them, and keep them secret. p and q: pq =n . And n is made public. I wonder if this probability, maybe coupled with concrete implementations, makes it for a more restricted set of guessing p and q. That would be it. I guess that given that this only introduces 'restrictions' on sequential prime numbers, doesn't really help at all, given that p and q should be random. Unless there's a shortcut applied in implementation that you find a random p and then q is the next prime number. Hence my question to the community. But I only know that both RSA and DH rely on prime numbers.
- foo101 7y agoThat's a fair point. Yes, I thought the same thing too when I read this. It is only introducing restrictions on sequential prime numbers. I doubt it has any bearing on the factoring problem yet, at least not without more work that can connect this to the factoring problem.
- siliconunit 7y agoClassic example of following definitions or illustrious assumptions too closely... another one is an obvious one, and historically has been challenged a few times: the beginning of the prime sequence 'should be' 1, 3, 5.. very clean, very coherent, but it got stuck in definitions limbo and now we got no 1 and the alien 2, that has to be excepted in most algorithms..eh...
- lanna 7y agoWhy do you think 2 is alien? How could the fundamental theorem of arithmetic be stated without 2?
- ianai 7y ago2 is definitely no “alien”. More like a legendary prime god amongst countably infinite odd primes. 0 and 1 are two sides of an extreme that either generates a meaningful number system through their separation and extremis from one another or no system at all if 1=0 is assumed true. They’re like a Jekyl and Hyde god.
- lanna 7y ago"Odd" is just a word that means "not divisible by two". There is truly nothing special about a prime not being divisible by two. I could equally say "3 is a legendary prime god amongst countably infinite non-divisible-by-three primes", "5 is a legendary prime god amongst countably infinite non-divisible-by-five primes"... The only difference is that we do not have special words that mean non-divisible-by-three, non-divisible-by-five, etc. In this regard, I don't see 2 as a special prime. Saying "2 is the only even prime" is the same as saying "2 is the only prime divisible by two", which, by definition, can be said about any other prime.
- ianai 7y agoRight. In the language of the article, if p is a whole number whose digits end in the number 2 then all numbers after it ending in the digits 0 or 2 are not prime. It’s a seemingly weak statement but it says a much stronger thing about the primes than the hypothesis of the article. Anyway, just trying to react in tone to calling any number an “alien”. I think of numbers as being outside the realm of words like alien - I don’t even know what that would mean for a number. Hence my comment is hyperbole hinting at my love of mathematics. To me, it really is a beautiful area of study. Wish I could do it more.
- bmn__ 7y agopaper: "Unexpected biases in the distribution of consecutive primes" http://arxiv.org/abs/1603.03720 http://arxiv.org/abs/1603.03720 explanation for non-experts: "The Last Digit of Prime Numbers - Numberphile" https://www.youtube.com/watch?v=YVvfY_lFUZ8 https://www.youtube.com/watch?v=YVvfY_lFUZ8
- arberavdullahu 7y agoIs the Numberphile video based on the paper? Because the paper was out on 30 May 2016 and video was out on 4 May 2016
- bmn__ 7y agoRead the paragraph with the heading "Submission history".
- ngneer 7y agoNot sure I understand the significance of a last digit of 9 for a prime implying the next prime is likelier to end with a 1 and not a 9. After all, base 10 is arbitrary. Can someone explain whether similar such "conspiracies" occur for all bases?
- Tyr42 7y agoYeah, the article says they investigated in base 3 first. In that base, it can by 0, 1, or 2 mod 3 (for the final digit). Primes clearly aren't 0 mod 3, so all (not 3) primes end in 1 or 2. They found that primes "liked" to alternate between them.
- entwife 7y agoIn base 30, a prime greater than 30 can end in only 9 of the possible 30 terminal digits. In contrast with base 10, where this statistic is 4 of 10.
- ganzuul 7y agoAbstract: While the sequence of primes is very well distributed in the reduced residue classes (mod q), the distribution of pairs of consecutive primes among the permissible ϕ(q)2 pairs of reduced residue classes (mod q) is surprisingly erratic. This paper proposes a conjectural explanation for this phenomenon, based on the Hardy-Littlewood conjectures. The conjectures are then compared to numerical data, and the observed fit is very good. - https://arxiv.org/abs/1603.03720 https://arxiv.org/abs/1603.03720