Prime Successor Irreducibility: Turing Machine Complexity, Kolmogorov Complexity, and Weakness-Based Formulations

Ben Goertzel; Bill Lauritzen

arxiv: 2605.12504 · v1 · pith:GBOELXWBnew · submitted 2026-01-23 · 💻 cs.CC · cs.AI

Prime Successor Irreducibility: Turing Machine Complexity, Kolmogorov Complexity, and Weakness-Based Formulations

Ben Goertzel , Bill Lauritzen This is my paper

Pith reviewed 2026-05-16 12:21 UTC · model grok-4.3

classification 💻 cs.CC cs.AI

keywords prime gapscomputational irreducibilityKolmogorov complexityTuring machinesieve boundsprime constellationslogical entropy

0 comments

The pith

No general algorithm finds the next prime substantially faster than sequential candidate testing, except on sparse input sets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops multiple formalizations of the claim that moving from a prime to its immediate successor is computationally irreducible. In a Turing-machine model this means no algorithm substantially beats the baseline of testing successive odd numbers for primality. A Kolmogorov-complexity version proves unconditionally that typical prime gaps are incompressible at their natural length using only standard sieve estimates. Weakness-based versions show that no small collection of gap sizes captures a positive fraction of all primes and that logical entropy of the gap distribution approaches its maximum. A reader would care because these statements tie the observed local unpredictability of primes directly to limits on compression and computation without invoking randomness.

Core claim

The prime successor function is irreducible: given a prime p, no general algorithm computes the least prime greater than p in time substantially better than the sequential baseline, except possibly on sparse sets. This is expressed in PSI-T as a lower bound on Turing-machine steps, in PSI-K as an unconditional proof that most gaps of size around log X in [X,2X] have Kolmogorov complexity at least c times their length for any fixed c<1, and in PSI-W as anti-concentration and entropy statements showing that gap values cannot be captured by any short menu.

What carries the argument

Prime Successor Irreducibility (PSI) formalized in three complementary ways—Turing-machine running-time lower bounds (PSI-T), Kolmogorov-complexity lower bounds on gaps (PSI-K), and weakness/anti-concentration measures (PSI-W)—that together bound the complexity of the next-prime map.

If this is right

Typical prime gaps in dyadic intervals carry Kolmogorov complexity close to their length, so no short program predicts them.
Prime-gap entropy in [X,2X] is bounded below by a positive fraction of the interval length.
No small finite menu of gap values accounts for a noticeable fraction of primes.
The same incompressibility statements extend to prime constellations and short vectors of consecutive gaps.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the incompressibility holds on average, then sieves or other arithmetic-progression methods cannot yield asymptotic speedups for next-prime computation outside sparse sets.
The statistical weakness measures supply a concrete link between prime-gap distribution and the absence of low-complexity shortcuts.
One could test the claim by searching for dense clusters where next-prime computation appears compressible and checking whether they remain sparse overall.

Load-bearing premise

Standard sieve upper and lower bounds on prime gaps suffice to prove that typical gaps are incompressible without hidden dense exceptions that would allow a fast general algorithm.

What would settle it

A dense infinite set of primes on which a single fixed algorithm computes the next prime using o(log p) bits of description or o(log p) steps on average would falsify the claim.

read the original abstract

We develop conjectures and theorems expressing the idea that the prime sequence exhibits computational irreducibility in the transition from one prime to its successor. Informally, given a prime pp p, no general algorithm can compute the least prime greater than pp p substantially faster than sequentially testing candidates for primality, except possibly on sparse input sets. Our framework proceeds along complementary lines. First, we formalize Prime Successor Irreducibility in a Turing-machine complexity model (PSI-T), asserting lower bounds on running time relative to a sequential baseline. Second, we propose a Kolmogorov-complexity formulation (PSI-K), asserting that typical prime gaps are algorithmically incompressible at their scale; we prove PSI-K(c, $\delta$) unconditionally for all fixed c<1 using standard sieve bounds. Third, we develop weakness-based formulations: PSI-W (sparse-set anti-concentration) shows no small menu of gap values captures a noticeable fraction of primes, while PSI-W-LE shows collision probabilities decay and logical entropy tends to 1. These extend to prime constellations and consecutive gap vectors. Finally, a sieve-theoretic framework connects local obstruction patterns to Selberg weakness parameters. The PSI-K and weakness formulations connect irreducibility to classical statistical questions about prime gaps. Using the relationship between Kolmogorov complexity and Shannon entropy, we derive rigorous lower bounds on prime gap entropy 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves an unconditional Kolmogorov bound on prime-gap incompressibility for c<1 and derives entropy lower bounds, but the Turing-machine claim stays conjectural with a sparse-set escape clause.

