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)=operatornamesgn(a0+langle a,xrangle), x∈-1,1n, are there? In this paper, we show that the number Tn of distinct Boolean threshold functions is [ Tn=2binom2n-1nbigl(1+O(n-99)bigr). ] Equivalently, the capacity of a single threshold neuron is n2-log2(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≤ r≤ n-1, and v1,ldots,vr are chosen at random from -1,1n, [ mathbb P!left langle v1,ldots,vrranglecap-1,1n =± v1,ldots,± vr 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≤ r≤ n-1, [ mathbb Pv1,ldots,vr are linearly dependent =2binom r2,2-n+O!left(2-ne-cnright), ] confirming a conjecture of Kahn--Koml'os--Szemer'edi.