ExampleConstruction: Literature-sourcedVerification: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Tie retention gives distinct Lloyd fixed points

Example

For the data $x_{1} = 0, x_{2} = 1, x_{3} = 2, x_{4} = 3$ in $R$ and $K = 2$ , use nearest-center initialization with smallest-index initialization ties, retain the current label on later ties, replace each nonempty center by its assigned-data mean, and leave empty centers unchanged. For clusters $C_{1}, C_{2}$ and centers $c_{1}, c_{2}$ , define the cost by $J = \sum_{k = 1}^{2} \sum_{x_{i} \in C_{k}} (x_{i} - c_{k})^{2}$ . Initial centers $(0, 11 / 10)$ yield the fixed clusters ${0}$ and ${1, 2, 3}$ with centers $(0, 2)$ and cost $2$ . Initial centers $(3, 19 / 10)$ yield the fixed clusters ${3}$ and ${0, 1, 2}$ with centers $(3, 1)$ and cost $2$ . Initial centers $(1 / 2, 5 / 2)$ yield the fixed clusters ${0, 1}$ and ${2, 3}$ with centers $(1 / 2, 5 / 2)$ and cost $1$ . In the first two runs, the boundary observation is tied between the two updated centers and stays in its current cluster by the retention rule; each output is a fixed point, while the third has lower cost.

Example references

Lloyd's k-means algorithm with explicit tie handling — initialization, tie retention, empty-center handling, and the stop condition requiring unchanged labels and centers.

K-means objective — the squared Euclidean within-cluster objective used for the reported values.

Facts & Assumptions

Given: Data $0, 1, 2, 3 \in R$ , two clusters, and the Lloyd rules in the Example.

[F1]

K-means objective: for labels $c_{i} \in {1, 2}$ and centers $μ_{1}, μ_{2}$ , the objective is $J = \sum_{i = 1}^{4} (x_{i} - μ_{c_{i}})^{2}$ .

[F2]

Lloyd's k-means algorithm with explicit tie handling: initialization selects a nearest center with smallest-index ties; later assignments retain the current label on a tie and otherwise select a nearest center; each nonempty center is replaced by its assigned-data mean; the algorithm stops when both labels and centers are unchanged.

Proof

1.1givenF2algebra

From initial centers $(0, 11 / 10)$ , the nearest labels are $(1, 2, 2, 2)$ : the respective comparisons are $0 < 121 / 100$ , $1 > 1 / 100$ , $4 > 81 / 100$ , and $9 > 361 / 100$ . The mean update gives centers $0$ and $(1 + 2 + 3) / 3 = 2$ .

1.2F2algebra

From initial centers $(3, 19 / 10)$ , nearest labels are $(2, 2, 2, 1)$ : observations $0, 1, 2$ are strictly nearer $19 / 10$ , while $3$ equals the first center. Their means become $3$ for cluster $1$ and $(0 + 1 + 2) / 3 = 1$ for cluster $2$ .

1.3F1F2algebra

From initial centers $(1 / 2, 5 / 2)$ , nearest labels are $(1, 1, 2, 2)$ . The means of these clusters are again $1 / 2$ and $5 / 2$ , so labels and centers are unchanged and the procedure stops. The objective is $4 (1 / 2)^{2} = 1$ .

2.1F1F2step 1.1algebra

With centers $(0, 2)$ , observations $0, 2, 3$ keep labels $1, 2, 2$ by strict nearest comparisons; observation $1$ is at distance $1$ from each center and retains its current label $2$ . The labels remain $(1, 2, 2, 2)$ , so their means remain $(0, 2)$ and the procedure stops. The objective is $(0 - 0)^{2} + (1 - 2)^{2} + (2 - 2)^{2} + (3 - 2)^{2} = 2$ .

2.2F1F2step 1.2algebra

With centers $(3, 1)$ , observations $0, 1, 3$ keep labels $2, 2, 1$ by strict nearest comparisons; observation $2$ is tied at distance $1$ and retains label $2$ . The labels stay $(2, 2, 2, 1)$ , their means remain $(3, 1)$ , and the procedure stops. The objective is $(0 - 1)^{2} + (1 - 1)^{2} + (2 - 1)^{2} + (3 - 3)^{2} = 2$ .

3.1step 2.1step 2.2step 1.3algebra∎

The three explicitly computed terminal states have objective values $2, 2, 1$ , respectively, so they are distinct fixed points and the third has strictly lower objective than the first two. In the first and second runs, changing the tied boundary point to the other cluster would change the fixed partition; under the stated rule it remains with its current label.

Diagram

The horizontal coordinate is the observation value. Each row is one run; blue dots are assigned to cluster 1 and red dots to cluster 2. Dashed vertical ticks mark the updated centers, with labels above them. Vertical row placement has no numerical meaning. The diagram records the verified terminal assignments; the proof above establishes them without using the picture.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · one level

2 results within one dependency step of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, 2nd ed., corrected 12th printing, §14.3.5 (standard reference, not scraped)
Christopher M. Bishop, Pattern Recognition and Machine Learning, §9.1 (standard reference, not scraped)