# BCH codes and polynomials with many values in a subfield

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?

• Are there any constraints on $m$? Can you choose all the coordinates of the points in $P$ to be in $\mathbb{F}_2$? Commented Aug 3, 2021 at 13:55
• No constraints on m. Choosing $P$ to be in ${\mathbb F}_2$ is fine, but then $n \leq 2$ and we want $n = \Omega(t)$. Commented Aug 3, 2021 at 15:06
• The $C(P,t) = \{(f(x_1), \ldots, f(x_n) )\}$ seemed to me like you were treating $P$ as a vector and not a set. Does the order of the elements in $P$ matter? If it does, morally it's not a set. Commented Aug 3, 2021 at 15:15
• You are right, though it doesn’t affect the question. Commented Aug 3, 2021 at 16:49