6
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 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
    Commented Jul 13, 2018 at 1:40

0

Reset to default

You must log in to answer this question.