En esta entrada veremos un joven matemático rechazando el consejo de su viejo profesor: deja de pensar en este problema imposible, dejando de lado el problema que su director de tesis le asignó y salirse con la suya a pesar de todo.
Veremos la solución de un problema de Erdös que todos consideraban difícil, con una solución elemental pero llena de ingenio.
La conjetura de los conjuntos primitivos de Erdös
Un conjunto de números naturales A se dice primitivo si ningún número de A divide a algún otro. En 1935 Erdös probó que supA, primitivo∑n∈A1nlogn=C<+∞.
El conjunto de los números primos P es un ejemplo sencillo de conjunto primitivo. En 1988 Erdös conjeturó que el supremo C se alcanza para el conjunto primitivo P de los primos. Es decir, que para cualquier conjunto primitivo A se cumple que f(A):=∑a∈A1aloga≤∑p∈P1plogp.
Esta conjetura proporciona una definición del conjunto de los primos. Una definición global. Distinguiendo a los primos de cualquier otro conjunto primitivo. Porque la suma para cualquier otro conjunto primitivo es estrictamente menor que para los primos.
El teorema de Erdös
Comenzamos explicando el resultado de Erdös sobre la finitud del supremo de f(A):=∑a∈A1aloga
En la criba de Eratóstenes, cuando tachamos los múltiplos de 2, quedan los números impares, un conjunto con densidad 1−12, cuando tachamos los múltiplos de 3 nos queda un conjunto de números de densidad (1−12)(1−13). Del mismo modo ∏p<P(a)(1−1p) representa la densidad de los números no divisibles por números primos menores que P(a) y 1a∏p<P(a)(1−1p) la densidad del conjunto de los números La={ma∈N:p∣m⟹p≥P(a)}.
Jared Duker Lichtman
Jared fue siempre un buen estudiante: «Desarrollé un interés especialmente fuerte hacia las matemáticas con la geometría del instituto (en noveno grado). En esta clase fue mi primer encuentro con demostraciones basadas en axiomas. Que un ser humano pueda dar pasos rigurosos para acceder a una verdad absoluta fue un concepto que realmente me abrió los ojos, y tuvo una potente influencia sobre mí.»
En su primer año en Dartmouth College (equivalente a nuestra Facultad) conoció a Carl Pomerance. Era el último curso que Carl impartía antes de jubilarse. Fue Jared quién pidió a Carl que le dirigiera su proyecto de investigación (equivalente al trabajo fin de grado). Carl aceptó y dirigió su trabajo sobre números no deficientes primitivos. Fue en este momento (2018, con 22 años) que tuvo conocimiento de la conjetura de Erdös sobre los conjuntos primitivos. «Inmediatamente pensé que era un problema absolutamente hermoso y empecé a pensar en él desde ese mismo momento.»
En 2018 fue nombrado Churchill Scholar (una beca muy prestigiosa del gobierno británico para estadounidenses) para hacer un master en Cambridge, que mas tarde lo llevó a Oxford a trabajar para su doctorado bajo la supervisión de James Maynard (medalla Field en 2022). La supervisión de un doctorado es algo serio. El director propone un problema que tiene que ser cuidadosamente escogido. No simple pero tampoco imposible, un tema con potencial. Generalmente mantendrá al alumno ocupado entre dos y cuatro años. Pero Jared ya tenía un problema en mente y no era fácil para él abandonarlo. Él no informó a Maynard sobre esto hasta que tuvo la solución. El mismo Jared da cuenta del momento en un video de Numberphile
¿Qué dijo tu director cuando se lo dijistes?
Bueno, uf, de hecho él no sabía que yo trabajaba en este problema. Pensaba que se enfadaría conmigo por no trabajar en el problema que él me había propuesto, y esto era algo que yo había estado haciendo a la luz de las velas, por la noche, subrepticiamente. Pero, en fin, le hice saber este invierno que lo había resuelto… había llegado a esta demostración, y él, uf…, se tomó varios meses para leerlo atentamente y comprobar cada paso, ya sabes, poner los puntos sobre todas las íes y cruzar todas las tes, pero él estaba también muy contento por mí y yo, yo estaba… yo era…, fue un momento muy agradable.
(video de Numberphile en Youtube 13:34–14:19)
Todo el mundo piensa que P≠NP, no reconocen el abrumador número de hechos experimentales que corroboran la eficacia del algoritmo que presenté en Creación artística y creación matemática, Sección El algoritmo que nadie quiere ver.
El algoritmo es: toma jóvenes motivados por la matemática. Muéstrales las conjeturas, proponles problemas relacionados que estén a su alcance. Proponles que estudien los trabajos relacionados y las herramientas próximas. Déjalos soñar y en unos años habrán encontrado las pruebas o construido edificios y herramientas con los que la siguiente generación estarán mejor equipados.
Comenzando y notaciones
Para cada natural n>1, denotamos por P(n) el mayor factor primo de n y por p(n) el menor. Definimos f(A)=∑a∈A1aloga, f(p)=f({p})=1plogp. La={an:p∣n⟹p≥P(a)},a∈N.
d(A):=limx→∞|A∩[1,x]|/x cuando el límite existe.
En resumen, la demostración de Erdös tiene tres pasos: ∑a∈A1aloga≤∑a∈A1alogP(a)sust. a→P(a)≤c∑a∈A1a∏p<P(a)(1−1p)Mertens=c∑a∈Ad(La)=cd(⋃a∈ALa)≤c.La disjuntos
Estrategia general y primos fuertes de Erdös
Siendo A un conjunto primitivo, queremos probar ∑a∈A1aloga≤∑p1plogp.
Una estrategia para probar la conjetura sería separar A=⋃pAp en conjuntos disjuntos uno para cada primo p y entonces probar que f(Ap)≤f(p). Un buen candidato para Ap serían los conjuntos Ap={a∈A:p es el menor primo que divide a a}.
Si p∈A, entonces Ap={p} y la desigualdad f(Ap)≤f(p) es trivial, siendo además una igualdad. En otro caso, cuando p∉A, tenemos f(Ap)<f(p) con desigualdad estricta, así que la prueba consiste en obtener cotas superiores de f(Ap) suficientemente buenas.
Puesto que f(A)=limx→∞f(A∩[1,x]) podemos generalmente suponer sin perder generalidad que A es finito. No repetiremos esto en lo que sigue.
Mejorando los tres pasos de Erdös
En el paso intermedio, el de Mertens, lo más que uno puede aspirar es a rebajar la constante a eγ y esto lo consiguieron Jared y Pomerance en un trabajo publicado en 2018. Los dos pasos más difíciles de mejorar fueron el primero y el último
En el primer paso es clara la diferencia entre a y P(a). Hay un exponente κ tal que a=P(a)κ. Así que loga=κlogP(a). Pero κ puede variar mucho dependiendo del valor de a. «Trabajé en diversas direcciones para atacar este problema durante varios años.»
Es muy interesante cómo ha evolucionado la prueba de Jared. Le pregunté («Cuando resolviste la conjetura, ¿hubo algún momento de iluminación? ¿Puedes dar detalles?») y en su respuesta ha explicado su proceso mental para llegar a la solución. Creo que es muy instructiva.
En la prueba de Erdös los conjuntos La son disjuntos porque A es un conjunto primitivo. Pero Jared se da cuenta de que puede extender el concepto de conjunto primitivo al de conjunto L-primitivo, como aquellos conjuntos A tales que los correspondientes La con a∈A son disjuntos. Y esto lleva al concepto de L-múltiplos: diremos que b es un L-múltiplo de a si b∈La. Estos conceptos son la clave para la mejora de los pasos 1 y 3 en la demostración de Erdös. [El lema 3.1 y los conjuntos Cva de los que habla aquí serán explicados más adelante después de la sección Para saber más.]
Trabajé varios intentos de atacar este problema durante varios años. Gradualmente, me di cuenta de que debería existir una definición explícita de conjuntos de L-multiplos y (más importante) conjuntos L-primitivos. Una vez tuve estas definiciones, se hizo natural buscar un resultado como el Lema 3.1, durante la prueba del cual la definición exacta de Cva se convierte esencialmente en algo obligado. Después de que se llega al lema 3.1, el resto de la prueba fluye rápidamente, y es realmente tarea fácil deducir el resultado final (con un poco de trabajo extra para el caso p=2). En este sentido quiero subrayar que la dificultad clave para mí fue desarrollar el marco adecuado y las definiciones que hacen natural pensar en algo como el Lema 3.1 (De hecho, ¡imagina el enunciado del Lema 3.1 sin mencionar los conjuntos de L-múltiplos, o los conjuntos L-primitivos!
(Jared, comunicación personal 21 de enero de 2023)
En su contestación a mi pregunta Jared termina dando algunas explicaciones sobre la demostración y las razones por las que el conjunto de los primos es el mejor conjunto primitivo:
Hay dos pasos que son potencialmente ineficientes, (1) la sustitución «a→P(a)» y (2) «el ser los La disjuntos». En mi demostración, un conjunto primitivo de números compuestos puede o bien mejorar el paso (1) fácilmente (si digamos a>P(a)2 para todo a∈A), o bien puede mejorar el paso (2) mediante el Lema 3.1 y sus consecuencias. La integral final (=π/4) representa el ahorro en el peor de los casos derivado de la combinación de estos pasos. Además, en el caso de los primos mismos, los pasos (1) y (2) son perfectamente eficientes en el argumento de Erdös (de hecho para (1) p=P(p), y para (2) la colección de los {Lp} no puede ser ampliada de manera que sigan siendo disjuntos dos a dos).
Por lo tanto esto da una explicación conceptual de por qué los primos son maximales entre los conjuntos de la conjetura de Erdös: a saber, los compuestos pueden ser mejorados o bien en el paso (1) o el (2), pero los primos no admiten tales mejoras.
(Jared, comunicación personal 21 de enero de 2023)
La demostración de Jared no usa conceptos matemáticos complicados. Se presta por esto a una exposición más detallada. Pero esta entrada es ya bastante larga, así que después de la usual sección «Para saber mas» incluiré un análisis más detallado de la prueba.
Para saber más
Podemos ver a Jared Duker Lichtman en dos vídeos de youtube Exponiendo su tesis en 3 minutos, y una interview en Numberphile que recomiendo. También hay una entrada muy buena en Quanta magazine sobre la solución de la conjetura de Erdös.
Una noticia sobre su vida como estudiante puede verse en la página web Jared named Churchill scholar.
Su articulo es muy legible puesto que no usa conceptos matemáticos complicados, solo sumas de Riemann, divisibilidad elemental. Puede encontrarse en arXiv:
Jared Dukker Lichtman, A proof of the Erdös primitive set conjecture, 2022. arXiv:2202.02384 [math.NT].
También es buena lectura el artículo original de Erdös, que puede verse como una versión simplificada/aproximada del articulo de Jared:
P. Erdös, Note on Sequences of integers no one of which is divisible by any other, J. London Math. Soc. 10 (1935) 126–128. pdf de este trabajo.
El artículo de Rosser y Schoenfeld que es usado por Jared puede ser uno de los más citados en Teoría de Números. Es también accesible libremente en la web:
Hay un trabajo previo de Jared con Carl Pomerance donde mejoran la constante C sustituyéndola por eγ.
La imagen destacada hoy esta inspirada en una cita de Carleson: Si quieres resolver problemas, como es mi caso, la propiedad más importante es ser muy muy terco. Si no los consejos de Pomerance y Maynard, este consejo, al menos, lo ha seguido Jared. Cuatro años tras una prueba imposible. La frase de Carleson me trae a la mente estas hierbas que crecen en el pavimento a pesar de todos los inconvenientes.
Cambiando la constante C en eγ
El ser A primitivo implica que los La son disjuntos dos a dos para a∈A. Pero en general, es fácil ver que para a≠b hay solo tres posibilidades, o bien La y Lb son disjuntos o La⊂Lb o Lb⊂La. Así que si llamamos al conjunto A L-primitivo cuando los La para a∈A son disjuntos, entonces el último paso en la demostración de Erdös se aplica para A L-primitivo.
Necesitaremos una variante del teorema de Mertens debida a Rosser y Schoenfeld ∏p<x(1−1p)≥e−γlog2x.
Lema 1. Sea A un conjunto L-primitivo y n>1 un entero con n∉A, entonces f(An):=f(A∩Ln)<eγd(Ln).
(Recordar que tenemos que probar que f(Aq)<f(q) cuando q es un primo que no está en A. Esto es un paso en la buena dirección pero todavía eγ es demasiado grande para nosotros)
Demostración. Cualquier a∈A∩Ln es múltiplo de n, y puesto que n∉A, a es compuesto, en particular a≥2P(a). Así que por la variante de Mertens 1aloga≤1alog(2P(a))≤eγa∏p<P(a)(1−1logp)≤eγd(La).
Dado un conjunto primitivo A y q∉A queremos probar la desigualdad f(Aq)≤f(q). Por el Lema 1 tenemos f(Aq)≤eγd(Lq)=eγq∏p<q(1−1p).
Primer paso: Mejorando la sustitución a→P(a) en la prueba de Erdös
Mirando la primera línea del razonamiento de Erdös vemos un punto en que la desigualdad puede mejorarse, cuando sustituimos loga por logP(a). Hay un exponente κ≥1 tal que P(a)κ=a. Poniendo κ=1+v obtenemos la siguiente mejora
Lema [Lema 2.5 en el artículo]. Sea A un conjunto L-primitivo. Sea v≥0 y n un entero n∉A, denotemos por q:=P(n). Si P(a)1+v≤a para todo a∈An, entonces f(An)=∑a∈An1aloga≤eγmqd(LAn)1+v.
Demostración. Puesto que n∉A todos los elementos de A son compuestos. Tenemos 1aloga≤11+v1alogP(a)=eγμP(a)11+v1a∏p<P(a)(1−1P(a))=eγμP(a)d(La)1+v.
Segundo paso: Mejorando el paso de los La disjuntos en la prueba de Erdös
Este es el punto clave de la prueba. Cuando A⊂Ln y A es primitivo obtenemos conjuntos La disjuntos todos ellos en Ln. Pero suponiendo que P(a)1+v≥a para todos los elementos en A, podemos obtener un conjunto L-primitivo mayor que A y todavía contenido en Ln. Así que buscamos un lema del tipo
Lema [Lema 3.1 del artículo]. Sea A un conjunto primitivo de números compuestos, y tomemos v∈(0,1). Si P(a)1+v≥a para todos los a∈A, entonces la colección de conjuntos Lac con a∈A y c∈Ca,v son disjuntos dos a dos. Ahí Ca,v:={c∈N:p∣c⟹p∈[P(a∗),P(a∗)1/√v)},
Proposición 1. Sea A un conjunto primitivo finito. Tomemos v∈(0,1), y un entero n>1 con n∉A, sea q=P(n)≥3. Si P(a)1+v>a para todo a∈A∩Ln entonces d(⋃a∈A∩LnLa)≤√vMqmqd(Ln).
[Idea de la demostración] Como antes podemos suponer que A=A∩Ln, por la observación previa tenemos Ln⊃⋃a∈A⋃c∈Ca,vLac,
Proposición. Para cualquier conjunto primitivo A, y cualquier entero n∉A con q=P(n)≥3, f(An) ≤ π4Mqm2qeγd(Ln).
Demostración [Esquema de la prueba] Consideremos una partición del intervalo [0,1], 0=v0<v1<⋯<vk=1 y separemos de acuerdo con él el conjunto A=⋃0≤i≤kA(i), donde A(i)={a∈A:P(a)1+vi≤a<P(a)1+vi+1},0≤i≤k−1,
El primo 2 necesita un tratamiento especial, pero no una idea importante adicional.
Dejar una contestacion