<s>[INST] $\varepsilon$-net of a $d$-dimensional unit ball formed by power set of $V = \{+1, 0 -1\}^d$ 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$.
 [/INST] 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}

</s>