Asymptotics of sums with Gaussian kernel and multiplicative coefficients

Full Text

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

Следует отметить, что анализ поведения дзета-функции Римана представляет собой сложную и нетривиальную задачу. Так, в работе [1]  продемонстрирована методика оценки среднего квадрата обобщения дзета-функции на коротких интервалах. В работе [2] дзета-функция и ее обобщение возникают при исследовании параметрических конечных сумм с биномиальными коэффициентами. В [3] проведен анализ конечных симметричных сумм Эйлера.

При анализе алгоритмов пузырьковой сортировки, обменной сортировки и поиска в бинарном дереве [4] возникает необходимость исследования конечной суммы следующего вида:
\[\begin{equation}
W(m, k, f) = \sum_{t=1}^{m-1} \exp\Bigl( {-\frac{t^2}{2m}} \Bigr)  t^k f(t),   
\tag{1}
\end{equation}\]
где $m \geqslant 2$, $m$, $k \in \mathbb{Z}$, а $f(t)$ — мультипликативная функция.

Для дальнейшего анализа потребуется представление выражения (1) в виде комплексного интеграла.

Утверждение. Функция $W(m, k, f),$ определенная формулой (1), допускает представление
\[
W(m, k, f) = \frac{1}{2\pi i} \int _{1/2-i\infty}^{1/2+i\infty} 
\Gamma(z) (2m)^z \biggl( \sum_{t=1}^{m-1} \frac{f(t)}{t^{2z-k}} \biggr) dz,
\]
где $\Gamma(z)$ — гамма-функция Эйлера.

Доказательство. Воспользуемся преобразованием Меллина для экспоненты. Пусть $x$ — произвольное положительное число. Тогда справедливо равенство [2, 4]:
\[\begin{equation}
e^{-x} = \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} 
\Gamma(z) x^{-z} dz, \quad c > 0.  
\tag{2}
\end{equation}\]

Подставляя в формулу (2) $x = t^2/(2m)$ из (1) получаем
\[\begin{equation}
W(m, k, f) = \frac{1}{2\pi i} \sum_{t=1}^{m-1} 
\biggl( \int_{c-i\infty}^{c+i\infty} \Gamma(z) t^{k-2z} (2m)^z dz \biggr) f(t). 
\tag{3}
\end{equation}\]

Пусть $z = x + iy$. Оценим интеграл в (3):
\[\begin{multline*}
\biggl| \int _{c-i\infty}^{c+i\infty} \Gamma(z) t^{k-2z} (2m)^z dz \biggr| 
\leqslant \int _{c-i\infty}^{c+i\infty} \bigl| \Gamma(z) t^{k-2z} (2m)^z \bigr| dy ={}
\\
{} = t^{k-2c} (2m)^c \lim_{b\to +\infty} 
\int _{c-ig_1(b)}^{c+ig_2(b)}  | \Gamma(c+iy)  | dy,  
\end{multline*}\]
где $g_1(x)$,  $g_2(x)$ — вещественнозначные функции вещественного переменного, такие что $\lim\limits_{x\to +\infty} g_1(x) = +\infty$, $\lim\limits_{x\to +\infty} g_2(x) = +\infty$.

Из [5] известна оценка для $|\Gamma(x+iy)|$. А именно, $\exists C_1$, $C_2 > 0$:
\[\begin{equation}
C_1 (|x+iy|+1)^{x-{1}/{2}} e^{- |y| {\pi}/{2}} \leqslant 
|\Gamma(x+iy)| \leqslant 
C_2 (|x+iy|+1)^{x-{1}/{2}} e^{- |y| {\pi}/{2}},  
\tag{4}
\end{equation}\]
где $x \in K \subset \mathbb{R}\setminus \{0, -1, -2, \ldots\}.$

