Функція дільників

Функція дільників σ₀(n) до n = 250

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

сума квадратів дільників, σ₂(n), до n = 250

Функція дільників — арифметична функція, пов'язана з дільниками цілого числа. Функція відома також під назвою функція дивізорів. Застосовується, зокрема, при дослідженні зв'язку дзета-функції Рімана і рядів Ейзенштейна для модулярних форм. Вивчалася Рамануджаном, який вивів ряд важливих рівностей в модульній арифметиці і арифметичних тотожностей.

З функцією дільників тісно пов'язана суматорна функція дільників, яка, як випливає з назви, є сумою функції дільників.

Означення

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

$\sigma _{x}(n)=\sum _{d|n}d^{x}\,\!,$

де ${d|n}$ означає «d ділить n».

Найважливішими частковими випадками є x = 0 і x = 1. Для позначення σ₀(n) або функції кількості дільників використовуються також позначення d(n), ν(n) и τ(n) (від німецького Teiler = дільник) . У цьому випадку функція має просту геометричну інтерпретацію: σ₀(n) = d(n) дорівнює кількості точок (x, y) з цілими координатами у «правому верхньому квадранті», що лежать на гіперболі xy = n.

Якщо x дорівнює 1, функція називається сигма-функцією або сумою дільників і індекс часто опускається, так що σ(n) є еквівалентним σ₁(n) .

Пов'язаною з σ(n) є функція s(n), що є рівною сумі власних дільників (тобто дільників, за винятком самого n) , тобто s(n) = σ₁(n) - n.

Приклади

Наприклад, σ₀(12) — кількість дільників числа 12:

${\begin{aligned}\sigma _{0}(12)&=1^{0}+2^{0}+3^{0}+4^{0}+6^{0}+12^{0}\\&=1+1+1+1+1+1=6,\end{aligned}}$

тоді як σ₁(12) — сума всіх дільників:

${\begin{aligned}\sigma _{1}(12)&=1^{1}+2^{1}+3^{1}+4^{1}+6^{1}+12^{1}\\&=1+2+3+4+6+12=28,\end{aligned}}$

і сума s(12) власних дільників є рівною:

${\begin{aligned}s(12)&=1^{1}+2^{1}+3^{1}+4^{1}+6^{1}\\&=1+2+3+4+6=16.\end{aligned}}$

Таблиця значень

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 (майже досконале)

σ0(n)	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9	+10	+11
0+		1	2	2	3	2	4	2	4	3	4	2
12+	6	2	4	4	5	2	6	2	6	4	4	2
24+	8	3	4	4	6	2	8	2	6	4	4	4
36+	9	2	4	4	8	2	8	2	6	6	4	2
48+	10	3	6	4	6	2	8	4	8	4	4	2
60+	12	2	4	6	7	4	8	2	6	4	8	2
72+	12	2	4	6	6	4	8	2	10	5	4	2
84+	12	4	4	4	8	2	12	4	6	4	4	4
96+	12	2	6	6	9	2	8	2	8	8	4	2
108+	12	2	8	4	10	2	8	4	6	6	4	4
120+	16	3	4	4	6	4	12	2	8	4	8	2
132+	12	4	4	8	8	2	8	2	12	4	4	4

σ1(n)	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9	+10	+11
0+		1	3	4	7	6	12	8	15	13	18	12
12+	28	14	24	24	31	18	39	20	42	32	36	24
24+	60	31	42	40	56	30	72	32	63	48	54	48
36+	91	38	60	56	90	42	96	44	84	78	72	48
48+	124	57	93	72	98	54	120	72	120	80	90	60
60+	168	62	96	104	127	84	144	68	126	96	144	72
72+	195	74	114	124	140	96	168	80	186	121	126	84
84+	224	108	132	120	180	90	234	112	168	128	144	120
96+	252	98	171	156	217	102	216	104	210	192	162	108
108+	280	110	216	152	248	114	240	144	210	182	180	144
120+	360	133	186	168	224	156	312	128	255	176	252	132
132+	336	160	204	240	270	138	288	140	336	192	216	168

