Dirichlet konvolution

I matematik är Dirichlet -faltningen en binär operation definierad för aritmetiska funktioner ; det är viktigt i talteorin . Den utvecklades av Peter Gustav Lejeune Dirichlet .

Definition

Om $f,g:\mathbb {N} \to \mathbb {C}$ är två aritmetiska funktioner från de positiva heltalen till de komplexa talen , är Dirichlet - faltningen f ∗ g en ny aritmetisk funktion definierad av:

$(f*g)(n)\ =\ \sum _{d\,\mid \,n}f(d)\,g\!\left({\frac {n}{d}}\right)\ =\ \summa _{ab\,=\ ,n}\!f(a)\,g(b)$

där summan sträcker sig över alla positiva delare d av n , eller ekvivalent över alla distinkta par ( a , b ) av positiva heltal vars produkt är n .

Denna produkt förekommer naturligt i studien av Dirichlet-serien som Riemann zeta-funktionen . Den beskriver multiplikationen av två Dirichlet-serier i termer av deras koefficienter:

$\left(\sum _{n\geq 1}{\frac {f(n)}{n^{s}}}\right)\left(\sum _{n\geq 1}{\frac {g(n)}{n^{s}}}\höger)\ =\ \left(\summa _{n\geq 1}{\frac {(f*g)(n)}{n^{s }}}\höger).$

Egenskaper

Uppsättningen av aritmetiska funktioner bildar en kommutativ ring , Dirichlet-ringen , under punktvis addition , där f + g definieras av ( f + g )( n ) = f ( n ) + g ( n ) och Dirichlet-faltning. Den multiplikativa identiteten är enhetsfunktionen ε definierad av ε ( n ) = 1 om n = 1 och ε ( n ) = 0 om n > 1 . Enheterna (inverterbara element) i denna ring är de aritmetiska funktionerna f med f (1 ≠ 0 ) .

Specifikt är Dirichlet-faltning associativ ,

$(f*g)*h=f*(g*h),$

fördelande framför addition

$f*(g+h)=f*g+f*h$ ,

kommutativ ,

$f*g=g*f$ ,

och har ett identitetselement,

$f*\varepsilon$ = $\varepsilon *f=f$ .

Dessutom, för varje $f$ som har $f(1)\neq 0$ , finns det en aritmetisk funktion $f^{-1}$ med $f*f^{-1}=\varepsilon$ , kallad Dirichlet-inversen av $f$ .

Dirichlet-faltningen av två multiplikativa funktioner är återigen multiplikativ, och varje multiplikativ funktion som inte är konstant noll har en Dirichlet-invers som också är multiplikativ. Multiplikativa funktioner bildar med andra ord en undergrupp av gruppen av inverterbara element i Dirichletringen. Observera dock att summan av två multiplikativa funktioner inte är multiplikativ (eftersom $(f+g)(1)=f( 1)+g(1)=2\neq 1$ ), så delmängden av multiplikativa funktioner är inte en subring av Dirichlet-ringen. Artikeln om multiplikativa funktioner listar flera faltningsrelationer mellan viktiga multiplikativa funktioner.

En annan operation på aritmetiska funktioner är punktvis multiplikation: fg definieras av ( fg )( n ) = f ( n ) g ( n ) . Givet en helt multiplikativ funktion ${\displaystyle h} fördelar$ punktvis multiplikation med $h$ över Dirichlet faltning: $(f*g) h=(fh)*(gh)$ . Konvolutionen av två fullständigt multiplikativa funktioner är multiplikativ, men inte nödvändigtvis fullständigt multiplikativ.

Exempel

I dessa formler använder vi följande aritmetiska funktioner :

