A Lower Bound of the Number of Threshold Functions in Terms of Combinatorial Flags on the Boolean Cube

Anwar Irmatov

Published 2018-11-25Version 1

Let $ E=\{ (1, b_1, \ldots , b_n)\in R^{n+1} \mid \; b_i= \pm 1 ,\; i=1, \ldots, n \}$, $E^{\times n}_{\ne 0} := \{ W=(w_{i_1}, \ldots , w_{i_n}) \mid w_{i_k}\in E, \, k=1, \ldots, n, \, dim \, span(w_{i_1}, \ldots , w_{i_n}) = n \},$ and $q^W_l := |span(w_{i_{n-l+1}}, \ldots , w_{i_n}) \cap E|.$ Then for any weights $p=(p_1, \ldots, p_{2^n})$, $p_i\in R$, $\sum_{i=1}^{2^n}{p_i} =1$ we have for the number of threshold functions $P(2,n)$ the following lower bound $$P(2, n) \geq 2\sum_{W\in E^{\times n}_{\ne 0}}{\frac{1- p_{i_1} -p_{i_2} - \cdots - p_{i_{q_n^W}}}{q_n^W\cdot q_{n-1}^W\cdots q_1^W}},$$ and the right side of the inequality doesn't depend on the choice of $p$. Here the indices used in the numerator correspond to vectors from $span(w_{i_1}, \ldots , w_{i_n})\cap E = \left\{w_{i_1}, \ldots, w_{i_n}, \ldots w_{i_{q_n^W}}\right\}$.