Теоретические основы прикладной дискретной математики
О числе однородных невырожденных $p$-ичных функций заданной степени
М. И. Анохин Институт проблем информационной безопасности
Московского государственного университета имени
М. В. Ломоносова, г. Москва, Россия
Аннотация:
Пусть
$p$ – простое число,
$F=\mathrm{GF}(p)$,
$V_n$ –
$n$-мерное векторное пространство над
$F$,
$e$ – базис пространства
$V_n$. Пусть также
$\varphi\colon V_n\to F$. Функция
$\varphi$ называется
$e$-однородной, если
$\varphi(x)=\pi_{\varphi,e}(\mathbf x)$ для всех
$x\in V_n$, где
$\pi_{\varphi,e}$ – однородный многочлен от
$n$ переменных над
$F$, имеющий степень не более
$p-1$ по каждой переменной, а
$\mathbf x$ – набор координат вектора
$x$ в базисе
$e$. Функция
$\varphi$ называется невырожденной, если
$\deg\varphi\ge1$ и
$\deg\partial_v\varphi=(\deg\varphi)-1$ для любого
$v\in V_n\setminus\{0\}$, где
$(\partial_v\varphi)(x)=\varphi(x+v)-\varphi(x)$ для всех
$v,x\in V_n$. Получена формула для числа
$\mathrm{HN}_p(n,d)$ $e$-однородных невырожденных функций
$\varphi\colon V_n\to F$, имеющих степень
$d$ (это число не зависит от
$e$), а именно: если
$n\ge1$ и
$d\in\{1,\dots,n(p-1)\}$, то $\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}$, где
$\genfrac{\{}{\}}{0pt}{0}md_p$ – обобщённый биномиальный коэффициент порядка
$p$;
$\begin{bmatrix}n\\k\end{bmatrix}_p$ – биномиальный коэффициент Гаусса;
$\sigma(S)$ – сумма всех элементов множества
$S$. Доказано, что $\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)$ для любых
$d\ge1$ и
$n\ge d/(p-1)$. Используя эту оценку, получаем, что если
$d\ge3$, то $\mathrm{HN}_p(n,d)\sim p^{\genfrac{\{}{\}}{0pt}{}nd_p}$ при
$n\to\infty$.
Ключевые слова:
$p$-ичная функция, однородная функция, невырожденная функция, степень функции, формула обращения Мёбиуса, групповая алгебра, фундаментальный идеал, базис Дженнингса.
УДК:
519.115+
519.113.5+
512.624+
512.552.7
DOI:
10.17223/20710410/41/1