Арифметическая функция

Функция, областью определения которой являются положительные целые числа

В теории чисел арифметическая , арифметическая или теоретико-числовая функция ^{[1] [2] — это} , как правило, любая функция f ( n ), областью определения которой являются положительные целые числа , а областью значений — подмножество комплексных чисел . [ ^{3] [4] [5]} Харди и Райт включают в свое определение требование, чтобы арифметическая функция «выражала некоторое арифметическое свойство n ». ^[6] Существует более широкий класс теоретико-числовых функций, которые не соответствуют этому определению, например, функции подсчета простых чисел . В этой статье приводятся ссылки на функции обоих классов.

Примером арифметической функции является функция делителя , значение которой при положительном целом числе n равно количеству делителей числа n .

Арифметические функции часто крайне нерегулярны (см. таблицу), но некоторые из них имеют разложения в ряды по сумме Рамануджана .

Мультипликативные и аддитивные функции

Арифметическая функция a — это

• полностью аддитивно , если a ( mn ) = a ( m ) + a ( n ) для всех натуральных чисел m и n ;
• полностью мультипликативно , если a ( mn ) = a ( m ) a ( n ) для всех натуральных чисел m и n ;

Два целых числа m и n называются взаимно простыми, если их наибольший общий делитель равен 1, то есть если не существует простого числа , которое делит их оба.

Тогда арифметическая функция a равна

• аддитивным , если a ( mn ) = a ( m ) + a ( n ) для всех взаимно простых натуральных чисел m и n ;
• мультипликативным , если a ( mn ) = a ( m ) a ( n ) для всех взаимно простых натуральных чисел m и n .

Обозначение

В этой статье и означает, что сумма или произведение берется по всем простым числам : и Аналогично, и означает, что сумма или произведение берется по всем степеням простых чисел со строго положительным показателем (поэтому k = 0 не включено): ${\textstyle \sum _{p}f(p)}$ ${\textstyle \prod _{p}f(p)}$ $${\displaystyle \sum _{p}f(p)=f(2)+f(3)+f(5)+\cdots }$$ $${\displaystyle \prod _{p}f(p)=f(2)f(3)f(5)\cdots .}$$ ${\textstyle \sum _{p^{k}}f(p^{k})}$ ${\textstyle \prod _{p^{k}}f(p^{k})}$ $${\displaystyle \sum _{p^{k}}f(p^{k})=\sum _{p}\sum _{k>0}f(p^{k})=f(2)+f(3)+f(4)+f(5)+f(7)+f(8)+f(9)+\cdots .}$$

Обозначения и означают, что сумма или произведение берется по всем положительным делителям n , включая 1 и n . Например, если n = 12 , то ${\textstyle \sum _{d\mid n}f(d)}$ ${\textstyle \prod _{d\mid n}f(d)}$ $${\displaystyle \prod _{d\mid 12}f(d)=f(1)f(2)f(3)f(4)f(6)f(12).}$$

Обозначения можно комбинировать: и означают, что сумма или произведение берется по всем простым делителям n . Например, если n = 18, то и аналогично и означают, что сумма или произведение берется по всем простым степеням, делящим n . Например, если n = 24, то ${\textstyle \sum _{p\mid n}f(p)}$ ${\textstyle \prod _{p\mid n}f(p)}$ $${\displaystyle \sum _{p\mid 18}f(p)=f(2)+f(3),}$$ ${\textstyle \sum _{p^{k}\mid n}f(p^{k})}$ ${\textstyle \prod _{p^{k}\mid n}f(p^{k})}$ $${\displaystyle \prod _{p^{k}\mid 24}f(p^{k})=f(2)f(3)f(4)f(8).}$$

Ω(н),ω(н),νп(н) – разложение на простые степени

Основная теорема арифметики гласит, что любое положительное целое число n может быть представлено единственным образом в виде произведения степеней простых чисел: где p ₁ < p ₂ < ... < p _k — простые числа, а a _j — положительные целые числа. (1 задается пустым произведением.) ${\displaystyle n=p_{1}^{a_{1}}\cdots p_{k}^{a_{k}}}$

Часто удобно записывать это как бесконечное произведение по всем простым числам, где все, кроме конечного числа, имеют нулевую экспоненту. Определим p -адическую оценку ν _p ( n ) как экспоненту наивысшей степени простого числа p , которая делит n . То есть, если p является одним из p _{i ,} то ν _p ( n ) = a _i , в противном случае она равна нулю. Тогда $${\displaystyle n=\prod _{p}p^{\nu _{p}(n)}.}$$

В терминах вышеизложенного простые омега-функции ω и Ω определяются как

ω ( n ) = k ,

Ω( п ) знак равно а ₁ + а ₂ + ... + а _k .

Чтобы избежать повторений, по возможности формулы для функций, перечисленных в этой статье, приводятся через n и соответствующие им p _i , a _i , ω и Ω.

Мультипликативные функции

σк(н), τ(н),г(н) – суммы делителей

σ _k ( n ) — сумма k -х степеней положительных делителей числа n , включая 1 и n , где k — комплексное число.

σ ₁ ( n ) , сумма (положительных) делителей числа n , обычно обозначается как σ( n ) .

Поскольку положительное число в нулевой степени равно единице, то σ ₀ ( n ) — это число (положительных) делителей числа n ; обычно его обозначают как d ( n ) или τ( n ) (от немецкого Teiler = делители).

$${\displaystyle \sigma _{k}(n)=\prod _{i=1}^{\omega (n)}{\frac {p_{i}^{(a_{i}+1)k}-1}{p_{i}^{k}-1}}=\prod _{i=1}^{\omega (n)}\left(1+p_{i}^{k}+p_{i}^{2k}+\cdots +p_{i}^{a_{i}k}\right).}$$

