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

Арифметическая функция — функция, определенная на множестве натуральных чисел $\mathbb{N}$, и принимающая значения во множестве комплексных чисел $\mathbb{C}$.

Определение

Как следует из определения, арифметической функцией называется любая функция

$f \colon \mathbb{N} \to \mathbb{C}$

Название арифметическая функция связано с тем, что в теории чисел известно много функций $~f(n)$ натурального аргумента $~n$, которые выражают те или иные арифметические свойства $~n$. Поэтому, неформально говоря, под арифметической функцией понимают функцию $~f(n)$, которая «выражает некоторое арифметическое свойство» натурального числа $~n$ (см. примеры арифметических функций ниже).

Многие арифметические функции, рассматриваемые в теории чисел, в действительности являются целозначными.

Операции и связанные понятия

• Суммой арифметической функции $f$ называют функцию $F:[0,+\infty)\to \C$, определённую как

$F(x)=\sum_{n\le x} f(n).$

Эта операция является «дискретным аналогом» неопределённого интеграла; при этом, хотя исходная функция и была определена только на $\N$, её сумму оказывается удобным считать определённой на всей положительной полуоси (при этом она, естественно, кусочно-постоянна).

• Свёрткой Дирихле двух арифметических функций f и g называется арифметическая функция h, определённая по правилу

$h(n)=\sum_{d|n} f(d) g(n/d).$

• Арифметической функции f можно сопоставить её «производящую функцию» — ряд Дирихле

$\Phi_f(s)=\sum_n f(n) n^{-s}.$

При этом свёртке Дирихле двух арифметических функций соответствует произведение их производящих функций.

• Поточечное умножение на логарифм,

$f\mapsto f', \quad f'(n)=f(n) \cdot \ln n,$

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

$(f*g)' = f'*g + f*g'.$

Переход к производящей функции превращает эту операцию в обычное дифференцирование.

Известные арифметические функции

Количество делителей

Арифметическая функция $~\tau \colon \mathbb{N} \to \mathbb{N}$ определяется как число положительных делителей натурального числа $~n$:

$~\tau(n) = \sum_{d|n} 1$

Если $~m$ и $~n$ взаимно просты, то каждый делитель произведения $~mn$ может быть единственным образом представлен в виде произведения делителей $~m$ и $~n$, и обратно, каждое такое произведение является делителем $~mn$. Отсюда следует, что функция $~\tau$ мультипликативна:

$~\tau(mn) = \tau(m) \tau(n)$

Если $~n = \prod_{i=1}^{r} p_i^{s_i}$ — каноническое разложение натурального $~n$, то в силу мультипликативности

$~\tau(n) = \tau(p_1^{s_1}) \tau(p_2^{s_2}) \ldots \tau(p_r^{s_r})$

Так как положительными делителями числа $p_i^{s_i}$ являются $~s_i+1$ чисел $1, p_i, \ldots, p_i^{s_i}$, то

$~\tau(n) = (s_1+1) (s_2+1) \ldots (s_r+1)$

Число делителей большого целого числа n растёт в среднем как $\ln n$^[1]. Более точно — см. формулу Дирихле.

Сумма делителей

Функция $\sigma \colon \mathbb{N} \to \mathbb{N}$ определяется как сумма делителей натурального числа $~n$:

$~\sigma (n) = \sum_{d|n} d$

Обобщая функции $~\tau(n)$ и $~\sigma(n)$ для произвольного, вообще говоря комплексного, $~k$ можно определить $~\sigma_k(n)$ — сумму $k$-х степеней положительных делителей натурального числа $~n$:

$~\sigma_k (n) = \sum_{d|n} d^k$

Используя нотацию Айверсона можно записать

$~\sigma_k(n) = \sum_{d} d^k[\,d|n\,]$

Функция $~\sigma_k$ мультипликативна:

$m \perp n \Rightarrow ~\sigma_k (mn) = \sigma_k (m) \sigma_k (n)$

Если $~n = \prod_{i=1}^{r} p_i^{s_i}$ — каноническое разложение натурального $~n$, то

$~\sigma_k(n) = \prod_{i=1}^r \frac {p_i^{(s_i+1)k}-1} {p_i - 1}$

Сумма делителей числа n растёт в среднем как линейная функция cn, где постоянная c найдена Эйлером и есть $c=\zeta(2)=\pi^2/6$^[1].

Функция Эйлера

Основная статья: Функция Эйлера

Функция Эйлера $\varphi(n)$, или тотиента, определяется как количество положительных целых чисел, не превосходящих $~n$, которые взаимно просты с $~n$.

Пользуясь нотацией Айверсона можно записать:

$\varphi(n) = \sum_{1 \leq k \leq n} [k \perp n]$

Функция Эйлера мультипликативна:

$m \perp n \Rightarrow ~\varphi (mn) = \varphi (m) \varphi (n)$

В явном виде значение функции Эйлера выражается формулой:

$\varphi (n) = n \left(1 - \frac{1}{p_1} \right) \left(1 - \frac{1}{p_2} \right) \dots \left(1 - \frac{1}{p_r} \right)$

где $p_1, p_2, \ldots, p_r$ — различные простые делители $~n$.

Функция Мёбиуса

Основная статья: Функция Мёбиуса

Функцию Мёбиуса $~\mu(n)$ можно определить как арифметическую функцию, которая удовлетворяет следующему соотношению:

$\sum_{d | n} \mu(d) = \begin{cases} 1,&n=1\\ 0,&n>1 \end{cases}$

То есть сумма значений функции Мёбиуса по всем делителям целого положительного числа $~n$ равна нулю, если $~n>1$, и равна $~1$, если $~n=1$.

Можно показать, что этому уравнению удовлетворяет лишь одна функция, и её можно явно задать следующей формулой:

$\mu(n) = \begin{cases} (-1)^r, & n = p_1 p_2 \ldots p_r \\ 0, & p^2 | n \\ 1, & n=1 \end{cases}$

Здесь $p_i$ — различные простые числа, $p$ — простое число. Иначе говоря, функция Мёбиуса $\mu(n)$ равна $0$, если $n$ не свободно от квадратов (то есть делится на квадрат простого числа), и равна $~\pm 1$ в противном случае (плюс или минус выбирается в зависимости от четности числа простых делителей $~n$).

Функция Мёбиуса является мультипликативной функцией. Важное значение функции Мёбиуса в теории чисел связано с формулой обращения Мёбиуса.

Примечания

1. ↑ ^{1 2} В. И Арнольд Динамика, статистика и проективная геометрия полей Галуа. — М.: МЦНМО, 2005. — С. 70. — 72 с.

См. также

• Мультипликативная функция

Литература

• Чандрасекхаран К. Введение в аналитическую теорию чисел = Introduction to Analytic Number Theory. — М.: «Мир», 1974. — 188 с.