קבוצות פרימיטיביות

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

הנושא הוא נסיון לכמת את הגודל של קבוצות פרימיטיביות.

הגדרה: קבוצה $A \subset \mathbb{N}$ נקראת פרימיטיבית אם אין בה שני מספרים שאחד הוא כפולה של השני.

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

תוצאות קלאסיות

לקבוצות פרימיטיביות לא בהכרח יש צפיפות 0: לחלקן הצפיפות לא מוגדרת (כלומר $\lim \sup > \lim \inf$).

דוגמא (קבוצה פרימיטיבית בלי צפיפות מוגדרת): נשים לב שבמספרים $\{n+1, n+2, \ldots, 2n\}$ אין אחד שהוא כפולה של אחר. אם בוחרים סדרה $n_1, n_2, \ldots$ שגדלה בקצב מאוד מאוד מהיר, אפשר לבנות קבוצה פרימיטיבית בשלבים: מתחילים מ-$[n_1+1, 2n_1]$, מוסיפים את האיברים מתוך $[n_2+1, 2n_2]$ שהם לא כפולות שלהם, וכן הלאה. כך אפשר לקבל קבוצה פרימיטיבית שהצפיפות שלה מתקרבת ל-$1/2$ אינסוף פעמים.

דרך אחרת למדוד גודל של קבוצה $A \subset \mathbb{N}$ היא לשקול טורים מהצורה $ \sum_{n\in A}f(n)$. למשל, האם הטור $\sum_{n\in A}1/n$ מתכנס ומה הסכום שלו. הטור הזה עשוי להתבדר עבור קבוצות פרימיטיביות, וכך קורה למשל עבור המספרים הראשוניים.

טענה: סכום ההפכיים של הראשוניים מתבדר ($\sum_p 1/p = \infty$). כדי לראות זאת, נשים לב שלכל $n \in \mathbb{N}$ מתקיים

$$ \sum_{k =1}^{n} \frac{1}{k} \le \sum_{b = 1}^{n} \frac{1}{b^2} \cdot \prod_{p \le n} \left( 1 + \frac{1}{p} \right) \le \tfrac{\pi^2}{6} \prod_{p \le n} e^{1/p} = \tfrac{\pi^2}{6} e^{\sum_{p \le n} 1/p} $$

ובהוצאת לוגריתם מקבלים שהטור $\sum 1/p$ מתבדר מהר כמו $\log \log n$. (המעבר הראשון בשורה משתמש בעובדה שכל מספר אפשר לפרק למכפלה של ראשוניים שונים כפול מספר ריבועי)

דרך קצת יותר עדינה למדוד גודל של קבוצה $A \subset \mathbb{N}$, היא סכום הטור $\sum_{n\in A}\frac{1}{n \log n}$. זה מתבדר עבור $A = \mathbb{N}$ אבל מתכנס עבור הראשוניים.

טענה: $\sum_p \frac{1}{p \log p}<\infty$. נתחיל מחישוב עזר: עבור $2^k < p \le 2^{k+1}$ מתקיים

$$ \frac{1}{p \log p} = \frac{\log p}{p \log^2 p} \le \frac{1}{2^k k^2 \log^2 2} \log p $$

ומצד שני

$$ \sum_{2^k < p \le 2^{k+1}} \log p \le \log \binom{2^{k+1}}{2^k} \le \log 2^{2^{k+1}} = 2^{k+1} \log 2 $$

ולכן

$$ \sum_{2^k < p \le 2^{k+1}} \frac{1}{p \log p} \le \frac{2^{k+1} \log 2}{2^k k^2 \log^2 2} = \frac{2}{k^2 \log 2} $$

אם סוכמים על פני כל ה-$k$-ים זה יוצא כל $\sum \frac{1}{p \log p}$ וזה מתכנס.

הטור $\sum_{n\in A} \frac{1}{n \log n}$ מתכנס לכל קבוצה פרימיטיבית $A$, ולא רק עבור הראשוניים. ארדש הוכיח את זה במאמר משנת 1935. השאלה הבאה היא מה סכום הטור. ארדש שיער שלמספרים הראשוניים יש את הסכום הכי גבוה מבין הקבוצות הפרימיטיביות (הסכום הוא $1.6366\ldots$), וזה הוכח לפני כמה שנים.

