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

Квазиполином можно рассматривать как полином многих переменных, в котором вхождения 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).