RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 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

 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}