פונקציה אריתמטית
פעולות נוספות
בתורת המספרים, פונקציה המקבלת מספר טבעי <math>n</math> ומחזירה ערך התלוי בתכונות אריתמטיות של <math>n</math>, נקראת פונקציה אריתמטית. חקר של פונקציות כאלה, ובעיקר הערך הממוצע שלהן, הוא ענף מרכזי בתורת המספרים האלמנטרית.
דוגמאות:
- הפונקציה <math>d:\N\to\N</math> מוגדרת כך ש- <math>d(n)</math> הוא מספר המחלקים השונים של <math>n</math>. למשל <math>d(1)=1, d(2)=2, d(4)=3, d(6)=4</math>. מספר <math>n</math> הוא מספר ראשוני אם ורק אם <math>d(n)=2</math>.
- פונקציית מביוס <math>\mu</math> מוגדרת לפי מספר המחלקים הראשוניים: <math>\mu(1)=1</math>, <math>\mu(n)=0</math> אם יש ל-<math>n</math> גורמים ריבועיים, ו-<math>\mu(n)=(-1)^r</math> אם <math>n</math> הוא מכפלת <math>r</math> ראשוניים שונים.
- פונקציית אוילר <math>\phi</math> (פי) מוגדרת לפי מספר המספרים הזרים למספר נתון וקטנים ממנו: <math>\phi(n)</math> שווה למספר המספרים הקטנים מ-<math>n</math> וזרים לו. כך למשל <math>\phi(12)=\bigl|\{1,5,7,11\}\bigr|=4</math>.
- הפונקציה <math>\sigma</math> מוגדרת על ידי סיכום המחלקים (החיוביים) של מספר. למשל <math>\sigma(12)=1+2+3+4+6+12=28</math>. מספר משוכלל הוא כזה המקיים <math>\sigma(n)=2n</math>.
- באופן כללי יותר, הפונקציה <math>\sigma_k</math> (פונקציית מחלקים) מוגדרת על ידי סיכום חזקות-<math>k</math> של המחלקים. למשל <math>\sigma_2(12)=1^2+2^2+3^2+4^2+6^2+12^2=210</math>. לפי הגדרה זו <math>\sigma_0=d,\sigma_1=\sigma</math>.
- הפונקציה <math>r</math> המחזירה לכל <math>n</math> את מספר הפתרונות השלמים למשוואה <math>x^2+y^2=n</math>. למשל <math>r(1)=4,r(3)=0,r(5)=8</math>. אם נסמן <math>d_1(n),d_3(n)</math> את סכומם של מחלקי <math>n</math> הנותנים בהתאמה שארית 1 או 3 בחלוקה ל-4, אזי מתקיים <math>r(n)=4(d_1(n)-d_3(n))</math> (ראו סכום של שני ריבועים), ומכאן שתמיד <math>d_1(n)\ge d_3(n)</math>.
- פונקציית ליוביל <math>\lambda(n)=(-1)^{d(n)}</math>, מחזירה <math>1</math> או <math>-1</math> לפי זוגיות מספר המחלקים הראשוניים של <math>n</math>.
גידול ממוצע עריכה
אם <math>f</math> היא פונקציה אריתמטית, הערך <math>f(n)</math> מחזיק משהו מן האריתמטיקה של המספר <math>n</math>. אם רוצים להבין תכונות אריתמטיות באופן כללי, טבעי לשאול מהו הערך הממוצע של <math>f</math>, כלומר, כיצד מתנהג הממוצע <math>\frac{f(1)+f(2)+\cdot+f(n)}{n}=\frac{1}{n} \sum_{k\,=\,1}^n f(k)</math>. לעיתים קרובות קל לקבל את סדר הגודל של הממוצע, אבל הערכה טובה של גורם השגיאה היא בדרך כלל בעיה אריתמטית ואנליטית קשה.
דוגמאות:
- הגודל הממוצע של הפונקציה <math>r</math> לעיל הוא <math>\pi</math> (פאי), כלומר: בממוצע ניתן להציג מספר כסכום של שני ריבועים ב-<math>\pi</math> דרכים.
- הערך הממוצע של מספר המחלקים <math>d(n)</math> הוא <math>\ln(n)+(2\gamma-1)+O(n^{-0.5})</math>. כאשר <math>\gamma</math> קבוע אוילר-מסקרוני. את גורם השגיאה אפשר לשפר ל-<math>O(n^{-285/416+\epsilon})</math> (Huxley, 2003).
- הערך הממוצע של <math>\sigma</math> הוא <math>\frac{\pi^2}{12}n+O(\log(n))</math>.
- הערך הממוצע של פונקציית אוילר <math>\phi</math> הוא <math>\frac{6n}{\pi^2}</math>.
- פונקציית מביוס <math>\mu</math> מקבלת את הערכים <math>\pm1</math> בצפיפות <math>\frac{6}{\pi^2}</math>, ו-0 בשאר הזמן. למרבה ההפתעה, התוצאה (הצפויה לכאורה) שהערך הממוצע שואף לאפס, שקולה למשפט המספרים הראשוניים, ואילו הטענה שהערך הממוצע קטן מ-<math>O(x^{-0.5})</math> שקולה להשערת רימן.
כפליות עריכה
פונקציה אריתמטית המקיימת <math>f(n_1n_2)=f(n_1)f(n_2)</math> לכל זוג מספרים זרים <math>n_1,n_2</math> נקראת פונקציה כפלית. כל הפונקציות שפגשנו קודם לכן (למעט <math>r</math>) הן כפליות. בגלל המשפט היסודי של האריתמטיקה, פונקציה כפלית נקבעת על ידי ערכיה במספרים <math>p^t</math> כאשר <math>p</math> ראשוני, ועובדה זו מקלה מאוד על החישוב. למשל, סכום המחלקים של <math>600</math> שווה ל-<math>\sigma(600)=\sigma(2^3)\sigma(3)\sigma(5^2)=15\cdot4\cdot31=1860</math>, בלי שנצטרך לסכם את כל <math>d(600)=d(2^3)d(3)d(5^2)=4\cdot 2\cdot 3=24</math> המחלקים.
פונקציה המקיימת את השוויון הנ"ל לכל <math>n_1,n_2</math> (גם אם אינם זרים) נקראת כפלית לחלוטין (completely multiplicative) או כפלית במובן החזק (strongly multiplicative).
קונבולוציית דיריכלה עריכה
אפשר להגדיר פעולה בינארית הנקראת קונבולוציית דיריכלה בין פונקציות אריתמטיות, באופן הבא:
- <math>(f*g)(n)=\sum_{d|n}f(d)g\bigl(\tfrac{n}{d}\bigr)</math>
ביחס לפעולה זו אוסף הפונקציות האריתמטיות הופך למונואיד, שהפונקציות ההפיכות בו הן כל אלו המקיימות <math>f(1)\ne0</math> (וכך הפונקציות האריתמטיות שלא מקבלות <math>0</math> ב-<math>1</math> הן חבורה אבלית ביחס לקונבולוציה). תכונות מעניינות רבות של פונקציות אריתמטיות אפשר לבטא באמצעות שוויונות בחבורה הזו.
נעיר שאם <math>f,g</math> שתיהן כפליות, אז גם <math>f*g</math> כפלית וגם <math>f^{-1}</math> כפלית (אבל אין הדבר כן לכפליות חזקה).
נגדיר עוד כמה פונקציות שימושיות:
- <math>\mathbf{1}(n)=1</math>, הפונקציה המחזירה <math>1</math> לכל <math>n</math>.
- <math>\text{id}(n)=n</math> – פונקציית הזהות.
- פונקציית היחידה השווה ל-<math>1</math> אם <math>n=1</math>, ול-<math>0</math> אחרת. זהו איבר הזהות בחבורת הפונקציות.
את התכונה החשובה ביותר של פונקציית מביוס אפשר לבטא כך: אם <math>F=\mathbf{1}*f</math>, אז <math>f=\mu*F</math>. במילים אחרות, <math>\mu=\mathbf{1}^{-1}</math>, כלומר <math>\mu</math> היא ההפכית של הפונקציה <math>\mathbf{1}</math> בחבורה. דוגמאות נוספות:
- <math>\mathbf{1}*\mathbf{1}=d</math>
- <math>\text{id}=\phi*\mathbf{1}</math> ולכן גם <math>\phi=\text{id}*\mu</math>. המשוואה הראשונה היא ניסוח מקוצר לזהות <math>\sum_{d|n}\phi(d)=n</math>.
- <math>\sigma=\text{id}*1</math>
קישורים חיצוניים עריכה
- פונקציה אריתמטית, באתר אנציקלופדיה למתמטיקה (באנגלית)