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

Квазиполином можно рассматривать как полином многих переменных, в котором вхождения x_i⁰, . . . , x_i^k−1 одной из переменных заменены на функции из некоторого множества {g₀(x_i), . . . , g_k−1(x_i)} линейно независимых одноместных функций.

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

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

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.