Ising perceptron capacity threshold

Description of constant

Let $G = (g_{ij})$ be an $M \times N$ random matrix with independent standard Gaussian entries, and let \(Z(G) := \left| \left\{ \sigma \in \{-1,1\}^N : G \sigma \geq 0 \text{ coordinatewise} \right\} \right|.\) This is the zero-margin binary (or Ising) perceptron. Write $M = \lfloor \alpha N \rfloor$.

Define $C_{80}$ to be the infimum of all $\alpha > 0$ such that \(\mathbb{P}(Z(G) > 0) \to 0 \qquad \text{as } N \to \infty.\) Equivalently, $C_{80}$ is the asymptotic storage-capacity / satisfiability threshold of the zero-margin Ising perceptron. Sharp-threshold results [X2021], [NS2023] show that this formulation captures the threshold location up to $o(1)$.

Known upper bounds

Bound Reference Comments
$<1$ [KR1998] Kim–Roche prove that the capacity is bounded away from $1$ with high probability.
$0.9963$ [KR1998] Explicit combinatorial upper bound.
$<1$ [T1999] Independent non-explicit upper bound of the form $1-\varepsilon$ for some $\varepsilon>0$.
$0.847$ [AT2024] Complete proof of the upper bound outlined earlier by Krauth–Mézard.
$\alpha_{\star} \approx 0.833$ [H2024] Conditional on an explicit numerical maximization hypothesis for a two-variable function $\mathscr{S}_{\star}(\lambda_1,\lambda_2)$.

Known lower bounds

Bound Reference Comments
$0$ Trivial  
$>0$ [KR1998] Shows the capacity is bounded away from zero with high probability.
$\alpha_{\star} \approx 0.833$ [DS2025], [NS2023] Conditional on an explicit numerical maximization hypothesis for a one-variable function $\mathscr{S}{\star}(\lambda)$; Ding–Sun prove the lower bound with positive probability, and the sharp-threshold theory of Nakajima–Sun upgrades this to with high probability for every $\alpha < \alpha{\star}$.

Additional comments

References

Contribution notes

Prepared with assistance from GPT5.4 Pro for a more in-depth literature search.