# How do we show $\int_{[0,\:1)^2}\exp\left(-\frac{\left\|x-\frac{x_i+x_j}2\right\|^2}{\sigma^2}\right)\:{\rm d}x=\pi\sigma^2$ here?

Let $$D=[0,\sqrt N)^d$$ for some $$N\in\mathbb N$$, $$x_i,x_j\in D$$ and $$\sigma>0$$. In equation $$(30)$$ of this paper I've read that, if $$d=2$$, then $$\begin{equation}\begin{split}\int_D\exp\left(-\frac{\left\|x-\frac{x_i+x_j}2\right\|^2}{\sigma^2}\right)\:{\rm d}x&=\int_{\mathbb R^2}\exp\left(-\frac{\left\|x-\frac{x_i+x_j}2\right\|^2}{2\left(\sigma/\sqrt 2\right)^2}\right)\:{\rm d}x\\&=2\pi\frac{\sigma^2}2=\pi\sigma^2\end{split}\tag1\end{equation}$$ as long as $$\sigma\ll\sqrt N$$ or "assuming an infinite periodic set".

How can we show this? I actually don't understand what's meant by "assuming an infinite periodic set". But even when $$\sigma\ll\sqrt N$$, I don't understand how we obtain the claim (at least approximately).

## EDIT

So, okay. Let us write $$z:=\frac{x_i+x_j}2$$. We've then got $$\int_{\left[0,\:\sqrt N\right)^d}\exp\left(-\frac{\|x-z\|^2}{\sigma^2}\right)=\sqrt N^d\int_{[0,\:1)^d}\exp\left(-\frac N{\sigma^2}\left\|x-\frac z{\sqrt N}\right\|^2\right)\:{\rm d}x\tag2.$$ Now note that $$\sqrt N\int_0^1\exp\left(-\frac N{\sigma^2}\left(x-\frac{z_i}{\sqrt N}\right)^2\right)\:{\rm d}x=\frac{\sqrt\pi}2\sigma\left(\operatorname{erf}\left(\frac{z_i}\sigma\right)-\operatorname{erf}\left(\frac{z_i}\sigma-\frac{\sqrt N}\sigma\right)\right).\tag3$$ Now how does $$\sigma\ll\sqrt N$$ imply $$(3)$$ is equal to $$\pi\sigma^2$$? I guess we need to use $$\frac{\sqrt N}\sigma\to\infty$$ instead of $$\sigma\ll\sqrt N$$, but I still don't see how to deal with $$\frac{z_i}\sigma$$ in $$(3)$$ when I take this limit ...

## EDIT 2

Maybe we need to assume $$\sigma=\delta\sqrt N$$ and consider $$\delta\to0+$$ as suggested by FShrike in the comments. For this, note that $$\int_0^{\sqrt N}\exp\left(-\frac{(x-z_i)^2}{\sigma^2}\right)\:{\rm d}x=\sigma\int_{-\frac{z_i}{\sqrt N}\frac1\delta}^{\left(1-\frac{z_i}{\sqrt N}\right)\frac1\delta}e^{-x^2}\:{\rm d}x\tag3.$$ Now the integral on the right-hand side clearly tends to $$\sqrt\pi$$ as $$\delta\to0+$$. I guess this is why they say that $$(3)$$ is approximately equal to $$\sqrt\pi\sigma$$. However, since $$\sigma\to0+$$ as $$\delta\to0+$$, this is somehow strange.

## So, that's why I would like to figure out the ofllowing: How small must $$\delta$$ actually be to make the error between $$\sqrt\pi\sigma$$ and $$(3)$$ smaller than a given $$\varepsilon>0$$; i.e. $$0<\sqrt\pi\sigma-\int_0^{\sqrt N}\exp\left(-\frac{(x-z_i)^2}{\sigma^2}\right)\:{\rm d}x<\varepsilon\tag4?$$

• The condition $\sigma \ll \sqrt{N}$ is used to justify replacing the domain of integration with all $R^2$, more or less. Mar 17 at 16:04
• @Aruralreader Yes, sure. But why is that possible then? And instead of replacing the integration domain, can't we argue with the error function? Mar 17 at 20:31
• This is a purely heuristic calculation such as one might find in a physics paper. If we work with "$P$" being infinitely spread out i.e. $D=\Bbb R^2$ literally or if we work with $\sigma\ll\sqrt{N}$ then one can approximately write: $$\int_D\cdots=\int_{\Bbb R^2}\cdots=\pi\sigma^2$$ Mar 18 at 19:52
• That is all there is to it. They have made an estimation (not a question of precise mathematics and $\operatorname{erf}$ and all that jazz), and have not claimed any particular degree of precision of this estimate (which would have been a suitable question of precise mathematics). In particular, the equality signs are not genuine equality signs Mar 18 at 19:53
• @FShrike Thank you for your comment. I already guessed that they understand their equation as actually an "approximate equality", but if it is really a sensible approximation, shouldn't we be able to give a suitable assumption on $\sigma$ and $\sqrt N$ (such as $\sigma\ll\sqrt N$) to show that this is indeed a sensible approximation using $(3)$? Mar 18 at 19:57

