משפט ארבעת הריבועים של לגראנז'

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

משוואת פל

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

מספרי ברנולי – ההוכחות

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

משפט המטריצה-עץ של קירכהוף

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

תורת המספרים האלגברית על קצה המזלג, חלק ג' – שובו של הפירוק היחיד

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

פונקציות יוצרות – והפעם ברצינות

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

שדות סופיים – מי, מה, כמה ולמה

בפוסט הקודם הסברתי מהו שדה והראיתי דוגמאות לשדות סופיים פשוטים: השדות $latex \mathbb{Z}_{p}$ לכל ראשוני $latex p$ של השלמים מ-0 עד $latex p-1$ עם חיבור וכפל מודולו $latex p$ (הסברתי מדוע זה חייב להיות ראשוני). בפוסט הזה אני רוצה לשכנע … להמשיך לקרוא

בעיית המזכירה, ואיך זה קשור למספרים הרמוניים

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

משפט רייס – הגרסה המלאה

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

IP=PSPACE – ההוכחה (חלק א')

בשעה טובה גמרנו להציג את השחקנים בהוכחה של IP=PSPACE ובפוסט הזה ניתן להם להשתולל. ההוכחה מכילה מספר פרטים טכניים ונראית די מפחידה במבט ראשון, אבל הרעיונות שלה אינם כה מסובכים ואני חושב שכל קורא עם ידע בסיסי במתמטיקה יהיה מסוגל … להמשיך לקרוא

משפט ברינגטון – ההוכחה

בפוסטים הקודמים הסברתי מה אומר משפט ברינגטון, וכעת אפשר להגיע לחלק היפה ביותר בכל העניין – ההוכחה שלו. האתגר הוא להראות שכל פונקציה שנמצאת ב-$latex \mbox{NC}^{1}$, כלומר ניתנת לחישוב על ידי מעגל בוליאני מגודל פולינומי ועומק לוגריתמי, ניתנת לחישוב על … להמשיך לקרוא

היה זה תענוג לגזור

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