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

Арифметическая функция, связанная с делителями целого числа

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

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

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

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

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

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

Определение

Сумма положительных делителей функции σ _z ( n ) для действительного или комплексного числа z определяется как сумма z - х степеней положительных делителей числа n . Это можно выразить в сигма-нотации как

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

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

Аликвотная сумма s ( n ) числа n представляет собой сумму собственных делителей (то есть делителей, исключающих сам n , OEIS : A001065 ), и равна σ ₁ ( 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}}}$

σ _-1 ( n ) иногда называют индексом изобилия n , и мы имеем :

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

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

Случаи x = 2–5 перечислены в OEIS : A001157 – OEIS : A001160 , x = 6–24 перечислены в OEIS : A013954 – OEIS : A013972 .

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

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

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

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

потому что по определению делители простого числа равны 1 и самому себе. Кроме того, где p _n # обозначает первоначальный ,

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

поскольку n простых множителей допускают последовательность двоичного выбора ( или 1) из n членов для каждого сформированного правильного делителя. Однако, как правило, это не самые маленькие числа, число делителей которых равно степени двойки ; вместо этого наименьшее такое число может быть получено путем умножения первых n простых чисел Ферми – Дирака , степеней простых чисел, показатель степени которых равен степени двойки. ^[4] ${\displaystyle p_{i}}$

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

Функция делителя является мультипликативной (поскольку каждый делитель c произведения mn однозначно соответствует делителю a произведения m и делителю b произведения n ), но не полностью мультипликативна : ${\displaystyle \gcd(m,n)=1}$

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

где r  =  ω ( n ) — количество различных простых делителей числа n , pi _— i-й простой делитель, а ai — максимальная степень числа pi, на которую делится _n , тогда _имеем : [ 5 ^]

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

что при x  ≠ 0 эквивалентно полезной формуле: ^[5]

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

Когда x  = 0, это: ^[5] ${\displaystyle \sigma _{0}(n)}$

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

Этот результат может быть непосредственно выведен из того факта, что все делители однозначно определяются различными кортежами целых чисел с (т.е. независимым выбором для каждого ). ${\displaystyle n}$ ${\displaystyle (x_{1},x_{2},...,x_{i},...,x_{r})}$ ${\displaystyle 0\leq x_{i}\leq a_{i}}$ ${\displaystyle a_{i}+1}$ ${\displaystyle x_{i}}$

Например, если n равно 24, существует два простых делителя ( p ₁ равно 2; p ₂ равно 3); отметив, что 24 является произведением 2 ³ ×3 ¹ , a ₁ равно 3 и a ₂ равно 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.

Другие свойства и личности

Эйлер доказал замечательную повторяемость: ^{[6] [7] [8]}

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

где , если это происходит, и для , и являются последовательными парами обобщенных пятиугольных чисел ( OEIS : A001318 , начиная со смещения 1). Действительно, Эйлер доказал это посредством логарифмического дифференцирования тождества в своей теореме о пятиугольных числах . ${\displaystyle \sigma _{1}(0)=n}$ ${\displaystyle \sigma _{1}(x)=0}$ ${\displaystyle x<0}$ ${\displaystyle {\tfrac {1}{2}}\left(3i^{2}\mp i\right)}$

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

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

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

Например, для двух простых чисел пусть ${\displaystyle p,q:p<q}$

${\displaystyle n=p\,q}$.

Затем

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

выразить p и q только через σ ( n ) и φ ( n ), не требуя знания n или , как ${\displaystyle p+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 и либо или , либо, альтернативно, и либо или позволяет легко восстановить p и q . ${\displaystyle \sigma (n)}$ ${\displaystyle \varphi (n)}$ ${\displaystyle p+q}$ ${\displaystyle \sigma (n)}$ ${\displaystyle \varphi (n)}$

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

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

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

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

Два ряда Дирихле , включающие функцию делителя: ^[10]

${\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 ( n ) =  σ ₀ ( n ) дает: ^[10] ${\displaystyle \zeta }$

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

и идентичность Рамануджана ^[11]

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

что является частным случаем свертки Рэнкина – Сельберга .

Ряд Ламберта , включающий функцию делителя: ^[12]

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

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

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

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

Темпы роста

В обозначениях «маленькое о» функция делителя удовлетворяет неравенству: ^{[14] [15]}

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

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

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

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

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

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

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

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

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

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

${\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 (Рамануджан, 1997). Наибольшее известное значение, которое нарушает неравенство, — n = 5040 . В 1984 году Гай Робин доказал, что неравенство верно для всех n > 5040 тогда и только тогда, когда верна гипотеза Римана (Robin 1984). Это теорема Робина , и после него это неравенство стало известно. Робин, кроме того, показал, что если гипотеза Римана неверна, то существует бесконечное число значений n , которые нарушают неравенство, и известно, что наименьшее такое n > 5040 должно быть избыточным (Akbary & Friggstad 2009). Было показано, что неравенство справедливо для больших нечетных целых чисел и чисел без квадратов и что гипотеза Римана эквивалентна неравенству только для n , делящегося на пятую степень простого числа (Choie et al. 2007).

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

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

справедливо для всех n ≥ 3.

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

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

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

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

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

Примечания

1. Лонг (1972, стр. 46)
2. Петтофреззо и Биркит (1970, стр. 63)
3. Петтофреззо и Биркит (1970, стр. 58)
4. Рамануджан, С. (1915), «Высокосложные числа», Труды Лондонского математического общества , s2-14 (1): 347–409, doi : 10.1112/plms/s2_14.1.347; см. раздел 47, стр. 405–406, воспроизведено в Сборнике статей Шринивасы Рамануджана , Cambridge Univ. Пресс, 2015, стр. 124–125.
5. Hardy & Wright (2008), стр. 310 f, §16.7.
6. Эйлер, Леонард; Белл, Джордан (2004). «Наблюдение о суммах делителей». arXiv : math/0411587 .
7. https://scholarlycommons.pacific.edu/euler-works/175/, Découverte d'une loi tout extraordinaire des nombres par rapport à la somme de leurs diviseurs
8. https://scholarlycommons.pacific.edu/euler-works/542/, De mirabilis proprietatibus numerorum pentagonalium
9. Джоя и Вайдья (1967).
10. Hardy & Wright (2008), стр. 326–328, §17.5.
11. Харди и Райт (2008), стр. 334–337, §17.8.
12. Харди и Райт (2008), стр. 338–341, §17.10.
13. Э. Кретцель (1981). Залентеория . Берлин: VEB Deutscher Verlag der Wissenschaften. п. 130.(Немецкий)
14. Апостол (1976), с. 296.
15. Hardy & Wright (2008), стр. 342–347, §18.1.
16. Апостол (1976), Теорема 3.3.
17. Харди и Райт (2008), стр. 347–350, §18.2.
18. Харди и Райт (2008), стр. 469–471, §22.9.

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

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

Внешние ссылки

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