Функция делителя - Divisor function

«Теорема Робина» перенаправляется сюда. О теореме Роббинса в теории графов см. Теорема Роббинса.

Функция делителя σ₀(п) вплоть до п = 250

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

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

Сумма кубов делителей, σ₃(п) вплоть до п = 250

В математика, и особенно в теория чисел, а делительная функция является арифметическая функция связанный с делители из целое число. Когда упоминается как то делитель, он считает количество делителей целого числа (включая 1 и само число). Он проявляется в ряде замечательных личностей, включая отношения на Дзета-функция Римана и Серия Эйзенштейна из модульные формы. Делительные функции изучались Рамануджан, который дал ряд важных совпадения и идентичности; они рассматриваются отдельно в статье Сумма Рамануджана.

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

Определение

В функция суммы положительных делителей σ_Икс(п), для действительного или комплексного числа Икс, определяется как сумма из Иксth полномочия положительных делители из п. Это может быть выражено в сигма-обозначение так как

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

где ${\displaystyle {d\mid n}}$ сокращение от "d разделяет п". Обозначения d(п), ν (п) и τ (п) (для немецкого Teiler = дивизоры) также используются для обозначения σ₀(п), или функция числа делителей^[1][2] (OEIS: A000005). Когда Икс равно 1, функция называется сигма-функция или функция суммы делителей,^[1][3] а индекс часто опускается, поэтому σ (п) совпадает с σ₁(п) (OEIS: A000203).

В аликвотная сумма s(п) из п это сумма собственные делители (т. е. дивизоры без учета п сам, OEIS: A001065) и равно σ₁(п) − п; то аликвотная последовательность из п формируется путем многократного применения функции суммы аликвот.

пример

Например, σ₀(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}}}$

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

Случаи Икс = От 2 до 5 перечислены в OEIS: A001157 − OEIS: A001160, Икс = От 6 до 24 указаны в OEIS: A013954 − OEIS: A013972.

п	факторизация	σ0(п)	σ1(п)	σ2(п)	σ3(п)	σ4(п)
1	1	1	1	1	1	1
2	2	2	3	5	9	17
3	3	2	4	10	28	82
4	2^2	3	7	21	73	273
5	5	2	6	26	126	626
6	2×3	4	12	50	252	1394
7	7	2	8	50	344	2402
8	2^3	4	15	85	585	4369
9	3^2	3	13	91	757	6643
10	2×5	4	18	130	1134	10642
11	11	2	12	122	1332	14642
12	2^2×3	6	28	210	2044	22386
13	13	2	14	170	2198	28562
14	2×7	4	24	250	3096	40834
15	3×5	4	24	260	3528	51332
16	2^4	5	31	341	4681	69905
17	17	2	18	290	4914	83522
18	2×3^2	6	39	455	6813	112931
19	19	2	20	362	6860	130322
20	2^2×5	6	42	546	9198	170898
21	3×7	4	32	500	9632	196964
22	2×11	4	36	610	11988	248914
23	23	2	24	530	12168	279842
24	2^3×3	8	60	850	16380	358258
25	5^2	3	31	651	15751	391251
26	2×13	4	42	850	19782	485554
27	3^3	4	40	820	20440	538084
28	2^2×7	6	56	1050	25112	655746
29	29	2	30	842	24390	707282
30	2×3×5	8	72	1300	31752	872644
31	31	2	32	962	29792	923522
32	2^5	6	63	1365	37449	1118481
33	3×11	4	48	1220	37296	1200644
34	2×17	4	54	1450	44226	1419874
35	5×7	4	48	1300	43344	1503652
36	2^2×3^2	9	91	1911	55261	1813539
37	37	2	38	1370	50654	1874162
38	2×19	4	60	1810	61740	2215474
39	3×13	4	56	1700	61544	2342084
40	2^3×5	8	90	2210	73710	2734994
41	41	2	42	1682	68922	2825762
42	2×3×7	8	96	2500	86688	3348388
43	43	2	44	1850	79508	3418802
44	2^2×11	6	84	2562	97236	3997266
45	3^2×5	6	78	2366	95382	4158518
46	2×23	4	72	2650	109512	4757314
47	47	2	48	2210	103824	4879682
48	2^4×3	10	124	3410	131068	5732210
49	7^2	3	57	2451	117993	5767203
50	2×5^2	6	93	3255	141759	6651267

Характеристики

Формулы при простых степенях

Для простое число п,

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

потому что по определению делители простого числа равны 1 и самому себе. Также, где п_п# обозначает первобытный,

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

