Метод гиперболы Дирихле

Пример метода гиперболы Дирихле с $n=10,$ $a\approx 2.7,$ и $b\approx 3.7.$

В теории чисел — метод гиперболы Дирихле это метод вычисления суммы

$F(n)=\sum _{k=1}^{n}f(k),$

где $f$ является мультипликативной функцией . Первый шаг — найти пару мультипликативных функций $g$ и $h$ так что, используя свертку Дирихле , мы имеем $f=g\ast h$; тогда сумма станет

$F(n)=\sum _{k=1}^{n}\sum _{xy=k}^{}g(x)h(y),$

где внутренняя сумма пробегает все упорядоченные пары $(x,y)$ натуральных чисел таких, что $xy=k$. В декартовой плоскости эти пары лежат на гиперболе , и когда двойная сумма полностью разложена, возникает биекция между членами суммы и точками решетки в первом квадранте на гиперболах вида $xy=k$, где $k$ работает над целыми числами $1\leq k\leq n$: за каждую такую ​​точку $(x,y)$, сумма содержит слагаемое $g(x)h(y)$, и наоборот.

Позволять $a$ быть действительным числом, не обязательно целым, таким, что $1<a<n$, и пусть $b=n/a$. Тогда точки решетки можно разбить на три перекрывающиеся области: одна область ограничена $1\leq x\leq a$ и $1\leq y\leq n/x$, другая область ограничена $1\leq y\leq b$ и $1\leq x\leq n/y$, а третий ограничен $1\leq x\leq a$ и $1\leq y\leq b$. На диаграмме первая область — это объединение синей и красной областей, вторая область — объединение красного и зеленого, а третья область — красная. Обратите внимание, что этот третий регион является пересечением первых двух регионов. Таким образом , согласно принципу включения и исключения , полная сумма представляет собой сумму по первому региону плюс сумму по второму региону минус сумму по третьему региону. Это дает формулу

$F(n)=\sum _{k=1}^{n}f(k)=\sum _{k=1}^{n}\sum _{xy=k}^{}g(x)h(y)=\sum _{x=1}^{a}\sum _{y=1}^{n/x}g(x)h(y)+\sum _{y=1}^{b}\sum _{x=1}^{n/y}g(x)h(y)-\sum _{x=1}^{a}\sum _{y=1}^{b}g(x)h(y).$ ( 1 )

Примеры

Позволять $\sigma _{0}(n)$ — функция счета делителей , и пусть $D(n)$ будет его суммирующая функция :

$D(n)=\sum _{k=1}^{n}\sigma _{0}(k).$

Вычисление $D(n)$ наивно требует факторизации каждого целого числа в интервале $[1,n]$; улучшение можно произвести, используя модифицированное Решето Эратосфена , но для этого все равно потребуется ${\widetilde {O}}(n)$ время . С $\sigma _{0}$ допускает свертку Дирихле $\sigma _{0}=1\ast 1$, принимая $a=b={\sqrt {n}}$ в ( 1 ) дает формулу

$D(n)=\sum _{x=1}^{\sqrt {n}}\sum _{y=1}^{n/x}1\cdot 1+\sum _{y=1}^{\sqrt {n}}\sum _{x=1}^{n/y}1\cdot 1-\sum _{x=1}^{\sqrt {n}}\sum _{y=1}^{\sqrt {n}}1\cdot 1,$

что упрощается до

$D(n)=2\cdot \sum _{x=1}^{\sqrt {n}}\left\lfloor {\frac {n}{x}}\right\rfloor -\left\lfloor {\sqrt {n}}\right\rfloor ^{2},$

который можно оценить в $O\left({\sqrt {n}}\right)$ операции.

Метод имеет и теоретическое применение: например, Питер Густав Лежен Дирихле представил этот метод в 1849 году для получения оценки

$D(n)=n\log n+(2\gamma -1)n+O({\sqrt {n}}),$

где $\gamma$ – постоянная Эйлера–Машерони .

Внешние ссылки

• Обсуждение метода гиперболы Дирихле для вычислительных целей.