Complejidad computacional del cálculo de grupos de homotopía de esferas

Question

En varias ocasiones he escuchado la afirmación de que computar la estructura del grupo de $\pi_k S^n$ es algoritmo . Pero nunca he encontrado una referencia que afirme esto.

¿Hay algún algoritmo preciso escrito en algún lugar de la literatura? ¿Hay alguno en la literatura, y si es así, cuáles son las estimaciones de tiempo de ejecución? Es de suponer que son bastante malas, ya que nadie parece mencionarlas.

¿Existen familias para las que haya mejores algoritmos, por ejemplo, para los grupos estables de homotopía de esferas? o $\pi_k S^2$ ?

edit: He hecho a Francis Sergeraert algunas preguntas relacionadas con su proyecto. Al parecer, todavía es una cuestión abierta en cuanto a si existe o no un algoritmo de tiempo de ejecución exponencial para calcular $\pi_k S^2$ .

Answer 1

Francis Sergeraert y sus colaboradores han implementado su teoría de topología algebraica efectiva en un programa llamado Kenzo. Parece capaz de calcular cualquier $\pi_n(S^k)$ (de hecho los grupos de homotopía de cualquier complejo CW finito simplemente conectado), aunque no sé hasta qué punto es factible. Por ejemplo $\pi_6 S^3$ es calculado en unos 30 segundos. En un 2002 papel En la página web de la empresa, se mencionan otros algoritmos de Rolf Schön y de Justin Smith, que no se aplicaron en su momento.

Answer 2

Lo demuestra D. J. Anick en The computation of rational homotopy groups is #℘-hard. Computers in geometry and topology, Proc. Conf., Chicago/Ill. 1986, Lect. Notes Pure Appl. Math. 114, 1-56, 1989. que, bueno, el cálculo de grupos racionales de homotopía es #p-duro.

Answer 3

Aquí hay una inútil algoritmo debido a Kan: Sea $G(S^n)$ sea el grupo simplicial que es Kan grupo de bucles del $n$ -Esfera. En cada grado simplicial, es un grupo libre. (Este grupo simplicial tiene el tipo de homotopía del espacio de bucles de base de $S^n$ por lo que sus grupos de homotopía computan los grupos de homotopía de $S^n$ desplazado un grado).

Para cada grado simplicial $k$ definir $N_k(S^n) \subset G_k(S^n)$ para ser la intersección de los núcleos de todos los mapas de caras, excepto el último $d_i: G_k(S^n) \to G_{k-1}(S^n)$ . Entonces el último mapa de caras es un homomorfismo $d_k: N_k(S^n) \to N_{k-1}(S^n)$ . Además, las identidades simpliciales muestran $d_kd_{k+1}$ tiene un valor constante $1$ , por lo que obtenemos un complejo de cadenas no abelianas de grupos libres. Su "homología", por un resultado de Kan, calcula $\pi_*(S^n)$ .

Para obtener un algoritmo para calcular esta homología, recordemos que la demostración del teorema de Nielsen-Schrier da un sistema de generadores para el subgrupo de cualquier grupo libre. Así que obtenemos un sistema de generadores para $N_k(S^n)$ así como un sistema de generadores para la imagen de $d_{k+1}$ . Así que en principio obtenemos un método para calcular los grupos de homotopía de las esferas.

En el documento de Kan, $\pi_3(S^2)$ se calcula de esta manera, y lleva varias páginas ¡así que no es un algoritmo muy bueno!

Answer 4

Weinberger's Ordenadores, rigidez y módulos: la geometría fractal a gran escala del espacio de módulos de Riemann contiene varias referencias aparentemente útiles en las páginas 93-4, en la sección de notas del capítulo sobre esferas de homología de diseño (que también puede ser de interés). Weinberger menciona "la naturaleza algorítmica de la teoría de la homotopía simplemente conectada" y cita el artículo de Brown que Mike mencionó antes de pasar a citar "Cálculos infinitesimales en topología", de Sullivan. Pub. Matemáticas. IHÉS , 47 269 (1977) , Griffiths y Morgan's Teoría de la homotopía racional y formas diferenciales , "Conferencias sobre modelos mínimos" de Halperin. Mém. Soc. Math. France, Sér. 2 , 9-10 1 (1983) y La "Teoría de la homotopía domesticada" de Dwyer. Topología 18 321 (1979) .

El resultado práctico de estas referencias posteriores parece ser el cálculo de $\pi_k(S^n) \otimes \mathbb{Q}$ o, en el caso de la teoría de la homotopía domesticada, el objeto análogo que implica un número finito de primos (cuyo número aumenta con la dimensión).

Answer 5

Está el artículo de R. V. Mikhailov y J. Wu, http://arxiv.org/abs/1108.3055 . Construyen un grupo cuyo centro es un grupo de homotopía inestable de una esfera o un espacio de Moore. Así que ahora parece que podríamos aplicar nuestros conocimientos algorítmicos para calcular los centros de los grupos, que pueden ser pocos o muchos, a los grupos de homotopía inestables.

Me imagino que esto sería más fácil de trabajar en un algoritmo, tal vez esto ya se ha hecho. Sin embargo, siempre estoy inseguro sobre estas cosas, a veces la palabra problema se esconde en las sombras.