В силу оценки (4) интеграл в (3) сходится абсолютно, поэтому можно изменить порядок суммирования и интегрирования. Полагая $c = {1}/{2}$, окончательно получаем
\[
W(m, k, f) = \frac{1}{2\pi i} \int _{{1}/{2}-i\infty}^{{1}/{2}+i\infty} 
\Gamma(z) (2m)^z \sum_{t=1}^{m-1} \frac{f(t)}{t^{2z-k}} dz.
\] $\square$

Следуя работам [3, 4], изложим метод комплексного интегрирования. Рассмотрим в комплексной плоскости прямоугольный контур $\gamma_1 =\gamma_1 \cup \gamma_2 \cup \gamma_3 \cup \gamma_4$ (рис. 1), который при фиксированных значениях $N$ и $M$ охватывает конечное число особых точек $\Gamma(z)$. При стремлении $N$ и $M$ к бесконечности в указанный контур попадают все особые точки подынтегральной функции.

Рис. 1. Контур интегрирования
[Fig. 1. Integration contour]

Выберем числа $N$ и $M$ достаточно большими. Согласно теореме Коши о вычетах, значение интеграла по замкнутому контуру равно сумме вычетов в особых точках, расположенных внутри контура. При этом интеграл по всему контуру можно представить как сумму интегралов по его составляющим:
\[\begin{equation}
\oint_\gamma f(z) dz = 2\pi i \sum_{k=1}^n \underset{z=z_k}{\operatorname{Res}} f(z) = \sum_{j=1}^4 \int_{\gamma_j} f(z) dz.
\tag{5}
\end{equation}\]

Пусть $\tau_k(n)$ обозначает количество решений в натуральных числах уравнения
\[
x_1 x_2 \cdots x_k = n,
\]
где $k$, $n \in \mathbb{N}$. Таким образом, функция $\tau_k(n)$ определяет число способов разложения натурального числа $n$ в произведение $k$ натуральных сомножителей.

Далее будем рассматривать $W(m, k, f)$, где положим $f(t) = \tau_k(t)$. В утверждении присутствует конечная сумма, верхний предел которой можно устремить к бесконечности. Поскольку
\[
\sum_{t=1}^\infty \frac{\tau_k(t)}{t^{2z-k}} = \sum_{t=1}^{m-1} \frac{\tau_k(t)}{t^{2z-k}} + \sum_{t=m}^\infty \frac{\tau_k(t)}{t^{2z-k}},
\]
справедливо равенство
\[\begin{equation}
\sum_{t=1}^{m-1} \frac{\tau_k(t)}{t^{2z-k}} = \sum_{t=1}^\infty \frac{\tau_k(t)}{t^{2z-k}} - \sum_{t=m}^\infty \frac{\tau_k(t)}{t^{2z-k}}.
\tag{6}
\end{equation}\]

Учитывая, что для любого $\varepsilon > 0$ выполняется $\tau_k(t) \ll C_\varepsilon t^\varepsilon$ [6], из (6) получаем асимптотическую оценку по $z$:
\[
\biggl| \sum_{t=m}^\infty \frac{\tau_k(t)}{t^{2z-k}} \biggr| \ll 
C_\varepsilon \sum_{t=m}^\infty \frac{1}{t^{2\operatorname{Re}  z - k - \varepsilon}},
\]
где ряд в правой части сходится при $\operatorname{Re}  z > ({1+k})/{2} + {\varepsilon}/{2}$. Следовательно,
\[
\lim_{m\to \infty} \sum_{t=m}^\infty \frac{\tau_k(t)}{t^{2z-k}} = 0.
\]

Известно [6], что для $n \in \mathbb{N}$ ряд Дирихле для $\tau_n(t)$ выражается через дзета-функцию Римана:
\[
\zeta^n(z) = \sum_{t=1}^\infty \frac{\tau_n(t)}{t^z}.
\]

Тогда можем записать:
\[
W(m, k, \tau_n(t)) = \frac{1}{2\pi i} \int _{1/2-i\infty}^{1/2+i\infty} \Gamma(z) (2m)^z \zeta^n(2z-k) dz.
\]

