01
The problem
| System | N identical atoms in three dimensions (2 ≤ N ≤ 200), a free cluster at zero pressure. Every pair interacts through the Lennard-Jones potential, written in the squared distance s = r²: φ(s) = 4ε(σ¹²/s⁶ − σ⁶/s³), not truncated. |
| Energy | E(x) = ½ Σi≠j φ(sij). Energy, gradient and Hessian are rational functions of the coordinates, so the checker evaluates exactly the formula Lean reasons about (CSP-C01). |
| Symmetry | E is invariant under rotations and reflections, translations and relabelling of the atoms. A minimum is therefore never isolated in ℝ3N; it is a minimum modulo these motions, and the six orbit directions are fixed by the Eckart gauge. |
| Input | ε, σ and every coordinate are exact dyadic rationals m·2e in the certificate — the doubles the searcher actually produced. The checker echoes the problem as a PROBLEM line for the caller to compare. |
02
What a certified run reports
LJ₁₃, seed 1, twelve generations of twelve particles. The searcher keeps its three best distinct minima and, as a demonstration of the deduplication certificate, adds the best one again rotated and with its atoms numbered backwards. The checker reads the certificate and re-checks everything in exact rational arithmetic; this is its full output.
certify-csp lj13.cert
PROBLEM N 13 eps 1.00000000000000000000 sigma 1.00000000000000000000 pressure 0 MIN_OK 0 -44.326801419534023 -44.326801419534022 0.000056994475 0.00000000000611516998 MIN_OK 1 -41.471979847810849 -41.471979847810848 0.000027927293 0.00000000001481269784 MIN_OK 2 -41.444597002447481 -41.444597002447480 0.000019549105 0.00000000002081694528 MIN_OK 3 -44.326801419534023 -44.326801419534022 0.000056994475 0.00000000000610162457 SAME_OK 0 3 DISTINCT 0 1 DISTINCT 0 2 DISTINCT 1 2 DISTINCT 1 3 DISTINCT 2 3 BEST 3 -44.326801419534023 -44.326801419534022 TIE 3 0 CSP_OK 4
| Line | What the Lean theorem guarantees | Claim |
|---|---|---|
| PROBLEM | The problem the certificate is about (N, ε, σ, pressure), exactly, for the caller to compare with what it asked for. | CSP-B02 |
| MIN_OK k lo hi R d | In the ball of radius R around candidate k (in the Eckart section) the energy has exactly one minimiser x*, with quadratic growth; it is the only stationary point there, ∇E(x*) = 0 in all of ℝ3N, ‖x* − x₀‖ ≤ d and E(x*) ∈ [lo, hi]. Any configuration within R of x₀ has energy ≥ E(x*), with equality only for a rotated, reflected or translated copy of x*. | CSP-B01, D01, D02 |
| SAME_OK a b | The exact minima of candidates a and b are the same structure: they differ by a permutation of the atoms, an orthogonal map and a translation, and have equal energy. | CSP-B04 |
| DISTINCT a b | The two energy intervals are disjoint, so the exact minima are different structures: no permutation, rotation, reflection or translation maps one onto the other. | CSP-B04 |
| UNDECIDED a b | Neither proved; the intervals overlap and the certificate holds no same record for the pair. | — |
| BEST k lo hi | Candidate k has the lowest certified upper bound among the candidates of this run. Not a claim that it is the global minimum. | CSP-B02 |
| TIE k j | Candidate j’s interval overlaps the best one’s, so the run cannot say which is lower. Here j is the rotated, renumbered copy, already proved the same structure by SAME_OK. | CSP-B02 |
| CSP_OK K / CSP_FAIL | All K candidates passed; otherwise the checker names the first check that failed and certifies nothing. | CSP-B02 |
03
How the certificate works
The searcher stops at a point x₀ with a tiny but non-zero gradient. The certificate proves that a true minimum x* lies within a radius it states, by showing that the energy is strongly convex on a small ball in the right slice of configuration space. All checks are exact rational arithmetic; the searcher’s floating-point numbers are only data.
- 1
Eckart gauge
Rotations and translations make the Hessian singular in six directions. The checker works in the Eckart section through x₀: displacements with no net translation and no net rotation relative to x₀. Lean proves every configuration can be rotated and translated into this section without moving further from x₀, so a strict minimum in the section is a strict minimum modulo Euclidean motions (CSP-D01).
- 2
Atoms stay apart
On the ball of radius R no pair moves by more than √2·R, so every squared distance stays above an explicit slo > 0. From it the checker computes, for every pair, how much the Hessian can drop across the ball, using explicit bounds on φ″ and φ‴ and the mean-value theorem.
- 3
Small gradient
‖∇E(x₀)‖ ≤ g, with every term rounded down to a 2⁻¹⁰⁰ grid and the rounding error added to the bound.
- 4
Positive definite, exactly
The Hessian at x₀ minus the pair losses, plus a penalty κ on the six orbit directions, minus μ·I, is shown positive semi-definite by a Schur-complement elimination that rounds to a 2⁻¹⁰⁰ grid at every step and subtracts the rounding error from the diagonal (proved sound in Lean). Then E is μ-strongly convex on the whole ball within the section.
- 5
Strong-convexity ball theorem
If g < μR, the ball contains exactly one stationary point, the unique minimiser, within g/μ of x₀, with energy in [E(x₀) − g²/(2μ), E(x₀)] (CSP-D02). The checker encloses E(x₀) itself, so this is the printed interval.
- 6
Same or distinct
For a
samerecord the certificate gives a permutation, an exactly orthogonal rational matrix (a signed Cayley transform, checked as QᵀQ = I exactly) and a translation that map one candidate into the other’s uniqueness ball, and vice versa. Two minima whose energy intervals are disjoint are distinct structures without any further data.
Why the intervals are so tight: the searcher finishes each relaxation with Newton steps until the gradient is about 10⁻¹³, so g²/(2μ) is about 10⁻²⁴; the width of the interval is set by the rounding of the 2⁻¹⁰⁰ grid and the outward rounding of the printed decimals. The uniqueness radius is 2×10⁻⁵ to 1.7×10⁻⁴ σ, limited by how fast the Lennard-Jones Hessian changes.
04
The search, and what is proved about it
The searcher build/mini-csp (C11, double precision) follows the algorithm published by Wang, Lv, Zhu and Ma (PRB 82, 094116, 2010; CPC 183, 2063, 2012), written from the papers alone, without reference to any existing program. Each generation relaxes every particle (BFGS, then Newton with a gauge penalty), sorts by energy, replaces the worst fraction with fresh random structures and moves the rest by the particle-swarm update v ← ωv + c₁r₁(p − x) + c₂r₂(g − x), x ← x + v. Sorted interatomic distances serve as a fingerprint, but only to propose merges; only the checker decides.
Nothing the searcher does enters the trust chain: a bug in it can only make it miss structures, never produce a wrong certified statement. Separately, Lean proves two properties of the search algorithm itself, under idealised assumptions stated in the ledger:
- Particle-swarm stability regions (CSP-A01)With the attractors fixed and ideal uniform random numbers, the mean of a particle converges exactly when |ω| < 1 and 0 < c₁ + c₂ < 4(1 + ω), and its mean square exactly in a smaller region that for c₁ = c₂ is Poli’s 0 < c < 24(1 − ω²)/(7 − 5ω). Both are “if and only if”, proved through the Schur–Cohn/Jury criteria for quadratic and cubic polynomials. The Clerc–Kennedy defaults ω = 0.7298, c₁ = c₂ = 1.49618 — and their exact double values — lie in both regions.
- Random restarts find the global basin (CSP-A02)If every generation contains at least one independent structure drawn uniformly from a box containing the global minimum, the probability that none has landed within δ of it after t generations is at most (1 − pδ)t → 0, with pδ > 0. Asymptotic only: it gives no guarantee for a finite run.
Acknowledgement. The search algorithm is that of CALYPSO, by Yanchao Wang, Jian Lv, Li Zhu and Yanming Ma (Jilin University). Their clear published description of particle-swarm structure prediction is what made an independent, verifiable implementation possible; mini-CSP is our tribute to that work, not a replacement for it.
05
Claims in the trust ledger
| Claim | Statement | Tier |
|---|---|---|
| CSP-C01 | The cluster energy and its first and second directional derivatives are rational functions of the coordinates and are the true derivatives while all distances are positive; the energy is invariant under orthogonal maps, translations and permutations of the atoms; explicit lower bound on the pair Hessian | T3 |
| CSP-D02 | Strong-convexity ball theorem: μ-convex on a ball with gradient ≤ g < μR at the centre gives a unique stationary point, the unique minimiser with quadratic growth, within g/μ, with energy in [f(x₀) − g²/(2μ), f(x₀)] | T3 |
| CSP-D01 | Gauge: every configuration can be moved into the Eckart section by a rotation, reflection and translation without moving further from x₀; a strict minimum in the section is a strict local minimum modulo Euclidean motions and a stationary point in all of ℝ3N | T3 |
| CSP-B01 | Checker soundness, local minimum: what MIN_OK states | T4 |
| CSP-B04 | Checker soundness, deduplication: SAME_OK and DISTINCT | T4 |
| CSP-B02 | Checker output: every line is read off B01 and B04; BEST is a comparison of intervals, not a global-optimum claim; PROBLEM echo | T4 |
| CSP-A01 | Particle-swarm first-order and mean-square stability regions, “if and only if”; the default parameters lie in both (idealised model A-CSP-01, 02) | T3 |
| CSP-A02 | Random restarts reach any neighbourhood of the global minimum with probability tending to 1 (idealised model A-CSP-03) | T3 |
| CSP-T01 | The searcher finds the Cambridge Cluster Database minima of LJ₃…LJ₁₃ and every output is accepted by the checker; tampered certificates are rejected (known answers in verify_all) | T0 |
| CSP-B06 | One exit-code rule (second adversarial review, 7 October): 0 only if no line starts with a tag ending in _FAIL or _PARTIAL; 3 when the main check passed and a secondary one failed; 1 rejected, 2 unreadable | T0 |
| CSP-P01 | Frama-C/WP proof of the C particle-swarm step (velocity clamp, box handling, fractional wrap-around) under the IEEE 754 model — not yet written, target T4 | T0 |
#print axioms for checkMin_sound, checkSame_sound, distinct_sound, ball_min and align shows only Lean’s standard propext, Classical.choice and Quot.sound.
06
Proof dependencies
Which claims are built on which, read from the Lean proof terms themselves (not from the ledger’s hand-written dependency column). The graph starts with this domain only; click the legend to add the others, or switch to “All Lean theorems” for the theorem level. All domains together are on the programme page.
- a claim or theorem, coloured by domain
- uses — points at what the proof relies on
- bigger — used by more results
- what the selection uses
- what uses the selection
Drag to pan, scroll or pinch to zoom, drag a node to move it; click a node to see what it uses and what uses it, and “Only its chain” to keep just those, directly or not. An arrow from claim A to claim B means that a proof behind A uses a theorem behind B (through lemmas that belong to no claim); two claims can use each other. Claims without a Lean theorem (tests, T0–T2) are not drawn. Generated by scripts/depgraph.py; a reading aid, not part of the trust chain.
07
Cross-checks and supporting evidence
| Cluster | Certified best energy (Lean interval) | Cambridge Cluster Database |
|---|---|---|
| LJ3 | [-3.000000000000001, -2.999999999999999] | -3.000000 |
| LJ4 | [-6.000000000000001, -5.999999999999999] | -6.000000 |
| LJ5 | [-9.103852415707557, -9.103852415707556] | -9.103852 |
| LJ6 | [-12.712062256809339, -12.712062256809338] | -12.712062 |
| LJ7 | [-16.505384168012216, -16.505384168012215] | -16.505384 |
| LJ8 | [-19.821489192154761, -19.821489192154760] | -19.821489 |
| LJ9 | [-24.113360433647182, -24.113360433647181] | -24.113360 |
| LJ10 | [-28.422531893437559, -28.422531893437558] | -28.422532 |
| LJ11 | [-32.765970089979004, -32.765970089979003] | -32.765970 |
| LJ12 | [-37.967599562363927, -37.967599562363926] | -37.967600 |
| LJ13 | [-44.326801419534023, -44.326801419534022] | -44.326801 |
- ASE 3.29 (
LennardJones, cut-off 1000 σ) on the 11 certified centres, against a 40-digit mpmath sum≤ 7.1×10⁻¹⁵ - Uniqueness radius R / distance bound ‖x* − x₀‖, LJ₃…LJ₁₃2×10⁻⁵…1.7×10⁻⁴ σ / ≤ 2.1×10⁻¹¹ σ
- A coordinate’s mantissa changed by 2³⁰CSP_FAIL (local-minimum check)
- Two entries of a
samepermutation swappedCSP_FAIL (same check) - ε changed to 2 in the certificateaccepted, caught by the known answer and the
PROBLEMecho - Searcher time per cluster / checker time for 4 candidates at N = 3, 7, 130.01–9 s / 0.1, 1.3, 17 s
- Searcher under AddressSanitizer, UBSan and LeakSanitizerclean
08
Open gaps
- Global optimality
BESTis the lowest certified minimum the run found. Proving it global needs a branch-and-bound certificate over configuration space (planned phase 5, CSP-B05). - Crystals, symmetry and pressureOnly free clusters at zero pressure so far. Symmetry-constrained generation with symmetry certificates, periodic cells, pressure and multi-component systems are phases 2 and 3 (CSP-B03, C02, D03, D04).
- Deduplication in the search
samerecords are only produced by--same-demo; merges the fingerprint proposes during a search do not yet come with permutation and rotation certificates, so only one representative is kept (permutation matching plus Kabsch alignment is planned). - The searcher’s codeUntrusted (T0). The particle-swarm step is to get a Frama-C/WP proof under the IEEE 754 model (CSP-P01); the search loop, its distribution and restart logic a TLA+ specification with trace validation (CSP-L01); and a
fis cspcommand with JSON output (CSP-L02). - Beyond the idealised modelCSP-A01 and A02 assume fixed attractors, ideal random numbers and real coordinates; the mean-square result covers p = g only. The phase-1 searcher uses ω = 0.7, c₁ = c₂ = 1.5, inside both regions by the proved formula but not the constants of
defaults_stable, and clamps velocities, which the model does not include.
Plan: docs/plan-mini-csp.md; specification: domains/csp/README.md; ledger: domains/csp/LEDGER.md. A comparison with CALYPSO itself on the same systems is optional and not a dependency.