teoría del tamiz

Formas de estimar el tamaño de conjuntos de números enteros tamizados

La teoría del tamiz es un conjunto de técnicas generales de la teoría de números , diseñadas para contar o, de manera más realista, estimar el tamaño de conjuntos tamizados de números enteros. El ejemplo prototípico de un conjunto tamizado es el conjunto de números primos hasta algún límite prescrito X. En consecuencia, el ejemplo prototípico de tamiz es el de Eratóstenes , o el más general de Legendre . El ataque directo a los números primos utilizando estos métodos pronto encuentra obstáculos aparentemente insuperables, en la forma de la acumulación de términos de error. ^{[ cita necesaria ]} En una de las principales corrientes de la teoría de números del siglo XX, se encontraron formas de evitar algunas de las dificultades de un ataque frontal con una idea ingenua de lo que debería ser el tamizado. ^{[ cita necesaria ]}

Un enfoque exitoso es aproximar un conjunto específico de números tamizados (por ejemplo, el conjunto de números primos) por otro conjunto más simple (por ejemplo, el conjunto de números casi primos ), que normalmente es algo mayor que el conjunto original y más fácil de analizar. Los tamices más sofisticados tampoco funcionan directamente con los conjuntos per se , sino que los cuentan de acuerdo con funciones de peso cuidadosamente elegidas en estos conjuntos (opciones para dar a algunos elementos de estos conjuntos más "peso" que otros). Además, en algunas aplicaciones modernas, los tamices no se utilizan para estimar el tamaño de un conjunto tamizado, sino para producir una función que es grande en el conjunto y mayormente pequeña fuera de él, siendo más fácil de analizar que la función característica del conjunto.

El término tamiz fue utilizado por primera vez por el matemático noruego Viggo Brun en 1915. ^[1] Sin embargo, el trabajo de Brun se inspiró en los trabajos del matemático francés Jean Merlin, quien murió en la Primera Guerra Mundial y solo dos de sus manuscritos sobrevivieron. ^[2]

Teoría básica del tamiz

Para obtener información sobre notación, consulte al final.

Comenzamos con alguna secuencia contable de números no negativos . En el caso más básico, esta secuencia es sólo la función indicadora de algún conjunto que queremos tamizar. Sin embargo, esta abstracción permite situaciones más generales. A continuación presentamos un conjunto general de números primos llamado rango de tamizado y su producto hasta como función . ${\displaystyle {\mathcal {A}}=(a_{n})}$ ${\displaystyle a_{n}=1_{A}(n)}$ ${\displaystyle A=\{s:s\leq x\}}$ ${\displaystyle {\mathcal {P}}\subseteq \mathbb {P} }$ ${\displaystyle z}$ ${\displaystyle P(z)=\prod \limits _{p\in {\mathcal {P}},p<z}p}$

El objetivo de la teoría del tamiz es estimar la función de tamizado.

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{n\leq x,{\text{gcd}}(n,P(z))=1}a_{n}.}$

En el caso de esto solo se cuenta la cardinalidad de un subconjunto de números, que son coprimos de los factores primos de . ${\displaystyle a_{n}=1_{A}(n)}$ ${\displaystyle A_{\operatorname {sift} }\subseteq A}$ ${\displaystyle P(z)}$

El principio de inclusión-exclusión

para definir ${\displaystyle {\mathcal {P}}}$

${\displaystyle A_{\operatorname {sift} }:=\{a\in A|(a,p_{1}\cdots p_{k})=1\},\quad p_{1},\dots ,p_{k}\in {\mathcal {P}}}$

y para cada primo denotemos el conjunto y sea la cardinalidad. Sea ahora un conjunto de números primos. ${\displaystyle p\in {\mathcal {P}}}$ ${\displaystyle E_{p}=\{pn:n\in \mathbb {N} \}}$ ${\displaystyle |E_{p}|}$ ${\displaystyle {\mathcal {P}}:=\{2,3,5,7,11,13\dots \}}$