Отметим, что функцию, определяемую рядом Дирихле, можно аналитически продолжить левее точки $z = ({1+k})/{2}$ [6].

Оценим интеграл по контуру $\gamma_1 =  \{ z \in \mathbb{C} \mid z = t + iN,\ t \in  [ {1}/{2}, -\infty ) \}$:
\[\begin{multline}
\frac{1}{2\pi i} \int _{\gamma_1}  \Gamma(z) (2m)^z \zeta^n(2z-k) dz = {}
\\ 
{} = \frac{1}{2\pi i} \int _{ {1}/{2}}^{-\infty}  \Gamma(t+iN) (2m)^{t+iN}  \zeta^n(2t+2iN-k) dt \ll {} 
\\
\ll e^{- N{\pi}/{2}}   (N^{ {1}/{2}} \ln N )^n  \int _{ {1}/{2}}^{-\infty} 
  (|t+iN|+1 )^{t- {1}/{2}} (2m)^t dt.  
\tag{7}
\end{multline}\]

При $N \to \infty$ правая часть оценки (7) стремится к нулю благодаря экспоненциальному множителю. Интеграл по контуру $\gamma_2 = \{ z \in \mathbb{C} \mid {z = t - iN},$  ${t \in [{1}/{2}, -\infty)} \}$ оценивается аналогичным образом.

Далее оценим интеграл по контуру $\gamma_3 =  \{ z \in \mathbb{C} \mid z =  {1}/{2} + it - M,$  ${t \in (N, -N)} \}$:
\[\begin{multline}
\frac{1}{2\pi i} \int _{\gamma_3}   \Gamma(z) (2m)^z \zeta^n(2z-k) dz = {} 
\\ 
{} = \frac{1}{2\pi i} \int _N^{-N} \Gamma \Bigl( \frac{1}{2}+it-M \Bigr) (2m)^{ {1}/{2}+it-M} \zeta^n(1+2it-2M-k) dt \ll {} 
\\
{} \ll \frac{(2m)^{ {1}/{2}-M}}{(M-1)!} \int  _N^{-N} e^{- t{\pi}/{2} }  (t^{2M}\ln t )^n dt.  
\tag{8}
\end{multline}\]

При $M \to \infty$ и $t \to \infty$ интеграл (8) стремится к нулю. 

Рассмотрим теперь интеграл по контуру $\gamma_4 =  \{ z \in \mathbb{C} \mid z =  {1}/{2} + it,$ ${t \in (-N, N)} \}$: 
\[\begin{multline*}
\frac{1}{2\pi i} \int _{\gamma_4}   \Gamma(z) (2m)^z \zeta^n(2z-k) dz = {}
\\ 
{}= \frac{1}{2\pi i} \int_{-N}^N \Gamma \Bigl( \frac{1}{2}+it \Bigr) (2m)^{ {1}/{2}+it} \zeta^n \Bigl( \frac12 +it-k \Bigr) dz.
\end{multline*}\]

Согласно (5), данный интеграл полностью определяется вычетами в особых точках подынтегральной функции. В точке $z = -j$ имеем следующий вычет: 
\[
\underset{z=-j}{\operatorname{Res}}  \bigl( \Gamma(z) (2m)^z \zeta^n(2z-k) \bigr) = 
\frac{(-1)^j}{j! (2m)^j} \Bigl( \frac{B_{2j+k+1}}{2j+k+1} \Bigr)^n,
\]
где $B_{2j+k+1}$ — числа Бернулли.

