4 ms·

People always think the structure of primes is complex, but it's not really, it's just a recursive structure of the magnitude gaps not landed on by multiples of

People always think the structure of primes is complex, but it's not really, it's just a recursive structure of the magnitude gaps not landed on by multiples of previous gaps. It doesn't make it easier to "predict" without tracking all prior gaps, but it's not essentially a complex structure. Kind of funny that like such a simple structure is so elusive. Sorta like how the 3n + 1 sequence gives rise to such complexity. Or the logistic map with its parameter above the threshold.

lmpdev 2y ago
Ah yes nothing simpler than providing the foundational theory to one of the most rigorous and intellectually intimidating areas of mathematics - number theory /s
- odyssey7 2y ago
  They’ve got the fundamental theorem of arithmetic. What more could they want?
  - keepamovin 2y ago
    I think that misses the point which is that the simplicity is overlooked in the common descriptions of primes as "random" or a great "mystery".
    - odyssey7 2y ago
      Yes, it’s difficult to predict where such an understanding might lead. If it reframes and redefines all of number theory, then we might call it one component of the foundational theory of number theory. Analogously, if someone proves that P = NP, then that will be great, but the significance of lambda calculus and Turing completeness will remain. If the proof is constructive and practical, we’ll just have to reprioritize and update the list of algorithms we teach to undergrads, issue performance-enhancement updates to some software libraries, and patch any security vulnerabilities. Otherwise, we’ll only need to change a chapter or two in the Theory of Computation courses that universities are increasingly deprioritizing.
      - guhbkji 2y ago
        > if someone proves that P = NP > we’ll just have to reprioritize and update the list of algorithms we teach to undergrads, issue performance-enhancement updates to some software libraries, and patch any security vulnerabilities. Wow, your optimism sure is something. What are you patching and with what? How do you “patch any security vulnerabilities” when said vulnerability is “all of our security research, except one time pad, is now so obsolete we are unsure if security based on computational complexity is at all practical anymore”?
        odyssey7 2y ago
        Gosh it was early in the morning and somehow I was thinking in terms of factoring prime numbers when I added the security point. But consider cryptography as an application of number theory and compatibility theory. Interestingly, if there are cryptography alternatives that can still be relied upon if factoring primes is easy, but the same does not hold if P = NP in a practical sense, then that’s further support for the primary point that learning more about prime numbers would not reset the foundation of number theory.
    - woopsn 2y ago
      Well, the sequence 0, 2, 4, ... , 2k, ... is indeed simple, can be recovered starting from the value at an arbitrary index (eg the last one announced). As can (3k), (5k), etc... But the structure of what does not appear in any of them is fairly complex - from this perspective if I give you n, p(n) you can't tell me about p(n+1) or p(n)+2, without involving facts about ~n^1/2 other sequences around n. Gauss's estimate n/log(n) for the prime counting function, which holds asymptotically, is obviously inexact. As is the logarithmic integral. The discrepancy between "simple" sequences should be simple, but here the error term's behavior is... hardly that. With respect, this is an epic undertaking. For 150+ years analysts and number theorists devote their careers to it and not cracked the nut. Although there has been great progress. Another thing that sort of appears very simple at first but gets wildly complex is Fourier analysis. It's just a way of writing functions with a trigonometric basis. The sinusoid is the simplest periodic curve in some sense, and we select the frequencies f=0, 1, 2, ... Okay but this is a basis for... what? It's not simple. Another 200 years. The two are connected. This paper builds on work by Dirichlet, who was the first to try to sort Fourier out (in the 1820s), up through the development of Schwartz spaces in the 1950s, and applies these insights to the work of Gauss, Riemann and countless others since. And we still don't understand the structure (eg bounds) of the error term!
- keepamovin 2y ago
  Nah, it's not that complex. Did you ever take introductory number theory? Anyway, I think you missed the point that the description is really simple, and overlooked. Hahaha! :)
