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

אני רוצה לדבר על אחת מהתוצאות הנחמדות ביותר (לטעמי) בתורת המספרים האלמנטרית – משפט ארבעת הריבועים של לגראנז'. בפשטות, המשפט אומר שאפשר להציג כל מספר טבעי בתור סכום של ארבעה ריבועים של מספרים טבעיים (כש-0 נחשב למספר טבעי). הנה דוגמאות עבור המספרים הטבעיים מ-1 עד 7: $latex 1=1^{2}+0^{2}+0^{2}+0^{2}$ $latex 2=1^{2}+1^{2}+0^{2}+0^{2}$ $latex 3=1^{2}+1^{2}+1^{2}+0^{2}$ $latex 4=2^{2}+0^{2}+0^{2}+0^{2}$ $latex …

משוואת פל

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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