ИГУ - «Известия Иркутского государственного университета»

«Известия Иркутского государственного университета»

Журнал ИГУ

Список выпусков > Серия «Математика» . 2014. Том 10

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

Автор(ы)
А. С. Балюк

Аннотация

Представления функций над конечными полями, в том числе полиномиальные, в настоящее время активно исследуются. Одним из основных направлений этих исследований является сложность таких представлений. В данной работе исследуется сложность задания функций квазиполиномами над конечными полями.

Квазиполином можно рассматривать как полином многих переменных, в котором вхождения xi0, . . . , xik−1 одной из переменных заменены на функции из некоторого множества {g0(xi), . . . , gk−1(xi)} линейно независимых одноместных функций.

Под сложностью полинома над конечным полем обычно понимают количество слагаемых в нем, число вхождений переменных или степень. В случае квазиполиномов напрямую можно оценивать количество слагаемых, число вхождений переменных и степень требуют обобщения. В статье в качестве сложности квазиполинома исследуется количество слагаемых в нем. Для случая квазиполиномов по модулю простого k ранее была известна верхняя оценка такой сложности, а именно, сложность задания квазиполиномами n-местной функции над конечным полем простого порядка k не превосходит величины k·kn/(k+1).

В работе получена верхняя оценка сложности представления квазиполиномами функций над произвольным конечным полем порядка q, которая при q ≥ 3 усиливает ранее известную верхнюю оценку, полученную для случая квазиполиномов по модулю простого числа. А именно, если q = kn, где k — простое, а n ≥ 1 для любой n-местной функции над конечным полем порядка q сложность её задания квазиполиномами ограничена сверху величиной (q-1)·qn/(q-q1-q).

Ключевые слова
конечное поле, полином, квазиполином, сложность

УДК
519.715

Литература

1. Пантелеев В. И. Полиномиальные разложения k-значных функций по операторам дифференцирования и нормализации / В. И. Пантелеев // Изв. высш. учеб. заведений. Математика. – 1998. – № 1. – С. 17–21.

2. Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм / Н. А. Перязев // Алгебра и логика. – 1995. – Т. 34. – №. 3. – С. 323–326.

3. Селезнева С. Н. О сложности k-значных функций в одном классе полиномов / С. Н. Селезнева // Проблемы теоретической кибернетики : материалы XVI Междунар. конф. (Нижний Новгород, 20–25 июня 2011 г.). – Н. Новгород : Изд-во Нижегор. ун-та, 2011. – С. 430–434.

4. Селезнева С. Н. О сложности представления функций многозначных логик поляризованными полиномами / С. Н. Селезнева // Дискрет. математика. – 2002. – Т. 14, № 2. – С. 48–53.