Endagorion's blog

By Endagorion, 8 years ago, In Russian,

С подачи e-maxx подзагрузился доказательством факта d(n) = o(nε). Факт, вроде бы, не очень известный и весьма содержательный с теоретической точки зрения (но не с практической, как будет видно дальше).

Ниже вы можете ознакомиться с моим вариантом доказательства. За комментарии и (тьфу-тьфу) указания ошибок буду благодарен. Если что-то непонятно, готов объяснить.

У меня при просмотре из Firefox 10 наблюдается такой спецэффект: при отображении записи рендерятся не все формулы, причем если обновлять страницу, то рендерится другое подмножество формул. =) Надеюсь, это поправят, а пока дочитав до места, где должна быть формула, надо обновлять, пока она не появится. =)

Итак, что же мы хотим доказать? Для любого ε > 0 верно, что , где d(n) — число делителей числа n.

Сперва заметим, что достаточно доказать, что d(n) = O(nε), т.е. существует положительное C, зависящее от ε, такое что d(n) ≤ Cnε. Действительно, пускай это так. Тогда d(n) ≤ Cnε / 2 = o(nε).

Приступим к доказательству d(n) = O(nε). Далее ε считаем фиксированным.

Пусть n = p1b1... pkbk, где все pi — различные простые числа и все bi натуральные (т.е. это каноническое разложение числа на степени простых). Тогда известно, что d(n) = (b1 + 1)... (bk + 1). Поделим d(n) на nε:

Мы доказываем, что это отношение не превосходит некоторого C.

Рассмотрим вспомогательную функцию , где k — некоторое положительное число, а ε ровно тот, что мы фиксировали (вид этой функции очень похож на вид одного множителя из последнего произведения). По ее виду сразу понятно, что если x стремится к 0 или к  + ∞, то fk(x) стремится к 0. Значит, в некоторой положительной точке она достигает максимума (таких точек может быть несколько), и в ней производная равна нулю. Для удобства мы будем дифференцировать логарифм fk(x), поскольку у него точка (или точки) максимума там же, где и у fk(x):

В точке максимума производная равна нулю, т.е. — глобальный максимум (т.к. других нулей у производной нет).

В любой другой точке x

Теперь применим доказанное к нашему отношению:

Из последней формулы видно, что если pj больше e2 / eε, то соответствующий член произведения будет меньше 1, поэтому, исходя из того, что все pj различны:

, где C зависит только от ε.

UPD: А вот еще прикол с этим доказательством, сам только что случайно наткнулся. Можно в качестве функции fk(x) взять как раз элемент произведения . Тогда при применении того же метода построения верхней оценки получится, что , что стремится к бесконечности с ростом k, и потому не годится для оценки произведения. Каково? =)

 
 
 
 
  • Vote: I like it
  • +67
  • Vote: I do not like it