Тождества суммы делителей - Divisor sum identities

Цель этой страницы - каталогизировать новые, интересные и полезные личности, связанные с теоретико-числовой суммы дивизоров, т. е. суммы арифметическая функция над делителями натурального числа ${ displaystyle n}$ , или эквивалентно Свертка Дирихле арифметической функции ${ Displaystyle f (п)}$ с одним:

{ displaystyle g (n): = sum _ {d mid n} f (d).}

Эти тождества включают приложения к суммам арифметической функции только по собственным простым делителям числа ${ displaystyle n}$ . Мы также определяем периодический варианты этих сумм дивизоров относительно наибольший общий делитель функция в виде

{ displaystyle g_ {m} (n): = sum _ {d mid (m, n)} f (d), 1 leq m leq n}

Известные соотношения инверсии, которые позволяют функции ${ Displaystyle f (п)}$ быть выраженным в терминах ${ Displaystyle г (п)}$ предоставляются Формула обращения Мебиуса. Естественно, некоторые из наиболее интересных примеров таких тождеств возникают при рассмотрении сумматорные функции среднего порядка над арифметической функцией ${ Displaystyle f (п)}$ определяется как сумма делителей другой арифметической функции ${ Displaystyle г (п)}$ . Для частных примеров сумм дивизоров, включающих специальные арифметические функции и специальные Свёртки Дирихле арифметических функций можно найти на следующих страницах: здесь, здесь, здесь, здесь, и здесь.

Идентификаторы средней суммы заказа

Обмен тождествами суммирования

Следующие личности являются основной мотивацией для создания этой страницы тем. Эти идентификаторы не кажутся хорошо известными или, по крайней мере, хорошо задокументированными, и являются чрезвычайно полезными инструментами, которые могут быть под рукой в некоторых приложениях. В дальнейшем мы считаем, что ${ displaystyle f, g, h, u, v: mathbb {N} rightarrow mathbb {C}}$ какие-либо предписанные арифметические функции и это ${ Displaystyle G (х): = сумма _ {п Leq x} г (п)}$ обозначает сумматорную функцию ${ Displaystyle г (п)}$ . Ниже приводится более частый частный случай первого суммирования. здесь.^[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 (нк)}$
${ displaystyle { begin {align} 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} } right) end {выровнен}}}$
${ 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 )}$
${ 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}}}$
${ displaystyle sum _ {m = 1} ^ {x} left ( sum _ {d mid (m, x)} f (d) g left ({ frac {x} {d}} right) right) t ^ {m} = (t ^ {x} -1) cdot sum _ {d mid x} { frac {t ^ {d} f (d)} {t ^ {d } -1}} g left ({ frac {x} {d}} right)}$

Как правило, эти идентичности собираются из так называемых "раритеты и би-сайды"как хорошо зарекомендовавших себя, так и полу неясных аналитическая теория чисел примечания и методы, а также документы и работы авторов. Сами тождества доказать несложно и представляют собой упражнение в стандартных манипуляциях с обращением рядов и суммами делителей. Поэтому здесь мы опускаем их доказательства.

Метод свертки

В метод свертки - это общий метод оценки сумм средних заказов вида

{ Displaystyle сумма _ {п Leq x} е (п) qquad { text {или}} qquad sum _ { stackrel {q leq x} {q { text {squarefree}}}} f (q),}

где мультипликативная функция ж можно записать в виде свертки вида ${ Displaystyle е (п) = (и аст v) (п)}$ для подходящих, определяемых применением арифметические функции ты и v. Краткий обзор этого метода можно найти здесь.

Суммы периодических делителей

An арифметическая функция является периодический (mod k), или же k-периодический, если ${ Displaystyle е (п + к) = е (п)}$ для всех ${ Displaystyle п в mathbb {N}}$ . Конкретные примеры k-периодическими функциями теории чисел являются Персонажи Дирихле ${ Displaystyle е (п) = чи (п)}$ по модулю k и наибольший общий делитель функция ${ Displaystyle е (п) = (п, к)}$ . Известно, что каждый k-периодическая арифметическая функция имеет представление в виде конечный дискретный Ряд Фурье формы

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

где Коэффициенты Фурье ${ displaystyle a_ {k} (м)}$ определены следующим уравнением, также k-периодический:

{ displaystyle a_ {k} (m) = { frac {1} {k}} sum _ {n = 1} ^ {k} f (n) e left (- { frac {mn} {k }}верно).}

Нас интересуют следующие k-периодические суммы делителей:

{ 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).}

Фактически, коэффициенты Фурье этих вариантов суммы делителей даются формулой ^[2]

{ displaystyle a_ {k} (m) = sum _ {d mid (m, k)} g (d) f left ({ frac {k} {d}} right) { frac {d } {k}}.}

Преобразования Фурье НОД

Мы также можем выразить коэффициенты Фурье в уравнении непосредственно выше через преобразование Фурье любой функции час на входе ${ displaystyle operatorname {gcd} (n, k)}$ используя следующий результат, где ${ Displaystyle c_ {q} (п)}$ это Рамануджанская сумма (ср. Преобразование Фурье тотент-функции ):^[3]

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

Таким образом, объединяя приведенные выше результаты, получаем, что

{ displaystyle a_ {k} (m) = sum _ {d mid (m, k)} g (d) f left ({ frac {k} {d}} right) { frac {d } {k}} = sum _ {d mid k} sum _ {r mid d} f (r) g (d) c _ { frac {d} {r}} (m).}

Суммы по простым делителям

Пусть функция ${ Displaystyle а (п)}$ обозначить характеристическая функция из простые числа, т.е. ${ Displaystyle а (п) = 1}$ если и только если ${ displaystyle n}$ простое и равнозначное в противном случае. Тогда как частный случай первого тождества в уравнении (1) в разделе обмен тождествами суммирования выше можно выразить среднюю сумму заказа

{ 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.}

У нас также есть интегральная формула, основанная на Суммирование Абеля для сумм вида ^[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 приблизительно { frac {xf (x)} { log x}} - int _ {2} ^ {x} { frac {t} { log t}} f ^ { prime} (t) dt,}

куда ${ displaystyle pi (x) sim { frac {x} { log x}}}$ обозначает функция подсчета простых чисел. Здесь обычно предполагается, что функция ж является непрерывный и дифференцируемый.

Некоторые менее ценные тождества суммы делителей

Имеются следующие формулы суммы дивизоров для ж любая арифметическая функция и грамм полностью мультипликативный куда ${ Displaystyle varphi (п)}$ является Функция Эйлера и ${ Displaystyle му (п)}$ это Функция Мёбиуса:^[5]^[6]

${ displaystyle sum _ {d mid n} f (d) varphi left ({ frac {n} {d}} right) = sum _ {k = 1} ^ {n} f ( имя оператора {gcd} (n, k))}$
${ displaystyle sum _ {d mid n} mu (d) f (d) = prod _ { stackrel {p mid n} {p { text {prime}}}} (1-f ( п))}$
${ Displaystyle е (м) е (п) = сумма _ {д середина (м, п)} г (д) е влево ({ гидроразрыва {mn} {d ^ {2}}} вправо) .}$
Если ж является полностью мультипликативный то поточечное умножение ${ displaystyle cdot}$ со сверткой Дирихле дает ${ Displaystyle е CDOT (г АСТ ч) = (е CDOT г) АСТ (е CDOT ч)}$ .
${ displaystyle sum _ {d ^ {k} mid n} mu (d) = { Biggl {} { begin {array} {ll} 0, & { text {if}} m ^ { k} mid n { text {для некоторых}} m> 1; 1, & { text {в противном случае.}} end {array}}}$
Если ${ Displaystyle м geq 1}$ и п имеет более чем м различные простые множители, тогда ${ displaystyle sum _ {d mid n} mu (d) log ^ {m} (d) = 0.}$

Обращение Дирихле к арифметической функции

Мы принимаем обозначения, что ${ Displaystyle varepsilon (п) = дельта _ {п, 1}}$ обозначает мультипликативную единицу свертки Дирихле, так что ${ Displaystyle ( varepsilon ast f) (n) = (f ast varepsilon) (n) = f (n)}$ для любой арифметической функции ж и ${ Displaystyle п geq 1}$ . В Обратный Дирихле функции ж удовлетворяет ${ Displaystyle (е аст е ^ {- 1}) (п) = (е ^ {- 1} аст е) (п) = varepsilon (п)}$ для всех ${ Displaystyle п geq 1}$ . Существует хорошо известная формула рекурсивной свертки для вычисления Обратный Дирихле ${ displaystyle f ^ {- 1} (п)}$ функции ж по индукции в виде ^[7]

{ displaystyle f ^ {- 1} (n) = { Biggl {} { begin {array} {ll} { frac {1} {f (1)}}, & { text {if}} n = 1; - { frac {1} {f (1)}} sum _ { stackrel {d mid n} {d> 1}} f (d) f ^ {- 1} left ({ frac {n} {d}} right), & { text {if}} n> 1. end {array}}}

Для фиксированной функции ж, пусть функция ${ 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}}}$

