2
$\begingroup$

For $\alpha>2$, i want to find the speed of convergence of $$S_n=\sum_{i=1}^n\sum_{j=n-i+1}^n i^{-\alpha}j^{-\alpha}.$$

In particular, i want $\sum_{i=1}^n\sum_{j=n-i+1}^n i^{-\alpha}j^{-\alpha}\leq Cn^{-\alpha+1-\epsilon}$ for some $C,\epsilon>0$.

My first attempt was to estimate by integrals $$\sum_{i=1}^n\sum_{j=n-i+1}^n i^{-\alpha}j^{-\alpha}\leq \int_{x=1}^n\int_{y=n-x+1}^n x^{-\alpha}y^{-\alpha}dxdy\\=\int_{x=1}^nx^{-\alpha}(n^{-\alpha+1})dx+\int_{x=1}^nx^{-\alpha}(n-x+1)^{-\alpha+1}dx$$ but the second integral on the left is not an easy one.

My second attempt was to show that $$n^{\alpha-1+\epsilon}\sum_{i=1}^n\sum_{j=n-i+1}^n i^{-\alpha}j^{-\alpha}$$ is bounded.

$\endgroup$

5 Answers 5

4
$\begingroup$

I'm not an expert at this, but looking at your first attempt's integration,

$$I = \int_1^n x^{-\alpha} (n-x+1)^{-\alpha+1} dx = \int_1^n (n - x + 1)^{-\alpha} x^{-\alpha + 1} dx$$

$$\begin{align*} I &= \frac{1}{2}\int_1^n x^{-\alpha} (n - x + 1)^{-\alpha} (n + 1) dx \\ &= \frac{n + 1}{2}\int_{-\frac{n - 1}{2}}^{\frac{n - 1}{2}} \left(\frac{(n + 1)^2}{4} - x^2\right)^{-\alpha} dx & x' = x - \frac{n + 1}{2} \\ &= v\int_{1 - v}^{v - 1} \frac{1}{(v^2 - x^2)^{\alpha}} dx\end{align*}$$

Where $v = \frac{n + 1}{2}$ is a constant. Perhaps someone else can fill in the integration steps (which should either be a trig-sub recurrence or partial fractions), but by using Sage, I get that

$$I \sim C(\alpha) v^{-\alpha}$$

Where $C(\alpha)$ is a constant that depends only on $\alpha$ and not $n$. In particular, your $\epsilon$ seems to be $1$ but should be $\left(\frac{n}{2}\right)^{-\alpha}$ instead.

a = 5
v = var('v')
it = integrate(1/(v^2-x^2)^a,x,1-v,v-1)
print([it.subs(v=10^k).log(10).n() for k in range(1, 8)])

Hope this helps at least slightly.

$\endgroup$
4
  • $\begingroup$ Your evaluation is correct: $\displaystyle S\sim 2\,\zeta(a-1)\,n^{-a}+o(n^{-a})$ $\endgroup$
    – Svyatoslav
    May 18 at 14:50
  • $\begingroup$ @Svyatoslav how did you arrive at that? $\endgroup$
    – Emmbee1
    May 20 at 13:11
  • $\begingroup$ Please see my heuristic evaluation in the post below $\endgroup$
    – Svyatoslav
    May 20 at 13:28
  • $\begingroup$ In fact, it was very interesting problem to solve :) I did it not rigorously, but it can be done in a more rigorous mode. The answer also shows why the condition $a>2$ is important. During the evaluation this condition was also used. $\endgroup$
    – Svyatoslav
    May 20 at 13:35
3
+25
$\begingroup$

Starting from @Gareth Ma's answer $$I_a=v\int_{1 - v}^{v - 1} \frac{1}{(v^2 - x^2)^{\alpha}}\, dx$$ $$I_a=2\, (v-1)\, v^{1-2 a} \,\, _2F_1\left(\frac{1}{2},a;\frac{3}{2};\frac{(v-1)^2}{v^2}\right)$$

What it seems is that $v^aI_a$ is almost a straight line with positive slope.

