1. Introduction

This document presents a formal mathematical framework in which constraint satisfaction, prime number distribution, and the Chebyshev error competition share a common mathematical structure under the assumptions stated herein. A SAT solver becomes a gradient flow on a Riemannian manifold. Clause weights become prime masses on the boundary. The stability of the solver at scale becomes a physical instantiation of the tradeoff between geometric spectral decay and the asymptotic distribution of primes.

NitroSAT is a physics-informed MaxSAT solver written in ~2,500 lines of LuaJIT combining Riemann zeta arithmetic, heat kernel diffusion, persistent homology, and Lambert-W branch annealing.

1.1 Background: From Casimir-SAT to NitroSAT

NitroSAT builds upon the theoretical foundations introduced in Casimir-SAT (Iyer, October 2025), which recast Boolean satisfiability as a continuous dynamical system inspired by quantum vacuum physics. Casimir-SAT established several core principles that carry forward into the present work.

The central insight of Casimir-SAT was to treat partial variable assignments not as discrete search states but as physical microstates in an energy landscape. Variables were relaxed from $\{0,1\}$ to the continuous interval $[0,1]$, with each clause contributing a differentiable penalty via the fractional satisfaction function $s_c(x) = 1 - \prod_{\ell \in c}(1 - x_\ell)$. The global energy functional $E(x) = \sum_c (1 - s_c(x))^2$ defined a smooth landscape whose global minima corresponded to satisfying assignments.

Three architectural ideas from Casimir-SAT proved foundational:

1. Langevin dynamics on the constraint manifold. Rather than backtracking through a discrete search tree, Casimir-SAT evolved the system via stochastic differential equations combining gradient descent with thermal fluctuations: $dx_i = -\eta \nabla_i E \, dt + \sqrt{2T} \, dW_i$. Temperature-controlled annealing provided a principled exploration-exploitation tradeoff with asymptotic convergence guarantees.
2. Spectral cluster detection. The Fiedler vector of a weighted constraint Laplacian was used to automatically partition variables into frozen clusters (low energy, internally consistent) and active domain walls (high gradient, still evolving). This eliminated the need for branching heuristics.
3. Free energy minimization. The dynamics were interpreted as minimizing a thermodynamic free energy $F = E - TS$, where $S = -\sum_i [x_i \ln x_i + (1-x_i)\ln(1-x_i)]$ is the Bernoulli entropy. This unified constraint satisfaction with statistical mechanical principles and provided a natural regularization against premature variable collapse.

Casimir-SAT demonstrated 2–6× speedups over MiniSat and Glucose on random 3-SAT below the clustering threshold ($\alpha < 3.86$), but scaling was limited to ~100 variables. Industrial instances favored CDCL solvers due to their superior clause learning capabilities.

Casimir-SAT validated the physics-inspired paradigm at small scale: random 3-SAT instances below the clustering threshold ($\alpha < 3.86$) converged in polynomial time, with the Fiedler spectral gap providing automatic hardness detection. However, the architecture faced three limitations that motivated the development of NitroSAT:

1. Scale. The $O(n^3 \log n)$ spectral analysis dominated runtime, restricting practical application to instances under ~100 variables.
2. Uniform clause weighting. All clauses contributed equally to the energy functional, providing no mechanism to break spectral resonances or prevent gradient concentration in specific eigenmodes.
3. Flat geometry. The dynamics operated on the Euclidean unit hypercube $[0,1]^n$ with no curvature-dependent regularization, allowing variables to collapse prematurely to Boolean extremes.

NitroSAT addresses each of these limitations through three corresponding innovations: (1) a degree-local heat kernel approximation replacing explicit Laplacian eigendecomposition, reducing per-iteration cost to $O(M)$; (2) prime-indexed clause weights $W(p_c) = 1/(1 + \ln p_c)$ that provide implicit spectral preconditioning via multiplicative independence (Theorem 3); and (3) an inverted Poincaré disk metric that creates an infinitely deep geometric uncertainty well at $x = 0.5$, quadratically suppressing premature collapse (Theorem 1). The free energy framework, Langevin dynamics, and spectral detection from Casimir-SAT are retained but reformulated on the Riemannian manifold with the additional machinery of persistent homology ($\beta_0, \beta_1$ tracking) and Lambert-W branch annealing (BAHA) for escaping metastable minima.

The result is a solver that scales from Casimir-SAT's ~100-variable ceiling to 788,000 variables and 80 million clauses while preserving the core physical intuition: computation as thermodynamic relaxation on a constraint manifold.

2. Geometric Foundations

2.1 The Inverted Poincaré Disk ($\mathbb{D}^*$)

The space begins with the standard open unit disk, $\mathbb{D} = \{z \in \mathbb{C} : |z| < 1\}$. An inverted metric $g^*$ is defined on $\mathbb{D} \setminus \{0\}$ using the conformal inversion $z \mapsto 1/z$.

The resulting metric tensor is:

$$ds^2 = \frac{4|dz|^2}{|z|^2(1-|z|^2)^2}$$

The geodesic distance from a point at radius $R \in (0, 1)$ to the boundary ($|z| \to 1$) and to the origin ($|z| \to 0$) is:

