Best lower bound for sum of vectors “close together”

banach-spacesfunctional-analysislinear algebranormed-spaces

Suppose $x_1, x_2, \dots, x_n$ are norm one vectors in a Banach space such that for any $i\neq j$, $||x_i-x_j||\leq\varepsilon$ where $\varepsilon$ is very small. What is, in general, the best lower bound for $||x_1+x_2+\dots+x_n||$? When I say in general I mean the lower bound that follows from the properties of a norm and not for a particular norm. In other words, what's the worst best estimate?

When $n=3$, we can write:

$$
||3x_1||=||x_1+x_2+x_3-(x_2-x_1)-(x_3-x_1)||\leq||x_1+x_2+x_3||+2\varepsilon
$$

Therefore $||x_1+x_2+x_3||\geq 3-2\varepsilon$.

However, I did not use that $||x_2-x_3||\leq\varepsilon$. Just from $||x_2-x_1||\leq\varepsilon$ and $||x_3-x_1||\leq\varepsilon$ it follows that $||x_2-x_3||\leq 2\varepsilon$. But my condition is stronger, that $||x_2-x_3||\leq\varepsilon$. Intuitively, this should improve the $3-2\varepsilon$ bound above and the "correct" one should be $3-\varepsilon$, and perhpas $n-\varepsilon$ in general, but I am not sure.

This feels like an easy application of triangle inequality. What am I not seeing here?

Best Answer

Consider $X=\ell^\infty$ with $\sup$ norm. For $0<\varepsilon <{1\over n-1}$ and $1\le k\le n$ let $$x_k=(1-\varepsilon){\mathbf 1}+\varepsilon\delta_k,$$ where $\delta_k$ denotes the sequence with entry $1$ on the $k$-th coordinate and $0$ otherwise, while ${\mathbf 1}$ denotes the constant sequence with all coordinates equal $1.$ Then $\|x_k\|=1,$ $\|x_k-x_l\|=\varepsilon, $ for $k\neq l,$ and $$\|x_1+x_2+\ldots +x_n\|=n-(n-1)\varepsilon $$ By the triangle inequality for any normed space we have $$\|x_2+x_2+\ldots +x_n\|\ge n-(n-1)\varepsilon ,\quad \|x_k\|=1$$ Hence the lower estimate is the worst possible.

Related Question