LARGE SIGNED SUBSET SUMS

DOI10.1112/MTK.12091MaRDI QIDQ6072632zbMATH OpenOpenAlexFDO

Authors Gergely Ambrus, Bernardo González Merino

Publication date 15 September 2023

Published in Mathematika (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.13164

zbMATH Keywords

\(\ell_p\)-polarizationvector sum minimization

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Convexity and finite-dimensional Banach spaces (including special norms, zonoids, etc.) (aspects of convex geometry) (52A21) Other problems of combinatorial convexity (52A37) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Abstract: We study the following question: for given $dgeq2$, $ngeqd$ and $kleqn$, what is the largest value $c(d,n,k)$ such that from any set of $n$ unit vectors in $mathbb{R}^d$, we may select $k$ vectors with corresponding signs $pm1$ so that their signed sum has norm at least $c(d,n,k)$? The problem is dual to classical vector sum minimization and balancing questions, which have been studied for over a century. We give asymptotically sharp estimates for $c(d,n,k)$ in the general case. In several special cases, we provide stronger estimates: the quantity $c(d,n,n)$ corresponds to the $el{l}_p$-polarization problem, while determining $c(d,n,2)$ is equivalent to estimating the coherence of a vector system, which is a special case of $p$-frame energies. Two new proofs are presented for the classical Welch bound when $n=d+1$. For large values of $n$, volumetric estimates are applied for obtaining fine estimates on $c(d,n,2)$. Studying the planar case, sharp bounds on $c(2,n,k)$ are given. Finally, we determine the exact value of $c(d,d+1,d+1)$ under some extra assumptions.

Recommendations

• Small subset sums
• A note on norms of signed sums of vectors
• Polarization, sign sequences and isotropic vector systems
• On a conjecture of Kömlos about signed sums of vectors inside the sphere
• Balancing vectors in the max norm

Cites work

• A Solution of the "Plank Problem"
• Additive colourful Carathéodory type results with an application to radii
• Balancing games
• Balancing unit vectors
• Balancing unit vectors
• Convex geometry and functional analysis
• Discrete energy on rectifiable sets
• Ellipsoids of maximal volume in convex bodies
• Energy on spheres and discreteness of minimizing measures
• Equiangular lines and spherical codes in Euclidean space
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 1149836 (Why is no real title available?)
• scientific article; zbMATH DE number 1380581 (Why is no real title available?)
• scientific article; zbMATH DE number 2117213 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Lower bounds on the maximum cross correlation of signals (Corresp.)
• Minkowski concentricity and complete simplices
• Nearly orthogonal vectors and small antipodal spherical codes
• On some combinatorial questions in finite-dimensional spaces
• On the Power of Linear Dependencies
• Polarization, sign sequences and isotropic vector systems
• Selectively balancing unit vectors
• Sets of unit vectors with small subset sums
• Small subset sums
• The asymmetry of complete and constant width bodies in general normed spaces and the Jung constant
• Universal optimal configurations for the \(p\)-frame potentials

Cited in

(6)

• Polarization, sign sequences and isotropic vector systems
• A note on norms of signed sums of vectors
• Small subset sums
• On series of signed vectors and their rearrangements
• Balancing sets of vectors
• Isoperimetric problems for zonotopes

This page was built for publication: LARGE SIGNED SUBSET SUMS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6072632)