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

Abstract

Let $E=\{(1,b_1,\dots ,b_n)\in R^{n+1}\mid b_i=\pm 1,i=1,\dots ,n\}$, $E_{\ne 0}^{\times n}:=\{W=(w_{i_1},\dots ,w_{i_n})\mid w_{i_k}\in E,k=1,\dots ,n,dimspan(w_{i_1},\dots ,w_{i_n})=n\},$ and $q_l^W:=|span(w_{i_{n-l+1}},\dots ,w_{i_n})\cap E|.$ Then for any weights $p=(p_1,\dots ,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)\ge 2\sum _{W\in E_{\ne 0}^{\times n}}\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},\dots ,w_{i_n})\cap E=\left\{w_{i_1},\dots ,w_{i_n},\dots w_{i_{q_n^W}}\right\}$.

arXiv comment11 pages