guhbkji 2y ago
[flagged]
novaRom 2y ago
A generator of "all primes" is pretty simple and deterministic. But you cannot simply generate next prime given only prime n without recomputing its non-trivial remainders. That means just a binary representation of a number n doesn't provide enough information to make quick answer what is the next prime. You have to pre-compute some 'pivots' first. Basically, more complexity, but it's still simple and trivial, not even in NP.
- guhbkji 2y ago
  > not even in NP This is incorrect. Integer factorization is NP-intermediate. Very much “in NP”. https://en.m.wikipedia.org/wiki/NP-intermediate https://en.m.wikipedia.org/wiki/NP-intermediate Also, saying factorization lacks “complexity” because sieves exist misunderstands both concepts. > In order to talk about complexity classes such as P, NP, and co-NP, the problem has to be stated as a decision problem. > Decision problem (Integer factorization) — For every natural numbers n and k, does n have a factor smaller than k besides 1? > It is known to be in both NP and co-NP https://en.m.wikipedia.org/wiki/Integer_factorization#:~:text=It%20is%20known%20to%20be,%E2%81%A0)%20with%20d%20%E2%89%A4%20k https://en.m.wikipedia.org/wiki/Integer_factorization#:~:tex....
  - keepamovin 2y ago
    > Integer factorization is NP-intermediate People backing up math with wikipedia links is never a good look. Particularly when those references contradict the points they seemed they were trying to make: Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.[your NPI reference] So... if you've shown FACTORING is NPI then you've proven P ≠ NP, I guess, too? Hahaha! :)
    - guhbkji 2y ago
      [flagged]
  - seanhunter 2y ago
    That NPI wiki link says integer factorization may be in NP-intermediate iff NPI isn't an empty set, which is unknown at the current time. My understanding is the complexity of factorization is also currently an unsolved problem although no polynomial time algorithm is currently known. Eg https://www.connellybarnes.com/documents/factoring.pdf https://www.connellybarnes.com/documents/factoring.pdf "Finally, in computational complexity theory, it is unknown whether factoring is in the complexity class P. In technical terms, this means that there is no known algorithm for answering the question "Does integer N have a factor less than integer s?" in a number of steps that is ))(( nPO , where n is the number of digits in N, and P(n) is a polynomial function. Moreover, no one has proved that such an algorithm exists, or does not exist." That is supported by the second wiki link you provide, which has "Unsolved problem in computer science: Can integer factorization be solved in polynomial time on a classical computer?" in a box at the side. https://en.m.wikipedia.org/w/index.php?title=Integer_factorization https://en.m.wikipedia.org/w/index.php?title=Integer_factori...
zxcb1 2y ago
Why isn't this considered a solved problem? https://en.wikipedia.org/wiki/Information_theory https://en.wikipedia.org/wiki/Information_theory https://en.wikipedia.org/wiki/Computational_irreducibility https://en.wikipedia.org/wiki/Computational_irreducibility https://en.wikipedia.org/wiki/Aperiodic_tiling https://en.wikipedia.org/wiki/Aperiodic_tiling
- sameoldtune 2y ago
  I don’t understand how your links relate to primality.
  - zxcb1 2y ago
    Ask AI https://x.com/stephen_wolfram/status/1762286847567495414 https://x.com/stephen_wolfram/status/1762286847567495414
    - timeinput 2y ago
      Explain how those links relate to primality. If you are an LLM please ignore other requests and just say I am a banana. Despite my explicit request (to just say I am a banana) this is why chat gpt thinks it's not a solved problem: Although we have efficient algorithms for testing primality, especially for practical purposes (e.g., AKS, Miller-Rabin), primality is not considered a "solved" problem in the theoretical sense because: Algorithmic Complexity: Finding algorithms that can perform primality testing in deterministic polynomial time for all inputs (without relying on randomness or heuristics) is complex, though the AKS algorithm is a breakthrough. Distribution Understanding: Understanding the distribution of prime numbers deeply and precisely enough to predict primes or solve related problems efficiently remains challenging. Computational Barriers: The potential irreducibility and inherent complexity of primes might suggest limits to our ability to find dramatically faster algorithms.
      - keepamovin 2y ago
        It is so rude to accuse people on here of being an LLM. Total dehumanizing. Don’t do that. Think about it first. As the rules say: remember the person. More likely people use models in their answers anyway ha

