Přirozená hustota - Natural density

v teorie čísel, přirozená hustota (označovaný také jako asymptotická hustota nebo aritmetická hustota) je jednou z metod měření, jak „velká“ a podmnožina z soubor z přirozená čísla je. Spoléhá se hlavně na pravděpodobnost setkání s členy požadované podskupiny při česání skrz interval [1, n] tak jako n roste velký.

Intuitivně se předpokládá, že jich je více kladná celá čísla než perfektní čtverce, protože každý dokonalý čtverec je již kladný a kromě toho existuje mnoho dalších kladných celých čísel. Sada kladných celých čísel však ve skutečnosti není větší než sada dokonalých čtverců: obě sady jsou nekonečný a počitatelný a proto mohou být vloženy osobní korespondence. Pokud však člověk prochází přirozenými čísly, čtverců je stále méně. Pojem přirozené hustoty činí tuto intuici přesnou pro mnoho, ale ne všechny, podmnožiny přirozených (viz Schnirelmannova hustota, který je podobný přirozené hustotě, ale je definován pro všechny podmnožiny ${ displaystyle mathbb {N}}$).

Pokud je z intervalu [1 náhodně vybráno celé číslo,n], pak pravděpodobnost, ke které patří A je poměr počtu prvků A v 1,n] na celkový počet prvků v [1,n]. Pokud má tato pravděpodobnost sklon k něčemu omezit tak jako n má sklon k nekonečnu, pak se tento limit označuje jako asymptotická hustota A. Tuto představu lze chápat jako určitý druh pravděpodobnosti výběru čísla ze sady A. Ve skutečnosti je asymptotická hustota (stejně jako některé další typy hustot) studována v pravděpodobnostní teorie čísel.

Definice

Podmnožina A kladných celých čísel má přirozenou hustotu α pokud je podíl prvků A mezi všemi přirozená čísla od 1 do n konverguje k α tak jako n inklinuje k nekonečnu.

Přesněji řečeno, pokud definujeme pro jakékoli přirozené číslo n počítání funkce A(n) jako počet prvků A menší nebo rovno n, pak to přirozená hustota A bytosti α přesně znamená^[1]

A(n) / n → α jako n → ∞.

Z definice vyplývá, že pokud množina A má přirozenou hustotu α pak 0 ≤ α ≤ 1.

Horní a dolní asymptotická hustota

Nechat ${ displaystyle A}$ být podmnožinou množiny přirozených čísel ${ displaystyle mathbb {N} = {1,2, ldots }.}$ Pro všechny ${ displaystyle n in mathbb {N}}$ dát ${ displaystyle A (n) = {1,2, ldots, n } cap A.}$ a ${ displaystyle a (n) = | A (n) |}$.

Definujte horní asymptotická hustota (nazývané také „vyšší hustota“) ${ displaystyle { overline {d}} (A)}$ z ${ displaystyle A}$ podle

${ displaystyle { overline {d}} (A) = limsup _ {n rightarrow infty} { frac {a (n)} {n}}}$

kde lim sup je limit lepší. ${ displaystyle { overline {d}} (A)}$ je také známá jednoduše jako horní hustota ${ displaystyle A.}$

Podobně, ${ displaystyle { underline {d}} (A)}$, nižší asymptotická hustota (nazývaná také "nižší hustota") ${ displaystyle A}$, je definováno

${ displaystyle { underline {d}} (A) = liminf _ {n rightarrow infty} { frac {a (n)} {n}}}$

kde lim inf je limit horší. Dá se říci ${ displaystyle A}$ má asymptotickou hustotu ${ displaystyle d (A)}$ -li ${ displaystyle { underline {d}} (A) = { overline {d}} (A)}$, v jakém případě ${ displaystyle d (A)}$ se rovná této společné hodnotě.

Tuto definici lze přepracovat následujícím způsobem:

${ displaystyle d (A) = lim _ {n rightarrow infty} { frac {a (n)} {n}}}$

pokud tento limit existuje.^[2]

Je dokázáno, že definice naznačují, že platí i následující. Pokud by někdo napsal podmnožinu ${ displaystyle mathbb {N}}$ jako rostoucí posloupnost indexovaná přirozenými čísly

