3
$\begingroup$

Note: This question relates to two previous questions on math.stackexchange (1 and 2), neither of which had satisfactory answers after posting bounties.

Whilst trying to count certain types of bipartite graphs, I'm lead to try to bound the following quantity $$ S:=\sum_{x=0}^\infty \sum_{y=0}^\infty (x+y)^m e^{-\frac{x^2}{2i} - \frac{y^2}{2j}} $$ where $i,j$ and $m$ are integers, and I'm interested in the asymptotics for large $i$ and $j$ and potentially $m$ (although it would suffice to have a good upper bound when $i \approx j$ and $m=o(i)$).

A natural strategy seems to be to consider the integral $$ I:=\int_0^\infty \int_0^\infty (x+y)^m e^{-\frac{x^2}{2i} - \frac{y^2}{2j}} dx\,dy $$ and show that $S \approx I$, and hopefully bound $I$ by analytic means. Unfortunately both parts of this strategy have been causing me difficulty.

One can derive an exact expression for $I$ by multiplying out the terms and using known identities for the quantities $\int_0^\infty x^k e^{-\frac{x^2}{2i}} dx$, however the asymptotics of this sum is unclear to me. It would seem more natural to use a type of `saddle-point' method here, approximate the logarithm of the function around its maximum at $(x_0,y_0) = \left(i \sqrt{\frac{m}{i+j}},j \sqrt{\frac{m}{i+j}} \right)$, where the function takes the value $\exp\left(m\log\sqrt{(i+j)(m)}-\frac{m}{2}\right)$, using the first two terms of the Taylor series, and so evaluate the integral in this region as a standard Gaussian, and then show that the contribution from outside this region is negligible.

This would lead to the following bound, which I believe is in fact the correct asymptotic order $$ I \approx \exp\left(m\log\sqrt{(i+j)(m)}-\frac{m}{2}\right)\pi\sqrt{2ij}, $$ however I wasn't able to get this approach to work, there is a gap between where I can show the approximation to the Gaussian holds and where the integral is negligible. With the help of a CAS this quantity can be shown to be an upper bound for $I$, which would be sufficient for my application, but it would be nice to know of a more natural method to approach such problems (and I suspect there are standard tools for this sort of thing).

With this, it would be sufficient to show that $$ |I-S| = o\left(\exp\left(m\log\sqrt{(i+j)(m)}-\frac{m}{2}\right)\sqrt{ij}\right), $$ and I wouldn't be surprised if the difference is even bounded by a multiple of the maximum of the function. Indeed, for functions of a single variable with a unique maximum it's possible to bound the difference between the integral and the sum in terms of the maximum by considering appropriate telescoping sums. However, a naive analogue of this argument doesn't seem to work in two dimensions, and trying to apply this argument to each `slice' of the integral led to some pretty horrendous calculations. I also looked into using the Euler-Maclaurin formula but it's a bit out of my area of expertise.

Of course, there may be a way to bound or approximate $S$ without considering $I$ at all, which I would be happy to hear about!

$\endgroup$
3
  • 2
    $\begingroup$ Maybe look at Poisson summation. $\endgroup$ – Brendan McKay Dec 16 '20 at 11:05
  • $\begingroup$ Does $i\approx j$ mean $\limsup(i/j+j/i)<\infty$? If not, what does it mean? $\endgroup$ – Iosif Pinelis Dec 16 '20 at 15:09
  • $\begingroup$ I had in mind $i=(1+o(1))j$. $\endgroup$ – Joshua Erde Dec 16 '20 at 17:10
1
$\begingroup$

$\newcommand{\Ga}{\Gamma}$Let $a:=\sqrt i$ and $b:=\sqrt j$, so that \begin{equation*} a^2\asymp b^2>>m. \tag{1} \end{equation*} Here in what follows, $A\asymp B$ means that $A\ll B$ and $A\gg B$;
$A\ll B$ and $B\gg A$ mean $A=O(B)$; $A<<B$ and $B>>A$ mean $A=o(B)$.
Note that for integers $k\ge0$ \begin{equation*} J_k:=J_k(a^2):=\int_0^\infty dx\,x^k e^{-x^2/(2a^2)}\, =2^{(k-1)/2} a^{k+1} \Ga\Big(\frac{k+1}{2}\Big)\gg(a^2k/C_1)^{k/2}, \tag{2} \end{equation*} where $0^0:=1$ and $C_1>0$ is a universal real constant.

Lemma 1: For $k\in[0,m]$ \begin{equation*} S_k:=S_k(a^2):=\sum_{n=0}^\infty n^k e^{-n^2/(2a^2)}\sim J_k. \end{equation*}

The proof of this lemma is straightforward, but very nasty, and it will be given at the end of this answer.