σ2(n)	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9	+10	+11
0+		1	5	10	21	26	50	50	85	91	130	122
12+	210	170	250	260	341	290	455	362	546	500	610	530
24+	850	651	850	820	1050	842	1300	962	1365	1220	1450	1300
36+	1911	1370	1810	1700	2210	1682	2500	1850	2562	2366	2650	2210
48+	3410	2451	3255	2900	3570	2810	4100	3172	4250	3620	4210	3482
60+	5460	3722	4810	4550	5461	4420	6100	4490	6090	5300	6500	5042
72+	7735	5330	6850	6510	7602	6100	8500	6242	8866	7381	8410	6890
84+	10500	7540	9250	8420	10370	7922	11830	8500	11130	9620	11050	9412
96+	13650	9410	12255	11102	13671	10202	14500	10610	14450	13000	14050	11450
108+	17220	11882	15860	13700	17050	12770	18100	13780	17682	15470	17410	14500
120+	22100	14763	18610	16820	20202	16276	22750	16130	21845	18500	22100	17162
132+	25620	18100	22450	21320	24650	18770	26500	19322	27300	22100	25210	20740

Випадки $x=2$, $x=3$ і так далі входять в послідовності  A001157,  A001158,  A001159,  A001160,  A013954,  A013955 …

Властивості

• Для цілих, які не є квадратами, кожен дільник d числа n має пов'язаний дільник n/d, і тому для таких чисел $\sigma _{0}(n)$ завжди є парним. Для квадратів один дільник, а саме ${\sqrt {n}}$, не має пари, так що для них $\sigma _{0}(n)$ завжди є непарним числом.

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

${\begin{aligned}\sigma _{0}(p)&=2\\\sigma _{0}(p^{n})&=n+1\\\sigma _{1}(p)&=p+1\end{aligned}}$

оскільки, за означенням, просте число ділиться тільки на одиницю і самого себе.

• Якщо p_n# позначає прайморіал, то

$\sigma _{0}(p_{n}\#)=2^{n}$

• Для всіх $n>2$ виконуються нерівності $1<\sigma _{0}(n)<n$ і $n{\sqrt {n}}>\sigma (n)>n$.

Для складених чисел виконується нерівність $\sigma (n)>n+n^{\frac {1}{2}}$.

Для будь-яких цілих чисел більших одиниці $\sigma (mn)>\sigma (n)+\sigma (m)\,$.

Для всіх $n$ окрім 1,2,3,4,6 и 8 виконується нерівність Анапурни)^,,:

$\sigma (n)<{\frac {6}{\pi ^{2}}}\cdot n^{\frac {3}{2}}$

Для всіх натуральних чисел $n$ і $m$ виконується нерівність Сіварамакрішнана — Венкатараманана:

$\sigma _{m}(n)\geq n^{\frac {m}{2}}\cdot \sigma _{0}(n)$

Нерівність Ленгфорда

$\sigma (n)\leq {\frac {1}{2}}(n+1)\sigma _{0}(n)$

• У кільці арифметичних функцій функція дільників є оборотним елементом і можна дати еквівалентне означення: $\sigma _{x}=\iota _{0}*\iota _{x},\,$ де, за означенням $\iota _{x}(n)=n^{x}$, а * позначає згортку Діріхле. Оберненим елементом для функції σ_x є мультиплікативна арифметична функція задана як:

  $\left(\sigma _{x}^{-1}\right)(p^{k})={\begin{cases}1{\text{,}}&k=0\\-1-p^{x}{\text{,}}&k=1\\p^{x}{\text{,}}&k=2\\0{\text{,}}&k>2\end{cases}}$ Для цієї функції виконується рівність $\sigma _{x}^{-1}=(\iota _{x}\mu )*\mu \,$, і зокрема для $x=0$: $\sigma _{0}^{-1}=\mu *\mu \,$, де $\mu$ — функція Мебіуса.

• При тих же позначеннях$\sigma _{-x}=\iota _{-x}\sigma _{x}.\,$

• Функція дільників є мультиплікативною, але не цілком мультиплікативною.

Якщо $m,n$ — взаємно прості натуральні числа, і $d^{*}|mn$, то $d^{*}=dd'$, де $d|m$ і $d'|m$ і до того ж такий запис є єдиним (з точністю до порядку множників). Навпаки, якщо $d|m$ і $d'|n$, то $dd'|mn$. Тому $\sum _{d|m}d^{x}\sum _{d'|n}(d')^{x}=\sum _{d^{*}|mn}(d^{*})^{x}$, тобто $\sigma _{x}(m)\sigma _{x}(n)=\sigma _{x}(mn)$.

