Abstract:
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.