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$?
 A: 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
A: 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
A: 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}$. 
