פונקציה אריתמטית

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

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

דוגמאות:

  • הפונקציה \ d : \mathbb{N}\rightarrow \mathbb{N} מוגדרת כך ש- \ d(n) הוא מספר המחלקים השונים של n. למשל \ d(1)=1, d(2)=2, d(4)=3, d(6)=4. מספר \ n הוא מספר ראשוני אם ורק אם \ d(n)=2.
  • פונקציית מביוס \ \mu מוגדרת לפי מספר המחלקים הראשוניים: \ \mu(1)=1, \ \mu(n)=0 אם יש ל- n גורמים ריבועיים, ו- \ \mu(n)=(-1)^s אם n הוא מכפלת s ראשוניים שונים.
  • פונקציית אוילר, \ \phi (פי), מוגדרת לפי מספר המספרים הזרים למספר נתון: \ \phi(n) שווה למספרם של המספרים \ 1,...,n שאינם מתחלקים באף גורם של n פרט ל- 1. כך למשל \ \phi(12)=\left|\{1,5,7,11\}\right|=4.
  • הפונקציה \ \sigma מוגדרת על ידי סיכום המחלקים (החיוביים) של מספר. למשל, \  \sigma(12)=1+2+3+4+6+12=28. מספר משוכלל הוא כזה המקיים \ \sigma(n)=2n.
  • באופן כללי יותר, הפונקציה \ \sigma_k (פונקציית מחלקים) מוגדרת על ידי סיכום חזקות-k של המחלקים. למשל, \ \sigma_2(12)=1^2+2^2+3^2+4^2+6^2+12^2=210. לפי הגדרה זו, \ \sigma_1=\sigma ו- \ \sigma_0=d.
  • הפונקציה \ r המחזירה לכל n את מספר הפתרונות השלמים למשוואה \ x^2+y^2 = n. למשל \ r(3)=0, r(5)=8, r(1)=4. אם נסמן ב- \ d_1(n),d_3(n) את סכומם של מחלקי n הנותנים שארית 1 או 3 בחלוקה ל- 4, בהתאמה, אז מתקיים \ r(n)=4(d_1(n)-d_3(n)) (ראו סכום של שני ריבועים), ומכאן שתמיד \ d_1(n)\geq d_3(n).

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

אם \ f היא פונקציה אריתמטית, הערך \ f(n) 'מחזיק' משהו מן האריתמטיקה של המספר n. אם רוצים להבין תכונות אריתמטיות באופן כללי, טבעי לשאול מהו הערך הממוצע של f, כלומר, כיצד מתנהג הממוצע \ \frac{f(1)+f(2)+...+f(n)}{n}. לעתים קרובות קל לקבל את סדר הגודל של הממוצע, אבל הערכת גורם השגיאה היא בדרך כלל בעיה אריתמטית קשה מאד.

דוגמאות:

  • הגודל הממוצע של הפונקציה \ r לעיל הוא \ \pi (פאי), כלומר: בממוצע ניתן להציג מספר כסכום של שני ריבועים ב- \ \pi דרכים.
  • הערך הממוצע של מספר המחלקים \ d(n) הוא \ \log(n)+(2\gamma-1) + O(n^{-1/2}). הלוגריתם הוא כמובן בבסיס הטבעי, ו- \ \gamma הוא הקבוע של אוילר.
  • הערך הממוצע של \ \sigma הוא \frac{\pi^2}{12}n+O(\log(n)).
  • הערך הממוצע של פונקציית אוילר הוא \ \frac{6n}{\pi^2}.
  • פונקציית מביוס  \mu מקבלת את הערכים \ \pm 1 בצפיפות \frac{6}{\pi^2}, ו- 0 בשאר הזמן. למרבה ההפתעה, התוצאה (הצפויה לכאורה) שהערך הממוצע שואף לאפס, שקולה למשפט המספרים הראשוניים, ואילו הטענה שהערך הממוצע קטן מ- \ O(x^{-1/2}) שקולה להשערת רימן.

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

פונקציה אריתמטית המקיימת \ f(nm)=f(n)f(m) לכל זוג מספרים זרים n,m נקראת פונקציה כפלית. כל הפונקציות שפגשנו קודם לכן (למעט r) הן כפליות. בגלל המשפט היסודי של האריתמטיקה, פונקציה כפלית נקבעת על ידי ערכיה במספרים \ p^t כאשר p ראשוני, ועובדה זו מקלה מאוד על החישוב. למשל, סכום המחלקים של 600 שווה ל- \ \sigma(600)=\sigma(2^3)\sigma(3)\sigma(5^2)=15\cdot 4\cdot 31=1860, בלי שנצטרך לסכם את כל \ d(600)=d(2^3)d(3)d(5^2)=4\cdot 2\cdot 3=24 המחלקים.

פונקציה המקיימת את השוויון הנ"ל לכל \ m,n (גם אם אינם זרים) נקראת כפלית במובן החזק (strongly multiplicative).

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

Postscript-viewer-shaded.png ערך מורחב – קונבולוציית דיריכלה

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

\ (f*g)(n)=\sum_{d|n}f(d)g(n/d). ביחס לפעולה זו אוסף הפונקציות האריתמטיות הופך למונואיד, שהפונקציות ההפיכות בו הן כל אלו המקיימות \ f(1)\ne 0 (וכך הפונקציות האריתמטיות שלא מקבלות 0 ב-1 הן חבורה אבלית ביחס לקונבולוציה). תכונות מעניינות רבות של פונקציות אריתמטיות אפשר לבטא באמצעות שוויונות בחבורה הזו.

נעיר שאם f,g שתיהן כפליות, אז גם f*g כפלית וגם \ f^{-1} כפלית (אבל אין הדבר כן לכפליות חזקה).

נגדיר עוד כמה פונקציות שימושיות:

  • \ One(n)=1, הפונקציה מחזירה 1 לכל ערך של n.
  • \ I(n)=n - פונקציית הזהות.
  • פונקציית היחידה השווה ל- 1 אם n=1, ול- 0 אחרת. זהו איבר הזהות בחבורת הפונקציות.

את התכונה החשובה ביותר של פונקציית מביוס אפשר לבטא כך: אם \ F = One*f, אז f = \mu * F. במלים אחרות, \ \mu = One^{-1}, כלומר \ \mu היא ההפכית של הפונקציה One בחבורה. דוגמאות נוספות:

  • \ One*One=d.
  • \ I = \phi * One ולכן גם \ \phi = I * \mu. המשוואה הראשונה היא ניסוח מקוצר לזהות \ \sum_{d|n}\phi(d)=n.
  • \ \sigma = I*One.