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

Вычисление точного значения или получение нижней оценки на нелинейность $r$-го порядка для булевой функции (расстояние функции до множества функций степени не выше $r$) является сложной задачей (особенно для $r>1$). В ряде работ были получены нижние оценки на нелинейность различных порядков через значение алгебраической иммунности. Эти оценки оказываются достаточно сильными, если значение алгебраической иммунности максимально или близко к максимальному. В данной статье мы докажем утверждение, которое позволяет получать довольно сильные нижние оценки на нелинейность различных порядков и для многих функций с низкой алгебраической иммунностью.
Библиография: 6 названий.