Estimates for the number of threshold functions

A. A. Irmatov

Diskretnaya Matematika, Tome 8 (1996) no. 4, pp. 92-107

Résumé

We obtain a lower bound and refine Schläfli's upper bound for the number of threshold functions. As a consequence it is shown that the assertion that the number of threshold functions is asymptotically equal to $$ 2\sum_{i=0}^n{2^n-1\choose i} $$ is equivalent to the assertion that the portion of the collections consisting of $n-1$ different $(1,-1)$-vectors $v_1,\ldots,v_{n-1}$ of length $n$ such that $\newspan(v_1,\ldots,v_{n-1})\cap \{1,-1\}^n$ coincides with the set of all vectors of the form $(\pm v_1,\ldots,\pm v_{n-1})$ tends to 1 as $n \to \infty$.The work was supported by the Russian Foundation for Basic Research, grant 95-01-00369.