Prikladnaya Diskretnaya Matematika
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






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 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)(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, Mö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}


Linking options:
  • http://mi.mathnet.ru/eng/pdm628
  • http://mi.mathnet.ru/eng/pdm/y2018/i3/p5

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Number of views:
    This page:97
    Full text:41
    References:6

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021