Problema de paridad (teoría del tamiz)

En teoría de números , el problema de la paridad se refiere a una limitación de la teoría de tamices que impide que estos proporcionen buenas estimaciones en muchos tipos de problemas de conteo de primos . El problema fue identificado y nombrado por Atle Selberg en 1949. A partir de 1996, John Friedlander y Henryk Iwaniec desarrollaron algunos tamices sensibles a la paridad que hacen que el problema de la paridad sea un obstáculo menor.

Declaración

Terence Tao dio esta declaración "aproximada" del problema: ^[1]

Problema de paridad . Si A es un conjunto cuyos elementos son todos productos de un número impar de primos (o son todos productos de un número par de primos), entonces (sin inyectar ingredientes adicionales), la teoría de tamices no puede proporcionar límites inferiores no triviales para el tamaño de A. Además, cualquier límite superior debe estar alejado de la verdad por un factor de 2 o más.

Este problema es importante porque puede explicar por qué es difícil para los tamices "detectar primos", en otras palabras, dar un límite inferior no trivial para el número de primos con alguna propiedad. Por ejemplo, en cierto sentido, el teorema de Chen está muy cerca de una solución de la conjetura de los primos gemelos , ya que dice que hay infinitos primos p tales que p + 2 es primo o el producto de dos primos. El problema de la paridad sugiere que, debido a que el caso de interés tiene un número impar de factores primos (es decir, 1), no será posible separar los dos casos utilizando tamices.

Ejemplo

Este ejemplo se debe a Selberg y se ofrece como ejercicio con sugerencias de Cojocaru y Murty. ^{[2] : 133–134}

El problema es estimar por separado el número de números ≤ x sin divisores primos ≤ x ^1/2 , que tienen un número par (o impar) de factores primos . Se puede demostrar que, sin importar la elección de pesos en un tamiz de tipo Brun o Selberg , el límite superior obtenido será al menos (2 + o (1)) x / ln x para ambos problemas. Pero de hecho el conjunto con un número par de factores está vacío y por lo tanto tiene tamaño 0. El conjunto con un número impar de factores es simplemente los primos entre x ^1/2 y x , por lo que por el teorema de los números primos su tamaño es (1 + o (1)) x / ln x . Por lo tanto, estos métodos de tamiz no pueden dar un límite superior útil para el primer conjunto, y sobreestiman el límite superior en el segundo conjunto por un factor de 2.

Tamices sensibles a la paridad

A partir de 1996, John Friedlander y Henryk Iwaniec desarrollaron algunas nuevas técnicas de tamiz para "romper" el problema de la paridad. ^{[3] [4]} Uno de los triunfos de estos nuevos métodos es el teorema de Friedlander-Iwaniec , que establece que hay infinitos primos de la forma a ² + b ⁴ .

Glyn Harman relaciona el problema de la paridad con la distinción entre información tipo I y tipo II en un tamiz. ^[5]

Fenómeno Karatsuba

En 2007, Anatolii Alexeevitch Karatsuba descubrió un desequilibrio entre los números de una progresión aritmética con paridades dadas del número de factores primos. Sus artículos ^{[6] [7]} fueron publicados después de su muerte.

Sea un conjunto de números naturales (enteros positivos) es decir, los números . El conjunto de los primos, es decir, los enteros , , que tienen sólo dos divisores distintos (a saber, y ), se denota por , . Todo número natural , , se puede representar como un producto de primos (no necesariamente distintos), es decir , donde , y dicha representación es única hasta el orden de los factores. ${\displaystyle \mathbb {N} }$ ${\displaystyle 1,2,3,\dots }$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle n>1}$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle \mathbb {P} }$ ${\displaystyle \mathbb {P} =\{2,3,5,7,11,\dots \}\subset \mathbb {N} }$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle n>1}$ ${\displaystyle n=p_{1}p_{2}\dots p_{k},}$ ${\displaystyle p_{1}\in \mathbb {P} ,\ p_{2}\in \mathbb {P} ,\ \dots ,\ p_{k}\in \mathbb {P} }$

Si formamos dos conjuntos, el primero formado por números enteros positivos que tienen un número par de factores primos, y el segundo formado por números enteros positivos que tienen un número impar de factores primos, en su representación canónica, entonces los dos conjuntos tienen aproximadamente el mismo tamaño.