Установка k = 0 во втором произведении дает $${\displaystyle \tau (n)=d(n)=(1+a_{1})(1+a_{2})\cdots (1+a_{\omega (n)}).}$$

φ(н) – функция Эйлера

φ( n ) , функция Эйлера, представляет собой количество положительных целых чисел, не превышающих n , которые взаимно просты с n .

$${\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)=n\left({\frac {p_{1}-1}{p_{1}}}\right)\left({\frac {p_{2}-1}{p_{2}}}\right)\cdots \left({\frac {p_{\omega (n)}-1}{p_{\omega (n)}}}\right).}$$

Дж.к(н) – функция Жордана тотиента

J _k ( n ) , функция тотиента Жордана, представляет собой число k -кортежей положительных целых чисел, все из которых меньше или равны n , которые образуют взаимно простой ( k + 1)-кортеж вместе с n . Это обобщение тотиента Эйлера, φ( n ) = J ₁ ( n ) . $${\displaystyle J_{k}(n)=n^{k}\prod _{p\mid n}\left(1-{\frac {1}{p^{k}}}\right)=n^{k}\left({\frac {p_{1}^{k}-1}{p_{1}^{k}}}\right)\left({\frac {p_{2}^{k}-1}{p_{2}^{k}}}\right)\cdots \left({\frac {p_{\omega (n)}^{k}-1}{p_{\omega (n)}^{k}}}\right).}$$

μ(н) – Функция Мёбиуса

μ( n ) , функция Мёбиуса, важна из-за формулы обращения Мёбиуса . См. свёртку Дирихле ниже.

$${\displaystyle \mu (n)={\begin{cases}(-1)^{\omega (n)}=(-1)^{\Omega (n)}&{\text{if }}\;\omega (n)=\Omega (n)\\0&{\text{if }}\;\omega (n)\neq \Omega (n).\end{cases}}}$$

Это означает, что μ(1) = 1. (Поскольку Ω(1) = ω(1) = 0.)

τ(н) – функция тау Рамануджана

τ( n ) , тау-функция Рамануджана, определяется ее производящей функцией :

$${\displaystyle \sum _{n\geq 1}\tau (n)q^{n}=q\prod _{n\geq 1}(1-q^{n})^{24}.}$$

Хотя трудно сказать, какое именно «арифметическое свойство n » оно «выражает», ^[7] ( τ ( n ) равно (2π) ⁻¹² раз больше n- го коэффициента Фурье в q-разложении модульной дискриминантной функции) ^[8] оно включено в число арифметических функций, поскольку оно мультипликативно и встречается в тождествах, включающих определенные функции σ _k ( n ) и r _k ( n ) (потому что они также являются коэффициентами в разложении модульных форм ).

сд(н) – сумма Рамануджана

c _q ( n ) , сумма Рамануджана, представляет собой суммуn-х степеней примитивныхq-й степенииз единицы: $${\displaystyle c_{q}(n)=\sum _{\stackrel {1\leq a\leq q}{\gcd(a,q)=1}}e^{2\pi i{\tfrac {a}{q}}n}.}$$

Хотя он определен как сумма комплексных чисел (иррациональных для большинства значений q ), он является целым числом. Для фиксированного значения n он мультипликативен по q :

Если q и r взаимно просты , то ${\displaystyle c_{q}(n)c_{r}(n)=c_{qr}(n).}$

ψ(н) - пси-функция Дедекинда

Пси-функция Дедекинда , используемая в теории модулярных функций , определяется формулой $${\displaystyle \psi (n)=n\prod _{p|n}\left(1+{\frac {1}{p}}\right).}$$

Полностью мультипликативные функции

λ(н) – Функция Лиувилля

λ ( n ) , функция Лиувилля, определяется как $${\displaystyle \lambda (n)=(-1)^{\Omega (n)}.}$$

χ(н) – персонажи

Все характеры Дирихле χ ( n ) полностью мультипликативны. Два характера имеют специальные обозначения:

Главный характер (mod n ) обозначается χ ₀ ( a ) (или χ ₁ ( a )). Он определяется как $${\displaystyle \chi _{0}(a)={\begin{cases}1&{\text{if }}\gcd(a,n)=1,\\0&{\text{if }}\gcd(a,n)\neq 1.\end{cases}}}$$

Квадратичный характер (mod n ) обозначается символом Якоби для нечетных n (он не определен для четных n ): $${\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{a_{1}}\left({\frac {a}{p_{2}}}\right)^{a_{2}}\cdots \left({\frac {a}{p_{\omega (n)}}}\right)^{a_{\omega (n)}}.}$$

В этой формуле есть символ Лежандра , определенный для всех целых чисел a и всех нечетных простых чисел p как ${\displaystyle ({\tfrac {a}{p}})}$ $${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0&{\text{if }}a\equiv 0{\pmod {p}},\\+1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and for some integer }}x,\;a\equiv x^{2}{\pmod {p}}\\-1&{\text{if there is no such }}x.\end{cases}}}$$

Следуя обычной традиции для пустого продукта, ${\displaystyle \left({\frac {a}{1}}\right)=1.}$

Аддитивные функции

ω(н) – различные простые делители

ω( n ) , определенное выше как число различных простых чисел, делящих n , является аддитивным (см. Функция омега-простого числа ).

Полностью аддитивные функции

Ω(н) – простые делители

Ω( n ) , определенная выше как число простых множителей числа n с учетом кратностей, является полностью аддитивной (см. Функция омега-простого числа ).

νп(н) –p- адическая оценкацелого числан

Для фиксированного простого числа p , ν _p ( n ) , определенное выше как показатель наибольшей степени числа p, делящей n , является полностью аддитивным.

