Функция делителей

Функция делителей от σ₀(n) до n = 250

Сигма-функция от σ₁(n) до n = 250

Сумма квадратов делителей, от σ₂(n), до n = 250

Фу́нкция дели́телей — арифметическая функция, связанная с делителями целого числа. Функция известна также под именем фу́нкция диви́зоров. Применяется, в частности, при исследовании связи дзета-функции Римана и рядов Эйзенштейна для модулярных форм. Изучалась Рамануджаном, который вывел ряд важных равенств в модульной арифметике и арифметических тождествах.

С этой функцией тесно связана суммирующая функция делителей, которая, как следует из названия, является суммой функции делителей.

Определение

Функция «сумма положительных делителей» σ_x(n) для вещественного или комплексного числа x определяется как сумма x-х степеней положительных делителей числа n. Функцию можно выразить формулой

[math]\displaystyle{ \sigma_{x}(n)=\sum_{d|n} d^x\,\! , }[/math]

где [math]\displaystyle{ {d|n} }[/math] означает «d делит n». Обозначения d(n), ν(n) и τ(n) (от немецкого Teiler = делитель) используются также для обозначения σ₀(n), или функции числа делителей . Если x равен 1, функция называется сигма-функцией или суммой делителей, и индекс часто опускается, так что σ(n) эквивалентна σ₁(n).

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

Примеры

Например, σ₀(12) — количество делителей числа 12:

[math]\displaystyle{ \begin{align} \sigma_{0}(12) & = 1^0 + 2^0 + 3^0 + 4^0 + 6^0 + 12^0 \\ & = 1 + 1 + 1 + 1 + 1 + 1 = 6, \end{align} }[/math]

в то время как σ₁(12) — сумма всех делителей:

[math]\displaystyle{ \begin{align} \sigma_{1}(12) & = 1^1 + 2^1 + 3^1 + 4^1 + 6^1 + 12^1 \\ & = 1 + 2 + 3 + 4 + 6 + 12 = 28, \end{align} }[/math]

и аликвотная сумма s(12) собственных делителей равна:

[math]\displaystyle{ \begin{align} s(12) & = 1^1 + 2^1 + 3^1 + 4^1 + 6^1 \\ & = 1 + 2 + 3 + 4 + 6 = 16. \end{align} }[/math]

Таблица значений

n	Делители	σ0(n)	σ1(n)	s(n) = σ1(n) − n	Комментарии
1	1	1	1	0	квадрат: значение σ0(n) нечётно; степень 2: s(n) = n − 1 (почти совершенное)
2	1,2	2	3	1	простое: σ1(n) = 1+n, так что s(n) =1
3	1,3	2	4	1	простое: σ1(n) = 1+n, так что s(n) =1
4	1,2,4	3	7	3	квадрат: σ0(n) нечётно; степень 2: s(n) = n − 1 (почти совершенное)
5	1,5	2	6	1	простое: σ1(n) = 1+n, так что s(n) =1
6	1,2,3,6	4	12	6	первое совершенное число: s(n) = n
7	1,7	2	8	1	простое: σ1(n) = 1+n, так что s(n) =1
8	1,2,4,8	4	15	7	степень 2: s(n) = n − 1 (почти совершенное)
9	1,3,9	3	13	4	квадрат: σ0(n) нечётно
10	1,2,5,10	4	18	8
11	1,11	2	12	1	простое: σ1(n) = 1+n, так что s(n) =1
12	1,2,3,4,6,12	6	28	16	первое избыточное число: s(n) > n
13	1,13	2	14	1	простое: σ1(n) = 1+n, так что s(n) =1
14	1,2,7,14	4	24	10
15	1,3,5,15	4	24	9
16	1,2,4,8,16	5	31	15	квадрат: σ0(n) нечётно; степень 2: s(n) = n − 1 (почти совершенное)

Случаи [math]\displaystyle{ x = 2 }[/math], [math]\displaystyle{ x = 3 }[/math] и так далее входят в последовательности A001157, A001158, A001159, A001160, A013954, A013955 …

Свойства

Для целых, не являющихся квадратами, каждый делитель d числа n имеет парный делитель n/d, а значит, [math]\displaystyle{ \sigma_{0}(n) }[/math] всегда чётно для таких чисел. Для квадратов один делитель, а именно [math]\displaystyle{ \sqrt n }[/math], не имеет пары, так что для них [math]\displaystyle{ \sigma_{0}(n) }[/math] всегда нечётно.

Для простого числа p,

[math]\displaystyle{ \begin{align} \sigma_0(p) & = 2 \\ \sigma_0(p^n) & = n+1 \\ \sigma_1(p) & = p+1 \end{align} }[/math]

поскольку, по определению, простое число делится только на единицу и самого себя. Если p_n# означает праймориал, то

