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

Представления функций над конечными полями, в том числе полиномиальные, в настоящее время активно исследуются. Одним из основных направлений этих исследований является сложность таких представлений.
В данной работе исследуется сложность задания функций квазиполиномами над конечными полями. Квазиполином можно рассматривать как полином многих переменных, в котором вхождения $x_i^0, \dots, x_i^{k-1}$ одной из переменных заменены на функции из некоторого множества $\{g_0(x_i), \dots, g_{k-1}(x_i)\}$ линейно независимых одноместных функций.
Под сложностью полинома над конечным полем обычно понимают количество слагаемых в нем, число вхождений переменных или степень. В случае квазиполиномов напрямую можно оценивать количество слагаемых, число вхождений переменных и степень требуют обобщения. В статье в качестве сложности квазиполинома исследуется количество слагаемых в нем. Для случая квазиполиномов по модулю простого $k$ ранее была известна верхняя оценка такой сложности, а именно, сложность задания квазиполиномами $n$-местной функции над конечным полем простого порядка $k$ не превосходит величины $\frac{k}{k+1}k^n$.
В работе получена верхняя оценка сложности представления квазиполиномами функций над произвольным конечным полем порядка $q$, которая при $q \geqslant 3$ усиливает ранее известную верхнюю оценку, полученную для случая квазиполиномов по модулю простого числа. А именно, если $q = k^n$, где $k$ — простое, а $n \geqslant 1$, для любой $n$-местной функции над конечным полем порядка $q$ сложность её задания квазиполиномами ограничена сверху величиной $ \frac{q-1}{q-q^{1-q}}q^n$.