Логарифмическая производная

${\displaystyle \operatorname {ld} (n)={\frac {D(n)}{n}}=\sum _{\stackrel {p\mid n}{p{\text{ prime}}}}{\frac {v_{p}(n)}{p}}}$, где — арифметическая производная. ${\displaystyle D(n)}$

Ни мультипликативный, ни аддитивный

π(х), П(х),θ(х),ψ(х) – функции подсчета простых чисел

Эти важные функции (которые не являются арифметическими функциями) определены для неотрицательных действительных аргументов и используются в различных утверждениях и доказательствах теоремы о простых числах . Они являются функциями суммирования (см. основной раздел чуть ниже) арифметических функций, которые не являются ни мультипликативными, ни аддитивными.

π ( x ) , функция подсчета простых чисел, есть количество простых чисел, не превосходящихx. Это функция суммирования характеристическойфункциипростых чисел. $${\displaystyle \pi (x)=\sum _{p\leq x}1}$$

Связанная функция подсчитывает степени простых чисел с весом 1 для простых чисел, 1/2 для их квадратов, 1/3 для кубов, ... Это функция суммирования арифметической функции, которая принимает значение 1/ k для целых чисел, которые являются k-й степенью некоторого простого числа, и значение 0 для других целых чисел.

$${\displaystyle \Pi (x)=\sum _{p^{k}\leq x}{\frac {1}{k}}.}$$

θ ( x ) и ψ ( x ), функции Чебышёва, определяются как суммы натуральных логарифмов простых чисел, не превосходящихx. $${\displaystyle \vartheta (x)=\sum _{p\leq x}\log p,}$$ $${\displaystyle \psi (x)=\sum _{p^{k}\leq x}\log p.}$$

Функция Чебышева ψ ( x ) является суммирующей функцией функции Мангольдта, представленной ниже.

Λ(н) – функция фон Мангольдта

Λ( n ) , функция фон Мангольдта, равна 0, если только аргумент n не является степенью простого числа p ^k , в этом случае он является натуральным логарифмом простого числа p : $${\displaystyle \Lambda (n)={\begin{cases}\log p&{\text{if }}n=2,3,4,5,7,8,9,11,13,16,\ldots =p^{k}{\text{ is a prime power}}\\0&{\text{if }}n=1,6,10,12,14,15,18,20,21,\dots \;\;\;\;{\text{ is not a prime power}}.\end{cases}}}$$

п(н) – функция распределения

p ( n ) , функция распределения, представляет собой число способов представленияnв виде суммы положительных целых чисел, где два представления с одинаковыми слагаемыми в разном порядке не считаются различными: $${\displaystyle p(n)=\left|\left\{(a_{1},a_{2},\dots a_{k}):0<a_{1}\leq a_{2}\leq \cdots \leq a_{k}\;\land \;n=a_{1}+a_{2}+\cdots +a_{k}\right\}\right|.}$$

λ(н) – Функция Кармайкла

λ ( n ) , функция Кармайкла, является наименьшим положительным числом, таким что   для всехaвзаимно просто сn. Эквивалентно, этонаименьшее общее кратноепорядков элементовмультипликативной группы целых чисел по модулю n . ${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$

Для степеней нечетных простых чисел, а также для 2 и 4, λ ( n ) равно функции Эйлера n ; для степеней 2 больше 4 оно равно половине функции Эйлера n : а для общего n оно равно наименьшему общему кратному λ каждого из множителей степени простого числа n : $${\displaystyle \lambda (n)={\begin{cases}\;\;\phi (n)&{\text{if }}n=2,3,4,5,7,9,11,13,17,19,23,25,27,\dots \\{\tfrac {1}{2}}\phi (n)&{\text{if }}n=8,16,32,64,\dots \end{cases}}}$$ $${\displaystyle \lambda (p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{\omega (n)}^{a_{\omega (n)}})=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})].}$$

час(н) – Номер класса

h ( n ) , функция числа классов, является порядкомидеальной группы классовалгебраического расширения рациональных чисел сдискриминантом n. Обозначение неоднозначно, так как в общем случае существует много расширений с одним и тем же дискриминантом. См.квадратичное полеициклотомическое поледля классических примеров.

гк(н) – Суммакквадраты

r _k ( n ) — это количество способовпредставленияnkквадратов, где представления, отличающиеся только порядком слагаемых или знаками квадратных корней, считаются различными.

$${\displaystyle r_{k}(n)=\left|\left\{(a_{1},a_{2},\dots ,a_{k}):n=a_{1}^{2}+a_{2}^{2}+\cdots +a_{k}^{2}\right\}\right|}$$

Д(н) – Арифметическая производная

Используя обозначение Хевисайда для производной, арифметическая производная D ( n ) представляет собой функцию, такую ​​что

• ${\displaystyle D(n)=1}$если n простое, и
• ${\displaystyle D(mn)=mD(n)+D(m)n}$( правило продукта )

Функции суммирования

Если задана арифметическая функция a ( n ), ее функция суммирования A ( x ) определяется как A можно рассматривать как функцию действительной переменной. Если задано положительное целое число m , A является постоянной вдоль открытых интервалов m < x < m + 1 и имеет скачок непрерывности для каждого целого числа, для которого a ( m ) ≠ 0. $${\displaystyle A(x):=\sum _{n\leq x}a(n).}$$

Поскольку такие функции часто представляются рядами и интегралами, для достижения поточечной сходимости обычно определяют значение на разрывах как среднее значение слева и справа: $${\displaystyle A_{0}(m):={\frac {1}{2}}\left(\sum _{n<m}a(n)+\sum _{n\leq m}a(n)\right)=A(m)-{\frac {1}{2}}a(m).}$$

