Русская Википедия:Функция делителей
Фу́нкция дели́телей — арифметическая функция, связанная с делителями целого числа. Функция известна также под именем фу́нкция диви́зоров. Применяется, в частности, при исследовании связи дзета-функции Римана и рядов Эйзенштейна для модулярных форм. Изучалась Рамануджаном, который вывел ряд важных равенств в модульной арифметике и арифметических тождествах.
С этой функцией тесно связана суммирующая функция делителей, которая, как следует из названия, является суммой функции делителей.
Определение
Функция «сумма положительных делителей» σx(n) для вещественного или комплексного числа x определяется как сумма x-х степеней положительных делителей числа n. Функцию можно выразить формулой
- <math>\sigma_{x}(n)=\sum_{d|n} d^x\,\! ,</math>
где <math>{d|n}</math> означает «d делит n». Обозначения d(n), ν(n) и τ(n) (от немецкого Teiler = делитель) используются также для обозначения σ0(n), или функции числа делителей [1][2]. Если x равен 1, функция называется сигма-функцией или суммой делителей[3], и индекс часто опускается, так что σ(n) эквивалентна σ1(n)[4].
Шаблон:Якорь2 s(n) для n — это сумма собственных делителей (то есть всех делителей, за исключением самого n[5], и равна σ1(n) − n. Аликвотная последовательность для n образуется последовательным вычислением аликвотной суммы, то есть каждое последующее значение в последовательности равно аликвотной сумме предыдущего значения.
Примеры
Например, σ0(12) — количество делителей числа 12:
- <math>
\begin{align} \sigma_{0}(12) & = 1^0 + 2^0 + 3^0 + 4^0 + 6^0 + 12^0 \\ & = 1 + 1 + 1 + 1 + 1 + 1 = 6, \end{align} </math>
в то время как σ1(12) — сумма всех делителей:
- <math>
\begin{align} \sigma_{1}(12) & = 1^1 + 2^1 + 3^1 + 4^1 + 6^1 + 12^1 \\ & = 1 + 2 + 3 + 4 + 6 + 12 = 28, \end{align} </math>
и аликвотная сумма s(12) собственных делителей равна:
- <math>
\begin{align} s(12) & = 1^1 + 2^1 + 3^1 + 4^1 + 6^1 \\ & = 1 + 2 + 3 + 4 + 6 = 16. \end{align} </math>
Таблица значений
| 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 (почти совершенное) |
Случаи <math>x = 2</math>, <math>x = 3</math> и так далее входят в последовательности Шаблон:OEIS2C, Шаблон:OEIS2C, Шаблон:OEIS2C, Шаблон:OEIS2C, Шаблон:OEIS2C, Шаблон:OEIS2C …
Свойства
Для целых, не являющихся квадратами, каждый делитель d числа n имеет парный делитель n/d, а значит, <math>\sigma_{0}(n)</math> всегда чётно для таких чисел. Для квадратов один делитель, а именно <math>\sqrt n</math>, не имеет пары, так что для них <math>\sigma_{0}(n)</math> всегда нечётно.
Для простого числа p,
- <math>
\begin{align} \sigma_0(p) & = 2 \\ \sigma_0(p^n) & = n+1 \\ \sigma_1(p) & = p+1 \end{align} </math>
поскольку, по определению, простое число делится только на единицу и самого себя. Если pn# означает праймориал, то
- <math> \sigma_0(p_n\#) = 2^n</math>
Ясно, что <math>1 < \sigma_0(n) < n</math> и <math>\sigma(n) > n</math> для всех <math>n > 2</math>.
Функция делителей мультипликативна, но не вполне мультипликативна.
Если мы запишем
- <math>n = \prod_{i=1}^r p_i^{a_i}</math>,
где r = ω(n) — число простых делителей числа n, pi — i-й простой делитель, а ai — максимальная степень pi, на которую делится n, то
- <math>\sigma_x(n) = \prod_{i=1}^{r} \frac{p_{i}^{(a_{i}+1)x}-1}{p_{i}^x-1}</math>,
что эквивалентно:
- <math>
\sigma_x(n) = \prod_{i=1}^r \sum_{j=0}^{a_i} p_i^{j x} = \prod_{i=1}^r (1 + p_i^x + p_i^{2x} + \cdots + p_i^{a_i x}). </math>
Если положить x = 0, получим, что d(n) равно:
- <math>\sigma_0(n)=\prod_{i=1}^r (a_i+1).</math>
Например, число n = 24 имеет два простых делителя — p1 = 2 и p2 = 3. Поскольку 24 — это произведение 23×31, то a1 = 3 и a2 = 1.
Теперь мы можем вычислить <math>\sigma_0(24)</math>:
- <math>
\begin{align} \sigma_0(24) & = \prod_{i=1}^{2} (a_i+1) \\ & = (3 + 1)(1 + 1) = 4 \times 2 = 8. \end{align} </math>
Восемь делителей числа 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 — степень двойки, то есть <math>n = 2^k</math>, то <math>\sigma(n) = 2 \times 2^k - 1 = 2n - 1,</math> и s(n) = n — 1, что делает n почти совершенным.
Как пример, для двух простых p и q (где p < q), пусть
- <math>n = pq.</math>
Тогда
- <math>\sigma(n) = (p+1)(q+1) = n + 1 + (p+q),</math>
- <math>\phi(n) = (p-1)(q-1) = n + 1 - (p+q),</math>
и
- <math>n + 1 = (\sigma(n) + \phi(n))/2,</math>
- <math>p + q = (\sigma(n) - \phi(n))/2,</math>
где φ(n) — функция Эйлера.
Тогда корни p и q уравнения:
- <math>(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</math>
можно выразить через σ(n) и φ(n) :
- <math>p = (\sigma(n) - \phi(n))/4 - \sqrt{[(\sigma(n) - \phi(n))/4]^2 - [(\sigma(n) + \phi(n))/2 - 1]},</math>
- <math>q = (\sigma(n) - \phi(n))/4 + \sqrt{[(\sigma(n) - \phi(n))/4]^2 - [(\sigma(n) + \phi(n))/2 - 1]}.</math>
Зная n и либо σ(n), либо φ(n) (или зная p+q и либо σ(n), либо φ(n)) мы легко можем найти p и q.
В 1984 году Хиз-Браун (Roger Heath-Brown) доказал, что
- <math>\sigma_0(n) = \sigma_0(n + 1)</math>
встречается бесконечно много раз.
Связь с рядами
Два ряда Дирихле, использующие функцию делителей:
- <math>\sum_{n=1}^\infty \frac{\sigma_{a}(n)}{n^s} = \zeta(s) \zeta(s-a),</math>
и при обозначении d(n) = σ0(n) получим
- <math>\sum_{n=1}^\infty \frac{d(n)}{n^s} = \zeta^2(s),</math>
и второй ряд,
- <math>\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)}.</math>
Ряд Ламбера, использующий функцию делителей:
- <math>\sum_{n=1}^\infty q^n \sigma_a(n) = \sum_{n=1}^\infty \frac{n^a q^n}{1-q^n}</math>
для любого комплексного |q| ≤ 1 и a.
Эта сумма появляется также в рядах Фурье для рядов Эйзенштейна и в инвариантах эллиптических функций Вейерштрасса.
Асимптотическая скорость роста
В терминах о-малое функция делителей удовлетворяет неравенству (см. стр. 296 книги Апостола[6])
- для всех <math>\epsilon>0,\quad d(n)=o(n^\epsilon).</math>
Северин Вигерт дал более точную оценку
- <math>\limsup_{n\to\infty}\frac{\log d(n)}{\log n/\log\log n}=\log2.</math>
С другой стороны, ввиду бесконечности количества простых чисел,
- <math>\liminf_{n\to\infty} d(n)=2.</math>
В терминах О-большое, Дирихле показал, что средний порядок функции делителей удовлетворяет следующему неравенству (см. теорему 3.3 книги Апостола)
- для всех <math>x\geq1, \sum_{n\leq x}d(n)=x\log x+(2\gamma-1)x+O(\sqrt{x}),</math>
где <math>\gamma</math> — постоянная Эйлера — Маскерони.
Задача улучшить границу <math>O(\sqrt{x})</math> в этой формуле — это проблема Дирихле о делителях
Поведение сигма-функции неравномерно. Асимптотическую скорость роста сигма-функции можно выразить формулой:
- <math>
\limsup_{n\rightarrow\infty}\frac{\sigma(n)}{n\,\log \log n}=e^\gamma, </math>
где lim sup — верхний предел. Этот результат является теоремой Грёнвалла (Grönwall), опубликованной в 1913 году[7]. Его доказательство использует третью теорему Мертенса, которая утверждает, что
- <math>\lim_{n\to\infty}\frac{1}{\log n}\prod_{p\le n}\frac{p}{p-1}=e^{\gamma},</math>
где p — простое.
В 1915 году Рамануджан доказал, что при выполнении гипотезы Римана неравенство
- <math>\ \sigma(n) < e^\gamma n \log \log n </math> (неравенство Робина)
выполняется для всех достаточно больших n[8]. В 1984 году Гай Робин доказал, что неравенство верно для всех n ≥ 5041 в том и только в том случае, если гипотеза Римана верна[9]. Это теорема Робина и неравенство стало широко известно после доказательства теоремы. Наибольшее известное число, нарушающее неравенство — это n=5040. Если гипотеза Римана верна, то нет чисел, больших этого и нарушающих неравенство. Робин показал, что в случае ошибочности гипотезы существует бесконечно много чисел n, нарушающих неравенство, и известно, что наименьшее из таких чисел n ≥ 5041 должно быть сверхизбыточным числом[10]. Было показано, что неравенство выполняется для больших нечётных свободных от квадратов чисел, и что гипотеза Римана эквивалентна выполнению неравенства для всех чисел n, делящихся на пятую степень простого числа[11]
Джефри Лагариас (Jeffrey Lagarias) в 2002 году доказал, что гипотеза Римана эквивалентна утверждению
- <math> \sigma(n) \le H_n + \ln(H_n)e^{H_n}</math>
для любого натурального n, где <math>H_n</math> — n-е гармоническое число[12].
Робин доказал, что неравенство
- <math>\ \sigma(n) < e^\gamma n \log \log n + \frac{0.6483\ n}{\log \log n}</math>
выполняется для n ≥ 3 без каких-либо дополнительных условий.
Примечания
Ссылки
- Bach, Eric; Shallit, Jeffrey, Algorithmic Number Theory, volume 1, 1996, MIT Press. ISBN 0-262-02405-5, see page 234 in section 8.8.
- Шаблон:Mathworld
- Elementary Evaluation of Certain Convolution Sums Involving Divisor Functions PDF, авторы — Huard, Ou, Spearman, и Williams. Содержит элементарное (то есть не опирающееся на теорию модулярных форм) доказательство свертки суммы делителей, формулы для представления различными способами чисел как суммы треугольных чисел.
Шаблон:Числа по характеристикам делимости Шаблон:Rq
- ↑ Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77-171950 стр 46
- ↑ Шаблон:OEIS
- ↑ Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766 , стр 58
- ↑ Шаблон:OEIS
- ↑ Шаблон: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
- ↑ Grönwall, 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 hypothèse de Riemann», Journal de Mathématiques Pures et Appliquées, Neuvième Série 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 théorie 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
