 |
|
 |
||
|
||||
 |
היה לי פעם חוש הומור, אבל הוא טבע בין התגובות בדיון הזה. אתה שואל מה הקבוצה הצפופה ביותר שאינה מכילה סדרות חשבוניות? אני לא חושב שזה ידוע במדוייק. יש משפטים מפורסמים המראים שקבוצות בעלות צפיפות חיובית חייבות להכיל סדרות חשבוניות; למשל, יש קבוע כלשהו c כך שאם תיקח יותר מ-cN מספרים בין 1 ל-N, לא תוכל להימלט מסדרה חשבונית באורך 3 (אותו דבר נכון גם לאורכים גדולים יותר, רק שהקבוע משתנה). אני לא יודע אם יודעים להוכיח שסדרה-הנמנעת-מס"ח-באורך-3 חייבת להיות בגודל לוגריתמי. |
 |
 |
 |
|
|
|
||
|
||||
|
אני חושב שפשוט להראות שאפשר להגיע לצפיפות n^1/3 (שורש שלישי של n). עבור סדרה סופית עולה ממש של מספרים טבעיים, נכנה את ערך האיבר המקסימלי (האחרון) שלה בשם "אורך" הסדרה. נסמן f_k האורך המינימלי של סדרה המכילה k מספרים ואינה מכילה סדרה חשבונית באורך 3. נבנה נוסחת נסיגה עבור f_k+1: נתבונן בסדרה בעלת האורך המינימלי בעלת k מספרים. כל זוג מספרים בסדרה מגדיר מיקום "אסור" שלא יכול להופיע בסדרה המכילה מספרים אלה ואינה כוללת סדרה חשבונית באורך 3, כלומר בסך הכל יש k(k-1)/2 מקומות אסורים. נתבונן ב- k(k-1)/2+1 המספרים העוקבים ל- f_k, בהכרח אחד מהם לא אסור. לכן קיימת סדרה שאינה מכילה סדרה חשבונית באורך 3 ואורכה לכל היותר f_k+k(k-1)/2+1. מכאן: f_k+1 <= f_k + k(k-1)/2+1. פתרון משוואת הנסיגה נותן f_k = O(k^3), כלומר צפיפות שורש שלישי. קל להרחיב את התוצאה לסדרה חשבונית באורך m. |
|
|
|
|
|
|
||
|
||||
|
כן, אבל לא ברור שזו הצפיפות המקסימלית שניתן להשיג. | |
|
|
|
|
|
||
|
||||
|
הסדרה של אלון נותנת לנו משהו הרבה יותר טוב: n^(log_3(2))=n^0.631 קצת יותר משורש שלישי. כנראה שגם אותך בלבלה תגובה 334670 ממנה משתמע כאילו צפיפות הסדרה המדוברת היא לוגריתמית.
|
|
|
|
|
|
|
||
|
||||
|
מהיכן החסם בנוגע לסדרה של אלון? התגובה לא בלבלה אותי אלא דווקא דרבנה אותי להוכיח את ההיפך ממה שהיא רמזה (כלומר להראות חסם תחתון סופר-לוגריתמי). עכשיו אני מנסה למצוא חסם עליון טוב. | |
|
|
|
|
|
||
|
||||
|
הצפיפות האסימפטוטית של הסדרה של אלון היא כפי שכתבתי. זה נובע מההגדרה השקולה שלה (שאותה איני כותב כדי לא להרוס לקורא פוטנציאלי). | |
|
|
|
|
|
||
|
||||
|
אני מתכוון לחסם עליון על צפיפות סדרה שאינה מכילה סדרה חשבונית באורך 3. אלא אם כן אתה יודע להוכיח שהסדרה של אלון היא הצפופה ביותר. | |
|
|
|
|
|
||
|
||||
|
שאלת: "מהיכן החסם בנוגע לסדרה של אלון?" עניתי: "הצפיפות האסימפטוטית של הסדרה של אלון היא כפי שכתבתי." "n^(log_3(2))=n^0.631" כלומר זה לא חסם אלא הצפיפות המדויקת.עכשיו אתה שואל משהו אחר, מה הסדרה הצפופה ביותר שאינה מכילה סדרה חשבונית באורך 3. את זה, כפי שניתן להבין מהדיון, אני לא יודע. למעשה, אני אתפלא אם זה ידוע. אני אחשוב על זה עוד קצת ואז אתענין אצל אילנות גבוהים ממני. |
|
|
|
|
|
|
||
|
||||
|
הכוונה שלי היתה שהסדרה של אלון מהווה חסם תחתון (על ידי בניה מפורשת) לצפיפות סדרה שאינה מכילה חשבונית באורך 3 (על כך דובר בתגובה 334670). לא משנה. אתה מצליח לראות איזשהו חסם עליון יותר טוב מ- n/2 לסדרה הצפופה ביותר? | |
|
|
|
|
|
||
|
||||
|
מסתבר שכל מספר חיובי מהווה חסם עליון: ל*כל* קבוע חיובי c יש N כך שכל קבוצה בגודל cN של מספרים בין 1 ל-N מכילה סדרה חשבונית באורך 3. מה שכתבתי קודם לא היה מספיק חזק. במלים אחרות, לסדרה הנמנעת מסדרות חשבוניות יש צפיפות 0. אפשר למצוא הרבה פרטים במאמרים של טים גאוורס, כאן: |
|
|
|
|
|
|
||
|
||||
|
זה נשמע סביר אינטואיטיבית. אנחנו שואלים כמה חזק הצפיפות שואפת ל- 0. כלומר אנחנו מבטאים את הצפיפות של סדרה שהאיבר הגדול ביותר שלה הוא n במונחי n (אולי השימוש במושג צפיפות לא מתאים, אנחנו מתבוננים ב- np כאשר p היא הצפיפות לפי הגדרתך). הראית שקיימת סדרה כזו שהאיבר הגדול ביותר שלה הוא n ומכילה n^0.62 (בערך) איברים, כלומר צפיפות של n^-0.38 - שואפת ל- 0. השאלה היא האם יש סדרה כזו שהצפיפות שלה דועכת למשל לפי 1/logn (לפי הטרמינולוגיה שלנו זו "צפיפות" n/logn). אני מניח שהבנת את זה כבר לפני פסקה וחצי אבל אני משתדל להיות כמה שיותר חד כדי לא ליפול שוב לבעית הגדרות. התכונה שציטטת אומרת שה"צפיפות" (כפי שהתייחסנו אליה עד כה, בניגוד לצפיפות סתם) אינה ליניארית, זה כבר מעניין, יש הוכחה פשוטה? |
|
|
|
|
|
|
||
|
||||
|
שוב, אינני יודע מה הצפיפות המקסימלית הניתנת להשגה. אין הוכחה פשוטה לכך שכל קבוצה בעלת צפיפות חיובית (במובן המקובל...) מכילה סדרות חשבוניות מכל אורך - יש לזה כמה הוכחות שונות. זו של Szemeredi היא קומבינטורית באופייה ומאוד קשה; ניסיתי ללמוד אותה פעם ואני לא יכול לומר שהצלחתי. יש הוכחה חשובה של פירסטנברג הנחשבת קלה יותר מבחינה קונספטואלית למי שיודע תורה ארגודית, אבל היא גם דורשת הרבה עבודה. ויש ההוכחה של גאוורס עצמו, המשתמשת בכלים של תורת-המספרים האנליטית; לי אישית היא הכי ברורה, אבל אי-אפשר לקרוא לה פשוטה. אם מסתפקים בסדרות מאורך 3, אפשר לחזור אחורה להוכחה של Roth שהיא אנליטית כמו זו של גאוורס, וגם לא קלה. (כמו שאתה רואה, זו תוצאה חשובה שלא מעט אנשים הקדישו לה מחשבה. הסיכוי שיש נימוק קצר הוא נמוך מאוד). |
|
|
|
| חזרה לעמוד הראשי |  |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |