TheoremStatement: Literature-sourcedProof: 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.

Equal-spherical mixture assignments and objective converge to k-means

Statement

Let $n, p, K$ be positive integers, let $x_{1}, \dots, x_{n}, μ_{1}, \dots, μ_{K} \in R^{p}$ , and fix positive weights $π_{1}, \dots, π_{K}$ with $\sum_{k = 1}^{K} π_{k} = 1$ . Put $d_{i k} : = ∥ x_{i} - μ_{k} ∥_{2}^{2}$ , $d_{i}^{*} : = \min_{1 \leq k \leq K} d_{i k}$ , and $M_{i} : = {k : d_{i k} = d_{i}^{*}}$ . For every $σ > 0$ , define the normalized soft-assignment weights

$ρ_{i k}^{(σ)} : = \frac{π_{k} \exp (- d_{i k} / (2 σ^{2}))}{\sum_{j = 1}^{K} π_{j} \exp (- d_{i j} / (2 σ^{2}))}$

and the finite-data objective

$Ψ_{σ} : = - 2 σ^{2} \sum_{i = 1}^{n} \log (\sum_{k = 1}^{K} π_{k} \exp (- d_{i k} / (2 σ^{2}))) .$

As $σ ↓ 0$ , for each $i$ and $k$ ,

$ρ_{i k}^{(σ)} ⟶ {\begin{cases} \frac{π_{k}}{\sum_{j \in M_{i}} π_{j}}, & k \in M_{i}, \\ 0, & k \notin M_{i}, \end{cases}$

and

$Ψ_{σ} ⟶ \sum_{i = 1}^{n} d_{i}^{*} = \min_{z \in {1, \dots, K}^{n}} \sum_{i = 1}^{n} d_{i, z_{i}} .$

Thus a unique nearest center receives limiting weight one, while tied nearest centers divide limiting weight in proportion to their fixed mixture weights. This is a fixed-parameter finite-data limit and asserts no convergence of EM iterates.

Facts & Assumptions

Given: Finite positive integers $n, p, K$ , fixed vectors $x_{i}, μ_{k} \in R^{p}$ , and fixed positive weights $π_{k}$ summing to one.

[A1]

All indices range over finite sets and all data, centers, and weights are fixed; no probability-space assumption or choice axiom is used.

[F1]

The exponential tends to $+ \infty$ at $+ \infty$ and to $0$ at $- \infty$ : $\exp (u) \to 0$ as $u \to - \infty$ .

Proof

1.1givenA1F1algebra

Fix $i$ and write $R_{i} (σ) : = \sum_{k \in M_{i}} π_{k} + \sum_{k \notin M_{i}} π_{k} \exp (- (d_{i k} - d_{i}^{*}) / (2 σ^{2}))$ . Every difference in the second sum is strictly positive, so each exponential there tends to zero by [F1], since its exponent tends to $- \infty$ as $σ ↓ 0$ ; the sum is finite. Hence $R_{i} (σ) \to \sum_{k \in M_{i}} π_{k} > 0$ .

2.1givenA1step 1.1algebra

Factoring $\exp (- d_{i}^{*} / (2 σ^{2}))$ from the denominator of $ρ_{i k}^{(σ)}$ gives $ρ_{i k}^{(σ)} = π_{k} \exp (- (d_{i k} - d_{i}^{*}) / (2 σ^{2})) / R_{i} (σ)$ . If $k \in M_{i}$ , its exponential is one and the limit is $π_{k} / \sum_{j \in M_{i}} π_{j}$ ; if $k \notin M_{i}$ , its positive distance gap makes the numerator tend to zero while the denominator tends to a positive number. This proves the stated responsibility limits.

2.2givenA1step 1.1algebra

The same factorization gives $- 2 σ^{2} \log \sum_{k} π_{k} e^{- d_{i k} / (2 σ^{2})} = d_{i}^{*} - 2 σ^{2} \log R_{i} (σ)$ . The nearest terms give $R_{i} (σ) \geq \sum_{k \in M_{i}} π_{k} > 0$ , while $d_{i k} - d_{i}^{*} \geq 0$ and $\sum_{k} π_{k} = 1$ give $R_{i} (σ) \leq 1$ . Thus $\log R_{i} (σ)$ stays between two finite constants, so the second term tends to zero. Summing over the finite set of observations gives $Ψ_{σ} \to \sum_{i} d_{i}^{*}$ .

3.1givenA1step 2.2constructalgebra∎

For each labeling $z \in {1, \dots, K}^{n}$ , $d_{i, z_{i}} \geq d_{i}^{*}$ for every $i$ , so $\sum_{i} d_{i, z_{i}} \geq \sum_{i} d_{i}^{*}$ . Define $z_{i} : = \min M_{i}$ , which exists because $M_{i}$ is a nonempty finite subset of ${1, \dots, K}$ . This labeling attains equality, proving the displayed minimum without any choice principle.

Depends on

The exponential tends to $+\infty$ at $+\infty$ and to $0$ at $-\infty$

Used by

A tied observation keeps fractional Gaussian responsibilities Example

Dependency tree · two levels

5 results within two dependency steps 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, Exercise 13.1 (standard reference, not scraped)
Christopher M. Bishop, Pattern Recognition and Machine Learning, §9.3.2 and Exercise 9.11 (standard reference, not scraped)