$$d^*(0, R) = \int_R^1 \frac{2}{r(1-r^2)}dr = \ln\!\left(\frac{1-R^2}{R^2}\right)$$ Evaluating the limits: as $R \to 0$, $d^* \to \infty$, and as $R \to 1$, $d^* \to 0$. The origin of the disk is infinitely far from everything—a geometric manifestation of maximum uncertainty.

2.2 The Prime Necklace (Boundary Conditions)

A discrete distribution of the first $K$ primes, denoted $\mathbb{P}_K = \{p_1, p_2, \dots, p_K\}$, is placed on the boundary $\partial \mathbb{D}^*$ where $|z|=1$.

Each prime is assigned a logarithmically smoothed weight function:

$$W(p_i) = \frac{1}{1 + \ln(p_i)}$$

Using the Prime Number Theorem ($p_K \sim K \ln K$), the total asymptotic mass of the system as $K \to \infty$ is:

$$\mathcal{M}_K = \sum_{i=1}^K \frac{1}{1+\ln(p_i)} \sim \int_2^{p_K} \frac{dx}{(1+\ln x)\ln x} \sim K$$ Small primes (low-order UNSAT atoms) exert strong force; large primes (high-order atoms) exert weaker, more diffuse force. The total mass grows linearly.

2.3 The Prime Equipartitioning Problem

The goal is to partition the set of primes $\mathbb{P}_K$ into $L$ disjoint clusters $\mathcal{C} = \{C_1, C_2, \dots, C_L\}$. The objective is for the mass of each subset, $M(C_j) = \sum_{p \in C_j} W(p)$, to approach the mean mass $\mu = \mathcal{M}_K / L$.

This is formulated as minimizing the partitioning variance $\Delta$:

$$\Delta = \sum_{j=1}^L \left( M(C_j) - \frac{\mathcal{M}_K}{L} \right)^2$$

2.4 The Riemann Connection and Spectral Stability

The stability of minimizing $\Delta \to 0$ without divergence relies on the distribution of primes in arithmetic progressions. This connects to von Mangoldt's explicit formula for $\psi(x) = \sum_{p^k \le x} \ln p$:

$$\psi(x) = x - \sum_{\rho} \frac{x^\rho}{\rho} - \ln(2\pi) - \frac{1}{2}\ln(1-x^{-2})$$

To ensure equipartitioning is asymptotically stable, the relative error term $E(x)/x = (\psi(x) - x)/x$ must not dominate the system's structural relaxation time.

• If the Riemann Hypothesis holds: All non-trivial zeros lie on the critical line $\text{Re}(\rho) = 1/2$. The relative error decays as $O(K^{-1/2} \ln^2 K)$. The prime fluctuation perturbation vanishes rapidly at scale.
• If the Riemann Hypothesis is false: There would exist a zero with $\text{Re}(\rho) = \sigma > 1/2$. The relative error decays much slower, as $O(K^{\sigma-1})$.

The Bombieri–Vinogradov Anchor

By the Bombieri–Vinogradov Theorem, primes are equidistributed in arithmetic progressions of modulus $q \le x^{1/2}/\log^B x$ on average. For cluster partitions corresponding to moduli $L$ in this regime, the equipartitioning variance satisfies:

$$\Delta = O\!\left(\frac{L K}{\log^{2A} K}\right)$$

unconditionally. This establishes square-root–scale decay of the relative fluctuation term ($\Phi(K) \sim K^{-1/2}$) in the averaged sense, independent of the full Riemann Hypothesis.

The Bombieri–Vinogradov theorem is often called "RH on average"—it provides the statistical guarantee without requiring the full conjecture.

Addendum: Cluster Variance via Large Sieve

Critique Addressed: Generalizing from Arithmetic Progressions to Spectral Clusters.

The Bombieri–Vinogradov theorem strictly bounds variance over arithmetic progressions. However, NitroSAT clusters $\mathcal{C}_j$ are defined by spectral connectivity, not residue classes. To rigorously generalize, we invoke the Montgomery–Vaughan Large Sieve Inequality.

Define the prime weight fluctuation as $a_n := W(p_n) - \bar{W}$. Let cluster membership be encoded by indicator functions $f_j(n) = \mathbb{1}[n \in C_j]$. The variance is the energy projection:

$$\Delta = \sum_{j=1}^L \left| \sum_{n \le K} a_n f_j(n) \right|^2$$

The Large Sieve provides a worst-case bound that is too weak ($\Delta \sim O(K^2)$). Instead, we invoke the Barban–Davenport–Halberstam (BDH) Theorem for the sharp average-case variance. To apply BDH to spectral clusters, we introduce the following assumption:

Under this condition, for $L \le K / \log^B K$, BDH guarantees:

$$\Delta \ll L K \log K$$

The relative fluctuation per cluster scales as:

$$\frac{\sqrt{\Delta/L}}{K/L} \sim L K^{-1/2} \log^{1/2} K$$

For sub-linear cluster scaling ($L \sim \sqrt{K}$), this yields $\Phi(K) \sim K^{-1/4} \log^{1/2} K$; for constant $L$, we recover pure $K^{-1/2}$ scaling.

