Naturlig densitet - Natural density

I talteori , naturliga densitet (även hänvisad till som asymptotisk densitet eller aritmetisk densitet ) är en metod att mäta hur "stora" en underuppsättning av uppsättningen av naturliga tal är. Det förlitar sig främst på sannolikheten att möta medlemmar av den önskade delmängden när man kammar genom intervallet [1,  n ] när n blir stor.

Intuitivt tros det att det finns fler positiva heltal än perfekta kvadrater , eftersom varje perfekt kvadrat redan är positivt, och många andra positiva heltal finns förutom. Uppsättningen positiva heltal är dock inte större än uppsättningen perfekta kvadrater: båda uppsättningarna är oändliga och räknbara och kan därför sättas i en-till-en-korrespondens . Ändå om man går igenom de naturliga siffrorna blir rutorna alltmer knappa. Begreppet naturlig densitet gör denna intuition exakt för många, men inte alla, delmängder av de naturliga (Se Schnirelmann-densitet , som liknar den naturliga densiteten men definierad för alla delmängder av ). ${\ displaystyle \ mathbb {N}}$

Om ett heltal väljs slumpmässigt från intervallet [1,  n ], är sannolikheten att det tillhör A förhållandet mellan antalet element av A i [1,  n ] och det totala antalet element i [1,  n ]. Om denna sannolikhet tenderar till viss gräns som n går mot oändligheten, då denna gräns kallas den asymptotiska densitet av A . Detta begrepp kan förstås som ett slags sannolikhet för att välja ett nummer från uppsättningen A . Faktum är att den asymptotiska densiteten (liksom vissa andra typer av densiteter) studeras i probabilistisk talteori .

Definition

En delmängd A av positiva heltal har naturlig densitet α om andelen element av A bland alla naturliga tal från 1 till n konvergerar till α när n tenderar till oändlighet.

Mer uttryckligt, om man definierar för varje naturligt tal n räkningsfunktionen en ( n ) som antalet element i A är mindre än eller lika med n , då den naturliga densiteten hos A är α exakt medel som

a ( n ) / n → α som n → ∞. 

Det följer av definitionen att om en uppsättning A har naturlig densitet α då 0 ≤ α ≤ 1.

Övre och nedre asymptotisk densitet

Låta vara en delmängd av uppsättningen naturliga tal För alla put och . ${\ displaystyle A}$${\ displaystyle \ mathbb {N} = \ {1,2, \ ldots \}.}$${\ displaystyle n \ in \ mathbb {N}}$${\ displaystyle A (n) = \ {1,2, \ ldots, n \} \ cap A.}$${\ displaystyle a (n) = | A (n) |}$

Definiera den övre asymptotiska densiteten (även kallad "övre densiteten") av by ${\ displaystyle {\ overline {d}} (A)}$${\ displaystyle A}$

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

där lim sup är gränsen överlägsen . är också känt helt enkelt som den övre densiteten av${\ displaystyle {\ overline {d}} (A)}$${\ displaystyle A.}$

På samma sätt definieras den lägre asymptotiska densiteten (även kallad "lägre densitet") av ${\ displaystyle {\ understrykning {d}} (A)}$${\ displaystyle A}$

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

där lim inf är gränsen sämre . Man kan säga har asymptotisk densitet om , i vilket fall är lika med detta gemensamma värde. ${\ displaystyle A}$${\ displaystyle d (A)}$${\ displaystyle {\ understrykning {d}} (A) = {\ överstrykning {d}} (A)}$${\ displaystyle d (A)}$

Denna definition kan omformuleras på följande sätt:

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

om denna gräns finns.

Det kan bevisas att definitionerna antyder att även följande gäller. Om man skulle skriva en delmängd av som en ökande sekvens indexerad av de naturliga siffrorna ${\ displaystyle \ mathbb {N}}$

${\ displaystyle A = \ {a_ {1} <a_ {2} <\ ldots \}}$

sedan

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

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

och om gränsen finns. ${\ displaystyle d (A) = \ lim _ {n \ rightarrow \ infty} {\ frac {n} {a_ {n}}}}$

En något svagare uppfattning om densitet är den övre Banach densiteten ; ges en uppsättning , definiera som ${\ displaystyle A \ subseteq \ mathbb {N}}$${\ displaystyle d ^ {*} (A)}$

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

Egenskaper och exempel

• Om d ( A ) finns för någon uppsättning A , och A ^c betecknar dess komplementuppsättning med avseende på då d ( A ^c ) = 1 -  d ( A ). ${\ displaystyle \ mathbb {N}}$
  • Naturlig följd: ${\ displaystyle d (\ mathbb {N}) = 1.}$

