For points $P=\{x_1, \ldots, x_n\} \subset {\mathbb F}_{2^m}$ define $$\mathcal{C}(P, t) =\{(f(x_1), \ldots, f(x_n)) \mid \mbox{$f\in {\mathbb F}_{2^m}[X]$ has degree $t$}\}$$ and $\mathcal{C}'(P, t) = \mathcal{C}(P, t) \cap {\mathbb F}_2^n$. These definitions are similar to definitions of Reed-Solomon and BCH codes, respectively, however I do not require that $P$ be all the nonzero points of ${\mathbb F}_{2^m}$ and, as will be clear, I am interested in slightly different properties than those of standard coding theory.
For some desired dimension $k$, is it possible to choose a set of points $P$ and a degree bound $t$ so that (1) $t$ not much larger than $k$, (2) $n$ is a constant factor larger than $t$, and (3) $\mathcal{C}'(P, t)$ has dimension (at least) $k$?
Related questions: for $f \in {\mathbb F}_{2^m}$ of degree $t$, what is the largest number of points on which $f$ evaluates to an element of ${\mathbb F}_2$? Is there a nice characterization of polynomials achieving that bound?