Отдельные значения арифметических функций могут сильно колебаться – как в большинстве приведенных выше примеров. Функции суммирования «сглаживают» эти колебания. В некоторых случаях может быть возможно найти асимптотическое поведение для функции суммирования при больших x .

Классический пример этого явления ^[9] дается суммирующей функцией делителей , функцией суммирования d ( n ), числа делителей n : $${\displaystyle \liminf _{n\to \infty }d(n)=2}$$ $${\displaystyle \limsup _{n\to \infty }{\frac {\log d(n)\log \log n}{\log n}}=\log 2}$$ $${\displaystyle \lim _{n\to \infty }{\frac {d(1)+d(2)+\cdots +d(n)}{\log(1)+\log(2)+\cdots +\log(n)}}=1.}$$

Средний порядок арифметической функции — это некоторая более простая или лучше понятая функция, которая имеет ту же самую функцию суммирования асимптотически, и, следовательно, принимает те же самые значения «в среднем». Мы говорим, что g — это средний порядок f , если $${\displaystyle \sum _{n\leq x}f(n)\sim \sum _{n\leq x}g(n)}$$

при стремлении x к бесконечности. Приведенный выше пример показывает, что d ( n ) имеет средний порядок log( n ). ^[10]

свертка Дирихле

Дана арифметическая функция a ( n ), пусть Fa ( _s ) , для комплексного s , будет функцией, определяемой соответствующим рядом Дирихле (где он сходится ): ^[11] Fa ( s ) называется производящей функцией a ( n ). Простейший такой ряд, соответствующий постоянной функции a ( n ) = 1 для всех n , есть ζ ( s ) — _дзета -функция Римана . $${\displaystyle F_{a}(s):=\sum _{n=1}^{\infty }{\frac {a(n)}{n^{s}}}.}$$

Производящая функция функции Мёбиуса является обратной функцией дзета-функции: $${\displaystyle \zeta (s)\,\sum _{n=1}^{\infty }{\frac {\mu (n)}{n^{s}}}=1,\;\;\Re s>1.}$$

Рассмотрим две арифметические функции a и b и их соответствующие производящие функции F _a ( s ) и F _b ( s ). Произведение F _a ( s ) F _b ( s ) можно вычислить следующим образом: $${\displaystyle F_{a}(s)F_{b}(s)=\left(\sum _{m=1}^{\infty }{\frac {a(m)}{m^{s}}}\right)\left(\sum _{n=1}^{\infty }{\frac {b(n)}{n^{s}}}\right).}$$

Это простое упражнение, чтобы показать, что если c ( n ) определяется как, то $${\displaystyle c(n):=\sum _{ij=n}a(i)b(j)=\sum _{i\mid n}a(i)b\left({\frac {n}{i}}\right),}$$ $${\displaystyle F_{c}(s)=F_{a}(s)F_{b}(s).}$$

Эта функция c называется сверткой Дирихле a и b и обозначается . ${\displaystyle a*b}$

Особенно важным случаем является свертка с постоянной функцией a ( n ) = 1 для всех n , что соответствует умножению производящей функции на дзета-функцию: $${\displaystyle g(n)=\sum _{d\mid n}f(d).}$$

Умножение на обратную дзета-функцию дает формулу обращения Мёбиуса : $${\displaystyle f(n)=\sum _{d\mid n}\mu \left({\frac {n}{d}}\right)g(d).}$$

Если f мультипликативна, то и g тоже . Если f полностью мультипликативна, то g мультипликативна, но может быть или не быть полностью мультипликативной.

Отношения между функциями

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

Вот несколько примеров:

Свертки Дирихле

${\displaystyle \sum _{\delta \mid n}\mu (\delta )=\sum _{\delta \mid n}\lambda \left({\frac {n}{\delta }}\right)|\mu (\delta )|={\begin{cases}1&{\text{if }}n=1\\0&{\text{if }}n\neq 1\end{cases}}}$     где λ — функция Лиувилля. ^[12]

${\displaystyle \sum _{\delta \mid n}\varphi (\delta )=n.}$      ^[13]

${\displaystyle \varphi (n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\delta =n\sum _{\delta \mid n}{\frac {\mu (\delta )}{\delta }}.}$       Инверсия Мёбиуса

${\displaystyle \sum _{d\mid n}J_{k}(d)=n^{k}.}$      ^[14]

${\displaystyle J_{k}(n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\delta ^{k}=n^{k}\sum _{\delta \mid n}{\frac {\mu (\delta )}{\delta ^{k}}}.}$       Инверсия Мёбиуса

${\displaystyle \sum _{\delta \mid n}\delta ^{s}J_{r}(\delta )J_{s}\left({\frac {n}{\delta }}\right)=J_{r+s}(n)}$      ^[15]

${\displaystyle \sum _{\delta \mid n}\varphi (\delta )d\left({\frac {n}{\delta }}\right)=\sigma (n).}$      ^{[16] [17]}

${\displaystyle \sum _{\delta \mid n}|\mu (\delta )|=2^{\omega (n)}.}$      ^[18]

${\displaystyle |\mu (n)|=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)2^{\omega (\delta )}.}$       Инверсия Мёбиуса

${\displaystyle \sum _{\delta \mid n}2^{\omega (\delta )}=d(n^{2}).}$      

${\displaystyle 2^{\omega (n)}=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)d(\delta ^{2}).}$       Инверсия Мёбиуса

${\displaystyle \sum _{\delta \mid n}d(\delta ^{2})=d^{2}(n).}$      

${\displaystyle d(n^{2})=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)d^{2}(\delta ).}$       Инверсия Мёбиуса

${\displaystyle \sum _{\delta \mid n}d\left({\frac {n}{\delta }}\right)2^{\omega (\delta )}=d^{2}(n).}$      

