Variedad solución (I)

Durante este curso de máster que estoy haciendo me he ido empapando de una idea, todavía expresada de manera bastante vaga en mi cabeza, pero que me parece interesante. La idea consiste en que a muchos problemas se les puede asociar un objeto geométrico llamado comúnmente variedad solución. Esto permite, de manera bastante sistemática, aplicar técnicas geométricas al estudio de problemas en los que, en principio, no era completamente evidente cómo hacerlo. El otro día tuve una clase de la que disfruté mucho y que me dejó pensando durante un buen rato, uno de esos momentos en los que tu cerebro hace click y tienes la sensación de entenderlo todo mejor. Queriendo dejar constancia de esto en mi diario, tengo previsto escribir dos entradas: la de hoy, contando lo que entendí de la clase del otro día, y otra aplicándolas a un problema concreto: la demostración de una versión generalizada del Teorema Fundamental del Álgebra.

El tipo de problemas que trataremos serán aquellos descritos por la Lógica de Primer Orden. Una manera sencilla de definir la Lógica de Primer Orden es como un lenguaje formal generado por una gramática libre de contexto (como los lenguajes de programación). El alfabeto consiste en

• Constantes: $\{0,1\}$
• Variables: $\{X_n\ |\ n \in \mathbb{N}\}$
• Operaciones: $\{+,-,\cdot\}$
• Operadores booleanos: $\{\wedge,\vee,\neg\}$
• Cuantificadores: $\{\forall,\exists\}$
• Delimitadores: $\{(,),","\}$
• Relacionales: $\{=\}$

Las producciones de la gramática son

• Funciones polinomiales:

$$\langle Pol \rangle \longmapsto 0\ |\ 1\ |\ X_n,\ \ \ n \in \mathbb{N}$$
$$\langle Pol \rangle \longmapsto (\langle Pol \rangle \star \langle Pol \rangle),\ \ \ \star \in \{+,-,\cdot\}$$

• Átomos:

$$\langle At \rangle \longmapsto (\langle Pol \rangle = 0)$$

• Fórmulas libres de cuantificadores:

$$\langle QFF \rangle \longmapsto \langle At \rangle \ |\ (\langle QFF\rangle\ op\ \langle QFF \rangle),\ \ \ op \in \{\wedge,\vee\}$$

$$\langle QFF \rangle \longmapsto (\neg \langle QFF \rangle)$$

• Fórmulas bien formadas

$$\langle QF \rangle \longmapsto \langle QFF \rangle$$

$$\langle QF \rangle \longmapsto (\exists X_i, \langle QF\rangle)\ |\ (\forall X_i, \langle QF \rangle),\ \ \ i \in \mathbb{N}$$

Con esto ya tenemos la morfología y la sintaxis de los problemas, pero nos falta la semántica, la interpretación de las fórmulas. Una fórmula de primer orden (con algo de libertad sobre los paréntesis) es, por ejemplo,

$$\exists X_1, \exists X_2, X_1\cdot X_1 + X_2 \cdot X_2 + 1 = 0$$

y no tiene sentido hablar de si esta fórmula es "cierta" o "falsa" sin darle un significado a los símbolos. Una interpretación de la Lógica de Primer Orden en un anillo conmutativo y con unidad $(R,+,\cdot)$ consiste en considerar las variables como elementos del anillo y las operaciones como operaciones del anillo. Por ejemplo, la fórmula anterior es falsa sobre el anillo $(\mathbb{R},+,\cdot)$, pero es cierta sobre el anillo $(\mathbb{C},+,\cdot)$.

Una pregunta natural es la siguiente: dada una fórmula interpretada sobre un anillo, ¿es cierta? Es más, ¿existe un algoritmo que responda a esta pregunta? Uno de los ejemplos más famosos es el Problema X de Hilbert:

Problema: Dar un algoritmo que, con entrada un polinomio $p \in \mathbb{Z}[X_1, ..., X_n]$, decida si la fórmula

$$\exists X_1, ..., \exists X_n,\ p(X_1, ..., X_n) = 0$$

es cierta o no.

En otras palabras, el Problema X de Hilbert pide un algoritmo que decida si una ecuación polinomial con coeficientes enteros tiene solución o no. En un tiempo anterior a Turing, antes de que se formalizara el concepto de algoritmo, Hilbert no podía sospechar la respuesta encontrada en 1970:

Teorema: (Robinson, Matiyasévich): No existe tal algoritmo.

La interpretación de la Lógica de Primer Orden en el anillo de los enteros se llama Teoría Elemental de Números y desde hace casi 100 años se sabe que es incompleta (existen tautologías que no son teoremas) y que es indecidible (no existe un algoritmo que, con entrada una fórmula, decida si la fórmula es un teorema o no).

Consideremos ahora la interpretación de la Lógica de Primer Orden en un cuerpo finito $(\mathbb{F}_q,+,\cdot)$. Aquí el Problema X de Hilbert se lee:

