Return to Question

I am interested in the following procedure that yields a sequence $D_1,D_2,\ldots,$ of probability distributions over $\mathbb{R}^n$.

Let $D_1$ be the $n$-dimensional Gaussian distribution with covariance $I_n/n$ (so that the expected squared norm of a vector is $1$) conditioned on the norm of the result being at most $1$. So, $D_1$ is a Gaussian with its tail chopped off. (The starting distribution is probably not too important.)

Then, for $i \geq 1$, let $D_{i+1}$ be the distribution obtained by convolving $D_i$ with itself and then conditioning on the result having norm at most $1$.

Equivalently, if $f_i$ is the PDF of $D_i$, then $f_{i+1} = (f_i \circ f_i) \cdot 1_{\|x\| \leq 1}/a_i$, where $a_i = \Pr_{x,y \sim D_i}[\|x+y\| \leq 1]$ is chosen so that $f_{i+1}$ is a probability distribution.

I think this is a relatively natural process (and it arises in an important context, as I discuss briefly below), but I'm having quite a hard time actually understanding how to reason about it. And, my attempts to search the literature have failed because I have no idea what to search for :).

So, I think what I'm really just asking for is for any help at all in understanding such a process (or a reference to work that has considered such things). (Of course, there are many natural specific questions that one can ask about this process. E.g., does it converge to some distribution, and if so, what is the limiting distribution?)

For my application, I am actually mostly interested in the $a_i$. It is clear that for all $i$, $a_i \geq \Pr_{x,y \sim S^{n-1}}[\|x+y\| \leq 1] \approx (3/4)^{n/2}$, i.e., $a_i$ is always at least the probability that two random vectors on a sphere sum to a shorter vector. However, it seems that this bound might not actually be tight. E.g., $a_1 \approx (\sqrt{e}/2)^{n/2} \approx 0.82^{n/2}$. Perhaps all of the $a_i$ are exponentially larger than this lower bound of $(3/4)^{n/2}$?

If the bound $(3/4)^{n/2}$ is in fact exponentially loose (for all $i$---or even just for, say, $i \lesssim \log n$), this could imply faster algorithms for computational lattice problems, which would have major implications for the security of lattice-based cryptography(!). For this reason, I would be happy even with a heuristic analysis of this process.

However, again, any help at all in understanding this process would be wonderful :).

(One curious fact that makes me think that $(4/3)^{n/2}$ is not the right answer: this procedure maps the uniform distribution on the sphere (which is in some sense the worst case distribution) to a distribution that puts significantly more mass on short vectors. In particular, if we pretend that $D_i$ is the uniform distribution over a sphere, then $D_{i+1}$ satisfies $\Pr_{x \sim D_{i+1}}[\|x\| = r] \approx r^{n}(1-r^2/4) \cdot (4/3)^{n/2}$. Notice that the latter distribution actually puts more mass on short vectors than even the Gaussian.)

@spencer-peters (my student) has numerically computed the limiting distribution in the 1-d case. Here's what it looks like in red, compared to a Gaussian in blue:

The limiting value of $a_i$ is roughly $0.8.

I am interested in the following procedure that yields a sequence $D_1,D_2,\ldots,$ of probability distributions over $\mathbb{R}^n$.

Let $D_1$ be the $n$-dimensional Gaussian distribution with covariance $I_n/n$ (so that the expected squared norm of a vector is $1$) conditioned on the norm of the result being at most $1$. So, $D_1$ is a Gaussian with its tail chopped off. (The starting distribution is probably not too important.)

Then, for $i \geq 1$, let $D_{i+1}$ be the distribution obtained by convolving $D_i$ with itself and then conditioning on the result having norm at most $1$.

Equivalently, if $f_i$ is the PDF of $D_i$, then $f_{i+1} = (f_i \circ f_i) \cdot 1_{\|x\| \leq 1}/a_i$, where $a_i = \Pr_{x,y \sim D_i}[\|x+y\| \leq 1]$ is chosen so that $f_{i+1}$ is a probability distribution.

I think this is a relatively natural process (and it arises in an important context, as I discuss briefly below), but I'm having quite a hard time actually understanding how to reason about it. And, my attempts to search the literature have failed because I have no idea what to search for :).

So, I think what I'm really just asking for is for any help at all in understanding such a process (or a reference to work that has considered such things). (Of course, there are many natural specific questions that one can ask about this process. E.g., does it converge to some distribution, and if so, what is the limiting distribution?)

