¿Existen pruebas no constructivas de isomorfismo?

Question

Me interesan las pruebas de afirmaciones de la forma "Objetos finitos $A$ y $B$ son isomorfos" que no son constructivos, en el sentido de que la prueba no exhibe el isomorfismo real en cuestión.

Un requisito más fuerte (y especificado con mayor precisión) sería un caso en el que es computacionalmente fácil escribir una prueba, pero computacionalmente difícil extraer el isomorfismo dada la prueba, por ejemplo, una clase de grafos para los que uno puede generar fácilmente triples $(G,H,P)$ con $P$ una prueba de que $G$ y $H$ son isomorfas pero para las que no hay un algoritmo (conocido) eficiente para tomar en $(G,H,P)$ y devuelve una permutación de los vértices que presentan el isomorfismo.

Algunos ejemplos de cosas que encajarían, si existieran:

• (dar una prueba no constructiva de que) todos los objetos de tipo $X$ se especifican de forma única por sus valores en cinco medidas específicas; observe que $A$ y $B$ alinearse en todas esas medidas.

• La función fácil de calcular de los gráficos $f(G,H)$ resulta ser igual al producto, sobre todas las reetiquetas de $G$ del número de aristas en las diferencias simétricas entre los conjuntos de aristas de $H$ y la copia reetiquetada de $G$ . (Esto ocurre por alguna bonita cancelación algebraica o algo así, como la forma de calcular los determinantes en el tiempo $O(n^3)$ .) Ahora observamos que $f(G,H) = 0$ a través del cálculo directo, y concluyen que un reetiquetado sin ninguna diferencia con $H$ debe existir.

• Grupos $G$ y $H$ de orden $n$ especificados por sus tablas de multiplicación, puede demostrarse fácilmente que se incrustan como subgrupos de un grupo mayor $K$ que podemos clasificar y demostrar más fácilmente las cosas. Pero la existencia de dos subgrupos no isomorfos de orden $n$ en $K$ implicaría algo sobre sus subgrupos Sylow que sabemos que es falso.

¿Hay buenos ejemplos de este fenómeno? ¿Razones para pensar que no ocurre? También me interesaría que me indicaran la bibliografía sobre temas relacionados.

Answer 1

El ejemplo más sencillo que conozco: la existencia de raíces primitivas nos dice que si $p$ es un primo, entonces el grupo $(\mathbb{Z}/p\mathbb{Z})^{\times}$ de unidades $\bmod p$ es cíclico, por lo que es isomorfo a $C_{p-1}$ . Sin embargo, exhibir tal isomorfismo equivale a encontrar tal raíz primitiva, y la prueba no lo hace, ni proporciona realmente un algoritmo eficiente para hacerlo.

No sé cuál es la complejidad temporal de encontrar una raíz primitiva. El algoritmo probabilístico "obvio" es factorizar $p - 1$ y, a continuación, elija un $a \in (\mathbb{Z}/p\mathbb{Z})^{\times}$ y comprobar si es una raíz primitiva calculando $a^{\frac{p-1}{q}} \bmod p$ para todos los divisores primos $q$ de $p-1$ . Esto debería ser bastante rápido en la práctica, aunque llevará al menos el mismo tiempo que la factorización $p - 1$ y no sé cuál es la complejidad temporal determinista.

Answer 2

He aquí un ejemplo encantadoramente feo. Supongamos que $X$ , $Y$ y $Z$ son complejos CW simplemente conectados. Supongamos que cada uno tiene los mismos grupos de homología que los demás:

$H_0(X; \mathbb{Z}) \cong H_0(Y; \mathbb{Z}) \cong H_0(Z; \mathbb{Z}) \cong \mathbb{Z}$

$H_3(X; \mathbb{Z}) \cong H_3(Y; \mathbb{Z}) \cong H_3(Z; \mathbb{Z}) \cong \mathbb{Z}$

$H_5(X; \mathbb{Z}) \cong H_5(Y; \mathbb{Z}) \cong H_5(Z; \mathbb{Z}) \cong \mathbb{Z}$

$H_n(X; \mathbb{Z}) \cong H_n(Y; \mathbb{Z}) \cong H_n(Z; \mathbb{Z}) \cong 0$ para todos $n\neq 0,3,5$ .

Entonces, al menos dos de los espacios $X$ , $Y$ y $Z$ son homotópicos entre sí. ¿Cómo se sabe eso? Porque los supuestos implican que los tipos de homotopía de cada uno de $X$ , $Y$ y $Z$ tienen una descomposición mínima de CW con:

un único punto base de la celda 0,

una sola célula de 3, por lo que cada una de $X$ , $Y$ y $Z$ tienen 3 esqueletos $S^3$ ,

y una única 5-célula, por lo que el tipo de homotopía viene determinado por la clase de homotopía del mapa de unión de la 5-célula al 3-esqueleto.

Pero el límite de una celda 5 es $S^4$ . Así que los posibles tipos de homotopía de $X$ , $Y$ y $Z$ son las clases de homotopía de los mapas $S^4 \rightarrow S^3$ es decir, el cuarto grupo de homotopía de la trisfera, $\pi_4(S^3)$ .

Un cálculo rápido arroja que $\pi_4(S^3) \cong \mathbb{Z}/2\mathbb{Z}$ . Así que sólo hay dos tipos de espacios homotópicos del tipo $X,Y$ y $Z$ se supone que son. Por lo tanto, al menos dos de los tres tienen que ser homotópicos entre sí. Pero no es constructivo: la información dada no es suficiente para determinar qué dos son homotopías equivalentes. Así que se obtiene un isomorfismo no constructivo en la categoría de homotopía de los espacios topológicos.

Sin embargo, es más no constructivo que eso. Incluso si se utiliza un argumento como este para averiguar que $X$ y $Y$ tienen que ser homotópicamente equivalentes entre sí, eso está muy lejos de tener mapas continuos entre ellos, una equivalencia homotópica explícita.

Answer 3

Sabemos que dos campos finitos con la misma cardinalidad son isomorfos. Por otro lado, supongamos que tenemos dos polinomios diferentes $f, g \in \mathbb{F}_q[x]$ que son irreductibles y tienen el mismo grado. No conozco ningún cálculo fácil que dé un isomorfismo explícito de campos $\mathbb{F}_q[x] / \langle f \rangle \simeq \mathbb{F}_q[x] / \langle g \rangle$ lo que equivaldría a encontrar una raíz de $g$ en el primer campo.

Answer 4

Si un ejemplo puramente teórico de conjuntos es aceptable:

Teorema de Cantor-Schröder-Bernstein dice que una biyección entre dos conjuntos $A$ y $B$ existe cuando hay inyecciones $i : A \rightarrow B$ y $j : B \rightarrow A$ .

Este el teorema no es constructivamente válido . Hay información sobre por qué esto es así en las respuestas de ese enlace a una pregunta de MathOverflow. La prueba original de Cantor, por ejemplo, utilizaba el teorema del buen orden (que es equivalente al axioma de elección).

Aquí es un trabajo reciente que demuestra que Cantor-Schröder-Bernstein implica el medio excluido.

Answer 5

Lovasz ["A note on the Line Reconstruction Problem", J Combinatorial Theory B, 13, 1972] demostró que dos grafos simples finitos $G,H$ en $n$ vértices con la misma colección de subgrafos propios no etiquetados deben ser isomorfos si cada uno tiene $m > \frac{1}{2}\binom{n}{2}$ bordes. Es un ataque a la conocida conjetura de reconstrucción de aristas. La prueba utiliza la inclusión-exclusión para contar el conjunto de monomorfismos $G\to H$ y muestra que $|G\to H| = |H\to H|$ pero $|H\to H|$ es, por supuesto, mayor que cero.

Por inclusión-exclusión $|G\to H| = \sum_{X\subseteq G} (-1)^{|E(X)|}|X\to \overline{H}|$ donde $X$ recorre todos los gráficos con $V(X)=V(G)$ y $E(X)\subseteq E(G)$ y $\overline{H}$ es el complemento de $H$ . De la misma manera, $|H\to H| = \sum_{X\subseteq H} (-1)^{|E(X)|}|X\to \overline{H}|$ . S $G$ y $H$ tienen los mismos subgrafos propios no etiquetados, los términos de la derecha con $|E(X)| < m$ debe ser idéntica en ambas ecuaciones, y como $m > \frac{1}{2}\binom{n}{2}$ los términos con $|E(X)| = m$ debe ser cero. Por lo tanto, $|G\to H| = |H\to H|$ y por tanto existe al menos un isomorfismo de $G$ a $H$ .

Nunca he visto una forma de modificar la prueba para encontrar un isomorfismo explícito de $G$ a $H$ utilizando isomorfismos conocidos de $G-e$ a $H-\phi(e)$ , donde $e\in E(G)$ y $\phi :E(G)\to E(H)$ es alguna biyección.