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

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

בערך זה נעשה שימוש בסימנים מוסכמים מתחום המתמטיקה. להבהרת הסימנים ראו סימון מתמטי.

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

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

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

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

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

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

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

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

$${\displaystyle {\underline {d}}(A)=\liminf _{n\to \infty }{\frac {|A(n)|}{n}}}$$

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

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

$${\displaystyle d(A)=\lim _{n\to \infty }{\frac {|A(n)|}{n}}}$$

כאשר גבול זה קיים.^[1]

תכונות

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

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

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

דוגמאות

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

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

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

${\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}}}$

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

${\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}}}$

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