Приближение булевых функций мономиальными

Каждая булева функция от $n$ переменных отождествляется с функцией $F\colon Q\to \nobreak P$, где $Q=\mathit{GF}(2^n)$, $P=\mathit{GF}(2)$. Ранее Йоссером и Гонгом для $n=2\lambda$ было установлено существование функций $F$, которые одинаково плохо приближаются не только линейными функциями (функциями $\operatorname{tr}(\mu x)$, где $\mu\in Q^*$ и $\operatorname{tr}\colon Q\to P$ есть функция след), но и собственными мономиальными функциями (функциями $\operatorname{tr}(\mu x^\delta)$, где $(\delta,2^n-1)=1)$). Такие функции $F$ названы гипер-бент-функциями (ГБ-функциями, ГБФ), и описан класс ГБФ со свойством $F(0)=0$, непустой при любом $n=2\lambda$. Это функции вида $F(x)=G(x^{2^\lambda-1})$ такие, что уравнение $F(x)=1$ имеет ровно $(2^\lambda-1)2^{\lambda-1}$ решений в $Q$. В данной работе указаны существенные ограничения на параметры произвольной ГБФ, показывающие, что класс ГБ-функций существенно меньше класса бент-функций. В частности, показано, что любая ГБ-функция есть бент-функция степени нелинейности $\lambda$ и при некоторых $n$ (например, в случае, когда $\lambda>2$, $2^\lambda-1$ – простое число или $\lambda\in\{4,9,25,27\}$) класс ГБ-функций исчерпывается функциями вида $F(x)=G(x^{2^\lambda-1})$, описанными Йоссером и Гонгом. Для $n=4$, кроме 10 ГБ-функций указанного вида, существует еще 18 других ГБ-функций со свойством $F(0)=0$. Вопрос о существовании других гипер-бент-функций при $n>4$ остается открытым.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 05–01–01048 и 05–01–01018, и программой Президента Российской Федерации поддержки ведущих научных школ, гранты НШ 1910.2003.1 и НШ 2358.2003.9.