Subset of vectors whose sum has a large norm

Question

In Rudin - Real & Complex Analysis we have the following

Lemma 6.3. If $z_1, \ldots, z_n \in \mathbb{C}$ then there is a subset $S \subseteq \{1,\ldots,n\}$ for which $$\left|\sum_{k \in S} z_k\right| \geq \frac1{\pi} \sum_{k=1}^n |z_k|.$$

This is used by Rudin to prove that a complex measure $\mu$ has a bounded total variation $|\mu|$. This lemma is presented also as an exercise in Krantz - Techniques of Problem Solving (Chap. 2, Ex. 34) and Greene and Krantz - Function Theory of One Complex Variable (Chap. 1, Ex. 57). Moreover, considering $z_k = e^{2\pi i k / n}$, $k=1,2,\ldots,n$, as $n \to \infty$, one can prove that the constant $\frac1{\pi}$ is in fact optimal.

Reading Rudin proof, it turn out that the algebraic structure of $\mathbb{C}$ plays no special role, so that $\mathbb{C}$ is considered as $\mathbb{R}^2$. Actually, without too much difficulty, one can adapt the proof to show the following

Theorem 1. For any integer $d \geq 1$ there exists an absolute constant $C_d > 0$, such that if $v_1, \ldots, v_n \in \mathbb{R}^d$ then there exists a subset $S \subseteq \{1, \ldots, n\}$ for which $$\left\|\sum_{k \in S} v_k\right\| \geq C_d \sum_{k=1}^n \|v_k\|,$$ where $\|\cdot\|$ is the euclidean norm of $\mathbb{R}^d$. In particular, we can take $$C_d = \frac{\Gamma(\tfrac{d}{2})}{2 \sqrt{\pi}\, \Gamma(\tfrac{d+1}{2})}$$ where $\Gamma$ is Euler's Gamma function, so $C_1 = \tfrac1{2}$, $C_2 = \tfrac1{\pi}$ and these two are optimal.

In conclusion, my questions are: Are there some references for Theorem 1, and these kind on inequalities, in the literature? What can we say about the best constants $C_d$? And about the size of $S$?

I think the topic is related in some ways to spherical codes.

Thank you.

Answer 1

Your constants are optimal, by the same arrangement: large number of unit vectors uniformly distributed over the sphere. Clearly, an optimal S consists of all vectors from a half space, say $x_1>0$. Then $$ C_d \le \frac{1}{S_{d-1}} \int_{S_{d-1}^+} x_1\, d\omega_{d-1}(x) $$ ($S_d$=surface area of the $d$-sphere), and the right-hand side evaluates to $$ \frac{S_{d-2}}{S_{d-1}} \int_0^1 x(1-x^2)^{(d-3)/2}\, dx = \frac{S_{d-2}}{(d-1)S_{d-1}} , $$ which is equal to your $C_d$.

Answer 2

Finally, I found that a stronger result is known:

Theorem. For any integer $d \geq 1$ and $\delta \in [0,1]$, let $$C_{d,\delta} = \frac{\Gamma(\tfrac{d}{2})(1-\delta^2)^{(d-1)/2}}{2\sqrt{\pi}\,\Gamma(\tfrac{d+1}{2})}.$$ Then for all $v_1, \ldots, v_n \in \mathbb{R}^d$ there exists $u \in \mathbb{R}^d$ with $\|u\| = 1$ such that if $S$ is the set of $k \in \{1,\ldots,n\}$ with $v_k \cdot u \geq \delta \|v_k\|$, then $$\left\|\sum_{k \in S} v_k\right\| \geq C_{d,\delta} \sum_{k=1}^n \|v_k\|.$$ Moreover, the constant $C_{d,\delta}$ is optimal.

I. Netuka, and J. Veselý - An inequality for finite sums in $\mathbb{R}^m$. Časopis pro pěstování matematiky 103 (1978), p. 73--77.