Empirical note: Fourier analysis of the graph Laplacian eigenvectors on benchmark instances reveals significant energy concentration in the lowest 10% of frequencies, remaining consistent with the Spectral Genericity assumption.

The Spectral Competition Tradeoff

The stability of the gradient flow is determined by a scaling competition between two opposing forces as $K \to \infty$:

1. Geometric Weakening: The rate at which the graph's spectral gap closes, $\lambda_2(G_K) \sim K^{-\gamma}$.
2. Prime Fluctuation Decay: The rate at which relative prime variance vanishes, $\Phi(K) \sim K^{\sigma-1}$.

Under the linear perturbation coupling ansatz, stability requires the asymptotic exponent condition:

$$1 - \sigma > \gamma$$

3. Riemannian Optimization Framework

3.1 Supporting Theorems

The following classical results form the tools needed to rigorously formalize the framework:

• The Selberg Trace Formula provides a geometric–spectral dictionary equating lengths of closed geodesics (primes) to Laplacian eigenvalues (zeros of zeta).
• Montgomery's Pair Correlation Theorem demonstrates that microscopic rigidity of zeros controls variance behavior, matching GUE statistics.
• The Bombieri–Vinogradov Theorem ensures primes are evenly distributed in arithmetic progressions up to $\sqrt{x}$, providing average equipartition stability.

3.2 The Manifold and the Laplace–Beltrami Operator

Let the geometric arena be $\mathbb{D}^*$ with the conformal metric $g_{ij}^* = \frac{4}{|z|^2(1-|z|^2)^2} \delta_{ij}$. Let the continuous state be a scalar field $x: \mathbb{D}^* \times \mathbb{R}^+ \to [0,1]$, representing the pre-measurement variable assignment.

The kinetic energy of the field is the Dirichlet energy on the manifold:

$$E_{\text{kin}}[x] = \frac{1}{2} \int_{\mathbb{D}^*} |\nabla_{g^*} x|^2 \, d\mu_{g^*}$$ Minimizing the Dirichlet energy yields the Laplace–Beltrami operator $\Delta_{g^*}$, which on a discrete constraint graph manifests as the graph Laplacian $L=D-A$.

3.3 The Boundary Potential (Contradiction Landscape)

The logical constraints (clauses) are projected as a potential field $V(x)$ on $\partial \mathbb{D}^*$. For $m$ clauses, let $p_c$ be the $c$-th prime. The weight of each clause is $W(p_c) = \frac{1}{1 + \ln p_c}$.

Let $L_i(x_i)$ be the continuous literal valuation. The penalty for unsatisfied constraints is modeled via a smooth log-barrier potential with a $10^{-6}$ stabilizer:

$$E_{\text{pot}}[x] = - \sum_{c=1}^m W(p_c) \ln\!\left(10^{-6} + 1 - \prod_{i \in c} L_i(x_i)\right)$$

3.4 Thermodynamic Free Energy

To maintain thermodynamic bounds, we introduce an entropy regularization term $S[x]$. Variables are clamped to $[10^{-9}, 1 - 10^{-9}]$:

$$S[x] = - \sum_i \left( x_i \ln x_i + (1 - x_i) \ln(1 - x_i) \right)$$

The total Free Energy $\mathcal{F}[x]$ at inverse temperature $\beta$ is:

$$\mathcal{F}[x] = \lambda E_{\text{kin}}[x] + E_{\text{pot}}[x] - \frac{1}{\beta} S[x]$$

3.5 The Gradient Flow (Langevin Dynamics)

The system evolves by gradient descent on the Free Energy functional:

$$\frac{\partial x}{\partial t} = - \frac{\delta \mathcal{F}}{\delta x}$$

Computing the variational derivative for each variable $x_v$ yields three terms:

Kinetic Derivative (Heat Diffusion):

$$- \frac{\delta E_{\text{kin}}}{\delta x_v} = \Delta_{g^*} x_v$$

On the discrete graph, this acts as a smoothing multiplier proportional to vertex degree.

Potential Derivative (Barrier Force):

$$- \frac{\delta E_{\text{pot}}}{\delta x_v} = \sum_{c \ni v} W(p_c) \cdot \frac{\prod_{i \in c} L_i(x_i)}{10^{-6} + 1 - \prod_{i \in c} L_i(x_i)} \cdot \frac{\partial \ln L_v(x_v)}{\partial x_v}$$

Entropic Derivative:

$$\frac{1}{\beta} \frac{\delta S}{\delta x_v} = \frac{1}{\beta} \ln\!\left(\frac{1 - x_v}{x_v}\right)$$

4. Implementation

4.1 The Isomorphism to nitrosat.c

The discretized PDE perfectly matches the compute_gradients function in the solver:

• Potential Force: $\frac{\prod L_i}{10^{-6} + 1 - \prod L_i}$ is exactly the code's barrier * violation, multiplied by prime weight $W(p_c)$.
• Entropic Force: $\ln\!\left(\frac{1 - x_v}{x_v}\right)$ is computed as ns->entropy_weight * log((1.0 - v_clamped) / v_clamped).
• Kinetic Diffusion: The heat kernel $\exp(t \Delta_{g^*})$ is approximated via pre-calculated multipliers:

// Heat kernel approximation (nitrosat.c, Lines 714-718)
ns->heat_mult_buffer[i] = 1.0 + ns->heat_lambda * exp(-ns->heat_beta * ns->degrees[i]);

Code Verification: From Math to Implementation

The following table maps each mathematical claim directly to its implementation in nitrosat.c:

Mathematical Claim	Code Location	Status
Prime weights $W(p) = 1/(1+\ln p)$	Line 684	✓
Zeta weights $\log(p)/p$	Line 685	✓
Log-barrier gradient	Lines 760–771	✓
Entropy term $\ln((1-x)/x)$	Lines 778–779	✓
Heat kernel $1 + \lambda e^{-\beta \cdot \text{degree}}$	Lines 714–718	✓
Spectral init (power iteration on XOR-Laplacian)	Lines 603–655	✓
Fracture detection (variance-based)	Lines 204–235	✓
Lambert-W for branch jumps	Lines 237–282	✓
Betti numbers $\beta_0, \beta_1$	Lines 485–491	✓
Topological repair phase	Lines 1207–1278	✓

5. Theoretical Guarantees

5.1 Convexity Regime and Convergence

5.2 Lambert W Phase Transition

No other weighting produces this specific $\ln K / \ln\ln K$ scaling law. It is a direct signature of the Prime Number Theorem operating through the weight function.

5.3 Theorem 1: Quadratic Gradient Vanishing in Inverse Hyperbolic Space

5.4 Theorem 2: Analytic BAHA Teleportation Bound

5.5 Theorem 3: Implicit Spectral Preconditioning via Prime Variance

This is the crucial result: the system is implicitly preconditioned by the prime weights, bypassing the need for explicit Hessian inversion.

Spectral Genericity Lemma

Theorem 4: Implicit Spectral Preconditioning via Heat-Diffused Prime Forcing

Lyapunov Structure of the NitroSAT Dynamics

Consider the free energy functional $F(x) = E(x) - \frac{1}{\beta}S(x)$, where $S$ is the Bernoulli entropy. The solver evolves via Riemannian gradient flow:

$$\dot{x}_i = -x_i(1-x_i)\frac{\partial F}{\partial x_i}$$

This explains three key solver properties:

1. No runaway dynamics: $F(x(t)) \le F(x(0))$ bounds all trajectories.
2. Interior confinement: Entropy diverges near $x=0$ or $1$, keeping trajectories inside the probability simplex.
3. Convergence to stationary points: Dynamics approach critical points where $\nabla F(x)=0$.

The Lyapunov property explains smooth relaxation phases, while BAHA acts as a controlled perturbation to escape metastable minima where the Lyapunov descent can continue.

$O(M)$ Scaling from Gradient Structure

The derivative $\frac{\partial E}{\partial x_i} = \sum_{c \ni i} w_c \frac{\partial \phi_c}{\partial x_i}$ sums only over clauses containing variable $i$. Computing the full gradient costs $\sum_i \deg(i) = \sum_c k_c = O(M)$ since clause width $k_c$ is bounded. Heat diffusion and topological diagnostics also scale as $O(M)$. Thus each iteration costs $O(M)$, and since iteration count grows slowly, total runtime behaves as $O(M)$.

6. Empirical Verification

NitroSAT has been tested on 5,000+ CNF instances across structured, random, adversarial, and real-world problem families, achieving a 77% perfect SATISFIED rate and a 99.7% median satisfaction. All benchmarks were executed single-threaded on an AMD Ryzen 5 5600H @ 4.280 GHz with gcc -O3 -lm.

6.1 Headline Results

Problem	Variables	Clauses	Satisfaction	Time
Enterprise Timetabling (v2)	147,600	80,278,884	100%	73s
Grid Coloring (1000×1000)	4,000,000	14,992,000	100%	475s
512×512 Multiplier	788,480	2,617,349	100%	5.92s
Titan Ramsey $R(5,5)$ on $K_{40}$	780	1,316,016	99.995%	3,403s
Adversarial Pitfall Trap (1M+ cls)	2,950	1,047,620	100%	~400s
Planted Coloring (Lua, 105K vars)	105,000	232,043	100%	13.78s
Small-World Lattice (300×300)	360,000	1,354,800	100%	62.75s
Edwards-Anderson 3D (40×40×40)	64,000	188,666	99.47%	4.3s
Random 3-SAT ($\alpha$=4.26, n=1000)	1,000	4,260	99.65%	—

6.2 Key Experimental Findings

• Prime weight speedup: 3.4–4× faster on structured geometries; $\beta_1$ reduced 75% (79→20) vs. uniform weights.
• Permutation invariance: 20/20 random permutations yield identical solutions (std dev = 0.0000%).
• Glassy plateau recovery: Phases 2/3 (topological repair + adelic saturation) consistently rescue +2–4% satisfaction from stagnation.
• $O(M)$ scaling verified: Throughput stable across 40× variable increase (5K → 200K vars).
• CDCL traps ineffective: Pitfall formula (1M+ clauses) solved at 100%; no discrete branch commitment.
• Edwards-Anderson 3D: First gradient-based solver to crack EA 3D at scale (64K+ spins, >99%).
• Hardware verification: 16/16 circuits (adders + multipliers up to 512×512) at 100% satisfaction.
• Expander graphs: Stable ~90% from 2K to 100K vars — the known breaking point for diffusion-based approaches.

