Idempotent and p-potent quadratic functions: Distribution of nonlinearity and co-dimension

Abstract

The Walsh transform $\hat{Q}$ of a quadratic function $Q:F_{p^n}\to F_p$ satisfies $|\hat{Q}(b)|\in \{0,p^{\frac{n+s}{2}}\}$ for all $b\in F_{p^n}$, where $0\le s\le n-1$ is an integer depending on $Q$. In this article, we study the following three classes of quadratic functions of wide interest. The class ${\mathcal{C}}_1$ is defined for arbitrary $n$ as ${\mathcal{C}}_1=\{Q(x)=Tr({\sum }_{i=1}^{\lfloor (n-1)/2\rfloor }{a}_i{x}^{2^i+1}):a_i\in F_2\}$, and the larger class ${\mathcal{C}}_2$ is defined for even $n$ as ${\mathcal{C}}_2=\{Q(x)=Tr({\sum }_{i=1}^{(n/2)-1}{a}_i{x}^{2^i+1})+\mathrm{T}{\mathrm{r}}_{n/2}(a_{n/2}{x}^{2^{n/2}+1}):a_i\in F_2\}$. For an odd prime $p$, the subclass $\mathcal{D}$ of all $p$-ary quadratic functions is defined as $\mathcal{D}=\{Q(x)=Tr({\sum }_{i=0}^{\lfloor n/2\rfloor }{a}_i{x}^{p^i+1}):a_i\in F_p\}$. We determine the distribution of the parameter $s$ for ${\mathcal{C}}_1,{\mathcal{C}}_2$ and $\mathcal{D}$. As a consequence we obtain the distribution of the nonlinearity for the rotation symmetric quadratic Boolean functions, and in the case $p>2$, our results yield the distribution of the co-dimensions for the rotation symmetric quadratic $p$-ary functions, which have been attracting considerable attention recently. We also present the complete weight distribution of the subcodes of the second order Reed-Muller codes corresponding to ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$.