משפט פרובניוס (תורת המספרים האלגברית)

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

משפט פרובניוס הוא משפט בתורת המספרים האלגברית, העוסק בתכונות הפירוק של פולינומים בעלי מקדמים שלמים, כאשר מתבוננים בהם מודולו מספרים ראשוניים שונים. את המשפט הוכיח פרדיננד פרובניוס ב-1880, והוא התפרסם ב-1896, לאחר שריכרד דדקינד ניסח (ב-1894) את העקרונות של תורת המספרים האידיאליים. באותו זמן שיער פרובניוס את משפט הצפיפות של צ'בוטרב, המכליל את התוצאה שלו; צ'בוטרב הראה שההשערה נכונה ב-1922.

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

מבוא[עריכת קוד מקור | עריכה]

תבנית פירוק[עריכת קוד מקור | עריכה]

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

כאשר מתבוננים במספר ראשוני יחיד, הקשר בין הפירוק של f מעל השלמים לפירוק מודולו p הוא חד סטרי: הפירוק מעל השלמים נשאר נכון גם מודולו p, ושם כל גורם שהיה אי-פריק מעל השלמים, עשוי להתפרק עוד יותר. לכן תבנית הפירוק מודולו p מהווה עידון של תבנית הפירוק המקורית.

לדוגמה, הפולינום מתפרק לגורמים מודולו 3, ולכן תבנית הפירוק שלו שם היא 2,2. מודולו 5 הפולינום מתפרק לגורמים , ותבנית הפירוק שלו היא 1,3. מהשוואת התבניות האלה לבדה אפשר להסיק שהפולינום אי-פריק מעל השלמים, והוא אכן אי-פריק מודולו 7.

חבורת גלואה ומבנה מחזורים[עריכת קוד מקור | עריכה]

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

כל תמורה אפשר לכתוב באופן יחיד כמכפלה של מחזורים זרים, ולאוסף של אורכי המחזורים קוראים מבנה המחזורים של התמורה.

משפט פרובניוס[עריכת קוד מקור | עריכה]

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

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

דוגמה. חבורת גלואה של הפולינום מעל הרציונליים היא , החבורה הדיהדרלית שסדרה 8 (שדה הפיצול הוא ). בחבורה הזו יש איבר אחד שמבנה המחזורים שלו הוא 1,1,1,1 (הזהות), שני איברים שמבנה המחזורים שלהם הוא 4, שני איברים שמבנה המחזורים שלהם 2,1,1, ושלושה שמבנה המחזורים שלהם הוא 2,2. מבנה המחזורים 3,1 אינו מופיע כלל. בהתאמה לפרופורציה 1:2:2:3 של מבני המחזורים, הפרופורציות של תבנית הפירוק המתקבלת מ-1228 הראשוניים עד 10000 הן 0.96:2.05:2.03:2.98.

קשרים לתוצאות אחרות[עריכת קוד מקור | עריכה]

ממשפט פרובניוס אפשר להוכיח את המסקנה הבאה: מספר הגורמים של f שווה לתוחלת מספר השורשים מודולו ראשוני אקראי p. תוצאה זו, שהוכיח לאופולד קרונקר ב-1880, הביאה את פרובניוס לנסח ולהוכיח את המשפט.

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

מקורות[עריכת קוד מקור | עריכה]

  • Chebotarev and his density theorem, P. Stevenhagen and H.W. Lenstra, 1995.