# The proof of Claim 5.2 in the "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography"

When I'm reading this paper "On lattices, learning with errors, random linear codes, and cryptography" by O. Regev. I have trouble understanding the proof of claim 5.2.

"Hence, it is enough to show that $$\left|\sum_{i=1}^k p x_i \bmod p\right| with high probability. This condition is equivalent to the condition that $$\left|\sum_{i=1}^k x_i \bmod 1\right|<1 / 16$$. Since $$\sum_{i=1}^k x_i \bmod 1$$ is distributed as $$\Psi_{\sqrt{k} \cdot \alpha}$$, and $$\sqrt{k} \cdot \alpha=o(1 / \sqrt{\log n})$$, the probability that $$\left|\sum_{i=1}^k x_i \bmod 1\right|<1 / 16$$ is $$1-\delta(n)$$ for some negligible function $$\delta(n)$$."

Why can we obtain the probability that $$\left|\sum_{i=1}^k x_i \bmod 1\right|<1 / 16$$ is $$1-\delta(n)$$ and what is the detailed proof process? I would appreciate your response. Thank you very much!

$$\Psi_\beta$$ is the probability density function of the wrapped normal distribution so that per equation 7 of the paper $$\mathbb P\left(|\sum x_i|<1/16|\right)=\int_{-1/16}^{1/16}\Psi(r)dr$$ $$=\int_{-1/16}^{1/16}\sum_i\frac1{\sqrt k\alpha}\exp\left(-\pi\left(\frac{(r-i}{\sqrt k\alpha}\right)^2\right)dr\\$$ Simply taking the $$k=0$$ term in the series we see that $$\mathbb P\left(|\sum x_i|<1/16|\right)>\int_{-1/16}^{1/16}\frac1{\sqrt k\alpha}\exp\left(-\pi\left(\frac r{\sqrt k\alpha}\right)^2\right)dr=\int_{-1/16}^{1/16}f(r)dr$$ where $$f(r)$$ is the density function for the normal distribution with mean 0 and standard deviation $$\alpha\sqrt{k/2\pi}$$.
Thus $$1-\mathbb P\left(|\sum x_i|<1/16|\right)$$ is less than twice the tail of the $$\mathcal N(0,\alpha\sqrt{k/2\pi})$$ distribution from 1/16 thus $$1-\mathbb P\left(|\sum x_i|<1/16|\right)<\frac{\exp(-(C\log n))}{\sqrt\log n}$$ for some constant $$C$$ which is $$o(1/n)$$ for large $$n$$.