Improved bounds found for sign patterns in matrices with plus minus one entries
Three Standard Deviations Suffice While One Does Not
Discrete Mathematics
Summary
This paper studies how to assign plus or minus signs to columns of a matrix so that the largest resulting value is as small as possible. A previous result said you can keep this maximum value under about six times the square root of the matrix size. The authors improve this to less than three times the square root, showing fewer signs are needed to control the outcome. They also find that one times the square root is not always possible by constructing special large matrices where the maximum has to be slightly bigger than that.
What this means in practice
- •For algorithm designers: Use tighter bounds on sign assignments in matrix computations to improve algorithms requiring discrepancy control.
- •For cryptography engineers: Understand limitations on controlling outputs of sign-multiplied matrices to strengthen construction of cryptographic protocols.
A theory result. No direct application yet.
Authors
Victor Reis, Zhao Song
Abstract
Spencer's 1985 ``six standard deviations suffice'' theorem shows that every $A \in [-1,1]^{n \times n}$ has a sign vector $x \in \{-1,1\}^n$ with $\|Ax\|_\infty \le 6\sqrt{n}$. We show the upper bound $\sqrt{3\operatorname{arsinh}(10)}\sqrt{n}+4 < 2.9992 \sqrt{n} + 4$ by directly rounding the minimizer of a potential function to a vertex of the cube. We also show that, for every power of two $n \ge 2^{50}$, there exists a matrix $A \in \{-1,1\}^{n \times n}$ such that $\|Ax\|_\infty >1.0000002\sqrt{n}$ for every choice of signs $x \in \{-1,1\}^n$. The construction simply replaces a $2^{-22}$ fraction of the columns of a Hadamard matrix with independent random sign vectors. This is the first improvement over the $\sqrt{n}$ lower bound of Olson and Spencer (1978), which uses a Hadamard matrix.