Por razones históricas y con el fin de tener aplicación a la solución de ecuaciones diofánticas , los resultados de la teoría de números se han examinado más que en otras ramas de las matemáticas para ver si su contenido es efectivamente computable . Cuando se afirma que alguna lista de números enteros es finita, la cuestión es si, en principio, la lista podría imprimirse después de un cálculo mecánico.
El resultado de Littlewood
Un ejemplo temprano de un resultado ineficaz fue el teorema de JE Littlewood de 1914, [1] que en el teorema de los números primos las diferencias de ψ ( x ) y π ( x ) con sus estimaciones asintóticas cambian de signo infinitamente a menudo. [2] En 1933 Stanley Skewes obtuvo un límite superior efectivo para el primer cambio de signo, [3] ahora conocido como número de Skewes .
Más detalladamente, escribiendo para una secuencia numérica f ( n ), un resultado efectivo acerca de su signo cambiante infinitamente a menudo sería un teorema que incluye, para cada valor de N , un valor M > N tal que f ( N ) yf ( M ) tienen signos diferentes, y de tal manera que M podría calcularse con recursos especificados. En términos prácticos, M se calcularía tomando valores de n a partir de N , y la pregunta es "¿hasta dónde debe llegar?" Un caso especial es encontrar el primer cambio de signo. El interés de la pregunta era que la evidencia numérica conocida no mostraba ningún cambio de signo: el resultado de Littlewood garantizaba que esta evidencia era solo un efecto de número pequeño, pero "pequeño" aquí incluía valores de n hasta mil millones.
El requisito de computabilidad refleja y contrasta con el enfoque utilizado en la teoría analítica de números para probar los resultados. Por ejemplo, cuestiona cualquier uso de la notación de Landau y sus constantes implícitas: ¿son las afirmaciones teoremas de existencia pura para tales constantes, o se puede recuperar una versión en la que 1000 (digamos) toma el lugar de la constante implícita? Es decir, si se supiera que hay M > N con cambio de signo y tal que
- M = O ( G ( N ))
para alguna función explícita G , digamos construida a partir de potencias, logaritmos y exponenciales, eso significa solo
- M < A . G ( N )
para alguna constante absoluta A . Es posible que el valor de A , la llamada constante implícita , también deba hacerse explícito, con fines computacionales. Una de las razones por las que la notación Landau fue una introducción popular es que oculta exactamente lo que es A. En algunas formas indirectas de prueba, puede que no sea del todo obvio que la constante implícita pueda hacerse explícita.
El 'período Siegel'
Muchos de los principales resultados de la teoría analítica de números que se probaron en el período 1900-1950 fueron de hecho ineficaces. Los principales ejemplos fueron:
- El teorema de Thue-Siegel-Roth
- Teorema de Siegel sobre puntos integrales , de 1929
- El teorema de 1934 de Hans Heilbronn y Edward Linfoot sobre el problema de la clase número 1 [4]
- El resultado de 1935 sobre el cero Siegel [5]
- El teorema de Siegel-Walfisz basado en el cero de Siegel.
La información concreta que quedó teóricamente incompleta incluía límites inferiores para los números de clase ( los grupos de clases ideales para algunas familias de campos numéricos crecen); y límites para las mejores aproximaciones racionales a números algebraicos en términos de denominadores . Estos últimos podrían leerse bastante directamente como resultados en ecuaciones diofánticas, después del trabajo de Axel Thue . El resultado usado para los números de Liouville en la demostración es efectivo en la forma en que aplica el teorema del valor medio : pero las mejoras (a lo que ahora es el teorema de Thue-Siegel-Roth) no lo fueron.
Trabajo posterior
Los resultados posteriores, en particular los de Alan Baker , cambiaron la posición. Hablando cualitativamente, los teoremas de Baker parecen más débiles, pero tienen constantes explícitas y en realidad se pueden aplicar, junto con el cálculo de la máquina, para demostrar que las listas de soluciones (que se sospecha que están completas) son en realidad el conjunto completo de soluciones.
Cuestiones teóricas
Las dificultades aquí se resolvieron mediante técnicas de prueba radicalmente diferentes, teniendo mucho más cuidado con las pruebas por contradicción. La lógica involucrada está más cerca de la teoría de la prueba que de la teoría de la computabilidad y las funciones computables . Se conjetura bastante vagamente que las dificultades pueden estar en el ámbito de la teoría de la complejidad computacional . Todavía se están probando resultados ineficaces en la forma A o B , donde no tenemos forma de saber cuál.
Notas
- ^ Littlewood, JE (1914). "Sur la distribution des nombres premiers". Comptes Rendus . 158 : 1869–1872. JFM 45.0305.01 .
- ^ Feferman, Solomon (1996). "Programa de" desenrollado "de Kreisel" (PDF) . Kreiseliana . Wellesley, MA: AK Peters. págs. 247-273. Señor 1435765 .Ver pág. 9 de la versión preimpresa.
- ^ Skewes, S. (1933). "Sobre la diferencia π ( x ) - Li ( x )". Revista de la Sociedad Matemática de Londres . 8 : 277-283. doi : 10.1112 / jlms / s1-8.4.277 . JFM 59.0370.02 . Zbl 0007.34003 .
- ^ Heilbronn, H .; Linfoot, EH (1934). "Sobre los cuerpos cuadráticos imaginarios de la clase número uno". Revista Trimestral de Matemáticas . Serie Oxford. 5 (1): 293–301. doi : 10.1093 / qmath / os-5.1.293 ..
- ^ * Sprindzhuk, VG (2001) [1994], "Aproximación diofántica, problemas de eficacia" , Enciclopedia de Matemáticas , EMS Press - comentarios sobre la ineficacia del límite.
enlaces externos
- Sprindzhuk, VG (2001) [1994], "Aproximaciones diofánticas" , Enciclopedia de Matemáticas , EMS Press