Pipeline-generated

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.

✓ 2 results · all verified · 2 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs; all 2 also cleared it.

Finite Quantization, Lloyd Iteration, and Compact Companders — Examples

1 · Prerequisites

2 · Summary

The exact five-point empirical calculation shows that Lloyd can stop at a strictly suboptimal fixed point. The uniform source on $[0, 1]$ gives the exact midpoint distortion $1 / (12 N^{2})$ and matches the compact compander limit. Both checks use the definitions and proved claims on the A page; this companion has no later A-page prerequisite.

Source context

The complete MIT chapter and Gray–Neuhoff survey explain the Lloyd local-optimum caveat and scalar high-rate context. The finite five-point costs and uniform-cell integral are computed exactly in the examples themselves; no source statement replaces those calculations.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Lloyd can stop at a strictly suboptimal finite-data fixed point

Statement refuted

Every fixed point of the exact finite-data Lloyd iteration is a global minimizer of empirical squared-error distortion.

Facts & Assumptions

Given: Five equally weighted data points $0, 1, 4, 5, 9 \in R$ , two ordered centers, and the exact iteration of Exact finite-data Lloyd quantizer.

[F1]

Exact finite-data Lloyd quantizer: the iteration uses least-index nearest-center assignments, updates nonempty clusters to their weighted centroids, leaves empty centers unchanged, and stops when centers are unchanged.

[F2]

The weighted centroid minimizes finite-cluster squared error: each nonempty cluster's weighted squared error is minimized at its weighted centroid.

[F3]

Let $X_{5} : = {0, 1, 4, 5, 9}$ and $(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) : = (0, 1, 4, 5, 9)$ . Put $μ_{5} : = \frac{1}{5} \sum_{i = 1}^{5} δ_{x_{i}}$ on $X_{5}$ , where $δ_{x_{i}}$ is unit point mass at $x_{i}$ . This is a probability measure on the relative Borel sigma algebra of the finite Borel set $X_{5}$ , with finite second moment $\frac{1}{5} \sum_{i = 1}^{5} ∣ x_{i} ∣^{2} < \infty$ . For a center pair $c = (c_{1}, c_{2})$ , let $Q_{c} : X_{5} \to {1, 2}$ be its least-index nearest-center rule. Each fiber is Borel because $X_{5}$ is finite, so Finite measurable squared-error quantizer and nearest-center rule gives

$D_{μ_{5}} (Q_{c}; c_{1}, c_{2}) = \frac{1}{5} \sum_{i = 1}^{5} \min_{1 \leq j \leq 2} ∣ x_{i} - c_{j} ∣^{2},$

so the sample-average costs below are exactly the distortions for this explicitly specified empirical law.

Counterexample

1.1givenF1F3algebra

Give each point weight $1 / 5$ and initialize centers at $(5 / 2, 9)$ . The squared distances to these centers, in point order $0, 1, 4, 5, 9$ , are $(25 / 4, 81)$ , $(9 / 4, 64)$ , $(9 / 4, 25)$ , $(25 / 4, 16)$ , and $(169 / 4, 0)$ ; each comparison is strict, so the clusters are ${0, 1, 4, 5}$ and ${9}$ .

1.2givenF3algebra

The alternative centers $(1 / 2, 6)$ assign $0, 1$ to $1 / 2$ and $4, 5, 9$ to $6$ , with strict comparisons: the respective squared-distance pairs are $(1 / 4, 36)$ , $(1 / 4, 25)$ , $(49 / 4, 4)$ , $(81 / 4, 1)$ , and $(289 / 4, 9)$ . Their total squared error is $(1 / 2) + (4 + 1 + 9) = 29 / 2$ , hence their average distortion is $29 / 10$ .

2.1F1F2F3step 1.1algebra

The two weighted centroids are $(0 + 1 + 4 + 5) / 4 = 5 / 2$ and $9$ , so the center update leaves $(5 / 2, 9)$ unchanged by [F2]. The nearest assignment is unchanged as well by step 1.1, so [F1] stops at this tuple. Its distortion is $(25 / 4 + 9 / 4 + 9 / 4 + 25 / 4) / 5 = 17 / 5$ by [F3].

3.1step 2.1step 1.2algebra∎

Since $29 / 10 < 17 / 5$ , the alternative two-center quantizer has strictly lower distortion than the stopped Lloyd output in step 2.1. Thus that exact fixed point is not globally optimal, refuting the statement.

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Uniform density gives exact midpoint compander distortion

Example

Take the uniform source density $f (x) = 1$ and point density $g (x) = 1$ on $[0, 1]$ . For every integer $N \geq 1$ , the compander uses $N$ equal cells and their midpoints as reproduction values.

Facts & Assumptions

Given: The interval $[0, 1]$ , densities $f = g = 1$ , and the compander definition of Positive C1 compact one-dimensional compander.

[F1]

Positive C1 compact one-dimensional compander: the cells are bounded by $ϕ (j / N)$ and the reproduction values are $ϕ ((j - \frac{1}{2}) / N)$ , where $ϕ$ is the inverse cumulative coordinate.

[F2]

Exact high-rate limit for a positive compact one-dimensional compander: the limit coefficient is $\frac{1}{12} \int_{0}^{1} f (x) / g (x)^{2} d x$ under the positive normalized $C^{1}$ hypotheses.

Verification

1.1givenF1algebra

Here $G_{g} (x) = x$ and $ϕ (u) = u$ , so cell $j$ is $[(j - 1) / N, j / N)$ (with the final endpoint included) and its reproduction value is $(j - \frac{1}{2}) / N$ by [F1].

2.1givenstep 1.1algebra

Put $h = 1 / N$ . On each cell, translation to its midpoint gives $\int_{(j - 1) / N}^{j / N} (x - (j - \frac{1}{2}) / N)^{2} d x = \int_{- h / 2}^{h / 2} t^{2} d t = h^{3} / 12$ . Summing the $N$ equal cell integrals yields $D_{N} (1, 1) = 1 / (12 N^{2})$ , including $N = 1$ .

3.1F2step 2.1algebra∎

Therefore $N^{2} D_{N} (1, 1) = 1 / 12$ for every $N$ , while [F2] gives the same limit coefficient $(1 / 12) \int_{0}^{1} 1 d x = 1 / 12$ .

Finite Quantization, Lloyd Iteration, and Compact Companders — Examples

1 · Prerequisites

2 · Summary

Source context

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Lloyd can stop at a strictly suboptimal finite-data fixed point

Statement refuted

Facts & Assumptions

Counterexample

Uniform density gives exact midpoint compander distortion

Example

Facts & Assumptions

Verification

Sources