• $\varepsilon$ är den multiplikativa identiteten: $\varepsilon (1)=1$ , annars 0 ( $\varepsilon (n) =\lgolv {\tfrac {1}{n}}\rgolv$ ).
• $1$ är konstantfunktionen med värdet 1: $1(n)=1$ för alla $n$ . Tänk på att $1$ inte är identiteten. (Vissa författare betecknar detta som $\zeta$ eftersom den associerade Dirichlet-serien är Riemann zeta-funktionen .)
• $1_{C}$ för $C\subset \mathbb {N}$ är en uppsättningsindikatorfunktion : 1 $\displaystyle 1_{C}(n)= 1}$ iff $n\in C$ , annars 0.
• ${\text{Id}}$ är identitetsfunktionen med värdet n : ${\text{Id}}(n)=n$ .
• ${\text{Id}}_{k}$ är den k: te potensfunktionen: ${\text{Id}}_{k}(n)= n^{k}$ .

Följande relationer gäller:

• $1*\mu =\varepsilon$ , Dirichlet-inversen av konstantfunktionen $1$ är Möbius-funktionen . Därav:
• $g=f*1$ om och endast om $f=g*\mu$ , Möbius-inversionsformeln
• $\sigma _{k}={\text{Id}}_{k}*1$ , den k:te potensen-av-divisors summafunktion σ _k
• $\sigma ={\text{Id}}*1$ , summa-av-divisorfunktionen σ = σ ₁
• $d=1*1$ , antalet-divisorfunktionen d ( n ) = σ ₀
• ${\displaystyle {\text{Id}}_{k}=\sigma _{k}*\mu } ,$ genom Möbius inversion av formlerna för σ _k , σ , och d
• ${\text{Id}}=\sigma *\mu$
• $1=d*\mu$
• $\phi *1={\text{Id}}$ , bevisad under Eulers totientfunktion
• $\phi ={\text{Id}}*\mu$ , genom Möbius inversion
• $\sigma =\phi *d$ , från att konvolvera 1 på båda sidor av $\phi *1={\text{Id}}$
• $\lambda *|\mu |=\varepsilon$ där λ är Liouvilles funktion
• $\lambda *1=1_{\text{Sq}}$ där Sq = {1, 4, 9, ...} är mängden kvadrater
• ${\text{Id}}_{k}*({\text{Id}}_{k}\mu )=\varepsilon$
• $d^{3}*1=(d*1)^{2}$
• ${\displaystyle J_{k}*1={\text{Id}}_{k}} ,$ Jordans totientfunktion
• $({\text{Id}}_{s}J_{r})*J_{s}=J_{s+r}$
• $\Lambda *1=\log$ , där $\Lambda$ är von Mangoldts funktion
• $|\mu |\ast 1=2^{\omega },$ där $\omega (n)$ är den primära omega-funktionen som räknar distinkta primtalsfaktorer av n
• ${\displaystyle \Omega \ast \mu =1_{\mathcal {P}}} ,$ den karakteristiska funktionen för primpotenserna.
• $\omega \ast \mu =1_{\mathbb {P} }$ där $1_{\mathbb {P} }(n) \mapsto \{0,1\}$ är primtalens karakteristiska funktion.

Denna sista identitet visar att primräkningsfunktionen ges av summeringsfunktionen

$\pi (x)=\summa _{n\leq x}(\omega \ast \mu )(n)=\summa _{d=1}^{x}\omega (d)M\left(\left\lgolv {\frac {x}{d}}\ höger\rgolv \höger)$

där $M(x)$ är Mertens-funktionen och $\omega$ är den distinkta primtalsfaktorräkningsfunktionen från ovan. Denna expansion följer av identiteten för summorna över Dirichlet-falsningar som ges på för delningssummaidentiteter ( ett standardtrick för dessa summor).

Dirichlet omvänd

Exempel

Givet en aritmetisk funktion ${\displaystyle f} kan$ dess Dirichlet-invers $g=f^{-1}$ beräknas rekursivt: värdet av $g(n)$ är i termer av $g(m)$ för $m<n$ .

För $n=1$ :