• Om och existerar, då${\ displaystyle d (A), d (B),}$${\ displaystyle d (A \ cup B)}$

${\ displaystyle \ max \ {d (A), d (B) \} \ leq d (A \ cup B) \ leq \ min \ {d (A) + d (B), 1 \}.}$

• För varje begränsad uppsättning F av positiva heltal är d ( F ) = 0.

• Om är uppsättningen av alla rutor, då är d ( A ) = 0.${\ displaystyle A = \ {n ^ {2}: n \ in \ mathbb {N} \}}$

• Om är uppsättningen av alla jämna tal, då är d ( A ) = 0,5. På samma sätt för alla aritmetiska framsteg vi får${\ displaystyle A = \ {2n: n \ in \ mathbb {N} \}}$${\ displaystyle A = \ {an + b: n \ in \ mathbb {N} \}}$${\ displaystyle d (A) = {\ tfrac {1} {a}}.}$

• För uppsättningen P för alla primtal får vi från primtalssatsen att d ( P ) = 0.

• Mängden av alla kvadratfritt heltal har densitet Mer allmänt mängden av alla n ^th -Power fria nummer för varje fysisk n har densitet där är zetafunktion Riemann .${\ displaystyle {\ tfrac {6} {\ pi ^ {2}}}.}$${\ displaystyle {\ tfrac {1} {\ zeta (n)}},}$${\ displaystyle \ zeta (n)}$

• Uppsättningen med rikliga siffror har icke-noll densitet. Marc Deléglise visade 1998 att densiteten för uppsättningen rikliga siffror och perfekta siffror är mellan 0.2474 och 0.2480.

• Uppsättningen

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

av tal vars binära expansion innehåller ett udda antal siffror är ett exempel på en uppsättning som inte har en asymptotisk densitet, eftersom den övre densiteten för denna uppsättning är

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

medan dess lägre densitet är

${\ displaystyle {\ understrykning {d}} (A) = \ lim _ {m \ till \ 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}}.}$

• Uppsättningen av siffror vars decimalaxpansion börjar med siffran 1 har på samma sätt ingen naturlig densitet: den lägre densiteten är 1/9 och den övre densiteten är 5/9. (Se Benfords lag .)

• Tänk på en ekvidistribuerad sekvens i och definiera en monotonfamilj med uppsättningar:${\ displaystyle \ {\ alpha _ {n} \} _ {n \ in \ mathbb {N}}}$${\ displaystyle [0,1]}$${\ displaystyle \ {A_ {x} \} _ {x \ in [0,1]}}$

${\ displaystyle A_ {x}: = \ {n \ in \ mathbb {N}: \ alpha _ {n} <x \}.}$

Sedan, per definition, för alla .${\ displaystyle d (A_ {x}) = x}$${\ displaystyle x}$

• Om S är en uppsättning av positiv övre densitet , säger Szemerédis sats att S innehåller godtyckligt stora ändliga aritmetiska framsteg , och Furstenberg – Sárközy-satsen säger att några två medlemmar av S skiljer sig åt med ett kvadratiskt antal.

Andra densitetsfunktioner

Andra densitetsfunktioner på delmängder av naturliga tal kan definieras analogt. Till exempel definieras den logaritmiska densiteten för en uppsättning A som gränsen (om den finns)

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

Övre och nedre logaritmiska densiteter definieras också analogt.

För uppsättningen multiplar av ett heltalssekvens anger Davenport – Erds teorem att den naturliga densiteten, när den finns, är lika med den logaritmiska densiteten.

Anteckningar

Se även

• Dirichlet densitet

Referenser

• Nathanson, Melvyn B. (2000). Elementära metoder i talteori . Graduate Texts in Mathematics. 195 . Springer-Verlag . ISBN 978-0387989129. Zbl  0953.11002 .
• Niven, Ivan (1951). "Den asymptotiska densiteten av sekvenser" . Bulletin of the American Mathematical Society . 57 (6): 420–434. doi : 10.1090 / s0002-9904-1951-09543-9 . MR  0044561 . Zbl  0044.03603 .
• Steuding, Jörn (2002). "Probabilistisk talteori" (PDF) . Arkiverad från originalet (PDF) den 22 december 2011 . Hämtad 2014-11-16 .
• Tenenbaum, Gérald (1995). Introduktion till analytisk och probabilistisk talteori . Cambridge-studier i avancerad matematik. 46 . Cambridge University Press . Zbl  0831.11001 .

Denna artikel innehåller material från asymptotisk densitet på PlanetMath , som är licensierat under Creative Commons Erkännande / Dela-Lika-licens .