Prime Factorization in Models of PV$_1$

Resumen Técnico: Factorización de Números Primos en Modelos de PV1

1. Planteamiento del Problema

El artículo aborda un problema fundamental en la aritmética acotada (bounded arithmetic) y su conexión con la teoría de la complejidad computacional. El objetivo central es determinar si la teoría PV1 (una extensión de primer orden de la teoría PV de Cook, que formaliza el razonamiento sobre predicados de tiempo polinomial) es lo suficientemente fuerte para probar que todo número entero mayor o igual a 2 tiene un divisor primo.

• Contexto: Se sabe que teorías más fuertes, como $S^1_2$, pueden probar la existencia de factorización prima utilizando el principio de inducción $\Sigma^b_1$-LMAX (máximo). Sin embargo, PV1 carece de este principio a menos que $NP \subseteq P/poly$.
• La Conjetura: El autor investiga si, bajo supuestos de dureza criptográfica estándar (la dificultad promedio de la factorización), PV1 (incluso extendida con el esquema de elección acotada agudamente, $BB(\Sigma^b_0)$) no puede probar la existencia de un divisor primo para todos los números.

2. Metodología

El autor emplea una combinación de herramientas de lógica matemática y teoría de la complejidad para demostrar la independencia de la afirmación de factorización prima respecto a la teoría PV1.

• Teorema de Testigo KPT (Krajíček, Pudlák, Takeuti): Esta es la herramienta central. El teorema establece que si una teoría como PV1 prueba una sentencia de la forma $\forall x \exists y \forall z \phi(x,y,z)$, entonces existe un algoritmo de tiempo polinomial (el "estudiante") que, interactuando con un oráculo ("profesor"), puede encontrar un testigo $y$ en un número constante de pasos. Si el algoritmo falla, el profesor proporciona un contraejemplo.
• Protocolos Estudiante-Profesor: Se formalizan protocolos de interacción donde el "estudiante" intenta encontrar un divisor primo y el "profesor" responde con información que guía o refuta al estudiante.
• Campos de Conjuntos (Fields of Sets): Se utiliza una estructura algebraica (campos de conjuntos cerrados bajo unión, intersección y complemento) para analizar el conjunto de números "obvios" (aquellos cuya factorización prima puede derivarse de los números ya vistos en el protocolo mediante operaciones de GCD y división).
• Supuesto de Dureza: La demostración se basa en la hipótesis de que no existe una familia de circuitos booleanos de tamaño polinomial que pueda factorizar una fracción constante de todos los productos de dos primos de $n$ bits.

3. Contribuciones Clave y Resultados

A. Inpruabilidad en PV1 (Sección 3)
El autor demuestra que, bajo la hipótesis de dureza de la factorización, la teoría PV1 no prueba la sentencia PrimeFactor (que todo número tiene un divisor primo).

• Mecanismo: Se asume por contradicción que PV1 prueba la existencia de un divisor primo. Por el teorema KPT, esto implicaría la existencia de un algoritmo de tiempo polinomial (estudiante) que, interactuando con un profesor específico diseñado por el autor, encontraría un factor primo.
• El Profesor: Se define un profesor $t(p_1, \dots, p_d)$ que responde a las conjeturas del estudiante dividiendo los números propuestos de manera estratégica. El profesor utiliza la estructura de "números obvios" para forzar al estudiante a realizar una factorización no trivial.
• Resultado: Se prueba que si el estudiante no es capaz de romper la estructura de los "números obvios" (es decir, si no encuentra un factor no trivial), entonces no puede encontrar un divisor primo en un número constante de rondas. Esto contradice la existencia del algoritmo garantizado por el teorema KPT, a menos que la factorización sea fácil (lo cual contradice la hipótesis).

B. Extensión a PV1 + BB($\Sigma^b_0$) (Sección 4)
El resultado se extiende a la teoría PV1 + BB($\Sigma^b_0$), que incluye el esquema de elección acotada agudamente.

• Desafío: En esta teoría, el teorema de testigo KPT permite que el estudiante proporcione secuencias de candidatos (no solo un solo número) en cada paso.
• Solución: El autor define un "profesor paralelo" que responde a secuencias de divisores. Utilizando un lema sobre el crecimiento de los átomos en el campo de conjuntos de números obvios, demuestra que incluso con la capacidad de manejar secuencias, el estudiante no puede evitar la necesidad de realizar una factorización no trivial en un número constante de pasos.
• Conversión: Se convierte el protocolo paralelo en uno secuencial para aplicar nuevamente el teorema 3.10, demostrando que la existencia de un testigo en esta teoría más fuerte también implicaría un algoritmo de factorización eficiente, contradiciendo la hipótesis.

C. Consecuencias Model-teóricas

• Existencia de Modelos No Estándar: Por el teorema de completitud, si la teoría no prueba la existencia de un divisor primo, existe un modelo $M$ de la teoría que contiene un número no estándar $m$ que no tiene factorización prima en $M$.
• Dominios de Furstenberg: El resultado implica que existen modelos de $PV1 + BB(\Sigma^b_0)$ que no son la parte positiva de un dominio de Furstenberg (un dominio donde todo elemento no invertible tiene un divisor irreducible). Esto contrasta con los modelos de $S^1_2$, que sí son dominios de Furstenberg.

4. Significado e Implicaciones

1. Separación de Jerarquías de Aritmética Acotada:
   El trabajo proporciona una única suposición de complejidad (dureza de la factorización contra algoritmos no uniformes) que separa tres teorías consecutivas en la jerarquía de Buss:
   $$PV1 \subsetneq PV1 + BB(\Sigma^b_0) \subsetneq S^1_2$$
   Esto demuestra que la capacidad de probar la existencia de factorización prima es un punto de ruptura crítico entre estas teorías.

2. Conexión Profunda entre Criptografía y Lógica:
   El artículo refuerza la idea de que la dificultad computacional de problemas criptográficos (como la factorización) tiene consecuencias directas sobre qué principios matemáticos pueden ser formalizados en teorías de aritmética débil. Si la factorización es difícil, la aritmética débil no puede "ver" la factorización de todos los números.

3. Limitaciones de PV1:
   Se establece que PV1, incluso con la elección acotada, es insuficiente para garantizar la descomposición en factores primos, lo que sugiere que la inducción sobre predicados de tiempo polinomial es demasiado débil para capturar la estructura completa de los números primos sin asumir la existencia de algoritmos de factorización eficientes.

4. Preguntas Abiertas:
   El autor plantea si es posible separar teorías superiores (como $S^1_2$ de $T^1_2$) bajo suposiciones similares que no mencionen explícitamente clases de complejidad como la Jerarquía Polinomial, sugiriendo que la factorización podría ser la clave para entender la estructura de estas teorías más allá de $S^1_2$.

En resumen, el artículo demuestra rigurosamente que la dureza promedio de la factorización implica la inpruabilidad de la existencia de factorización prima en teorías de aritmética acotada que capturan el tiempo polinomial, revelando límites fundamentales en lo que estas teorías pueden probar sobre la estructura de los números enteros.