חדו"א-צ'יט #1

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

אבי החדו

אבי החדו"א?

הבעיה: חשבו את הגבול \lim_{x\to 0, y\to 0} \frac{x^a y^b}{x^c + y^d} או הראו שאינו קיים, כאשר a,b,c,d הם פרמטרים – מספרים שלמים חיוביים כלשהם, לרוב.
דוגמא: הראו שהגבול הבא שווה 0:

\lim_{x\to 0, y\to 0} \frac{x^3 y^5}{x^4 + y^8}

נתחיל בלפתור את הדוגמא, באמצעות אי-השיוויון הטריוויאלי הבא:

אי-שיוויון טריוויאלי, גרסה חלקית: |xy| \le x^2 + y^2, לכל x,y ממשיים.
הסבר לאי-שיוויון: אם |x| \ge |y|, מתקיים |xy| \le |x|^2 \le x^2+y^2. המקרה השני מוכח באופן דומה. \blacksquare
פיתרון הדוגמא באמצעותו: נשתמש בכלל הסנדביץ' ובאי-שיוויון הנ"ל מופעל על x^3,y^5:

0 \le |\frac{x^3 y^5}{x^4+y^8}| \le \frac{x^6 + y^{10}}{x^4+y^8} \le \frac{x^6}{x^4} + \frac{y^{10}}{y^{8}} = x^2+y^2 \to 0

מה שנותן \lim_{x\to 0, y\to 0} |\frac{x^3 y^5}{x^4 + y^8}| = 0 ולכן \lim_{x\to 0, y\to 0} \frac{x^3 y^5}{x^4 + y^8} = 0.

בשרשרת המעברים הנ"ל השתמשנו במעבר הכללי \frac{a+b}{c+d} \le \frac{a}{c}+\frac{b}{d}, שנכון עבור a,b,c,d חיוביים, ומוסבר ע"י המעבר הבא:

להמשיך לקרוא

מודעות פרסומת
פורסם בקטגוריה כללי | עם התגים , | כתיבת תגובה

מעגלים ארוכים בתהליך ה-Interchange

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

בגלל שהמאמר מניח ידע מוקדם והסמינר לא, נאלצתי "להוריד תכולות", ואני מביא כאן את כל הידע המוקדם הנדרש על חשבון חלק מהתוצאות במאמר (היו לי פחות משעתיים להעביר הכל). אני חושב שפוסט זה הוא כמעט self-contained.
יש גם מסמך שחילקתי בכיתה, אך הפוסט אינפורמטיבי בהרבה.

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

1. מבוא

תהליך ה-Interchange על גרף לא-מכוון ממושקל (עם משקולות a_{i,j} = a_{j,i} \ge 0) שיסומן G=(V,E), הוא תהליך מקרי הפועל באופן הבא: בזמן t=0 מונחת גולה שונה בכל קודקוד בגרף. על כל צלע (i,j) יש שעון שמצלצל בתוחלת כל a_{i,j}^{-1} שניות, כאשר התפלגות הזמן עד הצלצול היא אקספוננציאלית. השעונים בלתי-תלויים ולמעשה מתקיימים כל התנאים על מנת שזה יהיה "תהליך פואסון".
כאשר השעון על הצלע (i,j) מצלצל, הגולות ב-2 קצות הצלע מחליפות את מקומיהן. תהליך ה-Interchange בזמן t הוא משתנה מקרי IP(t) עם ערכים ב-S_V המתאר את הפרמוטצייה של מיקומי הגולות בזמן t, שהיא מכפלה של חילופים אקראיים. בזמן t=0 מתקיים IP(t) = \text{Id}, פרמוטציית הזהות. (IP = Interchange Process.)

מסתבר שהתהליך הזה (ווריאציות שלו) הוא דבר דיי מסתורי. שאלות בסיסיות כמו: "החל מאיזו נקודת זמן סביר למצוא מעגלים מאורך מסויים בתהליך?" נותרות ללא מענה עבור מרבית המקרים. אבל יש דברים שכן מצליחים לענות עליהם.

במאמר נותנים נוסחה מפורשת לסיכוי למעגל באורך n בזמן t בתהליך ה-Interchange על גרף עם n קודקודים. נותנים בו גם חסם עליון על המרחק בין מספר המעגלים המצופה מאורך k (שהוא \frac{1}{k}) לבין תוחלת מספר המעגלים בתהליך בזמן נתון.

להמשיך לקרוא

פורסם בקטגוריה כללי | תגובה אחת

השערת השורש הפרימיטיבי של ארטין

אמיל ארטין

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

1. מוטיבציה

