Divisibility and Solvability

By Incnis Mrsi - Own work, CC BY-SA 3.0

The p-divisibility of exponential sums over finite fields can be used to determine solvability of systems of polynomial equations and have applications to coding theory and cryptography

$\newcommand{\sN}{\mathcal{N}}$ $\newcommand{\X}{\mathbf{X}}$ $\newcommand{\xx}{{\bf x}}$ $\newcommand{\yy}{{\bf y}}$ $\newcommand{\Fq}{{\mathbb{F\!}_q}}$ $\newcommand{\Fp}{{\mathbb{F\!}_p}}$ $\newcommand{\FF}{\mathbb{F}_2}$ $\newcommand{\F}{\mathbb{F}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\Qp}{{\mathbb{Q\!}_p}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\Zp}{\mathbb{Z}_p}$Exponential sums over finite fields are an important tool for solving mathematical problems and have applications to many other areas. The sum associated to a polynomial $F \in \Fq[\X]=\Fq[X_1, X_2, \ldots, X_n]$ has the form $$S(F)=\sum_{\xx\in \left(\Fq\right)^{n}}\left( e^{\frac{2\pi i}{p}} \right)^{Tr_{\F_q/\F_p}\left(F(\xx)\right)},$$
where $\Fq$ is the finite field with $p$ elements and $Tr$ is the trace function.

The explicit evaluation of the exponential sum of a polynomial might be a difficult task, but for many applications it is enough to have estimates for its $p$-divisibility (the highest power of $p$ dividing $S$). These estimates can be used to determine properties in coding theory such as the weight distribution, covering radius and minimum distance; they can also can be used to provide families of functions that are balanced and hence are good candidates for applications to cryptography.


The $p$-divisibility of exponential sums can provide an answer to the fundamental question of whether a system of polynomial equations has solutions over a finite field. If one can determine that the exponential sum associated to a system has exact $p$-divisibility, one guarantees that the system is solvable.

At the Emmy Noether Lab we have worked on determining sufficient conditions to guarantee that exponential sums of families of systems of polynomial equations have exact $p$-divisibility and hence are solvable.

The Covering Method

The covering method is an elementary and intuitive way to estimate or compute the $p$-divisibility of exponential sums, which is particularly convenient in the applications. In several collaborations we generalized to any prime field the covering method introduced by Moreno-Moreno for characteristic 2.

Comments are closed.