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

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

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

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

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

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

Означення

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

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

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

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

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

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

Приклади

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

${\displaystyle {\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) — сума всіх дільників:

${\displaystyle {\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) власних дільників є рівною:

${\displaystyle {\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

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

Властивості

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  ${\displaystyle \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}}}$ Для цієї функції виконується рівність ${\displaystyle \sigma _{x}^{-1}=(\iota _{x}\mu )*\mu \,}$, і зокрема для ${\displaystyle x=0}$: ${\displaystyle \sigma _{0}^{-1}=\mu *\mu \,}$, де ${\displaystyle \mu }$ — функція Мебіуса.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тоді

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

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

і

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

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

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

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

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

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

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

${\displaystyle 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) довів, що рівність

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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