${\displaystyle \sum _{\delta \mid n}\lambda (\delta )={\begin{cases}&1{\text{ if }}n{\text{ is a square }}\\&0{\text{ if }}n{\text{ is not square.}}\end{cases}}}$     где λ — функция Лиувилля .

${\displaystyle \sum _{\delta \mid n}\Lambda (\delta )=\log n.}$      ^[19]

${\displaystyle \Lambda (n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\log(\delta ).}$       Инверсия Мёбиуса

Суммы квадратов

Для всех     ( теорема Лагранжа о четырех квадратах ). ${\displaystyle k\geq 4,\;\;\;r_{k}(n)>0.}$

${\displaystyle r_{2}(n)=4\sum _{d\mid n}\left({\frac {-4}{d}}\right),}$ ^[20]

где символ Кронекера имеет значения

${\displaystyle \left({\frac {-4}{n}}\right)={\begin{cases}+1&{\text{if }}n\equiv 1{\pmod {4}}\\-1&{\text{if }}n\equiv 3{\pmod {4}}\\\;\;\;0&{\text{if }}n{\text{ is even}}.\\\end{cases}}}$

Формула для r ₃ приведена в разделе о числах классов ниже. где ν = ν ₂ ( n ) .     ^{[21] [22] [23]} $${\displaystyle r_{4}(n)=8\sum _{\stackrel {d\mid n}{4\,\nmid \,d}}d=8(2+(-1)^{n})\sum _{\stackrel {d\mid n}{2\,\nmid \,d}}d={\begin{cases}8\sigma (n)&{\text{if }}n{\text{ is odd }}\\24\sigma \left({\frac {n}{2^{\nu }}}\right)&{\text{if }}n{\text{ is even }}\end{cases}},}$$

$${\displaystyle r_{6}(n)=16\sum _{d\mid n}\chi \left({\frac {n}{d}}\right)d^{2}-4\sum _{d\mid n}\chi (d)d^{2},}$$где ^[24] ${\displaystyle \chi (n)=\left({\frac {-4}{n}}\right).}$

Определим функцию σ _k ^* ( n ) как ^[25] $${\displaystyle \sigma _{k}^{*}(n)=(-1)^{n}\sum _{d\mid n}(-1)^{d}d^{k}={\begin{cases}\sum _{d\mid n}d^{k}=\sigma _{k}(n)&{\text{if }}n{\text{ is odd }}\\\sum _{\stackrel {d\mid n}{2\,\mid \,d}}d^{k}-\sum _{\stackrel {d\mid n}{2\,\nmid \,d}}d^{k}&{\text{if }}n{\text{ is even}}.\end{cases}}}$$

То есть, если n нечетное, то σ _k ^* ( n ) представляет собой сумму k -х степеней делителей числа n , то есть σ _k ( n ), а если n четное, то это сумма k- х степеней четных делителей числа n минус сумма k -х степеней нечетных делителей числа n .

${\displaystyle r_{8}(n)=16\sigma _{3}^{*}(n).}$    ^{[24] [26]}

Примем соглашение, что τ ( x ) Рамануджана = 0 , если x не является целым числом.

${\displaystyle r_{24}(n)={\frac {16}{691}}\sigma _{11}^{*}(n)+{\frac {128}{691}}\left\{(-1)^{n-1}259\tau (n)-512\tau \left({\frac {n}{2}}\right)\right\}}$    ^[27]

Свертки суммы делителя

Здесь «свертка» не означает «свертку Дирихле», а вместо этого относится к формуле для коэффициентов произведения двух степенных рядов :

${\displaystyle \left(\sum _{n=0}^{\infty }a_{n}x^{n}\right)\left(\sum _{n=0}^{\infty }b_{n}x^{n}\right)=\sum _{i=0}^{\infty }\sum _{j=0}^{\infty }a_{i}b_{j}x^{i+j}=\sum _{n=0}^{\infty }\left(\sum _{i=0}^{n}a_{i}b_{n-i}\right)x^{n}=\sum _{n=0}^{\infty }c_{n}x^{n}.}$

Последовательность называется сверткой или произведением Коши последовательностей a _n и b _n . Эти формулы могут быть доказаны аналитически (см. ряд Эйзенштейна ) или элементарными методами. ^[28] ${\displaystyle c_{n}=\sum _{i=0}^{n}a_{i}b_{n-i}}$

${\displaystyle \sigma _{3}(n)={\frac {1}{5}}\left\{6n\sigma _{1}(n)-\sigma _{1}(n)+12\sum _{0<k<n}\sigma _{1}(k)\sigma _{1}(n-k)\right\}.}$    ^[29]

${\displaystyle \sigma _{5}(n)={\frac {1}{21}}\left\{10(3n-1)\sigma _{3}(n)+\sigma _{1}(n)+240\sum _{0<k<n}\sigma _{1}(k)\sigma _{3}(n-k)\right\}.}$    ^[30]

${\displaystyle {\begin{aligned}\sigma _{7}(n)&={\frac {1}{20}}\left\{21(2n-1)\sigma _{5}(n)-\sigma _{1}(n)+504\sum _{0<k<n}\sigma _{1}(k)\sigma _{5}(n-k)\right\}\\&=\sigma _{3}(n)+120\sum _{0<k<n}\sigma _{3}(k)\sigma _{3}(n-k).\end{aligned}}}$    ^{[30] [31]}

${\displaystyle {\begin{aligned}\sigma _{9}(n)&={\frac {1}{11}}\left\{10(3n-2)\sigma _{7}(n)+\sigma _{1}(n)+480\sum _{0<k<n}\sigma _{1}(k)\sigma _{7}(n-k)\right\}\\&={\frac {1}{11}}\left\{21\sigma _{5}(n)-10\sigma _{3}(n)+5040\sum _{0<k<n}\sigma _{3}(k)\sigma _{5}(n-k)\right\}.\end{aligned}}}$    ^{[29] [32]}

${\displaystyle \tau (n)={\frac {65}{756}}\sigma _{11}(n)+{\frac {691}{756}}\sigma _{5}(n)-{\frac {691}{3}}\sum _{0<k<n}\sigma _{5}(k)\sigma _{5}(n-k),}$     где τ ( n ) — функция Рамануджана.     ^{[33] [34]}

Поскольку σ _k ( n ) (для натурального числа k ) и τ ( n ) являются целыми числами, приведенные выше формулы можно использовать для доказательства сравнений ^[35] для функций. См. тау-функцию Рамануджана для некоторых примеров.

Расширим область определения функции распределения, установив p (0) = 1.

${\displaystyle p(n)={\frac {1}{n}}\sum _{1\leq k\leq n}\sigma (k)p(n-k).}$    ^[36]   Эту рекуррентность можно использовать для вычисления p ( n ).

Связанный с номером класса

Петер Густав Лежен Дирихле открыл формулы, связывающие число классов h квадратичных числовых полей с символом Якоби. ^[37]

Целое число D называется фундаментальным дискриминантом , если оно является дискриминантом квадратичного числового поля. Это эквивалентно тому, что D ≠ 1 и либо a) D является бесквадратным и D ≡ 1 (mod 4), либо b) D ≡ 0 (mod 4), D /4 является бесквадратным и D /4 ≡ 2 или 3 (mod 4). ^[38]

