¿Qué tan indecidible es la brecha espectral?

Question

Nature acaba de publicar un artículo de Cubitt, Pérez-García y Wolf titulado Indecidibilidad de la brecha espectral Hay un versión ampliada en arxiv que tiene 146 páginas. Esto es lo que dice el resumen:" Muchos problemas desafiantes abiertos, como la conjetura de Haldane, la cuestión de la existencia de fases líquidas de espín topológicas con brecha y la conjetura de la brecha de Yang-Mills, se refieren a las brechas espectrales. Estos y otros problemas son casos particulares del problema general de la brecha espectral: dado el Hamiltoniano de un sistema cuántico de muchos cuerpos, ¿tiene o no brecha? Aquí demostramos que se trata de un problema indecidible. Específicamente, construimos familias de sistemas cuánticos de espín en una red bidimensional con interacciones de vecino más cercano invariantes por traslación, para las que el problema de la brecha espectral es indecidible ".

Tengo curiosidad por la parte indecidible. El resumen dice " nuestro resultado implica que no existe ningún algoritmo para determinar si un modelo arbitrario tiene o no brecha, y que existen modelos para los que la presencia o ausencia de una brecha espectral es independiente de los axiomas de las matemáticas ". "Axiomas de las matemáticas" es algo vago, así que en la versión ampliada lo redactan de forma gödeliana:" Nuestros resultados implican que para cualquier axiomatización consistente y recursiva de las matemáticas, existen hamiltonianos específicos para los que la presencia o ausencia de una brecha espectral es independiente de los axiomas ". Pero aún así, la axiomatización de qué matemáticas, cuántas matemáticas necesitan para construir sus hamiltonianos. ¿Es el análisis real? ¿ZF? ¿ZFC? No puedo averiguarlo ni siquiera a partir de sus enunciados de teoremas.

¿Se trata de una demostración matemática o de algo al "nivel de rigor físico"? Si es así, ¿produce afirmaciones indecidibles "concretas", o son estos hamiltonianos tan oscuros como "soy indemostrable"? ¿Representa una nueva forma de demostrar resultados de independencia en comparación con el forzamiento, etc.? En otras palabras, ¿es un avance respecto a las sentencias de Gödel y la hipótesis del continuo?

EDITAR: Cubitt concedió una entrevista donde comentó de manera informal la naturaleza del resultado:" Es posible que los casos particulares de un problema se puedan resolver incluso cuando el problema general es indecidible, así que alguien puede ganar el codiciado premio de un millón de dólares... La razón por la que este problema es imposible de resolver en general es porque los modelos de este nivel muestran un comportamiento extremadamente extraño que esencialmente derrota cualquier intento de analizarlos... Por ejemplo, nuestros resultados muestran que añadir incluso una sola partícula a un trozo de materia, por grande que sea, podría en principio cambiar drásticamente sus propiedades ".

Answer 1

No he leído el artículo detenidamente, pero parece ser un resultado de indecidibilidad estándar, del tipo de los que hay docenas, si no cientos, en la literatura, del mismo tipo que la indecidibilidad de los tilings de Wang, la indecidibilidad de la existencia de soluciones a las ecuaciones diofantinas, el problema de la palabra para los grupos y muchos otros.

Es una demostración matemática formal que muestra (Teorema 3 en la versión extendida) que, existe una familia de Hamiltonianos $H^{\Lambda(L)}(n)$ tal que el conjunto de $n$ tal que $H^{\Lambda(L)}(n)$ es "vacío" es un conjunto completo computablemente enumerable.

La conexión con cosas como la axiomitización de las matemáticas es entonces completamente estándar -cualquier sistema correcto y consistente de axiomas no puede demostrar " $H^{\Lambda(L)}(n)$ no está vacía" para todos los $n$ para los que esto es cierto.

Answer 2

Interpreto que su pregunta se refiere a la transición de de la indecidibilidad computable a la indecidibilidad gödeliana o lógica lógica, y además sobre la medida en que esta indecidibilidad lógica puede depender de los axiomas matemáticos que hayamos adoptado. que hayamos adoptado.

La respuesta es que, en general, se puede deducir que hay casos concretos de indecidibilidad lógica, siempre que se tenga un problema indecidible computacionalmente, sin importar la teoría que se haya adoptada como axiomas de las matemáticas, ya sea PA o ZFC o ZFC más grandes cardinales o lo que sea. Los dos tipos de indecidibilidad -la indecidibilidad computable y la indecidibilidad lógica - están estrechamente entrelazadas, y cada problema indecidible computable está saturado de casos de independencia lógica con respecto a cada problema (computablemente axiomatizable y sólida).

Para ver esto, supongamos que $A$ es un problema de decisión computablemente indecidible como el problema de halting o el problema de los mosaicos o, ahora, el problema de la brecha espectral, ahora, el problema de la brecha espectral, y supongamos que $T$ es su teoría fundacional favorita, los axiomas de las matemáticas. Nosotros sólo requerimos que $T$ tiene una lista computable de axiomas, que $T$ es lo suficientemente fuerte como para expresar el problema de decisión $A$ y que $T$ es suficientemente sólida.