$\endgroup$
2
$\begingroup$

$$I_a=\int_{1}^n\int_{n-x+1}^n x^{-a}y^{-a}\,dy\,dx$$ $$I_a=\frac 1{a-1}\int_{1}^n \left(n^a (n-x+1)-n (n-x+1)^a\right) (n x (n-x+1))^{-a}\,dx$$ $$(a-1)n^aI_a=\frac{n \left(n^{1-a}-1\right)}{a-1}+$$ $$\frac{(n+1)^{1-a} \left(n^a \, _2F_1\left(1-a,a;2-a;\frac{1}{n+1}\right)-n \, _2F_1\left(1-a,a;2-a;\frac{n}{n+1}\right)\right)}{a-1}+$$ $$\frac{(n+1)^{-a} \left(n^2 \, _2F_1\left(2-a,a;3-a;\frac{n}{n+1}\right)-n^a \, _2F_1\left(2-a,a;3-a;\frac{1}{n+1}\right)\right)}{a-2}$$

Now, for large values of $n$ $$\, _2F_1\left(1-a,a;2-a;\frac{1}{n+1}\right) \quad \to \quad1$$ $$\, _2F_1\left(1-a,a;2-a;\frac{n}{n+1}\right)\quad \to\quad \frac{\sqrt{\pi } 2^{2 a-1} \Gamma (2-a)}{\Gamma \left(\frac{3}{2}-a\right)}$$ $$\, _2F_1\left(2-a,a;3-a;\frac{1}{n+1}\right) \quad \to \quad1$$ $$\, _2F_1\left(2-a,a;3-a;\frac{n}{n+1}\right)\quad \to\quad-\frac{\sqrt{\pi } 4^{a-1} (a-2) \Gamma (1-a)}{\Gamma \left(\frac{3}{2}-a\right)}$$ which, hoping no mistakes, makes $$I_a=\frac{a-1}{4} (n+1)^{-a}\Bigg[4\frac{(a-2) n-1}{(a-2) (a-1)} +\frac{\sqrt{\pi } 4^a (n+2) n^{1-a} \Gamma (1-a)}{\Gamma \left(\frac{3}{2}-a\right)}\Bigg]$$

For $n=100$ and $a=2\pi$, this gives $2.4463\times 10^{-14}$ while the exact value would be the same

$\endgroup$
2
$\begingroup$

We will find the leading term of the asymptotics of the sum at $n\to\infty$.

Let's denote $\displaystyle S(a,n)=\sum_{i=1}^n\sum_{j=n-i+1}^ni^{-a}j^{-a}\tag*{}$

Using the relation $j^{-a}=\frac{1}{\Gamma(a)}\int_0^\infty t^{a-1}e^{-jt}dt\,$, we can present our sum as

$\displaystyle S=\frac{1}{\Gamma^2(a)}\int_0^\infty\int_0^\infty dt\,ds\,t^{a-1}s^{a-1}\sum_{i=1}^n\sum_{j=n-i+1}^ne^{-jt}e^{-is}\tag*{}$ Performing summation

$\displaystyle S=\frac{1}{\Gamma^2(a)}\int_0^\infty\int_0^\infty dt\,ds\frac{t^{a-1}s^{a-1}}{e^t-1}e^{-s}\Big(\frac{e^{-nt}-e^{-ns}}{e^{-t}-e^{-s}}-e^{-nt}\frac{1-e^{-ns}}{1-e^{-s}}\Big)=I_1+I_2\tag*{}$

The second integral is easier to evaluate - it is factorized, and we can write $I_2=-\frac{1}{\Gamma^2(a)}I_AI_B$, where $\displaystyle I_A=\int_0^\infty\frac{t^{a-1}e^{-nt}}{e^t-1}dt=\frac{1}{n^a}\int_0^\infty\frac{x^{a-1}e^{-x}}{e^{x/n}-1}dt\tag*{}$