read the letter

The main new element is the trio of PSI-T, PSI-K, and PSI-W formulations for prime successor irreducibility, plus the unconditional proof of PSI-K(c, δ) for fixed c<1 via standard sieve bounds and the resulting lower bounds on prime-gap Shannon entropy in dyadic intervals. The weakness versions add anti-concentration over gap values and show logical entropy tending to 1, with extensions to constellations and consecutive gaps. These tie local obstruction patterns to Selberg-type parameters without claiming full randomness or independence. That connection between Kolmogorov complexity and entropy is handled cleanly and rests on classical results rather than circular definitions. The unconditional Kolmogorov and entropy pieces are the parts that actually hold up on their own terms. The Turing-machine lower bound remains conjectural and explicitly allows exceptions on sparse inputs, so the informal claim about no general algorithm computing the next prime much faster is qualified rather than absolute. The sieve-to-entropy step looks standard but would need checking for uniformity across the intervals. No load-bearing circularity or hidden parameters appear. This is for people already working at the intersection of algorithmic number theory and complexity who want a formal lens on why prime gaps resist simple prediction. A reader focused on Kolmogorov applications or gap statistics would extract usable ideas. The proven parts are grounded enough and the conjectures are stated plainly enough that it deserves referee time rather than a desk reject.

Referee Report

2 major / 2 minor

Summary. The paper introduces Prime Successor Irreducibility (PSI) as a complexity-theoretic perspective on the transition from a prime p to the next prime. It defines PSI-T (Turing-machine time lower bounds relative to sequential testing), PSI-K (Kolmogorov incompressibility of typical prime gaps, proved unconditionally for fixed c<1 via standard sieve bounds), and weakness-based variants PSI-W and PSI-W-LE (anti-concentration and logical entropy tending to 1). These are extended to constellations and gap vectors, with derived lower bounds on Shannon entropy of gaps in dyadic intervals [X,2X] via the Kolmogorov-Shannon relation.

Significance. If the unconditional PSI-K proof and entropy bounds hold, the work supplies a rigorous link between sieve theory and algorithmic incompressibility of prime gaps at natural scale, while explicitly allowing sparse-set exceptions. The weakness formulations connect to classical statistical questions about gap distributions. Credit is due for the parameter-free use of sieve bounds to obtain PSI-K(c, δ) and the entropy lower bounds.

major comments (2)

[Abstract, §2] Abstract and §2: The central informal claim (no general algorithm computes the least prime >p substantially faster than sequential testing, except on sparse sets) is not fully supported by the proved PSI-K statement alone; PSI-T appears to remain conjectural without explicit time lower bounds derived from the Kolmogorov or entropy results.
[§3] §3 (PSI-K proof): The step from standard sieve bounds to algorithmic incompressibility of typical gaps requires explicit verification that the resulting Kolmogorov lower bound holds uniformly outside sparse exceptions; the current sketch leaves open whether hidden pathologies in the sieve error terms could affect the δ parameter.

minor comments (2)

[§4] Notation for PSI-W-LE and logical entropy should be defined before first use in the weakness section to avoid forward references.
[§5] The extension to consecutive gap vectors is stated but lacks a concrete example or small-scale verification that would illustrate the anti-concentration claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the insightful comments on our manuscript. We appreciate the recognition of the unconditional PSI-K result and its connections to sieve theory. Below we address the major comments point by point, proposing clarifications and expansions where appropriate.

read point-by-point responses

Referee: [Abstract, §2] Abstract and §2: The central informal claim (no general algorithm computes the least prime >p substantially faster than sequential testing, except on sparse sets) is not fully supported by the proved PSI-K statement alone; PSI-T appears to remain conjectural without explicit time lower bounds derived from the Kolmogorov or entropy results.

Authors: We agree that the informal claim encompasses both the conjectural PSI-T (Turing-machine time lower bounds) and the proved PSI-K (Kolmogorov incompressibility). The PSI-K result provides unconditional evidence for the incompressibility of typical prime gaps, which intuitively supports the idea that no short description (hence no fast algorithm in some sense) exists for computing the successor prime in general. However, we acknowledge that explicit time lower bounds for Turing machines are not derived from PSI-K in the current manuscript, and PSI-T remains a conjecture. We will revise the abstract and §2 to explicitly distinguish the conjectural and proved parts, emphasizing that the informal claim is motivated by both but rigorously supported only in the Kolmogorov sense for the proved results. revision: partial
Referee: [§3] §3 (PSI-K proof): The step from standard sieve bounds to algorithmic incompressibility of typical gaps requires explicit verification that the resulting Kolmogorov lower bound holds uniformly outside sparse exceptions; the current sketch leaves open whether hidden pathologies in the sieve error terms could affect the δ parameter.

