86 votos

La complejidad enigmática de la teoría de números.

Uno de los más destacados aspectos de la disciplina de la teoría de números es que a partir de un número muy pequeño de las definiciones, las entidades y los axiomas que uno es llevado a una extraordinaria riqueza y diversidad de los teoremas, las relaciones y problemas, algunos de los cuales pueden ser fácilmente declaró sin embargo, son tan complejos que toman los siglos de los esfuerzos concertados de los mejores matemáticos para encontrar una prueba (Último Teorema de Fermat, ...), o se han resistido a tales esfuerzos (Goldbach de la Conjetura, de la distribución de los números primos, ...), o llevar a entidades matemáticas de gran complejidad, o requiere extraordinario esfuerzo colectivo, o se han caracterizado por Paul Erdös como "las Matemáticas no está preparado para tales problemas" (Conjetura de Collatz).

(Por supuesto, todas las ramas de la matemática tienen esta propiedad, en cierta medida, pero la teoría de los números parece el prototipo de caso, ya que ha atraído a algunos de los más serios esfuerzos en axiomization (Russell y Whitehead), que Gödel es un trabajo más relevantes a los fundamentos de la teoría de los números (más que, por ejemplo, la topología), y que ha habido una gran cantidad de trabajo en la cuantificación de la complejidad de la teoría de números--más de ecuaciones diferenciales, por ejemplo.)

Preguntas relacionadas, tales como una exploración de la relación entre el Teorema de Gödel y la complejidad de las matemáticas, han sido altamente valorado y evitado de alguna manera todos los esfuerzos para cerrar. Este problema actual parece más centrado en las referencias específicas, teoremas, y tal.

¿Cómo matemáticos profesionales entender mejor el origen fundacional de la complejidad en la teoría de los números? No creo respuestas tales como "una vez que las relaciones no son lineales las cosas se complican" o los de su calaña son intelectualmente satisfactorio. Uno puede referirse a la del Teorema de Gödel para "explicar" que la teoría de los números es tan complicado que no finito axiomitization de captura de todos sus teoremas, pero debemos considerar este teorema como, en cierto sentido, el origen de tal complejidad?

"Esta no es una opinión basada en" la pregunta (aunque es cierto que podría ser más apropiado para metamathematics o la filosofía de las matemáticas): estoy en busca de teoremas y conceptos matemáticos profesionales (en particular el número de teóricos) que se reconoce como esencial para nuestra comprensión del origen de la amplitud y complejidad de la teoría de números. ¿Por qué no la teoría de los números trivial?

¿Qué referencias, especialmente los libros, se han dedicado a atender específicamente el origen de las raíces profundas de la diversidad y la complejidad de la teoría de los números?


Por el contrario, creo que los físicos pueden señalar una serie de fuentes de la extraordinaria riqueza y variedad de los fenómenos físicos: es porque ciertas fuerzas (de alguna manera) actuar fundamentalmente diferente longitud y escalas de tiempo. Las reglas de la mecánica cuántica rigen la interacción de un pequeño número de partículas subatómicas. En lo suficientemente grandes escalas, sin embargo, la mecánica cuántica eficaz "apaga" de la mecánica clásica y domina, incluyendo en la mayoría de los de la mecánica estadística, donde es el gran número de partículas es relevante. En escalas más grandes (por ejemplo, la dinámica celeste), ignoramos los efectos cuánticos. Sí, los físicos están tratando de unificar la legislación, de modo que incluso la mecánica cuántica, que describe las interacciones de los quarks es de alguna manera unificada con la gravedad, la que rige en las escalas más grandes... pero el hecho de que estas fuerzas naturales diferentes escalas lleva cualitativamente diferentes clases de fenómenos a diferentes escalas, y, por tanto, la complejidad y la variedad de fenómenos físicos.

113voto

Ryan McCue Puntos 1178

Yo no soy un número teórico, pero por lo que vale: me gustaría hablar, no tanto sobre el Teorema de Gödel en sí, sino sobre el fenómeno más amplio que el Teorema de Gödel se apunta, aunque la terminología no existe aún cuando el teorema fue publicado en 1931. Es decir, la teoría de números es ya una computadora universal. O más precisamente: cuando nos preguntamos si una ecuación tiene un número entero de la solución, ya que es equivalente a preguntar si un equipo arbitrario programa se detiene. (Una forma fuerte de esa declaración, donde las ecuaciones deben ser el polinomio de Diophantine ecuaciones, fue Hilbert del Décimo Problema, y sólo fue probado por el famoso MRDP Teorema en 1970. Pero una forma más débil de la declaración está contenida en el Teorema de Gödel en sí misma).

Una vez que usted entiende esto, y también de entender lo arbitrario de los programas de ordenador se puede hacer, creo que no es ninguna sorpresa que la teoría de los números parecen contener cantidades ilimitadas de complejidad. La verdadera sorpresa, por supuesto, es que la "simple" teoría de los números de las preguntas, como Último Teorema de Fermat o la Conjetura de Goldbach, ya puede mostrar mucho de la complejidad, que ya se puede ver con las preguntas que tengo la intención de explicar a mi hija antes de que ella nueve. Este es el número de la teoría de la contraparte de el conocido fenómeno de que a corto programas de ordenador ya dar lugar a absurdamente complicado comportamiento.

