השבוע התפרסם מאמר פורץ דרך בקומבינטוריקה, שמוכיח שאם קבוצה $A \subset \mathbb{N}$ היא "גדולה" במובן שהטור $\sum_{n \in A} \frac{1}{n}$ מתבדר, אז ב-$A$ יש אינסוף סדרות חשבוניות באורך 3. זה ממשיך את המחקר שהתחיל בהשערה של ארדש וטוראן, שהוכחה ע"י סמרדי: קבוצה של מספרים טבעיים עם צפיפות חיובית בטבעיים מכילה סדרות חשבוניות בכל אורך.
ההשערה הזו הניעה מחקר בשאלה מה הגודל המקסימלי של קבוצה מתוך $\{1, \ldots, N\}$ שלא מכילה סדרות חשבוניות באורך 3 (ובדומה על סדרות חשבוניות ארוכות יותר). לא שואלים על סדרות באורך 1 או 2 כי כאלה יש בכל קבוצה עם איבר אחד או שני איברים בהתאמה.
שאלה דומה היא בעיית ה-Cap set, ששואלת כמה גדולה יכולה להיות קבוצה ב-$F_3^n$ שלא מכילה סדרות חשבוניות באורך 3. זו בעיה קלה יותר לניתוח בגלל המבנה האלגברי העשיר יותר: יש יותר תתי חבורות וזה מאפשר להגיע לתוצאות חזקות באנליזת פורייה, וכמו כן כל סדרה כזו היא ישר במרחב $F_3^n$ וזה מקל על השימוש בשיטות פולינומיאליות בבעיה הזו. לאחרונה הוכחה תוצאה חזקה בעניין: קבוצה כזו לא יכולה להכיל יותר מאשר $2.756^n$ איברים. במונחי $N=3^n$, גודל הקבוצה חסום ע"י $N^{0.922}$. הבעיה הזו מוכרת למי שמשחק במשחק Set, כשעולה השאלה אם לפתוח עוד שורה.
ראוי להזכיר בהקשר זה גם את משפט גרין-טאו: קבוצה בעלת צפיפות חיובית במספרים הראשוניים מכילה סדרות חשבוניות מכל אורך. גם לזה יש הכללות, למשל לראשוניים הגאוסיים ולסדרות יותר כלליות. תכונה מעניינת של המספרים הראשוניים היא שסכום ההפכיים שלהם מתבדר, וזה העלה את השאלה אם באופן כללי קבוצה שסכום ההפכיים שלה מתבדר מכילה סדרות חשבוניות מכל אורך.
סדרות חשבוניות באורך 3 קלות יותר לניתוח בין השאר בגלל שהן ניתנות לביטוי במשוואה דיופנטית אחת: מתקיים $(x,y,z) = (x,x+d,x+2d)$ אם ורק אם $x + z = 2y$. פתרונות למשוואה הזו שבהם $x \neq z$ נותנים סדרה חשבונית.
המשפט של בלום וסיססק קובע שקבוצה $A \subset \{1, \ldots, N\}$ שאינה מכילה סדרה חשבונית היא מגודל $c_1 \frac{N}{(\log N)^{1 + c_2}}$ לכל היותר, כאשר $c_1,c_2 > 0$ קבועים כלשהם שניתנים לחישוב במפורש. לדעת המחברים $c_2$ שמושג בהוכחה שלהם הוא מסדר גודל של $2^{-2^{2^{1000}}}$. מזה נובע שאם בקבוצה אינסופית $A \subset \mathbb{N}$ אין סדרות חשבוניות, הסכום שלה מתכנס. ניתן לראות זאת מסכימה בחלקים: נסמן $F(N) = | A \cap \{1, \ldots, N\} |$ ונקבל
$$
\begin{align*}
\sum_{\substack{n \le N \\ n \in A}} \frac{1}{n}
& = \sum_{n=1}^N \frac{1}{n} \big( F(n) – F(n-1) \big) \\
& = \frac{F(N)}{N} + \frac{F(1)}{2} + \sum_{n=2}^N F(n) \big( \frac{1}{n} – \frac{1}{n+1} \big) \\
& = \frac{F(N)}{N} + \frac{F(1)}{2} + \int_2^N \frac{F(t)}{t^2} dt \\
& = \frac{c_1}{(\log N)^{1+c_2}} + \frac{1}{2} + \int_2^N \frac{c_1}{t (\log t)^{1+c_2}} dt
\end{align*}
$$
והאינטגרל האחרון חסום כי החלפת משתנים $t=e^s$ מעבירה אותו לצורה
$$ \int_{\log 2}^{\log N} \frac{c_1}{s^{1 + c_2}} ds \le \frac{c_1}{c_2 2^{c_2}} $$
לא קראתי את המאמר עד הסוף, אבל אכתוב פה קצת על שיטת ההוכחה. ההוכחה משתמשת באנליזת פורייה, כמו בכמה מההוכחות שצוינו לעיל.
תהי $A \subset \{1, \ldots, N \}$. נשכן אותה בחבורה החיבורית $\mathbb{Z} / N'\mathbb{Z}$ עם $N'$ קרוב ל-$N$ אבל שלא ייצור סדרות חשבוניות נוספות. אפשר לבחור למשל $N'=2N+1$. נסמן ב-$T(A)$ את כמות הסדרות באורך 3, או לחליפין את כמות הפתרונות מתוך $A$ למשוואה $x + y = 2z$. זה כולל את הפתרונות הטריויאליים, כלומר צריך להפריד בין $T(A) = |A|$ לבין $T(A) \ge |A|+1$.
כדי לעשות זאת משתמשים באנליזת פורייה: עבור פונקציה $f \colon \{1 \ldots N \} \to \mathbb{C}$ מגדירים
$$ \hat{f}(k) = \sum_{n=0}^{N'-1} e^{-2 i \pi k n / N'} f(n) $$
ומקבלים
$$
\begin{align*}
T(A) & = \sum_{m,n \in A} 1_{2 \cdot A}(m + n) \\
& = \sum_{m,n=0}^{N'-1} \, 1_A(m) 1_A(n) \, 1_{2\cdot A}(m+n) \\
& = \langle 1_A * 1_A , 1_{2 \cdot A} \rangle \\
& = \frac{1}{N'} \big\langle (\hat{1_A})^2, \hat{1_{2 \cdot A}} \big\rangle
\end{align*}
$$
את הפונקציות האלה אפשר לחשב באופן כמעט מפורש, למשל הרכיב שמגיע מהתדר 0 במכפלה הפנימית הזו הוא $\frac{|A|^3}{N'}$.
ניתוח מדוקדק מראה שאו ש-$T(A)$ גדול, או שיש ל-$1_A$ כמה תדרים חזקים בהרבה מהממוצע. במקרה השני, זה אומר שיש הרבה מאיברי $A$ שהם בקפיצות כמעט קבועות זה מזה. וליתר דיוק אפשר למצוא תת-קבוצה $B \subset \{1,\ldots,N\}$ שהיא סדרה חשבונית ושאיברי $A$ צפופים יותר בתוכה בפקטור כלשהו מאשר $A$ כולה בתוך $\{1,\ldots,N\}$. אז מצטמצמים לסדרה החשבונית $B$ וממשיכים באינדוקציה.
אחרי כמה צעדים מקבלים ש-$T(A)$ גדול יחסית ל-$B$ המצומצם, והטריק הוא לסדר את הקבועים ואת התהליך המדויק שקורה בצעד האינדוקציה, בהתאם לגודל של $A$ ובהתאם ל-$N$, ככה שהחסם התחתון ל-$T(A)$ יצא מספיק גדול אם $A$ המקורית גדולה מ-$c_1 N / (\log N)^{1+c_2}$. וזה החידוש שיש בהוכחה הזו.