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

Рассматривается задача о приближении случайной булевой функции (СБФ) множеством всех булевых функций (БФ) второй степени нелинейности, т.е. квадратичных форм (КФ). Под СБФ мы подразумеваем БФ $f$, выбираемую из множества $B_{n}$ всех БФ от $n$ переменных в соответствии с равномерным распределением на $B_{n}$. Ранее в работе [1] решалась аналогичная задача о приближении СБФ множеством всех линейных БФ. В §1 получена основная теорема 1 о дважды экспоненциальном предельном распределении расстояния Хэмминга $\rho_{n}=\rho(f,Q_{n})$ от СБФ $f$ до множества $Q_{n}$ всех КФ. Величину $\rho_{n}$ можно рассматривать как нижнюю оценку радиуса покрытия $t_{n}$ для кода Рида–Маллера второго порядка длины $2^{n}$ [2], и теорема 1 дает асимптотическую (при $n\to\infty$) оценку числа таких БФ $f$ из $B_{n}$, для которых $t_{n}\ge\rho(f,Q_{n})\ge y_{n}$, где $y_{n}$ — некоторая последовательность, $y_{n}\to\infty$. Теорема 1 в работе получена как следствие более общей теоремы 2 о пуассоновском предельном распределении расстояния Хэмминга от СБФ до $k$-й ближайшей КФ. Доказательство теоремы 2 основано на сведении к схеме суммирования зависимых индикаторов и использовании методики [3], проведение которой в нашем случае по существу опирается на новый вариант многомерной центральной предельной теоремы в области больших уклонений (ЦПТБУ) для схемы серий специального вида. Формулировка и доказательство указанной ЦПТБУ вынесены в §2.
Авторы благодарны В. М. Сидельникову за постановку задачи и А. А. Грушо за обсуждение результатов.