Si se quiere calcular la cardinalidad de , se puede aplicar el principio de inclusión-exclusión . Este algoritmo funciona así: primero se elimina de la cardinalidad de la cardinalidad y . Ahora que se han eliminado los números que son divisibles por y dos veces, hay que sumar la cardinalidad . En el siguiente paso se quita y se agrega una y otra vez. Además ahora hay que eliminar , es decir, la cardinalidad de todos los números divisibles por y . Esto conduce al principio de inclusión-exclusión. ${\displaystyle A_{\operatorname {sift} }}$ ${\displaystyle |A|}$ ${\displaystyle |E_{2}|}$ ${\displaystyle |E_{3}|}$ ${\displaystyle 2}$ ${\displaystyle 3}$ ${\displaystyle |E_{6}|}$ ${\displaystyle |E_{5}|}$ ${\displaystyle |E_{10}|}$ ${\displaystyle |E_{15}|}$ ${\displaystyle |E_{30}|}$ ${\displaystyle 2,3}$ ${\displaystyle 5}$

${\displaystyle |A_{\operatorname {sift} }|=|A|-|E_{2}|-|E_{3}|+|E_{6}|-|E_{5}|+|E_{10}|+|E_{15}|-|E_{30}|+\cdots }$

La identidad de Legendre.

Podemos reescribir la función de tamizado con la identidad de Legendre.

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{d\mid P(z)}\mu (d)A_{d}(x)}$

utilizando la función de Möbius y algunas funciones inducidas por los elementos de ${\displaystyle A_{d}(x)}$ ${\displaystyle {\mathcal {P}}}$

${\displaystyle A_{d}(x)=\sum \limits _{n\leq x,n\equiv 0{\pmod {d}}}a_{n}.}$

Ejemplo

Deja y . La función de Möbius es negativa para todo primo, por lo que obtenemos ${\displaystyle z=7}$ ${\displaystyle {\mathcal {P}}=\mathbb {P} }$

${\displaystyle {\begin{aligned}S({\mathcal {A}},\mathbb {P} ,7)&=A_{1}(x)-A_{2}(x)-A_{3}(x)-A_{5}(x)+A_{6}(x)+A_{10}(x)+A_{15}(x)-A_{30}(x).\end{aligned}}}$

Aproximación de la suma de congruencia

Se supone entonces que se puede escribir como ${\displaystyle A_{d}(x)}$

${\displaystyle A_{d}(x)=g(d)X+r_{d}(x)}$

donde es una densidad , es decir, una función multiplicativa tal que ${\displaystyle g(d)}$

${\displaystyle g(1)=1,\qquad 0\leq g(p)<1\qquad p\in \mathbb {P} }$

y es una aproximación de y es algún término restante. La función de tamizado se convierte en ${\displaystyle X}$ ${\displaystyle A_{1}(x)}$ ${\displaystyle r_{d}(x)}$

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=X\sum \limits _{d\mid P(z)}\mu (d)g(d)+\sum \limits _{d\mid P(z)}\mu (d)r_{d}(x)}$

o en resumen

${\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=XG(x,z)+R(x,z).}$

Entonces se intenta estimar la función de tamizado encontrando los límites superior e inferior para y respectivamente . ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle R}$

La suma parcial de la función de tamizado alternativamente cuenta en exceso y en defecto, por lo que el término restante será enorme. La idea de Brun para mejorar esto fue sustituir la función de tamizado por una secuencia de pesas compuesta de funciones restringidas de Möbius. Al elegir dos secuencias apropiadas y y denotar las funciones de filtrado con y , se pueden obtener límites inferior y superior para las funciones de filtrado originales. ${\displaystyle \mu (d)}$ ${\displaystyle (\lambda _{d})}$ ${\displaystyle (\lambda _{d}^{-})}$ ${\displaystyle (\lambda _{d}^{+})}$ ${\displaystyle S^{-}}$ ${\displaystyle S^{+}}$

${\displaystyle S^{-}\leq S\leq S^{+}.}$^[3]

Como es multiplicativo, también se puede trabajar con la identidad. ${\displaystyle g}$

