$\varepsilon$-net of a $d$-dimensional unit ball formed by power set of $V = \{+1, 0 -1\}^d$

Question

I have a set of $d$-dimensional vectors $V = \{+1, 0, -1\}^d $. Then $P(V)$ constitutes the power set of $V$. I now construct a set of unit vectors $V_{\mathrm{sum}}$ from the power set $P(V)$ such that $$ V_{\mathrm{sum}} = \left\{\frac{\bar{v}}{\|\bar{v}\|} \quad \Bigg| \quad \bar{v} = \sum_{v \in S} v, \quad \forall S \in P(V)\right\} $$ That is, each subset $S \in P(V)$ contributes to a vector in $V_{\mathrm{sum}}$ formed as a sum of all the vectors in the subset $S$ and then taking the unit vector in that direction.

Note that there could be duplicates. For example, for $d = 3$, the vector $(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}})$ can be formed as a sum of vectors of any of the following subsets $$S_1 = \{(1,0,0),(0,1,0),(0,0,1)\},\\ S_2 = \{(1,1,0 ),(1,0,1),(0,1,1)\},\\ S_3 = \{(1,1,1)\}.$$

and many more possibilities.

Now I want to find the maximal isolation of a vector from $\,V_{\mathrm{sum}}\,$ from the remaining vectors of $\,V_{\mathrm{sum}},\,$ i.e. the maximum of Euclidean distance between any vector in $V_{\mathrm{sum}}$ to its closest vector in $V_{\mathrm{sum}}$. Is there an easy way to upper bound this max distance?

In other words, if I consider $V_{\mathrm{sum}}$ to be an $\varepsilon$-net to the surface of the unit ball in $d$-dimensions, then I want to find an upper bound on $\varepsilon$. Any weak upper bound on $\varepsilon$ should suffice. The goal is to show that $V_{\mathrm{sum}}$ forms a better $\varepsilon$-net than the unit vectors formed from the vectors in $V$.

Answer 1

Since the notation quickly becomes cumbersome for any $S \in 2^{V}$ define \begin{equation} v_S \overset{\text{def}}{=} \sum_{v \in S} v, \end{equation} and let \begin{equation} \hat v_S \overset{\text{def}}{=} \frac{v_S}{\|v_S\| }, \end{equation} If we fix a $v_S \in \text{span}(V)$ then the goal is to find/bound \begin{equation} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \end{equation} \begin{equation} = \min_{w \in V_\text{sum}}\left|\frac{1}{\|w_T \| \|v_S \| } \right|\left| \| w_T \| v_S - \|v_S \| w_T \right| \end{equation} and then use that to find/bound the value of \begin{equation} \max_{v_S \in V_\text{sum}}\min_{w_T \in V_\text{sum}} |v_S-w_T| . \end{equation} To that end notice that

• if $S = \{0\}$ then $\hat v_T$ doesn't make sense so that we can always assume that $\exists v' \in S$ such that $|v'_i|=1 $ (as a matter of fact we can further assume $0 \not\in S$ since it has no effect)
• furthermore if $\forall v' \in S$ we have that $-v' \in S$ then we have that $v_S = 0$ so that we can also assume that $\exists v' \in S$ such that $-v' \not\in S$
• taking this idea even further we have that if $ v \in S$ and $- v \in S $ then $v_S = v_{S \setminus \{ v, -v\}}$ and therefore we can assume that $v \in S \implies -v \notin S$
• generalizing this concept further we have that if $ T \subset S$ and $v_T = 0 $ then $v_S = v_{S \setminus T}$ and therefore we can assume that $(\not\exists T \subset S)(w_T = 0 )$

Therefore if we define the support of $v$ as the following \begin{equation} \text{supp}(v) = \{i \in [n] \ | \ v_i \neq 0\}, \end{equation} we can use the preceding claims to deduce the following:

Lemma $(\forall v_S \in \text{span}(V))(\exists m \in [n])$ such that both

• $(v_S)_m = \min\{ |(v_S)_i| \ | \ i \in [n] \}$

• either $e_m \not\in S$ or $-e_m \not\in S$

where \begin{equation} (e_m)_i = \begin{cases} 1 & \text{if } i = m \\ 0 & \text{o.w.}\end{cases} . \end{equation}

(Proof): By the previous claims we can assume W.L.O.G. that $v_S$ is reduced; i.e. \begin{equation} (\not\exists T \subset S)(w_T = 0 ). \end{equation} Let $m$ satisfy $(v_S)_m = \min\{ |(v_S)_i| \ | \ i \in [n] \}$ then by assumption either $e_m \not\in $ or $-e_m \not\in S$. QED

Therefore W.L.O.G. assume that $S$ satisfies the properties above and let $m \in [n]$ the index that satisfies the properties of the lemma and define \begin{equation} T = S \cup \{e_m \}, \end{equation} so that \begin{equation} (w_T)_i = \begin{cases} v_i \pm 1 & \text{if } i = m \\ v_i & \text{o.w.}\end{cases} . \end{equation} Notice that if $\| v_S \|= \sqrt k$ then $\|w_T \|= \sqrt{k \pm \epsilon}$ for some $\epsilon \leq |2v_m + 1|$; therefore we have that \begin{equation} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| \leq \frac{1}{\sqrt k \sqrt{k \pm \epsilon} } \left| \sqrt{k \pm \epsilon} v_S - \sqrt{k} w_T \right| \end{equation} \begin{equation} = \frac{1 }{ \sqrt k \sqrt{k \pm \epsilon} } \sqrt{ \left(\sqrt{k} v_m - \sqrt{k \pm \epsilon}(w_T )_m \right)^2+ ( \sqrt{k \pm \epsilon} - \sqrt{k})^2 \sum_{i \neq m } v_i^2 } \end{equation} \begin{equation} = \frac{1 }{ \sqrt k \sqrt{k \pm \epsilon} } \sqrt{ \left(\sqrt{k} v_m - \sqrt{k \pm \epsilon}v _m \pm \sqrt{k \pm \epsilon} \right)^2+ ( \sqrt{k \pm \epsilon} - \sqrt{k})^2 \sum_{i \neq m } v_i^2 }. \end{equation} But notice that \begin{equation} \left(\sqrt{k} v_m - \sqrt{k \pm \epsilon}v _m \pm \sqrt{k \pm \epsilon} \right)^2 = \end{equation} \begin{equation} = \left(\sqrt{k} v_m - \sqrt{k \pm \epsilon}v _m \pm \sqrt{k \pm \epsilon} \right)^2 -\left(\sqrt{k} v_m - \sqrt{k \pm \epsilon}v _m \right)^2 + \left(\sqrt{k} v_m - \sqrt{k \pm \epsilon}v _m \right)^2 \end{equation} \begin{equation} = 2\left(\sqrt{k} - \sqrt{k \pm \epsilon} \right) \left(k \pm \epsilon \right)v_m + \left(\sqrt{k} - \sqrt{k \pm \epsilon} \right)^2 v_m^2; \end{equation} and therefore have that \begin{equation} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| \leq \end{equation} \begin{equation} \leq \frac{1 }{ \sqrt k \sqrt{k \pm \epsilon} } \sqrt{ 2\left(\sqrt{k} - \sqrt{k \pm \epsilon} \right) \left(k \pm \epsilon \right)v_m + \left(\sqrt{k} - \sqrt{k \pm \epsilon} \right)^2 v_m^2 + ( \sqrt{k \pm \epsilon} - \sqrt{k})^2 \sum_{i \neq m } v_i^2 } \end{equation} \begin{equation} = \frac{1 }{ \sqrt k \sqrt{k \pm \epsilon} } \sqrt{ 2\left(\sqrt{k} - \sqrt{k \pm \epsilon} \right) \left(k \pm \epsilon \right)v_m + ( \sqrt{k \pm \epsilon} - \sqrt{k})^2 \sum_{i \in [n]} v_i^2 } \end{equation} \begin{equation} = \frac{1 }{ \sqrt k \sqrt{k \pm \epsilon} } \sqrt{ 2\left(\sqrt{k} - \sqrt{k \pm \epsilon} \right) \left(k \pm \epsilon \right)v_m + ( \sqrt{k \pm \epsilon} - \sqrt{k})^2 k } \end{equation}

Since $x \geq 0 \land y \geq 0 \implies \sqrt {x+y} \leq \sqrt x + \sqrt y $ we further get that \begin{equation} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| \leq \frac{ \sqrt{\left(\sqrt{k} - \sqrt{k \pm \epsilon} \right) \left(k \pm \epsilon \right)} }{ \sqrt k \sqrt{k \pm \epsilon} }\sqrt{2v_m} + \frac{\left| \sqrt{k \pm \epsilon} - \sqrt{k}\right| }{ \sqrt k \sqrt{k \pm \epsilon} } \sqrt{k}, \end{equation} which W.L.O.G., after possibly relableing $k \leftarrow k-\epsilon$, we have \begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| \leq \frac{ \sqrt{\left(\sqrt{k} - \sqrt{k + \epsilon} \right) \left(k + \epsilon \right)} }{ \sqrt k \sqrt{k + \epsilon} }\sqrt{2v_m } + \frac{ \sqrt{k + \epsilon} - \sqrt{k} }{ \sqrt{k + \epsilon} } \end{equation} \begin{equation} = \left(\frac{\sqrt{\epsilon} }{\sqrt 2 k^{\frac{7}{4}}} + \mathcal{O} \left(\frac{1}{k^{\frac{11}{4}}} \right) \right)\sqrt{2v_m } + \left(\frac{\epsilon}{2k^{\frac{3}{2}}} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) \right) \end{equation} \begin{equation} = \frac{\sqrt{\epsilon} }{\sqrt 2 k^{\frac{7}{4}}} \sqrt{2v_m } + \frac{\epsilon}{2k^{\frac{3}{2}}} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) = \frac{\sqrt{\epsilon} }{ k^{\frac{7}{4}}} \sqrt{v_m } + \frac{\epsilon}{2k^{\frac{3}{2}}} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right). \end{equation} by expanding the Puiseux series. But recall that either $\| v_S \|= k^{\frac{1}{2}}$ or $\| v_S \|= (k+\epsilon)^{\frac{1}{2}}$ (depending on whether we relabeled) by definition so that \begin{equation} |v_m| \leq \frac{1}{|\text{supp}(v_S)|}k^{\frac{1}{2}} \end{equation} by the pigeon-hole principle and therefore \begin{equation} \epsilon < 2|v_m|+1 \leq \frac{2}{|\text{supp}(v_S)|}k^{\frac{1}{2}}+1 \end{equation} and therefore \begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \frac{\sqrt{\epsilon} }{ k^{\frac{7}{4}}} \sqrt{v_m } + \frac{\epsilon}{2k^{\frac{3}{2}}} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) \end{equation} \begin{equation} = \frac{\sqrt{\epsilon} }{ \sqrt{|\text{supp}(v_S)|} k^{\frac{7}{4}}} k^{\frac{1}{4}} + \frac{k^{\frac{1}{2}}}{|\text{supp}(v_S)| k^{\frac{3}{2}}} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) \end{equation}

\begin{equation} = \frac{\sqrt{\epsilon} }{ \sqrt{|\text{supp}(v_S)|} k^{\frac{3}{2}}} + \frac{1}{|\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) \end{equation} \begin{equation} = \left( \frac{2}{|\text{supp}(v_S)|}k^{\frac{1}{2}}+1\right)^{\frac{1}{2}} \frac{1 }{ \sqrt{|\text{supp}(v_S)|} k^{\frac{3}{2}}} + \frac{1}{|\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) , \end{equation} and once again applying the rule $x \geq 0 \land y \geq 0 \implies \sqrt {x+y} \leq \sqrt x + \sqrt y $ we get that \begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \end{equation} \begin{equation} \left( \frac{2}{|\text{supp}(v_S)|}k^{\frac{1}{2}}\right)^{\frac{1}{2}} \frac{1 }{ \sqrt{|\text{supp}(v_S)|} k^{\frac{3}{2}}} +\frac{1 }{ \sqrt{|\text{supp}(v_S)|} k^{\frac{3}{2}}} +\frac{1 }{ |\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) \end{equation} \begin{equation} = \frac{\sqrt{2}k^{\frac{1}{4}} }{ |\text{supp}(v_S)| k^{\frac{3}{2}}} +\frac{1 }{ |\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{3}{2}}} \right) \end{equation} \begin{equation} = \frac{\sqrt{2}}{ |\text{supp}(v_S)| k^{\frac{5}{4}}} +\frac{1 }{ |\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{2}}} \right) \end{equation} \begin{equation} = \frac{1 }{ |\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{4}}} \right) \end{equation}

Therefore the bound you are looking for is \begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \frac{1 }{ |\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{4}}} \right) \end{equation}

In particular since $|\text{supp}(v_S)|$ is an integer and $|\text{supp}(v_S)|> 1$ we can weaken this to\begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \frac{1 }{ k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{4}}} \right) \end{equation}

Or recalling that $k = \| v_S \|^2$ we can equivalently right this as \begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \frac{1 }{ |\text{supp}(v_S)| \| v_S \|^2} + \mathcal{O} \left(\frac{1}{\| v_S \|^{\frac{5}{2}}} \right) \end{equation}

and\begin{equation} \max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \frac{1 }{ \| v_S \|^2 } + \mathcal{O} \left(\frac{1}{\| v_S \|^{\frac{5}{2}}} \right) \end{equation}

But most importantly we have that the vectors in $V_\text{sum}$ get arbitrarily close for large $n$; i.e. by choosing say $S = \{e_i \ | \ i \in [n]\}$ we have that \begin{equation} \lim_{n \to \infty }\max_{v_S \in V_\text{sum}} \min_{w_T \in V_\text{sum}} |\hat v_S- \hat w_T| = \end{equation} \begin{equation} =\lim_{n \to \infty } \frac{1 }{ |\text{supp}(v_S)| k} + \mathcal{O} \left(\frac{1}{k^{\frac{5}{4}}} \right) \leq \lim_{n \to \infty } \frac{1 }{ |n| n} + \mathcal{O} \left(\frac{1}{n^{\frac{5}{4}}} \right) = 0 \end{equation}