Тождества суммы делителей

В этой статье есть несколько проблем. Помогите улучшить ее или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти сообщения ) В статье содержится список общих ссылок , но в ней отсутствуют соответствующие встроенные цитаты . Please help to improve this article by introducing more precise citations. (April 2018) (Learn how and when to remove this message) The article's lead section may need to be rewritten. The reason given is: Lead section need to rewrite - Pls see MOS:LEAD. Please help improve the lead and read the lead layout guide. (April 2018) (Learn how and when to remove this message) (Learn how and when to remove this message)

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

${\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(n)}$${\displaystyle g(n)}$${\displaystyle f(n)}$${\displaystyle g(n)}$

Следующие тождества являются основной мотивацией для создания этой страницы тем. Эти тождества, по-видимому, не являются общеизвестными или, по крайней мере, хорошо документированными, и являются чрезвычайно полезными инструментами, которые нужно иметь под рукой в ​​некоторых приложениях. В дальнейшем мы считаем, что являются любыми предписанными арифметическими функциями и что обозначает сумматорную функцию . Более распространенный частный случай первого суммирования ниже упоминается здесь . ^[1]${\displaystyle f,g,h,u,v:\mathbb {N} \rightarrow \mathbb {C} }$${\textstyle G(x):=\sum _{n\leq x}g(n)}$${\displaystyle g(n)}$

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}\sum _{d\mid n}f(d)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{aligned}}}$
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}}\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)}$

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

Метод свертки — это общий метод оценки средних порядковых сумм вида

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

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

Связанный метод — использование формулы

${\displaystyle \sum _{k=1}^{n}f(k)=\sum _{k=1}^{n}\sum _{xy=k}^{}g(x)h(y)=\sum _{x=1}^{a}\sum _{y=1}^{n/x}g(x)h(y)+\sum _{y=1}^{b}\sum _{x=1}^{n/y}g(x)h(y)-\sum _{x=1}^{a}\sum _{y=1}^{b}g(x)h(y);}$

это известно как метод гиперболы Дирихле .

Арифметическая функция является периодической (mod k) или k -периодической, если для всех . Конкретными примерами k -периодических функций теории чисел являются характеры Дирихле по модулю k и функция наибольшего общего делителя . Известно, что каждая k -периодическая арифметическая функция имеет представление в виде конечного дискретного ряда Фурье вида${\displaystyle f(n+k)=f(n)}$${\displaystyle n\in \mathbb {N} }$ ${\displaystyle f(n)=\chi (n)}$${\displaystyle f(n)=(n,k)}$

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

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

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

Нас интересуют следующие 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}}.}$

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

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

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

${\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\approx {\frac {xf(x)}{\log x}}-\int _{2}^{x}{\frac {t}{\log t}}f^{\prime }(t)dt,}$

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

Имеем следующие формулы суммы делителей для любой арифметической функции f и полностью мультипликативной функции g , где — функция Эйлера , а — функция Мёбиуса : ^{[5] [6]}${\displaystyle \varphi (n)}$${\displaystyle \mu (n)}$

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)=\sum _{d\mid (m,n)}g(d)f\left({\frac {mn}{d^{2}}}\right).}$
4. Если f полностью мультипликативна , то поточечное умножение со сверткой Дирихле дает .${\displaystyle \cdot }$${\displaystyle f\cdot (g\ast h)=(f\cdot g)\ast (f\cdot h)}$
5. ${\displaystyle \sum _{d^{k}\mid n}\mu (d)={\Biggl \{}{\begin{array}{ll}0,&{\text{ if }}m^{k}\mid n{\text{ for some }}m>1;\\1,&{\text{otherwise.}}\end{array}}}$
6. Если и n имеет более m различных простых множителей , то${\displaystyle m\geq 1}$ ${\displaystyle \sum _{d\mid n}\mu (d)\log ^{m}(d)=0.}$

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

${\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}}}$

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

Далее определим следующие два варианта множественной, или вложенной, свертки для любой фиксированной арифметической функции 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{array}{ll}f_{\pm }(n),&{\text{ if }}j=1;\\\sum \limits _{\stackrel {d\mid n}{d>1}}f(d)\operatorname {ds} _{j-1,f}(n/d),&{\text{ if }}j>1.\end{array}}\end{aligned}}}$

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

${\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)^{i+1}{\widetilde {\operatorname {ds} }}_{i+1,f}(n)}$

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

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

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

н	${\displaystyle D_{f}(n)}$	н	${\displaystyle D_{f}(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}}}}$

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

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

This section needs expansion with: See p. 14 of Apostol's book. You can help by adding to it. (April 2018)

• Суммирование
• Серия колоколов
• Список математических рядов

• Апостол, Т. (1976). Введение в аналитическую теорию чисел . Нью-Йорк: Springer. ISBN 0-387-90163-9.
• Цифровая библиотека математических функций (DLMF). NIST. 2018. Получено 24 апреля 2018 г.
• Тао, Терренс. «Свёртка Дирихле: что нового?».