${\displaystyle \sum \limits _{d\mid n}\mu (d)g(d)=\prod \limits _{\begin{array}{c}p|n;\;p\in \mathbb {P} \end{array}}(1-g(p)),\quad \forall \;n\in \mathbb {N} .}$

Notación: una advertencia con respecto a la notación, en la literatura a menudo se identifica el conjunto de secuencias con el conjunto mismo. Esto significa que uno escribe para definir una secuencia . También en la literatura la suma a veces se indica como la cardinalidad de algún conjunto , mientras que nosotros ya hemos definido que es la cardinalidad de este conjunto. Solíamos denotar el conjunto de números primos y para el máximo común divisor de y . ${\displaystyle {\mathcal {A}}}$ ${\displaystyle A}$ ${\displaystyle {\mathcal {A}}=\{s:s\leq x\}}$ ${\displaystyle {\mathcal {A}}=(a_{n})}$ ${\displaystyle A_{d}(x)}$ ${\displaystyle |A_{d}(x)|}$ ${\displaystyle A_{d}(x)}$ ${\displaystyle A_{d}(x)}$ ${\displaystyle \mathbb {P} }$ ${\displaystyle (a,b)}$ ${\displaystyle a}$ ${\displaystyle b}$

Tipos de tamizado

Los tamices modernos incluyen el tamiz Brun , el tamiz Selberg , el tamiz Turán , el tamiz grande , el tamiz más grande y el tamiz Goldston-Pintz-Yıldırım . Uno de los propósitos originales de la teoría del tamiz era tratar de probar conjeturas en la teoría de números como la conjetura de los primos gemelos . Si bien los objetivos generales originales de la teoría de los tamices aún no se han logrado en gran medida, ha habido algunos éxitos parciales, especialmente en combinación con otras herramientas de la teoría de números. Los aspectos más destacados incluyen:

1. el teorema de Brun , que demuestra que la suma de los recíprocos de los primos gemelos converge (mientras que la suma de los recíprocos de todos los primos diverge);
2. El teorema de Chen , que muestra que hay infinitos números primos p tales que p + 2 es primo o semiprimo (el producto de dos primos); un teorema estrechamente relacionado de Chen Jingrun afirma que todo número par suficientemente grande es la suma de un número primo y otro número que es primo o semiprimo. Estos pueden considerarse casi errores de la conjetura de los primos gemelos y la conjetura de Goldbach , respectivamente.
3. El lema fundamental de la teoría del tamiz , que afirma que si uno está tamizando un conjunto de N números, entonces se puede estimar con precisión el número de elementos que quedan en el tamiz después de las iteraciones, siempre que sea lo suficientemente pequeño (fracciones como 1/10 son bastante típicas). aquí). Este lema suele ser demasiado débil para filtrar números primos (que generalmente requieren algo así como iteraciones), pero puede ser suficiente para obtener resultados relacionados con números casi primos. ${\displaystyle N^{\varepsilon }}$ ${\displaystyle \varepsilon }$ ${\displaystyle N^{1/2}}$
4. El teorema de Friedlander-Iwaniec , que afirma que hay infinitos números primos de la forma . ${\displaystyle a^{2}+b^{4}}$
5. El teorema de Zhang (Zhang 2014), que muestra que hay infinitos pares de números primos dentro de una distancia acotada . El teorema de Maynard-Tao (Maynard 2015) generaliza el teorema de Zhang a secuencias de números primos arbitrariamente largas.

Técnicas de la teoría del tamiz.

Las técnicas de la teoría de tamices pueden ser bastante poderosas, pero parecen estar limitadas por un obstáculo conocido como problema de paridad , que en términos generales afirma que los métodos de la teoría de tamices tienen extrema dificultad para distinguir entre números con un número impar de factores primos y números con un número impar de factores primos. número par de factores primos. Este problema de paridad aún no se comprende muy bien.