поскольку п простые множители допускают последовательность двоичного выбора (${\displaystyle p_{i}}$ или 1) от п условия для каждого образованного собственного делителя.

Ясно, ${\displaystyle 1<\sigma _{0}(n)<n}$ и σ (п) > п для всехп > 2.

Функция делителя мультипликативный, но нет полностью мультипликативный:

${\displaystyle \gcd(a,b)=1\Longrightarrow \sigma _{x}(ab)=\sigma _{x}(a)\sigma _{x}(b).}$

Следствием этого является то, что если мы напишем

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

где р = ω(п) это количество различных простых множителей из п, п_я это яй простой фактор, и а_я это максимальная мощность п_я по которому п является делимый, то имеем: ^[4]

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

который, когда Икс ≠ 0, эквивалентно полезной формуле: ^[4]

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

Когда Икс = 0, d(п) является: ^[4]

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

Например, если п равно 24, есть два простых множителя (п₁ равно 2; п₂ равно 3); отмечая, что 24 является продуктом 2³×3¹, а₁ 3 и а₂ равно 1. Таким образом, мы можем вычислить ${\displaystyle \sigma _{0}(24)}$ как так:

${\displaystyle \sigma _{0}(24)=\prod _{i=1}^{2}(a_{i}+1)=(3+1)(1+1)=4\cdot 2=8.}$

По этой формуле подсчитываются восемь делителей: 1, 2, 4, 8, 3, 6, 12 и 24.

Прочие свойства и личности

Эйлер доказал замечательное повторение:^[5][6][7]

${\displaystyle {\begin{aligned}\sigma (n)&=\sigma (n-1)+\sigma (n-2)-\sigma (n-5)-\sigma (n-7)+\sigma (n-12)+\sigma (n-15)+\cdots \\&=\sum _{i\in \mathbb {Z} }(-1)^{i+1}\left(\sigma \left(n-{\frac {1}{2}}\left(3i^{2}-i\right)\right)+\delta \left(n,{\frac {1}{2}}\left(3i^{2}-i\right)\right)n\right)\end{aligned}}}$

где мы устанавливаем ${\displaystyle \sigma (0)=n}$ если это произойдет и ${\displaystyle \sigma (i)=0}$ за ${\displaystyle i\leq 0,}$, мы используем Дельта Кронекера ${\displaystyle \delta (\cdot ,\cdot ),}$ и ${\displaystyle {\tfrac {1}{2}}\left(3i^{2}-i\right)}$ являются пятиугольные числа. Действительно, Эйлер доказал это логарифмическим дифференцированием тождества в его Теорема о пятиугольном числе.

Для целого числа, не являющегося квадратом, п, каждый делитель, d, из п спарен с делителем п/d из п и ${\displaystyle \sigma _{0}(n)}$ даже; для квадратного целого числа один делитель (а именно ${\displaystyle {\sqrt {n}}}$) не спарен с отдельным дивизором и ${\displaystyle \sigma _{0}(n)}$ странно. Аналогично число ${\displaystyle \sigma _{1}(n)}$ нечетно тогда и только тогда, когда п квадрат или дважды квадрат.^{[нужна цитата ]}

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

Если n - степень 2, например, ${\displaystyle n=2^{k}}$, тогда ${\displaystyle \sigma (n)=2\cdot 2^{k}-1=2n-1,}$ и s (n) = n - 1, что делает п практически идеально.

Например, для двух различных простых чисел п и q с p , позволять

${\displaystyle n=pq.}$

потом

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

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

и

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

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

где ${\displaystyle \varphi (n)}$ является Функция Эйлера.

Затем корни:

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

позвольте нам выразить п и q с точки зрения σ(п) и φ(п) только, даже не зная п или р + д, так как:

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

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

Кроме того, зная n и либо ${\displaystyle \sigma (n)}$ или ${\displaystyle \varphi (n)}$ (или зная p + q и либо ${\displaystyle \sigma (n)}$ или ${\displaystyle \varphi (n)}$) позволяет нам легко найти п и q.

В 1984 г. Роджер Хит-Браун доказал, что равенство

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

верно для бесконечного числа значений n, см. OEIS: A005237.

Серийные отношения

Два Серия Дирихле с участием функции делителя: ^[8]

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

который для d(п) = σ₀(п) дает: ^[8]

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

и ^[9]

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

А Серия Ламберта с функцией делителя: ^[10]

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

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

За ${\displaystyle k>0}$ существует явное представление серии с Суммы Рамануджана ${\displaystyle c_{m}(n)}$ в качестве :^[11]

