Paritetsproblem (siktteori)

I talteorin hänvisar paritetsproblemet till en begränsning i siktteorin som hindrar siktar från att ge bra uppskattningar i många typer av primtalsproblem . Problemet identifierades och namngavs av Atle Selberg 1949. Med början omkring 1996 utvecklade John Friedlander och Henryk Iwaniec några paritetskänsliga siktar som gör paritetsproblemet mindre av ett hinder.

Påstående

Terence Tao gav detta "grova" uttalande om problemet:

Paritetsproblem . Om A är en mängd vars element alla är produkter av ett udda antal primtal (eller alla är produkter av ett jämnt antal primtal), då (utan att injicera ytterligare ingredienser), kan siktteorin inte ge icke-triviala nedre gränser på storleken på A. Dessutom måste alla övre gränser vara borta från sanningen med en faktor 2 eller mer.

Detta problem är betydande eftersom det kan förklara varför det är svårt för siktar att "upptäcka primtal", med andra ord att ge en icke-trivial nedre gräns för antalet primtal med någon egenskap. Till exempel, i en mening Chens sats är mycket nära en lösning av tvillingprimtalsförmodan , eftersom den säger att det finns oändligt många primtal p så att p + 2 är antingen primtal eller produkten av två primtal. Paritetsproblemet antyder att eftersom fallet av intresse har ett udda antal primtalsfaktorer (nämligen 1), kommer det inte att vara möjligt att separera de två fallen med hjälp av siktar.

Exempel

Detta exempel beror på Selberg och ges som en övning med tips av Cojocaru & Murty.

Problemet är att separat uppskatta antalet tal ≤ x utan primtalsdelare ≤ x ^1/2 , som har ett jämnt (eller ett udda) antal primtalsfaktorer . Det kan visas att, oavsett val av vikter i en Brun - eller Selberg -typ, kommer den erhållna övre gränsen att vara minst (2 + o (1)) x / ln x för båda problemen. Men i själva verket är mängden med ett jämnt antal faktorer tom och det har också storlek 0. Mängden med ett udda antal faktorer är bara primtal mellan x 1/2 ^och x, så enligt primtalssatsen är dess storlek (1) + o (1)) x / ln x . Således kan dessa siktmetoder inte ge en användbar övre gräns för den första uppsättningen, och överskattar den övre gränsen för den andra uppsättningen med en faktor 2.

Paritetskänsliga silar

Med början omkring 1996 utvecklade John Friedlander och Henryk Iwaniec några nya sikttekniker för att "bryta" paritetsproblemet. En av triumferna för dessa nya metoder är Friedlander–Iwaniec-satsen , som säger att det finns oändligt många primtal av formen a ² + b ⁴ .

Glyn Harman relaterar paritetsproblemet till skillnaden mellan typ I- och typ II -information i en sikt.

Karatsuba-fenomen

2007 upptäckte Anatolii Alexeevitch Karatsuba en obalans mellan talen i en aritmetisk progression med givna pariteter av antalet primtalsfaktorer. Hans tidningar publicerades efter hans död.

Låt $\mathbb {N}$ vara en uppsättning naturliga tal (positiva heltal), det vill säga talen $1,2,3,\dots$ . Uppsättningen av primtal, det vill säga sådana heltal $n\in \mathbb {N}$ , $n>1$ , som bara har två distinkta divisorer (nämligen $n$ och $1$ ), betecknas med $\mathbb {P}$ , $\mathbb {P} =\{2,3,5,7,11,\dots \}\subset \mathbb {N}$ . Varje naturligt tal $n\in \mathbb {N}$ , $n>1$ , kan representeras som en produkt av primtal (inte nödvändigtvis distinkta), det vill säga $n=p_{1}p_{2}\dots p_{k},$ där ${\displaystyle p_{1 }\in \mathbb {P} ,\ p_{2}\in \mathbb {P} ,\ \dots ,\ p_{k}\in \mathbb {P} } , och sådan representation är unik upp till$ ordningen faktorer.

Om vi ​​bildar två mängder, den första består av positiva heltal med jämna antal primtalsfaktorer, och den andra består av positiva heltal med ett udda antal primtalsfaktorer, i sin kanoniska representation, då är de två uppsättningarna ungefär lika stora.