Натомість, наприклад, $\sigma _{x}(2)=1+2^{x},\ \sigma _{x}(4)=1+2^{x}+4^{x}$ і тому $\sigma _{x}(2)\cdot \sigma _{x}(2)=1+2\cdot 2^{x}+4^{x}\neq \sigma _{x}(4)=1+2^{x}+4^{x}$.

• Якщо записати

$n=\prod _{i=1}^{r}p_{i}^{a_{i}}$,

де r = ω(n) — кількість простих дільників числа n, p_i — i-й простий дільник, а a_i — максимальний степінь p_i, на який ділиться n, то з мультиплікативності функції дільників отримуємо:

$\sigma _{x}(n)=\prod _{i=1}^{r}\sum _{j=0}^{a_{i}}p_{i}^{jx}=\prod _{i=1}^{r}(1+p_{i}^{x}+p_{i}^{2x}+\cdots +p_{i}^{a_{i}x}).$.

Використовуючи формулу суми геометричної прогресії, також можна записами:

$\sigma _{x}(n)=\prod _{i=1}^{r}{\frac {p_{i}^{(a_{i}+1)x}-1}{p_{i}^{x}-1}}$,

• Якщо у попередній формулі взяти x = 0, отримаємо, що d(n) є рівним:

$\sigma _{0}(n)=\prod _{i=1}^{r}(a_{i}+1).$

Приклад, число n = 24 має два простих дільники — p₁ = 2 і p₂ = 3. Оскільки 24 — добуток 2³×3¹, то a₁ = 3 і a₂ = 1.

Тепер можна обчислити $\sigma _{0}(24)$:

${\begin{aligned}\sigma _{0}(24)&=\prod _{i=1}^{2}(a_{i}+1)\\&=(3+1)(1+1)=4\times 2=8.\end{aligned}}$

Вісім дільників числа 24 — 1, 2, 4, 8, 3, 6, 12 і 24.

• Функція s(n) використовується для означення досконалих чисел — для них s(n) = n. Якщо s (n) > n, то n називається надлишковим, а якщо s(n) < n, то n називається недостатнім.

Якщо n — степінь двійки, тобто $n=2^{k}$, то $\sigma (n)=2\times 2^{k}-1=2n-1,$ і s(n) = n-1, що робить n майже досконалим.

• Як приклад, для двох простих p і q (де p < q), нехай $n=pq.$

Тоді

$\sigma (n)=(p+1)(q+1)=n+1+(p+q),$

$\phi (n)=(p-1)(q-1)=n+1-(p+q),$

і

$n+1=(\sigma (n)+\phi (n))/2,$

$p+q=(\sigma (n)-\phi (n))/2,$

де φ(n) — функція Ейлера.

Тоді корені p і q рівняння:

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

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

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

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

Знаючи n і або σ(n), або φ(n) (чи знаючи p+q і або σ(n) або φ(n)) можна знайти p і q.

• В 1984 році Хіз-Браун (Roger Heath-Brown) довів, що рівність

$\sigma _{0}(n)=\sigma _{0}(n+1)$

виконується для нескінченної кількості натуральних чисел.

Зв'язок з рядами

Два ряди Діріхле, із функцією дільників:

$\sum _{n=1}^{\infty }{\frac {\sigma _{a}(n)}{n^{s}}}=\zeta (s)\zeta (s-a),$

і при позначенні d(n) = σ₀(n) зокрема

$\sum _{n=1}^{\infty }{\frac {d(n)}{n^{s}}}=\zeta ^{2}(s),$

Інший ряд, де використовуються ці функції:

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

Ряд Ламбера, із функцією дільників:

$\sum _{n=1}^{\infty }q^{n}\sigma _{a}(n)=\sum _{n=1}^{\infty }{\frac {n^{a}q^{n}}{1-q^{n}}}$

для будь-якого комплексного |q| ≤ 1 і a.

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

Асимптотична швидкість росту

Швидкість росту кількості дільників

• Для всіх $\varepsilon >0$ справедливою є границя:

$\varlimsup _{n\to \infty }{\frac {d(n)}{(\log n)^{\varepsilon }}}=\infty .$

