RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1993 Volume 5, Issue 3, Pages 40–43 (Mi dm689)

This article is cited in 4 papers

On the number of threshold functions

A. A. Irmatov


Abstract: A Boolean function is called a threshold function if its truth domain is a part of the $n$-cube cut off by some hyperplane. The number of threshold functions of $n$ variables $P(2,n)$ was estimated in [1, 2, 3]. Obtaining the lower bounds is a problem of special difficulty. Using a result of [4], Yu. A. Zuev showed [3] that for sufficiently large $n$
$$ P(2,n)>2^{n^2(1-10/\ln n)}. $$
In the present paper a new proof which gives a more precise lower bound of $P(2,n)$ is proposed, namely, it is proved that for sufficiently large $n$
$$ P(2,n)>2^{n^2(1-7/\ln n)}P\biggl(2,\biggl[\frac{7(n-1)\ln 2}{\ln(n-1)}\biggr]\biggr). $$


Received: 02.07.1992


 English version:
Discrete Mathematics and Applications, 1993, 3:4, 429–432

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025