📊 Complete benchmark heritage (616 lines, 6 chronological phases, every table):
github.com/sethuiyer/NitroSAT/benchmarks/README.md
Includes: full hardware suite (16 circuits) · scheduling (28ms → 80M clauses) · CNFgen (44 instances) · LeetCode (14 problems) · protein folding · spin glass · Death Run · prime weight ablation · thermal sensitivity · engine parity · and more.

The variance of random 3-SAT results contracts with increasing instance size (std dev: 0.11% → 0.06%), indicating mean-field self-averaging behavior predicted by the Lyapunov structure. The constant 99.6% plateau across all $n$ is consistent with the replica-symmetric free energy of the random 3-SAT energy landscape (Section 7).

6.19 Quantitative Predictions

For random 3-SAT at $\alpha = 4.26$ with $k=3$, $d_{\text{clause}} \approx 12.78$, and $\delta = 0.3$, the critical inverse temperature satisfies:

$$\beta^* \sim \frac{4\delta^2 \ln K}{k^2 \cdot d_{\text{clause}} \cdot \ln\ln K}$$

$K$ (clauses)	$\ln K$	$\ln\ln K$	$\beta^*$ (theory)
10,000	9.21	2.22	0.0130
100,000	11.51	2.44	0.0147
1,000,000	13.82	2.63	0.0165

These are parameter-free predictions derived without fitting. The only inputs are $k=3$ and the prime weight formula $W(p) = 1/(1+\ln p)$. The $\ln K / \ln\ln K$ scaling is a direct fingerprint of the Prime Number Theorem acting through the weight function. Empirical verification of the predicted $\beta^*$ transition would constitute strong evidence for the causal role of prime weighting.

7. Spectral Coherence Analysis

Structured Instance Convergence

Every instance achieving 100% satisfaction shares a common property: algebraic or geometric regularity of the constraint hypergraph. Graph coloring, clique coloring, Ramsey numbers, scheduling, Latin squares, N-Queens, exact cover, planted 3-SAT, parity, and XOR-SAT all exhibit structured constraint graphs with large spectral gaps $\lambda_2$. From the convergence theorem:

$$\mu_{\text{eff}} = \frac{4}{\beta} - \frac{W_{\max} k_{\max}^2 d_{\text{clause}}}{\delta^2} + \lambda \cdot \lambda_2(L)$$

A larger $\lambda_2$ directly increases $\mu_{\text{eff}}$, giving faster exponential convergence.

Grid graph coloring: $\lambda_2 \sim 1/N$ but regular geometry enables global propagation in $O(N)$ steps. Clique coloring: dense local structure yields high $\lambda_2$. Ramsey constructions: delocalized Fourier-like eigenvectors make diffusion extremely efficient.

Entropic Symmetry Breaking

Notably, the hardest instances for CDCL solvers are often the most tractable for NitroSAT. Ramsey $R(5,5,5)$, clique coloring, and Latin squares present severe difficulties for CDCL because of massive symmetry—clause learning does not transfer across symmetry orbits.

The entropy term operates on all symmetric copies simultaneously. When $x_i = 0.5$ for all variables in a symmetry orbit, the entropy gradient drives them simultaneously toward the correct assignment. Symmetry breaks naturally as $\Pi_c$ values diverge between clauses.

The Random 3-SAT Plateau at 99.6%

Random 3-SAT at clause-to-variable ratio 4.26 exhibits an energy landscape in which satisfying assignments are clustered in exponentially many small clusters separated by large barriers (the overlap gap property). NitroSAT converges to 99.6% satisfaction because this corresponds to the free energy minimum in the replica-symmetric phase. The residual 0.4% gap represents the energy cost of the clustering barrier—critically, this gap is constant across $n$, indicating a thermodynamic limit rather than a finite-size effect.

XOR-SAT Tractability

Standard continuous relaxations fail on XOR-SAT because parity constraints produce flat gradient directions. Two mechanisms address this in NitroSAT. First, the entropic force $\ln((1-x)/x)$ creates a nonzero gradient from any infinitesimal perturbation, preventing the system from stalling at the flat point. Second, Laplacian diffusion propagates parity information along constraint chains, effectively implementing Gaussian elimination in continuous time. The persistent homology detector ($\beta_1 = 98$) identifies the cycle structure of the XOR constraint graph and uses it to guide the flow.

Limitation Regime

Tiling (99.1%), subset cardinality (95.7%), extreme numerical (95.69%), and Sudoku (99.92% but never exact) share a common characteristic: high-weight frustrated constraints with no algebraic regularity. In these instances, the spectral gap is small, the clause structure lacks exploitable symmetry, and barrier forces create rough landscapes with near-degenerate local minima.

8. Primes as Irreducible Constraint Atoms

Primes are the irreducible unsatisfiable cores of arithmetic. The connection to constraint satisfaction is structural, not merely analogical.

