Prime Factorization in Models of PV$_1$

1. Problema e Contesto

Il paper si inserisce nel campo dell'aritmetica limitata (bounded arithmetic), una famiglia di teorie del primo ordine che sono frammenti deboli dell'aritmetica di Peano e che hanno forti connessioni con la teoria della complessità computazionale.

Il problema centrale affrontato è la provabilità della fattorizzazione intera nella teoria PV1.

• PV1 è un'estensione della teoria di Cook (PV) che ammette l'induzione solo per predicati calcolabili in tempo polinomiale.
• È noto che teorie più forti, come $S^1_2$, possono dimostrare che ogni numero intero maggiore di 1 ha un divisore primo (e quindi una fattorizzazione in primi), utilizzando il principio di massimizzazione $\Sigma^b_1$-LMAX.
• Tuttavia, PV1 non possiede questo principio a meno che non si assuma $NP \subseteq P/poly$.
• Domanda aperta: PV1 (anche potenziata con lo schema di scelta fortemente limitata $BB(\Sigma^b_0)$) è in grado di dimostrare che ogni numero ha un divisore primo?

L'obiettivo dell'autore è dimostrare che, sotto un'ipotesi di complessità crittografica standard, la teoria PV1 non può provare l'esistenza di un divisore primo per ogni numero. Di conseguenza, esistono modelli di PV1 contenenti numeri "non standard" che non ammettono una fattorizzazione in primi.

2. Ipotesi Fondamentale

Il risultato si basa su un'ipotesi di durezza media della fattorizzazione contro avversari non uniformi:
Si assume che non esista una famiglia di circuiti booleani di dimensione polinomiale che possa fattorizzare una frazione costante di tutti i prodotti di due numeri primi di $n$ bit, per ogni $n$. In termini crittografici, questo significa che la fattorizzazione è difficile in media anche per algoritmi probabilistici non uniformi.

3. Metodologia e Strumenti Tecnici

L'autore utilizza una combinazione di strumenti di logica matematica e teoria della complessità:

• Teorema di Witnessing di KPT (Krajíček, Pudlák, Takeuti): Questo è lo strumento principale. Il teorema afferma che se una teoria come PV1 prova una formula della forma $\forall x \exists y \forall z \phi(x,y,z)$, allora esiste un algoritmo in tempo polinomiale (il "studente") che, interagendo con un "insegnante" (che fornisce controesempi), trova un valore corretto per $y$ dopo un numero costante di scambi.
• Protocolli Studente-Insegnante: L'autore formalizza l'interazione tra un algoritmo (studente) che tenta di trovare un divisore primo e un insegnante che risponde con informazioni parziali o controesempi.
• Campi di Insiemi (Fields of Sets): Per analizzare la struttura delle risposte dello studente, l'autore introduce il concetto di "numeri ovvi" (obvious numbers). Un numero è "ovvio" se la sua fattorizzazione in primi può essere derivata dalle fattorizzazioni dei numeri già visti (input e risposte precedenti) tramite unioni, intersezioni e complementi. Questi insiemi formano una struttura algebrica chiamata campo di insiemi.
• Analisi Combinatoria: Viene dimostrato che se lo studente non produce mai un numero "non ovvio", il numero di fattori primi distinti di un numero "ovvio" diminuisce troppo lentamente per permettere di isolare un singolo primo entro un numero costante di round.

4. Risultati Principali

A. Inprovabilità in PV1 (Teorema 3.10 e Corollario 3.11)

L'autore dimostra che, sotto l'ipotesi di durezza della fattorizzazione, la teoria PV1 non prova la frase:
$$\text{PrimeFactor: } (\forall x \ge 2)(\exists y \le x)(\text{y è un divisore primo di x})$$
La dimostrazione procede per assurdo:

1. Si assume che PV1 provi PrimeFactor.
2. Per il teorema di KPT, esisterebbe un algoritmo in tempo polinomiale (studente) capace di trovare un divisore primo interagendo con un insegnante.
3. L'autore costruisce un insegnante specifico che risponde in modo da mantenere i numeri dello studente "ovvi" il più a lungo possibile, impedendo la fattorizzazione completa.
4. Si dimostra che se lo studente riesce a trovare un divisore primo, deve necessariamente "rompere" una coppia di primi specifici in un numero costante di passi.
5. Questo comporterebbe l'esistenza di un algoritmo (o circuito) in grado di fattorizzare una frazione costante di prodotti di primi, violando l'ipotesi di complessità.

B. Estensione a PV1 + BB($\Sigma^b_0$) (Teorema 4.6)

Il risultato viene esteso alla teoria potenziata dallo schema di scelta fortemente limitata $BB(\Sigma^b_0)$.

• In questo contesto, lo studente può fornire sequenze di candidati invece di un singolo numero.
• L'autore definisce un "insegnante parallelo" e utilizza una variante del teorema di witnessing (di Cook e Thapen) che permette allo studente di outputtare più candidati.
• Attraverso un'analisi degli atomi nel campo di insiemi generato dalle risposte, si dimostra che anche con la scelta limitata, lo studente non può evitare di fallire nella fattorizzazione senza violare l'ipotesi di durezza.
• Conclusione: $PV1 + BB(\Sigma^b_0) \nvdash \text{PrimeFactor}$.

5. Significato e Implicazioni

• Esistenza di Modelli Non Standard: Per il teorema di completezza di Gödel, l'inprovabilità implica l'esistenza di un modello $M$ di PV1 (o PV1 + BB) che contiene un numero non standard $m$ tale che $m$ non ha fattorizzazione in primi in $M$. In altre parole, ogni divisore di $m$ ha un divisore proprio, ma non esiste un divisore irriducibile (primo) per $m$.
• Separazione delle Gerarchie: Il risultato fornisce una separazione tra teorie dell'aritmetica limitata basata su un'assunzione di complessità "naturale" (durezza della fattorizzazione) e non su assunzioni astratte sulla gerarchia polinomiale.
  • Si ottiene la catena di separazioni: $PV1 \prec PV1 + BB(\Sigma^b_0) \prec S^1_2$.
  • Questo mostra che $PV1 + BB(\Sigma^b_0)$ è strettamente più debole di $S^1_2$ (che prova la fattorizzazione) e che l'aggiunta dello schema di scelta non è sufficiente a recuperare la forza di $S^1_2$ per questo problema.
• Connessione con Domini di Furstenberg: Il risultato implica che esistono modelli di PV1 + BB che non sono la parte positiva di un dominio di Furstenberg (un dominio in cui ogni elemento non invertibile ha un divisore irriducibile).
• Domande Aperte: L'autore solleva questioni sulla possibilità di separare teorie più alte (come $T^1_2$) usando ipotesi simili e sulla relazione tra la fattorizzazione e il principio del piccione debole (Weak Pigeonhole Principle).

In sintesi, il paper stabilisce un legame rigoroso tra la difficoltà computazionale della fattorizzazione dei numeri interi e la forza logica delle teorie di aritmetica limitata, dimostrando che la capacità di fattorizzare non è una conseguenza logica delle proprietà di base dei numeri interi calcolabili in tempo polinomiale, a meno che la crittografia a chiave pubblica non sia fondamentalmente insicura.