In this exercise, we will prove the so called Griesmer Bound. For any [n,k,d]q , prove that n ≥ k−1 i X=0 » q d i ¼中文回答

这题是要证明 Griesmer Bound ，对于任意 [n,k,d]q ，有 n ≥ k−1 i X=0 » q d i ¼。

证明如下：

考虑构造一个 k-1 阶的仿射空间 AG(k-1,q)，其中每个点代表一个 k-1 阶的多项式。此时，我们可以将每个 n 阶的多项式表示成一个 k-1 阶的多项式加上一个 k-1 阶以下的余项。

假设 d 是该码的最小距离，那么存在一个非零多项式 f(x) 使得它的次数小于 d，但是每个非零多项式 g(x) 满足 f(x) 和 g(x) 乘积的次数都大于等于 d。这意味着我们可以用 f(x) 来表示该码中的每个非零多项式。

此外，我们知道一个 k-1 阶的多项式最多有 q^(k-1) 个不同的系数，所以 AG(k-1,q) 中最多有 q^(k-1) 个点。由于 f(x) 的次数小于 d，所以它至多有 q^d 个根。因此，对于任意一个非零多项式 g(x)，它和 f(x) 的乘积最多有 q^d 个根，这些根对应着 AG(k-1,q) 的一些点，因此码中的非零多项式数量最多为 q^(k-1) / q^d = q^(k-d-1) 个。

因此，我们得出结论：n ≥ k-1 + q^(k-d-1)。