The Divisibility Constraint

Consider: "Given $n > 1$, find a non-trivial factorization $n = a \cdot b$ with $1 < a, b < n$." This is a constraint satisfaction problem. A composite number satisfies the constraint. A prime $p$ cannot—it is the UNSAT core of the factoring CSP.

By the Fundamental Theorem of Arithmetic, every integer has a unique factorization into primes. In SAT language: every satisfiable arithmetic instance decomposes uniquely into irreducible UNSAT atoms (primes). This correspondence is structural rather than categorical.

The Multiplicative Independence Guarantee

Primes are uniquely suited for constraint weighting because they are multiplicatively independent:

• No resonance cancellation: Differently-weighted clauses cannot produce destructive interference, as their weights share no common factors.
• Unique spectral identity: $\prod_{c \in S} p_c$ is unique for each subproblem, providing a distinct fingerprint in the Archimedean topology.
• Gauge invariance: Weights depend only on clause index, not on variable labeling, yielding 0.0000% permutation variance.

If primes cluster irregularly (a zero off the critical line), some clause groups would carry anomalously high or low mass, creating irrecoverable gradient imbalances.

The Riemann Hypothesis asserts these obstructions are distributed as regularly as possible, with fluctuations bounded by $O(\sqrt{x})$. NitroSAT's prime weighting embeds this regularity directly into the gradient flow.

9. NitroSAT as a Physical Instrument

The preceding sections establish a chain of dynamical relationships: Section 2.4 defines the stability boundary ($1 - \sigma > \gamma$); Section 5 proves strong convexity; Section 6 confirms empirical behavior matches predictions.

Key empirical consistencies:

• Variance shrinks with scale: Random 3-SAT std. dev. drops from 0.11% ($n=300$) to 0.06% ($n=1000$).
• $O(N)$ scaling holds to $10^6$ clauses: Grid coloring at $N = 1000 \times 1000$ (14.99M clauses) solves at 100%.
• Structured instances at 100%: Clique, Parity, and Ramsey instances converge to full satisfaction, consistent with robust spectral protection.

NitroSAT functions as a tunable physical instrument. By deliberately solving problems on topological meshes where the spectral gap decays rapidly ($\gamma \to 1/2$), and artificially suppressing diffusion and entropy constants, the solver can be pushed into the critical asymptotic regime.

Statement (The Chebyshev Scaling Experiment): NitroSAT embeds a Chebyshev-weighted perturbation into a gradient flow. Systematic scaling tests that suppress geometric stabilizers while driving structural decay ($\gamma$) offer an empirical framework to probe the threshold condition $1 - \sigma = \gamma$, translating algorithmic stability directly into bounds on the prime aggregation error.

9.1 Note: Asymptotic Stability of Prime-Weighted Constraint Flows and the Chebyshev Error Bound

This note formalizes the behavior of the NitroSAT dynamical system in the limit $M \to \infty$, where $M$ is the clause count. The purpose is to state precisely what is proved, what is proved conditionally, and what remains conjectural, in the language of analytic number theory rather than solver engineering.

Setup

Consider a family of constraint graphs $\{G_K\}_{K=1}^{\infty}$ indexed by clause count $K$, with $n_K$ variables and $K$ clauses. Each clause $c$ receives a prime-indexed weight $w_c = 1/(1 + \ln p_c)$, where $p_c$ is the $c$-th prime. The solver evolves according to the free energy gradient flow $\dot{x} = -g^{-1}(x)\nabla F(x)$ on the inverted Poincaré disk $\mathbb{D}^*$ (Section 3).

Two exponents govern the asymptotic behavior:

• Spectral decay exponent $\gamma$: The algebraic connectivity of $G_K$ satisfies $\lambda_2(G_K) \sim K^{-\gamma}$ for some $\gamma \in [0, 1]$ determined by the graph family.
• Prime fluctuation exponent $\sigma$: The relative error in the prime-weighted cluster variance decays as $\Phi(K) \sim K^{\sigma - 1}$, where $\sigma$ is the supremum of the real parts of the non-trivial zeros of $\zeta(s)$.

Unconditional Results

This is a direct application of the Bombieri–Vinogradov theorem (Section 2.4). It guarantees that on average, the prime weights distribute evenly across spectral clusters at square-root scale, independent of the Riemann Hypothesis.

The Exponent Competition

As $K \to \infty$, two forces compete. The spectral gap $\lambda_2(G_K) \sim K^{-\gamma}$ weakens the structural rigidity of the gradient flow, reducing the convergence rate $\mu$. Simultaneously, the prime-weighted cluster variance decays as $\Phi(K) \sim K^{\sigma - 1}$, determining whether the perturbation from non-uniform prime distribution overwhelms the residual curvature.

Under a linear perturbation coupling ansatz (where the prime fluctuation enters the convexity bound as an additive perturbation to the effective Hessian), the convergence rate remains positive if and only if:

$$1 - \sigma > \gamma$$ This inequality is the central structural claim. It is proved under the linear coupling ansatz. The question of whether nonlinear damping, entropy barriers, or higher-order spectral corrections shift the threshold remains open.