${\displaystyle \sigma _{k}(n)=\zeta (k+1)n^{k}\sum _{m=1}^{\infty }{\frac {c_{m}(n)}{m^{k+1}}}.}$

Вычисление первых членов ${\displaystyle c_{m}(n)}$ показывает свои колебания около «среднего значения» ${\displaystyle \zeta (k+1)n^{k}}$:

${\displaystyle \sigma _{k}(n)=\zeta (k+1)n^{k}\left[1+{\frac {(-1)^{n}}{2^{k+1}}}+{\frac {2\cos {\frac {2\pi n}{3}}}{3^{k+1}}}+{\frac {2\cos {\frac {\pi n}{2}}}{4^{k+1}}}+\cdots \right]}$

Скорость роста

В маленькая нотация, функция делителя удовлетворяет неравенству:^[12][13]

${\displaystyle {\mbox{for all }}\varepsilon >0,\quad d(n)=o(n^{\varepsilon }).}$

Точнее, Северин Вигерт показало, что:^[13]

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

С другой стороны, поскольку есть бесконечно много простых чисел,^[13]

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

В Обозначение Big-O, Питер Густав Лежен Дирихле показал, что средний заказ функции делителей удовлетворяет следующему неравенству:^[14][15]

${\displaystyle {\mbox{for all }}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}})}$ в этой формуле известен как Проблема делителей Дирихле.

Поведение сигма-функции нерегулярно. Асимптотическая скорость роста сигма-функции может быть выражена как: ^[16]

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

где lim sup - это предел высшего. Этот результат Grönwall теорема, опубликовано в 1913 г. (Грёнвалль 1913 ). Его доказательство использует 3-я теорема Мертенса, в котором говорится, что:

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

где п обозначает простое число.

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

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

выполняется для всех достаточно больших п (Рамануджан 1997 ). Наибольшее известное значение, нарушающее неравенство, равно п=5040. В 1984 г. Гай Робин доказал, что неравенство верно для всех п > 5040 если и только если гипотеза Римана верна (Робин 1984 ). Это Теорема Робина и неравенство стало известно после него. Кроме того, Робин показал, что если гипотеза Римана неверна, то существует бесконечное число значений п нарушающие неравенство, и известно, что наименьшее из таких п > 5040 должно быть избыточный (Акбари и Фриггстад ​​2009 ). Было показано, что неравенство справедливо для больших нечетных целых чисел и чисел без квадратов, и что гипотеза Римана эквивалентна неравенству только для п делится на пятую степень простого числа (Choie et al. 2007 г. ).

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

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

относится ко всем п ≥ 3.

Связанная оценка была дана Джеффри Лагариас в 2002 году, который доказал, что гипотеза Римана эквивалентна утверждению, что:

${\displaystyle \sigma (n)<H_{n}+\log(H_{n})e^{H_{n}}}$

для каждого натуральное число п > 1, где ${\displaystyle H_{n}}$ это пth номер гармоники, (Лагариас 2002 ).

Смотрите также

• Свертки суммы делителей Перечисляет несколько тождеств, включающих функции делителей.
• Функция Эйлера (Функция Эйлера фи)
• Рефакторинговое число
• Таблица делителей
• Унитарный делитель

Примечания

1. Длинный (1972 г., п. 46)
2. Петтофреццо и Биркит (1970, п. 63)
3. Петтофреццо и Биркит (1970, п. 58)
4. Харди и Райт (2008), pp. 310 f, §16.7.
5. Эйлер, Леонард; Белл, Джордан (2004). «Замечание о суммах делителей». arXiv:математика / 0411587.
6. http://eulerarchive.maa.org//pages/E175.html, Decouverte d'une loi tout extraordinaire des nombres par rapport a la somme de leurs diviseurs
7. https://scholarlycommons.pacific.edu/euler-works/542/, De mirabilis proprietatibus numerorum pentagonalium
8. Харди и Райт (2008), pp. 326-328, §17.5.
9. Харди и Райт (2008), pp. 334-337, §17.8.
10. Харди и Райт (2008), pp. 338-341, §17.10.
11. Э. Кретцель (1981). Zahlentheorie. Берлин: VEB Deutscher Verlag der Wissenschaften. п. 130. (Немецкий)
12. Апостол (1976), п. 296. ошибка sfnp: нет цели: CITEREFApostol1976 (Помогите)
13. Харди и Райт (2008), pp. 342-347, §18.1.
14. Апостол (1976), Теорема 3.3. ошибка sfnp: нет цели: CITEREFApostol1976 (Помогите)
15. Харди и Райт (2008), pp. 347-350, §18.2.
16. Харди и Райт (2008), pp. 469-471, §22.9.

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

