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

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

В теории чисел арифметическая , арифметическая или теоретико-числовая функция ^{[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 .

Обозначения

В этой статье это означает, что сумма или произведение относится ко всем простым числам : ${\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 .}$$

простым степенямk = 0 ${\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, то ${\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),}$$

nn ${\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 ), ω ( n ), ν p ( n ) – разложение по простым степеням

Основная теорема арифметики гласит, что любое положительное целое число 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)}.}$$

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

ω ( п ) знак равно k ,

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

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

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

σ k ( n ), τ( n ), d ( n ) – суммы делителей

σ _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 , которые взаимно просты с 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 ) – Жордановая функция тотента

J _k ( n ) , функция тотента Жордана, представляет собой количество k -кортежей натуральных чисел, все меньшие или равные n , которые вместе с n образуют взаимно простой ( k + 1)-кортеж . Это обобщение принципа Эйлера: φ( 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 ) – функция Мёбиуса

µ( 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 ) – тау-функция Рамануджана

τ( 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} ) и rk ( n ) (поскольку они также являются коэффициентами разложения модулярных форм ).

c q ( 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).}$

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

Пси-функция Дедекинда , используемая в теории модулярных функций , определяется формулой

$${\displaystyle \psi (n)=n\prod _{p|n}\left(1+{\frac {1}{p}}\right).}$$

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

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

λ ( n ) , функция Лиувилля, определяется формулой

$${\displaystyle \lambda (n)=(-1)^{\Omega (n)}.}$$

χ ( 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 ) – простые делители

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

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

Для фиксированного простого числа 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 ), θ ( x ), ψ ( x ) – функции, считающие простые числа

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

π ( 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 ) – функция Мангольдта

Λ( 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 ) – статистическая сумма

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 ) – функция Кармайкла

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

Для степеней нечетных простых чисел, а также для 2 и 4 λ ( n ) равна общей функции Эйлера n ; для степеней 2 больше 4 он равен половине функции Эйлера от 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}}}$$

nn

$${\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 ) – Номер класса

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

r k ( n ) – Сумма k квадратов

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

$${\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 ) – арифметическая производная

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

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

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

Учитывая арифметическую функцию a ( n ), ее функция суммирования A ( x ) определяется выражением

$${\displaystyle A(x):=\sum _{n\leq x}a(n).}$$

AmAоткрытых интервалах mxmразрыв скачкаam

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

$${\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 ), пусть F _a ( s ) для комплексного s будет функцией, определяемой соответствующим рядом Дирихле (где он сходится ): ^[11]

$${\displaystyle F_{a}(s):=\sum _{n=1}^{\infty }{\frac {a(n)}{n^{s}}}.}$$

F _asфункцией anannζ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 ₃ приведена ниже в разделе о числах классов.

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

ν знак равно ν ₂ ( п )^{[21] [22] [23]}

$${\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 . степени четных делителей числа 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 и либо а) D не содержит квадратов и D ≡ 1 (mod 4), либо б) 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]
  $${\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),}$$
  где a ₁ , a ₂ , ..., a _s — целые числа, НОД( a ₁ , a ₂ , ..., a _s , n ) = 1.
• Ласло Фейеш Тот ^[50]
  $${\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}))},}$$
  где m ₁ и m ₂ нечетны, m = lcm( m ₁ , m ₂ ).