This inequality partitions the $(\sigma, \gamma)$ plane into a stable region (solver converges exponentially) and an unstable region (prime fluctuations dominate, solver destabilizes at finite $K$).

Conditional Results

The Asymptotic Lock Conjecture

Three gaps separate this conjecture from a theorem:

1. Graph construction. It is not established that the required spectral decay rate $\gamma \to 1/2$ is achievable by an explicit, efficiently constructible graph family that simultaneously satisfies the Spectral Genericity assumption (Section 5). Candidate families include Ramanujan graph perturbations and random regular graphs, but neither has been verified to satisfy all required conditions simultaneously.
2. Coupling ansatz. The stability threshold $1 - \sigma > \gamma$ is derived under a linear perturbation model. The actual dynamics include entropy barriers (which diverge at $x = 0$ and $x = 1$) and nonlinear damping from the log-barrier potential. These may provide additional stabilization not captured by the linear analysis, potentially weakening the required condition on $\sigma$.
3. Finite-size separation. At empirically accessible scales ($K \le 10^7$), the classical zero-free region of $\zeta(s)$ already guarantees $\sigma_{\text{eff}} < 1/2 + \epsilon$ for any detectable $\epsilon$. The geometric stabilizers (heat diffusion, entropy) are strong at these scales. Asymptotic distinguishing requires $K$ far beyond current computational reach.

What Is and Is Not Claimed

Statement	Status
Free energy is Lyapunov; gradient flow is monotone	Proved (Section 5)
Interior strong convexity at finite $K$	Proved (Theorem 5.1)
$\kappa_{\text{eff}} = O(1)$ under Spectral Genericity	Proved (Theorem 4)
Prime variance bounded at $K^{-1/2}$ on average (BV)	Proved unconditionally
Stability threshold $1 - \sigma > \gamma$ under linear coupling	Proved (Section 2.4)
RH $\Rightarrow$ stability for all $\gamma < 1/2$	Proved (conditional on RH)
$\neg$RH $\Rightarrow$ finite-$K$ destabilization for $\gamma > 1-\sigma$	Proved (conditional on $\neg$RH)
Existence of graph family achieving $\gamma \to 1/2$ with genericity	Conjecture
Nonlinear corrections do not shift the threshold	Open
Empirical benchmarks at $K \le 10^7$ probe RH	No — stabilizers dominate

The honest summary: the framework establishes that if the right graph family exists and if the linear coupling ansatz captures the dominant behavior, then asymptotic solver stability is equivalent to RH. Both conditions remain open.

The framework does not compute or verify the Riemann Hypothesis. It establishes a conditional equivalence: under the Asymptotic Lock conjecture, the long-run stability of prime-weighted constraint flows on critical-dimension graphs is governed by the same exponent that controls the distribution of prime numbers. The solver functions as a physical system whose asymptotic phase boundary coincides with the critical line $\text{Re}(s) = 1/2$, providing a thermodynamic interpretation of the Chebyshev error bound rather than a computational proof.

10. Academic Citations

11. Proved vs Conjectured Summary

Claim	Status
Free energy gradient flow derivation	✓ Proved
Correspondence to compute_gradients	✓ Proved (structural)
Interior strong convexity theorem	✓ Proved
Convergence rate via spectral gap	✓ Proved
Stability requires $1-\sigma > \gamma$	✓ Proved
Limit $\gamma \to 1/2$ forces $\sigma \to 1/2$	Conjecture (Asymptotic Lock)
Heat multiplier = Laplace–Beltrami discretization	✓ Proved for lattice graphs
Empirical scaling bounds $\sigma$	Measurable via suppressed stabilizers
Theorem 1: Quadratic gradient vanishing	✓ Proved
Theorem 2: BAHA Lambert-W bound	✓ Proved
Theorem 3: Implicit spectral preconditioning	✓ Proved
Spectral Genericity Lemma	✓ Proved (with assumptions)
Theorem 4: $\kappa_{\text{eff}} = O(1)$	✓ Proved
Lyapunov structure	✓ Proved
$O(M)$ scaling from gradient locality	✓ Proved

12. Prime Weight Ablation Summary

The complete ablation study (Section 6.15) compares prime-indexed clause weights against uniform weights across structured, random, and parity instances. The key findings are:

1. Topological pruning: On structured instances (clique_4_20), prime weights reduce the first Betti number $\beta_1$ by 75% (79 → 20) and the convergence step count by 75% (381 → 94).
2. Speed improvement: Prime weights yield 3.4–4× wall-clock speedups on both structured and random geometries.
3. Topology complexity trend: The uniform weight configuration exhibits a positive complexity trend (0.78), indicating accumulation of spurious constraint cycles. The prime weight configuration maintains a flat trend (0.0).

These results support Theorem 3's claim that multiplicatively independent prime weights prevent spectral resonance, yielding implicit preconditioning of the constraint landscape.

13. Conclusion

The $\beta_1$ ablation establishes that prime weights are causally significant—they directly alter the topology of the constraint manifold. By assigning each clause a unique prime-based mass, the gradient flow encounters fewer spectral collisions, yielding:

1. Topological Pruning: 75% reduction in detected constraint cycles ($\beta_1$: 79→20).
2. Accelerated Convergence: 4× speedup on structured problems.
3. Geometric Stabilization: The solver remains in the convex regime over a larger portion of the optimization trajectory.

NitroSAT does not constitute a proof of the Riemann Hypothesis. Rather, it provides a thermodynamic engine in which the asymptotic distribution of primes explicitly determines the boundary conditions of algorithmic stability. By tuning the geometry of the constraint graph to close the spectral gap at a controlled rate, the framework establishes a formal mathematical competition: stability is maintained only if the prime aggregation error decays faster than the graph's structural rigidity.

Solver Performance Summary

NitroSAT's performance has been verified across 13+ problem domains, from 80M-clause industrial scheduling to 512×512 arithmetic circuits. For high-fidelity technical tables, latency breakdowns, and engine parity audits, see the authoritative benchmarks README.

View Full Numerical Results on GitHub →

$O(M)$ Linear Scaling Verified across three orders of magnitude in clause count. Largest instance: 80,278,884 clauses (Enterprise Timetabling) on a single laptop core. Prime weight speedup: 3.4–4× on structured geometries with 75% topological complexity reduction.

Assessment: The prime weighting mechanism is empirically causal. The mathematical framework presented in Sections 2–5 is consistently supported by the topological ablation study and large-scale benchmarks spanning hardware verification, scheduling, graph theory, adversarial constructions, and biological constraint satisfaction.

14. Navokoj: Production API

To make NitroSAT's capabilities accessible beyond the command line, the solver is deployed as a production API under the name Navokoj (navokoj.shunyabar.foo). Navokoj provides multiple solver engines, spectral diagnostics, and structured output for integration into larger systems.

Multi-Engine Architecture

Navokoj exposes several solver configurations adapted to different problem regimes:

Engine	Description	Use Case
nano	Minimal, fast	Small instances, latency-sensitive
mini-deepthink	Lightweight with diagnostics	Parsing, Boolean expression input
pro-deepthink	Full NitroSAT pipeline	Large structured and adversarial instances
hybrid	Adaptive engine selection	Unknown problem structure
auto	Batch-optimized routing	Throughput-oriented workloads

DEFEKT Spectral Diagnostics

Navokoj includes a spectral diagnostic system (DEFEKT) that provides a structural analysis of the constraint graph prior to solving. DEFEKT computes spectral gap estimates, clause density statistics, and topological complexity indicators in approximately 5–6 ms, functioning as a rapid characterization tool for constraint instances. This enables upstream systems to route problems to appropriate engines and estimate difficulty before committing compute resources.

API Validation Results

The Navokoj API implementation has been validated against the full NitroSAT benchmark suite, ensuring 100% parity between the raw C engine and the production-grade endpoint.

Detailed API latency benchmarks and engine validation logs are archived in the Project Heritage section.

Navokoj supports Boolean expression input (no manual CNF conversion required), violation debugging with variable blame attribution, and anytime solving with timeout budgets returning partial results.

Key capabilities validated: multiple engine routing, DEFEKT spectral diagnostics, violation debugging with variable blame attribution, Boolean expression input without manual CNF conversion, batch solving, and anytime solving with timeout budgets returning partial results.

15. Reproducibility and Open Source Rationale

NitroSAT is released under the Apache License 2.0 as a scientific decision rather than a commercial one. The theory presented in this paper makes specific, falsifiable predictions: prime weights reduce topological complexity ($\beta_1$) by approximately 75%; heat kernel diffusion detects phase transitions in constraint geometry; satisfaction improves as constraint density increases within the structured regime. These predictions cannot be verified from a publication alone—they require execution of the solver on the stated instances.

When NitroSAT solves an 80-million-clause enterprise timetabling instance and reports $\beta_1$ decreasing from 44,983,725 to 6,701,177 over the course of optimization, that trajectory constitutes an observable, reproducible empirical test of the theory. Every topology snapshot, every phase transition signal, and every prime weight ablation is visible in the solver's output. A closed-source implementation would render the mathematical claims unverifiable.

Availability

Resource	Location
NitroSAT (C)	GitHub · Zenodo
NitroSAT (LuaJIT)	Codeberg
Navokoj API	navokoj.shunyabar.foo
CNF Test Dataset	HuggingFace
Distill Article	sethuiyer.codeberg.page/NitroSAT
Video Presentation	YouTube

Compilation requires only a C99 compiler and the standard math library:

gcc -O3 -march=native -std=c99 nitrosat.c -o nitrosat -lm

The empirical validation loop closes only when any researcher can compile, execute, and observe the theory behaving as predicted on the published benchmark instances.

Related Papers

Explore the broader research ecosystem around physics-inspired SAT solving:

Paper	Description	Links
BAHA: Branch-Aware Holonomy Annealing	The Lambert-W teleportation mechanism for escaping topological fractures in constraint landscapes.	DOI · Web
Casimir-SAT: When Boolean Logic Meets the Casimir Effect	Foundational work introducing continuous relaxation, Langevin dynamics, and free energy minimization for SAT.	DOI · Web

These papers form the theoretical foundation for NitroSAT's physics-inspired approach to constraint satisfaction.