Sin embargo, si limitamos nuestros dos conjuntos a aquellos enteros positivos cuya representación canónica no contiene primos en progresión aritmética , por ejemplo , o la progresión , , , , entonces de estos enteros positivos, aquellos con un número par de factores primos tenderán a ser menos que aquellos con un número impar de factores primos. Karatsuba descubrió esta propiedad. Encontró también una fórmula para este fenómeno, una fórmula para la diferencia en cardinalidades de conjuntos de números naturales con cantidad par e impar de factores primos, cuando estos factores se cumplen con ciertas restricciones. En todos los casos, dado que los conjuntos involucrados son infinitos, por "mayor" y "menor" queremos decir que el límite de la razón de los conjuntos como un límite superior en los primos tiende al infinito. En el caso de los primos que contienen una progresión aritmética, Karatsuba demostró que este límite es infinito. ${\displaystyle 6m+1}$ ${\displaystyle m=1,2,\dots }$ ${\displaystyle km+l}$ ${\displaystyle 1\leq l<k}$ ${\displaystyle (l,k)=1}$ ${\displaystyle m=0,1,2,\dots }$

Reformulamos el fenómeno Karatsuba utilizando terminología matemática.

Sean y subconjuntos de , tales que , si contiene un número par de factores primos, y , si contiene un número impar de factores primos. Intuitivamente, los tamaños de los dos conjuntos y son aproximadamente iguales. Más precisamente, para todo , definimos y , donde es la cardinalidad del conjunto de todos los números de tales que , y es la cardinalidad del conjunto de todos los números de tales que . El comportamiento asintótico de y fue derivado por E. Landau : ^[8] ${\displaystyle \mathbb {N} _{0}}$ ${\displaystyle \mathbb {N} _{1}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle n\in \mathbb {N} _{0}}$ ${\displaystyle n}$ ${\displaystyle n\in \mathbb {N} _{1}}$ ${\displaystyle n}$ ${\displaystyle \mathbb {N} _{0}}$ ${\displaystyle \mathbb {N} _{1}}$ ${\displaystyle x\geq 1}$ ${\displaystyle n_{0}(x)}$ ${\displaystyle n_{1}(x)}$ ${\displaystyle n_{0}(x)}$ ${\displaystyle n}$ ${\displaystyle \mathbb {N} _{0}}$ ${\displaystyle n\leq x}$ ${\displaystyle n_{1}(x)}$ ${\displaystyle n}$ ${\displaystyle \mathbb {N} _{1}}$ ${\displaystyle n\leq x}$ ${\displaystyle n_{0}(x)}$ ${\displaystyle n_{1}(x)}$

${\displaystyle n_{0}(x)={\frac {1}{2}}x+O\left(xe^{-c{\sqrt {\ln x}}}\right),n_{1}(x)={\frac {1}{2}}x+O\left(xe^{-c{\sqrt {\ln x}}}\right);c>0.}$

Esto demuestra que

${\displaystyle n_{0}(x)\sim n_{1}(x)\sim {\frac {1}{2}}x,}$

es decir y son asintóticamente iguales. ${\displaystyle n_{0}(x)}$ ${\displaystyle n_{1}(x)}$

Más,

${\displaystyle n_{1}(x)-n_{0}(x)=O\left(xe^{-c{\sqrt {\ln x}}}\right),}$

de modo que la diferencia entre las cardinalidades de los dos conjuntos es pequeña.

Por otra parte, si dejamos que sea un número natural, y sea una sucesión de números naturales, , tales que ; ; todos son diferentes módulo ; Sea un conjunto de primos pertenecientes a las progresiones ; . ( es el conjunto de todos los primos que no dividen a ). ${\displaystyle k\geq 2}$ ${\displaystyle l_{1},l_{2},\dots l_{r}}$ ${\displaystyle 1\leq r<\varphi (k)}$ ${\displaystyle 1\leq l_{j}<k}$ ${\displaystyle (l_{j},k)=1}$ ${\displaystyle l_{j}}$ ${\displaystyle k}$ ${\displaystyle j=1,2,\dots r.}$ ${\displaystyle \mathbb {A} }$ ${\displaystyle kn+l_{j}}$ ${\displaystyle j\leq r}$ ${\displaystyle \mathbb {A} }$ ${\displaystyle k}$