Heuristically, we note that $x=0$ is a regular point, and that at $\,x\sim\sqrt n\quad e^{-x}\sim e^{-\sqrt n}\ll1$. At the same time for such $\,x\quad\frac{x}{n}\sim\frac{1}{\sqrt n}\ll1$. It means that with the accuracy up to exponentially small corrections we can decompose $e^{x/n}$ into the series and integrate term by term:

$\displaystyle I_A=\frac{1}{n^a}\int_0^\infty\frac{x^{a-1}e^{-x}}{\frac{x}{n}\big(1+\frac{x}{2n}+..\big)}dt=n^{1-a}\int_0^\infty x^{a-2}e^{-x}dx-\frac{n^{-a}}{2}\int_0^\infty x^{a-1}e^{-x}dx+...\tag*{}$

$\displaystyle I_A=n^{1-a}\Gamma(a-1)-\frac{n^{-a}}{2}\Gamma(a)+O(n^{-a-1})\tag*{}$

In the same way we evaluate $I_B$:

$\displaystyle I_B=\int_0^\infty s^{a-1}\frac{1-e^{-ns}}{e^s-1}ds=\int_0^\infty \frac{s^{a-1}}{e^s-1}ds-n^{1-a}\int_0^\infty y^{a-2}e^{-y}dy\,+...\tag*{}$

Using the relation $\int_0^\infty \frac{s^{a-1}}{e^s-1}ds=\Gamma(a)\zeta(a)$

$\displaystyle I_B=\Gamma(a)\zeta(a)-n^{1-a}\Gamma(a-1)+O(n^{-a})\tag*{}$

Keeping only the terms of the orders $n^{1-a}$ and $n^{-a}$ (we will see below that we need both),

$\displaystyle I_2=-\frac{1}{\Gamma^2(a)}I_A\cdot I_B=-\frac{n^{1-a}\zeta(a)}{a}+\frac{n^{-a}\zeta(a)}{2}+o(n^{-a})\qquad(1)\tag*{}$

I would like to point out that the rigorous proof of this evaluation is straightforward - I omitted it for reasons of brevity, since the solution is already quite long.

The similar approach we use to evaluate $I_1$. This integral is more complicated; it is not factorized, but due to the presence of the $e^{-nt}$ and $e^{-ns}$ the corresponding variable contributes only near zero. Noting also that at $a>2$ the function is integrable at zero, we can use the similar decomposition. The more detailed proof of validity of such approach and some subtle points are discussed in the Addendum below.

$\displaystyle I_1=\frac{1}{\Gamma^2(a)}\int_0^\infty\int_0^\infty \frac{t^{a-1}s^{a-1}}{e^t-1}\frac{e^{-nt}-e^{-ns}}{e^{-t}-e^{-s}}e^{-s}\,dt\,ds=I_C+I_D\tag*{}$ where we denote $\displaystyle I_C=\frac{1}{\Gamma^2(a)}\int_0^\infty\int_0^\infty \frac{t^{a-1}s^{a-1}}{e^t-1}\frac{e^{-nt}}{e^{-t}-e^{-s}}e^{-s}\,dt\,ds\tag*{}$

$\displaystyle =\frac{1}{\Gamma^2(a)}\int_0^\infty\int_0^\infty \frac{t^{a-1}s^{a-1}}{1-e^{-t}}\frac{e^{-nt}}{e^s-e^t}\,dt\,ds\tag*{}$

$\displaystyle =\frac{n^{-a}}{\Gamma^2(a)}\int_0^\infty\int_0^\infty \frac{x^{a-1}s^{a-1}}{1-e^{-x/n}}\frac{e^{-x}}{e^s-e^{x/n}}\,dx\,ds\tag*{}$

Decomposing $e^{x/n}$ into the series, we can write $I_C=J_1+J_2+J_3+o(n^{-a})$, where the evaluation of all three integrals is straightforward:

$\displaystyle J_1=\frac{n^{1-a}}{\Gamma^2(a)}\int_0^\infty\int_0^\infty x^{a-2}e^{-x}\frac{s^{a-1}}{e^s-1}\,dx\,ds=\frac{n^{1-a}\zeta(a)}{a}\qquad(2)\tag*{}$