נסתכל על מספר רציונליים מהצורה \frac{1}{p}, כאשר p מספר ראשוני. ידוע שהפיתוח של רציונליים בבסיס 10 הוא מחזורי, בואו ניתן דוגמאות עבור המספרים שמעניינים אותנו:

\frac{1}{3} = 0.33...=0.\overline{3}: \text{ period of length 1}
\frac{1}{7} = 0.142857142857... = 0.\overline{142857}: \text{ period of length 6}
\frac{1}{11} = 0.9090... = 0.\overline{90}: \text{ period of length 2}
\frac{1}{13} = 0.076923076923...=0.\overline{076923}: \text{ period of length 6}

אפשר לשים לב שאורך המחזור של \frac{1}{p} תמיד מחלק את p-1. זה לא במקרה. כמו שגאוס שם לב, אורך המחזור הוא בדיוק הסדר של 10 בחבורה הכפלית (\mathbb{Z}/p\mathbb{Z})^{\times}, שמחלק את p-1 לפי משפט לגראנז'/פרמה. הנה הוכחה קצרצרה של הבחנה זו (תחת ההנחה (p,10)=1):

\frac{1}{p} = \frac{a}{10^{\text{ord}_{p}(10)}-1} = \frac{a}{10^{\text{ord}_{p}(10)}} \sum_{k\ge 0 } 10^{-k \text{ord}_{p}(10)}

כאשר a:= \frac{10^{\text{ord}_{p}(10)}-1}{p} \in \mathbb{N}.

אפשר לשאול: האם יש אינסוף ראשוניים p עבורם המחזור מקסימלי (קרי, שווה p-1)?
אפשר למעשה להחליף את 10 בכל בסיס אחר, לדוגמא בסיס 2, ולשאול את אותה השאלה, ששקולה לשאלה הפשוטה למראה הבאה: האם 2 שורש פרימיטיבי עבור אינסוף ראשוניים?

תזכורת: לכל ראשוני p, החבורה הכפלית G=(\mathbb{Z}/p\mathbb{Z})^{\times} היא חבורה ציקלית מסדר p-1. איבר a \in G נקרא יוצר אמ"מ G = \langle a \rangle, ובמקרה של החבורה הספציפית שלנו הוא מכונה גם "שורש פרימיטיבי".
הערה: אם נחליף את \frac{1}{p} ב-\frac{1}{n}, אורך המחזור מחלק את \phi(n) (לפי משפט לגראנז'/אוילר), ובפרט קטן ממש מ-n-1 כאשר n אינו ראשוני.

2. השערות

אפשר לנסח את השערת השורש הפרימיטיבי בשתי דרכים:

1. "איכותית": לכל a\in \mathbb{Z} \setminus \{-1, 0, 1\} שאינו ריבוע, יש אינסוף ראשוניים p כך ש-a שורש פרימיטיבי של (\mathbb{Z}/p\mathbb{Z})^{\times}.
(למה אסור ריבועים? כי אם p>2 אז סדר החבורה (\mathbb{Z}/p\mathbb{Z})^{\times} הוא זוגי (2 \mid p-1), ולכן הסדר של ריבוע הוא לכל היותר \frac{p-1}{2}.)
מה ידוע? ובכן, הרבה אך לא מספיק:

  • ב-84' הוכיחו Gupta ו-Murty שהשערה זו נכונה עבור אינסוף a-ים.
  • ב-86' הוכיח Heath-Brown שהשערה זו נכונה לכל ה-a-ים הראשוניים, מלבד לכל היותר 2 ראשוניים. מכאן מקבלים, לדוגמא, שהתוצאה נכונה לפחות לאחד מבין המספרים \{2,3,5\}.

2. "כמותית": עוד ב-27' ארטין כימת את ההשערה האיכותית. אם נסמן P_a(x) := \{p \le x: a\text{ is a primitive root of } (\mathbb{Z}/p\mathbb{Z})^{\times}\}, הוא שיער כי P_a(x) \sim C_a \pi(x)\sim C_a \frac{x}{\ln x}, כאשר C_a קבוע סופי וחיובי ו-\pi(x) כמות הראשוניים עד x.
אפשר להגיד יותר על הקבוע הזה: אם a אינו חזקה, והחלק נטול-הריבועים של a אינו 1 מודולו 4, אז C_a אינו תלוי ב-a! הוא יוצא קבוע ארטין, \prod_{p} (1-\frac{1}{p(p-1)}), אותו נסביר בהמשך.

ב-67' הוכיח Hooley את ההשערה הכמותית תחת הנחת השערת רימן המוכללת. המטרה שלנו בפוסט זה היא להוכיח את המשפט שלו. להמשיך לקרוא

פורסם בקטגוריה תורת המספרים | כתיבת תגובה