Take $X$ uniform on the unit sphere in $\mathbb{R}^n.$ For $r>0$, take $S_r=\{x\in \mathbb{Z}^n: \sum_i x_i^2 \leq r^2\}.$

  • With $\|\cdot \|$ the 2-norm, what is the distribution (or at least the mean) of:

\begin{align} \underset{x \in S_r}{\min} \ \left\|X-\frac{x}{\|x\|}\right\|^2 \end{align}

  • How can this optimization be performed efficiently?

One idea for performing the optimization is by exhaustion: the point in $S_r$ that attains the minimum will be a nearest-integer rounding of a point on the ray $\alpha X$. The values $\alpha$ for which $\operatorname{round}(\alpha X)$ changes can be readily computed. Then choose the best value once $\alpha$ is small enough that $\alpha X$ rounds to zero. However I am not sure what the complexity of this is in general.

  • 1
    $\begingroup$ See this paper arxiv.org/pdf/1606.05880.pdf by Bourgain, Rudnick, and Sarnak on the distribution of integer points on a sphere. They essentially study your first question when S_r is taken to be the integer points in a sphere, rather than a ball, and I believe that this is the state of the art for that variant of the question. It's possible that the question becomes easier when you switch from a sphere to a ball, though. $\endgroup$ – Noah Stephens-Davidowitz Jul 13 '18 at 1:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.