בתשובה להאייל הצעיר, 29/09/05 21:37
 |
|
 |
||
|
||||
 |
בוא ואנסה להסיח את דעתך עם סיפור שאולי מוסר-השכל בצידו: דווקא היעדרותה הזמנית של האמס"ש הסבה לי קורת-רוח שכנראה היתה נמנעת ממני אחרת. עלה בדעתי להביט בסדרה 1, 2, 4, 5, 10, 11, 13, 14, ... שאינה כוללת אף סדרה חשבונית באורך שלוש, ובה מוסיפים בכל שלב את המספר הטבעי הקטן ביותר שאינו מקלקל תכונה זו. עם קצת מזל וקצת סבלנות אפשר למצוא לסדרה הזו פרשנות אחרת לגמרי, נחמדה מאוד. האמס"ש, כמובן, מאכילה אותך בכפית, וזה הרבה פחות כיף. זה קצת קשור לדיון (אליו הפנית בתגובה 327219) על התקדמות המתמטיקה. זה נחמד שדברים נהיים יותר קלים, אבל כשהם נעשים קלים מדי אנחנו עלולים לאבד את המוטיווציה לחקור אותם "באצבעות", לפתח אינטואיציה לגביהם ואולי לגלות דברים שהיום, בדור הכפית, לא נגלה. |
 |
 |
 |
