# $\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$$.

• @domotorp, there would be some $\varepsilon$ such that any vector on the surface of the $d$-dimensional unit ball is at a distance at most $\varepsilon$ from one of the vectors in $V_{\text{sum}}$ right? That's the reason I am calling it an $\varepsilon$-net. – usercsw May 17 '20 at 8:07
• What is the motivation behind asking this question? Is there a specific application you have in mind? – Pedro Juan Soto May 20 '20 at 5:29
• It is hard to say anything useful for general $S$. Are you looking for a feasible algorithm to compute such an upper bounds (or exact value) or do you have some restrictions on the $S$. In full generality, $|S|$ could be ${v,-v}$ and the maximal isolation is 2. Maybe one can say more if we lower bound $|S|$, but because there are many ways to duplicate vectors this will be probably not too helpful. – M. Winter Jun 19 '20 at 7:02
• The "surface of the unit ball" is usually called the "unit sphere". – YCor Oct 17 '20 at 7:15
• Purely out of curiosity where did you find this set $V_{sum}$? – Christian Chapman Oct 17 '20 at 16:38

## 1 Answer

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}$$