Sum of the values of a polynomial over a finite field

Question

I’ve come across this problem in a coding theory course, and neither I nor several of my colleagues could solve it to our satisfaction. Let $F:=\mathrm{GF}{\left(q\right)}$ denote the field with $q$ elements, where $q$ is a prime power, and let $f\in F[x]$ be a polynomial of degree at most $q-2$. I’m trying to show that $$\sum_{\alpha\in F}{f{\left(\alpha\right)}}=0_F.$$ The condition that $\mathrm{deg}(f)\leq q-2$ seems to be crucial: consider the polynomial $f(x)=x\in\mathbb{Z}_{2}[x]$. $f{\left(\overline{0}\right)}+f{\left(\overline{1}\right)}=\overline{0}+\overline{1}=\overline{1}\ne\overline{0}$. Any hints would be appreciated.

Answer 1

Nothing wrong with Andres' answer (+1). Offering a possibly technically simpler approach based on the cyclicity of the multiplicative group $F^*=GF(q)\setminus\{0\}$. We know that the group consists of powers of a generator (aka a primitive element) $g$ of order $q-1$. Thus $F^*=\{1,g,g^2,g^3,\ldots,g^{q-2}\}.$

So if $k$ is an exponent, $0< k\le q-2$, then $$ \sum_{\alpha\in F}\alpha^k=\sum_{\alpha\in F^*}\alpha^k=\sum_{i=0}^{q-2}g^{ki}=\frac{1-g^{(q-1)k}}{1-g^k}=\frac{1-1}{1-g^k}=0 $$ by the formula for a geometric sum.

OTOH if $k=0$, then $$ \sum_{\alpha\in F}\alpha^0=\sum_{\alpha\in F}1=q\cdot 1=0. $$

The claim follows by taking a linear combination of sums like these.

===

This result comes in handy in coding theory. For example in the study of the duals of Reed-Solomon codes. It also shows up at other places such as in this question, where it is used as a tool of discrete $GF(q)$-valued Fourier analysis of functions $F^*\to F^*$.

===

EDIT:

An even simpler way is the following. Let's fix an exponent $k$, $0<k<q-1$. The polynomial $x^k-1$ is of degree $k$, so it has at most $k$ zeros in $GF(q)$. Thus there exists a non-zero element $\beta\in F^*$ such that $\beta^k\neq1$. The summation variable $\alpha$ ranges over $GF(q)$ while $\beta\alpha$ does, so the sum $$ S(k)=\sum_{\alpha\in GF(q)}\alpha^k=\sum_{\beta\alpha\in GF(q)}\beta^k\alpha^k= \sum_{\alpha\in GF(q)}\beta^k\alpha^k=\beta^kS(k). $$ As $\beta^k\neq1$ this equation implies that $S(k)=0$.

Answer 2

You just need to show that $\sum_{\alpha\in F}\alpha^k=0$ for $k=0,1,\dots,q-2$. This is clear for $k=0$ (understanding $0^0$ as $1$). But $\alpha^q-\alpha=0$ for all $\alpha$ so $\alpha^{q-1}-1=0$ for all $\alpha\ne0$, and the result follows from the Newton identities.

Answer 3

Here is a solution that uses almost only linear algebra. In short: taking the sum of their values in all elements of$~K$ is a linear form $\sigma$ on the vector space of polynomials over $F$ of degree${}<q$, which is invariant under shifting ($X:=X+a$); that space has a basis formed of a shift-orbit of monic degree $q-1$ polynomials; being determined by its values on this basis, $\sigma$ must be a multiple of the form consisting of taking the coefficient of $X^{q-1}$, hence vanish on lower degree polynomials. Details follow.

Let $V$ be the vector space of polynomials over $F$ of degree${}<q$, and $W=F^F$ the vector space of functions on$~F$. There is a linear map $\phi:V\to W$ that sends a polynomial to its polynomial function $\phi(P):x\mapsto P[x]$, and there are actions by the additive group of$~F$ by translations on polynomials $a\cdot P=P[X-a]$ and on functions $a\cdot f: x\mapsto f(x-a)$, with which $\phi$ is compatible: $\phi(a\cdot P)=a\cdot\phi(P)$. Summing over all values in$~F$ defines a linear form $S:W\to F$ namely $S(f)=\sum_{x\in F}f(x)$, which is clearly translation invariant: $S(a\cdot f)=S(f)$ for all $a\in F$. The linear form $L:V\to K$ that takes the coefficient of $X^{q-1}$ is also translation invariant $L(a\cdot P)=L(P)$, because of the absence in$~V$ of higher degree monomials than $X^{q-1}$.

Since the polynomials of degree${}<d-1$ form $\ker(L)$, one needs to show $\ker(L)\subseteq\ker(S\circ\phi)$.

Define the polynomial $P_0=\prod_{c\in F\setminus\{0\}}(X+c)\in V$, whose function $\phi(P_0)$ has as support the singleton set $\{0\}$. Then for the $q$ polynomials $P_a=a\cdot P_0$ of its translation orbit, the functions $\phi(P_a)$ have disjoint non empty supports, so they are linearly independent, and the$~P_a$ must be linearly independent as well. And $\dim(V)=q$, so $\{\, P_a\mid a\in F\,\}$ forms a basis of$~V$. Now by the invariance of$~S$ and the compatibility of$~\phi$ with translation, the linear form $S\circ\phi$ takes a constant value$~d$ on this basis. But $L$ takes the constant value$~1$ on that basis, so $S\circ\phi=dL$, which implies $\ker(L)\subseteq\ker(S\circ\phi)$ as desired.

Remark: it is immediate from the definitions of$~P_0$ and$~S$ that $d=\prod_{c\in F\setminus\{0\}}c\neq0$, so that one in fact has $\ker(L)=\ker(S\circ\phi)$ (none of the polynomials of degree $q-1$ satisfy the equation of the question); indeed it is easy to see that $d=-1$ (a generalisation of the non-trivial part of Wilson's theorem) since each pair of distinct inverse elements contributes nothing to the product. But these precisions were not needed to answer the question. Similarly it is easy to see that $\phi$ is injective (a polynomial of degree${}<q$ with $q$ roots must be zero), and since $\dim(V)=q=\dim(W)$ it is also surjective; while these facts motivated my approach, they turned out not to be needed in the proof either.