В самом деле, если 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. ​​Издательство Кембриджского университета . стр. 36–55. ISBN 0-521-41261-7.
11. Харди и Райт, § 17.6, показывают, как теорию производящих функций можно построить чисто формально, не обращая внимания на сходимость.
12. Харди и Райт, Thm. 263
13. Харди и Райт, Thm. 63
14. см. ссылки на функцию totient Джордана.
15. Холден и др. во внешних ссылках Формула Гегенбауэра
16. Харди и Райт, Thm. 288–290
17. Динева во внешних ссылках, подп. 4
18. Харди и Райт, Thm. 264
19. Харди и Райт, Thm. 296
20. Харди и Райт, Thm. 278
21. Харди и Райт, Thm. 386
22. Харди, Рамануджан , уравнения 9.1.2, 9.1.3
23. Коблиц, Ex. III.5.2
24. Харди и Райт, § 20.13
25. Харди, Рамануджан , § 9.7
26. Харди, Рамануджан , § 9.13
27. Харди, Рамануджан , § 9.17
28. Уильямс, гл. 13; Хуард и др. (Внешние ссылки).
29. Рамануджан, О некоторых арифметических функциях , Таблица IV; Документы , с. 146
30. Коблиц, бывш. III.2.8
31. Коблиц, бывш. III.2.3
32. Коблиц, бывш. III.2.2
33. Коблиц, бывш. III.2.4
34. Апостол, Модульные функции ... , Упр. 6.10
35. Апостол, Модульные функции... , Гл. 6 Пр. 10
36. Г.Х. Харди, С. Раманнуян, Асимптотические формулы в комбинаторном анализе , § 1.3; в Раманнуджане, Papers p. 279
37. Ландау, с. 168, авторы отдают должное Гауссу и Дирихле.
38. Коэн, Def. 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. Тот, экв. 5
49. Тот, экв. 3
50. Тот, экв. 35
51. Тот, экв. 2
52. Тот утверждает, что Менон доказал это для мультипликативного f в 1965 году и В. Сита Рамайя для общего f .
53. Харди Рамануджан , экв. 3.10.3
54. Харди и Райт, § 22.13
55. Харди и Райт, Thm. 329
56. Харди и Райт, Thms. 271, 272
57. Харди и Райт, экв. 16.3.1
58. Рамануджан, Некоторые формулы аналитической теории чисел , ур. (С); Документы стр. 133. В сноске говорится, что Харди сообщил Рамануджану, что это также появляется в статье Лиувилля 1857 года.
59. Рамануджан, Некоторые формулы аналитической теории чисел , ур. (Ф); Документы стр. 134
60. Апостол, Модульные функции... , гл. 6 экв. 4
61. Апостол, Модульные функции... , гл. 6 экв. 3

Рекомендации

• Том М. Апостол (1976), Введение в аналитическую теорию чисел , Тексты для студентов Springer по математике , 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). Великая теорема Ферма . Нью-Йорк: Спрингер . ISBN 0-387-90230-9.
• Харди, GH (1999), Рамануджан: Двенадцать лекций по темам, предложенным его жизнью и работой , Провиденс, Род-Айленд: AMS / Челси, hdl : 10115/1436, ISBN 978-0-8218-2023-0
• Харди, штат Джорджия ; Райт, Э.М. (1979) [1938]. Введение в теорию чисел (5-е изд.). Оксфорд: Кларендон Пресс. ISBN 0-19-853171-0. МР  0568909. Збл  0423.10001.
• Джеймсон, GJO (2003), Теорема о простых числах , издательство Кембриджского университета, 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), Элементы теории чисел , Энглвуд Клиффс: Прентис Холл , LCCN  77-81766
• Рамануджан, Шриниваса (2000), Сборник статей , Провиденс, Род-Айленд: AMS / Челси, ISBN 978-0-8218-2076-6
• Уильямс, Кеннет С. (2011), Теория чисел в духе Лиувилля , Тексты для студентов Лондонского математического общества, том. 76, Кембридж: Издательство Кембриджского университета , ISBN 978-0-521-17562-3, Збл  1227.11002

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

• Шварц, Вольфганг; Спилкер, Юрген (1994), Арифметические функции. Введение в элементарные и аналитические свойства арифметических функций и в некоторые из их почти периодических свойств , Серия лекций Лондонского математического общества, том. 184, Издательство Кембриджского университета , ISBN 0-521-42725-8, Збл  0807.11001

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

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