Функция делителей — арифметическая функция, связанная с делителями целого числа. Функция известна также под именем функция дивизоров. Применяется, в частности, при исследовании связи дзета-функции Римана и рядов Эйзенштейна для модулярных форм. Изучалась Рамануджаном, который вывел ряд важных равенств в модульной арифметике и арифметических тождествах.
С этой функцией тесно связана суммирующая функция делителей, которая, как следует из названия, является суммой функции делителей.
Определение
Функция «сумма положительных делителей» σx(n) для вещественного или комплексного числа x определяется как сумма x-х степеней положительных делителей числа n. Функцию можно выразить формулой
σ x ( n ) = ∑ d | n d x , {displaystyle sigma _{x}(n)=sum _{d|n}d^{x},!,}где d | n {displaystyle {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:
σ 0 ( 12 ) = 1 0 + 2 0 + 3 0 + 4 0 + 6 0 + 12 0 = 1 + 1 + 1 + 1 + 1 + 1 = 6 , {displaystyle {egin{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) — сумма всех делителей:
σ 1 ( 12 ) = 1 1 + 2 1 + 3 1 + 4 1 + 6 1 + 12 1 = 1 + 2 + 3 + 4 + 6 + 12 = 28 , {displaystyle {egin{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) собственных делителей равна:
s ( 12 ) = 1 1 + 2 1 + 3 1 + 4 1 + 6 1 = 1 + 2 + 3 + 4 + 6 = 16. {displaystyle {egin{aligned}s(12)&=1^{1}+2^{1}+3^{1}+4^{1}+6^{1}&=1+2+3+4+6=16.end{aligned}}}Таблица значений
Случаи x = 2 {displaystyle x=2} , x = 3 {displaystyle x=3} и так далее входят в последовательности A001157, A001158, A001159, A001160, A013954, A013955 …
Свойства
Для целых, не являющихся квадратами, каждый делитель d числа n имеет парный делитель n/d, а значит, σ 0 ( n ) {displaystyle sigma _{0}(n)} всегда чётно для таких чисел. Для квадратов один делитель, а именно n {displaystyle {sqrt {n}}} , не имеет пары, так что для них σ 0 ( n ) {displaystyle sigma _{0}(n)} всегда нечётно.
Для простого числа p,
σ 0 ( p ) = 2 σ 0 ( p n ) = n + 1 σ 1 ( p ) = p + 1 {displaystyle {egin{aligned}sigma _{0}(p)&=2sigma _{0}(p^{n})&=n+1sigma _{1}(p)&=p+1end{aligned}}}поскольку, по определению, простое число делится только на единицу и самого себя. Если pn# означает праймориал, то
σ 0 ( p n # ) = 2 n {displaystyle sigma _{0}(p_{n}#)=2^{n}}
Ясно, что 1 < σ 0 ( n ) < n {displaystyle 1<sigma _{0}(n)<n} и σ ( n ) > n {displaystyle sigma (n)>n} для всех n > 2 {displaystyle n>2} .
Функция делителей мультипликативна, но не вполне мультипликативна.
Если мы запишем
n = ∏ i = 1 r p i a i {displaystyle n=prod _{i=1}^{r}p_{i}^{a_{i}}} ,где r = ω(n) — число простых делителей числа n, pi — i-й простой делитель, а ai — максимальная степень pi, на которую делится n, то
σ x ( n ) = ∏ i = 1 r p i ( a i + 1 ) x − 1 p i x − 1 {displaystyle sigma _{x}(n)=prod _{i=1}^{r}{frac {p_{i}^{(a_{i}+1)x}-1}{p_{i}^{x}-1}}} ,что эквивалентно:
σ x ( n ) = ∏ i = 1 r ∑ j = 0 a i p i j x = ∏ i = 1 r ( 1 + p i x + p i 2 x + ⋯ + p i a i x ) . {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) равно:
σ 0 ( n ) = ∏ i = 1 r ( a i + 1 ) . {displaystyle sigma _{0}(n)=prod _{i=1}^{r}(a_{i}+1).}Например, число n = 24 имеет два простых делителя — p1 = 2 и p2 = 3. Поскольку 24 — это произведение 23×31, то a1 = 3 и a2 = 1.
Теперь мы можем вычислить σ 0 ( 24 ) {displaystyle sigma _{0}(24)} :
σ 0 ( 24 ) = ∏ i = 1 2 ( a i + 1 ) = ( 3 + 1 ) ( 1 + 1 ) = 4 × 2 = 8. {displaystyle {egin{aligned}sigma _{0}(24)&=prod _{i=1}^{2}(a_{i}+1)&=(3+1)(1+1)=4 imes 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 — степень двойки, то есть n = 2 k {displaystyle n=2^{k}} , то σ ( n ) = 2 × 2 k − 1 = 2 n − 1 , {displaystyle sigma (n)=2 imes 2^{k}-1=2n-1,} и s(n) = n — 1, что делает n почти совершенным.
Как пример, для двух простых p и q (где p < q), пусть
n = p q . {displaystyle n=pq.}Тогда
σ ( n ) = ( p + 1 ) ( q + 1 ) = n + 1 + ( p + q ) , {displaystyle sigma (n)=(p+1)(q+1)=n+1+(p+q),} ϕ ( n ) = ( p − 1 ) ( q − 1 ) = n + 1 − ( p + q ) , {displaystyle phi (n)=(p-1)(q-1)=n+1-(p+q),}и
n + 1 = ( σ ( n ) + ϕ ( n ) ) / 2 , {displaystyle n+1=(sigma (n)+phi (n))/2,} p + q = ( σ ( n ) − ϕ ( n ) ) / 2 , {displaystyle p+q=(sigma (n)-phi (n))/2,}где φ(n) — функция Эйлера.
Тогда корни p и q уравнения:
( x − p ) ( x − q ) = x 2 − ( p + q ) x + n = x 2 − [ ( σ ( n ) − ϕ ( n ) ) / 2 ] x + [ ( σ ( n ) + ϕ ( n ) ) / 2 − 1 ] = 0 {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) :
p = ( σ ( n ) − ϕ ( n ) ) / 4 − [ ( σ ( n ) − ϕ ( n ) ) / 4 ] 2 − [ ( σ ( n ) + ϕ ( n ) ) / 2 − 1 ] , {displaystyle p=(sigma (n)-phi (n))/4-{sqrt {[(sigma (n)-phi (n))/4]^{2}-[(sigma (n)+phi (n))/2-1]}},} q = ( σ ( n ) − ϕ ( n ) ) / 4 + [ ( σ ( n ) − ϕ ( n ) ) / 4 ] 2 − [ ( σ ( n ) + ϕ ( 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) доказал, что
σ 0 ( n ) = σ 0 ( n + 1 ) {displaystyle sigma _{0}(n)=sigma _{0}(n+1)}встречается бесконечно много раз.
Связь с рядами
Два ряда Дирихле, использующие функцию делителей:
∑ n = 1 ∞ σ a ( n ) n s = ζ ( s ) ζ ( s − a ) , {displaystyle sum _{n=1}^{infty }{frac {sigma _{a}(n)}{n^{s}}}=zeta (s)zeta (s-a),}и при обозначении d(n) = σ0(n) получим
∑ n = 1 ∞ d ( n ) n s = ζ 2 ( s ) , {displaystyle sum _{n=1}^{infty }{frac {d(n)}{n^{s}}}=zeta ^{2}(s),}и второй ряд,
∑ n = 1 ∞ σ a ( n ) σ b ( n ) n s = ζ ( s ) ζ ( s − a ) ζ ( s − b ) ζ ( s − a − b ) ζ ( 2 s − a − b ) . {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)}}.}Ряд Ламбера, использующий функцию делителей:
∑ n = 1 ∞ q n σ a ( n ) = ∑ n = 1 ∞ n a q n 1 − q n {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 книги Апостола)
для всех ϵ > 0 , d ( n ) = o ( n ϵ ) . {displaystyle epsilon >0,quad d(n)=o(n^{epsilon }).}Северин Вигерт дал более точную оценку
lim sup n → ∞ log d ( n ) log n / log log n = log 2. {displaystyle limsup _{n o infty }{frac {log d(n)}{log n/log log n}}=log 2.}С другой стороны, ввиду бесконечности количества простых чисел,
lim inf n → ∞ d ( n ) = 2. {displaystyle liminf _{n o infty }d(n)=2.}В терминах О-большое, Дирихле показал, что средний порядок функции делителей удовлетворяет следующему неравенству (см. теорему 3.3 книги Апостола)
для всех x ≥ 1 , ∑ n ≤ x d ( n ) = x log x + ( 2 γ − 1 ) x + O ( x ) , {displaystyle xgeq 1,sum _{nleq x}d(n)=xlog x+(2gamma -1)x+O({sqrt {x}}),}где γ {displaystyle gamma } — постоянная Эйлера — Маскерони.
Задача улучшить границу O ( x ) {displaystyle O({sqrt {x}})} в этой формуле — это проблема Дирихле о делителях
Поведение сигма-функции неравномерно. Асимптотическую скорость роста сигма-функции можно выразить формулой:
lim sup n → ∞ σ ( n ) n log log n = e γ , {displaystyle limsup _{n ightarrow infty }{frac {sigma (n)}{n,log log n}}=e^{gamma },}где lim sup — верхний предел. Этот результат является теоремой Грёнвалла (Grönwall), опубликованной в 1913 году. Его доказательство использует третью теорему Мертенса, которая утверждает, что
lim n → ∞ 1 log n ∏ p ≤ n p p − 1 = e γ , {displaystyle lim _{n o infty }{frac {1}{log n}}prod _{pleq n}{frac {p}{p-1}}=e^{gamma },}где p — простое.
В 1915 году Рамануджан доказал, что при выполнении гипотезы Римана неравенство
σ ( n ) < e γ n log log n {displaystyle sigma (n)<e^{gamma }nlog log n} (неравенство Робина)выполняется для всех достаточно больших n. В 1984 году Гай Робин доказал, что неравенство верно для всех n ≥ 5041 в том и только в том случае, если гипотеза Римана верна. Это теорема Робина и неравенство стало широко известно после доказательства теоремы. Наибольшее известное число, нарушающее неравенство — это n=5040. Если гипотеза Римана верна, то нет чисел, больших этого и нарушающих неравенство. Робин показал, что в случае ошибочности гипотезы существует бесконечно много чисел n, нарушающих неравенство, и известно, что наименьшее из таких чисел n ≥ 5041 должно быть сверхизбыточным числом. Было показано, что неравенство выполняется для больших нечётных свободных от квадратов чисел, и что гипотеза Римана эквивалентна выполнению неравенства для всех чисел n, делящихся на пятую степень простого числа
Джефри Лагариас (Jeffrey Lagarias) в 2002 году доказал, что гипотеза Римана эквивалентна утверждению
σ ( n ) ≤ H n + ln ( H n ) e H n {displaystyle sigma (n)leq H_{n}+ln(H_{n})e^{H_{n}}}для любого натурального n, где H n {displaystyle H_{n}} — n-е гармоническое число.
Робин доказал, что неравенство
σ ( n ) < e γ n log log n + 0.6483 n log log n {displaystyle sigma (n)<e^{gamma }nlog log n+{frac {0.6483 n}{log log n}}}выполняется для n ≥ 3 без каких-либо дополнительных условий.