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

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

דוגמאות:

הפונקציה $\ d : \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 כסכום של שני ריבועים. למשל $\ 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)$ .

[עריכה] גידול ממוצע

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

דוגמאות:

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

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

[עריכה] כפל של פונקציות

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

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

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

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

$\ One(n)=1$ , הפונקציה מחזירה 1 לכל ערך של n.
$\ I(n)=n$ - פונקציית הזהות.
$\ \delta_1(n)$ השווה ל- 1 אם n=1, ול- 0 אחרת. זהו איבר הזהות בחבורת הפונקציות.

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