Denotamos como un conjunto de números naturales, que no contienen factores primos de , y como un subconjunto de números de con número par de factores primos, como un subconjunto de números de con número impar de factores primos. Definimos las funciones ${\displaystyle \mathbb {N} ^{*}}$ ${\displaystyle \mathbb {A} }$ ${\displaystyle \mathbb {N} _{0}^{*}}$ ${\displaystyle \mathbb {N} ^{*}}$ ${\displaystyle \mathbb {N} _{1}^{*}}$ ${\displaystyle \mathbb {N} ^{*}}$

${\displaystyle n^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} ^{*}\end{array}}1;n_{0}^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} _{0}^{*}\end{array}}1;n_{1}^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} _{1}^{*}\end{array}}1.}$

Karatsuba demostró que para , la fórmula asintótica ${\displaystyle x\to +\infty }$

${\displaystyle n_{1}^{*}(x)-n_{0}^{*}(x)\sim Cn^{*}(x)(\ln x)^{2\left({\frac {r}{\varphi (k)}}-1\right)},}$

es válido, donde es una constante positiva. ${\displaystyle C}$

También demostró que es posible demostrar teoremas análogos para otros conjuntos de números naturales, por ejemplo, para números que son representables en forma de suma de dos cuadrados, y que los conjuntos de números naturales, cuyos factores pertenecen a , mostrarán un comportamiento asintótico análogo. ${\displaystyle \mathbb {A} }$

El teorema de Karatsuba se generalizó para el caso cuando hay un cierto conjunto ilimitado de números primos. ${\displaystyle \mathbf {A} }$

El fenómeno Karatsuba se ilustra con el siguiente ejemplo. Consideremos los números naturales cuya representación canónica no incluye primos pertenecientes a la progresión , . Entonces este fenómeno se expresa con la fórmula: ${\displaystyle 6m+1}$ ${\displaystyle m=1,2,\dots }$

${\displaystyle n_{1}^{*}(x)-n_{0}^{*}(x)\sim {\frac {\pi }{8{\sqrt {3}}}}{\frac {n^{*}(x)}{\ln x}},\qquad x\to +\infty .}$

Notas

1. Tao, Terence (5 de junio de 2007). «Cuestión abierta: el problema de la paridad en la teoría de tamices» . Consultado el 11 de agosto de 2008 .
2. Cojocaru, Alina Carmen ; M. Ram Murty (2005). Introducción a los métodos de tamizado y sus aplicaciones . Textos para estudiantes de la London Mathematical Society. Vol. 66. Cambridge University Press. ISBN 0-521-61275-6.
3. Friedlander, John ; Henryk Iwaniec (18 de febrero de 1997). "Uso de un tamiz sensible a la paridad para contar valores primos de un polinomio". Actas de la Academia Nacional de Ciencias . 94 (4): 1054–1058. Bibcode :1997PNAS...94.1054F. doi : 10.1073/pnas.94.4.1054 . PMC 19742 . PMID  11038598. 1054–1058. 
4. Friedlander, John ; Henryk Iwaniec (1998). "Tamiz asintótica para primos". Anales de Matemáticas . 148 (3): 1041–1065. arXiv : math/9811186 . Bibcode :1998math.....11186F. doi :10.2307/121035. JSTOR  121035. S2CID  11574656.
5. Harman, Glyn (2007). Tamices de detección de primos . Monografías de la London Mathematical Society. Vol. 33. Princeton University Press. págs. 45, 335. ISBN. 978-0-691-12437-7.Zbl 1220.11118  .
6. Karatsuba, AA (2011). "Una propiedad del conjunto de números primos". Encuestas matemáticas rusas . 66 (2): 209–220. Código Bibliográfico :2011RuMaS..66..209K. doi :10.1070/RM2011v066n02ABEH004739.
7. Karatsuba, AA (2011). "Una propiedad del conjunto de primos como base multiplicativa de los números naturales". Doklady Mathematics (84:1): 1–4.
8. Landau, E. (1912). "Über die Anzahl der Gitter punkte in gewissen Bereichen". Gött. Nachricht. : 687–771.