Меню Главная Случайная статья Настройки Функция делителей Материал из https://ru.wikipedia.org Функция делителей — арифметическая функция, связанная с делителями целого числа. Функция известна также под именем функция дивизоров. Применяется, в частности, при исследовании связи дзета-функции Римана и рядов Эйзенштейна для модулярных форм. Изучалась Рамануджаном, который вывел ряд важных равенств в модульной арифметике и арифметических тождествах. С этой функцией тесно связана суммирующая функция делителей, которая, как следует из названия, является суммой функции делителей. Содержание 1 Определение 2 Примеры 3 Таблица значений 4 Свойства 5 Связь с рядами 6 Асимптотическая скорость роста 7 Примечания 8 Ссылки Определение Функция «сумма положительных делителей» ${\displaystyle \sigma _{z}(n)}$ для вещественного или комплексного числа ${\displaystyle n}$ определяется как сумма ${\displaystyle z}$-х степеней положительных делителей числа n. Функцию можно выразить формулой ${\displaystyle \sigma _{z}(n)=\sum _{d|n}d^{z}\,\!,}$ где ${\displaystyle {d|n}}$ означает «d делит n». Обозначения d(n), (n) и (n) (от немецкого Teiler = делитель) используются также для обозначения 0(n), или функции числа делителей [1][2]. Если z равен 1, функция называется сигма-функцией или суммой делителей[3], и индекс часто опускается, так что (n) эквивалентна 1(n)[4]. Аликвотная сумма s(n) для n — это сумма собственных делителей (то есть всех делителей, за исключением самого n[5], и равна 1(n) n. Аликвотная последовательность для n образуется последовательным вычислением аликвотной суммы, то есть каждое последующее значение в последовательности равно аликвотной сумме предыдущего значения. Примеры Например, 0(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}}}$ в то время как 1(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 (почти совершенное) Случаи ${\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}}}$ поскольку, по определению, простое число делится только на единицу и самого себя. Если pn# означает праймориал, то ${\displaystyle \sigma _{0}(p_{n}\#)=2^{n}}$ Ясно, что ${\displaystyle 1<\sigma _{0}(n)<n}$ и ${\displaystyle \sigma (n)>n}$ для всех ${\displaystyle n>2}$. Функция делителей мультипликативна, но не вполне мультипликативна. Если мы запишем ${\displaystyle n=\prod _{i=1}^{r}p_{i}^{a_{i}}}$, где r = (n) — число простых делителей числа n, pi — i-й простой делитель, а ai — максимальная степень pi, на которую делится n, то ${\displaystyle \sigma _{x}(n)=\prod _{i=1}^{r}{\frac {p_{i}^{(a_{i}+1)x}-1}{p_{i}^{x}-1}}}$, что эквивалентно: ${\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}).}$ Если положить x = 0, получим, что d(n) равно: ${\displaystyle \sigma _{0}(n)=\prod _{i=1}^{r}(a_{i}+1).}$ Например, число n = 24 имеет два простых делителя — p1 = 2 и p2 = 3. Поскольку 24 — это произведение 2331, то a1 = 3 и a2 = 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) = (n) n. Здесь s(n) обозначает сумму собственных делителей числа n, то есть делителей, за исключением самого числа 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) = 0(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. Эта сумма появляется также в рядах Фурье для рядов Эйзенштейна и в инвариантах эллиптических функций Вейерштрасса. Асимптотическая скорость роста В терминах о-малое функция делителей удовлетворяет неравенству (см. стр. 296 книги Апостола[6]) для всех ${\displaystyle \epsilon >0,\quad d(n)=o(n^{\epsilon }).}$ Северин Вигерт дал более точную оценку ${\displaystyle \limsup _{n\to \infty }{\frac {\log d(n)}{\log n/\log \log n}}=\log 2.}$ С другой стороны, ввиду бесконечности количества простых чисел, ${\displaystyle \liminf _{n\to \infty }d(n)=2.}$ В терминах О-большое, Дирихле показал, что средний порядок функции делителей удовлетворяет следующему неравенству (см. теорему 3.3 книги Апостола) для всех ${\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 \limsup _{n\rightarrow \infty }{\frac {\sigma (n)}{n\,\log \log n}}=e^{\gamma },}$ где lim sup — верхний предел. Этот результат является теоремой Грёнвалла (Grnwall), опубликованной в 1913 году[7]. Его доказательство использует третью теорему Мертенса, которая утверждает, что ${\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\ln \ln n}$ (неравенство Робина) выполняется для всех достаточно больших n[8]. В 1984 году Гай Робин доказал, что неравенство верно для всех n 5041 в том и только в том случае, если гипотеза Римана верна[9]. Это теорема Робина и неравенство стало широко известно после доказательства теоремы. Наибольшее известное число, нарушающее неравенство — это n=5040. Если гипотеза Римана верна, то нет чисел, больших этого и нарушающих неравенство. Робин показал, что в случае ошибочности гипотезы существует бесконечно много чисел n, нарушающих неравенство, и известно, что наименьшее из таких чисел n 5041 должно быть сверхизбыточным числом[10]. Было показано, что неравенство выполняется для больших нечётных свободных от квадратов чисел, и что гипотеза Римана эквивалентна выполнению неравенства для всех чисел n, делящихся на пятую степень простого числа[11] Джефри Лагариас (Jeffrey Lagarias) в 2002 году доказал, что гипотеза Римана эквивалентна утверждению ${\displaystyle \sigma (n)\leq H_{n}+\ln(H_{n})e^{H_{n}}}$ для любого натурального n, где ${\displaystyle H_{n}}$ — n-е гармоническое число[12]. Робин доказал, что неравенство ${\displaystyle \ \sigma (n)<e^{\gamma }n\ln \ln n+{\frac {0.6483\ n}{\ln \ln n}}}$ выполняется для n 3 без каких-либо дополнительных условий. Примечания Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950 стр 46 последовательность A000005 в OEIS Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766 , стр 58 последовательность A000203 в OEIS последовательность A001065 в OEIS "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 Grnwall, Thomas Hakon (1913), «Some asymptotic expressions in the theory of numbers», Transactions of the American Mathematical Society 14: 113—122, doi:10.1090/S0002-9947-1913-1500940-6 Ramanujan, Srinivasa (1997), «Highly composite numbers, annotated by Jean-Louis Nicolas and Guy Robin», The Ramanujan Journal 1 (2): 119—153, doi:10.1023/A:1009764017495, ISSN 1382-4090, MR 1606180 Robin, Guy (1984), «Grandes valeurs de la fonction somme des diviseurs et hypothse de Riemann», Journal de Mathmatiques Pures et Appliques, Neuvime Srie 63 (2): 187—213, ISSN 0021-7824, MR 774171 Akbary, Amir; Friggstad, Zachary (2009), «Superabundant numbers and the Riemann hypothesis», American Mathematical Monthly 116 (3): 273—275, doi:10.4169/193009709X470128 YoungJu Choie, Nicolas Lichiardopol Pieter Moree Patrick Sol On Robin’s criterion for the Riemann hypothesis 2007 Journal de thorie des nombres de Bordeaux, ISSN=1246-7405, v19, issue 2, pages=357-372 Lagarias, Jeffrey C. (2002), «An elementary problem equivalent to the Riemann hypothesis», The American Mathematical Monthly 109 (6): 534—543, doi:10.2307/2695443, ISSN 0002-9890, JSTOR 2695443, MR 19080 Ссылки 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 PDF, авторы — Huard, Ou, Spearman, и Williams. Содержит элементарное (то есть не опирающееся на теорию модулярных форм) доказательство свертки суммы делителей, формулы для представления различными способами чисел как суммы треугольных чисел.