(Como ejemplo, existen 5-estado de máquinas de Turing con una cinta y un alfabeto binario, para que nadie ha demostrado si detener o no, cuando se ejecuta en una cinta que inicialmente todos los ceros. Esto es equivalente a decir que aún no sabemos el valor de la quinta Busy Beaver número.)

Aquí, creo que un papel crucial jugado por un efecto selección. Anteriormente, yo no hablar de la inmensa mayoría de la 5-estado de máquinas de Turing para que nos haga saber si se detienen, ni tampoco hablo de 10,000-estado TMs---porque esas no hubiera hecho mi punto. Asimismo, el número teoría de las preguntas que se hacen famosos, son abrumadoramente sesgada hacia aquellos que son más fáciles de estado aún más difícil de resolver. Eso es suficiente para algunas de estas preguntas a existir---o, más precisamente, para algunos existen y que son reconocibles por los seres humanos---para dar lugar a lo que usted está preguntando acerca de.

Otra manera de ver esto es que el número de teóricos, en el curso de su trabajo, son, naturalmente, va a ser empujado hacia la "complejidad" de la frontera"---como un ejemplo, hasta el más complicado de los tipos de Diophantine ecuaciones sobre el que todavía puede realizar profundos y no trivial de las declaraciones, y no completamente en Gödel/Turing pantanos. E. g., mi laico de la caricatura es que lineal y, a continuación, cuadrática Diophantine las ecuaciones se han entendido desde hace bastante tiempo atrás, por lo que, a continuación, el siguiente son las cúbicos, que son las que dan lugar a curvas elípticas, que son, por supuesto, donde la teoría de los números todavía gasta gran parte de su esfuerzo de hoy. Mientras tanto, sabemos que si se sube a lo suficientemente mayor complejidad---al parecer, un grado 4 ecuación en 9 incógnitas basta; no se sabe si eso es óptima---entonces usted ya ha entrado en el terreno de la MRDP Teorema y, por tanto, Gödel-undecidability (al menos arbitrarias de las ecuaciones de ese tipo).

En resumen, si no es una frontera entre la banalidad y la undecidability, donde las preguntas, todavía puede ser resuelto, pero sólo por el gasto de los siglos para desarrollar teóricos de la maquinaria, el número teoría parece tener una muy mecanismo natural que podría causar que el end!

(Que uno ve algo similar en la topología de baja dimensión: clasificación de las 2-variedades es clásica; 4-colector de homeomorphism es conocido por ser al menos tan duro como el cese problema; así que deja la clasificación de las 3-variedades, que fue alcanzado por Perelman de la prueba de la geometrización desde entonces he aprendido que esto sigue abierto, aunque la geometrización da lugar a un procedimiento de decisión para la 3-variedad homeomorphism.)

En cierto sentido estoy de acuerdo con Gerhard Paseman la respuesta, excepto que creo que Wolfram llegaron varias generaciones demasiado tarde para ser acreditado por la intuición fundamental, y que no hay demasiado mal con Un Nuevo Tipo de Ciencia para que pueda recomendarse sin advertencias. Las imágenes de los autómatas celulares son muy divertidos, aunque, y ayudar a hacer el punto sobre cuán pocos pasos que usted necesita tomar a través del espacio de la regla-sistemas antes de que ya estás en el borde del abismo.

43voto

Dean Hill Puntos 2006

¿Qué referencias, especialmente los libros, se han dedicado a atender específicamente el origen de las raíces profundas de la diversidad y la complejidad de la teoría de los números?

En una primera aproximación, yo diría que la respuesta a esta pregunta es, no hay ninguno.

Se han puesto de relieve que usted está interesado en el punto de vista de profesional número de teóricos. Yo diría que para la mayoría de los número de teóricos, un término como el de la "diversidad y la complejidad de la teoría de los números" trae a la mente problemas centrales de la moderna teoría de los números, tales como la generalización de la hipótesis de Riemann, el problema de la paridad en el tamiz de la teoría, la Langlands conjeturas, la estructura de los Gal(${\overline{\mathbb{Q}}}/\mathbb{Q})$, etc. Estos son el tipo de cosas que los profesionales de la número de teóricos podría citar como la "fuente" de la diversidad y la complejidad de la teoría de números. Nota en particular de que las cosas tales como Hilbert del Décimo Problema son interesantes a relativamente pocos profesional número de teóricos. El tipo de "complejidad" que los lógicos, teóricos y científicos de la computación interesa no es lo que interesa a la mayoría de los número de teóricos. A grandes rasgos, es porque undecidability preguntas son considerados como signos de caos , mientras que el número de los teóricos están interesados en la búsqueda de la estructura.