Authors: The proof of PSI-K(c, δ) relies on the fact that the sieve upper bounds (such as those from the Brun sieve or Selberg sieve) provide a uniform estimate for the number of primes in short intervals or with small gaps, with error terms that are o(π(x)) and thus affect only a sparse set of exceptions. The Kolmogorov lower bound is obtained by showing that if a gap were compressible below c log x, it would contradict the sieve density for most x. We believe the uniformity holds because the sieve bounds are effective and apply across the range without introducing non-sparse pathologies. To address the concern, we will expand §3 with a detailed lemma that explicitly bounds the exceptional set and verifies that the δ parameter remains unaffected by the error terms. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes PSI-K(c, δ) unconditionally for fixed c<1 by direct appeal to classical external sieve bounds, without defining any of its target quantities in terms of fitted parameters or prior self-results. The Kolmogorov-to-entropy step and the weakness formulations (PSI-W, PSI-W-LE) likewise rest on standard statistical and sieve-theoretic facts rather than on any internal reduction or self-citation chain. No load-bearing premise collapses to a definition or a fitted input by construction; the derivation chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The unconditional results rest on classical sieve bounds; no free parameters or invented entities are introduced in the abstract.

axioms (1)

standard math Standard sieve bounds apply to prime gaps in dyadic intervals
Invoked to prove PSI-K(c, δ) for all fixed c<1

pith-pipeline@v0.9.0 · 5582 in / 1260 out tokens · 62347 ms · 2026-05-16T12:21:00.550746+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We prove PSI-K(c, δ) unconditionally for all fixed c<1 using standard Selberg/Brun-type sieve upper bounds... wX ≪ log log(3X)/logX implying logical entropy ℓX→1
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat recovery and embed_strictMono unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

The unifying thread through the weakness formulations is the quantale-weakness framework... collision probability w(Hπ)=∑p(u)p(v)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages

[1]

Halberstam and H.-E

H. Halberstam and H.-E. Richert,Sieve Methods, Academic Press, 1974

work page 1974
[2]

Iwaniec and E

H. Iwaniec and E. Kowalski,Analytic Number Theory, American Mathematical Society, 2004

work page 2004
[3]

H. L. Montgomery and R. C. Vaughan,Multiplicative Number Theory I: Classical Theory, Cambridge University Press, 2006

work page 2006
[4]

Lauritzen,Prime Successor Irreducibility, https://earth360.com/ prime-successor-irreducibility.html

B. Lauritzen,Prime Successor Irreducibility, https://earth360.com/ prime-successor-irreducibility.html

work page
[5]

PhD thesis, Australian National University, 2021

Michael Timothy Bennett.How to Build Conscious Machines. PhD thesis, Australian National University, 2021. (Introduces the original concept of weakness as a measure of simplic- ity/generality for cognitive structures.)

work page 2021
[6]

Weakness is All You Need: Notes on Quantale Weakness as a Unifying Generalized- Occam Principle for Cognitive Science and AGI

Ben Goertzel. Weakness is All You Need: Notes on Quantale Weakness as a Unifying Generalized- Occam Principle for Cognitive Science and AGI. Unpublished manuscript, 2024. (Introduces quantale weakness as a mathematical framework for formalizing Occam-style preferences.) 22

work page 2024

[1] [1]

Halberstam and H.-E

H. Halberstam and H.-E. Richert,Sieve Methods, Academic Press, 1974

work page 1974

[2] [2]

Iwaniec and E

H. Iwaniec and E. Kowalski,Analytic Number Theory, American Mathematical Society, 2004

work page 2004

[3] [3]

H. L. Montgomery and R. C. Vaughan,Multiplicative Number Theory I: Classical Theory, Cambridge University Press, 2006

work page 2006

[4] [4]

Lauritzen,Prime Successor Irreducibility, https://earth360.com/ prime-successor-irreducibility.html

B. Lauritzen,Prime Successor Irreducibility, https://earth360.com/ prime-successor-irreducibility.html

work page

[5] [5]

PhD thesis, Australian National University, 2021

Michael Timothy Bennett.How to Build Conscious Machines. PhD thesis, Australian National University, 2021. (Introduces the original concept of weakness as a measure of simplic- ity/generality for cognitive structures.)

work page 2021

[6] [6]

Weakness is All You Need: Notes on Quantale Weakness as a Unifying Generalized- Occam Principle for Cognitive Science and AGI

Ben Goertzel. Weakness is All You Need: Notes on Quantale Weakness as a Unifying Generalized- Occam Principle for Cognitive Science and AGI. Unpublished manuscript, 2024. (Introduces quantale weakness as a mathematical framework for formalizing Occam-style preferences.) 22

work page 2024