Combinatorial-probability and geometric methods in threshold logic

Yu. A. Zuev

Diskretnaya Matematika, Tome 3 (1991) no. 2, pp. 47-57.

Résumé

We consider the problem of estimating the number $N_n$ of threshold functions in $n$ variables. The following estimates, asymptotic with respect to $n$, were obtained earlier for the logarithm of this number: $n^2/2\lesssim\log_2N_n\lesssim n^2$. We prove a lemma connecting the number of regions into which the $n$-dimensional Euclidean space is partitioned by a finite set of hyperplanes, with the number of affine subspaces that are generated by the intersections of the hyperplanes. By means of this lemma we prove that for sufficiently large $n$ the inequality $\log_2N_n>n^2(1-10/\ln n)$ holds. In the same way we establish the asymptotic formula $\log_2N_n\\thicksim n^2$, $n\to\infty$. We introduce the concept of the graph of threshold functions and show the asymptotics for $\log _2N_n(M)$ for various $M$, where $N_n(M)$ is the number of threshold functions with $M$ units.