Let $K \subseteq \mathbb{R}^n$ be a "fat" convex body, i.e. one that contains a ball of radius 1. I'm interested in the following question about points $y \in K$: If you take a normally distributed $e \sim \mathcal{N}(0,\sigma^2)^n$ and add $e$ to $y$, what is the probability that $y + e \in K$? This question can be rephrased to: what is the noncentral gaussian measure \begin{equation} \mu_{y,\sigma^2}(K) = \frac{1}{(\sqrt{2 \pi \sigma^2})^n} \int_K e^{\frac{\| x - y \|^2}{2 \sigma^2}} \mathrm{d} \lambda^n(x) \end{equation} of $K$? $\mu_{y,\sigma^2}(K)$ can be interpreted as a measure of how much of the neighborhood of $y$ is in $K$. Now, it's easy to see that if $y$ is an extreme point in $K$, then $\mu_{y,\sigma^2}(K)$ is negligibly small. Take for instance the cube $[0,1]^n$, if $y$ is one of the corners of $[0,1]^n$, then $\mu_{y,\sigma^2}(K) \leq 2^{-n}$ (regardless of $\sigma^2$). However, it seems like $\mu_{y,\sigma^2}(K)$ can be lower-bounded by some non-neglible term for "typical" $y$ if $\sigma = O(1/n)$. I'm looking for some sort of mass-inequality for $\mu_{y,\sigma^2}(K)$, something like \begin{equation} \mu( \mu_{y,\sigma^2}(K) < \gamma ) < \epsilon \end{equation} where $y$ follows the uniform law on $K$. I need $\gamma$ to be non-negligible and $\epsilon$ to be negligible. I wonder if there has been a treatment of this or a closely related question about convex bodies. I've solved this problem for spheres (trivially) and for cubes and suspect that it is some general property of fat convex bodies or at least symmetric convex bodies. Moreover, I can show that for any convex body this is true for average $y$, i.e. something like $\mathbb{E}[\mu_{y,\sigma^2}(K)] \geq \alpha$ for any constant $\alpha < 1$ if $\sigma = O(1/n)$. One more observation is that that $\mu_{y,\sigma^2}(K)$ does not concentrate around its average, i.e. $\mu_{y,\sigma^2}(K)$ easily varies by a factor of $1/2$ or more. This can be seen in the cube example: If $y$ is uniformly distributed on $[0,1]$, then both $|y - 1/2| < \sigma/2$ and $y < \sigma / 2$ have significant probability. If $y \approx 1/2$, then the probability that $y + e \in [0,1]$ is close to 1. If $y \approx 0$, then the probability of $y + e \in [0,1]$ is close to $1/2$.

I suspect this problem to be somehow related to the study of isoperimetry of convex bodies, as a typical $y$ in $K$ is very close to the boundary of $K$. However, I didn't find any result that would help me with my problem.

This problem originates from an application in lattice-based cryptography. I would be very grateful for any pointers!


Your Answer

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

Browse other questions tagged or ask your own question.