Identity dělitele součtu - Divisor sum identities

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Dubna 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) The hlavní část tohoto článku možná bude třeba přepsat. Důvod je uveden: Sekce olova musí být přepsána - viz Pls MOS: VEDTE Použijte průvodce rozvržením elektrody zajistit, aby tato část dodržovala normy Wikipedie a obsahovala všechny důležité podrobnosti. (Dubna 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek vyžaduje pozornost odborníka na toto téma. Přidejte prosím důvod nebo a mluvit parametr k této šabloně pro vysvětlení problému s článkem. Při umisťování této značky zvažte přidružení této žádosti s WikiProject. (Květen 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Účelem této stránky je katalogizovat nové, zajímavé a užitečné identity související s číselně teoretický dělitel součty, tj. součty an aritmetická funkce nad děliteli přirozeného čísla ${ displaystyle n}$, nebo ekvivalentně Dirichletova konvoluce aritmetické funkce ${ displaystyle f (n)}$ s jedním:

${ displaystyle g (n): = součet _ {d mid n} f (d).}$

Tyto identity zahrnují aplikace na součty aritmetické funkce přes jen správné prvočíselné děliče ${ displaystyle n}$. Také definujeme periodicky varianty těchto dělících částek s ohledem na největší společný dělitel funkce v podobě

${ Displaystyle g_ {m} (n): = součet _ {d mid (m, n)} f (d), 1 leq m leq n}$

Známé inverzní vztahy, které umožňují funkci ${ displaystyle f (n)}$ bude vyjádřeno jako ${ displaystyle g (n)}$ jsou poskytovány Möbioův inverzní vzorec. Při zvažování přirozeně vznikají některé z nejzajímavějších příkladů takových identit funkce průměrné objednávky nad aritmetickou funkcí ${ displaystyle f (n)}$ definován jako dělitel součet jiné aritmetické funkce ${ displaystyle g (n)}$. Pro konkrétní příklady dělitelských částek zahrnujících speciální aritmetické funkce a speciální Dirichletovy závity aritmetických funkcí najdete na následujících stránkách: tady, tady, tady, tady, a tady.

Průměrné identity součtu objednávky

Výměna součtových identit

Následující identity jsou primární motivací pro vytvoření této tematické stránky. Tyto identity se nejeví jako dobře známé nebo přinejmenším dobře zdokumentované a jsou velmi užitečnými nástroji, které můžete mít v některých aplikacích po ruce. V následujícím textu to považujeme ${ displaystyle f, g, h, u, v: mathbb {N} rightarrow mathbb {C}}$ jsou předepsány aritmetické funkce a to ${ displaystyle G (x): = součet _ {n leq x} g (n)}$ označuje součtovou funkci ${ displaystyle g (n)}$. Běžnější zvláštní případ prvního součtu níže je odkazován tady.^[1]

1. ${ displaystyle sum _ {n = 1} ^ {x} v (n) sum _ {d mid n} h (d) u ​​ left ({ frac {n} {d}} right) = sum _ {n = 1} ^ {x} h (n) sum _ {k = 1} ^ { left lfloor { frac {x} {n}} right rfloor} u (k) v (nk)}$
2. ${ displaystyle { begin {aligned} sum _ {n = 1} ^ {x} f (n) sum _ {d mid n} g left ({ frac {n} {d}} right ) & = sum _ {n = 1} ^ {x} f (n) G left ( left lfloor { frac {x} {n}} right rfloor right) = sum _ {i = 1} ^ {x} left ( sum _ { left lceil { frac {x + 1} {i + 1}} right rceil leq n leq left lfloor { frac {x -1} {i}} right rfloor} f (n) right) G (i) + sum _ {d mid x} G (d) f left ({ frac {x} {d} } vpravo) end {zarovnáno}}}$
3. ${ displaystyle sum _ {d = 1} ^ {x} f (d) left ( sum _ {r mid (d, x)} g (r) h left ({ frac {d} { r}} right) right) = sum _ {r mid x} g (r) left ( sum _ {1 leq d leq x / r} h (d) f (rd) right )}$
4. ${ displaystyle sum _ {m = 1} ^ {x} left ( sum _ {d mid (m, x)} f (d) g left ({ frac {x} {d}} right) right) = sum _ {d mid x} f (d) g left ({ frac {x} {d}} right) cdot { frac {x} {d}}}$
5. ${ displaystyle sum _ {m = 1} ^ {x} left ( sum _ {d mid (m, x)} f (d) g left ({ frac {x} {d}} vpravo) vpravo) t ^ {m} = (t ^ {x} -1) cdot sum _ {d mid x} { frac {t ^ {d} f (d)} {t ^ {d } -1}} g vlevo ({ frac {x} {d}} vpravo)}$

Obecně se tyto identity shromažďují z tzv.rarity a b-strany„jak dobře zavedené, tak polotmavé analytická teorie čísel poznámky a techniky a práce a práce přispěvatelů. Samotné identity není obtížné prokázat a jsou cvičením standardních manipulací s řadou inverzí a dělitelskými součty. Proto zde jejich důkazy vynecháváme.

Metoda konvoluce

The metoda konvoluce je obecná technika pro odhad průměrného součtu objednávek formuláře

${ displaystyle sum _ {n leq x} f (n) qquad { text {nebo}} qquad sum _ { stackrel {q leq x} {q { text {squarefree}}}} f (q),}$

kde multiplikativní funkce F lze napsat jako konvoluci formuláře ${ displaystyle f (n) = (u ast v) (n)}$ pro vhodné, definované aplikací aritmetické funkce u a proti. Krátký přehled této metody lze nalézt tady.

Periodické dělicí částky

An aritmetická funkce je periodické (mod k)nebo k-periodické, pokud ${ displaystyle f (n + k) = f (n)}$ pro všechny ${ displaystyle n in mathbb {N}}$. Zvláštní příklady k- teoretické funkce periodického čísla jsou Dirichletovy postavy ${ displaystyle f (n) = chi (n)}$ modulo k a největší společný dělitel funkce ${ displaystyle f (n) = (n, k)}$. Je známo, že každý k-periodická aritmetická funkce má reprezentaci jako a konečný oddělený Fourierova řada formuláře

${ displaystyle f (n) = součet _ {m = 1} ^ {k} a_ {k} (m) e left ({ frac {mn} {k}} right),}$

Kde Fourierovy koeficienty ${ displaystyle a_ {k} (m)}$ definované následující rovnicí jsou také k-periodické:

${ displaystyle a_ {k} (m) = { frac {1} {k}} součet _ {n = 1} ^ {k} f (n) e left (- { frac {mn} {k }}že jo).}$

Zajímá nás následující k-periodické dělicí součty:

${ displaystyle s_ {k} (n): = sum _ {d mid (n, k)} f (d) g left ({ frac {k} {d}} right) = sum _ {m = 1} ^ {k} a_ {k} (m) e left ({ frac {mn} {k}} right).}$

Faktem je, že Fourierovy koeficienty těchto variant dělitelského součtu jsou dány vzorcem ^[2]

${ displaystyle a_ {k} (m) = součet _ {d mid (m, k)} g (d) f levý ({ frac {k} {d}} pravý) { frac {d } {k}}.}$

Fourierovy transformace GCD

Můžeme také vyjádřit Fourierovy koeficienty v rovnici bezprostředně výše, pokud jde o Fourierova transformace jakékoli funkce h na vstupu ${ displaystyle operatorname {gcd} (n, k)}$ pomocí následujícího výsledku kde ${ displaystyle c_ {q} (n)}$ je Ramanujan součet (srov. Fourierova transformace totientní funkce ):^[3]

${ displaystyle F_ {h} (m, n) = součet _ {k = 1} ^ {n} h ((k, n)) e left (- { frac {km} {n}} right ) = (h ast c _ { bullet} (m)) (n).}$

Kombinací výše uvedených výsledků to tedy získáme

${ displaystyle a_ {k} (m) = součet _ {d mid (m, k)} g (d) f doleva ({ frac {k} {d}} doprava) { frac {d } {k}} = sum _ {d mid k} sum _ {r mid d} f (r) g (d) c _ { frac {d} {r}} (m).}$

Součty za hlavní dělitele

Nechte funkci ${ displaystyle a (n)}$ označit charakteristická funkce z připraví, tj., ${ displaystyle a (n) = 1}$ kdyby a jen kdyby ${ displaystyle n}$ je prvočíslo a jinak má nulovou hodnotu. Pak jako speciální případ první identity v rovnici (1) v sekci výměna identifikačních součtů výše můžeme vyjádřit průměrné částky objednávky

${ displaystyle sum _ {n = 1} ^ {x} sum _ { stackrel {p mid n} {p { text {prime}}}} f (p) = sum _ {p = 1 } ^ {x} a (p) f (p) left lfloor { frac {x} {p}} right rfloor = sum _ { stackrel {p = 1} {p { text {prime }}}} ^ {x} f (p) left lfloor { frac {x} {p}} right rfloor.}$

Máme také integrální vzorec založený na Abelův součet pro součty formuláře ^[4]

${ displaystyle sum _ { stackrel {p = 1} {p { text {prime}}}} ^ {x} f (p) = pi (x) f (x) - int _ {2} ^ {x} pi (t) f ^ { prime} (t) dt přibližně { frac {xf (x)} { log x}} - int _ {2} ^ {x} { frac {t} { log t}} f ^ { prime} (t) dt,}$

kde ${ displaystyle pi (x) sim { frac {x} { log x}}}$ označuje funkce počítání prvočísel. Zde obvykle vytváříme předpoklad, že funkce F je kontinuální a rozlišitelný.

Někteří méně ocenili identitu dělitele součtu

Máme následující vzorce dělitele součtu pro F libovolná aritmetická funkce a G zcela multiplikativní kde ${ displaystyle varphi (n)}$ je Eulerova totientová funkce a ${ displaystyle mu (n)}$ je Möbiova funkce:^[5][6]

1. ${ displaystyle sum _ {d mid n} f (d) varphi left ({ frac {n} {d}} right) = sum _ {k = 1} ^ {n} f ( operatorname {gcd} (n, k))}$
2. ${ displaystyle sum _ {d mid n} mu (d) f (d) = prod _ { stackrel {p mid n} {p { text {prime}}}} (1-f ( p))}$
3. ${ displaystyle f (m) f (n) = součet _ {d mid (m, n)} g (d) f doleva ({ frac {mn} {d ^ {2}}} doprava) .}$
4. Li F je zcela multiplikativní pak bodové násobení ${ displaystyle cdot}$ s výtěžkem Dirichletovy konvoluce ${ Displaystyle f cdot (g ast h) = (f cdot g) ast (f cdot h)}$.
5. ${ displaystyle sum _ {d ^ {k} mid n} mu (d) = { Biggl {} { begin {pole} {ll} 0, & { text {if}} m ^ { k} mid n { text {pro některé}} m> 1; 1, & { text {jinak.}} end {pole}}}$
6. Li ${ displaystyle m geq 1}$ a n má více než m odlišné hlavní faktory, pak ${ displaystyle sum _ {d mid n} mu (d) log ^ {m} (d) = 0.}$

Dirichletova inverze aritmetické funkce

Přijmeme notaci, že ${ displaystyle varepsilon (n) = delta _ {n, 1}}$ označuje multiplikativní identitu Dirichletovy konvoluce ${ displaystyle ( varepsilon ast f) (n) = (f ast varepsilon) (n) = f (n)}$ pro jakoukoli aritmetickou funkci F a ${ displaystyle n geq 1}$. The Dirichlet inverzní funkce F splňuje ${ displaystyle (f ast f ^ {- 1}) (n) = (f ^ {- 1} ast f) (n) = varepsilon (n)}$ pro všechny ${ displaystyle n geq 1}$. Existuje dobře známý rekurzivní konvoluční vzorec pro výpočet Dirichlet inverzní ${ displaystyle f ^ {- 1} (n)}$ funkce F indukcí ve formě ^[7]

${ displaystyle f ^ {- 1} (n) = { Biggl {} { begin {pole} {ll} { frac {1} {f (1)}}, a { text {if}} n = 1; - { frac {1} {f (1)}} sum _ { stackrel {d mid n} {d> 1}} f (d) f ^ {- 1} vlevo ({ frac {n} {d}} vpravo), & { text {if}} n> 1. end {pole}}}$

Pro pevnou funkci F, nechte funkci ${ displaystyle f _ { pm} (n): = (- 1) ^ { delta _ {n, 1}} f (n) = { Biggl {} { begin {matrix} -f (1) , & { text {if}} n = 1; f (n), & { text {if}} n> 1 end {matrix}}}$

Dále definujte následující dvě vícenásobné nebo vnořené varianty konvoluce pro jakoukoli pevnou aritmetickou funkci F:

${ displaystyle { begin {aligned} { widetilde { operatorname {ds}}} _ {j, f} (n) &: = underbrace { left (f _ { pm} ast f ast cdots ast f right)} _ {j { text {times}}} (n) operatorname {ds} _ {j, f} (n) &: = { Biggl {} { begin { pole} {ll} f _ { pm} (n), & { text {if}} j = 1; součet limity _ { stackrel {d mid n} {d> 1}} f ( d) operatorname {ds} _ {j-1, f} (n / d), & { text {if}} j> 1. end {pole}} end {zarovnáno}}}$

Funkce ${ displaystyle D_ {f} (n)}$ ekvivalentní dvojicí součtových vzorců v další rovnici úzce souvisí s Dirichlet inverzní pro libovolnou funkci F.^[8]

${ displaystyle D_ {f} (n): = součet _ {j = 1} ^ {n} operatorname {ds} _ {2j, f} (n) = součet _ {m = 1} ^ { left lfloor { frac {n} {2}} right rfloor} sum _ {i = 0} ^ {2m-1} { binom {2m-1} {i}} (- 1) ^ { i + 1} { widetilde { operatorname {ds}}} _ {i + 1, f} (n)}$

Zejména to můžeme dokázat ^[9]

${ displaystyle f ^ {- 1} (n) = left (D + { frac { varepsilon} {f (1)}} right) (n).}$

Tabulka hodnot hodnoty ${ displaystyle D_ {f} (n)}$ pro ${ displaystyle 2 leq n leq 16}$ zobrazí se níže. Tato tabulka upřesňuje zamýšlený význam a interpretaci této funkce jako podepsaného součtu všech možných násobků k-konvolce funkce F sám se sebou.

n	${ displaystyle D_ {f} (n)}$	n	${ displaystyle D_ {f} (n)}$	n	${ displaystyle D_ {f} (n)}$
2	${ displaystyle - { frac {f (2)} {f (1) ^ {2}}}}$	7	${ displaystyle - { frac {f (7)} {f (1) ^ {2}}}}$	12	${ displaystyle { frac {2f (3) f (4) + 2f (2) f (6) -f (1) f (12)} {f (1) ^ {3}}} - { frac { 3f (2) ^ {2} f (3)} {f (1) ^ {4}}}}$
3	${ displaystyle - { frac {f (3)} {f (1) ^ {2}}}}$	8	${ displaystyle { frac {2f (2) f (4) -f (1) f (8)} {f (1) ^ {3}}} - { frac {f (2) ^ {3}} {f (1) ^ {4}}}}$	13	${ displaystyle - { frac {f (13)} {f (1) ^ {2}}}}$
4	${ displaystyle { frac {f (2) ^ {2} -f (1) f (4)} {f (1) ^ {3}}}}$	9	${ displaystyle { frac {f (3) ^ {2} -f (1) f (9)} {f (1) ^ {3}}}}$	14	${ displaystyle { frac {2f (2) f (7) -f (1) f (14)} {f (1) ^ {3}}}}$
5	${ displaystyle - { frac {f (5)} {f (1) ^ {2}}}}$	10	${ displaystyle { frac {2f (2) f (5) -f (1) f (10)} {f (1) ^ {3}}}}$	15	${ displaystyle { frac {2f (3) f (5) -f (1) f (15)} {f (1) ^ {3}}}}$
6	${ displaystyle { frac {2f (2) f (3) -f (1) f (6)} {f (1) ^ {3}}}}$	11	${ displaystyle - { frac {f (11)} {f (1) ^ {2}}}}$	16	${ displaystyle { frac {f (2) ^ {4}} {f (1) ^ {5}}} - { frac {3f (4) f (2) ^ {2}} {f (1) ^ {4}}} + { frac {f (4) ^ {2} + 2f (2) f (8)} {f (1) ^ {3}}} - { frac {f (16)} {f (1) ^ {2}}}}$

Nechat ${ displaystyle p_ {k} (n): = p (n-k)}$ kde p je Funkce rozdělení (teorie čísel). Pak existuje další výraz pro Dirichletovu inverzi daný z hlediska výše uvedených funkcí a koeficientů q-Pochhammerův symbol pro ${ displaystyle n> 1}$ dána ^[8]

${ displaystyle f ^ {- 1} (n) = součet _ {k = 1} ^ {n} left [(p_ {k} ast mu) (n) + (p_ {k} ast D_ {f} ast mu) (n) right] times [q ^ {k-1}] { frac {(q; q) _ { infty}} {1-q}}.}$

Varianty součtů nad aritmetickými funkcemi

Tato sekce potřebuje expanzi s: Prosáknout. 14 knihy Apoštola. Můžete pomoci přidávat k tomu. (Dubna 2018)

Viz také

• Shrnutí
• Bell série
• Seznam matematické řady

Poznámky

Reference

• Apostol, T. (1976). Úvod do teorie analytických čísel. New York: Springer. ISBN  0-387-90163-9.
• Digitální knihovna matematických funkcí (DLMF). NIST. 2018. Citováno 24. dubna 2018.
• Tao, Terrence. „Dirichletova konvoluce: Co je nového?“.