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

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

דוגמאות:

• הפונקציה ${\displaystyle d:\mathbb {N} \to \mathbb {N} }$ מוגדרת כך ש- ${\displaystyle d(n)}$ הוא מספר המחלקים השונים של ${\displaystyle n}$. למשל ${\displaystyle d(1)=1,d(2)=2,d(4)=3,d(6)=4}$. מספר ${\displaystyle n}$ הוא מספר ראשוני אם ורק אם ${\displaystyle d(n)=2}$.
• פונקציית מביוס ${\displaystyle \mu }$ מוגדרת לפי מספר המחלקים הראשוניים: ${\displaystyle \mu (1)=1}$, ${\displaystyle \mu (n)=0}$ אם יש ל-${\displaystyle n}$ גורמים ריבועיים, ו-${\displaystyle \mu (n)=(-1)^{r}}$ אם ${\displaystyle n}$ הוא מכפלת ${\displaystyle r}$ ראשוניים שונים.
• פונקציית אוילר ${\displaystyle \phi }$ (פי) מוגדרת לפי מספר המספרים הזרים למספר נתון וקטנים ממנו: ${\displaystyle \phi (n)}$ שווה למספר המספרים הקטנים מ-${\displaystyle n}$ וזרים לו. כך למשל ${\displaystyle \phi (12)={\bigl |}\{1,5,7,11\}{\bigr |}=4}$.
• הפונקציה ${\displaystyle \sigma }$ מוגדרת על ידי סיכום המחלקים (החיוביים) של מספר. למשל ${\displaystyle \sigma (12)=1+2+3+4+6+12=28}$. מספר משוכלל הוא כזה המקיים ${\displaystyle \sigma (n)=2n}$.
• באופן כללי יותר, הפונקציה ${\displaystyle \sigma _{k}}$ (פונקציית מחלקים) מוגדרת על ידי סיכום חזקות-${\displaystyle k}$ של המחלקים. למשל ${\displaystyle \sigma _{2}(12)=1^{2}+2^{2}+3^{2}+4^{2}+6^{2}+12^{2}=210}$. לפי הגדרה זו ${\displaystyle \sigma _{0}=d,\sigma _{1}=\sigma }$.
• הפונקציה ${\displaystyle r}$ המחזירה לכל ${\displaystyle n}$ את מספר הפתרונות השלמים למשוואה ${\displaystyle x^{2}+y^{2}=n}$. למשל ${\displaystyle r(1)=4,r(3)=0,r(5)=8}$. אם נסמן ${\displaystyle d_{1}(n),d_{3}(n)}$ את סכומם של מחלקי ${\displaystyle n}$ הנותנים בהתאמה שארית 1 או 3 בחלוקה ל-4, אזי מתקיים ${\displaystyle r(n)=4(d_{1}(n)-d_{3}(n))}$ (ראו סכום של שני ריבועים), ומכאן שתמיד ${\displaystyle d_{1}(n)\geq d_{3}(n)}$.
• פונקציית ליוביל ${\displaystyle \lambda (n)=(-1)^{d(n)}}$, מחזירה ${\displaystyle 1}$ או ${\displaystyle -1}$ לפי זוגיות מספר המחלקים הראשוניים של ${\displaystyle n}$.

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

דוגמאות:

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

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

פונקציה המקיימת את השוויון הנ"ל לכל ${\displaystyle n_{1},n_{2}}$ (גם אם אינם זרים) נקראת כפלית לחלוטין (completely multiplicative) או כפלית במובן החזק (strongly multiplicative).

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

${\displaystyle (f*g)(n)=\sum _{d|n}f(d)g{\bigl (}{\tfrac {n}{d}}{\bigr )}}$

ביחס לפעולה זו אוסף הפונקציות האריתמטיות הופך למונואיד, שהפונקציות ההפיכות בו הן כל אלו המקיימות ${\displaystyle f(1)\neq 0}$ (וכך הפונקציות האריתמטיות שלא מקבלות ${\displaystyle 0}$ ב-${\displaystyle 1}$ הן חבורה אבלית ביחס לקונבולוציה). תכונות מעניינות רבות של פונקציות אריתמטיות אפשר לבטא באמצעות שוויונות בחבורה הזו.

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

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

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

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

• ${\displaystyle \mathbf {1} *\mathbf {1} =d}$
• ${\displaystyle {\text{id}}=\phi *\mathbf {1} }$ ולכן גם ${\displaystyle \phi ={\text{id}}*\mu }$. המשוואה הראשונה היא ניסוח מקוצר לזהות ${\displaystyle \sum _{d|n}\phi (d)=n}$.
• ${\displaystyle \sigma ={\text{id}}*1}$

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

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