Часть 3. Математические модели

Оценка максимального числа ненулевых коэффициентов многочлена функции при действии группы перестановок на таблицу значений функции

А. О. Гремяков

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Для коэффициентов полиномов функций над конечными полями $F_q$ рассматривается задача отыскания нижней оценки на максимум минимума числа ненулевых коэффициентов в полиноме, где максимум берется по всем функциям, а минимум - по их преобразованиям, соответствующим различным заданиям поля. При этом возможно рассматривать различные типы таких преобразований. В работе получена оценка $L(q) \geq q-2$ на максимум минимума числа ненулевых коэффициентов в полиноме для определенного типа преобразований, оставляющих нулевой элемент поля на месте.

Ключевые слова: коэффициенты полиномов, булевы функции, полином булевой функции, таблица значений функции.