ShunyaBar: Spectral–Arithmetic Phase Transitions for Combinatorial Optimization
Sethurathienam Iyer · Zenodo (CERN European Organization for Nuclear Research) · 2025
ShunyaBar: Differentiable Combinatorial Optimization using Arithmetic Symmetry Breaking ShunyaBar is a dynamical optimization framework grounded in non-commutative geometry and quantum statistical mechanics. The system is formalized as a spectral triple $(\mathcal{A}, \mathcal{H}, \mathcal{D})$ encoding the arithmetic and geometric structure of the SAT phase space. The associated partition function factorizes over the adèlic ring $\mathbb{A}_{\mathbb{Q}}$ as: $$Z(\beta) = \zeta(\beta) \cdot \text{Tr}(e^{-\beta L})$$ where $\zeta(\beta)$ is the Riemann zeta function and $L$ is the constraint graph Laplacian. Core Mechanism We prove that the corresponding Kubo–Martin–Schwinger (KMS) states undergo a phase transition at inverse temperature $\beta_c = 1$, exhibiting full one-step Replica Symmetry Breaking (1-RSB). Applied to combinatorial optimization—such as random 3-SAT near the critical density $\alpha \approx 4.26$—a quasi-static Renormalization Group (RG) sweep across $\beta_c = 1$ produces dramatic speedups. These are bounded only by the Quantum Adiabatic Theorem, rather than by exponential search. Method Summary ShunyaBar does not perform combinatorial search. Instead, it: Continuously relaxes Boolean constraints into a global dynamical system. Destroys illegal regions of state space by making them energetically unstable. Forces a phase transition via an arithmetic singularity at $\beta = 1$. Freezes into a discrete Boolean assignment once full satisfaction is achieved. Terminates immediately upon reaching 100% satisfaction (no repair phase). This approach replaces backtracking and clause learning with global consistency enforcement. Blog Post: https://theory.shunyabar.foo/ Live API: https://navokoj.shunyabar.foo/ Performance & Industrial Benchmarks SAT 2024 Industrial Track Navokoj (the implementation of ShunyaBar) achieved a 92.57% perfect solution rate on the SAT 2024 industrial benchmarks (4,199 problems), tested across three engines: Engine Perfect Rate Speed Quality Use Case PRO 92.57% 7.9/sec 99.92% Mission-critical MINI 31.37% 10.6/sec 99.55% Balanced NANO 3.24% 12/sec 96.41% Real-time Case Study 1: 129-SAT (Ultra-High-k Regime) Problem: $N=200, M=10^6$, Alpha $\approx 5000$ (1000x over-constrained). Challenge: Locality is destroyed; CDCL search is ineffective as clause learning loses meaning. Result: 100% satisfaction (0/1M violated) in ~9–10 minutes on a single H100 GPU. Case Study 2: Ramsey R(5,5,5) at N = 52 Problem: Construct a 3-edge-coloring of $K_{52}$ with no monochromatic $K_5$ subgraphs. Search space: $3^{1326} \approx 10^{633}$. Result: Perfect 3-coloring found in ~17 minutes. This constitutes a constructive lower bound for $R(5,5,5)$. Comparison: ShunyaBar vs. NVIDIA TurboSAT Aspect NVIDIA TurboSAT ShunyaBar Core approach Gradient-guided search + CDCL Pure continuous dynamics Uses CDCL Yes (CPU side) No Repair phase Required None Handles High-k Not targeted Native Proof output CDCL certificates Boolean witness + verifier While TurboSAT offloads exploration to GPUs to accelerate classical SAT, ShunyaBar eliminates search entirely, operating in regimes where CDCL ceases to be meaningful. Verification & Reproducibility Instance Type Size Satisfaction Rate Status 129sat_n200 129-SAT $N=200, M=10^6$ 100.00% Verified pyth_n5000 Pythagorean $N=5000$ 100.00% Verified ramsey_n52 Ramsey $K_{52}, R(5,5,5)$ 100.00% Verified 3sat_100k 3-SAT $N=23k$ 94.90% Partial To verify these results independently: python3 verify_reproducibility.py This script scans the results/ directory, regenerates instances using deterministic generators, and verifies all assignments. ShunyaBar replaces combinatorial search with arithmetic-spectral phase transitions, enforcing global consistency to produce verifiable witnesses in regimes where classical solvers fail.