0
$\begingroup$

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|<p / 16$ 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!

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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