אם מגבילים את תשומת הלב לתת-מחלקות מסוימות של קבוצות פרימיטיביות, החסם העליון נעשה קטן יותר. ארדש שאל מה החסם על $\sum_{n\in A}\frac{1}{n \log n}$ עבור $A \subset \mathbb{N} \cap [a, \infty)$ פרימיטיבית, ושיער שזה שואף ל-$1$ כאשר $a$ שואף לאינסוף. זה מה שהוכח השבוע.

תהליך מרקוב

רעיון ההוכחה הוא להשתמש בסדרות עולות של מספרים, שאיברים עוקבים הם כפולות זה של זה: $n_1 \mid n_2 \mid n_3 \mid \ldots$. הסדרות ייבנו כשרשראות מרקוב, שמתחילות במספרים מ-$a$ ומעלה, כאשר מכל מספר ניתן לעבור רק לכפולות שלו. כיוון שבקבוצה פרימיטיבית אין איברים שהם כפולה זה של זה, כל סדרה כזו יכולה לגעת בקבוצה רק בנקודה אחת.

הגדרה: $v(n)$ היא ההסתברות שהסדרה עוברת בנקודה $n$.

בהוכחה נסדר את ההסתברויות ההתחלתיות והסתברויות המעבר ככה שיהיה בקירוב $v(n) \approx \frac{1}{n \log n}$. אם $A$ קבוצה פרימיטיבית, התהליך פוגש את $A$ פעם אחת לכל היותר ולכן $\sum_{n \in A}v(n) \le 1$.

נעשה כמה חישובים כדי להבין מה דרוש כדי לבנות תהליך כזה. נסמן בהם ב-$b(n)$ את ההסתברות להתחיל בנקודה $n$ וב-$P(m \to n)$ את הסתברות המעבר. אז $v(n)$ מקיימת את התכונה הרקורסיבית

$$ .v(n) = b(n) + \sum_{d \mid n} v(d) P(d \to n) $$

באופן גס, כמות המחלקים של מספר היא בערך לוגריתמית. לכן בסכום יש משהו כמו $\log n$ מחוברים, ונרצה שהם יהיו קטנים בערך פי $\log n$ מ-$v(n)$. נציב את הערך המקורב $v(n) \approx \frac{1}{n\log n}$ בסכום

$$ .\sum_{d \mid n} \frac{1}{d \log d}P(d \to n) $$

כדי שכל אחד מהמחוברים יהיה בערך $\frac{1}{n \log^2 n}$ נרצה $P(d \to n) \approx \frac{d \log d}{n \log^2 n}$.

בשביל ההוכחה צריך שזה יעבוד בדיוק, ואת זה עושים בעזרת פונקציית משקול שתתקן את זה שאין בדיוק $\log n$ מחלקים ל-$n$, שסכום הסתברויות המעבר לא יעבור את $1$ וכו'. הסכום לא יצא בדיוק הערך הרצוי ל-$v(n)$ ואת היתרה סופגים לתוך $b(n)$ באופן שהסכום של הסתברויות ההתחלה יהיה $1$.

פונקציית פון מנגולד

הגדרה: פונקציית פון מנגולד $\Lambda : \mathbb{N} \to \mathbb{R}$ נתמכת בחזקות ראשוניים:

$$ \Lambda(n) = \begin{cases}\log p & n = p^k \\ 0 & \text{otherwise} \end{cases} $$

נמנה כמה תכונות שיהיו שימושיות לנו בהוכחה בהמשך.

תכונה 1: $\sum_{d\mid n} \Lambda(d) = \log n$. זה כיוון שאם ראשוני כלשהו $p$ מופיע $k$ פעמים בפירוק לגורמים של $n$, בסכום יופיע $\log p$ עבור $d = p, p^2, \ldots, p^k$.

תכונה 2: $\sum_{k=1}^{n}\Lambda(k) = O(n)$. את זה מוודאים בשלוש רדוקציות: ראשית, אפשר לקזז את חזקות הראשוניים (יש רק בערך $n^{1/2}$ כאלה). שנית, מספיק לבדוק עבור קטעים גדלים מעריכית. שלישית, הראשוניים בקטע כזה הם גורמים של $\binom{2n}{n}$ ולכן סכום הלוגריתמים שלהם הוא $O(n)$ (בדומה בחישוב הקלאסי למעלה).