Расширим символ Якоби, чтобы он принимал четные числа в «знаменателе», определив символ Кронекера : $${\displaystyle \left({\frac {a}{2}}\right)={\begin{cases}\;\;\,0&{\text{ if }}a{\text{ is even}}\\(-1)^{\frac {a^{2}-1}{8}}&{\text{ if }}a{\text{ is odd. }}\end{cases}}}$$

Тогда, если D < −4 является фундаментальным дискриминантом ^{[39] [40]} $${\displaystyle {\begin{aligned}h(D)&={\frac {1}{D}}\sum _{r=1}^{|D|}r\left({\frac {D}{r}}\right)\\&={\frac {1}{2-\left({\tfrac {D}{2}}\right)}}\sum _{r=1}^{|D|/2}\left({\frac {D}{r}}\right).\end{aligned}}}$$

Существует также формула, связывающая r ₃ и h . Опять же, пусть D будет фундаментальным дискриминантом, D < −4. Тогда ^[41] $${\displaystyle r_{3}(|D|)=12\left(1-\left({\frac {D}{2}}\right)\right)h(D).}$$

Связанный с простым числом

Пусть   будет n- м гармоническим номером . Тогда ${\displaystyle H_{n}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}}$

${\displaystyle \sigma (n)\leq H_{n}+e^{H_{n}}\log H_{n}}$   верно для каждого натурального числа n тогда и только тогда, когда верна     гипотеза Римана . ^[42]

Гипотеза Римана также эквивалентна утверждению, что для всех n > 5040, (где γ — константа Эйлера–Маскерони ). Это теорема Робина . $${\displaystyle \sigma (n)<e^{\gamma }n\log \log n}$$

${\displaystyle \sum _{p}\nu _{p}(n)=\Omega (n).}$

${\displaystyle \psi (x)=\sum _{n\leq x}\Lambda (n).}$    ^[43]

${\displaystyle \Pi (x)=\sum _{n\leq x}{\frac {\Lambda (n)}{\log n}}.}$    ^[44]

${\displaystyle e^{\theta (x)}=\prod _{p\leq x}p.}$    ^[45]

${\displaystyle e^{\psi (x)}=\operatorname {lcm} [1,2,\dots ,\lfloor x\rfloor ].}$    ^[46]

Личность Менона

В 1965 году П. Кесава Менон доказал ^[47] $${\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\gcd(k-1,n)=\varphi (n)d(n).}$$

Это было обобщено рядом математиков. Например,

• Б. Сури ^[48] $${\displaystyle \sum _{\stackrel {1\leq k_{1},k_{2},\dots ,k_{s}\leq n}{\gcd(k_{1},n)=1}}\gcd(k_{1}-1,k_{2},\dots ,k_{s},n)=\varphi (n)\sigma _{s-1}(n).}$$
• Н. Рао ^[49] где a ₁ , a ₂ , ..., a _s — целые числа, gcd( a ₁ , a ₂ , ..., a _s , n ) = 1. $${\displaystyle \sum _{\stackrel {1\leq k_{1},k_{2},\dots ,k_{s}\leq n}{\gcd(k_{1},k_{2},\dots ,k_{s},n)=1}}\gcd(k_{1}-a_{1},k_{2}-a_{2},\dots ,k_{s}-a_{s},n)^{s}=J_{s}(n)d(n),}$$
• Ласло Фейеш Тот ^[50] где m ₁ и m ₂ нечетны, m = lcm( m ₁ , m ₂ ). $${\displaystyle \sum _{\stackrel {1\leq k\leq m}{\gcd(k,m)=1}}\gcd(k^{2}-1,m_{1})\gcd(k^{2}-1,m_{2})=\varphi (n)\sum _{\stackrel {d_{1}\mid m_{1}}{d_{2}\mid m_{2}}}\varphi (\gcd(d_{1},d_{2}))2^{\omega (\operatorname {lcm} (d_{1},d_{2}))},}$$

На самом деле, если f — любая арифметическая функция ^{[51] [52],} где обозначает свертку Дирихле. $${\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}f(\gcd(k-1,n))=\varphi (n)\sum _{d\mid n}{\frac {(\mu *f)(d)}{\varphi (d)}},}$$ ${\displaystyle *}$

