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

Известно, что максимальное расстояние между булевой функций от $2n$ переменных и классом аффинных булевых функций от $2n$ переменных равно $2^{2n-1}-2^{n-1}$. В работе исследуется расстояние между классом максимально-нелинейных булевых функций от $2n$ переменных и классом булевых функций от $2n$ переменных, у которых в полиноме Жегалкина присутствует не более $k$ нелинейных слагаемых. Показано, что при любом фиксированном $k$ и $n\to\infty$ это расстояние равно $2^{2n-1}-3^k\cdot2^{n-1}+o(2^{n-1})$.
Работа поддержана Российским фондом фундаментальных исследований, проект 10–01–00475–а.