Result · D-EXCHANGE-VIOLATION-LOWER-BOUND

Geometry violations have a measurable gain

Proved heremachine-checked statementpublication: internal

Read the proof and evidence →

Meaning

A wrongly assigned atom supplies a strictly improving relocation with an explicit lower bound under the stated hypotheses.

Statement

For the theorem-triggering violation, ΔF_D >= log(1+αβ q_delta^2/4)>0 for distinct centroids.

Relationships

Rests on

The full chain beneath it

Open next door

Machine-checked statement

The statement is proved in Lean 4.33.1 + Mathlib 4.33.1 as ScoreQuantFormal.violation_log_gain. Its hypotheses and conclusion are frozen in a specification file that was audited against this page's statement before the proof was written (verdict: match after hardening). A Lean build certifies the theorem, not the Python and JAX code that implements it.

Local graph
Local map of Quantitative D gain lower bound for a Voronoi violation3 prerequisites to the left, 0 results it enables or questions it raises to the right, 0 boundary cases below.Scalar core of the D exchange-violation lower boundScalar core of the D…D leverage inequalityD leverage inequalityExact finite D log-determinant gainExact finite D log-de…Quantitative D gain lower bound for a Voronoi violationQuantitative D gain l…
Prerequisites to the left, what it enables or raises to the right, boundary cases below. Open in the map.

Proof

D5. Exchange stability implies strict D-Voronoi geometry

Let coincident score rows be merged into distinct atoms with positive weights, and partition those atoms into exactly KK nonempty cells. Assume I≻0I\succ0, that the only relocation constraint is preservation of nonempty cells, and that exchange stability means no exact positive-gain relocation (zero gain tolerance). Then a point in a non-singleton source that is tied with or farther from its own centroid than a competing centroid under I−1I^{-1} has

ΔFD≥log⁡(1+αβ4qδ2)>0\boxed{ \Delta F_D \ge \log\left(1+\frac{\alpha\beta}{4}q_\delta^2\right)>0 }

when the two centroids are distinct. Here qδ=(μa−μb)⊤I−1(μa−μb)q_\delta=(\mu_a-\mu_b)^\top I^{-1}(\mu_a-\mu_b).

The exact algebra is

det⁡(I+ΔI)det⁡I=1+E,E≥αβ4[qδ2+(qaa−qbb)2].\frac{\det(I+\Delta I)}{\det I}=1+E, \qquad E\ge\frac{\alpha\beta}{4} \left[q_\delta^2+(q_{aa}-q_{bb})^2\right].

Distinct centroids follow from stability rather than needing a separate assumption. If μa=μb\mu_a=\mu_b and either cell is non-singleton, moving a non-centroid atom between them gives determinant ratio 1+(α−β)qaa>11+(\alpha-\beta)q_{aa}>1. If both are singletons, equality would mean the two score atoms are duplicates, excluded by merging. A singleton atom is then strictly nearest to its own centroid because its own distance is zero and every other centroid is distinct.

Hence

one-point exchange stable⇒strict self-consistent D-Voronoi.\boxed{ \text{one-point exchange stable} \Rightarrow \text{strict self-consistent D-Voronoi}. }

The converse fails.

Exact ties between distinct centroids are therefore ruled out, not left as an unresolved degeneracy. Split duplicate atoms are a genuine boundary failure: see COUNTEREXAMPLES/CE-D-UNMERGED-DUPLICATES-001.json, machine-checked as ScoreQuantFormal.UnmergedDuplicates.not_strictVoronoi — every hypothesis but injectivity of the score map holds there, and the conclusion fails. Zero-weight rows, singular/pseudodeterminant objectives, extra capacity or mass constraints, and nonzero solver gain tolerances are outside the theorem. At tolerance ε>0\varepsilon>0, the implementation certifies only that no geometric disagreement has exact gain exceeding ε\varepsilon; strict training-label reproduction need not hold.

Machine-checked. The whole of D5 is verified in Lean 4.33.1 + Mathlib for arbitrary dd: the frozen statement boundary is formal/ScoreQuantFormal/ExchangeVoronoiSpec.lean and the proof is ScoreQuantFormal.exchange_voronoi, with the quantitative bound as ScoreQuantFormal.violation_log_gain and its determinant forms violation_lower_bound / violation_strict_gain. Distinct centroids are derived there, as here, by centroid_ne_of_stable. Independent statement audit: AUDITS/FORMALIZATION-D-EXCHANGE-IMPLIES-VORONOI-001.md. The formalization covers the merged-atoms branch of the duplicate hypothesis only, and certifies nothing about the Python/JAX implementation.

Publication-grade audit and proof: AUDITS/AUDIT-D-EXCHANGE-VORONOI-001.md. Exact-rational regression: py/audit_d_exchange_voronoi.py.

From D-optimality · chapter contents