פונקציית מביוס

פונקציית מביוס, המסומנת μ(n), היא פונקציה אריתמטית שהוצגה על ידי אוגוסט פרדיננד מביוס. היא מוגדרת על המספרים הטבעיים ותלויה רק בפירוק של n לגורמים ראשוניים.

אם ל-n יש גורם ריבועי (מספר שמכיל את אותו ראשוני בחזקה 2), אז μ(n)=0. אחרת נניח ש-n הוא מכפלה של r ראשוניים שונים; אז μ(n)=(-1)^r. בפרט μ(1)=1. כלומר, μ מחזירה 1 אם מספר הראשוניים הוא זוגי, ו-1- אם הוא אי זוגי.

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

נסמן f(m,n) כמספר המספרים בין 1 ל-m שמקיימים gcd(k,n)=1, כלומר שזרים ל-n (אין להם מחלק משותף גדול מ-1). בעזרת עקרון ההכלה וההפרדה מסירים את המספרים המחולקים על ידי כל ראשוני שמחלק את n. התוצאה ניתנת בצורה מקוצרת על ידי סכום על כל המחלקים d של n: f(m,n)=∑_{d|n} μ(d) ⌊m/d⌋, כאשר ⌊x⌋ היא פונקציית הרצפה, כלומר החלק השלם של x. כאשר לוקחים m=n הנוסחה מתמצקת לנוסחה הידועה של פונקציית אוילר לפעולת חישוב מספר המספרים הזרים עד n.

פונקציית מביוס מוגדרת גם על קבוצות מסודרות (קבוצות עם יחס סדר חלש). בהכללה זו μ(x,y) היא הערך במטריצה ההפוכה של המטריצה [X], שבה [X]_{a,b}=1 אם a≤b ו-0 אחרת. עבור הטבעיים עם יחס החילוק מתקבלת אותה פונקציית מביוס הרגילה.

פונקציית מביוס נקראת μ(n). זוהי חוק שמקבל מספר טבעי ומחזיר מספר אחר.

אם ל-n יש גורם ריבועי, כלומר מספר שהוא כפולה של מספר בעצמו, אז μ(n)=0. אם אין כזה גורם, סופרים כמה ראשוניים שונים מחלקים את n. אם המספר הזה זוגי μ(n)=1. אם הוא אי־זוגי μ(n)=-1. למשל μ(1)=1 ו-μ של ראשוני הוא -1. (ראשוני הוא מספר שמתחלק רק ב-1 ובעצמו.)

נרצה לדעת כמה מספרים בין 1 ל-m הם זרים ל-n. זרים זה אומר שאין להם מחלק משותף חוץ מ-1. משתמשים בעקרון פשוט: מוסיפים את כל המספרים ואז מורידים כפילויות. את הסכימה מקצרים בעזרת μ: אם לוקחים סכום של μ(d) על כל המחלקים d של n ומבצעים חיתוך כלפי מטה של m על כל d, מקבלים את התוצאה. כשמניחים m=n, זה קשור לנוסחה של פונקציית אוילר לחישוב מספר הזרים ל-n.

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