Комбинаторно-вероятностные и геометрические методы в пороговой логике

Рассматривается задача оценивания числа $N_n$ пороговых функций от $n$ переменных. Ранее для логарифма этого числа были получены следующие асимптотические по $n$ оценки: $n^2/2\lesssim\log_2N_n\lesssim n^2$. В работе доказана лемма, связывающая число областей, на которые $n$-мерное евклидово пространство разбивается конечным множеством гиперплоскостей, с числом аффинных подпространств, порожденных пересечениями гиперплоскостей. С помощью этой леммы показано, что для достаточно больших $n$ справедливо неравенство $\log_2N_n>n^2(1-10/\ln n)$. Тем самым установлена асимптотика $\log_2N_n\thicksim n^2,\, n^2\to\infty$.
Введено понятие графа пороговых функций и указаны асимптотики для $\log_2N_n(M)$ при раз личных $M$, где $N_n(M)$ – число пороговых функций с $M$ единицами.