Boolean threshold functions, neuron capacity, and memory retrieval

How much information can a single neuron remember? How many memories can neural networks retrieve without creating false memories? These questions are related to a basic question: how many Boolean threshold functions $f(x)=\mathrm{sgn}(a_0+⟨a,x⟩)$, $x\in \{-1,1{\}}^n$, are there? In this paper, we show that the number $T_n$ of distinct Boolean threshold functions is \[ T_n=2\binom{2^n-1}{n}\bigl(1+O(n^{-99})\bigr). \] Equivalently, the capacity of a single threshold neuron is $n^2-{\log }_2(n!)+1+O(n^{-99})$ bits, improving the $O(n)$ error term in the result of Kahn--Koml\'os--Szemer\'edi to $O(n^{-99})$. To prove this, we show that, for $1\le r\le n-1$, and $v_1,\dots ,v_r$ are chosen at random from $\{-1,1{\}}^n$, \[ \mathbb P\!\left\{ \langle v_1,\ldots,v_r\rangle\cap\{-1,1\}^n =\{\pm v_1,\ldots,\pm v_r\} \right\} =1-O(n^{-99}). \] In the context of the Kanter--Sompolinsky Hamiltonian for memory retrieval, this identifies $r=n-1$ as a sharp threshold, at which, for almost every collection of $r$ memories, the only ground states are these memories and their negatives, confirming a weaker form of the Kalai--Linial--Odlyzko conjecture. It also settles a recent open problem posed by M. Anthony on the specification number of Boolean threshold functions. In addition, we show that, for every $1\le r\le n-1$, \[ \mathbb P\{v_1,\ldots,v_r are linearly dependent\} =2\binom r2 2^{-n}+O\!\left(2^{-n}e^{-cn}\right), \] confirming a conjecture of Kahn--Koml\'os--Szemer\'edi.