Разнообразный

Пусть m и n различны, нечетны и положительны. Тогда символ Якоби удовлетворяет закону квадратичной взаимности : $${\displaystyle \left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{(m-1)(n-1)/4}.}$$

Пусть D ( n ) — арифметическая производная. Тогда логарифмическая производная . Подробнее см. в разделе Арифметическая производная . $${\displaystyle {\frac {D(n)}{n}}=\sum _{\stackrel {p\mid n}{p{\text{ prime}}}}{\frac {v_{p}(n)}{p}}.}$$

Пусть λ ( n ) — функция Лиувилля. Тогда

${\displaystyle |\lambda (n)|\mu (n)=\lambda (n)|\mu (n)|=\mu (n),}$     и

${\displaystyle \lambda (n)\mu (n)=|\mu (n)|=\mu ^{2}(n).}$    

Пусть λ ( n ) — функция Кармайкла. Тогда

${\displaystyle \lambda (n)\mid \phi (n).}$     Дальше,

${\displaystyle \lambda (n)=\phi (n){\text{ if and only if }}n={\begin{cases}1,2,4;\\3,5,7,9,11,\ldots {\text{ (that is, }}p^{k}{\text{, where }}p{\text{ is an odd prime)}};\\6,10,14,18,\ldots {\text{ (that is, }}2p^{k}{\text{, where }}p{\text{ is an odd prime)}}.\end{cases}}}$

См. Мультипликативная группа целых чисел по модулю n и Первообразный корень по модулю n .  

${\displaystyle 2^{\omega (n)}\leq d(n)\leq 2^{\Omega (n)}.}$    ^{[53] [54]}

${\displaystyle {\frac {6}{\pi ^{2}}}<{\frac {\phi (n)\sigma (n)}{n^{2}}}<1.}$    ^[55]

${\displaystyle {\begin{aligned}c_{q}(n)&={\frac {\mu \left({\frac {q}{\gcd(q,n)}}\right)}{\phi \left({\frac {q}{\gcd(q,n)}}\right)}}\phi (q)\\&=\sum _{\delta \mid \gcd(q,n)}\mu \left({\frac {q}{\delta }}\right)\delta .\end{aligned}}}$    ^[56]     Обратите внимание, что   ^[57] ${\displaystyle \phi (q)=\sum _{\delta \mid q}\mu \left({\frac {q}{\delta }}\right)\delta .}$    

${\displaystyle c_{q}(1)=\mu (q).}$

${\displaystyle c_{q}(q)=\phi (q).}$

${\displaystyle \sum _{\delta \mid n}d^{3}(\delta )=\left(\sum _{\delta \mid n}d(\delta )\right)^{2}.}$    ^[58]   Сравните это с 1 ³ + 2 ³ + 3 ³ + ... + n ³ = (1 + 2 + 3 + ... + n ) ²

${\displaystyle d(uv)=\sum _{\delta \mid \gcd(u,v)}\mu (\delta )d\left({\frac {u}{\delta }}\right)d\left({\frac {v}{\delta }}\right).}$    ^[59]

${\displaystyle \sigma _{k}(u)\sigma _{k}(v)=\sum _{\delta \mid \gcd(u,v)}\delta ^{k}\sigma _{k}\left({\frac {uv}{\delta ^{2}}}\right).}$    ^[60]

${\displaystyle \tau (u)\tau (v)=\sum _{\delta \mid \gcd(u,v)}\delta ^{11}\tau \left({\frac {uv}{\delta ^{2}}}\right),}$     где τ ( n ) — функция Рамануджана.     ^[61]

Первые 100 значений некоторых арифметических функций

Примечания

1. Лонг (1972, стр. 151)
2. Петтофреццо и Биркит (1970, стр. 58)
3. Нивен и Цукерман, 4.2.
4. Нагелл, I.9.
5. Бейтман и Даймонд, 2.1.
6. Харди и Райт, введение к гл. XVI.
7. Харди, Рамануджан , § 10.2
8. Апостол, Модулярные функции ... , § 1.15, гл. 4 и гл. 6
9. Харди и Райт, §§ 18.1–18.2
10. Джеральд Тененбаум (1995). Введение в аналитическую и вероятностную теорию чисел . Кембриджские исследования в области высшей математики. Том 46. Cambridge University Press . С. 36–55. ISBN 0-521-41261-7.
11. Харди и Райт, § 17.6, показывают, как теория производящих функций может быть построена чисто формальным образом, не обращая внимания на сходимость.
12. Харди и Райт, Теория 263
13. Харди и Райт, Теория 63
14. см. ссылки на функцию тотиента Джордана
15. Холден и др. во внешних ссылках Формула Гегенбауэра
16. Харди и Райт, Теория 288–290
17. Динева во внешних ссылках, предложение 4
18. Харди и Райт, Теория 264
19. Харди и Райт, Теория 296
20. Харди и Райт, Теория 278
21. Харди и Райт, Теория 386
22. Харди, Рамануджан , уравнения 9.1.2, 9.1.3
23. Коблиц, Пример III.5.2
24. Харди и Райт, § 20.13
25. Харди, Рамануджан , § 9.7
26. Харди, Рамануджан , § 9.13
27. Харди, Рамануджан , § 9.17
28. Уильямс, гл. 13; Хуард и др. (внешние ссылки).
29. Ramanujan, О некоторых арифметических функциях , Таблица IV; Статьи , стр. 146
30. Koblitz, ex. III.2.8
31. Коблиц, пример III.2.3
32. Коблиц, пр. III.2.2
33. Коблиц, пример III.2.4
34. Апостол, Модульные функции ... , Пример 6.10
35. Апостол, Модульные функции... , Гл. 6 Пример 10
36. GH Hardy, S. Ramannujan, Asymptotic Formulaæ in Combinatory Analysis , § 1.3; в Ramannujan, Papers , стр. 279
37. Ландау, стр. 168, приписывает заслуги Гаусса, а также Дирихле.
38. Коэн, Опр. 5.1.2
39. Коэн, Корр. 5.3.13
40. см. Эдвардс, § 9.5 упражнения для более сложных формул.
41. Коэн, Предложение 5.3.10
42. См . функцию делителя .
43. Харди и Райт, уравнение 22.1.2
44. См. функции подсчета простых чисел .
45. Харди и Райт, уравнение 22.1.1
46. Харди и Райт, уравнение 22.1.3
47. Ласло Тот, Тождество Менона и арифметические суммы ... , экв. 1
48. Tóth, ур. 5
49. Tóth, ур. 3
50. Tóth, ур. 35
51. Tóth, ур. 2
52. Тот утверждает, что Менон доказал это для мультипликативного f в 1965 году, а В. Сита Рамайях — для общего f .
53. Харди Рамануджан , ур. 3.10.3
54. Харди и Райт, § 22.13
55. Харди и Райт, Теория 329
56. Харди и Райт, Тезисы 271, 272
57. Харди и Райт, уравнение 16.3.1
58. Рамануджан, Некоторые формулы в аналитической теории чисел , ур. (C); Статьи, стр. 133. В сноске говорится, что Харди сказал Рамануджану, что эта формула также появляется в статье Лиувилля 1857 года.
59. Рамануджан, Некоторые формулы в аналитической теории чисел , ур. (F); Статьи, стр. 134
60. Апостол, Модульные функции ... , гл. 6 ур. 4
61. Апостол, Модульные функции ... , гл. 6 ур. 3