Om vi ​​däremot begränsar våra två uppsättningar till de positiva heltal vars kanoniska representation inte innehåller några primtal i aritmetisk progression , till exempel $6m+1$ , $m=1 ,2,\dots$ eller progressionen $km+l$ , $1\leq l<k$ , $(l, k)=1$ , ${\displaystyle m=0,1,2,\dots } ,$ då av dessa positiva heltal tenderar de med ett jämnt antal primtalsfaktorer att vara färre än de med udda antal primtalsfaktorer. Karatsuba upptäckte den här egenskapen. Han hittade också en formel för detta fenomen, en formel för skillnaden i kardinaliteter av uppsättningar av naturliga tal med udda och jämna antal primtalsfaktorer, när dessa faktorer är uppfyllda med vissa restriktioner. I alla fall, eftersom de inblandade mängderna är oändliga, menar vi med "större" och "mindre" gränsen för förhållandet mellan mängderna då en övre gräns för primtal går till oändlighet. I fallet med primtal som innehåller en aritmetisk progression, bevisade Karatsuba att denna gräns är oändlig.

Vi upprepar Karatsuba-fenomenet med matematisk terminologi.

Låt $\mathbb {N} _{0}$ och $\mathbb {N} _{1}$ vara delmängder av $\mathbb {N}$ , så att $n\in \mathbb {N} _{0}$ , om $n$ innehåller ett jämnt antal primtalsfaktorer, och $n\in \mathbb {N} _{ 1}$ , om $n$ innehåller ett udda antal primtalsfaktorer. Intuitivt är storlekarna på de två uppsättningarna $\mathbb {N} _{0}$ och $\mathbb {N} _{1}$ ungefär desamma. Mer exakt, för alla $x\geq 1$ definierar vi $n_{0}(x)$ och $n_{1}(x)$ , där $n_{0}(x)$ är kardinaliteten för mängden av alla tal $n$ från $\mathbb {N} _{0}$ så att $n\leq x$ , och $n_{1}(x)$ är kardinaliteten för mängden av alla tal $n$ från $\mathbb {N} _{1}$ så att $n\leq x$ . Det asymptotiska beteendet för $n_{0}(x)$ och $n_{1}(x)$ härleddes av E. Landau :

$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.$

Detta visar det

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

det vill säga $n_{0}(x)$ och $n_{1}(x)$ är asymptotiskt lika.

Ytterligare,

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

så att skillnaden mellan kardinaliteterna för de två uppsättningarna är liten.

Å andra sidan, om vi låter $k\geq 2$ vara ett naturligt tal, och $l_{1},l_{2},\dots l_ {r}$ vara en följd av naturliga tal, $1\leq r<\varphi (k)$ , så att $1\leq l_{ j}<k$ ; $(l_{j},k)=1$ ; varje $l_{j}$ är olika modulo $k$ ; $j=1,2,\dots r.$ Låt $\mathbb {A}$ vara en uppsättning primtal som hör till följderna $kn+l_{j}$ ; $j\leq r$ . ( $\mathbb {A}$ är mängden av alla primtal som inte delar $k$ ).

Vi betecknar som $\mathbb {N} ^{*}$ en uppsättning naturliga tal, som inte innehåller primtalsfaktorer från $\mathbb {A}$ , och som $\ mathbb {N} _{0}^{*}$ en delmängd av tal från $\mathbb {N} ^{*}$ med jämna antal primtalsfaktorer, som $\mathbb { N} _{1}^{*}$ en delmängd av tal från $\mathbb {N} ^{*}$ med udda antal primtalsfaktorer. Vi definierar funktionerna

$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\i \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 bevisade att för $x\to +\infty$ , den asymptotiska formeln

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

är giltig, där $C$ är en positiv konstant.

Han visade också att det är möjligt att bevisa de analoga satserna för andra uppsättningar av naturliga tal, till exempel för tal som kan representeras i form av summan av två kvadrater, och att mängder av naturliga tal, som alla faktorer tillhör till $\mathbb {A}$ , kommer att visa analogt asymptotiskt beteende.

Karatsuba-satsen generaliserades för det fall då $\mathbf {A}$ är en viss obegränsad uppsättning primtal.

Karatsuba-fenomenet illustreras av följande exempel. Vi betraktar de naturliga tal vars kanoniska representation inte inkluderar primtal som hör till progressionen $6m+1$ , $m=1,2,\dots$ . Sedan uttrycks detta fenomen med formeln:

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