 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

 Personal entry: Login: Password: Save password Enter Forgotten password? Register

 Prikl. Diskr. Mat., 2018, Number 41, Pages 5–16 (Mi pdm628) Theoretical Backgrounds of Applied Discrete Mathematics

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

M. I. Anokhin

Information Security Institute, Lomonosov University, Moscow, Russia

Abstract: 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,…,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,…,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 Mö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)(p^{\genfrac{ {\}}{0pt} {n-1}d_p}-1)/(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$.

Keywords: $p$-nh ary function, homogeneous function, nondegenerate function, degree of a function, Möbius inversion formula, group algebra, augmentation ideal, Jennings basis.

 Funding Agency Grant Number Russian Foundation for Basic Research 16-01-00226

DOI: https://doi.org/10.17223/20710410/41/1  Full text: PDF file (678 kB) References: PDF file   HTML file

Bibliographic databases:  UDC: 519.115+519.113.5+512.624+512.552.7

Citation: M. I. Anokhin, “On the number of homogeneous nondegenerate $p$-ary functions of the given degree”, Prikl. Diskr. Mat., 2018, no. 41, 5–16 Citation in format AMSBIB
\Bibitem{Ano18} \by M.~I.~Anokhin \paper On the number of homogeneous nondegenerate $p$-ary functions of the given degree \jour Prikl. Diskr. Mat. \yr 2018 \issue 41 \pages 5--16 \mathnet{http://mi.mathnet.ru/pdm628} \crossref{https://doi.org/10.17223/20710410/41/1} \elib{https://elibrary.ru/item.asp?id=35688724} 

 SHARE:      •  Contact us: math-net2021_09 [at] mi-ras ru Terms of Use Registration to the website Logotypes © Steklov Mathematical Institute RAS, 2021