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?

  • $\begingroup$ Are there any constraints on $m$? Can you choose all the coordinates of the points in $P$ to be in $\mathbb{F}_2$? $\endgroup$ Commented Aug 3, 2021 at 13:55
  • $\begingroup$ 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)$. $\endgroup$
    – user6584
    Commented Aug 3, 2021 at 15:06
  • $\begingroup$ 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. $\endgroup$ Commented Aug 3, 2021 at 15:15
  • $\begingroup$ You are right, though it doesn’t affect the question. $\endgroup$
    – user6584
    Commented Aug 3, 2021 at 16:49


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.