• Акбары, Амир; Фриггстад, Захари (2009), «Сверхизбыточные числа и гипотеза Римана» (PDF), Американский математический ежемесячный журнал, 116 (3): 273–275, Дои:10.4169 / 193009709X470128, заархивировано из оригинал (PDF) на 2014-04-11.
• Апостол, Том М. (1976), Введение в аналитическую теорию чисел, Тексты для бакалавриата по математике, Нью-Йорк-Гейдельберг: Springer-Verlag, ISBN  978-0-387-90163-3, Г-Н  0434929, Zbl  0335.10001
• Бах, Эрик; Шаллит, Джеффри, Алгоритмическая теория чисел, том 1, 1996, MIT Press. ISBN  0-262-02405-5, см. стр. 234 в разделе 8.8.
• Кавени, Джеффри; Николя, Жан-Луи; Сондоу, Джонатан (2011), «Теорема Робина, простые числа и новая элементарная переформулировка гипотезы Римана» (PDF), INTEGERS: Электронный журнал комбинаторной теории чисел, 11: A33, arXiv:1110.5078, Bibcode:2011arXiv1110.5078C
• Чой, YoungJu; Личиардополь, Николас; Мори, Питер; Соле, Патрик (2007), "О критерии Робина для гипотезы Римана", Журнал Теории Номеров Бордо, 19 (2): 357–372, arXiv:math.NT / 0604314, Дои:10.5802 / jtnb.591, ISSN  1246-7405, Г-Н  2394891, Zbl  1163.11059
• Грёнвалл, Томас Хакон (1913), «Некоторые асимптотические выражения в теории чисел», Труды Американского математического общества, 14: 113–122, Дои:10.1090 / S0002-9947-1913-1500940-6
• Харди, Г. Х.; Райт, Э.М. (2008) [1938], Введение в теорию чисел, Редакция Д. Р. Хит-Браун и Дж. Х. Сильверман. Предисловие Эндрю Уайлс. (6-е изд.), Оксфорд: Oxford University Press, ISBN  978-0-19-921986-5, Г-Н  2445243, Zbl  1159.11001
• Ивич, Александар (1985), Дзета-функция Римана. Теория дзета-функции Римана с приложениями, A Wiley-Interscience Publication, Нью-Йорк и т.д .: John Wiley & Sons, стр. 385–440, ISBN  0-471-80634-X, Zbl  0556.10026
• Лагариас, Джеффри С. (2002), «Элементарная проблема, эквивалентная гипотезе Римана», Американский математический ежемесячник, 109 (6): 534–543, arXiv:математика / 0008177, Дои:10.2307/2695443, ISSN  0002-9890, JSTOR  2695443, Г-Н  1908008
• Лонг, Кальвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Лексингтон: Д. К. Хит и компания, LCCN  77171950
• Петтофреццо, Энтони Дж .; Биркит, Дональд Р. (1970), Элементы теории чисел, Энглвудские скалы: Prentice Hall, LCCN  77081766
• Рамануджан, Шриниваса (1997), "Сильно составные числа, аннотированные Жан-Луи Николя и Ги Робеном", Рамануджанский журнал, 1 (2): 119–153, Дои:10.1023 / А: 1009764017495, ISSN  1382-4090, Г-Н  1606180
• Робин, Гай (1984), "Великие валеринты соммы дивизионеров и гипотез Римана", Journal de Mathématiques Pures et Appliquées, Neuvième Série, 63 (2): 187–213, ISSN  0021-7824, Г-Н  0774171
• Уильямс, Кеннет С. (2011), Теория чисел в духе Лиувилля, Студенческие тексты Лондонского математического общества, 76, Кембридж: Издательство Кембриджского университета, ISBN  978-0-521-17562-3, Zbl  1227.11002

внешняя ссылка

• Вайсштейн, Эрик В. «Функция делителя». MathWorld.
• Вайсштейн, Эрик В. «Теорема Робина». MathWorld.
• Элементарное вычисление некоторых сумм сверток с участием функций делителей PDF с докладом Хуарда, Оу, Спирмана и Уильямса. Содержит элементарные (т.е. не опирающиеся на теорию модулярных форм) доказательства сверток суммы делителей, формулы для количества способов представления числа в виде суммы треугольных чисел и связанные с ними результаты.