by Bill Lauritzen
November 26, 2025
Abstract
Prime numbers exhibit well-understood global density patterns yet remain locally irregular and difficult to predict.
Although analytic number theory describes how primes are distributed on large scales,
it provides no method for determining the next prime after a given one.
This paper proposes a conjecture on the computational irreducibility of prime successors:
that any general algorithm for computing p(n+1) from p(n) must, in essence,
perform the full computational work required to inspect the intervening integers.
The conjecture is framed heuristically, with an emphasis on its conceptual motivation rather than formal model-specific lower bounds.
A related conjecture for highly composite numbers is noted as a direction for future research.
Version: v1.0 Status: Public preprint. Notes: Prepared for discussion and future formalization.
With the above conjecture as an inspiration, Ben Goertzel and I wrote the following paper and submitted it to arxiv.org on 23 January 2026. It was accepted on 14 May 2026.
by Ben Goertzel and Bill Lauritzen
You could view the paper and download a PDF on arxiv.org here.
Abstract
We develop a family of conjectures and theorems expressing the idea that the sequence of
prime numbers exhibits a form of computational irreducibility in the transition from one prime
to its successor. Informally, given a prime p, there is no general algorithm that can compute the
least prime greater than p substantially faster than sequentially testing candidate integers for
primality, except possibly on sparse sets of inputs.
Our framework proceeds along several complementary lines. First, we formalize Prime
Successor Irreducibility in a uniform Turing-machine complexity model (PSI-T), asserting lower
bounds on the running time of any algorithm computing prime successors relative to a natural
sequential baseline. Second, we propose a Kolmogorov-complexity formulation (PSI-K), which
asserts that typical prime gaps are algorithmically incompressible given the scale at which they
occur; we prove PSI-K(c,δ) unconditionally for all fixed c<1 using standard sieve upper bounds.
Third, we develop weakness-based formulations: PSI-W (sparse-set anti-concentration) shows
that no small “menu” of candidate gap values captures a noticeable fraction of primes, while
PSI-W-LE (logical entropy) shows that collision probabilities decay and logical entropy tends
to 1. These results extend to prime constellations and consecutive gap vectors. Finally, we
present a sieve-theoretic framework that connects local obstruction patterns to Selberg weakness
parameters, providing clean compositional bounds.
The PSI-K and weakness formulations connect irreducibility directly to classical statistical
questions about prime gaps. Using the relationship between Kolmogorov complexity and Shannon
entropy, we derive rigorous lower bounds on the entropy of prime gap distributions in dyadic
intervals [X,2X]. Together, these formulations provide a unified complexity-theoretic perspective
on the apparent local unpredictability of the prime sequence, without asserting randomness or
independence.
Conclusion
We have developed multiple complementary formalizations of Prime Successor Irreducibility:
1. PSI-T asserts running-time lower bounds for prime successor algorithms.
2. PSI-K asserts incompressibility of typical prime gaps given the scale; we prove PSI-K(c,δ)
unconditionally for all c<1.
3. PSI-W shows that no small menu of gap values can capture significant probability mass.
4. PSI-W-LE shows that collision probability decays, hence logical entropy tends to 1.
5. The local-to-Selberg weakness framework provides compositional sieve bounds.
These results extend to prime constellations and consecutive gap vectors. The combination of
operational and informational formulations offers a promising template for connecting computational
irreducibility with classical questions in number theory.
The unifying thread through the weakness formulations is the quantale-weakness framework intro-
duced in Section 2.6. By recognizing collision probability, menu bounds, and sieve-theoretic weakness
as instances of a single algebraic structure, we gain both conceptual clarity and compositional tools
for combining and extending these results.
Overall, while the results of this paper are technically involved and framed in statistical and
sieve-theoretic terms, they conceptually support the original motivating conjecture articulated by
Lauritzen, which was the inspiration for the lines of investigation taken: that despite large-scale
regularities in the distribution of primes, the task of identifying the immediate successor of a given
prime remains locally irreducible. That is, even when global structure is known, the information
needed to determine the next prime is typically not compressible beyond trivial scale information.
PSI-T expresses the strongest algorithmic form of this intuition, while PSI-K and PSI-W provide
rigorous, unconditional results that capture provably accessible consequences of it.