$\displaystyle J_2=\frac{n^{-a}}{2\Gamma^2(a)}\int_0^\infty\int_0^\infty x^{a-1}e^{-x}\frac{s^{a-1}}{e^s-1}\,dx\,ds=\frac{n^{-a}\zeta(a)}{2}\qquad(3)\tag*{}$

$\displaystyle J_3=\frac{n^{-a}}{\Gamma^2(a)}\int_0^\infty\int_0^\infty x^{a-1}e^{-x}\frac{s^{a-1}}{(e^s-1)^2}\,dx\,ds=n^{-a}\big(\zeta(a-1)-\zeta(a)\big)\quad(4)\tag*{}$

In the same way $\displaystyle I_D=-\frac{1}{\Gamma^2(a)}\int_0^\infty\int_0^\infty \frac{t^{a-1}s^{a-1}}{e^t-1}\frac{e^{-ns}}{e^{-t}-e^{-s}}e^{-s}\,dt\,ds=n^{-a}\zeta(a-1)+o(n^{-a})\quad(5)\tag*{}$

Taking all together $\big((1)-(5)\big)$,

$\displaystyle S=I_1+I_2=I_C+I_D+I_2\tag*{}$

$\displaystyle =\frac{n^{1-a}\zeta(a)}{a}+\frac{n^{-a}\zeta(a)}{2}+n^{-a}\big(\zeta(a-1)-\zeta(a)\big)+n^{-a}\zeta(a-1)-\frac{n^{1-a}\zeta(a)}{a}+\frac{n^{-a}\zeta(a)}{2}+o(n^{-a})\tag*{}$

and we get the desired asymptotics at $n\to\infty\,$:

$\displaystyle \boxed{\boxed{\,\,S(a,n)=2\,\zeta(a-1)\,n^{-a}+o(n^{-a}),\,\,a>2\,\,}}\tag*{}$


$\mathbf{Numeric \,check}$ at WolframAlpha:

$\displaystyle a=3,\, n=10\,000\quad S=3.29 \cdot10^{-12};\quad 2\,\zeta(a-1)\,n^{-a}=3.29 \cdot10^{-12}\tag*{}$

$\displaystyle a=4,\, n=1\,000\quad S=2.405 \cdot10^{-12};\quad 2\,\zeta(a-1)\,n^{-a}=2.404 \cdot10^{-12}\tag*{}$


$\mathbf{Addendum}$

Now I want to outline the proof of the legitimacy of the manipulations above. The logic is the following: using different scales for the functions of the integrand we can show that only one interval contributes to the main asymptotics terms $\sim n^{1-a}, \,n^{-a}$; all other intervals give the smaller asymptotics terms. I will not prove every evaluation, but just show how it works with respect to the leading term of one of the integrals.

First of all we note that though $I_C+I_D$ does not contains singularities, we can also consider $I_C$ and $I_D$ separately - each one converges in the principal value sense. Let's take $I_C$ as an example.

$\displaystyle I_C=\frac{n^{-a}}{\Gamma^2(a)}\int_0^\infty\int_0^\infty\frac{x^{a-1}s^{a-1}}{1-e^{-x/n}}\frac{e^{-x}}{e^s-e^{x/n}}dxds\tag*{}$

If we choose $x\in[0;n^{1-\beta}]$, where $0<\beta<1$, we see that for $x\sim n^{1-\beta}\,\,e^{-x}\sim e^{-n^{1-\beta}}\ll1$, but still $\frac{x}{n}\sim n^{-\beta}\ll1$. It means that the integrand becomes exponentially small, but $e^{x/n}$ can be decomposed into the series. With the accuracy up to exponentially small corrections ($\sim e^{-n^{1-\beta}}$),