Comparada con otros métodos de la teoría de números, la teoría de tamices es comparativamente elemental , en el sentido de que no requiere necesariamente conceptos sofisticados ni de la teoría algebraica de números ni de la teoría analítica de números . Sin embargo, los tamices más avanzados todavía pueden volverse muy complejos y delicados (especialmente cuando se combinan con otras técnicas profundas de la teoría de números), y se han dedicado libros de texto enteros a este único subcampo de la teoría de números; una referencia clásica es (Halberstam & Richert 1974) y un texto más moderno es (Iwaniec & Friedlander 2010).

Los métodos de criba analizados en este artículo no están estrechamente relacionados con los métodos de criba de factorización de enteros, como la criba cuadrática y la criba de campo numérico general . Esos métodos de factorización utilizan la idea del tamiz de Eratóstenes para determinar de manera eficiente qué miembros de una lista de números pueden factorizarse completamente en números primos pequeños.

Literatura

• Cojocaru, Alina Carmen ; Murty, M. Ram (2006), Introducción a los métodos de tamizado y sus aplicaciones , Textos para estudiantes de la London Mathematical Society, vol. 66, Prensa de la Universidad de Cambridge , ISBN 0-521-84816-4, SEÑOR  2200366
• Motohashi, Yoichi (1983), Conferencias sobre métodos de tamiz y teoría de números primos , Conferencias del Instituto Tata de Investigación Fundamental sobre Matemáticas y Física, vol. 72, Berlín: Springer-Verlag , ISBN 3-540-12281-8, señor  0735437
• Greaves, George (2001), Tamices en la teoría de números, Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 43, Berlín: Springer-Verlag , doi :10.1007/978-3-662-04658-6, ISBN 3-540-41647-1, señor  1836967
• Harman, Glyn (2007). Tamices detectores de cebados . Monografías de la Sociedad Matemática de Londres. vol. 33. Princeton, Nueva Jersey: Princeton University Press. ISBN 978-0-691-12437-7. SEÑOR  2331072. Zbl  1220.11118.
• Halberstam, Heini ; Richert, Hans-Egon (1974). Métodos de tamiz . Monografías de la Sociedad Matemática de Londres. vol. 4. Londres-Nueva York: Academic Press . ISBN 0-12-318250-6. SEÑOR  0424730.
• Iwaniec, Henryk ; Friedlander, John (2010), Opera de cribro , Publicaciones del Coloquio de la Sociedad Matemática Estadounidense, vol. 57, Providence, RI: Sociedad Matemática Estadounidense , ISBN 978-0-8218-4970-5, señor  2647984
• Hooley, Christopher (1976), Aplicaciones de los métodos de tamiz a la teoría de números , Cambridge Tracts in Mathematics, vol. 70, Cambridge-Nueva York-Melbourne: Cambridge University Press , ISBN 0-521-20915-3, SEÑOR  0404173
• Maynard, James (2015). "Pequeños espacios entre números primos". Anales de Matemáticas . 181 (1): 383–413. arXiv : 1311.4600 . doi : 10.4007/annals.2015.181.1.7. SEÑOR  3272929.
• Tenenbaum, Gérald (1995), Introducción a la teoría analítica y probabilística de números , Estudios de Cambridge en matemáticas avanzadas, vol. 46, traducido de la segunda edición francesa (1995) por CB Thomas, Cambridge University Press , págs. 56–79, ISBN 0-521-41261-7, SEÑOR  1342300
• Zhang, Yitang (2014). "Brechas acotadas entre números primos". Anales de Matemáticas . 179 (3): 1121-1174. doi : 10.4007/anales.2014.179.3.7 . SEÑOR  3171761.

enlaces externos

• Bredikhin, BM (2001) [1994], "Método del tamiz", Enciclopedia de Matemáticas , EMS Press

Referencias

1. Brun, Viggo (1915). "Über das Goldbachsche Gesetz und die Anzahl der Primzahlpaare". Archivo de Matemáticas. Naturvidenskab . 34 .
2. Cojocaru, Alina Carmen; Murty, M. Ram (2005). Introducción a los métodos de tamiz y sus aplicaciones . Prensa de la Universidad de Cambridge. doi :10.1017/CBO9780511615993.
3. (Iwaniec y Friedlander 2010)