×

On the number of homogeneous nondegenerate \(p\)-ary functions of a given degree. (Russian. English summary) Zbl 1515.16022

Summary: Let \(p\) be a prime number and \(F=\text{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 \(\text{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 \(\text{HN}_p(n,d)=\sum_{k=0}^n(-1)^k p^{\binom{k}{2}+\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}{}{m}{d}_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 \(\text{HN}_p(n,2)\) were known; unlike our formula, their forms depend on the parities of \(p\) and \(n\). Second, we prove that \(\text{HN}_p(n,d)\ge p^{\genfrac{\{}{\}}{0pt}{}{n}{d}_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 \(\text{HN}_p(n,d)\sim p^{\genfrac{\{}{\}}{0pt}{}{n}{d}_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\).

MSC:

16S34 Group rings
05A15 Exact enumeration problems, generating functions
20C07 Group rings of infinite groups and their modules (group-theoretic aspects)

References:

[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) · Zbl 07301723
[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) · Zbl 1053.06010
[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 · Zbl 0186.33702 · doi:10.1080/00029890.1969.12000160
[5] Bondarenko B. A., Generalized Pascal triangles and pyramids, their fractals, graphs, and applications, The Fibonacci Association, Santa Clara, CA, 1993 · Zbl 0792.05001
[6] Aigner M., Combinatorial Theory, Springer Verlag, Berlin et al., 1979 · Zbl 0415.05001
[7] Kac V., Cheung P., Quantum Calculus, Springer Verlag, New York et al., 2002 · Zbl 0986.05001
[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) · Zbl 1072.20001 · doi:10.4213/mzm240
[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 · JFM 67.0072.03
[11] Zimmermann K.-H., Beiträge zur algebraischen Codierungstheorie mittels modularer Darstellungstheorie, Bayreuther mathematische Schriften, 48, 1994 (in German) · Zbl 0820.94017
[12] Berman S. D., “On the theory of group codes”, Kibernetika, 1967, no. 1, 31-39 (in Russian) · Zbl 0216.55803
[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 · Zbl 0206.03503
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.