Problem parzystości (teoria sita)

W teorii liczb problem parzystości odnosi się do ograniczeń w teorii sit , które uniemożliwiają sitom dawanie dobrych oszacowań w wielu rodzajach problemów z liczeniem liczb pierwszych . Problem został zidentyfikowany i nazwany przez Atle Selberga w 1949 r. Od około 1996 r. John Friedlander i Henryk Iwaniec opracowali kilka sit wrażliwych na parzystość, które sprawiają, że problem z parzystością jest mniejszą przeszkodą.

Oświadczenie

Terence Tao przedstawił to „szorstkie” stwierdzenie problemu:

Problem z parzystością . Jeśli A jest zbiorem, którego wszystkie elementy są iloczynami nieparzystej liczby liczb pierwszych (lub wszystkie są iloczynami parzystej liczby liczb pierwszych), to (bez wstrzykiwania dodatkowych składników) teoria sit nie jest w stanie podać nietrywialnych dolnych granic na rozmiar A. _ Ponadto wszelkie górne granice muszą różnić się od prawdy o współczynnik 2 lub więcej.

Ten problem jest istotny, ponieważ może wyjaśniać, dlaczego sitom trudno „wykryć liczby pierwsze”, innymi słowy podać nietrywialną dolną granicę liczby liczb pierwszych z pewną właściwością. Na przykład, w pewnym sensie twierdzenie Chena jest bardzo bliskie rozwiązaniu hipotezy bliźniaczych liczb pierwszych , ponieważ mówi, że istnieje nieskończenie wiele liczb pierwszych p takich, że p + 2 jest albo liczbą pierwszą, albo iloczynem dwóch liczb pierwszych. Problem parzystości sugeruje, że ponieważ interesujący nas przypadek ma nieparzystą liczbę czynników pierwszych (mianowicie 1), nie będzie możliwe oddzielenie tych dwóch przypadków za pomocą sit.

Przykład

Ten przykład pochodzi od Selberga i został podany jako ćwiczenie z podpowiedziami Cojocaru & Murty.

Problem polega na oddzielnym oszacowaniu liczby liczb ≤ x bez dzielników pierwszych ≤ x ^1/2 , które mają parzystą (lub nieparzystą) liczbę czynników pierwszych . Można wykazać, że bez względu na wybór wag na Bruna lub Selberga uzyskana górna granica będzie wynosić co najmniej (2 + o (1)) x / ln x dla obu problemów. Ale w rzeczywistości zbiór o parzystej liczbie czynników jest pusty, więc ma rozmiar 0. Zbiór o nieparzystej liczbie czynników to same liczby pierwsze między x ^1/2 a x, więc zgodnie z twierdzeniem o liczbach pierwszych jego rozmiar wynosi (1 + o (1)) x / ln x . Zatem te metody sitowe nie są w stanie podać użytecznej górnej granicy dla pierwszego zestawu i zawyżają górną granicę drugiego zestawu o współczynnik 2.

Sita wrażliwe na parzystość

Od około 1996 roku John Friedlander i Henryk Iwaniec opracowali kilka nowych technik przesiewania, aby „przełamać” problem parzystości. Jednym z triumfów tych nowych metod jest twierdzenie Friedlandera-Iwańca , które stwierdza, że ​​istnieje nieskończenie wiele liczb pierwszych postaci a ² + b ⁴ .

Glyn Harman odnosi problem parzystości do rozróżnienia informacji typu I i typu II na sicie.

Zjawisko Karatsuby

W 2007 roku Anatolij Aleksiejewicz Karatsuba odkrył brak równowagi między liczbami w ciągu arytmetycznym z zadanymi parzystościami liczby czynników pierwszych. Jego prace zostały opublikowane po jego śmierci.

