Index bounds for character sums of polynomials over finite fields (Q329186): Difference between revisions

Let \(q\) be a power of a prime \(p\). Let \(g(x)\) be a polynomial over \(\mathbb F_q\) of degree \(n>0\) and let \(\psi : \mathbb F_q\to \mathbb C^*\) be a non-trivial additive character. If \((p,n)=1\) and \(g\) is not of the form \(f^p-f+c\) (\(f\in\mathbb F_q[x]\), \(c\in\mathbb F_q\)) then the Weil bound is: \[ \left|\sum_{x\in\mathbb F_q} \psi (g(x))\right|\leq (n-1)\sqrt{q}. \] Note that for large \(n\) this is worse than the trivial upper bound \(q\). Write \(g(x)=x^rf(x^{(q-1)/\ell})+b\) and let \(n_0\) be the number of \(\ell\)th roots of unity in \(\mathbb F_q\) that are zeros of \(f\). The authors show that: \[ \left| \sum_{x\in\mathbb F_q} \psi (g(x))-\frac{qn_0}{\ell}\right| \leq (\ell -n_0)\, \gcd\left( r,\frac{q-1}{\ell}\right) \sqrt{q}. \] This can be better than the Weil bound. In particular, if \(\ell\) (called the index of \(g\)) is small but \(n\) is large then this new bound can be non-trivial while the Weil bound is not. The authors use their bound to improve Weil's bound on the number of solutions to the Artin-Schreier equation \(y^q-y=g(x)\). This in turn is used to get better bounds on the weights of codewords in certain cyclic codes. They prove their bound by breaking the sum into sums over cyclotomic sets and applying the Weil bound to each subsum.