Ссылки

• Том М. Апостол (1976), Введение в аналитическую теорию чисел , Springer Undergraduate Texts in Mathematics , ISBN 0-387-90163-9
• Апостол, Том М. (1989), Модулярные функции и ряды Дирихле в теории чисел (2-е издание) , Нью-Йорк: Springer, ISBN 0-387-97127-0
• Бейтман, Пол Т.; Даймонд, Гарольд Г. (2004), Аналитическая теория чисел, введение , World Scientific , ISBN 978-981-238-938-1
• Коэн, Анри (1993), Курс вычислительной алгебраической теории чисел , Берлин: Springer , ISBN 3-540-55640-0
• Эдвардс, Гарольд (1977). Великая теорема Ферма . Нью-Йорк: Springer . ISBN 0-387-90230-9.
• Харди, Г. Х. (1999), Рамануджан: Двенадцать лекций по темам, предложенным его жизнью и работой , Провиденс, Род-Айленд: AMS / Челси, hdl :10115/1436, ISBN 978-0-8218-2023-0
• Харди, ГХ ; Райт, ЭМ (1979) [1938]. Введение в теорию чисел (5-е изд.). Оксфорд: Clarendon Press. ISBN 0-19-853171-0. MR  0568909. Zbl  0423.10001.
• Джеймсон, GJO (2003), Теорема о простых числах , Cambridge University Press, ISBN 0-521-89110-8
• Коблиц, Нил (1984), Введение в эллиптические кривые и модулярные формы , Нью-Йорк: Springer, ISBN 0-387-97966-2
• Ландау, Эдмунд (1966), Элементарная теория чисел , Нью-Йорк: Челси
• Уильям Дж. Левек (1996), Основы теории чисел , Courier Dover Publications, ISBN 0-486-68906-9
• Лонг, Кэлвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Лексингтон: DC Heath and Company , LCCN  77-171950
• Эллиот Мендельсон (1987), Введение в математическую логику , CRC Press, ISBN 0-412-80830-7
• Нагелл, Трюгве (1964), Введение в теорию чисел (2-е издание) , Челси, ISBN 978-0-8218-2833-5
• Нивен, Иван М.; Цукерман, Герберт С. (1972), Введение в теорию чисел (3-е издание) , John Wiley & Sons , ISBN 0-471-64154-5
• Петтофреццо, Энтони Дж.; Биркит, Дональд Р. (1970), Элементы теории чисел , Englewood Cliffs: Prentice Hall , LCCN  77-81766
• Рамануджан, Шриниваса (2000), Сборник статей , Провиденс, Род-Айленд: AMS / Челси, ISBN 978-0-8218-2076-6
• Уильямс, Кеннет С. (2011), Теория чисел в духе Лиувилля , Лондонское математическое общество, студенческие тексты, т. 76, Кембридж: Cambridge University Press , ISBN 978-0-521-17562-3, ЗБЛ  1227.11002

Дальнейшее чтение

• Шварц, Вольфганг; Шпилькер, Юрген (1994), Арифметические функции. Введение в элементарные и аналитические свойства арифметических функций и в некоторые их почти периодические свойства , London Mathematical Society Lecture Note Series, т. 184, Cambridge University Press , ISBN 0-521-42725-8, ЗБЛ  0807.11001

Внешние ссылки

• «Арифметическая функция», Энциклопедия математики , EMS Press , 2001 [1994]
• Мэтью Холден, Майкл Оррисон, Майкл Варбл Еще одно обобщение функции Эйлера
• Huard, Ou, Spearman, and Williams. Элементарная оценка некоторых сумм сверток, включающих функции делителей
• Динева, Росица, Эйлеров тотиент, Мёбиус и функции делителей Архивировано 16 января 2021 г. на Wayback Machine
• Ласло Тот, тождество Менона и арифметические суммы, представляющие функции многих переменных