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

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

דוגמאות:

• הפונקציה $d:\mathbb {N} \to \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)^{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)\geq 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$ מקבלת את הערכים $\pm 1$ בצפיפות ${\frac {6}{\pi ^{2}}}$, ו-0 בשאר הזמן. למרבה ההפתעה, התוצאה (הצפויה לכאורה) שהערך הממוצע שואף לאפס, שקולה למשפט המספרים הראשוניים, ואילו הטענה שהערך הממוצע קטן מ-$O(x^{-0.5})$ שקולה להשערת רימן.

כפליות

פונקציה אריתמטית המקיימת $f(n_{1}n_{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\cdot 4\cdot 31=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)\neq 0$ (וכך הפונקציות האריתמטיות שלא מקבלות $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$

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

מדיה וקבצים בנושא פונקציה אריתמטית בוויקישיתוף

• פונקציה אריתמטית, באתר אנציקלופדיה למתמטיקה (באנגלית)