An Intuitionistic Glance at Primes

Technical Summary: An Intuitionistic Glance at Primes

Problem Statement
The paper addresses the proof-theoretic classification of positive integers into units, primes, and composites within the framework of intuitionistic logic (specifically Heyting Arithmetic, HA). While classical arithmetic treats these categories as mutually exclusive and exhaustive extensions, the paper investigates the distinct forms of evidence required to establish these properties constructively. The central problem is to formalize how "compositehood" (an existential claim) and "primality" (a universal refutation claim) function as decidable predicates when the search space is bounded, and to distinguish between the syntactic rules of a formal theory, the internal agreement of a model, and the semantic interpretation relative to the standard natural numbers $\mathbb{N}$.

Methodology
The author employs a constructive, proof-theoretic approach grounded in intuitionistic logic. The methodology proceeds through several layers:

1. Ternary Classification via Evidence Forms: The paper defines three predicates—Unit ($U$), Composite ($C$), and Prime ($P$)—based on specific evidence types:

   • $U(n)$: Evidence of equality $n=1$.
   • $C(n)$: Evidence of an interior factorization $n=ab$ with $a,b > 1$ (an existential witness).
   • $P(n)$: Evidence of $n > 1$ combined with a bounded refutation of every possible interior factorization (a universal negative).
     Because the domain of potential factors for any $n$ is finite and decidable, both $C(n)$ and $P(n)$ are shown to be decidable predicates.

2. Staged Block Presentations: To operationalize the bounded search, the paper introduces "staged block configurations." These are finite, ordered lists of candidate factor pairs. The paper analyzes the "defect" relations (omissions, duplications, ordering violations) that arise when extending these stages. It distinguishes between local inhabitation (a valid decision at a specific stage) and uniform totalization (a global selector for all stages).

3. Euclidean Escape and Sieves: The paper utilizes a constructive variant of Euclid's argument ("Euclidean Escape") to demonstrate that no finite set of "catchers" (generators of composite numbers) can capture all composites. This leads to a recursive sieve construction where the least survivor of a finite catcher set is promoted to a new generator, effectively enumerating the primes.

4. Algebraic and Semantic Analysis: The paper examines the algebraic consequences of this classification, specifically the contrast between modular cancellation (for primes) and zero-divisor annihilation (for composites). It then moves to a semantic analysis, distinguishing between:

   • Rule Conformity: Syntactic verification of proofs.
   • Internal Multiplicative Agreement: The satisfaction of definitions within a fixed model.
   • Standard Definitional Agreement: The alignment of a theory with the standard structure $\mathbb{N}$, which requires metatheoretic representation.

Key Contributions and Results

• Decidability of Primality: The paper establishes that primality is a decidable property in HA because the universal quantifier in its definition is bounded by the input $n$. The distinction between prime and composite is one of "proof polarity" (existential witness vs. universal refutation) rather than arithmetical hierarchy complexity (both are $\Delta_0$).
• The Unit Boundary: A rigorous treatment of the unit ($1$) is provided, showing that the binary opposition $\neg P(n) \to C(n)$ fails at $n=1$. The ternary classification $U(n) \lor P(n) \lor C(n)$ is proven constructively.
• Finite Catchers and Sieve Transition: It is proven that any finite set of composite generators misses some composites (specifically, the square of the least survivor). This mechanism drives a recursive sieve that generates the sequence of ordinary primes.
• Algebraic Characterization: The paper links the number-theoretic definition of primes to the algebraic property of cancellation in the ring $\mathbb{Z}/n\mathbb{Z}$. A number $n > 1$ is prime if and only if multiplication by any non-zero residue is injective.
• Semantic Hierarchy: The paper delineates a hierarchy of certification:
  1. Local Evidence: Finite witnesses or refutations for specific $n$.
  2. Model Agreement: The extension of predicates in a fixed model.
  3. Metatheoretic Representation: The assertion that a theory agrees with the standard $\mathbb{N}$.
     The paper demonstrates that while the local theory is a conservative extension of HA, establishing agreement with the standard model requires external metatheoretic data.
• Limits of Uniformity: The paper applies Rice's Theorem and Gödel's Second Incompleteness Theorem to show that while individual primality tests are decidable, uniform bilateral certification (producing proofs for both primality and compositeness for all $n$) or uniform completion bounds for halting problems carry computational strength equivalent to the halting oracle ($0'$).

Significance and Claims
The paper claims to provide a "proof-theoretic account" of the classification of integers, emphasizing that the distinction between primes and composites is structural and evidential rather than merely extensional.

• Intuitionistic Rigor: It argues that the "unit boundary" and the nature of bounded search are crucial for understanding the constructive content of primality. The paper clarifies that the "lack of interior factorization" for primes is not a negative infinity but a finite, exhaustive refutation.
• Separation of Levels: A primary contribution is the explicit separation of syntactic rule conformity, internal model satisfaction, and the representation of the standard structure. The paper asserts that "agreement with primes" is a relative notion dependent on the chosen metatheory and interpretation.
• Primes as "Mirage": In the conclusion, the paper offers a metaphorical characterization: relative to interior multiplication, composites form the positively generated image, while primes are the "holes" in that image. The paper claims that global conjectures about primes (like the Twin Prime Conjecture or Goldbach's Conjecture) ask for organization among these "holes" without supplying a positive generator for their distribution, highlighting a fundamental asymmetry in their constructive presentation.

The paper does not propose new algorithms for factoring or primality testing, nor does it claim to solve open conjectures. Instead, it offers a foundational analysis of how these concepts are constructed, verified, and interpreted within intuitionistic arithmetic, distinguishing what is provable internally from what depends on the standard interpretation of the natural numbers.