Niech będzie zbiorem liczb naturalnych (dodatnich liczb $całkowitych$ ), to znaczy liczbami $\ kropki}$ . Zbiór liczb pierwszych, czyli takich liczb całkowitych , które mają tylko dwa różne dzielniki (mianowicie ${\ displaystyle n> 1} , n ∈ N {\ displaystyle n \ in \ mathbb {N}$$displaystyle$ n > 1 $1 } n}$ i ${\ displaystyle 1}$ ), jest oznaczony przez ${\ Displaystyle \ mathbb {P}}$ , ${\ Displaystyle \ mathbb {P} = \ {2,3,5, 7,11,\kropki \}\podzbiór \mathbb {N}}$ . Każda liczba naturalna ${\ Displaystyle n \ w \ mathbb {N}}$ , ${\ Displaystyle n> 1}$ , można przedstawić jako iloczyn liczb pierwszych (niekoniecznie odrębnych), to znaczy ${\ Displaystyle n = p_ {1} p_ {2} \ kropki p_ {k},}$ gdzie ${\ Displaystyle p_ {1} \ w \ mathbb {P}, \ p_ {2} \ w \ mathbb {P}, \ \ kropki, \ p_ { k}\in \mathbb {P} }$ , a taka reprezentacja jest jednoznaczna do rzędu czynników.

Jeśli utworzymy dwa zbiory, pierwszy składający się z dodatnich liczb całkowitych o parzystej liczbie czynników pierwszych, drugi składający się z dodatnich liczb całkowitych o nieparzystej liczbie czynników pierwszych, w ich reprezentacji kanonicznej, wówczas oba zbiory będą mniej więcej tej samej wielkości.

Jeśli jednak ograniczymy nasze dwa zbiory do tych dodatnich liczb całkowitych, których reprezentacja kanoniczna nie zawiera liczb pierwszych w postępie arytmetycznym , na przykład ${\ Displaystyle 6m + 1}$ , ${\ Displaystyle m = 1 , 2, \ kropki}$ lub progresja ${\ Displaystyle km + l}$ , ${\ Displaystyle 1 \ równoważnik l <k}$ , ${\ Displaystyle (l, k) = 1}$ , ${\ Displaystyle m = 0,1,2, \ kropki}$ , a następnie z tych dodatnich liczb całkowitych te z parzystą liczba czynników pierwszych będzie zwykle mniejsza niż tych, które mają nieparzystą liczbę czynników pierwszych. Karatsuba odkrył tę właściwość. Znalazł również wzór na to zjawisko, wzór na różnicę liczności zbiorów liczb naturalnych o nieparzystej i parzystej liczbie czynników pierwszych, gdy czynniki te są spełnione z pewnymi ograniczeniami. We wszystkich przypadkach, ponieważ zbiory, których to dotyczy, są nieskończone, przez „większy” i „mniejszy” rozumiemy granicę stosunku zbiorów, gdy górna granica liczb pierwszych dąży do nieskończoności. W przypadku liczb pierwszych zawierających ciąg arytmetyczny Karatsuba udowodnił, że granica ta jest nieskończona.

Przekształcamy zjawisko Karatsuby, używając terminologii matematycznej.

Niech i $\ Displaystyle \ mathbb {N} _ {1}$$}$ będą podzbiorami ${N}}$ tak, że ${\ Displaystyle n \ in \ mathbb {N} _ {0}}$ , jeśli ${\ displaystyle n}$ zawiera parzystą liczbę czynników pierwszych i ${\ Displaystyle n \ in \ mathbb {N} _ { 1}}$ , jeśli ${\ displaystyle n}$ zawiera nieparzystą liczbę czynników pierwszych. $w$ , rozmiary dwóch zestawów $.$ są przybliżeniu takie Dokładniej, dla wszystkich $}$ n ${0} (x)}$$\ Displaystyle$ i ${\ Displaystyle n_ {1} (x$ , gdzie ${\ Displaystyle n_ {0} (x)}$ to liczność zbioru wszystkich liczb z $\ Displaystyle$$\ mathbb {N} _ {0}}$ taka, że $\ Displaystyle n \ leq x}$ i ${\ Displaystyle n_ {1} (x)}$ to liczność zbioru wszystkich liczb ${\ Displaystyle n}$ z ${\ Displaystyle \ mathbb {N} _ { 1}}$ takie, że ${\ displaystyle n \ równoważnik x}$ . Asymptotyczne zachowanie $\ Displaystyle n_ {0} (x)}$${\ Displaystyle n_ {1} (x)}$ i zostało wyprowadzone przez E. Landau :

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

