13
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Your value $C_d=1/\pi$ for all $d\geq 2$ puzzles me. It seems to contradict the phenomenon of measure concentration along the equator on a sphere of high dimensions. This implies (I believe) that the optimal value of $C_d$ tends to $0$ for $d\rightarrow \infty$. $\endgroup$ Mar 28, 2014 at 17:17
  • $\begingroup$ @RolandBacher Oh, you are right, thanks! I redid my calculations and found a mistake simplifying Euler's Gamma function, but now $C_d$ should be correct and actually $C_d \to 0$ as $d \to \infty$. $\endgroup$
    – user40023
    Mar 28, 2014 at 21:06

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ OK, it works, thanks. Moreover, taking $v_1, v_2, \ldots \in \mathbb{R}^d$ equidistributed over $\mathbb{S}^{d-1}$ it follows that $|S| \sim n / 2$ as $n \to \infty$. $\endgroup$
    – user40023
    Mar 29, 2014 at 9:31
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The following reference may also be of help: "On a new method of analysis and its applications" by Paul Turán, published posthumously, with the assistance of Gábor Halász and János Pintz, 1984, John Wiley & Sons $\endgroup$ Apr 4, 2014 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.