Using Lemma 1, it is easy to reduce the asymptotics of $S$ to that of the corresponding double integral $I$ (which will not explicitly appear in the following display, though): \begin{align*} S&=\sum_{x,y=0}^\infty (x+y)^m e^{-\frac{x^2}{2a^2} - \frac{y^2}{2b^2}} \\ &=\sum_{x,y=0}^\infty \sum_{k=0}^m\binom mk x^k y^{m-k} e^{-\frac{x^2}{2a^2} - \frac{y^2}{2b^2}} \\ &=\sum_{k=0}^m\binom mk \sum_{x,y=0}^\infty x^k y^{m-k} e^{-\frac{x^2}{2a^2} - \frac{y^2}{2b^2}} \\ &=\sum_{k=0}^m\binom mk S_k(a^2)S_{m-k}(b^2) \\ &\sim\sum_{k=0}^m\binom mk J_k(a^2)J_{m-k}(b^2) \\ &=ab\,2^{m/2-1}\sum_{k=0}^m\binom mk a^k b^{m-k}\Ga\Big(\frac{k+1}2\Big)\Ga\Big(\frac{m-k+1}2\Big) \\ &=ab\,2^{m/2-1}\Ga\Big(\frac m2+1\Big)\sum_{k=0}^m\binom mk a^k b^{m-k} \int_0^1 dx\, x^{\frac{k+1}2-1}(1-x)^{\frac{m-k+1}2-1} \\ &=ab\,2^{m/2-1}\Ga\Big(\frac m2+1\Big) \int_0^1 \frac{dx}{\sqrt{x(1-x)}}\,\sum_{k=0}^m\binom mk (a\sqrt x)^k (b\sqrt{1-x})^{m-k} \\ &=ab\,2^{m/2-1}\Ga\Big(\frac m2+1\Big)K_m, \end{align*} where \begin{align*} K_m&:=\int_0^1 \frac{dx}{\sqrt{x(1-x)}}\,(a\sqrt x+b\sqrt{1-x})^m \\ &=2\int_0^{\pi/2} dt\,(a\cos t+b\sin t)^m \\ &=2(a^2+b^2)^{m/2}\int_0^{\pi/2} dt\,\cos^m(t-t_{a,b}) \end{align*} and \begin{equation*} t_{a,b}:=\arccos\frac a{\sqrt{a^2+b^2}}. \end{equation*} A straightforward saddlepoint approximation (noting, in particular, that $(\ln\cos)''\le-1$) shows that \begin{equation*} K_m\sim2\sqrt{2\pi/m}\,(a^2+b^2)^{m/2} \end{equation*} if $m\to\infty$, whence \begin{align*} S&\sim ab\,2^{m/2-1}\Ga\Big(\frac m2+1\Big)2\sqrt{2\pi/m}\,(a^2+b^2)^{m/2}. \end{align*}

If $m\not\to\infty$, then without loss of generality $m=m_*$, a constant, whence \begin{align*} S&\sim ab\,2^{m_*/2-1}\Ga\Big(\frac{m_*}2+1\Big)2(a^2+b^2)^{m_*/2}\int_0^{\pi/2} dt\,\cos^{m_*}(t-t_{a,b}). \end{align*}

It remains to prove Lemma 1.


Proof of Lemma 1: Note that \begin{equation*} S_k=\sum_{n=0}^\infty S_{k,n},\quad J_k=\sum_{n=0}^\infty J_{k,n}, \end{equation*} where \begin{equation*} S_{k,n}:=e^{g(n)},\quad J_{k,n}:=\int_n^{n+1} dx\,e^{g(x)}, \end{equation*} and \begin{equation*} g(x):=g_k(x):=k\ln x-x^2/(2a^2). \end{equation*} Next, \begin{equation*} g'(x)=\frac kx-\frac x{a^2}=\frac{ka^2-x^2}{xa^2}. \tag{2.5} \end{equation*} So, if \begin{equation*} k<<n<<a^2, \end{equation*} then for $x\in[n,n+1]$ we have $g'(x)\to0$ and hence $S_{k,n}\sim J_{k,n}$.