|
|
|
||
|
||||
|
''אינציקלופדיה המקוונת של סדרות מספרים שלמים'' | |
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
תגובה 333802. | |
|
|
|
|
|
||
|
||||
|
כן, ראיתי. פשוט לא הבנתי איך הראשי תיבות האלא מסתדרים (למה אכלת את המ' של המספרים?). (מצד שני, אולי כדאי שתתעלם מהערות מטופשות שאני מעיר?) |
|
|
|
|
|
|
||
|
||||
|
ברור שאילו שאריות ריבועיות מודולו 78 פלוס 1. | |
|
|
|
|
|
||
|
||||
|
יותר מדי יין שתית שם, באיטליה. | |
|
|
|
|
|
||
|
||||
|
מסתבר שאפילו כלום זה יותר מדי. אתה רוצה לומר לי שכל אלו אינן שאריות ריבועיות מודולו 78 פלוס 1? דרך אגב, שים לב להבדל התמוה בין התיאור של הסדרה (הטבעית יותר): 0, 1, 3, 4, 9, 10, 12, 13,.. לתיאור של: 1, 2, 4, 5, 10, 11, 13, 14,.. באמס"ש. |
|
|
|
|
|
|
||
|
||||
|
האם זו הסדרה הצפופה ביותר האפשרית שאינה מכילה סדרה חשבונית באורך 3? 1 עלולה להיות טיפשית, לא חשבתי. |
|
|
|
|
|
|
||
|
||||
|
הרבה יותר מדי יין שתית שם, באיטליה. (קרא שוב את התגובה שלי. זו ההגדרה המקורית. החידה היא למצוא לזה תיאור אחר, המאפשר יותר בקלות למצוא את האיבר המיליארד בסדרה). |
|
|
|
|
|
|
||
|
||||
|
זה לא אותו דבר. ההגדרה היא שתמיד מוסיפים את האיבר הקטן ביותר שלא מקלקל את התכונה, אבל אולי בקצת תכנון מוקדם אפשר לקלקל את האיבר הקרוב, ולשפר את הצפיפות? | |
|
|
|
|
|
||
|
||||
|
בוודאי, אלא שלא כך פירשתי את השאלה של אורי (אולי בטעות). השאלה שלי היא על דרך אחרת לגמרי לתאר את הסדרה הספציפית הזו, החמדנית. | |
|
|
|
|
|
||
|
||||
|
אתם המתמטיקאים, אין לכם שום חוש הומור. זו היתה סתם בדיחה על קלות וריבוי הפתרונות באמס"ש. מה עם השאלה שלי (עדיין לא חשבתי עליה)? |
|
|
|
|
|
|
||
|
||||
|
היה לי פעם חוש הומור, אבל הוא טבע בין התגובות בדיון הזה. אתה שואל מה הקבוצה הצפופה ביותר שאינה מכילה סדרות חשבוניות? אני לא חושב שזה ידוע במדוייק. יש משפטים מפורסמים המראים שקבוצות בעלות צפיפות חיובית חייבות להכיל סדרות חשבוניות; למשל, יש קבוע כלשהו 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 שהיא אנליטית כמו זו של גאוורס, וגם לא קלה. (כמו שאתה רואה, זו תוצאה חשובה שלא מעט אנשים הקדישו לה מחשבה. הסיכוי שיש נימוק קצר הוא נמוך מאוד). |
|
|
|
|
|
|
||
|
||||
|
אז מה בסוף הקשר הפשוט? את התאור באתר של a(n)-1 in ternary = n-1 in binary לא הבנתי. | |
|
|
|
|
|
||
|
||||
|
רשום, לפי הסדר, את כל המספרים הטבעיים שהפיתוח שלהם בבסיס 3 לא מכיל את הספרה 2. | |
|
|
|
|
|
||
|
||||
|
ולמה לי לעשות את זה? (סתאאאם. למה לא תתרום את חלקך לאספקט ה"גדל"י של הויכוח על רוג'ר פנרוז? רק בגלל שאתה עסוק מעל הראש?) |
|
|
|
|
|
|
||
|
||||
|
(גם בגלל זה, וגם בגלל שקצת עייפתי מהויכוח הזה אחרי המרתון עם ד.ק. והמאמר.) | |
|
|
|
|
|
||
|
||||
|
תודה רבה. עכשיו כשהבנתי איך לחשב את האיבר הnי, איך מוכיחים שהוא באמת לא יוצר סדרה חשבונית עם אף איבר אחר במערך באופן כללי? | |
|
|
|
|
|
||
|
||||
|
נקרא למספרים האלה (אלו שבבסיס 3 אין להם אף 2) "נמוכים". אם יש סדרה חשבונית של נמוכים, הרי לפנינו מספרים a ו-d כך ש-a נמוך וכמוהו גם a+d וגם a+2d. זו פשוט הצורה הכללית של כל סדרה חשבונית בת שלושה איברים. המספר d איננו 0, ולכן פיתוחו לבסיס 3 מכיל את הספרה 1 באיזה מקום. נביט במיקומה של הספרה 1 הימנית ביותר. למספר a מוכרח להיות 0 באותו המקום (אחרת בסכום a+d היינו מקבלים 2 במקום זה). למספר 2d יש הספרה 2 במקום הנדון, וכשנחבר ל-a את 2d נקבל, שוב, 2 במקום זה. מכאן שאם a וגם a+d נמוכים, a+2d לא יכול להיות נמוך. (הערה: הבטנו במספרה הימנית ביותר כדי לוודא שלא יהיו שום "שאריות" בתהליך החיבור עד שלב זה). הטענה המקורית שטענתי היא יותר חזקה: אם מתחילים מ-0 ומוסיפים בכל שלב את המספר הקטן ביותר האפשרי שאינו יוצר סדרה חשבונית, מתקבלת בדיוק סדרת המספרים הנמוכים. (אני התחלתי מ-1, ולכן קיבלתי את אותה הסדרה מוזזת ב-1). את זה אפשר להוכית באינדוקציה, ואתה מוזמן לשאול אותי אם אתה נתקע (ואם זה מעניין אותך). |
|
|
|
|
|
|
||
|
||||
|
מזכיר לי את ההוכחה שהעוצמה של קבוצת קנטור היא א. | |
|
|
|
|
|
||
|
||||
|
רגע, 5 בבסיס 3 זה לא 12? איך זה מתיישב עם התאור? (עם הנוסחה שבאתר בסוף הסתדרתי, ברגע שהבנתי שטרנרי זה בסיס 3 ולא אופרטור שפועל על שלושה אברים, אבל אז ההוכחה שלך כבר לא תקפה) |
|
|
|
|
|
|
||
|
||||
|
ועוד אחד. (גם 2 מכיל את הספרה 2 בבסיס 3) |
|
|
|
|
|
|
||
|
||||
|
5=4+1 נתפשר על פחות אחד? |
|
|
|
|
|
|
||
|
||||
|
התלבטתי אם לכתוב ועוד אחד או פחות אחד. הכל תלוי מאיפה אתה מתחיל. | |
|
|
|
|
|
||
|
||||
|
בעצם ההוכחה של אלון היא שאין סדרות חשבוניות ב An-1, ומכאן המעבר לAn טריוויאלי | |
|
|
|
|
|
||
|
||||
|
http://www.research.att.com/~njas/sequences/ , אני מניחה. | |
|
|
|
|
|
||
|
||||
|
''האנציקלופדיה לסדרות של מספרים שלמים''. אתר חביב - כתוב התחלה של סדרת מספרים, והוא יציג לך את כל הסדרות (המעניינות - כלומר, בתקווה, שיש לך מאמרים רציניים שמדברים עליהן) שזו ההתחלה שלהן. כמובן שגם אפשר לחפש לפי שם וכאלה. יכול להיות מאוד שימושי לחוקרים שנתקלים בסדרת מספרים כלשהי ורוצים לדעת אילו אספקטים שלה כבר מוכרים. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |