Ambrus Gergely: Large signed sums and the polarization constant of convex bodies

Vector balancing problems have been studied extensively for at least half a century, while their siblings, anti-balancing problems received much less attention. In this talk, we make up for this deficit by considering the following problem . Given a norm on $\mathbb{R}^d$, and a positive integer $n$, what is the largest constant $C(n)$ so that for any set of $n$ unit vectors $u_1, \ldots, u_n$ (in the chosen norm), one can assign signs $\varepsilon_i  \in \pm 1$ to them for which the signed sum $\varepsilon_1 u_1 + \ldots \varepsilon_n u_n$ has norm at least $C(n)$? Equivalently, one would like to partition the set of vectors into two parts so that the corresponding sums are far from each other in the specified norm. We show that the worst case (i.e. the smallest $C(n)$) corresponds to the maximum norm, while $C(n)$ is asymptotically the largest for the Euclidean norm. En route, we also introduce the notion of the polarization constant of general convex bodies, and demonstrate its connection to the question of large signed sums.

This is joint work with Florian Grundbacher (TU Munich).