PhaseRelax: A Deep Dive into the Geometry of Random 3-SAT

PhaseRelax is a continuous-variable relaxation method designed for random 3-SAT problems, utilizing heavy-ball momentum on the $N$-torus. Unlike conventional solvers, this approach serves as a mechanistic probe into the geometry of the continuous relaxation landscape, particularly at the critical phase transition ($\alpha = 4.27$).

Core Contributions

This study offers a thorough exploration and characterization of the continuous dynamics that result in permanent freeze, addressing key theoretical challenges within the context of gradient descent:

1. The 4-Criterion Obstruction (Theorem 5.3): For large systems (where $N \approx 75$), the dynamics approach tropical local minima, adhering to four essential geometric conditions:

   • Pole-locking via the coordinate Jacobian.
   • An outward normal gradient at the hypercube boundary.
   • Backbone rigidity with energy barriers that diverge as $\Theta(N)$.
   • A significant linear programming integrality gap ($\geq 6$ simultaneous flips).

2. Resolved Gradient Paradox: This paradox arises from the observed 20-fold ratio between gradients in $x$-space and $\varphi$-space, governed by the Jacobian relationship:
   [ | \nabla_x E | / | \nabla_\varphi E | \approx 1 / \langle |\sin \varphi_i| \rangle. ]
   Notably, the $x$-space gradient presents no feasible escape due to its alignment with the outward normal of the hypercube $[-1,1]^N$.

3. Scaling and Thermodynamic Limit: The decay rate of the per-chain basin probability is given by
   [ \hat{p} \approx 232 \cdot N^{-2.32}, ]
   reflecting the strengthening obstruction that persists as $N$ increases, confirming the logarithmically growing core of critical unfrozen variables.

Verification and Repository Structure

The repository includes a structured verification script (verification_phaserelax.py) that aligns with the paper's findings, providing validation for key claims, theorems, and scaling laws.

• Directory Structure:
  • /paper: Contains LaTeX source files and the PDF preprint.
  • /script: Features the primary verification script.
  • /misc: Includes raw experimental scripts utilized for data generation in the manuscript.

Verification Script Functionality

The main verification script executes a series of checks, displaying either PASS or FAIL for each assertion. Here is a summary of what the script verifies:

Script ID	Corresponding Paper Section	Verified Content
V1	Section 3 / Observation 3.1	Step-budget saturation at $K=1500$
V2	Section 4.2 / Table 5	Quality floor ($\sim0.16%$) comparison vs WalkSAT
V3	Section 4.3	SAT-gated solve rates and basin probability fit
V4	Section 2.2 / Proposition 2.3	Gradient conditions at stuck points
V5	Section 5.1	Stuck configurations as tropical local minima
V6	Section 5.2	LP integrality gap analysis
V7	Section 5.5	Obstruction locality assessments

Key Structural Insights

The findings of this research provide crucial insights into the nature of random 3-SAT problems, which are summarized as follows:

Finding	Description / Value	Section
Quality floor	$\sim 0.16%$ broken clauses, comparable to WalkSAT	Section 4.2
Basin probability	$\hat{p} \approx 232 \cdot N^{-2.32}$	Section 4.3
Jacobian gradient ratio	$	\nabla_x E
$x$-space direction	Outward normal to $[-1,1]^N$	Theorem 5.3
LP gap analysis	Mean $\approx 6.3$ fractional flips	Section 5.2
Backbone scaling	$\Theta(N)$ at $\alpha=4.27$	Section 4.3

This repository provides a comprehensive exploration of the geometry surrounding random 3-SAT transitions, serving as a resource for researchers investigating algebraic obstructions in optimization problems.