Problema: Dar un algoritmo que, con entrada un polinomio $p \in \mathbb{F}_q[X_1, ..., X_n]$, decida si la fórmula

$$\exists X_1, ..., \exists X_n,\ p(X_1, ..., X_n) = 0$$

es cierta o no.

En este caso existe un algoritmo trivial para dar respuesta a la pregunta: como $\mathbb{F}_q$ tiene $q$ elementos, basta probar todas las combinaciones posibles y en a lo sumo $q^n$ evaluaciones habremos respondido a la pregunta. Aunque pueda parecer que un algoritmo de fuerza bruta, de complejidad exponencial en el grado del polinomio, es "poco elegante", no se sabe hacer mucho mejor porque se trata de un problema NP-completo: el problema anterior sobre $\mathbb{F}_2$ no es más que el problema SAT: el problema de satisfacibilidad booleana.

Para otros problemas parecidos también se intenta reducir la cuestión a explorar una cantidad finita de soluciones. Por ejemplo, una modificación del Problema X de Hilbert consiste en imponer una condición adicional sobre el polinomio $p$: que defina una variedad abeliana. Una varidad abeliana es una variedad algebraica con una estructura adicional de grupo abeliano, como las curvas elípticas, que son variedades abelianas de dimensión $1$.

Problema: Dar un algoritmo que, con entrada un polinomio $p \in \mathbb{Z}[X_1, ..., X_n]$ tal que $V(p)$ es una variedad abeliana, decida si la fórmula

$$\exists X_1, ..., \exists X_n,\ p(X_1, ..., X_n) = 0$$

es cierta o no.

Entre los Problemas del Milenio del Instituto Clay (los del millón de dólares) se encuentra en una forma parecida la siguiente conjetura

Conjetura (Birch y Swinnerton-Dyer): Existe una función $h = h(V,n)$, donde $V$ es una variedad abeliana y $n \in \mathbb{N}$, tal que si $V \cap \mathbb{Z}^n \neq \emptyset$, entonces existe $\zeta \in V \cap \mathbb{Z}^n$ con $\|\zeta\| \leq h$.

Es decir, que si la ecuación $p(X_1, ..., X_n) = 0$ posee soluciones enteras, alguna de esas soluciones se encuentra en la bola de centro el origen y radio $h$, por lo que, para responder a la pregunta anterior, basta evaluar todos los puntos con coordenadas enteras dentro de la bola y este conjunto es finito.

Una técnica algo más general para tratar de encontrar un algoritmo es la eliminación de cuantificadores: dada una fórmula bien formada $\mathcal{F}$, podemos suponer que $\mathcal{F}$ se escribe en forma prenexa (con una serie de variables cuantificadas al principio y una fórmula libre de cuantificadores al final):

$$\mathcal{F} = Q_1X_1, ..., Q_rX_r,\ \Phi(X_1, ..., X_r, X_{r+1}, ..., X_n)$$

$$Q_i \in \{\forall, \exists\},\ \ \ \Phi \in QFF$$

y queremos encontrar una fórmula $\mathcal{F}' = \Psi(X_{r+1}, ..., X_n)$ libre de cuantificadores equivalente a $\mathcal{F}$. Por ejemplo, en el anillo de matrices $n \times n$ con entradas reales, consideremos la fórmula

$$\exists B,\ A \cdot B = Id$$

¿Cómo es el conjunto de matrices $A$ para las que se satisface la fórmula anterior? Son las matrices invertibles, aquellas que tienen determinante distinto de cero. Por tanto, una fórmula equivalente a la anterior pero libre de cuantificadores es la siguiente:

$$\neg (det(A) = 0)$$

entendiendo que el determinante se puede expresar como una ecuación polinomial en las entradas de $A$. Las fórmulas libres de cuantificadores son útiles para hacer algoritmos: para saber si una matriz es invertible, hacemos unas cuentas para calcular su determinante y así podemos dar una respuesta. Observemos que las matrices invertibles son un objeto geométrico: el grupo lineal general, que es un grupo de Lie.

Pensemos ahora en el caso real. Dada una fórmula libre de cuantificadores $\Phi(X_1, ..., X_n)$ interpretada en el cuerpo de los números reales, ¿qué tipo de objeto geométrico podría ser

$$\{(x_1, ..., x_n)\in \mathbb{R}^n\ |\ \Phi(x_1, ..., x_n) = 0\}?$$

Haciendo los arreglos necesarios (técnicamente, expresando $\Phi$ en forma normal disyuntiva), podemos ver que $\Phi(X_1, ..., X_n)$ siempre puede interpretarse como un conjunto de ecuaciones polinomiales $p_i = 0$ y desigualdades polinomiales $q_j \neq 0$, por lo que el conjunto de puntos de $\mathbb{R}^n$ que satisfacen la fórmula $\Phi$ es siempre un conjunto localmente cerrado (intersección de un abierto y un cerrado). Consideremos por ejemplo el polinomio

$$p(X,Y) = XY - 1 \in \mathbb{R}[X,Y]$$

