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

CC BY-SA 4.0
2021-08-03T13:55:26.813Z
Are there any constraints on $m$?  Can you choose all the coordinates of  the points in $P$ to be in $\mathbb{F}_2$?
Peter Shor 
CC BY-SA 4.0
2021-08-03T15:06:08.733Z
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)$.
user6584
CC BY-SA 4.0
2021-08-03T15:15:57.020Z
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.
Peter Shor 
CC BY-SA 4.0
2021-08-03T16:49:42.763Z
You are right, though it doesn’t affect the question.
user6584
<coding-theory><polynomials><finite-fields>
BCH codes and polynomials with many values in a subfield
user6584
# BCH codes and polynomials with many values in a subfield

(Asked by: username_0 on 2021-08-02)

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?

**Tags:** coding-theory, polynomials, finite-fields
> **Comments:**
> **username_1**: Are there any constraints on $m$?  Can you choose all the coordinates of  the points in $P$ to be in $\mathbb{F}_2$?  
> **username_0**: 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)$.  
> **username_1**: 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.  
> **username_0**: You are right, though it doesn’t affect the question.  

---

## 0 answers

