[keepamovin]

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.

[novaRom]

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]

> not even in NP

This is incorrect. Integer factorization is NP-intermediate. Very much “in NP”.

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#:~:tex....

[seanhunter]

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

    "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_factori...

[guhbkji]

You are conflating.

Integer factorization is unsolved and it’s decision problem is in NP.

IF’s decision problem’s complexity “may be in NP” because the question of whether P equalling NP is unknown.

Meaning IF is NP, but may well be P if P=NP. If P!=NP then IF is NP.

[klyrs]

No, IF is unquestionably in NP. The definition of NP is that a purported solution can be checked in polynomial time. That's it. Factorization can be verified by multiplication, in polynomial time, therefore the problem is in NP. Perhaps you're confounding NP with NPC? Recall that P is a subset of NP.

Not sure what you mean by "IF's decision problem" though. Primality is in P.

[keepamovin]

This! People get a bit confused by the classes: i have been. But they’re pretty simple, especially when explained like that.

Kinda funny tho we have a categorization system of problems to keep things organized and analogous, but there’s lots of confusion on how it sorts. Haha! :)

[keepamovin]

> 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! :)

[lmpdev]

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]

They’ve got the fundamental theorem of arithmetic. What more could they want?

[keepamovin]

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".

[woopsn]

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!

[odyssey7]

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]

> 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]

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.

[keepamovin]

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! :)

[zxcb1]

Why isn't this considered a solved problem?

https://en.wikipedia.org/wiki/Information_theory

https://en.wikipedia.org/wiki/Computational_irreducibility

https://en.wikipedia.org/wiki/Aperiodic_tiling

[sameoldtune]

I don’t understand how your links relate to primality.

[zxcb1]

Ask AI

https://x.com/stephen_wolfram/status/1762286847567495414

[timeinput]

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]

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