2018-13 Bernoulli vectors

Assume that \( x \in \mathbb{R}^n \) with at least \( k \) non-zero entries \( ( k> 0 ) \). Let
\[
A = \{ y \in \{-1, 1\}^n : y \cdot x = 0 \}.
\]
Prove that \( |A| \leq k^{-1/2} 2^n \).

GD Star Rating
loading...
2018-13 Bernoulli vectors, 3.5 out of 5 based on 12 ratings