On the number of homogeneous nondegenerate $p$-ary functions of the given degree

M. I. Anokhin

Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 5-16

Résumé

Let $p$ be a prime number and $F=\mathrm{GF}(p)$. Suppose $V_n$ is an $n$-dimensional vector space over $F$ and $e$ is a basis of $V_n$. Also, let $\varphi\colon V_n\to F$. The function $\varphi$ is called $e$-homogeneous if $\varphi(x)=\pi_{\varphi,e}(\mathbf x)$ for all $x\in V_n$, where $\pi_{\varphi,e}$ is an $n$-variate homogeneous polynomial over $F$ of degree at most $p-1$ in each variable and $\mathbf x$ is the coordinate vector of $x$ with respect to the basis $e$. The function $\varphi$ is said to be nondegenerate if $\deg\varphi\ge1$ and $\deg\partial_v\varphi=(\deg\varphi)-1$ for any $v\in V_n\setminus\{0\}$, where $(\partial_v\varphi)(x)=\varphi(x+v)-\varphi(x)$ for all $v,x\in V_n$. This notion was introduced by O. A. Logachev, A. A. Sal'nikov, and V. V. Yashchenko in the case when $p=2$. Our main results are as follows. First, we obtain a formula for the number $\mathrm{HN}_p(n,d)$ of $e$-homogeneous nondegenerate functions $\varphi\colon V_n\to F$ of degree $d$ (this number does not depend on $e$). Namely, if $n\ge1$ and $d\in\{1,\dots,n(p-1)\}$, then $\mathrm{HN}_p(n,d)=\sum_{k=0}^n(-1)^kp^{\binom k2+\genfrac{\{}{\}}{0pt}{}{n-k}d_p}\begin{bmatrix}n\\k\end{bmatrix}_p=\sum_{S\subseteq\{1,\dots,n\}}(-1)^{|S|}p^{\sigma(S)-|S|+\genfrac{\{}{\}}{0pt}{}{n-|S|}d_p}$, where $\genfrac{\{}{\}}{0pt}{0}md_p$ is the generalized binomial coefficient of order $p$, $\begin{bmatrix}n\\k\end{bmatrix}_p$ is the Gaussian binomial coefficient, and $\sigma(S)$ is the sum of all elements of $S$. The proof of this formula is based on the Möbius inversion. Previously, only formulas for $\mathrm{HN}_p(n,2)$ were known; unlike our formula, their forms depend on the parities of $p$ and $n$. Second, we prove that $\mathrm{HN}_p(n,d)\ge p^{\genfrac{\{}{\}}{0pt}{}nd_p}-1-(p^n-1)\left(p^{\genfrac{\{}{\}}{0pt}{}{n-1}d_p}-1\right)/(p-1)$ for any $d\ge1$ and $n\ge d/(p-1)$. Using this bound, we obtain that if $d\ge3$, then $\mathrm{HN}_p(n,d)\sim p^{\genfrac{\{}{\}}{0pt}{}nd_p}$ as $n\to\infty$. For $p=2$ the last two statements were proved by Yu. V. Kuznetsov. The proofs of our main results use a Jennings basis of the group algebra $FG_n$, where $G_n$ is an elementary abelian $p$-group of rank $n$.

Détail

Keywords: $p$-nh ary function, homogeneous function, nondegenerate function, degree of a function, group algebra, Jennings basis.
Mots-clés : Möbius inversion formula, augmentation ideal

Bibliographie

[1] Cheremushkin A. V., “An additive approach to defining the degree of nonlinearity of a discrete function”, Prikladnaya Diskretnaya Matematika, 2010, no. 2(8), 22–33 (in Russian)

[2] Logachev O. A., Sal'nikov A. A., Yashchenko V. V., “The nondegenerate normal form of Boolean functions”, Doklady RAN, 373:2 (2000), 164–167 (in Russian) | MR | Zbl

[3] Logachev O. A., Sal'nikov A. A., Smyshlyaev S. V., Yashchenko V. V., Boolean Functions in Coding Theory and Cryptology, LENAND Publ., Moscow, 2015 (in Russian)

[4] MacWilliams J., “Orthogonal matrices over finite fields”, Amer. Math. Monthly, 76:2 (1969), 152–164 | DOI | MR | Zbl

[5] Bondarenko B. A., Generalized Pascal triangles and pyramids, their fractals, graphs, and applications, The Fibonacci Association, Santa Clara, CA, 1993 | MR | Zbl

[6] Aigner M., Combinatorial Theory, Springer Verlag, Berlin et al., 1979 | MR | Zbl

[7] Kac V., Cheung P., Quantum Calculus, Springer Verlag, New York et al., 2002 | MR | Zbl

[8] Kuznetsov Yu. V., “On the number of nondegenerate Boolean forms”, Trudy laboratorii MGU po matematicheskim problemam kriptografii, 2000, 78–80 (in Russian)

[9] Anokhin M. I., “On some sets of group functions”, Matem. Zametki, 74:1 (2003), 3–11 (in Russian) | DOI | MR | Zbl

[10] Jennings S. A., “The structure of the group ring of a $p$-group over a modular field”, Trans. Amer. Math. Soc., 50:1 (1941), 175–185 | MR

[11] Zimmermann K.-H., Beiträge zur algebraischen Codierungstheorie mittels modularer Darstellungstheorie, Bayreuther mathematische Schriften, 48, 1994 (in German) | MR | Zbl

[12] Berman S. D., “On the theory of group codes”, Kibernetika, 1967, no. 1, 31–39 (in Russian) | Zbl

[13] Hill E. T., “The annihilator of radical powers in the modular group ring of a $p$-group”, Proc. Amer. Math. Soc., 25:4 (1970), 811–815 | MR | Zbl