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

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

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

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

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

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

Тождества средней суммы заказа

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

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

1. $\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. ${\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. $\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. $\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. $\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-сторон » как хорошо известных, так и малоизвестных заметок и методов аналитической теории чисел , а также статей и работ авторов. Сами тождества доказать несложно, и они представляют собой упражнение в стандартных манипуляциях с обращением рядов и суммами делителей. Поэтому мы опускаем здесь их доказательства.

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

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

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

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

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

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

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

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

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

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

$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).$

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

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

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

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

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

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

$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).$

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

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

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

У нас также есть интегральная формула, основанная на суммировании Абеля для сумм вида

$\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,$

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

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

У нас есть следующие формулы суммы делителей для f любой арифметической функции g и полностью мультипликативной , где $\varphi (n)$ - это полная функция Эйлера и $\mu (n)$ это функция Мёбиуса :

1. $\sum _{d\mid n}f(d)\varphi \left({\frac {n}{d}}\right)=\sum _{k=1}^{n}f(\operatorname {gcd} (n,k))$
2. $\sum _{d\mid n}\mu (d)f(d)=\prod _{\stackrel {p\mid n}{p{\text{ prime}}}}(1-f(p))$
3. $f(m)f(n)=\sum _{d\mid (m,n)}g(d)f\left({\frac {mn}{d^{2}}}\right).$
4. Если f то вполне мультипликативна, поточечное умножение $\cdot$ со сверткой Дирихле дает $f\cdot (g\ast h)=(f\cdot g)\ast (f\cdot h)$.
5. $\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. Если $m\geq 1$ и n имеет более чем m различных простых делителей , то $\sum _{d\mid n}\mu (d)\log ^{m}(d)=0.$

Обратная арифметическая функция Дирихле.

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

$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 пусть функция $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 :

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

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

$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)$

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

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

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

н	$D_{f}(n)$	н	$D_{f}(n)$	н	$D_{f}(n)$
2	$-{\frac {f(2)}{f(1)^{2}}}$	7	$-{\frac {f(7)}{f(1)^{2}}}$	12	${\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	$-{\frac {f(3)}{f(1)^{2}}}$	8	${\frac {2f(2)f(4)-f(1)f(8)}{f(1)^{3}}}-{\frac {f(2)^{3}}{f(1)^{4}}}$	13	$-{\frac {f(13)}{f(1)^{2}}}$
4	${\frac {f(2)^{2}-f(1)f(4)}{f(1)^{3}}}$	9	${\frac {f(3)^{2}-f(1)f(9)}{f(1)^{3}}}$	14	${\frac {2f(2)f(7)-f(1)f(14)}{f(1)^{3}}}$
5	$-{\frac {f(5)}{f(1)^{2}}}$	10	${\frac {2f(2)f(5)-f(1)f(10)}{f(1)^{3}}}$	15	${\frac {2f(3)f(5)-f(1)f(15)}{f(1)^{3}}}$
6	${\frac {2f(2)f(3)-f(1)f(6)}{f(1)^{3}}}$	11	$-{\frac {f(11)}{f(1)^{2}}}$	16	${\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_{k}(n):=p(n-k)$ где p — статистическая сумма (теория чисел) . Тогда существует другое выражение для обратного Дирихле, заданное через приведенные выше функции и коэффициенты символа q-Похгаммера для $n>1$ данный

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

См. также

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

Ссылки

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