1
$\begingroup$

Let $d$ and $n$ be integers. For $i \in \lbrace 1,\dots,n \rbrace$ let $x_i \in \mathbb{R}^d$ be a vector such that $\lVert x \rVert=1 $. For a fixed $1/2 < \alpha \leq 1$, assume we have $\lVert \sum_{i=1}^{n}x_i \rVert \geq \alpha n$ where $\lVert \cdot \rVert$ denotes $\ell_2$ norm.

Question:

Let $w = \frac{ \sum_{i=1}^{n}x_i}{\lVert \sum_{i=1}^{n}x_i \rVert}$. Define the spherical cap of degree $\theta \in [0,\pi/2]$ as follows:

$$ C_{\theta} = \lbrace x \in \mathbb{R}^d: \lVert x \rVert = 1 ~ \text{and} ~ \langle x , w \rangle \geq \cos(\theta) \rbrace. $$

My goal is to find maximum $\cos(\theta)$ such that at least half, i.e., $> n/2 $, of $x_i$s belong to $C_{\theta}$.

Corner Case:

if $\alpha=1$ then it is easy to see that all the vectors are in the direction of $w$. Therefore, setting $\theta=0$ we can see that the number of vectors that belong to $C_{\theta}$ is $n$.

$\endgroup$
2
  • $\begingroup$ @Carlyle yes you are right. I fixed the typo. thanks $\endgroup$
    – MMH
    Dec 26, 2023 at 16:41
  • 1
    $\begingroup$ A potentially interesting question is to ask what happens if we interpret "large fraction" as the output of some function of $\alpha$ itself and the dimension $d$, and then ask which function of $\alpha$ and $d$ has the property that the minimum $\theta$ stays constant when you change $d$. For example, it might be that if you require at least $\alpha^d$ of the $x_i$ to be in $C_{\theta}$ then the minimum $\theta$ is the same for all dimensions. This is interesting in its own right, but can also lead to some insight for your main question $\endgroup$
    – Carlyle
    Dec 26, 2023 at 17:26

1 Answer 1

1
$\begingroup$

Not an answer, just a remark about the other extreme, of $\alpha = \frac{1}{2}$.

Note that if $n = 2m$ then we can arrange $m$ of the vectors on the equator, spacing them out to look like the $m$'th roots of unity, so that when we add all the vectors on the equator, we get the $0$ vector. The other half can be arranged to all be aligned with one another and orthogonal to the first $m$, and thus the sum $$ \left\lVert \sum_{i=1}^{n}x_i \right\rVert = m = \frac{n}{2} $$

Then if we reasonably interpret "A large fraction" as more than half of the $x_i$'s, then the minimum $\cos(\theta)$ is exactly $0$, since we need to include all of the vectors on the equator, which are all orthogonal to $w$.

$\endgroup$
3
  • $\begingroup$ makes sense. thanks for the formalization. I am in particular interested in the regime when $\alpha>1/2$. $\endgroup$
    – MMH
    Dec 26, 2023 at 17:55
  • $\begingroup$ @MMH, yes I saw, but one cannot analyse the extreme case when there is no extreme case...In any case, we can protrude one of the vectors on the equator by an arbitrarily small amount, and have the sum be greater than a half, corresponding to the minimum $\cos(\theta)$ being able to be made arbitrarily close to $0$ $\endgroup$
    – Carlyle
    Dec 26, 2023 at 18:05
  • $\begingroup$ I see your point. I am mainly thinking about the case that $\alpha=3/4$. Can we have a such a counter example in this case? $\endgroup$
    – MMH
    Dec 26, 2023 at 18:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .