This is a $d$-dimensional generalisation of the post Inequality with Complex Numbers. (See my comment under Robert Israel's answer.)

Generalising Potato's proof for $d$-dimensions, we can show the following theorem:

Theorem. For any positive integer $d$, there exists $c_d > 0$ such that the following holds:

For any $n$ and any $n$-tuple $(v_1, v_2, \ldots, v_n)$ of $d$-dimensional vectors (i.e., $v_i \in \mathbb{R}^d$), there exists a subset $J \subseteq \{ 1, 2, \ldots, n\}$ such that $$ \left\| \sum_{j \in J} v_j \right\| \geqslant c_d \cdot \sum_{i=1}^{n} \| v_i \|. $$

I skip my proof of this theorem because it is exactly analogous to Potato's proof; with two modifications: (a) our vectors are in $\mathbb{R}^d$, rather than $\mathbb{C}$ or $\mathbb{R}^2$); (b) I am using the notation $v_i$ in place of $z_i$ here, since it feels more natural in this context.

Now, my question (slightly informally stated) is

Question. For any fixed $d$, what is the largest value $c_d^{\ast}$ of $c_d$ for which the above theorem is true?

If we cannot find the exact value $c_d^{\ast}$, it will be interesting to find nontrivial upper and lower bounds. Working out the details of the above proof, we can show that $c_d$ can be taken to be (at least) $\frac{1}{2d}$; i.e., $c_d^{\ast} \geqslant \frac{1}{2d}$. Can we say anything better?

It is easy to see that $c_1 = \frac{1}{2}$, which matches the above bound for $d=1$. Robert Israel's answer shows that $c_2 = \frac{1}{\pi}$ (exactly!), which is strictly better than $\frac{1}{2 \cdot 2} = \frac{1}{4}$. However, his proof seems to make an essential use of complex numbers that I could not generalise to $d$ dimensions.

  • $\begingroup$ If anyone wants to see the proof I skipped, I will be happy to include it. $\endgroup$ – Srivatsan Jan 26 '12 at 2:54

This simply extends this answer by Robert Israel to $\mathbb{R}^d$.

Define $$ R(x)=\left\{\begin{array}{ll}x_1&\text{when }x_1\ge0\\0&\text{when }x_1\lt0\end{array}\right.\tag{1} $$ Integrating $R(x)$ over the sphere of radius $r$ yields $$ \omega_{d-2}\;r^d\int_0^{\pi/2}\cos^{d-2}(\theta)\sin(\theta)\;\mathrm{d}\theta=\omega_{d-2}\;\frac{r^d}{d-1}\tag{2} $$ Integrating $1$ over the sphere of radius $r$ yields $$ \begin{align} \omega_{d-2}\;r^{d-1}\int_{-\pi/2}^{\pi/2}\cos^{d-2}(\theta)\;\mathrm{d}\theta &=2\;\omega_{d-2}\;r^{d-1}\int_0^{\pi/2}\cos^{d-2}(\theta)\;\mathrm{d}\theta\\ &=\omega_{d-2}\;r^{d-1}\mathrm{B}\left(\frac{d-1}{2},\frac12\right)\\ &=\omega_{d-2}\;r^{d-1}\frac{\Gamma\left(\frac{d-1}{2}\right)\Gamma\left(\frac12\right)}{\Gamma\left(\frac d2\right)}\tag{3} \end{align} $$ using the identity $$ \int_0^{\pi/2}\sin^{\alpha-1}(t)\;\cos^{\beta-1}(t)\;\mathrm{d}t =\frac12\mathrm{B}\left(\frac{\alpha}{2},\frac{\beta}{2}\right)\tag{4} $$ Therefore, the mean of $R(x)$ over the surface of the sphere of radius $r$ is $(2)$ divided by $(3)$: $$ \frac{r\;\Gamma\left(\frac{d}{2}\right)}{(d-1)\Gamma\left(\frac{d-1}{2}\right)\Gamma\left(\frac{1}{2}\right)}=\frac{r\;\Gamma\left(\frac{d}{2}\right)}{2\Gamma\left(\frac{1}{2}\right)\Gamma\left(\frac{d+1}{2}\right)}\tag{5} $$ Thus, the mean of $\displaystyle\sum_{k=1}^nR(x_j)$ over all rotations of the sphere is $$ \frac{\Gamma\left(\frac{d}{2}\right)}{2\Gamma\left(\frac{1}{2}\right)\Gamma\left(\frac{d+1}{2}\right)}\sum_{k=1}^n|x_k|\tag{6} $$ Thus, for some rotation of the sphere, we must have $$ \sum_{k=1}^nR(x_k)\ge\frac{\Gamma\left(\frac{d}{2}\right)}{2\Gamma\left(\frac{1}{2}\right)\Gamma\left(\frac{d+1}{2}\right)}\sum_{k=1}^n|x_k|\tag{7} $$ To see that $(7)$ is the best possible independent of $n$, consider an "even" distribution of $n$ points as $n\to\infty$. This estimates the $(d{-}1)$-dimensional analog of the Riemann sum for the integral in $(2)$.

Therefore, $$ c_d=\frac{\Gamma\left(\frac{d}{2}\right)}{2\Gamma\left(\frac{1}{2}\right)\Gamma\left(\frac{d+1}{2}\right)}\tag{8} $$

As shown in the appendix to this answer, $\displaystyle\lim_{x\to\infty}\frac{\Gamma(x+\alpha)}{x^\alpha\Gamma(x)}=1$. Therefore, asymptotically, $$ c_d\sim\dfrac{1}{\sqrt{2\pi d}}\tag{9} $$ which is the geometric mean of $\dfrac{1}{\pi}$ and $\dfrac{1}{2d}$, the upper bound derived in the question.

The first several values of $c_d$ are: $$ \begin{array}{c|cccc} d&1&2&3&4&5&6&7&8\\ \hline\\ c_d&\frac{1}{2}&\frac{1}{\pi}&\frac{1}{4}&\frac{2}{3\pi}&\frac{3}{16}&\frac{8}{15\pi}&\frac{15}{96}&\frac{48}{105\pi} \end{array}\tag{10} $$ Furthermore, $(8)$ implies that $$ c_{d+2}=\dfrac{d}{d+1}c_d\tag{11} $$

  • $\begingroup$ This is one bloody cool answer! +1. $\endgroup$ – Jonas Teuwen Jan 26 '12 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.