For my application, I am actually mostly interested in the $a_i$. It is clear that for all $i$, $a_i \geq \Pr_{x,y \sim S^{n-1}}[\|x+y\| \leq 1] \approx (3/4)^{n/2}$, i.e., $a_i$ is always at least the probability that two random vectors on a sphere sum to a shorter vector. However, it seems that this bound might not actually be tight. E.g., $a_1 \approx (\sqrt{e}/2)^{n/2} \approx 0.82^{n/2}$. Perhaps all of the $a_i$ are exponentially larger than this lower bound of $(3/4)^{n/2}$?

If the bound $(3/4)^{n/2}$ is in fact exponentially loose (for all $i$---or even just for, say, $i \lesssim \log n$), this could imply faster algorithms for computational lattice problems, which would have major implications for the security of lattice-based cryptography(!). For this reason, I would be happy even with a heuristic analysis of this process.

However, again, any help at all in understanding this process would be wonderful :).

(One curious fact that makes me think that $(4/3)^{n/2}$ is not the right answer: this procedure maps the uniform distribution on the sphere (which is in some sense the worst case distribution) to a distribution that puts significantly more mass on short vectors. In particular, if we pretend that $D_i$ is the uniform distribution over a sphere, then $D_{i+1}$ satisfies $\Pr_{x \sim D_{i+1}}[\|x\| = r] \approx r^{n}(1-r^2/4) \cdot (4/3)^{n/2}$. Notice that the latter distribution actually puts more mass on short vectors than even the Gaussian.)

@spencer-peters (my student) has numerically computed the limiting distribution in the 1-d case. Here's what it looks like in red, compared to a Gaussian in blue:

The limiting value of $a_i$ is roughly $0.8$.

I am interested in the following procedure that yields a sequence $D_1,D_2,\ldots,$ of probability distributions over $\mathbb{R}^n$.

Let $D_1$ be the $n$-dimensional Gaussian distribution with covariance $I_n/n$ (so that the expected squared norm of a vector is $1$) conditioned on the norm of the result being at most $1$. So, $D_1$ is a Gaussian with its tail chopped off. (The starting distribution is probably not too important.)

Then, for $i \geq 1$, let $D_{i+1}$ be the distribution obtained by convolving $D_i$ with itself and then conditioning on the result having norm at most $1$.

Equivalently, if $f_i$ is the PDF of $D_i$, then $f_{i+1} = (f_i \circ f_i) \cdot 1_{\|x\| \leq 1}/a_i$, where $a_i = \Pr_{x,y \sim D_i}[\|x+y\| \leq 1]$ is chosen so that $f_{i+1}$ is a probability distribution.

I think this is a relatively natural process (and it arises in an important context, as I discuss briefly below), but I'm having quite a hard time actually understanding how to reason about it. And, my attempts to search the literature have failed because I have no idea what to search for :).

So, I think what I'm really just asking for is for any help at all in understanding such a process (or a reference to work that has considered such things). (Of course, there are many natural specific questions that one can ask about this process. E.g., does it converge to some distribution, and if so, what is the limiting distribution?)

For my application, I am actually mostly interested in the $a_i$. It is clear that for all $i$, $a_i \geq \Pr_{x,y \sim S^{n-1}}[\|x+y\| \leq 1] \approx (3/4)^{n/2}$, i.e., $a_i$ is always at least the probability that two random vectors on a sphere sum to a shorter vector. However, it seems that this bound might not actually be tight. E.g., $a_1 \approx (\sqrt{e}/2)^{n/2} \approx 0.82^{n/2}$. Perhaps all of the $a_i$ are exponentially larger than this lower bound of $(3/4)^{n/2}$?

If the bound $(3/4)^{n/2}$ is in fact exponentially loose (for all $i$---or even just for, say, $i \lesssim \log n$), this could imply faster algorithms for computational lattice problems, which would have major implications for the security of lattice-based cryptography(!). For this reason, I would be happy even with a heuristic analysis of this process.

However, again, any help at all in understanding this process would be wonderful :).

(One curious fact that makes me think that $(4/3)^{n/2}$ is not the right answer: this procedure maps the uniform distribution on the sphere (which is in some sense the worst case distribution) to a distribution that puts significantly more mass on short vectors. In particular, if we pretend that $D_i$ is the uniform distribution over a sphere, then $D_{i+1}$ satisfies $\Pr_{x \sim D_{i+1}}[\|x\| = r] \approx r^{n}(1-r^2/4) \cdot (4/3)^{n/2}$. Notice that the latter distribution actually puts more mass on short vectors than even the Gaussian.)

