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

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Январь 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

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

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

Определение [ править ]

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

${\ Displaystyle \ сигма _ {х} (п) = \ сумма _ {д \ середина п} д ^ {х} \, \ !,}$

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

В аликвоту Sum сек ( п ) из п есть сумма собственных делителей (то есть, за исключением делители п само по себе, 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}}}$

Таблица значений [ править ]

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

Свойства [ править ]

Формулы при простых степенях [ править ]

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

${\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 членов для каждого сформированного правильного делителя.${\displaystyle p_{i}}$

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

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

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

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

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

Когда x  = 0, d ( n ) равно: ^[4]

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

Например, если n равно 24, есть два простых множителя ( p ₁ равно 2; p ₂ равно 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)}$

Для целого числа n , не являющегося квадратом, каждый делитель d числа n спарен с делителем n / d числа n и является четным; для квадратного целого числа один делитель (а именно ) не спарен с отдельным делителем и является нечетным. Аналогично, число нечетное тогда и только тогда, когда n - квадрат или дважды квадрат. ^{[ необходима цитата ]}${\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, например, то и s (n) = n - 1 , что делает n почти идеальным .${\displaystyle n=2^{k}}$${\displaystyle \sigma (n)=2\cdot 2^{k}-1=2n-1,}$

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

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

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

В 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 ( n ) =  σ ₀ ( n ) дает: ^[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 и  а . Это суммирование также появляется в виде ряда Фурье ряда Эйзенштейна и инвариантов эллиптических функций Вейерштрасса .

Ибо существует явное представление ряда с суммами Рамануджана в виде: ^[11]${\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]}$

Скорость роста [ править ]

В кратких обозначениях функция делителей удовлетворяет неравенству: ^{[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.}$

В Большом-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 - верхний предел . Этот результат представляет собой теорему Гренвалла , опубликованную в 1913 г. ( Grönwall 1913 ). Его доказательство использует 3-ю теорему Мертенса , которая гласит:

${\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 должно быть сверхизбыточным (Акбари и Фриггстад ​​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}+\log(H_{n})e^{H_{n}}}$

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

• Акбары, Амир; Friggstad, Захарьте (2009), "излишнее число и гипотеза Римана" (PDF) , American Mathematical Monthly , 116 (3): 273-275, DOI : 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
• Choie, YoungJu ; Личиардополь, Николас; Мори, Питер ; Соле, Патрик (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 , Zbl  1163.11059
• Гронуолл, Томас Хакон (1913), «Некоторые асимптотические выражения в теории чисел», Труды Американского математического общества , 14 : 113-122, DOI : 10,1090 / S0002-9947-1913-1500940-6
• Харди, GH ; Райт, EM (2008) [1938], Введение в теорию чисел , пересмотренное Д. Р. Хитом-Брауном и Дж . Х. Сильверманом . Предисловие Эндрю Уайлса . (6-е изд.), Оксфорд: Oxford University Press , ISBN 978-0-19-921986-5, Руководство по ремонту  2445243 , Zbl  1159.11001
• Ивич, Александар (1985), Дзета-функция Римана. Теория дзета-функции Римана с приложениями , Публикация Wiley-Interscience, Нью-Йорк и т.д .: John Wiley & Sons, стр. 385–440, ISBN 0-471-80634-X, Zbl  0556,10026
• Лагариас, Джеффри К. (2002), «Элементарная проблема, эквивалентная гипотезе Римана», The American Mathematical Monthly , 109 (6): 534–543, arXiv : math / 0008177 , doi : 10.2307 / 2695443 , ISSN  0002-9890 , JSTOR  2695443 , Руководство по ремонту  1908008
• Лонг, Кальвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Lexington: DC Heath and Company , LCCN  77171950
• Петтофреццо, Энтони Дж .; Биркит, Дональд Р. (1970), Элементы теории чисел , Englewood Cliffs: Prentice Hall , LCCN  77081766
• Ramanujan, Сринивас (1997), "Highly составных числа, аннотированные Жаны-Луи Николя и Гай Робин", Ramanujan Journal , 1 (2): диапазон 119-153, DOI : 10,1023 / A: 1009764017495 , ISSN  1382-4090 , MR  1606180
• Робин, Гай (1984), "Grandes valeurs de la fonction somme des diviseurs et hypothèse de Riemann", Journal de Mathématiques Pures et Appliquées , Neuvième Série, 63 (2): 187–213, ISSN  0021-7824 , MR  0774171
• Уильямс, Кеннет С. (2011), Теория чисел в духе Лиувилля , Студенческие тексты Лондонского математического общества, 76 , Кембридж: Cambridge University Press , ISBN 978-0-521-17562-3, Zbl  1227,11002

Внешние ссылки [ править ]

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