$(f*g)(1)=f(1)g(1)=\varepsilon (1) =1$ , så

$g(1)=1/f(1)$ . Detta innebär att $f$ inte har en Dirichlet-invers om $f(1)=0$ .

För $n=2$ :

$(f*g)(2)=f(1)g( 2)+f(2)g(1)=\varepsilon (2)=0$ ,

$g(2)= -(f(2)g(1))/f(1)$ ,

För $n=3$ :

$(f*g)(3)=f(1)g( 3)+f(3)g(1)=\varepsilon (3)=0$ ,

$g(3)= -(f(3)g(1))/f(1)$ ,

För $n=4$ :

$(f*g)( 4)=f(1)g(4)+f(2)g(2)+f(4)g(1)=\varepsilon (4)=0$ ,

$g(4)=-(f(4)g(1)+f(2)g(2))/f( 1)$ ,

och i allmänhet för $n>1$ ,

$g(n)\ =\ {\frac {-1}{f(1)}}\mathop {\sum _{d\,\mid \,n}} _{d<n}f\vänster ({\frac {n}{d}}\right)g(d).$

Egenskaper

Följande egenskaper hos Dirichlet-inversen gäller:

• Funktionen f har en Dirichlet-invers om och endast om f (1) ≠ 0 .
• Dirichlet-inversen av en multiplikativ funktion är återigen multiplikativ.
• Dirichlet-inversen av en Dirichlet-faltning är faltningen av inverserna av varje funktion: $(f\ast g)^{-1}=f^{ -1}\ast g^{-1}$ .
• En multiplikativ funktion f är helt multiplikativ om och endast om $f^{-1}(n)=\mu (n)f(n)$ .
• Om f är fullständigt multiplikativ då $(f\cdot g)^{-1}=f\cdot g^{-1}$ när $g(1)\neq 0$ och där $\cdot$ anger punktvis multiplikation av funktioner.

Andra formler

Aritmetisk funktion	Dirichlet invers:
Konstant funktion med värde 1	Möbius funktion μ
$n^{\alpha }$	$\mu (n)\,n^{\alpha }$
Liouvilles funktion λ	Absolutvärde för Möbius-funktionen | μ |
Eulers totientfunktion $\varphi$	$\sum _{d|n}d\,\mu (d)$
Den generaliserade summa-av-divisorfunktionen $\sigma _{\alpha }$	$\sum _{d|n}d^{\alpha }\mu (d)\mu \left({\frac {n}{d}}\ höger)$

En exakt, icke-rekursiv formel för Dirichlet-inversen av valfri aritmetisk funktion f ges i Divisor summa identiteter . Ett mer partitionsteoretiskt uttryck för Dirichlet-inversen av f ges av

$f^{-1}(n)=\sum _{k=1}^{\Omega (n)}\left\{\sum _{{\lambda _{1}+2\lambda _{ 2}+\cdots +k\lambda _{k}=n} \atop {\lambda _{1},\lambda _{2},\ldots ,\lambda _{k}|n}}{\frac { (\lambda _{1}+\lambda _{2}+\cdots +\lambda _{k})!}{1!2!\cdots k!}}(-1)^{k}f(\lambda _{1})f(\lambda _{2})^{2}\cdots f(\lambda _{k})^{k}\right\}.$

Följande formel ger ett kompakt sätt att uttrycka Dirichlet-inversen av en inverterbar aritmetisk funktion f :

$f^{-1}=\summa _{k=0}^{+\infty }{\frac {(f(1)\varepsilon -f)^{*k}}{f(1)^{k+1}}}$

där uttrycket $(f(1)\varepsilon -f)^{*k}$ står för den aritmetiska funktionen $f( 1)\varepsilon -f$ hopvikt med sig själv k gånger. Lägg märke till att för ett fast positivt heltal $n$ , om $k>\Omega (n)$ så ${ \displaystyle (f(1)\varepsilon -f)^{*k}(n)=0} ,$ detta beror på att $f(1)\varepsilon (1)-f(1)=0$ och varje sätt att uttrycka n som en produkt av k positiva heltal måste inkludera en 1, så serien på höger sida konvergerar för varje fast positivt heltal n.

