Singularity of $\{\pm 1\}$-matrices and asymptotics of the number of threshold functions

Abstract

Two results concerning the number of threshold functions $P(2,n)$ and the probability ${\mathbb{P}}_n$ that a random $n\times n$ Bernoulli matrix is singular are established. We introduce a supermodular function ${\eta }_n^{★}:2_{fin}^{{\mathbf{RP}}^n}\to {\mathbb{Z}}_{\ge 0},$ defined on finite subsets of ${\mathbf{RP}}^n,$ that allows us to obtain a lower bound for $P(2,n)$ in terms of ${\mathbb{P}}_{n+1}.$ This, together with L.Schläfli's famous upper bound, give us asymptotics $$P(2,n)\sim 2\left(\genfrac{}{}{0ex}{}{2^n-1}{n}\right),n\to \infty .$$ Also, the validity of the long-standing conjecture concerning ${\mathbb{P}}_n$ is proved: $${\mathbb{P}}_n\sim (n-1{)}^2{2}^{1-n},n\to \infty .$$

arXiv comment41 pages. v.3