$\displaystyle I_C\approx\frac{n^{-a}}{\Gamma^2(a)}\int_0^{n^{1-\beta}}dx\int_0^\infty\frac{x^{a-1}s^{a-1}}{\frac{x}{n}+...}\,\frac{e^{-x}}{e^s-1-\frac{x}{n}-...}dxds\tag*{}$

... and, keeping only the first power of $\frac{x}{n}$

$\displaystyle I_C\approx\frac{n^{1-a}}{\Gamma^2(a)}\int_0^{n^{1-\beta}}dx\int_0^\infty \frac{x^{a-2}s^{a-1}e^{-x}}{e^s-1-\frac{x}{n}}ds=\frac{n^{1-a}}{\Gamma^2(a)}\int_0^{n^{1-\beta}}x^{a-2}e^{-x}dx\int_0^\infty \frac{s^{a-1}}{e^s-1-\frac{x}{n}}ds\tag*{}$

At this stage we introduce $\alpha\in(0;1)$ such, that $\alpha<\beta\,$ (the strict requirement for $\alpha$ we will define in the end). Then $n^{-\alpha}\gg n^{-\beta}$ and at $\,x\sim n^{1-\beta}\quad n^{-\alpha}\gg\frac{x}{n}\sim n^{-\beta}$.

We split the integral with respect to $s$ into two parts:

$\displaystyle \int_0^\infty \frac{s^{a-1}}{e^s-1-\frac{x}{n}}ds=\int_0^{n^{-\alpha}} \frac{s^{a-1}}{e^s-1-\frac{x}{n}}ds+\int_{n^{-\alpha}}^\infty \frac{s^{a-1}}{e^s-1-\frac{x}{n}}ds=I_1+I_2\tag*{}$

Regarding $I_1: \,\, s\ll1$ on the whole interval; decomposing $e^s$

$\displaystyle I_1\approx\int_{n^{-\alpha}}^\infty \frac{s^{a-1}}{s-\frac{x}{n}}ds=\Big(\frac{x}{n}\Big)^{a-1}\int_0^{n^{1-\alpha}/x} \frac{t^{a-1}}{t-1}ds\tag*{}$

$\displaystyle =\Big(\frac{x}{n}\Big)^{a-1}\bigg(-\int_0^1\frac{t^{a-1}}{1-t}dt+\int_1^2\frac{t^{a-1}}{t-1}dt+\int_2^{n^{1-\alpha}/x}\frac{t^{a-1}}{1-t}dt\bigg)\tag*{}$

Evaluation is straightforward. Bearing in mind that for $x\in [0;n^{1-b}]\quad\frac{n^{1-\alpha}}{x}\in [n^{\beta-\alpha};\infty)$ and that $n^{\beta-\alpha}\to \infty$ at $n\to\infty\,\,(\beta>\alpha$ by the choice), we have for the leading term

$\displaystyle I_1\approx\Big(\frac{x}{n}\Big)^{a-1}\bigg(F(a)+G(a)\Big(\frac{n^{1-\alpha}}{x}\Big)^{a-1}\bigg)=\Big(\frac{x}{n}\Big)^{a-1}F(a)+G(a)n^{-\alpha(a-1)}\tag*{}$

where $F(a), G(a)$ - regular functions of $a$, not depending on $n$. While evaluating $I_2$ we notice that $s\gg \frac{x}{n}$ on the interval of integration. It means that we can drop $\frac{x}{n}$:

$\displaystyle I_2\approx \int_{n^{-\alpha}}^\infty\frac{s^{a-1}}{e^s-1}ds=\int_0^\infty\frac{s^{a-1}}{e^s-1}ds-\int_0^{n^{-\alpha}}\frac{s^{a-1}}{e^s-1}ds\tag*{}$

Given that $n^{-\alpha}\ll1$

$\displaystyle I_2\approx\Gamma(a)\zeta(a)+\frac{\zeta(a)}{a}n^{-\alpha(1-a)}\tag*{}$

Now, putting $I_1, I_2$ into $I_C$

