נוסחת ההיפוך של מביוס

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

הנוסחה הוכחה לראשונה על ידי אוגוסט פרדיננד מביוס בשנת 1832.

סימונים והגדרות בסיסיות

בערך זה נשתמש בסימון המקובל לקבוצת המספרים הטבעיים $\mathbb {N}$ ונגדירה ללא המספר 0 (כלומר, המספרים הטבעיים יחלו מהמספר 1).

באופן דומה נסמן ב-$\mathbb {C}$ את קבוצת המספרים המרוכבים, כמקובל.

בהינתן זוג מספרים טבעיים $a,b\in \mathbb {N}$, נאמר כי $a$ מחלק את $b$ ונסמן $a|b$ אם ורק אם קיים $c\in \mathbb {N}$ כלשהו כך ש-$b=ac$.

הפונקציה האריתמטית $\mu \colon \mathbb {N} \to \mathbb {N}$ נקראת פונקציית מביוס והיא מוגדרת כך שלכל $n\in \mathbb {N}$:

$\mu (n):={\begin{cases}1&{\text{if }}n=1\\0&{\text{if }}\exists p{\text{ prime}},p^{2}|n\\(-1)^{k}&{\text{if }}\exists p_{1},p_{2},\dots ,p_{k}{\text{ distinct primes}},n=p_{1}p_{2}\cdots p_{k}\end{cases}}$

הפונקציה האריתמטית $\epsilon \colon \mathbb {N} \to \mathbb {N}$ נקראת פונקציית היחידה והיא מוגדרת כך שלכל $n\in \mathbb {N}$:

$\epsilon (n):={\begin{cases}1&{\text{if }}n=1\\0&{\text{else}}\end{cases}}$

לבסוף, לכל זוג פונקציות אריתמטיות $f,g$ מגדירים את קונבולוציית דיריכלה שלהן $f*g$ כך שלכל $n\in \mathbb {N}$:

$(f*g)(n)=\sum _{d|n}{f\left({\frac {n}{d}}\right)g(d)}$

ניסוח פורמלי

ניסוח קלאסי

יהי שתי פונקציות אריתמטיות $f,F$. אזי, שני התנאים הבאים שקולים:

1. לכל $n\in \mathbb {N}$ מתקיים ש-$F(n)=\sum _{d|n}{f(d)}$
2. לכל $n\in \mathbb {N}$ מתקיים ש-$f(n)=\sum _{d|n}{\mu \left({\frac {n}{d}}\right)F(d)}$

ניסוח באמצעות קונבולוציית דיריכלה

מגדירים את הפונקציה האריתמטית $\mathbf {1} \colon \mathbb {N} \to \mathbb {N}$ כך שלכל $n\in \mathbb {N}$ מתקיים ש-${\textbf {1}}(n)=1$.

יהי שתי פונקציות אריתמטיות $f,F$. אזי, התנאים הבאים שקולים:

1. $F=f*{\textbf {1}}$
2. $f=F*\mu$

הוכחה

תחת קונבולוציית דיריכלה, פונקציית היחידה $\epsilon$ משמשת כאיבר יחידה. כלומר, לכל פונקציה אריתמטית $h$ מתקיים ש-$h*\epsilon =\epsilon *h=h$.

בנוסף, ניתן להוכיח כי $\mu$ ו-${\textbf {1}}$ הן איברים הופכיים תחת קונבולוציית דיריכלה, כלומר -$\mu *{\textbf {1}}={\textbf {1}}*\mu =\epsilon$.

מכל זה ניתן להראות כי:

$F=f*{\textbf {1}}\Longleftrightarrow F*\mu =f*{\textbf {1}}*\mu \Longleftrightarrow F*\mu =f*\epsilon \Longleftrightarrow F*\mu =f$

מ.ש.ל.

מסקנות

• לכל $n\in \mathbb {N}$ מתקיים ש-$n=\sum _{d|n}{\varphi (d)}$, כאשר $\varphi (n)$ היא פונקציית אוילר, לכן לפי נוסחת ההיפוך של מביוס $\varphi (n)=n\sum _{d|n}{\frac {\mu (d)}{d}}$.
• לכל $n,k\in \mathbb {N}$ מתקיים ש-$n^{k}=\sum _{d|n}{J_{k}(d)}$, כאשר $J_{k}(n)$ היא פונקציית ז'ורדן מסדר $k$, לכן לפי נוסחת ההיפוך של מביוס $J_{k}(n)=n^{k}\sum _{d|n}{\frac {\mu (d)}{d^{k}}}$.
• לכל $n\in \mathbb {N}$ מתקיים ש-$\ln(n)=\sum _{d|n}{\Lambda (d)}$, כאשר $\Lambda (n)$ היא פונקציית פון מנגולדט, לכן לפי נוסחת ההיפוך של מביוס $\Lambda (n)=\sum _{d|n}{\mu \left({\frac {n}{d}}\right)\ln d}$.
• לכל $n\in \mathbb {N}$ מתקיים ש-$\sum _{d|n}{\lambda (d)}={\begin{cases}1&{\text{if }}\exists k\in \mathbb {N} ,k^{2}|n\\0&{\text{else}}\end{cases}}$, כאשר $\lambda (n)$ היא פונקציית ליוביל, לכן לפי נוסחת ההיפוך של מביוס $\lambda (n)=\sum _{d^{2}|n}{\mu \left({\frac {n}{d^{2}}}\right)}$.

הכללה לפונקציות כלליות

בהינתן זוג פונקציות $F,G\colon (0,\infty )\to \mathbb {C}$ המתאפסות בקטע הפתוח $(0,1)$ ופונקציה אריתמטית כפלית לחלוטין $\alpha$, שני התנאים הבאים שקולים:

1. $G(x)=\sum _{n\leq x}{\alpha (n)F\left({\frac {x}{n}}\right)}$
2. $F(x)=\sum _{n\leq x}{\mu (n)\alpha (n)G\left({\frac {x}{n}}\right)}$

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

• גדי אלכסנדרוביץ', נוסחת ההיפוך של מביוס, באתר "לא מדויק", 7 בינואר 2012
• נוסחת ההיפוך של מביוס, באתר MathWorld (באנגלית)
• Mobius Inversion -- Number Theory's Secret Weapon, סרטון בערוץ "Michael Penn", באתר יוטיוב, 13/8/2024