In a paper I have read on random Bernoulli matrices it was stated that for any subspace $V\subseteq \mathbb{R}^n$ of dimension at most $l$ one has: $$|V\cap \{\pm 1\}^n|\leq 2^l$$ With no proof. A reference was provided. However, the claim does not appear there.
How should this be proven?
On
By an elementary duality argument, there is a subset $A$ of $\{1,\dots,n\}$ such that the natural projection $\Pi : \mathbb{R}^n \to \mathbb{R}^A$ (that selects coordinates indexed by $A$) induces an isomorphism between $V$ and $\mathbb{R}^A$ (in particular, the cardinal of $A$ is $\ell$). Since $\Pi$ sends $\{\pm 1\}^n \cap V$ into $\{\pm 1\}^{A}$, and is injective on $\{\pm 1\}^n \cap V$ (because it is injective on $V$), we see that the cardinal of $\{\pm 1 \}^n \cap V$ is less than $2^\ell$.
Consider the solid $n$ dimensional hypercube $Q$ with side length $4$, with vertices $\{\pm 2\}^n$. We can partition this into $2^n$ sub-cubes with side length $2$, with a cube $Q_i$ centered at vector $i$ for each $i\in \{\pm 1\}^n$.
Let $S=Q\cap V$. For each $j\in V\cap \{\pm1\}^n$, let $S_j=Q_j\cap V$. Note that $S_j$ and $S$ are both sections of an $l$-dimensional plane through the center of a cube, the difference being that the cube for $S_j$ has half the side length for the cube for $S$. Letting $\def\vol{\text{vol}}\vol$ denote $l$-dimensional volume, this proves
$\sum_{j\in V\cap \{\pm1\}^n} \vol(S_j)\le \vol(S)$
$\vol(S_j)=2^{-l}\vol(S)$, because $S_j$ is congruent to $S$ scaled down by a factor of $2$.
Combined, these prove $|V\cap \{\pm1\}^n|\le 2^l$.
I believe this volume argument can be modified to prove the same result is true even when $V$ is an arbitrary affine subspace, not just a linear one.