Back to Search
Start Over
LARGE SIGNED SUBSET SUMS
- Source :
- Mathematika. 67:579-595
- Publication Year :
- 2021
- Publisher :
- Wiley, 2021.
-
Abstract
- We study the following question: for given $d\geq 2$, $n\geq d$ and $k \leq n$, 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 $\pm 1$ 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 $\ell_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.<br />15 pages. Updated from the printed version: planar bounds are slightly corrected, and reference to sharp bound on c(2,n,n) is added
- Subjects :
- General Mathematics
010102 general mathematics
Value (computer science)
Metric Geometry (math.MG)
0102 computer and information sciences
01 natural sciences
Combinatorics
52A47, 52A40, 05A99
Mathematics - Metric Geometry
010201 computation theory & mathematics
Unit vector
Norm (mathematics)
FOS: Mathematics
Mathematics - Combinatorics
Vector system
Combinatorics (math.CO)
0101 mathematics
Special case
Mathematics
Subjects
Details
- ISSN :
- 20417942 and 00255793
- Volume :
- 67
- Database :
- OpenAIRE
- Journal :
- Mathematika
- Accession number :
- edsair.doi.dedup.....6604129da829bd934a1a8c8fffc2b4cb