Далее, подынтегральное выражение имеет полюс в точке $z = ({k+1})/{2}$. Для нахождения вычета выполним замену $w = (z -  ({k+1}))/{2}$ и разложим подынтегральную функцию в ряд Лорана:
\[\begin{multline}
\Gamma \Bigl(w + \frac{k+1}{2} \Bigr) (2m)^{w + ({k+1})/{2}} \zeta^n(2w + 1) ={} 
\\
{}= \Gamma \Bigl(\frac{k+1}{2}\Bigr) \Bigl(1 + w\psi\Bigl(\frac{k+1}{2}\Bigr) + O(w^2)\Bigr) \times {}
\\
{} \times  
(2m)^{({k+1})/{2}}  \bigl(1 + w\ln 2m + O(w^2)\bigr)  \Bigl(\frac{1}{2w} + \gamma + O(w)\Bigr)^n,  
\tag{9}
\end{multline}\]
где $\psi(z) = \frac{d}{dz}\ln\Gamma(z)$, $\gamma$ — постоянная Эйлера.

Рассмотрим последний сомножитель в (9) и применим бином Ньютона
\[
\Bigl(\frac{1}{2w} + \gamma\Bigr)^n = \sum_{p=0}^n \frac{C_n^p}{(2w)^{n-p}}\gamma^p, 
\]
выделяя слагаемые  
\[
C_n^{n-2} \Bigl( \frac{1}{2w} \Bigr)^{n- (n-2)} \gamma ^{n-2}+
C_n^{n-1} \Bigl( \frac{1}{2w} \Bigr)^{n- (n-1)} \gamma ^{n-1}=
\frac{n ( n-1) \gamma ^{n-2}}{8w^2}+ \frac{n\gamma ^{n-1}}{2w},
\]
которых достаточно для того, чтобы найти вычет  в точке $z=({k+1})/{2} $:
\[\begin{multline}
\underset{z=({k+1})/{2}}{\operatorname{Res}} \bigl(\Gamma(z)(2m)^z \zeta^n(2z-k)\bigr) = {} 
\\
{}=\Gamma\Bigl( \frac{k+1}{2} \Bigr) (2m)^{({k+1})/{2}} 
\Bigl( 1+w\psi \Bigl( \frac{k+1}{2} \Bigr)+O (w^2) \Bigr)\times{}
\\
{} \times
\bigl( 1+w\ln 2m+O (w^2) \bigr)
\Bigl( \frac{n (n-1)\gamma ^{n-2}}{8w^2}+\frac{n\gamma ^{n-1}}{2w} \Bigr) \approx{}
\\
\approx\Gamma\Bigl( \frac{k+1}{2} \Bigr)  (2m)^{({k+1})/{2}}
\Bigl( 
\frac{n(n-1)\gamma ^{n-2}}{8}\Bigl( \psi \Bigl(\frac{k+1}{2} \Bigr)+\ln 2m \Bigr)+\frac{n\gamma ^{n-1}}{2} 
\Bigr).  
\tag{10}
\end{multline}\]

Формула (10) позволяет анализировать все подобные интегралы в точке $z = (k+1)/2$ при $n \geqslant 1$. Например, для $n=1$:
\[
\underset{z=({k+1})/{2}}{\operatorname{Res}} \bigl(\Gamma(z)(2m)^z \zeta(2z-k)\bigr) \approx  
\frac{1}{2}\Gamma\Bigl(\frac{k+1}{2}\Bigr) (2m)^{ ({k+1})/{2}},
\]
что согласуется с известными результатами из [4, 7].

При $n=2$ вычет в точке $z=({k+1})/{2}$ вычисляется так:
\[\begin{multline*}
\underset{z=({k+1})/{2}}{\operatorname{Res}} \bigl(\Gamma(z)(2m)^z \zeta^2(2z-k)\bigr) 
\approx {}
\\
{}\approx \Gamma\Bigl(\frac{k+1}{2}\Bigr) (2m)^{({k+1})/{2}} 
\Bigl(\frac{1}{4}\Bigl(\psi\Bigl(\frac{k+1}{2}\Bigr) + \ln 2m\Bigr) + \gamma\Bigr).
\end{multline*}\]