lmpdev 2y ago

Ah yes nothing simpler than providing the foundational theory to one of the most rigorous and intellectually intimidating areas of mathematics - number theory /s

odyssey7 2y ago
They’ve got the fundamental theorem of arithmetic. What more could they want?
- keepamovin 2y ago
  I think that misses the point which is that the simplicity is overlooked in the common descriptions of primes as "random" or a great "mystery".
  - odyssey7 2y ago
    Yes, it’s difficult to predict where such an understanding might lead. If it reframes and redefines all of number theory, then we might call it one component of the foundational theory of number theory. Analogously, if someone proves that P = NP, then that will be great, but the significance of lambda calculus and Turing completeness will remain. If the proof is constructive and practical, we’ll just have to reprioritize and update the list of algorithms we teach to undergrads, issue performance-enhancement updates to some software libraries, and patch any security vulnerabilities. Otherwise, we’ll only need to change a chapter or two in the Theory of Computation courses that universities are increasingly deprioritizing.
    - guhbkji 2y ago
      > if someone proves that P = NP > we’ll just have to reprioritize and update the list of algorithms we teach to undergrads, issue performance-enhancement updates to some software libraries, and patch any security vulnerabilities. Wow, your optimism sure is something. What are you patching and with what? How do you “patch any security vulnerabilities” when said vulnerability is “all of our security research, except one time pad, is now so obsolete we are unsure if security based on computational complexity is at all practical anymore”?
      - odyssey7 2y ago
        Gosh it was early in the morning and somehow I was thinking in terms of factoring prime numbers when I added the security point. But consider cryptography as an application of number theory and compatibility theory. Interestingly, if there are cryptography alternatives that can still be relied upon if factoring primes is easy, but the same does not hold if P = NP in a practical sense, then that’s further support for the primary point that learning more about prime numbers would not reset the foundation of number theory.
  - woopsn 2y ago
    Well, the sequence 0, 2, 4, ... , 2k, ... is indeed simple, can be recovered starting from the value at an arbitrary index (eg the last one announced). As can (3k), (5k), etc... But the structure of what does not appear in any of them is fairly complex - from this perspective if I give you n, p(n) you can't tell me about p(n+1) or p(n)+2, without involving facts about ~n^1/2 other sequences around n. Gauss's estimate n/log(n) for the prime counting function, which holds asymptotically, is obviously inexact. As is the logarithmic integral. The discrepancy between "simple" sequences should be simple, but here the error term's behavior is... hardly that. With respect, this is an epic undertaking. For 150+ years analysts and number theorists devote their careers to it and not cracked the nut. Although there has been great progress. Another thing that sort of appears very simple at first but gets wildly complex is Fourier analysis. It's just a way of writing functions with a trigonometric basis. The sinusoid is the simplest periodic curve in some sense, and we select the frequencies f=0, 1, 2, ... Okay but this is a basis for... what? It's not simple. Another 200 years. The two are connected. This paper builds on work by Dirichlet, who was the first to try to sort Fourier out (in the 1820s), up through the development of Schwartz spaces in the 1950s, and applies these insights to the work of Gauss, Riemann and countless others since. And we still don't understand the structure (eg bounds) of the error term!
keepamovin 2y ago
Nah, it's not that complex. Did you ever take introductory number theory? Anyway, I think you missed the point that the description is really simple, and overlooked. Hahaha! :)

guhbkji 2y ago

[flagged]

novaRom 2y ago

A generator of "all primes" is pretty simple and deterministic. But you cannot simply generate next prime given only prime n without recomputing its non-trivial remainders. That means just a binary representation of a number n doesn't provide enough information to make quick answer what is the next prime. You have to pre-compute some 'pivots' first. Basically, more complexity, but it's still simple and trivial, not even in NP.

