What is the maximum number vectors of Hamming weight at most $w$ in a $d$-dimensional subspace of $\mathbb{F}\_p^n$, where $w,d,p$ are constant and $p$ is odd. (The Hamming weight is the number of nonzero coordinates.) In particular, does an upper bound of the form $d^{Cw}$ hold for some constant $C$ depending only on $p$?



Low-Hamming weight vectors in low-dimensional subspaces of $\mathbb{F}_p^n$
**Answer.** It is $\sum\_{k=0}^w (p-1)^k{d\choose k}$ (for a coordinate subspace, the equality holds).


**Proof.** Denote by $N(f)$, for $f=(x\_1,\ldots,x\_n)\in \mathbb{F}\_p^n\setminus 0$, the minimal $i$ for which $x\_i\ne 0$. By Gauss elimination we may find a basis $f\_1,\ldots,f\_d$ in our $d$-dimensional space such that $N(f\_1)<N(f\_2)<\ldots<N(f\_d)$. Note that any linear combination of more than $w$ $f\_i$'s (with non-zero coefficients) has more than $w$ non-zero coordinates. Thus all vectors with Hamming weight at most $w$ are linear combinations of at most $w$ $f\_i$'s, so the bound.


