Boolean threshold functions, neuron capacity, and memory retrieval
Abstract
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)=sgn(a0+⟨ a,x⟩), x∈{−1,1}n, are there? In this paper, we show that the number Tn of distinct Boolean threshold functions is Tn=2binom2n−1n(1+O(n−99)). 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ós--Szemerédi to O(n−99). To prove this, we show that, for 1≤ r≤ n−1, and v1,…,vr are chosen at random from {−1,1}n, ℙ { ⟨ v1,…,vr⟩∩{−1,1}n ={± v1,…,± vr} } =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, ℙ{v1,…,vr are linearly dependent} =2binom r2 2−n+O (2−ne−cn), confirming a conjecture of Kahn--Komlós--Szemerédi.
Related
- Linear Independence of Random Boolean Tensor Powers at the Dimension Threshold
- Almost every Boolean function has central threshold degree
- On the Fourier Entropy-Influence Conjecture for Boolean Plateaued Functions
- Subthreshold oscillations and spiking in hybrid neuron models with a dynamic threshold
- Tameness of transitive Boolean functions
BibTeX
@misc{xie2026boolean,
title = {{Boolean threshold functions, neuron capacity, and memory retrieval}},
author = {Xinyuan Xie},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29756},
eprint = {2609.29756},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29756},
}
RIS
TY - UNPB
TI - Boolean threshold functions, neuron capacity, and memory retrieval
AU - Xinyuan Xie
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.29756
UR - https://arxiv.org/abs/2609.29756
AB - 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)=sgn(a_0+⟨ a,x⟩), x∈{−1,1}^n, are there? In this paper, we show that the number T_n of distinct Boolean threshold functions is T_n=2binom2^n−1n(1+O(n^−99)). 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ós--Szemerédi to O(n^−99). To prove this, we show that, for 1≤ r≤ n−1, and v_1,…,v_r are chosen at random from {−1,1}^n, ℙ { ⟨ v_1,…,v_r⟩∩{−1,1}^n ={± v_1,…,± v_r} } =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, ℙ{v_1,…,v_r are linearly dependent} =2binom r2 2^−n+O (2^−ne^−cn), confirming a conjecture of Kahn--Komlós--Szemerédi.
ER -