Дійсно можна вибрати таке ціле число $k$, що $k\leqslant \varepsilon <k+1$ і позначаючи $p_{k}$ — k-те по величині просте число можна ввести числа $n_{i}=(2\cdot 3\cdot \ldots \cdot p_{k})^{i}$ для $i\in \mathbb {N}$. Тоді з формули кількості дільників через розклад на добуток простих чисел $d(n_{i})=(i+1)^{k+1}>i^{k+1}=\left({\frac {\log n_{i}}{\log(2\cdot \ldots \cdot p_{k+1})}}\right)^{k+1}>c(\log n_{i})^{k+1}$, де $c$ — константа, що не залежить від $i$. Позначивши $\delta =k+1-\varepsilon$ з попередньої нерівності отримаємо $\lim _{i\to \infty }{\frac {d(n_{i})}{(\log n_{i})^{\varepsilon }}}>\lim _{i\to \infty }c(\log n_{i})^{\delta }=\infty .$

• З іншого боку функція кількості дільників задовольняє нерівність

для всіх $\epsilon >0,\quad d(n)=o(n^{\epsilon })$, тобто $\lim _{n\to \infty }{\frac {d(n)}{n^{\varepsilon }}}=0.$

• Северин Вігерт дав більш точну оцінку

$\varlimsup _{n\to \infty }{\frac {\log d(n)}{\log n/\log \log n}}=\log 2.$

• З іншого боку, для будь-якого простого числа $d(p)=2$ і з огляду на нескінченність множини простих чисел,

$\varliminf _{n\to \infty }d(n)=2.$

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

Для всіх $x\geq 1,\sum _{n\leq x}d(n)=x\log x+(2\gamma -1)x+O({\sqrt {x}}),$

де $\gamma$ — стала Ейлера — Маскероні.

Завдання покращити границю $O({\sqrt {x}})$ в цій формулі називається проблемою Діріхле про дільники.

Швидкість росту суми дільників

• Поведінка сигма функції є нерівномірною. Асимптотичну швидкість росту сигма функції можна виразити формулою:

$\varlimsup _{n\rightarrow \infty }{\frac {\sigma (n)}{n\,\log \log n}}=e^{\gamma }.$

Цей результат називається теоремою Гронвала (Gronwall) і був опублікований у 1913 році . Його доведення використовує третю теорему Мертенса, яка стверджує, що

$\lim _{n\to \infty }{\frac {1}{\log n}}\prod _{p\leq n}{\frac {p}{p-1}}=e^{\gamma },$

де p — просте число.

• У 1915 році Рамануджан довів, що при виконанні гіпотези Рімана нерівність

$\ \sigma (n)<e^{\gamma }n\log \log n$ (нерівність Робіна)

виконується для всіх досить великих n .

У 1984 році Гай Робін довів, що нерівність є вірною для всіх n ≥ 5041 в тому і тільки в тому випадку, якщо гіпотеза Рімана є вірною . Це твердження називається теоремою Робіна.

Найбільше відоме число, що порушує нерівність Робіна — n = 5040. Якщо гіпотеза Рімана вірна, то немає більших чисел, що порушують нерівність. Робін показав, що в разі помилковості гіпотези існує нескінченна кількість чисел n, що порушують нерівність, і відомо, що найменше з таких чисел n ≥ 5041 має бути надлишковим числом . Було показано, що нерівність виконується для великих непарних вільних від квадратів чисел, і що гіпотеза Рімана еквівалентна виконанню нерівності для всіх чисел n, що діляться на п'ятий степінь простого числа

• Джефрі Лагаріас (Jeffrey Lagarias) в 2002 році довів, що гіпотеза Рімана еквівалентна твердженням

$\sigma (n)\leq H_{n}+\ln(H_{n})e^{H_{n}}$

для будь-якого натурального n, де $H_{n}$ — n-е гармонічне число .

• Робін довів, що нерівність

$\ \sigma (n)<e^{\gamma }n\log \log n+{\frac {0.6483\ n}{\log \log n}}$

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

Див. також

• Функція суми квадратів

Посилання

• Чандрасекхаран К. Введение в аналитическую теорию чисел. — Москва : Мир, 1974. — 187 с.(рос.)
• Apostol Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001
• 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