$$\newcommand{\d}{\,\mathrm{d}}$$Take $$z$$ to be in $$(0,\sqrt{N})^2$$ and $$0<\sigma$$. By the multivariate integral substitution rule we have: $$\int_{[0,\sqrt{N})^2}\exp(-\sigma^{-2}\|x-z\|^2)\d\lambda(x)\\=\sigma^2\int_{[-z_1/\sigma,(\sqrt{N}-z_1)/\sigma)\times[-z_2/\sigma,(\sqrt{N}-z_2)/\sigma)}\exp(-\|x\|^2)\d\lambda(x)$$

The difference between this and: $$\sigma^2\int_{\Bbb R^2}\exp(-\|x\|^2)\d\lambda(x)=\pi\sigma^2$$Is exactly: $$\psi(\sigma,N,z):=\sigma^2\int_{\Bbb R^2\setminus[-z_1/\sigma,(\sqrt{N}-z_1)/\sigma)\times[-z_2/\sigma,(\sqrt{N}-z_2)/\sigma)}\exp(-\|x\|^2)\d\lambda(x)$$We can bound: \begin{align}0&<\psi(\sigma,N,z)\\&\le\sigma^2\int_{\{|u|\ge\mu/\sigma\}\times\{|v|\ge\nu/\sigma\}}\exp(-\|(u,v)\|^2)\d\lambda(u,v)\\&\le4\sigma^2\int_{(\kappa/\sigma,\infty)^2}\exp(-\|(u,v)\|^2)\d\lambda(u,v)\end{align}Where $$0<\mu:=\min(z_1,\sqrt{N}-z_1),\,0<\nu:=\min(z_2,\sqrt{N}-z_2)$$ and $$\kappa:=\min(\mu,\nu)>0$$. We can continue to bound: \begin{align}\psi(\sigma,N,z)&\le4\sigma^2\exp(-2\kappa^2/\sigma^2)\int_{(\kappa/\sigma,\infty)^2}\exp(-(u^2-\kappa^2/\sigma^2+v^2-\kappa^2/\sigma^2))\d\lambda(u,v)\\&=4\sigma^2\exp(-2\kappa^2/\sigma^2)\left(\int_{\kappa/\sigma}^\infty\exp(-(x^2-\kappa^2/\sigma^2))\d x\right)^2\end{align}

If we substitute $$y^2=x^2-\kappa^2/\sigma^2$$ then $$0\le\frac{\d x}{\d y}=\frac{y}{x}=\sqrt{1-\frac{\kappa^2}{\sigma^2x^2}}\le1$$ so I can continue to bound: $$0<\psi(\sigma,N,z)\le4\sigma^2\exp(-2\kappa^2/\sigma^2)\left(\int_0^\infty\exp(-y^2)\d y\right)^2=\pi\sigma^2\cdot\exp(-2\kappa^2/\sigma^2)$$

Now - if $$z$$ is "pretty close" to the middle of the region, say we've fixed a constant $$0<\alpha<1$$ and $$\alpha\sqrt{N}\le\min(z_1,z_2,\sqrt{N}-z_1,\sqrt{N}-z_2)$$ and if $$\sigma:=\delta\sqrt{N}$$ for some defined $$\delta>0$$ then you've got: $$0<\left|\pi\sigma^2-\int_D\cdots\right|\le\pi\sigma^2\cdot\exp(-2\alpha^2/\delta^2)$$If $$\delta\ll\alpha$$ the right hand side is extremely small indeed. What's more, we're actually saying the right hand side is small even if you divide through by $$\sigma^2$$ (which is also very small). So the error clearly decays very fast, and the paper's heuristic is about as justified as a heuristic can be.

• Thank you for your answer! Some minor corrections: (a) After "we can bound", how did you obtain the last inequality? Note that $M:=\{x\in\mathbb R^2:|x_1|\ge\frac\mu\sigma,|x_2|\ge\frac\nu\sigma\}\subseteq\{x\in\mathbb R^2:|x_i|\ge\frac\kappa\sigma\}=\mathbb R^2\setminus\left(-\frac\kappa\sigma,\frac\kappa\sigma\right)=\left(-\infty,\frac\kappa\sigma\right]^2\cup\left[\frac\kappa\sigma,\infty\right)^2$. This is different from what you've obtained. In particular, where did the factor $4$ came from? (b) Sometimes you've used the Lebesgue measure $\lambda$ in your equations; sometimes not. Mar 19 at 19:55
• @0xbadf00d True, my use of $\lambda$ was inconsistent because I was writing my own stuff whilst also looking at the question statement which used "dx". It's not that different from what I obtained - I just used evenness of the integrand to go from integrating over $M$ to $4\times$ the integral of the positive portion of $M$, which is $(k/\sigma,\infty)^2$ Mar 19 at 20:07
• This is the analogue of something like $\int_{-a}^ax^2\,\mathrm{d}x=2\int_0^ax^2\,\mathrm{d}x$ Mar 19 at 20:35
• Yes, okay. Trivial. In arbitrary dimension, we've got $2^d$ before the integral over $[\frac\kappa\sigma,\infty)^d$. Mar 19 at 20:48
• @0xbadf00d I mean if you hold $\alpha$ constant then as $\delta\to0^+$ we get really strong error bounds - but if you don’t have any control on $\alpha$, that is, if $z$ can be arbitrarily close to the boundary of $D$, then the error might be quite bad (in particular if $\alpha\approx\delta$ then the error isn’t so small) and when I say ‘bad’ I mean ‘bad’ after you’ve removed the $\sigma^2$ factor (kinda like considering what the percentage error is rather than the absolute error) Mar 19 at 22:48