О числе однородных невырожденных p-ичных функций заданной степени | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/1

О числе однородных невырожденных p-ичных функций заданной степени

Пусть p - простое число, F = GF(p), Vn - n-мерное векторное пространство над F, е - базис пространства Vn. Пусть также р: Vn ^ F. Функция р называется e-однородной, если р(х) = nv,e(x) для всех х G Vn, где nv,e - однородный многочлен от n переменных над F, имеющий степень не более p - 1 по каждой переменной, а x - набор координат вектора х в базисе е. Функция р называется невырожденной, если deg р ^ 1 и deg dvр = (deg р) - 1 для любого v G Vn \ {0}, где (dvр)(х) = р(х + v) - р(х) для всех v,x G Vn. Получена формула для числа HNp(n, d) е-однородных невырожденных функций р: Vn ^ F, имеющих степень d (это число не зависит от е), а именно: если n ^ 1 и d G {1,... ,n(p - 1)}, n k p то HNp(n,d) = Е (-1)fcp(2)+{"dfe}p n = Е (-1)|S|pCT(S)-|S|+{n dS|}p, где k=0 SC{1.....n} n - биномиаль- k m \ - обобщённый биномиальный коэффициент порядка p dp p ный коэффициент Гаусса; ct(S) - сумма всех элементов множества S. Доказано, что HNp(n, d) ^ p{d}p - 1 - (pn - 1) (p{ d }p - 1 J /(p - 1) для любых d ^ 1 и jnj n ^ d/(p-1). Используя эту оценку, получаем, что если d ^ 3, то HNp(n, d) ~ p{d}p при n ^ то.

On the number of homogeneous nondegenerate p-ary functions of the given degree.pdf 1. Определения, обозначения и необходимые факты Фиксируем простое число p и обозначим через F поле из p элементов. В настоя- щей работе все объекты и понятия линейной алгебры рассматриваются над основным полем F. Для произвольного множества X через FX обозначается множество всех функций из X в F. Это множество является векторным пространством относительно поточечных операций сложения и умножения на элементы из F. Если S - какая-либо система векторов произвольного векторного пространства, то (S) обозначает линейную оболочку этой системы. Пусть также n - произвольное целое неотрицательное число и Vn - n-мерное векторное пространство (над полем F). Элементы множества FVn есте- ственно назвать p-ичными функциями. Выберем какой-либо базис e = (e1 , . . . , e n ) пространства Vn. Иногда будем выби- рать этот базис некоторым специальным образом. Пусть также ^ +то при n ^ то. dp Поэтому 1 -г^--> 0 при n ^ то. (23) p { d J p Кроме того, непосредственно проверяется, что И fn - 1\ = Ру!/n - 1\ >/ n - 1\ > (n - 1 4p I d Jp = г=Л d - ijp d - > \d - 1 In! In - 1 | (см. также [5, формула (1.13)]). Поэтому - | ^ j - n ^ +то при n ^ то, так как ( ) - n ~ nd-1 /(d - 1)! при n ^ то (напомним, что d - 1 > 2). Следовательно, Vd - V (pn _ 1)(p{n d 1}р - 1) 1 ^^-^- ~ гП _г„_n п ^ 0 при n ^ то. (24) p{ d } p p{ d } p { d } p jnj Из (22)-(24) вытекает теперь, что HNp(n, d)/p{d}p ^ 1 при n ^ то. Таким образом, jnj HNp(n, d) ~ p{d}p при n ^ то. ■ Автор благодарит анонимного рецензента, отзыв которого побудил автора к существенной переработке первоначальной версии настоящей работы.

Ключевые слова

p-ичная функция, однородная функция, невырожденная функция, степень функции, формула обращения Мёбиуса, групповая алгебра, фундаментальный идеал, базис Дженнингса, p-ary function, homogeneous function, nondegenerate function, degree of a function, Mobius inversion formula, group algebra, augmentation ideal, Jennings basis

Авторы

ФИООрганизацияДополнительноE-mail
Анохин Михаил ИгоревичМосковский государственный университет имени М. В. Ломоносовакандидат физико-математических наук, старший научный сотрудник Института проблем информационной безопасностиanokhin@mccme.ru
Всего: 1

Ссылки

Черемушкин А. В. Аддитивный подход к определению степени нелинейности дискретной функции // Прикладная дискретная математика. 2010. №2(8). С. 22-33.
Логачев О. А., Сальников А. А., Ященко В. В. Невырожденная нормальная форма булевых функций // Доклады РАН. 2000. Т. 373. №2. С. 164-167.
Логачев О. А., Сальников А. А, Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: ЛЕНАНД, 2015.
MacWilliams J. Orthogonal matrices over finite fields // Amer. Math. Monthly. 1969. V. 76. No. 2. P. 152-164.
Бондаренко Б. А. Обобщенные треугольники и пирамиды Паскаля, их фракталы, графы и приложения. Ташкент: Фан, 1990.
Айгнер М. Комбинаторная теория. М.: Мир, 1982.
Кац В. Г., Чен П. Квантовый анализ. М.: МЦНМО, 2005.
Кузнецов Ю. В. О числе невырожденных булевых форм // Труды лаборатории МГУ по математическим проблемам криптографии. 2000. С. 78-80.
Анохин М. И. О некоторых множествах групповых функций // Матем. заметки. 2003. Т. 74. №1. С. 3-11.
Jennings S. A. The structure of the group ring of a p-group over a modular field // Trans. Amer. Math. Soc. 1941. V. 50. No. 1. P. 175-185.
Циммерман К.-Х. Методы теории модулярных представлений в алгебраической теории кодирования. М.: МЦНМО, 2011.
Берман С. Д. К теории групповых кодов // Кибернетика. 1967. №1. С. 31-39.
Hill E. T. The annihilator of radical powers in the modular group ring of a p-group // Proc. Amer. Math. Soc. 1970. V.25. No. 4. P. 811-815.
 О числе однородных невырожденных p-ичных функций заданной степени | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/1

О числе однородных невырожденных p-ичных функций заданной степени | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/1