תכונה 3: $\sum_{k=1}^{n}\frac{\Lambda(k)}{k} = \log n + O(1)$. את זה אפשר לראות בעזרת קירוב סטירלינג $\log(n!) \sim n \log n$:

$$ \sum_{k=1}^{n}\frac{\Lambda(k)}{k} = \frac{1}{n} \left( \sum_{k=1}^{n} \left\lfloor\frac{n}{k}\right\rfloor\Lambda(k) + \sum_{k=1}^{n} \left\{\frac{n}{k}\right\}\Lambda(k) \right) = \tfrac{1}{n} \sum_{k=1}^{n} \left\lfloor\frac{n}{k}\right\rfloor\Lambda(k) + \tfrac{1}{n}O(n) $$

$$ \tfrac{1}{n} \sum_{k=1}^{n} \left\lfloor\frac{n}{k}\right\rfloor\Lambda(k) = \tfrac{1}{n} \sum_{m=1}^{n} \sum_{k \mid m} \Lambda(k) = \tfrac{1}{n} \sum_{m=1}^{n} \log m = \tfrac{1}{n} \log(n!) = \log n + O(1) $$

תכונות 2 ו-3 אומרות שבמובנים מסויימים, הפונקצייה $\Lambda$ היא משקול מחדש של המספרים הטבעיים, כלומר הכמות הכוללת בטווחים גדולים היא מאותו סדר גודל בכמה מדדים שונים. אבל תכונה 1 מראה שפונקציית פון מנגולד מרכזת את הצפיפות באופן שיותר נוח לאריתמטיקה כפלית.

בנוסף לאלה אנחנו נצטרך חישוב טכני שיהיה שימושי בכמה מקומות בהוכחה.

למה: קיים $C > 0$ שלכל $m,y \ge 2$ מתקיים

$$ \sum_{q=y}^{\infty} \frac{\Lambda(q)}{q \log^2(mq)} \le \frac{1}{\log(my)} + \frac{C}{\log^2(my)} $$

נשים לב שמובטח פה $C$ יחיד שעובד עבור כל $m$ ו-$y$.

הוכחה: נסמן

$$ .u(t) = \sum_{k=y}^{\lfloor t \rfloor}\Lambda(k)/k \quad , \quad v(t)=1/\log^2(mt) $$

הסכום בלמה הוא $\sum_{q=y}^\infty [u(q)-u(q-1)] v(q)$. נפעיל את הטרנספורמציה של סכימה בחלקים ונקבל שזה שווה ל-$-\int_y^\infty u(t) v'(t) dt$. מתכונה 3 נובע $u(q) = \log(q/y) + O(1)$, ובעזרת אינטגרציה בחלקים נקבל

$$ \begin{align*} \int_y^\infty \frac{2\log (t/y) + O(1)}{t \log^3(mt)} dt & = \int_y^\infty \frac{1}{t \log^2(mt)} dt + \int_y^\infty \frac{O(1)}{t \log^3(mt)} dt \\ & = \frac{1}{\log(my)} + \frac{O(1)}{\log^2(my)} \end{align*} $$

הערה וסימון: הלמה הזו מבטיחה שקיים $y$ כזה ש-$\sum_{q=y}^{\infty}\frac{\Lambda(q)\log m}{q \log^2(mq)} \le 1$ לכל $m$. נסמן את $y$ הזה בשם $q_0$.

ההוכחה שיצאה השבוע

משפט: אם $A \subset \mathbb{N}$ קבוצה פרימיטיבית, אז

$$ .\sum_{n \in A}\frac{1}{n \log n} \le 1 + O(\tfrac{1}{\log(\min(A))}) $$

אנחנו נסמן $a = \min(A)$, ונבנה תהליך מרקוב שתלוי ב-$a$ (אך לא ב-$A$) שאפשר יהיה להסיק ממנו שהסכום חסום ע"י $1 + O(1 / \log a)$.

הגדרה: התהליך העולה הוא תהליך מרקובי שיוצר סדרות $\{n_1, n_2, \ldots\}$ לפי ההסתברויות