To pokazuje że

${\ Displaystyle n_ {0} (x) \ sim n_ {1} (x) \ sim {\ Frac {1} {2}} x,}$

to znaczy $(x)$$\ Displaystyle n_ {0}$ są asymptotycznie

Dalej,

${\ Displaystyle n_ {1} (x) -n_ {0} (x) = O \ lewo (xe ^ {-c {\sqrt {\ln x}}}\po prawej),}$

tak, że różnica między licznościami dwóch zestawów jest niewielka.

Z drugiej strony, jeśli pozwolimy być liczbą naturalną i $2$${r}}$${\ Displaystyle l_ {1}, l_ {2}$ być ciągiem liczb naturalnych, takim, że ${\ Displaystyle 1 \ równoważnik r <\ varphi (k)}$${\ Displaystyle 1 \ równoważnik l_ { j}<k}$ ; ${\ Displaystyle (l_ {j}, k) = 1}$ ; każdy $displaystyle$ inny modulo $k}$ ; ${\ Displaystyle j = 1,2, \ kropki r.}$ Niech ${\ Displaystyle \ mathbb {A}}$ będzie zbiorem liczb pierwszych należących do ciągów ${\ displaystyle kn + l_ {j}}$ ; ${\ Displaystyle j \ równoważnik r}$ . ( ${\ Displaystyle \ mathbb {A}}$ to zbiór wszystkich liczb pierwszych niepodzielnych ${\ displaystyle k}$ ).

Oznaczamy jako $zbiór$ liczb naturalnych, które nie zawierają czynników pierwszych z jako $mathbb {N} _ {0}^{*}}$${$$\$ podzbiór liczb z parzystej liczby czynników pierwszych, ponieważ $^ {*}}$$\ Displaystyle \ mathbb {$ podzbiór liczb z ${\ Displaystyle \ mathbb {N} ^ {*}}$ z nieparzystą liczbą czynników pierwszych. Definiujemy funkcje

${\ Displaystyle n ^ {*} (x) = \ Displaystyle \ suma _ {\ rozpocząć {tablica} {c} n \ równoważnik x \\ n \ w \ mathbb {N} ^ {*} \ koniec {tablica}} 1; n_ {0} ^ {*} (x) = \ Displaystyle \ suma _ {\ rozpocząć {tablica} {c} n \ równoważnik x \\ n \ w \ mathbb {N} _ {0} ^ {*} \end{array}}1;n_{1}^{*}(x)=\displaystyle\sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} _{ 1}^{*}\end{tablica}}1.}$

Karatsuba udowodnił, że dla formuły asymptotycznej ${\ Displaystyle x \ do + \ infty}$

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

jest poprawna, gdzie jest $stałą$ .

Pokazał również, że można udowodnić analogiczne twierdzenia dla innych zbiorów liczb naturalnych, na przykład dla liczb dających się przedstawić w postaci sumy dwóch kwadratów, oraz że zbiory liczb naturalnych, których wszystkie czynniki należą do $.$ wyświetli analogiczne asymptotyczne zachowanie

Twierdzenie Karatsuba zostało uogólnione dla przypadku, gdy jest $.$ nieograniczonym zbiorem liczb pierwszych

Zjawisko Karatsuba ilustruje następujący przykład. Rozważamy liczby naturalne, których reprezentacja kanoniczna nie obejmuje liczb pierwszych należących do ciągu , $…$ = $Displaystyle m = 1,2,$ Wówczas zjawisko to wyraża się wzorem:

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