$\displaystyle I_C\approx\frac{n^{1-a}}{\Gamma^2(a)}\int_0^{n^{1-\beta}}x^{a-2}e^{-x}\bigg(\Big(\frac{x}{n}\Big)^{a-1}F(a)+G(a)n^{-\alpha(a-1)}+\Gamma(a)\zeta(a)+\frac{\zeta(a)}{a}n^{-\alpha(a-1)}\bigg)dx\tag*{}$

Expanding integration to $\infty$, we get the main asymptotics term of $I_C\sim\frac{n^{1-a}\zeta(a)}{a}\,$ (please, see (2) above), plus - some corrections, which powers are $\displaystyle\sim n^{2(1-a)}$ and $\displaystyle\sim n^{1-a}n^{-\alpha(a-1)}=n^{(1+\alpha)(1-a)}$.

It is easy to show that both correction terms are $\displaystyle \ll n^{-\alpha}$.

Indeed, for $\displaystyle a>2\quad 2-a<0\,\,\Rightarrow\,\,2-2a<-a$.

Also, if we choose $\alpha>\frac{1}{a-1}\,\,\Rightarrow\,\,\alpha(a-1)>1\,\,\Rightarrow\,\,(1+\alpha)(1-a)<-a$.

The validity of the whole program is based on the possibility to choose such $\displaystyle \alpha, \beta$ that $\displaystyle \frac{1}{a-1}<\alpha< \beta<1$ - what is realizable for $a>2$.

$\endgroup$
1
  • $\begingroup$ @Gary, I'm sorry to disturb you, but if there is a way to find the asymptotics of the sum by means of the series analysis? My colleagues tried to do this on Quora, but did not succeed. Thank you in advance for any reference or suggestion! $\endgroup$
    – Svyatoslav
    May 24 at 9:24
1
$\begingroup$

We will show that $S_n=o(n^{-(\alpha-1)})$. We claim $$n^{(\alpha-1)}S_n \approx n^{(\alpha-1)} \sum_{i=1}^n i^{-\alpha}\left[(n-i+1)^{-(\alpha-1)}-n^{-(\alpha-1)}\right] =\sum_{i=1}^n i^{-\alpha}\left[\left(1+\frac{1-i}{n}\right)^{-(\alpha-1)}-1\right]$$ converges to $0$ where we replace the inner sum (over $j$) with difference of the tails.

Let $k=i-1$. Then \begin{align*} \sum_{i=1}^n i^{-\alpha}\left[\left(1+\frac{1-i}{n}\right)^{-(\alpha-1)}-1\right]&=\sum_{k=0}^{n-1} (k+1)^{-\alpha}\left[\left(1-\frac{k}{n}\right)^{-(\alpha-1)}-1\right]\\ &=0+\sum_{k=1}^{n-1} (k+1)^{-\alpha}\left[\left(1-\frac{k}{n}\right)^{-(\alpha-1)}-1\right]\\ &\leq \sum_{k=1}^{n-1} k^{-\alpha}\left[\left(1-\frac{k}{n}\right)^{-(\alpha-1)}-1\right]. \end{align*} Let $a_k(n)=k^{-\alpha}\left[\left(1-\frac{k}{n}\right)^{-(\alpha-1)}-1\right]$. Applying the generalized binomial theorem we have that $$a_k(n)\leq \frac{1}{n}C_{\alpha}k^{-(\alpha-1)}\left(1-\frac{k}{n}\right)^{-(\alpha-1)}.$$ Together with the fact that $$\left(\frac{n}{k(n-k)}\right)^{(\alpha-1)}=2^{(\alpha-1))}\left(\frac{n}{2k(n-k)}\right)^{(\alpha-1)}<2^{(\alpha-1)}\frac{n}{2k(n-k)}$$ we have that $$n^{(\alpha-1)}S_n\leq \frac{C_{\alpha}}{n}\sum_{k=1}^{n-1}\frac{n}{k(n-k)}\leq \frac{C_{\alpha}}{n}\int_{1}^{n-1}\frac{n}{x(n-x)}dx=\frac{C_{\alpha}}{n}2\log{(n-1)}\to 0.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.