y la fórmula

$$\exists X, p(X,Y) = 0$$

¿Cómo podemos expresar el conjunto de los $y \in \mathbb{R}$ que satisfacen la fórmula anterior? Dado número real $y$, existe un número real $x$ tal que $xy = 1$ si, y sólo si, $y$ posee inverso multiplicativo, es decir, si y sólo si $y \neq 0$. Esto quiere decir que la fórmula anterior equivale a la fórmula libre de cuantificadores

$$Y \neq 0$$

Observemos algo curioso: el conjunto $S$ de puntos $(x,y) \in \mathbb{R}^2$ que satisfacen $xy - 1 = 0$ es la hipérbola representada en el siguiente dibujo:

Y el conjunto de puntos que satisfacen la fórmula libre de cuantificadores $Y \neq 0$ es $\pi_2(S)$, la proyección del conjunto $S$ sobre el eje $y$. Ahora cambiemos un poco el polinomio $p$. Digamos que

$$p(X,Y) = X^2Y-1$$

y sea la fórmula

$$\exists X,\ p(X,Y) = 0$$

Ahora el dibujo del conjunto $S$ de puntos $(x,y) \in \mathbb{R}^2$ que satisfacen $x^2y-1 = 0$ es el siguiente:

y, de nuevo, el conjunto de puntos $y$ para los que existe $x$ con $x^2y - 1 = 0$ es la proyección del conjunto $S$ sobre la componente $y$, es decir, que la fórmula libre de cuantificadores equivalente es

$$Y > 0$$

Sin embargo, esta forma libre de cuantificadores no es válida porque, recordemos, el símbolo $>$ no estaba en nuestro alfabeto. De aquí podemos sacar un par de conclusiones: que la eliminación de cuantificadores existenciales se identifica con la proyección de objetos geométricos y que, si queremos eliminar cuantificadores, a veces no basta con "$ = 0$" y "$\neq 0$", hace falta algo más.

La solución propuesta por A. Tarski fue seguir el esquema de la Lógica de Primer Orden, pero añadiendo el símbolo $>$ al alfabeto. De este modo, los objetos geométricos asociados a la interpretación de las fórmulas de la teoría de Tarski sobre las números reales son los subconjuntos de $\mathbb{R}^n$ definidos por igualdades polinomiales y desigualdades polinomiales con $> 0$. S. Łojasiewicz llamó a estos conjuntos conjuntos semialgebraicos y son hoy en día el objeto de estudio de la Geometría Algebraica Real. Tarski logró con su teoría dar un marco de trabajo bueno para los números reales:

Principio de Tarski: La Teoría de Primer Orden sobre cuerpos realmente cerrados (cuerpos como $\mathbb{R}$ y similares) es una teoría model-completa (toda tautología es un teorema), es decidible (existe un algoritmo que decide si una fórmula es un teorema) y admite eliminación de cuantificadores (toda fórmula bien formada es equivalente a una fórmula sin cuantificadores).

Tarski dio un algoritmo que, dada una fórmula (un sistema de igualdades y desigualdades polinomiales), devuelve otra fórmula equivalente libre de cuantificadores. Sin embargo, este algoritmo no es práctico porque su complejidad se expresa como una torre de exponenciales, lo cual no quiere decir que no tengamos fórmulas libres de cuantificadores para algunos casos sencillos. Por ejemplo, es bien sabido que dado un polinomio mónico

$$p(X) = X^2+bX+c \in \mathbb{R}[X]$$

la ecuación

$$p(X) = 0$$

posee solución si, y sólo si, $b^2-4c \geq 0$.

Para terminar, paramos en el caso complejo, donde no es necesaria la Teoría de Tarski y donde el Teorema de los Ceros de Hilbert puede expresarse en términos de las propiedades de la Lógica de Primer Orden interpretada en $\mathbb{C}$.

Teorema (Teorema de los Ceros de Hilbert): La Teoría de Primer Orden sobre cuerpos algebraicamente cerrados (con $= 0$ y $\neq 0$) es model-completa, es decidible y admite eliminación de cuantificadores.

Esto es, dados $f_1, ..., f_s \in \mathbb{C}[X_1, ..., X_n]$,

$$\exists (x_1, ..., x_n) \in \mathbb{C}^n,\ f_i(x_1, ..., x_n) = 0, \ \ \ i = 1, ..., s$$

es decidible por un algoritmo.

En la próxima entrada, que escribiré cuando tenga tiempo, pondré la demostración de una versión generalizada del Teorema Fundamental del Álgebra que saca partido del hecho de que se puede asociar un objeto geométrico a una fórmula de primer orden y se pueden reemplazar los cuantificadores existenciales por proyecciones. Concretamente, se trata de estudiar el conjunto

$$\mathcal{V} = \{(h,\zeta)\ |\ h(\zeta) = 0\}$$

cuando $h$ es un polinomio o un conjunto de polinomios y $\zeta$ es una tupla de números complejos o un conjunto de tuplas de números complejos.