Prime Factorization in Models of PV$_1$

1. Problématique et Contexte

L'article s'inscrit dans le domaine de l'arithmétique bornée, une famille de théories du premier ordre faibles de l'arithmétique de Peano, étroitement liées à la théorie de la complexité computationnelle.

• Théorie cible : L'auteur se concentre sur la théorie PV1, introduite par Krajíček, Pudlák et Takeuti (KPT91). PV1 est une extension de la théorie PV de Cook, caractérisée par une induction limitée aux prédicats décidables en temps polynomial. Son langage contient des symboles de fonction pour chaque algorithme de temps polynomial.
• Le problème central : La question de savoir si PV1 (et ses extensions faibles) peut prouver que tout entier $x \ge 2$ possède un diviseur premier. Formellement, il s'agit de prouver la sentence :
  $$\text{PrimeFactor} : (\forall x \ge 2)(\exists y \le x)(2 \le y \land y|x \land \text{y est premier})$$
• Contexte théorique : Il est connu que la théorie plus forte $S^1_2$ (qui admet l'induction pour les formules $\Sigma^b_1$) prouve l'existence d'un diviseur premier en utilisant le principe de maximisation ($\Sigma^b_1$-LMAX). Cependant, PV1 ne dispose pas de ce principe, sauf si $NP \subseteq P/poly$.
• Hypothèse de travail : L'auteur suppose l'hypothèse cryptographique standard selon laquelle aucune famille de circuits booléens de taille polynomiale ne peut factoriser une fraction constante de tous les produits de deux nombres premiers de $n$ bits (durabilité moyenne de la factorisation contre des adversaires non uniformes).

2. Méthodologie

La preuve de non-démontrabilité repose sur une combinaison de la théorie de la complexité et de la logique mathématique, utilisant principalement le théorème de KPT (Krajíček-Pudlák-Takeuti).

A. Le Théorème de KPT et les Protocoles Étudiant-Maître

Le théorème de KPT stipule que si une théorie comme PV1 prouve une sentence de la forme $\forall x \exists y \forall z \phi(x,y,z)$, alors il existe un algorithme de temps polynomial (l'« étudiant ») qui, en interaction avec un « maître » (qui fournit des contre-exemples), finit par produire un témoin valide pour $y$ après un nombre constant d'échanges.

L'auteur formalise cette interaction via des protocoles étudiant-maître :

1. L'étudiant ($s$) : Un algorithme de temps polynomial qui propose des candidats pour le diviseur premier.
2. Le maître ($t$) : Une fonction qui, si la proposition de l'étudiant est incorrecte, fournit une réponse (un diviseur partiel ou une information) pour corriger l'étudiant.

B. Construction du Maître et Analyse Combinatoire

Pour montrer que PV1 ne peut pas prouver PrimeFactor, l'auteur construit un maître spécifique $t(p_1, \dots, p_d)$ capable de simuler la factorisation d'un nombre $x = \prod p_i$ (produit de $d$ premiers distincts).

• Logique du maître : Le maître répond aux candidats de l'étudiant en utilisant des opérations de $\text{pgcd}$ et de division. Il définit des nombres « évidents » (obvious numbers) : ceux dont la factorisation peut être déduite des réponses précédentes par des opérations ensemblistes (unions, intersections, compléments).
• Champs d'ensembles (Fields of Sets) : L'auteur modélise l'ensemble des nombres « évidents » à chaque tour comme un champ d'ensembles. Il utilise des lemmes combinatoires (Lemmes 3.5 et 3.6) pour montrer que si l'étudiant ne produit pas de nombre « non évident » (c'est-à-dire un nombre dont la factorisation n'est pas déduite des réponses précédentes), la taille des « atomes » (ensembles minimaux non vides) dans ce champ diminue trop lentement.
• Le paradoxe : Pour que l'étudiant trouve un diviseur premier en un nombre constant de tours, il doit nécessairement produire un nombre « non évident ». Cependant, la construction du maître garantit que si l'étudiant produit un tel nombre, cela impliquerait l'existence d'un algorithme de temps polynomial capable de factoriser une fraction constante de produits de deux premiers, contredisant l'hypothèse cryptographique.

C. Extension à BB($\Sigma^b_0$)

L'article étend ce résultat à la théorie PV1 + BB($\Sigma^b_0$), qui inclut le schéma de choix borné strictement borné.

• L'auteur adapte le théorème de KPT (selon Cook et Thapen, CT06) pour permettre à l'étudiant de proposer plusieurs candidats simultanément (sous forme de séquences).
• Il définit un maître parallèle qui répond coordonnée par coordonnée.
• La preuve montre que même avec ce schéma de choix, la réduction du problème de factorisation à un nombre constant de requêtes échoue sous l'hypothèse de difficulté de la factorisation.

3. Résultats Principaux

1. Non-démontrabilité dans PV1 : Sous l'hypothèse de la difficulté moyenne de la factorisation, la théorie PV1 ne prouve pas que tout nombre a un diviseur premier.
   • Théorème 3.11 : $TPV \nvdash \text{PrimeFactor}$.
2. Non-démontrabilité avec le choix borné : Le résultat s'étend à la théorie augmentée du schéma de choix strictement borné.
   • Théorème 4.6 : $TPV + BB(\Sigma^b_0) \nvdash \text{PrimeFactor}$.
3. Existence de modèles non standards : Par le théorème de complétude de Gödel, il existe un modèle $M$ de PV1 (et de PV1 + BB($\Sigma^b_0$)) contenant un nombre non standard $m$ qui n'a pas de factorisation en nombres premiers dans ce modèle.
   • Dans ce modèle, tout diviseur de $m$ possède un diviseur propre, ce qui signifie que $m$ n'a pas de diviseur irréductible.
4. Séparation de la hiérarchie de Buss :
   • L'auteur combine son résultat avec celui de Cook et Thapen (qui montrent que PV1 $\nvdash$ BB($\Sigma^b_0$) sous une hypothèse similaire).
   • Cela établit une séparation stricte sous une seule hypothèse cryptographique :
     $$PV1 \subsetneq PV1 + BB(\Sigma^b_0) \subsetneq S^1_2$$
   • Cela signifie que l'ajout du schéma de choix strictement borné augmente réellement la puissance de preuve de PV1, mais reste insuffisant pour atteindre le niveau de $S^1_2$ concernant la factorisation.

4. Contributions Techniques Clés

• Formalisation des protocoles : L'auteur donne une définition formelle rigoureuse des protocoles étudiant-maître, permettant une manipulation précise dans le cadre de la preuve de non-démontrabilité.
• Utilisation des champs d'ensembles : L'application de la théorie des champs d'ensembles (fields of sets) pour analyser la croissance de la complexité des « nombres évidents » est une innovation méthodologique dans ce contexte.
• Réduction de la factorisation : La construction d'un algorithme qui, à partir d'un étudiant hypothétique prouvant PrimeFactor, extraireait un algorithme de factorisation efficace, reliant directement la logique à la complexité cryptographique.

5. Signification et Implications

• Limites de l'arithmétique bornée : Ce travail démontre que la capacité à prouver l'existence de diviseurs premiers (et par extension, la factorisation) est intrinsèquement liée à la puissance de l'induction et du choix dans les théories faibles. PV1 est trop faible pour capturer cette propriété arithmétique fondamentale sans hypothèses de complexité non prouvées.
• Lien Logique-Complexité : L'article renforce le lien entre les hypothèses de sécurité cryptographique (la difficulté de factoriser) et les limites de la démonstration formelle dans des systèmes faibles. Si la factorisation est difficile, alors certaines vérités arithmétiques de base sont indémontrables dans ces systèmes.
• Domaines de Furstenberg : Le résultat implique qu'il existe des modèles de PV1 + BB($\Sigma^b_0$) qui ne sont pas des « parties positives » de domaines de Furstenberg (domaines où tout élément non inversible a un diviseur irréductible). Cela contraste avec $S^1_2$, dont tous les modèles possèdent cette propriété.
• Questions ouvertes : L'auteur ouvre la voie à des questions sur la séparation de théories plus élevées dans la hiérarchie de Buss ($S^i_2$ vs $T^i_2$) et sur la relation entre la factorisation et le principe de la colombe faible injective (iWPHP).

En résumé, Ondřej Ježil démontre que la difficulté computationnelle de la factorisation des entiers se traduit directement par l'impossibilité pour des théories arithmétiques faibles (PV1 et ses extensions immédiates) de prouver l'existence de décompositions en nombres premiers, révélant ainsi des limites fondamentales de la puissance de preuve de ces systèmes.