Si queremos una explicación de por qué hay tanta diversidad y complejidad en la teoría de números, incluso cuando nos centramos en las estructuras que ocupan la atención de número de teóricos, entonces no creo que mirando hacia undecidability nos dará la respuesta. Generalizada de ajedrez, por ejemplo, muestra que tipo de "complejidad", pero el más profundo de los estudios de ajedrez, más se parece a exhibir aparentemente "al azar" de la conducta que desafía elegante descripción (sólo echar un vistazo al registro de los titulares en la final tablebases por ejemplo). En generalizada de ajedrez no encontramos ninguna señal de nada, con la hermosa y profunda de la estructura de, digamos, la clase de teoría de campo.

La búsqueda de una explicación de lo que el número de teóricos de la materia como la diversidad y la complejidad de su sujeto es el lugar probable para obtener ensayos con "irrazonable efectividad" o alguna de esas en el título, y la discusión es probable que siga el mismo camino que la discusión de Wigner del artículo se ha tomado. Por ejemplo, se puede señalar que existe un proceso de selección natural, con número de teóricos deliberadamente gravitando hacia las áreas de diversidad, la complejidad y el abandono de las áreas que son estériles.

9voto

lterrier Puntos 31

Usted podría disfrutar de Un Nuevo Tipo De Ciencia. Es un libro profusamente ilustrado con abundantes (Edit: notas a pie de página, no referencias; gracias a Scott Aaronson para ayudarme a ver la distinción) centrada en torno al tema de la computación y la complejidad en el comportamiento de los autómatas celulares. Aunque usted podría escuchar el libro de los críticos antes de sumergirse en ella, me pasé un par de horas rozando sus mil y pico de páginas y no lamento el tiempo que pasó.

Uno puede tomar un automático (o sintáctica) punto de vista de su pregunta, como se ha hecho en otro digno de leer (Goedel, Escher, Bach: Una Eterna Trenza Dorada), donde tipográficos de la teoría de números es considerado. Un resultado de esto es que los comprobable sentencias de esta teoría son recursivos (recursivo conjunto), mientras que la verdadera oraciones (aquellos que poseen en un modelo estándar de la teoría) no recursivo (que son recursivamente enumerable, si recuerdo correctamente). Editar 2017.10.07 De hecho, me recordó de forma incorrecta. Gracias a Alex Kruckman, quien comentó que el conjunto de los comprobable frases es recursivamente enumerable (no recursiva) y el conjunto de verdad de oraciones no es aritméticamente definibles (muy diferente de recursivamente enumerable). Parece que la necesidad de algunos de reciclaje. Final De Edición 2017.10.07. A fin de relacionar este punto de vista el aspecto filosófico de su pregunta, me gustaría entender más acerca de cómo se percibe la complejidad, pero confío en lo que sugiere que su percepción se refiere a cómo las palabras se puede describir una colección de cosas, y que los resultados técnicos dicen que no habrá ninguna descripción sencilla en cualquier momento pronto.

Aparte de la metamathematics involucrados en la teoría de la recursividad y el estudio de los conceptos descriptivos y definible complejidades, yo diría que estudia el comportamiento de los autómatas (y más aún, la participación en un estudio psicológico de este tipo de estudios!) es como un camino rápido para responder a tu pregunta como cualquier otra. Un ejemplo de esto es Cómo hacer estos primos de saltar? , donde puedo tomar una simple variante de un primer tamiz y el algoritmo de pedir un número teórico de preguntas. No he formalizado las preguntas y el estudio, pero me sorprendería si me necesitaba mucho más que el PRA (primitiva recursiva aritmética) para llevar a cabo dicho estudio. Creo que incluso hay sistemas más simples cuyo metamathematics son fácilmente formalizado y rinde de complejidad similar a lo que se ve en la teoría de números.

(Edit: Eterna, no Enigmático)

Gerhard "Que El Estudio De La Studier?" Paseman, 2017.10.06.

6voto

Pierre Spring Puntos 2398

Es una pregunta interesante si hay algo de complejidad-como jerarquía para (ordinario) de las conjeturas en la teoría de números, y se puede limitar nuestro interés, incluso a conjeturas alegando una cierta aleatoriedad de los números primos. (Para tales declaraciones no soy consciente de la universalidad de los resultados, pero esto de por sí es interesante.)

Algo de este tipo se manifiesta en polymath4 - la tarea de encontrar de manera eficiente un número primo con $n$ dígitos. Esto se puede hacer si usted toma para concedido Cramer conjetura con respecto a las brechas entre los números primos, y también puede ser alcanzado si se toma por sentado muy fuerte derandomization conjeturas (que a su vez seguir (o algunos debilitamiento de la siguiente manera) de muy muy muy muy en forma más fuerte de la $NP \ne P$ conjetura.)

Otra manifestación de la especulación con respecto a la complejidad del tipo de jerarquía para (estándar) número de la teoría de las conjeturas es en este MO pregunta infinidad de números primos, y Mobius aleatoriedad en la escasa establece que propone que Mobius aleatoriedad dispersas conjuntos podrían ser difíciles de tratar.

(Sin embargo, otra relación, pero de menos especulativa de la naturaleza, aspecto de la complejidad de la teoría de números se pueden encontrar en esta pregunta Walsh transformada de Fourier de la función de Möbius y el post sobre AC0-teorema de los números primos. refiriéndose a los distintos problemas que se plantearon a partir de una conferencia a cargo de Sarnak en HUJI.)

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X