I am interested in the following procedure that yields a sequence $D_1,D_2,\ldots,$ of probability distributions over $\mathbb{R}^n$.

Let $D_1$ be the $n$-dimensional Gaussian distribution with covariance $I_n/n$ (so that the expected squared norm of a vector is $1$) conditioned on the norm of the result being at most $1$. So, $D_1$ is a Gaussian with its tail chopped off. (The starting distribution is probably not too important.)

Then, for $i \geq 1$, let $D_{i+1}$ be the distribution obtained by convolving $D_i$ with itself and then conditioning on the result having norm at most $1$.

Equivalently, if $f_i$ is the PDF of $D_i$, then $f_{i+1} = (f_i \circ f_i) \cdot 1_{\|x\| \leq 1}/a_i$, where $a_i = \Pr_{x,y \sim D_i}[\|x+y\| \leq 1]$ is chosen so that $f_{i+1}$ is a probability distribution.

I think this is a relatively natural process (and it arises in an important context, as I discuss briefly below), but I'm having quite a hard time actually understanding how to reason about it. And, my attempts to search the literature have failed because I have no idea what to search for :).

So, I think what I'm really just asking for is for any help at all in understanding such a process (or a reference to work that has considered such things). (Of course, there are many natural specific questions that one can ask about this process. E.g., does it converge to some distribution, and if so, what is the limiting distribution?)

For my application, I am actually mostly interested in the $a_i$. It is clear that for all $i$, $a_i \geq \Pr_{x,y \sim S^{n-1}}[\|x+y\| \leq 1] \approx (3/4)^{n/2}$, i.e., $a_i$ is always at least the probability that two random vectors on a sphere sum to a shorter vector. However, it seems that this bound might not actually be tight. E.g., $a_1 \approx (\sqrt{e}/2)^{n/2} \approx 0.82^{n/2}$. Perhaps all of the $a_i$ are exponentially larger than this lower bound of $(3/4)^{n/2}$?

If the bound $(3/4)^{n/2}$ is in fact exponentially loose (for all $i$---or even just for, say, $i \lesssim \log n$), this could imply faster algorithms for computational lattice problems, which would have major implications for the security of lattice-based cryptography(!). For this reason, I would be happy even with a heuristic analysis of this process.

However, again, any help at all in understanding this process would be wonderful :).

(One curious fact that makes me think that $(4/3)^{n/2}$ is not the right answer: this procedure maps the uniform distribution on the sphere (which is in some sense the worst case distribution) to a distribution that puts significantly more mass on short vectors. In particular, if we pretend that $D_i$ is the uniform distribution over a sphere, then $D_{i+1}$ satisfies $\Pr_{x \sim D_{i+1}}[\|x\| = r] \approx r^{n}(1-r^2/4) \cdot (4/3)^{n/2}$. Notice that the latter distribution actually puts more mass on short vectors than even the Gaussian.)

@spencer-peters (my student) has numerically computed the limiting distribution in the 1-d case. Here's what it looks like in red, compared to a Gaussian in blue:

The limiting value of $a_i$ is roughly $0.8.

I am interested in the following procedure that yields a sequence $D_1,D_2,\ldots,$ of probability distributions over $\mathbb{R}^n$.

Let $D_1$ be the $n$-dimensional Gaussian distribution with covariance $I_n/n$ (so that the expected squared norm of a vector is $1$) conditioned on the norm of the result being at most $1$. So, $D_1$ is a Gaussian with its tail chopped off. (The starting distribution is probably not too important.)

Then, for $i \geq 1$, let $D_{i+1}$ be the distribution obtained by convolving $D_i$ with itself and then conditioning on the result having norm at most $1$.

Equivalently, if $f_i$ is the PDF of $D_i$, then $f_{i+1} = (f_i \circ f_i) \cdot 1_{\|x\| \leq 1}/a_i$, where $a_i = \Pr_{x,y \sim D_i}[\|x+y\| \leq 1]$ is chosen so that $f_{i+1}$ is a probability distribution.

I think this is a relatively natural process (and it arises in an important context, as I discuss briefly below), but I'm having quite a hard time actually understanding how to reason about it. And, my attempts to search the literature have failed because I have no idea what to search for :).

So, I think what I'm really just asking for is for any help at all in understanding such a process (or a reference to work that has considered such things). (Of course, there are many natural specific questions that one can ask about this process. E.g., does it converge to some distribution, and if so, what is the limiting distribution?)

