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

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

דוגמאות:

הפונקציה $d\colon \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)$ .
פונקציית ליוביל, $\lambda (n)=(-1)^{d(n)}$ , מחזירה $1$ או $-1$ לפי זוגיות מספר המחלקים של $n$ ‏ ( $\lambda (1)=1$ ).

גידול ממוצע

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

דוגמאות:

הגודל הממוצע של הפונקציה $r$ לעיל הוא $\pi$ (פאי), כלומר: בממוצע ניתן להציג מספר כסכום של שני ריבועים ב- $\pi$ דרכים.
הערך הממוצע של מספר המחלקים $d(n)$ הוא $\log(n)+(2\gamma -1)+O(n^{-1/2})$ . הלוגריתם הוא כמובן בבסיס הטבעי, ו- $\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^{-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$ המחלקים.

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

קונבולוציית דיריכלה

ערך מורחב – קונבולוציית דיריכלה

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

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

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

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

$\mathbf {1} (n)=1$ , הפונקציה שמחזירה $1$ לכל ערך של $n$ .
$\operatorname {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$ .
$\operatorname {id} =\phi *\mathbf {1}$ ולכן גם $\phi =\operatorname {id} *\mu$ . המשוואה הראשונה היא ניסוח מקוצר לזהות $\sum _{d|n}\phi (d)=n$ .
$\sigma =\operatorname {id} *1$ .