צפיפות (תורת המספרים)

תבנית:סימון מתמטי תורת המספרים עוסקת בין השאר בקבוצות אינסופיות של מספרים טבעיים, ובהשוואה ביניהן. למשל, "מובן מאליו" שיש "יותר" מספרים זוגיים, מאשר מספרים ריבועיים; בקבוצת המספרים הטבעיים שעד מיליון יש חצי-מיליון מספרים זוגיים, ורק אלף מספרים ריבועיים (המילה "יותר" נתונה במירכאות משום שלשתי הקבוצות עוצמה זהה, ${\mathrm{\aleph }}_0$). טיפול מתמטי מסודר בשאלות כאלה נעשה בעזרת מושג הצפיפות, שאפשר להגדיר בכמה דרכים.

ההגדרה הפשוטה ביותר היא של צפיפות טבעית:תבנית:ש תהי $A$ קבוצת מספרים טבעיים. את הרישות שלה מסמנים $A(n)=A\cap \{1,\dots ,n\}$. העוצמה של הרישא מקיימת $0\le |A(n)|\le n$, וההשוואה בין הקבוצה $A$ לקבוצת כל המספרים נעשית דרך הסדרה $\frac{|A(n)|}{n}$. הגבול של סדרה זו (אם הוא קיים) נקרא בשם "הצפיפות הטבעית של הסדרה". צפיפות זו (אם קיימת) היא בהכרח מספר בין 0 ל-1. אם הגבול אינו קיים, אין לקבוצה צפיפות טבעית. במקרה זה אפשר להשתמש בגבול העליון ובגבול התחתון של הסדרה שקיימים תמיד, לתיאור הצפיפות; אולם מערכי גבולות אלה קשה יותר להסיק על תכונות הקבוצה.

בתורת המספרים האנליטית שכיחה יותר צפיפות דיריכלה, המכלילה את הצפיפות הטבעית: אם לקבוצה יש צפיפות טבעית, אז יש לה גם צפיפות דיריכלה, והן שוות. בתורת המספרים האדיטיבית נעזרים במושג אחר של צפיפות, הנקרא צפיפות שנירלמן.

צפיפות עליונה וצפיפות תחתונה

תהי $A$ תת-קבוצה של קבוצת המספרים הטבעיים $\mathbb{N}=\{1,2,\dots \}$.תבנית:ש לכל $n\in \mathbb{N}$ נגדיר $A(n)=A\cap \{1,\dots ,n\}$, ו-$0\le |A(n)|\le n$ הוא מספר האיברים של $A$.

נגדיר צפיפות עליונה של $A$:

$$\bar{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{|A(n)|}{n}$$

כאשר lim sup הוא גבול עליון.

נגדיר צפיפות תחתונה של $A$:

$$\underset{\_}{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{|A(n)|}{n}$$

כאשר lim inf הוא גבול תחתון. לקבוצה $A$ יש צפיפות $d(A)$ כאשר $\underset{\_}{d}(A)=\bar{d}(A)$, ובמקרה זה $d(A)$ שווה לערך משותף זה.

ניתן לנסח הגדרה זו באופן הבא:

$$d(A)=\underset{n\to \mathrm{\infty }}{\lim }\frac{|A(n)|}{n}$$

כאשר גבול זה קיים.תבנית:הערה

תכונות

נסמן את הצפיפות של קבוצה $A$ ב-$d(A)$. מתקיימות התכונות הבאות:

• לכל קבוצה סופית $F$ של מספרים טבעיים מתקיים $d(F)=0$.
• אם $d(A)$ קיים לקבוצה מסוימת $A$ ו-$A^c$ מסמן את המשלים שלה ב-$\mathbb{N}$, מתקיים $d(A^c)=1-d(A)$.
  • מסקנה: אם $F\subset \mathbb{N}$ היא קבוצה סופית (כולל המקרה $F=\mathrm{\varnothing }$), מתקיים $d(\mathbb{N}\setminus F)=1$.
• אם קיימים $d(A),d(B),d(A\cup B)$, אז מתקיים

$$\max \{d(A),d(B)\}\le d(A\cup B)\le \min \{d(A)+d(B),1\}$$

דוגמאות

• אם $A=\{n^2:n\in \mathbb{N}\}$ היא קבוצת כל המספרים הריבועיים, אז $d(A)=0$.
• אם $A=\{2n:n\in \mathbb{N}\}$ היא קבוצת כל המספרים הזוגיים, אז $d(A)=0.5$. באופן דומה, לכל סדרה חשבונית $A=\{an+b:n\in \mathbb{N}\}$ נקבל $d(A)=\frac{1}{a}$.
• לסדרה $P$ של כל המספרים הראשוניים נקבל לפי משפט המספרים הראשוניים כי $d(P)=0$.
• לקבוצת המספרים השופעים יש צפיפות גדולה מ-0. מרק דלגליז (Marc Deléglise) הראה ב-1998 שהצפיפות של קבוצה זו היא בין 0.2474 ל-0.2480.תבנית:הערה
• הקבוצה

$A=\bigcup _{n=0}^{\mathrm{\infty }}\{2^{2n},\dots ,2^{2n+1}-1\}$

של המספרים שהייצוג הבינארי שלהם כולל מספר אי-זוגי של ספרות היא דוגמה לקבוצה שאין לה צפיפות טבעית, משום שהצפיפות העליונה שלה היא

$\bar{d}(A)=\underset{m\to \mathrm{\infty }}{\lim }\frac{1+2^2+\cdots +2^{2m}}{2^{2m+1}-1}=\underset{m\to \mathrm{\infty }}{\lim }\frac{2^{2m+2}-1}{3(2^{2m+1}-1)}=\frac{2}{3}$

ואילו הצפיפות התחתונה שלה היא:

$\underset{\_}{d}(A)=\underset{m\to \mathrm{\infty }}{\lim }\frac{1+2^2+\cdots +2^{2m}}{2^{2m+2}-1}=\underset{m\to \mathrm{\infty }}{\lim }\frac{2^{2m+2}-1}{3(2^{2m+2}-1)}=\frac{1}{3}$

• לקבוצת המספרים שהייצוג העשרוני שלהם מתחיל בספרה 1 אין צפיפות טבעית: הצפיפות התחתונה היא 1/9 והצפיפות העליונה היא 5/9.תבנית:הערה (ראו: חוק בנפורד.)