Формула (10) позволяет находить оценки для случаев, когда подынтегральное выражение содержит многочлен от дзета-функции Римана:
\[
\Omega_q(m) = \frac{1}{2\pi i} \int _{1/2-i\infty}^{1/2+i\infty} \Gamma(z) (2m)^z P_q \bigl(\zeta(2z-k)\bigr) dz,
\]
где
\[
P_q\bigl(\zeta(2z-k)\bigr) = \sum_{l=0}^q p_l \zeta^l(2z-k).
\]

В случае $q=3$ 
\[\begin{multline*}
\Omega_3(m) = \frac{1}{2\pi i} \int _{1/2-i\infty}^{1/2+i\infty} \Gamma(z) (2m)^z P_3(\zeta(2z-k)) dz ={}
\\
{}= \frac{1}{2\pi i} \int _{1/2-i\infty}^{1/2+i\infty} \Gamma(z) (2m)^z \bigl(p_0 + p_1 \zeta(2z-k) + p_2 \zeta^2(2z-k) + p_3 \zeta^3(2z-k)\bigr) dz
\end{multline*}\]
оценка в точке $z=({k+1})/{2}$ определяется выражением
\[\begin{multline*}
\Omega_3(m) \approx \Gamma\Bigl(\frac{k+1}{2}\Bigr) (2m)^{({k+1})/{2}} 
\Bigl[p_0 + \frac{1}{2}p_1 + p_2 \Bigl(\frac{1}{4}\Bigl(\psi\Bigl(\frac{k+1}{2}\Bigr) + \ln 2m\Bigr) + \gamma\Bigr) + {}\\
{} + p_3 \Bigl(\frac{3}{4}\gamma\Bigl(\psi\Bigl(\frac{k+1}{2}\Bigr) + \ln 2m\Bigr) + \frac{3}{2}\gamma^2\Bigr)\Bigr].
\end{multline*}\]

Заключение

В работе предложен метод вычисления асимптотического поведения конечных сумм специального вида, основанный на сведении исходной суммы к комплексному интегралу. Ключевой особенностью исследуемого интеграла является наличие в подынтегральном выражении полинома от дзета-функции Римана. 
Основные результаты работы включают:

• разработку алгоритма вычисления асимптотического значения суммы через анализ особенностей подынтегральной функции;
• явное получение асимптотических выражений для случая полинома третьей степени от дзета-функции;
• анализ вычетов в особых точках, определяющих главный член асимптотики.

Полученные результаты могут быть применены для анализа сложности алгоритмов, связанных с обходом бинарных деревьев и задачами лучевого поиска, где возникают суммы рассматриваемого типа. 

Конкурирующие интересы. У нас нет конфликта интересов в отношении авторства и публикации этой статьи.
Авторский вклад и ответственность. Все авторы принимали участие в разработке концепции статьи и в написании рукописи. Авторы несут полную ответственность за предоставление окончательной рукописи в печать. Окончательная версия рукописи была одобрена всеми авторами.

About the authors

Alexandr S. Zinchenko

Moscow Aviation Institute (National Research University)

Email: zinchenkoas@mai.ru
ORCID iD: 0000-0001-7971-4572
SPIN-code: 7948-5040
Scopus Author ID: 59124941500
ResearcherId: AAJ-2633-2020
https://www.mathnet.ru/rus/person229294

Cand. Econom. Sci.; Associate Professor; Dept. of Mathematics

Russian Federation, 125993, Moscow, Volokolamskoe Shosse, 4

Alexander M. Romanenkov

Moscow Aviation Institute (National Research University)

Author for correspondence.
Email: romanaleks@gmail.com
ORCID iD: 0000-0002-0700-8465
SPIN-code: 7586-0934
Scopus Author ID: 57196480014
ResearcherId: AAH-9530-2020
https://www.mathnet.ru/rus/person29785

Cand. Techn. Sci., Associate Professor; Associate Professor; Dept. of Mathematics

Russian Federation, 125993, Moscow, Volokolamskoe Shosse, 4

References

Supplementary files