New bounds on the nonlinearity of PN and APN functions over finite fields

The nonlinearity of a vectorial function over a finite field is defined here as the Hamming distance from it to the set of affine mappings in the space of values of all vectorial functions. For an arbitrary field of $q$ elements, lower bounds on the nonlinearity of PN and APN functions of $n$ variables are obtained, equal to $q^n - \sqrt { q^n - 3 \cdot 2^{-2}} - 2^{-1}$ and $q^n - \sqrt { 2q^n - 7 \cdot 2^{-2}} - 2^{-1}$ respectively, and improving the previously known bounds for the Boolean case. It is shown that the quantity $q^n - n - 1$ can be used as an upper bound on the nonlinearity of such functions. For $q = 2,3,4$, the exact values of the nonlinearity PN and APN of functions in small dimension are obtained.