So, to complete the proof of the lemma, it suffices to show that for any real $C>0$ \begin{equation*} \sum_{0\le n\le Ck} e^{g(n)}+\sum_{n\ge a^2/C} e^{g(n)} +\int_{0\le x\le Ck} dx\, e^{g(x)}+\int_{x\ge a^2/C} dx\, e^{g(x)}<<J_k. \tag{3} \end{equation*} Conditions $k\in[0,m]$ and (1), together with (2.5), imply that (eventually) $g$ is increasing on $[0,Ck]$ and hence \begin{equation*} \sum_{0\le n\le Ck} e^{g(n)}\le(1+Ck)e^{g(Ck)}\le(1+Ck)(Ck)^k<<J_k, \tag{4} \end{equation*} by (2). Similarly, \begin{equation*} \int_{0\le x\le Ck} dx\, e^{g(x)}<<J_k. \tag{5} \end{equation*} Next, for $x\ge a^2/C$ we have $g'(x)\le0$ and also $g''(x)\le0$ (since $g$ is concave). So, for $n\ge a^2/C$ we have $g(n)\le k\ln(a^2/C)-a^2/(2C^2)$ and also \begin{equation*} g'(n)\le\frac{Ck}{a^2}-\frac1C\sim-\frac1C, \end{equation*} again because of conditions $k\in[0,m]$ and (1). So, \begin{equation*} \sum_{n\ge a^2/C} e^{g(n)}\ll\exp\Big\{k\ln\frac{a^2}C-\frac{a^2}{2C^2}\Big\}. \tag{5.5} \end{equation*} With $C_1$ as in (2), consider now \begin{equation*} H(k):=k\ln\frac{a^2}C-\frac{a^2}{2C^2}-\ln((a^2k/C_1)^{k/2}) =\frac k2\,\ln\frac{C_1a^2}{C^2k}-\frac{a^2}{2C^2}. \end{equation*} Again by conditions $k\in[0,m]$ and (1), one has $k\le ca^2$, where $c\downarrow0$, whence \begin{equation*} H'(k)=\frac12\,\ln\frac{C_1a^2}{C^2k}-\frac12>0, \end{equation*} so that $H(k)$ is increasing and hence \begin{equation*} H(k)\le H(ca^2) =\frac{ca^2}2\,\ln\frac{C_1}{C^2c}-\frac{a^2}{2C^2}\sim-\frac{a^2}{2C^2}\to-\infty. \end{equation*} Now (5.5) and (2) yield
\begin{equation*} \sum_{n\ge a^2/C} e^{g(n)}<<J_k. \tag{6} \end{equation*} Similarly, \begin{equation*} \int_{x\ge a^2/C} dx\, e^{g(x)}<<J_k. \tag{7} \end{equation*} Collecting (4), (5), (6), and (7), we get (3), which completes the proof of the lemma. $\Box$

$\endgroup$
4
  • $\begingroup$ In the previous answer, it remained to show that the double sum is asymptotic to the corresponding double integral. While the proof of that is straightforward, it is exceedingly nasty. In this alternative proof, we only need to show that an ordinary sum is asymptotic to the ordinary integral. The latter task is also straightforward and also very nasty, but not as nasty as for the double sum. $\endgroup$ – Iosif Pinelis Dec 17 '20 at 4:40
  • $\begingroup$ Both of these answers look brilliant, thank you. It is a shame that this approximation step is so arduous. I will try to find the time to read them closely next week. $\endgroup$ – Joshua Erde Dec 18 '20 at 11:45
  • $\begingroup$ I'm just discussing with my co-authors the best way to cite this for use in our paper. As I understand it is common to just cite the answers from the website, but I'm not certain about the long term aspects of that, so I would perhaps feel more comfortable (if it would be acceptable to you) citing the answer but also including at least a sketch of the mathematical detail in the paper itself. Does that sound ok, or would you have another suggestion? $\endgroup$ – Joshua Erde Jan 6 at 9:42
  • $\begingroup$ @JoshuaErde : This looks good to me. $\endgroup$ – Iosif Pinelis Jan 6 at 17:22
2
$\begingroup$

Let $a:=\sqrt i$ and $b:=\sqrt j$. Let us find the asymptotics of $I$ (leaving the proof of $S\sim I$ for a hopefully near future). Passing, if necessary, to a subsequence, we see that without loss of generality (wlog) one of the following two cases occurs:

Case 1: $m\to\infty$ or Case 2: $m=m_0$ is constant.

Also, wlog \begin{equation} t_{a,b}:=\arccos\frac a{\sqrt{a^2+b^2}}\to t_0 \end{equation} for some $t_0\in[0,\pi/2]$.

By substitutions $x=ar\cos t$ and $y=br\sin t$, \begin{equation} I=ab \int_0^\infty r\,dr\,e^{-r^2/2}r^m\ J_m=ab\, 2^{m/2} \Gamma \left(\frac{m}{2}+1\right) J_m, \end{equation} where \begin{equation} J_m:=\int_0^{\pi/2} dt\,e^{mg(t)},\quad g(t):=\ln(a\cos t+b\sin t); \end{equation} this is the key observation.

A straightforward saddlepoint approximation (noting, in particular, that $g''(t)=-\frac{a^2+b^2}{(a \cos t+b \sin t)^2}\le-1$) shows that \begin{equation} J_m\sim\sqrt{2\pi/m}\,(a^2+b^2)^{m/2} \end{equation} if $m\to\infty$, that is, if Case 1 occurs, whence \begin{equation} I\sim ab\, 2^{m/2} \Gamma \left(\frac{m}{2}+1\right) \sqrt{2\pi/m}\,(a^2+b^2)^{m/2}, \end{equation} with the asymptotics of $ \Gamma \left(\frac{m}{2}+1\right)$ obtained by Stirling's formula, if desired.

In Case 2, \begin{equation} J_m\sim (a^2+b^2)^{m/2} \int_0^{\pi/2} dt\,(\cos t_0\,\cos t+\sin t_0\sin t)^m =(a^2+b^2)^{m/2} \int_0^{\pi/2} dt\,\cos^m(t-t_0), \end{equation} whence \begin{equation} I\sim ab\, 2^{m_0/2} \Gamma \left(\frac{m_0}{2}+1\right) (a^2+b^2)^{m_0/2} \int_0^{\pi/2} dt\,\cos^{m_0}(t-t_0). \end{equation}

$\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.