# Number of binary vectors of a given Hamming weight in a subspace of the Hypercube

Let $n$ be a natural number. Let $U \subseteq \mathbb{F}_2^n$ be a linear subspace of dimension $k$. What is the maximum number of vectors in $U$ of Hamming weight $\ell$?

The case I am specifically interested in is $k \approx 0.99n$, $\ell = n/2$, where $n$ is a large enough even number. Is this number at most $C \cdot 2^k \cdot \frac{\binom{n}{n/2}}{2^n}$ for some constant $C$, independent of $n$?

For a closely related analysis of the number of vectors with hamming weight $\approx \frac{n}{2}$ in any large affine subspace of the hypercube, see Lemma 1 in Blais and Kane's "Testing Linear Functions":

http://math.stanford.edu/~dankane/TestingLinearFunctions.pdf

I just found out that the question (at least with the set of parameters written above) was asked by Ben-Or and answered by Linial and Samordinsky. Their paper proves that for any constant $r>1/2$ a subspace of dimension $k = rn$ has at most $C_r \cdot 2^k \cdot \frac{\binom{n}{n/2}}{2^n}$ vectors of weight $n/2$. http://www.cs.huji.ac.il/~nati/PAPERS/lin_codes.pdf

I think the answer is yes. Take a basis for $U$ and form a matrix where these are the rows. We can then put the matrix in row-reduced echelon form and call it $A$. Each column then has at most one 1. By permuting the columns, you can further suppose that each row consists of a block of 1's; the lengths of the blocks are non-decreasing and all the 0's are at the end. Call the resulting matrix $\tilde A$, and let the subspace it spans be $\tilde U$. Putting in row-reduced echelon form does not change the subspace spanned, so that the rows of $A$ still span $U$. Applying the column permutation does not change Hamming weights of vectors, so that $\tilde U$ has the same distribution of Hamming weights as $U$.

Assume that $k=0.99n$, so that each $\tilde A$ has $0.99n$ rows. At most $0.02n$ of these can have two 1's.

Let $W(x)$ denote the Hamming weight of the vector $x$. Your question is whether $\mathbb P_{\tilde U}(W(x)=\ell)\le C\mathbb P_{\mathbb F_2^n}(W(x)=\ell)$ (where $\mathbb P_V$ is the uniform distribution on the subspace $V$).

Let the rows of $\tilde A$ be $v_1,\ldots,v_{k}$. Any vector in $\tilde U$ can be uniquely expressed as $\epsilon_1 v_1+\ldots+\epsilon_k v_k$. Its weight is $\epsilon_1 W(v_1)+\ldots+\epsilon_k W(v_k)$. Of course $\epsilon_k$ is uniformly distributed on $\{0,1\}$. Given this we are asking about the distribution of the random variable $N=\epsilon_1 W(v_1)+\ldots+\epsilon_k W(v_k)$. Write this as $N_1+N_2$, where $N_1=\sum_{i\le i_0}\epsilon_i W(v_i)$ and $N_2=\sum_{i>i_0}\epsilon_i W(v_i)$; and $i_0$ is chosen so that $W(v_i)=1$ if and only if $i\le i_0$.

Now $\mathbb P(N_1+N_2=\ell)\le \sup_r \mathbb P(N_1+N_2=\ell|N_2=r) \le \mathbb P(N_1=\lfloor i_0/2\rfloor)=2^{-i_0}\binom{i_0}{\lfloor i_0/2\rfloor}$. This is known to be approximately $\sqrt {2/\pi i_0}\le 1.01 \sqrt{2/\pi n}$.

• I don't see why the row-reduced echelon form has at most one 1 in each column. If the first $k$ columns contain an identity matrix, the other columns can have anything at all. May 12, 2014 at 7:19
• Hmmm... I see... but still you've got $k$ columns with a single 1, leaving only a handful with multiple 1's... Let me think some more... May 12, 2014 at 15:23