Capacity threshold for the Ising perceptron

Abstract

We show that the capacity of the Ising perceptron is with high probability upper bounded by the constant $\hat{I}{\pm }_{\star }\approx 0.833$ conjectured by Krauth and Mézard, under the condition that an explicit two-variable function ${\mathcal{S}}_{\ast }(\hat{I}{»}_1,\hat{I}{»}_2)$ is maximized at $(1,0)$. The earlier work of Ding and Sun proves the matching lower bound subject to a similar numerical condition, and together these results give a conditional proof of the conjecture of Krauth and Mézard.

76 pages, 2 figures. This version includes rigorous interval arithmetic verification of the numerical estimates in Appendix B, carried out in the attached Python file. This proves all numerical conditions in the paper (for kappa=0) except the main Condition 1.3. We slightly reformulate Condition 3.4 to simplify the numerical verification