$$ \begin{align*} ,&P(n_1 = n) = \frac{1}{Z} \frac{1}{n \log^2 n} \sum_{\substack{d \mid n \\ d \notin [a, n/q_0]}} \Lambda(\tfrac{n}{d}) \\ .&P(n_{t+1} = q\cdot m \mid n_t = m) = \frac{\log m}{q \log^2 (qm)} \Lambda(q) \end{align*} $$

כאשר ההסתברויות מוגדרות רק למספרים מ-$a$ ומעלה, $Z$ הוא גורם נרמול שנקבע כך שסכום הסתברויות ההתחלה יהיה $1$, והסתברויות המעבר אינן $0$ רק לכפולות $m \to q \cdot m$ עם $q \ge q_0$.

הערה: הסתברויות ההתחלה מנורמלות לפי הגורם $Z$, אבל הסתברויות המעבר לא. לפי ההערה בסעיף הקודם הסכום שלהן אינו עולה על $1$, אבל הוא באופן כללי יהיה נמוך מ-1. נגדיר במקרה זה שבהסתברות שנותרה התהליך נפסק.

טענה: $Z = 1 + O(1/\log a)$.

הוכחה: לסכום שמגדיר את $Z$

$$ Z = \sum_{n=a}^{\infty} \tfrac{1}{n \log^2 n} \!\!\! \sum_{\substack{d \mid n \\ d \notin [a, n/q_0]}} \!\! \Lambda(\tfrac{n}{d}) $$

יש שני חלקים: המחלקים $d>n/q_0$ נותנים

$$ ,\sum_{n=a}^{\infty} \tfrac{1}{n \log^2 n} \sum_{\substack{d \mid n \\ d < q_0}} \Lambda(d) \le \sum_{n=a}^{\infty} \tfrac{1}{n \log^2 n} \cdot \sum_{k=1}^{q_0} \Lambda(k) $$

והגורם הראשון הוא מסדר גודל של $O(1/\log a)$ והשני חסום.

המחלקים הקטנים $d < \min\{a, n/q_0\}$ נותנים

$$ ,\sum_{n=a}^\infty \tfrac{1}{n \log^2 n} \!\!\! \sum_{\substack{d \mid n \\ d > \max\{q_0, n/a\}}} \!\!\! \Lambda(d) = \sum_{d=q_0+1}^{\infty} \sum_{k=\lceil\frac{a}{d}\rceil}^{a-1} \frac{\Lambda(d)}{kd \log^2(kd)} \le \sum_{k=1}^{a} \frac{1}{k} \sum_{d=\lceil\frac{a}{k}\rceil}^{\infty} \frac{\Lambda(d)}{d \log^2(kd)} $$

ולפי הלמה מלמעלה זה

$$ \begin{align*} \ & \le \sum_{k=1}^{a} \frac{1}{k} \left( \frac{1}{\log(k\lceil\tfrac{a}{k}\rceil)} + \frac{C}{\log^2(k\lceil\tfrac{a}{k}\rceil)} \right) \\ & \le \sum_{k=1}^a \frac{1}{k} \cdot \left(\frac{1}{\log a} + \frac{C}{\log^2 a}\right) = 1 + O\left(\frac{1}{\log a}\right) \end{align*} $$

טענה: לכל $n \ge a$, הסיכוי שהסדרה עוברת ב-$n$ הוא $v(n) = \frac{1}{Z n \log n}$. את זה נראה באינדוקציה על $n$: נניח שזה מתקיים למספרים קטנים יותר, ונקבל

$$ v(n) = \frac{1}{Z n \log^2 n} \sum_{\substack{d \mid n \\ d \notin [a, n/q_0]}} \! \Lambda(\tfrac{n}{d}) + \!\!\! \sum_{\substack{m \mid n \\ m \in [a, n/q_0]}} \!\!\! v(m) P(m \to n) = \frac{1}{Z n \log^2 n} \sum_{d \mid n} \Lambda(\tfrac{n}{d}) $$

ובסך הכל $v(n) = \frac{\log n}{Z n \log^2 n} = \frac{1}{Z n \log n}$.

הוכחת המשפט: אם $A \subset \mathbb{N} \cap [a, \infty)$ קבוצה פרימיטיבית, מתקיים $\sum_{n \in A}v(n) \le 1$, ולכן $\sum_{n \in A}\frac{1}{n \log n} \le Z = 1 + O(1 / \log a)$.