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

Представления функций над конечными полями, в том числе полиномиальные, в настоящее время активно исследуются. Одним из основных направлений этих исследований является сложность таких представлений. Вопросы полиномиальных представлений булевых функций довольно хорошо изучены. Для многих классов полиномов найдены точные значения сложности таких представлений.
В последнее время возрос интерес к полиномиальным представлениям функций над конечными полями порядка больше двух и кольцами вычетов по составному модулю. Исследование сложности таких представлений сопряжено с определенными трудностями, и даже в довольно простых классах полиномиальных форм найдены только несовпадающие верхние и нижние оценки сложности.
В настоящей работе внимание уделено поляризованным полиномам над конечным полем порядка 4. Полиномы этого класса представляют собой суммы произведений множителей определенного вида. Каждый полином реализует некоторую $n$-местную функцию над конечным полем. Под сложностью полинома понимается число ненулевых слагаемых в нем. Каждая функция может быть реализована несколькими различными полиномами из одного класса. Под сложностью функции в классе полиномов понимается минимально возможная сложность реализующего ее полинома из этого класса.
Ранее были известны эффективные нижние оценки сложности в классе поляризованных полиномов для случая булевых и трехзначных функций и более слабая мощностная оценка для случая функций над конечным полем простого порядка.
В настоящей статье получена эффективная нижняя оценка сложности функций над конечным полем порядка 4, аналогичная ранее известным оценкам для булевых и трехзначных функций.