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

Функция делителей — арифметическая функция, связанная с делителями целого числа. Функция известна также под именем функция дивизоров. Применяется, в частности, при исследовании связи дзета-функции Римана и рядов Эйзенштейна для модулярных форм. Изучалась Рамануджаном, который вывел ряд важных равенств в модульной арифметике и арифметических тождеств.
 С этой функцией тесно связана суммирующая функция делителей, которая, как следует из названия, является суммой функции делителей.

Определение


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

σx(n)=d|ndx,
  где d|n означает «d делит n». Обозначения d(n), ν(n) и τ(n) (от немецкого Teiler = делитель) используются также для обозначения σ0(n), или функции числа делителей . Если x равен 1, функция называется сигма-функцией или суммой делителей, и индекс часто опускается, так что σ(n) эквивалентна σ1(n).
s(n) для n — это сумма собственных делителей (то есть делители, за исключением самого n, и равна σ1(n) − n. Аликвотная последовательность для n образуется последовательным вычислением аликвотной суммы, то есть каждое последующее значение в последовательности равно аликвотной сумме предыдущего значения.

Примеры


 Например, σ0(12) — количество делителей числа 12:


  \{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\}
 в то время как σ1(12) — сумма всех делителей:


  \{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\}
 и аликвотная сумма s(12) собственных делителей равна:


  \{begin\{align\} s(12) \& = 1\^1 + 2\^1 + 3\^1 + 4\^1 + 6\^1 \{\{ \& = 1 + 2 + 3 + 4 + 6 = 16. \{end\{align\}

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


nДелителиσ0(n)σ1(n)s(n) = σ1(n) − nКомментарии
11110квадрат: значение σ0(n) нечётно; степень 2: s(n) = n − 1 (почти совершенное)
21,2231простое: σ1(n) = 1+n, так что s(n) =1
31,3241простое: σ1(n) = 1+n, так что s(n) =1
41,2,4373квадрат: σ0(n) нечётно; степень 2: s(n) = n − 1 (почти совершенное)
51,5261простое: σ1(n) = 1+n, так что s(n) =1
61,2,3,64126первое совершенное число: s(n) = n
71,7281простое: σ1(n) = 1+n, так что s(n) =1
81,2,4,84157степень 2: s(n) = n − 1 (почти совершенное)
91,3,93134квадрат: σ0(n) нечётно
101,2,5,104188
111,112121простое: σ1(n) = 1+n, так что s(n) =1
121,2,3,4,6,1262816первое избыточное число: s(n) \textgreater n
131,132141простое: σ1(n) = 1+n, так что s(n) =1
141,2,7,1442410
151,3,5,154249
161,2,4,8,1653115квадрат: σ0(n) нечётно; степень 2: s(n) = n − 1 (почти совершенное)

 Случаи x=2, x=3 и так далее входят в последовательности , , , , , \ldots

Свойства


 Для целых, не являющихся квадратами, каждый делитель d числа n имеет парный делитель n/d, а значит, σ0(n) всегда чётно для таких чисел. Для квадратов один делитель, а именно n, не имеет пары, так что для них σ0(n) всегда нечетно.
 Для простого числа p,


  \{begin\{align\} \{sigma\_0(p) \& = 2 \{\{ \{sigma\_0(p\^n) \& = n+1 \{\{ \{sigma\_1(p) \& = p+1 \{end\{align\}
 поскольку, по определению, простое число делится только на единицу и самого себя. Если pn\# означает праймориал, то

σ0(pn#)=2n
  Ясно, что 1<σ0(n)<n и σ(n)>n для всех n>2.
 Функция делителей мультипликативна, но не вполне мультипликативна.
 Если мы запишем

n=i=1rpiai,
  где r = ω(n) — число простых делителей числа n, pi — i-й простой делитель, а ai — максимальная степень pi, на которую делится n, то

σx(n)=i=1rpi(ai+1)x1pix1,
  что эквивалентно:


  \{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\}).
 Если положить x = 0, получим, что d(n) равно:

σ0(n)=i=1r(ai+1).
  Например, число n = 24 имеет два простых множителя — p1 = 2 и p2 = 3. Поскольку 24 — это произведение 23×31, то a1 = 3 и a2 = 1.
 Теперь мы можем вычислить σ0(24):


  \{begin\{align\} \{sigma\_0(24) \& = \{prod\_\{i=1\}\^\{2\} (a\_i+1) \{\{ \& = (3 + 1)(1 + 1) = 4 \{times 2 = 8. \{end\{align\}
 Восемь делителей числа 24 — это 1, 2, 4, 8, 3, 6, 12, и 24.
 Заметим также, что s(n) = σ(n) − n. Здесь s(n) обозначает сумму собственных делителей числа n, то есть делителей, за исключением самого числа n. Эта функция используется для определения совершенности числа — для них s(n) = n. Если s(n) \textgreater n, n называется избыточным, а если s(n) \textless n, n называется недостаточным.
 Если n — степень двойки, то есть n=2k, то σ(n)=2×2k1=2n1, и s(n) = n — 1, что делает n почти совершенным.
 Как пример, для двух простых p и q (где p \textless q), пусть

n=pq.
  Тогда

σ(n)=(p+1)(q+1)=n+1+(p+q),
ϕ(n)=(p1)(q1)=n+1(p+q),
  и

n+1=(σ(n)+ϕ(n))/2,
p+q=(σ(n)ϕ(n))/2,
  где φ(n) — функция Эйлера.
 Тогда корни p и q уравнения:

(xp)(xq)=x2(p+q)x+n=x2[(σ(n)ϕ(n))/2]x+[(σ(n)+ϕ(n))/21]=0
  можно выразить через σ(n) и φ(n) :

p=(σ(n)ϕ(n))/4[(σ(n)ϕ(n))/4]2[(σ(n)+ϕ(n))/21],
q=(σ(n)ϕ(n))/4+[(σ(n)ϕ(n))/4]2[(σ(n)+ϕ(n))/21].
  Зная n и либо σ(n), либо φ(n) (или зная p+q и либо σ(n), либо φ(n)) мы легко можем найти p и q.
 В 1984 году Хиз-Браун (Roger Heath-Brown) доказал, что

σ0(n)=σ0(n+1)
  встречается бесконечно много раз.

Связь с рядами


 Два ряда Дирихле, использующие функцию делителей:

n=1σa(n)ns=ζ(s)ζ(sa),
  и при обозначении d(n) = σ0(n) получим

n=1d(n)ns=ζ2(s),
  и второй ряд,

n=1σa(n)σb(n)ns=ζ(s)ζ(sa)ζ(sb)ζ(sab)ζ(2sab).
  Ряд Ламбера, использующий функцию делителей:

n=1qnσa(n)=n=1naqn1qn
  для любого комплексного q ≤ 1 и a.
 Эта сумма появляется также в рядах Фурье для рядов Эйзенштейна и в инвариантах эллиптических функций Вейерштрасса.

Асимптотическая скорость роста


 В терминах о-малое, функция делителей удовлетворяет неравенству (см. стр. 296 книги Апостола)

  для всех ϵ>0,d(n)=o(nϵ).
  Северин Вигерт дал более точную оценку

lim supnlogd(n)logn/loglogn=log2.
  С другой стороны, ввиду бесконечности количества простых чисел,

lim infnd(n)=2.
  В терминах О-большое, Дирихле показал, что средний порядок функции делителей удовлетворяет следующему неравенству (см. теорему 3.3 книги Апостола)

  для всех x1,nxd(n)=xlogx+(2γ1)x+O(x),
  где γ — постоянная Эйлера — Маскерони.
 Задача улучшить границу O(x) в этой формуле — это проблема Дирихле о делителях
 Поведение сигма функции неравномерно. Асимптотическую скорость роста сигма функции можно выразить формулой:


  \{limsup\_\{n\{rightarrow\{infty\}\{frac\{\{sigma(n)\}\{n\{,\{log \{log n\}=e\^\{gamma,
 где lim sup — верхний предел. Этот результат является теоремой Грёнвалла (Grönwall), опубликованной в 1913 году. Его доказательство использует третью теорему Мертенса, которая утверждает, что

limn1lognpnpp1=eγ,
  где p — простое.
 В 1915 году Рамануджан доказал, что при выполнении гипотезы Римана неравенство

 σ(n)<eγnloglogn (неравенство Робина)
  выполняется для всех достаточно больших n. В 1984 году Гай Робин доказал, что неравенство верно для всех n ≥ 5041 в том и только в том случае, если гипотеза Римана верна. Это теорема Робина и неравенство стало широко известно после доказательства теоремы. Наибольшее известное число, нарушающее неравенство — это n=5040. Если гипотеза Римана верна, то нет чисел, больших этого и нарушающих неравенство. Робин показал, что в случае ошибочности гипотезы существует бесконечно много чисел n, нарушающих неравенство, и известно, что наименьшее из таких чисел n ≥ 5041 должно быть сверхизбыточным числом. Было показано, что неравенство выполняется для больших нечётных свободных от квадратов чисел, и что гипотеза Римана эквивалентна выполнению неравенства для всех чисел n, делящихся на пятую степень простого числа
 Джефри Лагариас (Jeffrey Lagarias) в 2002 году доказал, что гипотеза Римана эквивалентна утверждению

σ(n)Hn+ln(Hn)eHn
  для любого натурального n, где Hn — n-е гармоническое число.
 Робин доказал, что неравенство

 σ(n)<eγnloglogn+0.6483 nloglogn
  выполняется для n ≥ 3 без каких-либо дополнительных условий.