Desde $A$ es computablemente indecidible, no existe un procedimiento computable para determinar en la entrada $n$ si es o no $n\in A$ . Consideremos el algoritmo que en la entrada $n$ busca una prueba de $T$ que $n\in A$ o una prueba de $T$ que $n\notin A$ . Dado que el problema de pertenencia para $A$ era computablemente indecidible, este algoritmo no puede resolver correctamente todas las instancias del problema, ya que de lo contrario sería un procedimiento de decisión computable. Dado que $T$ es sólida, sin embargo, el algoritmo es correcto sobre las instancias del problema que sí resuelve. Así que debe haber una instancia específica del problema $n$ (de hecho, infinitas tales $n$ ) para el que $T$ no demuestra $n\in A$ y $T$ no probar $n\notin A$ . Por lo tanto, para este $n$ y este específico $T$ la cuestión de si $n\in A$ es independiente de $T$ .

Este argumento funciona incluso cuando refuerzas tus axiomas, y por lo tanto no importa si usas PA o ZFC o ZFC más grandes cardinales o lo que sea. Una teoría más fuerte puede resolver algunos de los casos concretos que no fueron resueltos por las teorías más débiles. teorías más débiles, pero toda teoría admitirá casos concretos que que no resuelve, pues de lo contrario el algoritmo de búsqueda de pruebas sería un procedimiento computacional que decide $A$ En contra de la hipótesis de que suposición de que $A$ es indecidible.

Véase también la pregunta de John Pardon, ¿Están relacionados los dos significados de "indecidible"?

Answer 3

¿Representa una nueva forma de demostrar los resultados de independencia en comparación con el forzamiento, etc.? En otras palabras, ¿es un avance respecto a las sentencias de Gödel y la hipótesis del continuo?

Nadie lo ha dicho todavía, así que: la respuesta a ambas preguntas es no. Por lo que puedo decir, el resultado es una reducción estándar del problema de detención. El artículo muestra que calcular las brechas espectrales es tan difícil como decidir si las máquinas de Turing se detienen, y ya sabemos lo que tiene que ver con la independencia.

Answer 4

No soy un experto, pero la versión corta del documento http://arxiv.org/pdf/1502.04135v1.pdf parece abordar estas cuestiones en la conclusión:

Pero, ¿qué significa que una propiedad física sea indecidible? Después de todo, si es física, seguramente podríamos en principio construir el sistema en el laboratorio, y medirlo. Un sistema cuántico real un sistema cuántico real de muchos cuerpos podría mostrar una física con huecos o una física crítica sin huecos, pero física crítica, ¡pero debe mostrar algún tipo de física! La clave para conciliar esto con nuestros resultados es darse cuenta de que el límite termodinámico es una idealización. Un sistema físico real tiene necesariamente un tamaño finito (aunque muy grande en el caso de un sistema típico de muchos cuerpos de muchos cuerpos, compuesto por $10^{26}$ átomos). No obstante, las señales de indecidibilidad aparecen en el comportamiento muy inusual de tamaño finito de de estos modelos. En realidad, solemos sondear el límite termodinámico infinito idealizado límite termodinámico idealizado estudiando cómo se comporta el sistema a medida que tomamos sistemas finitos cada vez más grandes. En la física cuántica experimental física cuántica de muchos cuerpos, se suele suponer que los sistemas, aunque finitos son tan grandes que ya vemos el comportamiento asintótico. En simulaciones numéricas de sistemas de materia condensada, se suele sistemas finitos de tamaño creciente y se extrapola el comportamiento comportamiento asintótico a partir del escalado de tamaño finito. Del mismo modo, la QCD de celosía simulan espaciamientos de red finitos y extrapolan los resultados al continuo. resultados al continuo. Las técnicas de grupos de renormalización logran prácticamente lo mismo matemáticamente.

Sin embargo, los modelos cuánticos indecidibles de muchos cuerpos construidos en este trabajo muestran un comportamiento que derrota a todos estos enfoques. A medida que el tamaño del sistema, el hamiltoniano se parecerá inicialmente a un sistema como un sistema sin huecos, con el espectro de baja energía que parece converger convergen a un continuo. Pero a partir de un cierto tamaño de celosía, aparecerá de repente un constante aparecerá de repente. (Nuestra construcción puede también se puede utilizar para producir el comportamiento opuesto, con el sistema que tiene un hueco espectral constante hasta un cierto tamaño de retícula umbral, más allá del cual que cambia bruscamente a una física sin brecha. No sólo puede el tamaño de celosía en el que el sistema pasa de no tener huecos a tenerlos arbitrariamente grande, el umbral en el que se produce esta transición es no se puede calcular. Esto implica que nunca podremos saber si el sistema está realmente sin huecos, o si el aumento del tamaño de la red -incluso sólo un sitio más de la red, revelaría que tiene huecos.