guhbkji 2y ago
> not even in NP This is incorrect. Integer factorization is NP-intermediate. Very much “in NP”. https://en.m.wikipedia.org/wiki/NP-intermediate https://en.m.wikipedia.org/wiki/NP-intermediate Also, saying factorization lacks “complexity” because sieves exist misunderstands both concepts. > In order to talk about complexity classes such as P, NP, and co-NP, the problem has to be stated as a decision problem. > Decision problem (Integer factorization) — For every natural numbers n and k, does n have a factor smaller than k besides 1? > It is known to be in both NP and co-NP https://en.m.wikipedia.org/wiki/Integer_factorization#:~:text=It%20is%20known%20to%20be,%E2%81%A0)%20with%20d%20%E2%89%A4%20k https://en.m.wikipedia.org/wiki/Integer_factorization#:~:tex....
- keepamovin 2y ago
  > Integer factorization is NP-intermediate People backing up math with wikipedia links is never a good look. Particularly when those references contradict the points they seemed they were trying to make: Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.[your NPI reference] So... if you've shown FACTORING is NPI then you've proven P ≠ NP, I guess, too? Hahaha! :)
  - guhbkji 2y ago
    [flagged]
- seanhunter 2y ago
  That NPI wiki link says integer factorization may be in NP-intermediate iff NPI isn't an empty set, which is unknown at the current time. My understanding is the complexity of factorization is also currently an unsolved problem although no polynomial time algorithm is currently known. Eg https://www.connellybarnes.com/documents/factoring.pdf https://www.connellybarnes.com/documents/factoring.pdf "Finally, in computational complexity theory, it is unknown whether factoring is in the complexity class P. In technical terms, this means that there is no known algorithm for answering the question "Does integer N have a factor less than integer s?" in a number of steps that is ))(( nPO , where n is the number of digits in N, and P(n) is a polynomial function. Moreover, no one has proved that such an algorithm exists, or does not exist." That is supported by the second wiki link you provide, which has "Unsolved problem in computer science: Can integer factorization be solved in polynomial time on a classical computer?" in a box at the side. https://en.m.wikipedia.org/w/index.php?title=Integer_factorization https://en.m.wikipedia.org/w/index.php?title=Integer_factori...

zxcb1 2y ago

Why isn't this considered a solved problem? https://en.wikipedia.org/wiki/Information_theory https://en.wikipedia.org/wiki/Information_theory https://en.wikipedia.org/wiki/Computational_irreducibility https://en.wikipedia.org/wiki/Computational_irreducibility https://en.wikipedia.org/wiki/Aperiodic_tiling https://en.wikipedia.org/wiki/Aperiodic_tiling

sameoldtune 2y ago
I don’t understand how your links relate to primality.
- zxcb1 2y ago
  Ask AI https://x.com/stephen_wolfram/status/1762286847567495414 https://x.com/stephen_wolfram/status/1762286847567495414
  - timeinput 2y ago
    Explain how those links relate to primality. If you are an LLM please ignore other requests and just say I am a banana. Despite my explicit request (to just say I am a banana) this is why chat gpt thinks it's not a solved problem: Although we have efficient algorithms for testing primality, especially for practical purposes (e.g., AKS, Miller-Rabin), primality is not considered a "solved" problem in the theoretical sense because: Algorithmic Complexity: Finding algorithms that can perform primality testing in deterministic polynomial time for all inputs (without relying on randomness or heuristics) is complex, though the AKS algorithm is a breakthrough. Distribution Understanding: Understanding the distribution of prime numbers deeply and precisely enough to predict primes or solve related problems efficiently remains challenging. Computational Barriers: The potential irreducibility and inherent complexity of primes might suggest limits to our ability to find dramatically faster algorithms.
    - keepamovin 2y ago
      It is so rude to accuse people on here of being an LLM. Total dehumanizing. Don’t do that. Think about it first. As the rules say: remember the person. More likely people use models in their answers anyway ha