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

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

דוגמאות:
*הפונקציה d:\N\to\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)^r אם n הוא מכפלת r ראשוניים שונים.
*פונקציית אוילר \phi (פי) מוגדרת לפי מספר המספרים הזרים למספר נתון וקטנים ממנו: \phi(n) שווה למספר המספרים הקטנים מ-n וזרים לו. כך למשל \phi(12)=\bigl|\{1,5,7,11\}\bigr|=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_0=d,\sigma_1=\sigma.
*הפונקציה r המחזירה לכל n את מספר הפתרונות השלמים למשוואה x^2+y^2=n. למשל r(1)=4,r(3)=0,r(5)=8. אם נסמן d_1(n),d_3(n) את סכומם של מחלקי n הנותנים בהתאמה שארית 1 או 3 בחלוקה ל-4, אזי מתקיים r(n)=4(d_1(n)-d_3(n)) (ראו סכום של שני ריבועים), ומכאן שתמיד d_1(n)\ge d_3(n).
*פונקציית ליוביל \lambda(n)=(-1)^{d(n)}, מחזירה 1 או -1 לפי זוגיות מספר המחלקים הראשוניים של n.

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

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

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

פונקציה המקיימת את השוויון הנ"ל *לכל* n_1,n_2 (גם אם אינם זרים) נקראת **כפלית לחלוטין** (completely multiplicative) או **כפלית במובן החזק** (strongly multiplicative).

## [[קונבולוציית דיריכלה]]
אפשר להגדיר פעולה בינארית הנקראת **קונבולוציית דיריכלה** בין פונקציות אריתמטיות, באופן הבא:
:(f*g)(n)=\sum_{d|n}f(d)g\bigl(\tfrac{n}{d}\bigr)
ביחס לפעולה זו אוסף הפונקציות האריתמטיות הופך למונואיד, שהפונקציות ההפיכות בו הן כל אלו המקיימות f(1)\ne0 (וכך הפונקציות האריתמטיות שלא מקבלות 0 ב-1 הן חבורה אבלית ביחס לקונבולוציה). תכונות מעניינות רבות של פונקציות אריתמטיות אפשר לבטא באמצעות שוויונות בחבורה הזו.

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

נגדיר עוד כמה פונקציות שימושיות: 
*\mathbf{1}(n)=1, הפונקציה המחזירה 1 לכל n.
*\text{id}(n)=n – פונקציית הזהות.
*פונקציית היחידה השווה ל-1 אם n=1, ול-0 אחרת. זהו איבר הזהות בחבורת הפונקציות.

את התכונה החשובה ביותר של פונקציית מביוס אפשר לבטא כך: אם F=\mathbf{1}*f, אז f=\mu*F. במילים אחרות, \mu=\mathbf{1}^{-1}, כלומר \mu היא ההפכית של הפונקציה \mathbf{1} בחבורה. 
דוגמאות נוספות: 
*\mathbf{1}*\mathbf{1}=d
*\text{id}=\phi*\mathbf{1} ולכן גם \phi=\text{id}*\mu. המשוואה הראשונה היא ניסוח מקוצר לזהות \sum_{d|n}\phi(d)=n.
*\sigma=\text{id}*1

## קישורים חיצוניים

*

*
קטגוריה:תורת המספרים