Затем определите следующие два варианта множественной или вложенной свертки для любой фиксированной арифметической функции. ж:

{ displaystyle { begin {align} { 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 { array} {ll} f _ { pm} (n), & { text {if}} j = 1; sum limits _ { stackrel {d mid n} {d> 1}} f ( г) operatorname {ds} _ {j-1, f} (n / d), & { text {if}} j> 1. end {array}} end {align}}}

Функция ${ Displaystyle D_ {f} (п)}$ эквивалентной парой формул суммирования в следующем уравнении тесно связано с Обратный Дирихле для произвольной функции ж.^[8]

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

В частности, мы можем доказать, что ^[9]

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

Таблица значений ${ Displaystyle D_ {f} (п)}$ за ${ Displaystyle 2 Leq п Leq 16}$ появляется ниже. Эта таблица уточняет предполагаемое значение и интерпретацию этой функции как знаковую сумму всех возможных множественных k-свертки функции ж с собой.

п	${ Displaystyle D_ {f} (п)}$	п	${ Displaystyle D_ {f} (п)}$	п	${ Displaystyle D_ {f} (п)}$
2	${ Displaystyle - { гидроразрыва {е (2)} {е (1) ^ {2}}}}$	7	${ Displaystyle - { гидроразрыва {е (7)} {е (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 { гидроразрыва {е (2) ^ {2} -f (1) е (4)} {е (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 - { гидроразрыва {е (5)} {е (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}}}}$

Позволять ${ displaystyle p_ {k} (n): = p (n-k)}$ куда п это Функция распределения (теория чисел). Тогда есть еще одно выражение для обратной функции Дирихле, выраженное через указанные выше функции и коэффициенты символ q-Pochhammer за ${ displaystyle n> 1}$ данный ^[8]

{ displaystyle f ^ {- 1} (n) = sum _ {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}}.}.}

Варианты сумм по арифметическим функциям

Смотрите также

Примечания

^ См. Также Раздел 3.10 Апостола.
^ Раздел 27.10 в Справочник NIST по математическим функциям (DLMF).
^ Шрамм, В. (2008). «Преобразование Фурье функций наибольших общих делителей». Целые числа. 8.
^ См. Раздел 2.2 в Вильярино, М. Б. (2005). «Доказательство Мертенса теоремы Мертенса». arXiv:математика / 0504289.
^ В соответствующем порядке из книги Апостола: упражнение 2.29, теорема 2.18 и упражнения 2.31–2.32.
^ Первая личность имеет хорошо известную Серия Дирихле формы ${ displaystyle sum _ {n geq 1} { frac {1} {n ^ {s}}} sum _ {k = 1} ^ {n} f ( operatorname {gcd} (n, k) ) = { frac { zeta (s-1)} { zeta (s)}} sum _ {n geq 1} { frac {f (n)} {n ^ {s}}}}$ каталогизирован в Гулд, Генри В .; Шонива, Темба (2008). «Каталог интересных серий Дирихле». Мисс J. Math. Наука. 20 (1). Архивировано из оригинал на 2011-10-02.
^ См. Доказательство в разделе 2.7 книги Апостола.
^ ^а ^б М. Мерка и М. Д. Шмидт (2017). "Факторизационные теоремы для обобщенных рядов Ламберта и приложений". С. 13–20. arXiv:1712.00611 [math.NT ].
^ Эта идентичность подтверждается в неопубликованной рукописи М. Д. Шмидта, которая появится на ArXiv в 2018 году.