An Intuitionistic Glance at Primes

Résumé Technique : Un Regard Intuitionniste sur les Nombres Premiers

Énoncé du Problème
L'article traite de la classification proof-théorique des entiers positifs en unités, nombres premiers et composés au sein du cadre de la logique intuitionniste (spécifiquement l'Arithmétique de Heyting, HA). Alors que l'arithmétique classique traite ces catégories comme des extensions mutuellement exclusives et exhaustives, l'article étudie les formes distinctes de preuves requises pour établir ces propriétés de manière constructive. Le problème central est de formaliser comment la « compositionnalité » (une affirmation existentielle) et la « primalité » (une réfutabilité universelle) fonctionnent comme des prédicats décidables lorsque l'espace de recherche est borné, et de distinguer les règles syntaxiques d'une théorie formelle, l'accord interne d'un modèle et l'interprétation sémantique par rapport aux nombres naturels standards $\mathbb{N}$.

Méthodologie
L'auteur emploie une approche constructive et proof-théorique fondée sur la logique intuitionniste. La méthodologie procède par plusieurs couches :

1. Classification Ternaire via les Formes de Preuve : L'article définit trois prédicats — Unité ($U$), Composé ($C$) et Premier ($P$) — basés sur des types de preuves spécifiques :

   • $U(n)$ : Preuve de l'égalité $n=1$.
   • $C(n)$ : Preuve d'une factorisation intérieure $n=ab$ avec $a,b > 1$ (un témoin existentiel).
   • $P(n)$ : Preuve de $n > 1$ combinée à une réfutation bornée de toute factorisation intérieure possible (un négatif universel).
     Parce que le domaine des facteurs potentiels pour tout $n$ est fini et décidable, $C(n)$ et $P(n)$ sont démontrés être des prédicats décidables.

2. Présentations par Blocs Échelonnés : Pour opérationnaliser la recherche bornée, l'article introduit des « configurations de blocs échelonnés ». Ce sont des listes finies et ordonnées de paires de facteurs candidates. L'article analyse les relations de « défaut » (omissions, duplications, violations d'ordre) qui surviennent lors de l'extension de ces étapes. Il distingue l'inhabitation locale (une décision valide à une étape spécifique) de la totalisation uniforme (un sélecteur global pour toutes les étapes).

3. Évasion Euclidienne et Cribles : L'article utilise une variante constructive de l'argument d'Euclide (« Évasion Euclidienne ») pour démontrer qu'aucun ensemble fini de « capteurs » (générateurs de nombres composés) ne peut capturer tous les composés. Cela conduit à une construction de crible récursive où le plus petit survivant d'un ensemble fini de capteurs est promu à un nouveau générateur, effectuant ainsi l'énumération des nombres premiers.

4. Analyse Algébrique et Sémantique : L'article examine les conséquences algébriques de cette classification, notamment le contraste entre la annulation modulaire (pour les nombres premiers) et l'annihilation par diviseur de zéro (pour les composés). Il passe ensuite à une analyse sémantique, distinguant :

   • La Conformité aux Règles : Vérification syntaxique des preuves.
   • L'Accord Multiplicatif Interne : La satisfaction des définitions au sein d'un modèle fixe.
   • L'Accord de Définition Standard : L'alignement d'une théorie avec la structure standard $\mathbb{N}$, ce qui nécessite une représentation métathéorique.

Contributions Clés et Résultats

• Décidabilité de la Primalité : L'article établit que la primalité est une propriété décidable dans HA car le quantificateur universel dans sa définition est borné par l'entrée $n$. La distinction entre premier et composé est une question de « polarité de preuve » (témoin existentiel vs réfutation universelle) plutôt que de complexité de la hiérarchie arithmétique (tous deux sont $\Delta_0$).
• La Frontière de l'Unité : Un traitement rigoureux de l'unité ($1$) est fourni, montrant que l'opposition binaire $\neg P(n) \to C(n)$ échoue pour $n=1$. La classification ternaire $U(n) \lor P(n) \lor C(n)$ est prouvée de manière constructive.
• Capteurs Finis et Transition de Crible : Il est prouvé que tout ensemble fini de générateurs composés manque certains composés (spécifiquement, le carré du plus petit survivant). Ce mécanisme conduit un crible récursif qui génère la séquence des nombres premiers ordinaires.
• Caractérisation Algébrique : L'article lie la définition arithmétique des nombres premiers à la propriété algébrique de simplification dans l'anneau $\mathbb{Z}/n\mathbb{Z}$. Un nombre $n > 1$ est premier si et seulement si la multiplication par tout résidu non nul est injective.
• Hiérarchie Sémantique : L'article délimite une hiérarchie de certification :
  1. Preuve Locale : Témoins ou réfutations finis pour un $n$ spécifique.
  2. Accord du Modèle : L'extension des prédicats dans un modèle fixe.
  3. Représentation Métathéorique : L'assertion qu'une théorie concorde avec le $\mathbb{N}$ standard.
     L'article démontre que bien que la théorie locale soit une extension conservatrice de HA, établir l'accord avec le modèle standard nécessite des données métathéoriques externes.
• Limites de l'Uniformité : L'article applique le théorème de Rice et le second théorème d'incomplétude de Gödel pour montrer que si les tests de primalité individuels sont décidables, la certification bilatérale uniforme (produire des preuves pour la primalité et la composition pour tous les $n$) ou les bornes de complétion uniforme pour les problèmes d'arrêt possèdent une force computationnelle équivalente à l'oracle d'arrêt ($0'$).

Signification et Revendications
L'article prétend fournir un « compte proof-théorique » de la classification des entiers, en soulignant que la distinction entre nombres premiers et composés est structurelle et évidentielle plutôt que simplement extensionnelle.

• Rigueur Intuitionniste : Il soutient que la « frontière de l'unité » et la nature de la recherche bornée sont cruciales pour comprendre le contenu constructif de la primalité. L'article clarifie que l'« absence de factorisation intérieure » pour les nombres premiers n'est pas un infini négatif, mais une réfutation finie et exhaustive.
• Séparation des Niveaux : Une contribution primaire est la séparation explicite de la conformité aux règles syntaxiques, de la satisfaction du modèle interne et de la représentation de la structure standard. L'article affirme que « l'accord avec les nombres premiers » est une notion relative dépendant de la métathéorie et de l'interprétation choisies.
• Les Premiers comme « Mirage » : Dans la conclusion, l'article propose une caractérisation métaphorique : par rapport à la multiplication intérieure, les composés forment l'image générée positivement, tandis que les nombres premiers sont les « trous » dans cette image. L'article affirme que les conjectures globales sur les nombres premiers (comme la conjecture des nombres premiers jumeaux ou la conjecture de Goldbach) interrogent l'organisation parmi ces « trous » sans fournir de générateur positif pour leur distribution, mettant en évidence une asymétrie fondamentale dans leur présentation constructive.

L'article ne propose pas de nouveaux algorithmes pour la factorisation ou le test de primalité, et ne prétend pas résoudre de conjectures ouvertes. Au lieu de cela, il offre une analyse fondamentale de la manière dont ces concepts sont construits, vérifiés et interprétés au sein de l'arithmétique intuitionniste, distinguant ce qui est prouvable en interne de ce qui dépend de l'interprétation standard des nombres naturels.