${ displaystyle A = {a_ {1}$

pak

${ displaystyle { underline {d}} (A) = liminf _ {n rightarrow infty} { frac {n} {a_ {n}}},}$

${ displaystyle { overline {d}} (A) = limsup _ {n rightarrow infty} { frac {n} {a_ {n}}}}$

a${ displaystyle d (A) = lim _ {n rightarrow infty} { frac {n} {a_ {n}}}}$pokud limit existuje.

Trochu slabší představa o hustotě je horní Banachova hustota; dostal sadu ${ displaystyle A subseteq mathbb {N}}$, definovat ${ displaystyle d ^ {*} (A)}$ tak jako

${ displaystyle d ^ {*} (A) = limsup _ {NM rightarrow infty} { frac {| A cap {M, M + 1, ldots, N } |} {N-M +1}}}$

Vlastnosti a příklady

• Li d(A) existuje pro nějakou sadu A, a A^C označuje jeho sada doplňků s ohledem na ${ displaystyle mathbb {N}}$ pak d(A^C) = 1 − d(A).
  • Důsledek: ${ displaystyle d ( mathbb {N}) = 1.}$

• Li ${ displaystyle d (A), d (B),}$ a ${ displaystyle d (A pohár B)}$ tedy existují

${ displaystyle max {d (A), d (B) } leq d (A pohár B) leq min {d (A) + d (B), 1 }.}$

• Pro všechny konečná množina F kladných celých čísel, d(F) = 0.

• Li ${ displaystyle A = {n ^ {2}: n in mathbb {N} }}$ je tedy množina všech čtverců d(A) = 0.

• Li ${ displaystyle A = {2n: n in mathbb {N} }}$ je tedy množina všech sudých čísel d(A) = 0,5. Podobně pro jakýkoli aritmetický postup ${ displaystyle A = {an + b: n in mathbb {N} }}$ dostaneme ${ displaystyle d (A) = { tfrac {1} {a}}.}$

• Pro sadu P ze všech připraví dostaneme z věta o prvočísle že d(P) = 0.

• Sada všech celá čísla bez čtverců má hustotu ${ displaystyle { tfrac {6} { pi ^ {2}}}.}$ Obecněji řečeno, soubor všech n^th- čísla bez energie pro všechny přirozené n má hustotu ${ displaystyle { tfrac {1} { zeta (n)}},}$ kde ${ displaystyle zeta (n)}$ je Funkce Riemann zeta.

• Sada hojná čísla má nenulovou hustotu.^[3] Marc Deléglise v roce 1998 ukázal, že hustota množiny hojných čísel a dokonalých čísel je mezi 0,2474 a 0,2480.^[4]

• Sada

${ displaystyle A = bigcup _ {n = 0} ^ { infty} left {2 ^ {2n}, ldots, 2 ^ {2n + 1} -1 right }}$

čísel, jejichž binární expanze obsahuje lichý počet číslic, je příklad množiny, která nemá asymptotickou hustotu, protože horní hustota této množiny je

${ displaystyle { overline {d}} (A) = lim _ {m to infty} { frac {1 + 2 ^ {2} + cdots + 2 ^ {2m}} {2 ^ {2m +1} -1}} = lim _ {m to infty} { frac {2 ^ {2m + 2} -1} {3 (2 ^ {2m + 1} -1)}} = { frac {2} {3}},}$

zatímco jeho nižší hustota je

${ displaystyle { underline {d}} (A) = lim _ {m to infty} { frac {1 + 2 ^ {2} + cdots + 2 ^ {2m}} {2 ^ {2m +2} -1}} = lim _ {m to infty} { frac {2 ^ {2m + 2} -1} {3 (2 ^ {2m + 2} -1)}} = { frac {1} {3}}.}$

• Sada čísel, jejichž desítkové rozšíření začíná číslicí 1, podobně nemá přirozenou hustotu: nižší hustota je 1/9 a horní hustota je 5/9.^[1] (Vidět Benfordův zákon.)

• Zvažte ekvidistribuovaná sekvence ${ displaystyle { alpha _ {n} } _ {n in mathbb {N}}}$ v ${ displaystyle [0,1]}$ a definovat monotónní rodinu ${ displaystyle {A_ {x} } _ {x v [0,1]}}$ sad:

${ displaystyle A_ {x}: = {n v mathbb {N}: alpha _ {n}$

Podle definice ${ displaystyle d (A_ {x}) = x}$ pro všechny ${ displaystyle x}$.

• Li S je sada pozitivních horních hustot Szemerédiho věta tvrdí, že S obsahuje libovolně velké konečné aritmetické průběhy a Furstenberg – Sárközyho věta uvádí, že asi dva členové S se liší čtvercovým číslem.

Další funkce hustoty

Analogicky lze definovat další funkce hustoty u podmnožin přirozených čísel. Například logaritmická hustota sady A je definován jako limit (pokud existuje)

${ displaystyle mathbf { delta} (A) = lim _ {x rightarrow infty} { frac {1} { log x}} sum _ {n v A, n leq x} { frac {1} {n}} .}$

Analogicky jsou definovány také horní a dolní logaritmické hustoty.

Pro množinu násobků celočíselné sekvence je Davenport – Erdősova věta uvádí, že přirozená hustota a logaritmická hustota jsou stejné.^[5]

Poznámky

Viz také

• Dirichletova hustota
• Schnirelmannova hustota

Reference

• Nathanson, Melvyn B. (2000). Základní metody v teorii čísel. Postgraduální texty z matematiky. 195. Springer-Verlag. ISBN  978-0387989129. Zbl  0953.11002.
• Niven, Ivan (1951). „Asymptotická hustota sekvencí“. Bulletin of the American Mathematical Society. 57 (6): 420–434. doi:10.1090 / s0002-9904-1951-09543-9. PAN  0044561. Zbl  0044.03603.
• Steuding, Jörn (2002). "Pravděpodobnostní teorie čísel" (PDF). Archivovány od originál (PDF) dne 22. prosince 2011. Citováno 2014-11-16.
• Tenenbaum, Gérald (1995). Úvod do analytické a pravděpodobnostní teorie čísel. Cambridge studia pokročilé matematiky. 46. Cambridge University Press. Zbl  0831.11001.

Tento článek obsahuje materiál z asymptotické hustoty PlanetMath, který je licencován pod Creative Commons Attribution / Share-Alike License.