6
$\begingroup$

Given a symmetric convex body $K \subset \mathbb{R}^n$ (i.e., a bounded symmetric convex set with non-empty interior), I am interested in the following quantity $$p_K := \Pr_{x_1, x_2 \sim K}[x_1 \in K + x_2] \; ,$$ i.e., the probability given two uniformly random and independent vectors $x_1,x_2$ in $K$ that $x_1 \in K + x_2$, which you might call the "kissing probability" of $K$, in analogy with the kissing number. (I know it's not a great name.) An equivalent definition is $$ p_K := \mathop{\mathbb{E}}_{x \sim K}[\mathrm{vol}(K \cap (K+x))/\mathrm{vol}(K)] \; . $$

For example if $K$ is the $n$-ball, then $p_K \approx (3/4)^{n/2}$, and if $K$ is the $n$-cube, then $p_K = (3/4)^n$.

My main question is whether this quantity is maximized by the ball. More generally, has $p_K$ been studied? Can we get a decent upper bound on $p_K$?


Some context:

This quantity arises relatively naturally in the study of sieving algorithms for lattice problems. At a very high level, these algorithms work by sampling a very large number of more-or-less random vectors from a convex body $K$ and then looking for pairs of vectors $x_1, x_2$ such that $x_1 \in x_2 + K/(1+\varepsilon)$, taking their difference, and repeating the procedure on the differences. The running time of these algorithms is more-or-less governed by the number of points that need to be sampled in order to guarantee that nearly every point can be paired with another, which is more-or-less $1/p_K$.

So, if one can find a convex body with $p_K \gg (3/4)^{n/2}$, then one might hope to find a faster algorithm for lattice problems, which would be quite significant.

$\endgroup$
4
  • 3
    $\begingroup$ Gah, I can't find the paper now. But the unit ball is best. It seems you're asking for the symmetric convex set that is the most "closed under addition", or closest to being an approximate subgroup. The paper that I'm thinking of (but can't find) shows that the unit ball has the most solutions to $x_1+\dots+x_k = 0$ as $x_1,\dots,x_k$ range in the set. By taking $k=3$, you get what you want. $\endgroup$ Commented Oct 12, 2021 at 21:04
  • $\begingroup$ @mathworker21 Interesting! I can't find the paper either :-/. $\endgroup$ Commented Oct 12, 2021 at 22:17
  • 3
    $\begingroup$ It looks similar, if not identical to mathoverflow.net/questions/282526/…. $\endgroup$
    – Luc Guyot
    Commented Oct 14, 2021 at 19:31
  • $\begingroup$ Thanks so much @LucGuyot ! (Voting to close as apparently this is a duplicate.) $\endgroup$ Commented Oct 14, 2021 at 20:38

0

Browse other questions tagged .