Главная
Новости
Строительство
Ремонт
Дизайн и интерьер

















Яндекс.Метрика





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



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

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

Определение

Функция «сумма положительных делителей» σ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, pii-й простой делитель, а 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 без каких-либо дополнительных условий.