Teoría del tamiz

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

La teoría de tamices es un conjunto de técnicas generales de teoría de números diseñadas para contar o, de manera más realista, para 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 un límite prescrito X. En consecuencia, el ejemplo prototípico de un tamiz es el tamiz de Eratóstenes o el más general tamiz de Legendre . El ataque directo a los números primos utilizando estos métodos pronto alcanza obstáculos aparentemente insuperables, en el camino de la acumulación de términos de error. ^{[ cita requerida ]} En una de las principales corrientes de la teoría de números en el 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 requerida ]}

Un enfoque exitoso es aproximar un conjunto específico de números tamizados (por ejemplo, el conjunto de números primos) mediante otro conjunto más simple (por ejemplo, el conjunto de números casi primos ), que normalmente es algo más grande 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 se utilizan no para estimar el tamaño de un conjunto tamizado, sino para producir una función que es grande en el conjunto y mayoritariamente pequeña fuera de él, a la vez que es 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 las obras del matemático francés Jean Merlin, quien murió en la Primera Guerra Mundial y solo sobrevivieron dos de sus manuscritos. ^[2]

Teoría básica del tamiz

Para obtener información sobre la notación, consulte el final.

Comenzamos con una secuencia contable de números no negativos . En el caso más básico, esta secuencia es simplemente la función indicadora de un 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 una 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 de tamices 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 con 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 denotamos el conjunto y sea la cardinalidad. ${\displaystyle p\in {\mathcal {P}}}$ ${\displaystyle E_{p}=\{pn:n\in \mathbb {N} \}}$ ${\displaystyle |E_{p}|}$

Ahora presentamos una forma de calcular la cardinalidad de . Para ello, el rango de cribado será un ejemplo concreto de primos . ${\displaystyle A_{\operatorname {sift} }}$ ${\displaystyle {\mathcal {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, como se han eliminado los números que son divisibles por y dos veces, hay que sumar la cardinalidad . En el siguiente paso se elimina y se suma y de nuevo. 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 cribado 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

Sea y . La función de Möbius es negativa para cada 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 un término restante. La función de cribado 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).}$

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

La suma parcial de la función de cribado alternadamente cuenta en exceso y en defecto, por lo que el término restante será enorme. La idea de Brun para mejorar esto fue reemplazar en la función de cribado con una secuencia de pesos que consistía en funciones de Möbius restringidas. Al elegir dos secuencias apropiadas y y denotando las funciones de cribado con y , se pueden obtener límites inferior y superior para las funciones de cribado 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 multiplicativa, 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 se escribe para definir una secuencia . También en la literatura, la suma a veces se anota como la cardinalidad de algún conjunto , mientras que hemos definido como ya la cardinalidad de este conjunto. Solíamos denotar el conjunto de 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 de Brun , el tamiz de Selberg , el tamiz de Turán , el tamiz grande , el tamiz mayor y el tamiz de Goldston-Pintz-Yıldırım . Uno de los propósitos originales de la teoría de tamices era tratar de demostrar conjeturas en la teoría de números, como la conjetura de los primos gemelos . Si bien los amplios objetivos originales de la teoría de tamices aún no se han logrado en gran medida, ha habido algunos éxitos parciales, especialmente en combinación con otras herramientas de teoría de números. Los aspectos más destacados incluyen:

1. Teorema de Brun , que muestra 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 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 primo y otro número que es primo o semiprimo. Estos pueden considerarse casi idénticos a la conjetura de los primos gemelos y a la conjetura de Goldbach respectivamente.
3. El lema fundamental de la teoría de tamices , que afirma que si se tamiza un conjunto de N números, se puede estimar con precisión el número de elementos que quedan en el tamiz después de iteraciones, siempre que sea lo suficientemente pequeño (las fracciones como 1/10 son bastante típicas en este caso). Este lema suele ser demasiado débil para tamizar los números primos (que generalmente requieren algo así como iteraciones), pero puede ser suficiente para obtener resultados con respecto a los 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. Teorema de Zhang (Zhang 2014), que muestra que hay infinitos pares de primos dentro de una distancia acotada . El teorema de Maynard-Tao (Maynard 2015) generaliza el teorema de Zhang a secuencias arbitrariamente largas de primos.

Técnicas de la teoría de tamices

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

En comparación 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 pueden llegar a ser muy intrincados 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 que se analizan en este artículo no están estrechamente relacionados con los métodos de criba de factorización de números enteros, como la criba cuadrática y la criba de cuerpos numéricos generales . Esos métodos de factorización utilizan la idea de la criba de Eratóstenes para determinar de manera eficiente qué miembros de una lista de números se pueden factorizar completamente en primos pequeños.

Literatura

• Cojocaru, Alina Carmen ; Murty, M. Ram (2006), Introducción a los métodos de tamizado y sus aplicaciones , London Mathematical Society Student Texts, vol. 66, Cambridge University Press , ISBN 0-521-84816-4, Sr.  2200366
• Motohashi, Yoichi (1983), Lecciones sobre métodos de tamiz y teoría de números primos , Tata Institute of Fundamental Research Lectures on Mathematics and Physics, vol. 72, Berlín: Springer-Verlag , ISBN 3-540-12281-8, Sr.  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, Sr.  1836967
• Harman, Glyn (2007). Tamices de detección de primos . Monografías de la London Mathematical Society. Vol. 33. Princeton, NJ: Princeton University Press. ISBN 978-0-691-12437-7.MR 2331072.Zbl 1220.11118  . ​
• Halberstam, Heini ; Richert, Hans-Egon (1974). Métodos de tamizado . Monografías de la London Mathematical Society. Vol. 4. Londres-Nueva York: Academic Press . ISBN 0-12-318250-6.Sr. 0424730  .
• Iwaniec, Henryk ; Friedlander, John (2010), Opera de cribro , American Mathematical Society Colloquium Publications, vol. 57, Providence, RI: American Mathematical Society , ISBN 978-0-8218-4970-5, Sr.  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, Sr.  0404173
• Maynard, James (2015). "Pequeñas brechas entre números primos". Anales de Matemáticas . 181 (1): 383–413. arXiv : 1311.4600 . doi :10.4007/annals.2015.181.1.7. MR  3272929.
• Tenenbaum, Gérald (1995), Introducción a la teoría analítica y probabilística de números , Cambridge studies in advanced mathematics, vol. 46, Traducido de la segunda edición francesa (1995) de CB Thomas, Cambridge University Press , pp. 56–79, ISBN 0-521-41261-7, Sr.  1342300
• Zhang, Yitang (2014). "Bounded gaps between primes" (Brechas acotadas entre primos). Anales de Matemáticas . 179 (3): 1121–1174. doi : 10.4007/annals.2014.179.3.7 . MR  3171761.

Enlaces externos

• Bredikhin, BM (2001) [1994], "Método de 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 tamizado y sus aplicaciones . Cambridge University Press. doi :10.1017/CBO9780511615993. ISBN 978-0-521-84816-9.
3. (Iwaniec y Friedlander 2010)