Dirichlet-serien

Om f är en aritmetisk funktion, definieras Dirichlet-seriens genererande funktion av

$DG(f;s)=\summa _{n=1}^{\infty }{\frac {f(n) }{n^{s}}}$

för de komplexa argument s för vilka serien konvergerar (om det finns några). Multiplikationen av Dirichlet-serien är kompatibel med Dirichlet-faltning i följande betydelse:

$DG(f;s)DG(g;s)=DG(f*g;s)\,$

för alla s för vilka båda serierna på vänster sida konvergerar, en av dem konvergerar åtminstone absolut (observera att enkel konvergens av båda serierna på vänster sida inte innebär konvergens av höger sida!). Detta är besläktat med faltningssatsen om man tänker på Dirichlet-serien som en Fouriertransform .

Relaterade begrepp

Begränsningen av divisorerna i faltningen till enhetliga , bi-unitära eller infinitära divisorer definierar liknande kommutativa operationer som delar många egenskaper med Dirichlet-faltningen (existensen av en Möbius-inversion, beständig multiplikativitet, definitioner av totienter, produktformler av Euler-typ över associerade primtal etc.).

Dirichlet-faltning är faltningen av incidensalgebra för de positiva heltal ordnade efter delbarhet.

Se även

• Aritmetisk funktion
• Delningssummaidentiteter
• Möbius inversionsformel

•     Apostol, Tom M. (1976), Introduktion till analytisk talteori , Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3 , MR 0434929 , Zbl 03135.1000
•   Chan, Heng Huat (2009). Analytisk talteori för studenter . Monografier i talteori. World Scientific Publishing Company. ISBN 978-981-4271-36-3 .
•   Hugh L. Montgomery ; Robert C. Vaughan (2007). Multiplikativ talteori I. Klassisk teori . Cambridge traktater i avancerad matematik. Vol. 97. Cambridge: Cambridge Univ. Tryck. sid. 38. ISBN 978-0-521-84903-6 .
•   Cohen, Eckford (1959). "En klass av restsystem (mod r) och relaterade aritmetiska funktioner. I. En generalisering av Möbius-inversion". Pacific J. Math . Vol. 9, nr. 1. s. 13–23. MR 0109806 .
•   Cohen, Eckford (1960). "Aritmetiska funktioner förknippade med enhetsdelaren för ett heltal". Mathematische Zeitschrift . Vol. 74. s. 66–80. doi : 10.1007/BF01180473 . MR 0112861 .
•   Cohen, Eckford (1960). "Antalet enhetsdelare för ett heltal". American Mathematical Monthly . Vol. 67, nr. 9. s. 879–880. MR 0122790 .
•   Cohen, Graeme L. (1990). "På ett heltals oändliga delare". Matematik. Comp . Vol. 54, nr. 189. s. 395–411. doi : 10.1090/S0025-5718-1990-0993927-5 . MR 0993927 .
• Cohen, Graeme L. (1993). "Aritmetiska funktioner associerade med infinitära divisorer av ett heltal". Int. J. Math. Matematik. Sci . Vol. 16, nr. 2. s. 373–383. doi : 10.1155/S0161171293000456 .
•   Sandor, Jozsef; Berge, Antal (2003). "Möbiusfunktionen: generaliseringar och förlängningar". Adv. Hingst. Contemp. Matematik. (Kyungshang) . 6 (2): 77–128. MR 1962765 .
• Finch, Steven (2004). "Unitarism och infinitarism" (PDF) . Arkiverad från originalet (PDF) 2015-02-22.

externa länkar

• "Dirichlet convolution" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]