[math]\displaystyle{ \sigma_0(p_n\#) = 2^n }[/math]

Ясно, что [math]\displaystyle{ 1 \lt \sigma_0(n) \lt n }[/math] и [math]\displaystyle{ \sigma(n) \gt n }[/math] для всех [math]\displaystyle{ n \gt 2 }[/math].

Функция делителей мультипликативна, но не вполне мультипликативна.

Если мы запишем

[math]\displaystyle{ n = \prod_{i=1}^r p_i^{a_i} }[/math],

где r = ω(n) — число простых делителей числа n, p_i — i-й простой делитель, а a_i — максимальная степень p_i, на которую делится n, то

[math]\displaystyle{ \sigma_x(n) = \prod_{i=1}^{r} \frac{p_{i}^{(a_{i}+1)x}-1}{p_{i}^x-1} }[/math],

что эквивалентно:

[math]\displaystyle{ \sigma_x(n) = \prod_{i=1}^r \sum_{j=0}^{a_i} p_i^{j x} = \prod_{i=1}^r (1 + p_i^x + p_i^{2x} + \cdots + p_i^{a_i x}). }[/math]

Если положить x = 0, получим, что d(n) равно:

[math]\displaystyle{ \sigma_0(n)=\prod_{i=1}^r (a_i+1). }[/math]

Например, число n = 24 имеет два простых делителя — p₁ = 2 и p₂ = 3. Поскольку 24 — это произведение 2³×3¹, то a₁ = 3 и a₂ = 1.

Теперь мы можем вычислить [math]\displaystyle{ \sigma_0(24) }[/math]:

[math]\displaystyle{ \begin{align} \sigma_0(24) & = \prod_{i=1}^{2} (a_i+1) \\ & = (3 + 1)(1 + 1) = 4 \times 2 = 8. \end{align} }[/math]

Восемь делителей числа 24 — это 1, 2, 4, 8, 3, 6, 12, и 24.

Заметим также, что s(n) = σ(n) − n. Здесь s(n) обозначает сумму собственных делителей числа n, то есть делителей, за исключением самого числа n. Эта функция используется для определения совершенности числа — для них s(n) = n. Если s(n) > n, n называется избыточным, а если s(n) < n, n называется недостаточным.

Если n — степень двойки, то есть [math]\displaystyle{ n = 2^k }[/math], то [math]\displaystyle{ \sigma(n) = 2 \times 2^k - 1 = 2n - 1, }[/math] и s(n) = n — 1, что делает n почти совершенным.

Как пример, для двух простых p и q (где p < q), пусть

[math]\displaystyle{ n = pq. }[/math]

Тогда

[math]\displaystyle{ \sigma(n) = (p+1)(q+1) = n + 1 + (p+q), }[/math]

[math]\displaystyle{ \phi(n) = (p-1)(q-1) = n + 1 - (p+q), }[/math]

и

[math]\displaystyle{ n + 1 = (\sigma(n) + \phi(n))/2, }[/math]

[math]\displaystyle{ p + q = (\sigma(n) - \phi(n))/2, }[/math]

где φ(n) — функция Эйлера.

Тогда корни p и q уравнения:

[math]\displaystyle{ (x-p)(x-q) = x^2 - (p+q)x + n = x^2 - [(\sigma(n) - \phi(n))/2]x + [(\sigma(n) + \phi(n))/2 - 1] = 0 }[/math]

можно выразить через σ(n) и φ(n) :

[math]\displaystyle{ p = (\sigma(n) - \phi(n))/4 - \sqrt{[(\sigma(n) - \phi(n))/4]^2 - [(\sigma(n) + \phi(n))/2 - 1]}, }[/math]

[math]\displaystyle{ q = (\sigma(n) - \phi(n))/4 + \sqrt{[(\sigma(n) - \phi(n))/4]^2 - [(\sigma(n) + \phi(n))/2 - 1]}. }[/math]

Зная n и либо σ(n), либо φ(n) (или зная p+q и либо σ(n), либо φ(n)) мы легко можем найти p и q.

В 1984 году Хиз-Браун (Roger Heath-Brown) доказал, что

[math]\displaystyle{ \sigma_0(n) = \sigma_0(n + 1) }[/math]

встречается бесконечно много раз.

Связь с рядами

Два ряда Дирихле, использующие функцию делителей:

[math]\displaystyle{ \sum_{n=1}^\infty \frac{\sigma_{a}(n)}{n^s} = \zeta(s) \zeta(s-a), }[/math]

и при обозначении d(n) = σ₀(n) получим

[math]\displaystyle{ \sum_{n=1}^\infty \frac{d(n)}{n^s} = \zeta^2(s), }[/math]

и второй ряд,

[math]\displaystyle{ \sum_{n=1}^\infty \frac{\sigma_a(n)\sigma_b(n)}{n^s} = \frac{\zeta(s) \zeta(s-a) \zeta(s-b) \zeta(s-a-b)}{\zeta(2s-a-b)}. }[/math]

Ряд Ламбера, использующий функцию делителей:

[math]\displaystyle{ \sum_{n=1}^\infty q^n \sigma_a(n) = \sum_{n=1}^\infty \frac{n^a q^n}{1-q^n} }[/math]

для любого комплексного |q| ≤ 1 и a.

Эта сумма появляется также в рядах Фурье для рядов Эйзенштейна и в инвариантах эллиптических функций Вейерштрасса.

Асимптотическая скорость роста

В терминах о-малое функция делителей удовлетворяет неравенству (см. стр. 296 книги Апостола)

для всех [math]\displaystyle{ \epsilon\gt 0,\quad d(n)=o(n^\epsilon). }[/math]

Северин Вигерт дал более точную оценку

[math]\displaystyle{ \limsup_{n\to\infty}\frac{\log d(n)}{\log n/\log\log n}=\log2. }[/math]

С другой стороны, ввиду бесконечности количества простых чисел,

[math]\displaystyle{ \liminf_{n\to\infty} d(n)=2. }[/math]

В терминах О-большое, Дирихле показал, что средний порядок функции делителей удовлетворяет следующему неравенству (см. теорему 3.3 книги Апостола)

для всех [math]\displaystyle{ x\geq1, \sum_{n\leq x}d(n)=x\log x+(2\gamma-1)x+O(\sqrt{x}), }[/math]

где [math]\displaystyle{ \gamma }[/math] — постоянная Эйлера — Маскерони.

Задача улучшить границу [math]\displaystyle{ O(\sqrt{x}) }[/math] в этой формуле — это проблема Дирихле о делителях

Поведение сигма-функции неравномерно. Асимптотическую скорость роста сигма-функции можно выразить формулой:

[math]\displaystyle{ \limsup_{n\rightarrow\infty}\frac{\sigma(n)}{n\,\log \log n}=e^\gamma, }[/math]

где lim sup — верхний предел. Этот результат является теоремой Грёнвалла (Grönwall), опубликованной в 1913 году. Его доказательство использует третью теорему Мертенса, которая утверждает, что

[math]\displaystyle{ \lim_{n\to\infty}\frac{1}{\log n}\prod_{p\le n}\frac{p}{p-1}=e^{\gamma}, }[/math]

где p — простое.

В 1915 году Рамануджан доказал, что при выполнении гипотезы Римана неравенство

[math]\displaystyle{ \ \sigma(n) \lt e^\gamma n \log \log n }[/math] (неравенство Робина)

выполняется для всех достаточно больших n. В 1984 году Гай Робин доказал, что неравенство верно для всех n ≥ 5041 в том и только в том случае, если гипотеза Римана верна. Это теорема Робина и неравенство стало широко известно после доказательства теоремы. Наибольшее известное число, нарушающее неравенство — это n=5040. Если гипотеза Римана верна, то нет чисел, больших этого и нарушающих неравенство. Робин показал, что в случае ошибочности гипотезы существует бесконечно много чисел n, нарушающих неравенство, и известно, что наименьшее из таких чисел n ≥ 5041 должно быть сверхизбыточным числом. Было показано, что неравенство выполняется для больших нечётных свободных от квадратов чисел, и что гипотеза Римана эквивалентна выполнению неравенства для всех чисел n, делящихся на пятую степень простого числа

Джефри Лагариас (Jeffrey Lagarias) в 2002 году доказал, что гипотеза Римана эквивалентна утверждению

[math]\displaystyle{ \sigma(n) \le H_n + \ln(H_n)e^{H_n} }[/math]

для любого натурального n, где [math]\displaystyle{ H_n }[/math] — n-е гармоническое число.

Робин доказал, что неравенство

[math]\displaystyle{ \ \sigma(n) \lt e^\gamma n \log \log n + \frac{0.6483\ n}{\log \log n} }[/math]

выполняется для n ≥ 3 без каких-либо дополнительных условий.

Ссылки

• Bach, Eric; Shallit, Jeffrey, Algorithmic Number Theory, volume 1, 1996, MIT Press. ISBN 0-262-02405-5, see page 234 in section 8.8.
• Weisstein, Eric W. Robin's Theorem (англ.) на сайте Wolfram MathWorld.
• Elementary Evaluation of Certain Convolution Sums Involving Divisor Functions PDF, авторы — Huard, Ou, Spearman, и Williams. Содержит элементарное (то есть не опирающееся на теорию модулярных форм) доказательство свертки суммы делителей, формулы для представления различными способами чисел как суммы треугольных чисел.