For my application, I am actually mostly interested in the $a_i$. It is clear that for all $i$, $a_i \geq \Pr_{x,y \sim S^{n-1}}[\|x+y\| \leq 1] \approx (3/4)^{n/2}$, i.e., $a_i$ is always at least the probability that two random vectors on a sphere sum to a shorter vector. However, it seems that this bound might not actually be tight. E.g., $a_1 \approx (2/\sqrt{e})^{n/2} \approx 1.2^{n/2}$. Perhaps all of the $a_i$ are exponentially larger than this lower bound of $(3/4)^{n/2}$?

If the bound $(3/4)^{n/2}$ is in fact exponentially loose (for all $i$---or even just for, say, $i \lesssim \log n$), this could imply faster algorithms for computational lattice problems, which would have major implications for the security of lattice-based cryptography(!). For this reason, I would be happy even with a heuristic analysis of this process.

However, again, any help at all in understanding this process would be wonderful :).

(One curious fact that makes me think that $(4/3)^{n/2}$ is not the right answer: this procedure maps the uniform distribution on the sphere (which is in some sense the worst case distribution) to a distribution that puts significantly more mass on short vectors. In particular, if we pretend that $D_i$ is the uniform distribution over a sphere, then $D_{i+1}$ satisfies $\Pr_{x \sim D_{i+1}}[\|x\| = r] \approx r^{n}(1-r^2/4) \cdot (4/3)^{n/2}$. Notice that the latter distribution actually puts more mass on short vectors than even the Gaussian.)

I am interested in the following procedure that yields a sequence $D_1,D_2,\ldots,$ of probability distributions over $\mathbb{R}^n$.

Let $D_1$ be the $n$-dimensional Gaussian distribution with covariance $I_n/n$ (so that the expected squared norm of a vector is $1$) conditioned on the norm of the result being at most $1$. So, $D_1$ is a Gaussian with its tail chopped off. (The starting distribution is probably not too important.)

Then, for $i \geq 1$, let $D_{i+1}$ be the distribution obtained by convolving $D_i$ with itself and then conditioning on the result having norm at most $1$.

Equivalently, if $f_i$ is the PDF of $D_i$, then $f_{i+1} = (f_i \circ f_i) \cdot 1_{\|x\| \leq 1}/a_i$, where $a_i = \Pr_{x,y \sim D_i}[\|x+y\| \leq 1]$ is chosen so that $f_{i+1}$ is a probability distribution.

I think this is a relatively natural process (and it arises in an important context, as I discuss briefly below), but I'm having quite a hard time actually understanding how to reason about it. And, my attempts to search the literature have failed because I have no idea what to search for :).

So, I think what I'm really just asking for is for any help at all in understanding such a process (or a reference to work that has considered such things). (Of course, there are many natural specific questions that one can ask about this process. E.g., does it converge to some distribution, and if so, what is the limiting distribution?)

For my application, I am actually mostly interested in the $a_i$. It is clear that for all $i$, $a_i \geq \Pr_{x,y \sim S^{n-1}}[\|x+y\| \leq 1] \approx (3/4)^{n/2}$, i.e., $a_i$ is always at least the probability that two random vectors on a sphere sum to a shorter vector. However, it seems that this bound might not actually be tight. E.g., $a_1 \approx (\sqrt{e}/2)^{n/2} \approx 0.82^{n/2}$. Perhaps all of the $a_i$ are exponentially larger than this lower bound of $(3/4)^{n/2}$?

If the bound $(3/4)^{n/2}$ is in fact exponentially loose (for all $i$---or even just for, say, $i \lesssim \log n$), this could imply faster algorithms for computational lattice problems, which would have major implications for the security of lattice-based cryptography(!). For this reason, I would be happy even with a heuristic analysis of this process.

However, again, any help at all in understanding this process would be wonderful :).

(One curious fact that makes me think that $(4/3)^{n/2}$ is not the right answer: this procedure maps the uniform distribution on the sphere (which is in some sense the worst case distribution) to a distribution that puts significantly more mass on short vectors. In particular, if we pretend that $D_i$ is the uniform distribution over a sphere, then $D_{i+1}$ satisfies $\Pr_{x \sim D_{i+1}}[\|x\| = r] \approx r^{n}(1-r^2/4) \cdot (4/3)^{n/2}$. Notice that the latter distribution actually puts more mass on short vectors than even the Gaussian.)