Counterexample · D-VORONOI-NOT-EXCHANGE

Nearest-centre consistency is not enough

Counterexamplepublication: internal

Meaning

A self-consistent D-Voronoi partition can still admit a profitable exact relocation.

Scientific context

Exchange stability implies a nearest-centre structure, but the converse is false: a partition can be a fixed point of its own nearest-centre rule and still admit a single relocation with a strictly positive exact gain. The witness is a four-row, one-dimensional, two-cell example (CE-D-VORONOI-CONVERSE-001).

The consequence is that a partition looking geometric is not evidence that it is stable, and stability — not the appearance of geometry — is what licenses compiling a partition into a reusable rule. This is why compile_quantizer() refuses a partition whose stability certificate is False, citing the fixture, and reports the remaining gain so the size of the gap is visible.

The nearest precedent is the analogous statement for sum-of-squared-errors, where Lloyd fixed points are known not to be Hartigan-stable.

Statement

Self-consistent nearest-centroid assignment under the current D metric is strictly weaker than one-point exact exchange stability.

Where it stops

Refuted by

CE-D-VORONOI-CONVERSE-001
Every strictly self-consistent I_q^{-1}-Voronoi finite partition (each row strictly nearest its own centroid) is one-point exchange stable.

Closest prior work

Nearest prior work

Telgarsky, Vattani (2010)Hartigan's Method: k-means Clustering without Voronoi

Relationships

Open next door

In the library

Enforced by the refusal CE-D-VORONOI-CONVERSE-001: the library declines the operation and names the fixture.

Every object and refusal

Local graph

Prerequisites to the left, what it enables or raises to the right, boundary cases below. Open in the map.

The example

D10. Voronoi fixed point does not imply exchange stability

Measured suite: 35/100 Lloyd/Voronoi fixed points still admitted an exact improving one-point move, with improvements up to about 1.033 nat.

The exact witness CE-D-VORONOI-CONVERSE-001 is machine-checked as ScoreQuantFormal.VoronoiConverse.strictVoronoi together with VoronoiConverse.not_exchangeStable in formal/ScoreQuantFormal/Counterexamples.lean: every row is strictly nearest its own centroid, yet moving row 2 raises the retained information from $25/48$ to $9/16$ . The claim's formal_proof field stays empty because its statement is the proposition being refuted (ADR 0030).

From D-optimality · chapter contents

Evidence: COUNTEREXAMPLES/CE-D-VORONOI-CONVERSE-001.json. Measured, never theorem authority.