ExampleConstruction: AI-adaptedVerification: AI-adaptedPipeline-generatedprecheck passaudited 2026-08-29

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.

A short floating-point dot product obeys the gamma_n error bound

Example

Take $x = (1, 2)$ , $y = (3, 4)$ and the binary64 unit roundoff $u = 2^{- 53}$ , for which $γ_{2} = 2 u / (1 - 2 u) \approx 2.2 \cdot 10^{- 16}$ . The left-to-right computed dot product $s_{2}$ satisfies

$s_{2} = 3 (1 + δ_{0}) + 8 (1 + δ_{1}) with ∣ δ_{0} ∣, ∣ δ_{1} ∣ \leq γ_{2},$

so the computed value is the exact dot product of slightly perturbed summands, and

$∣ s_{2} - 11 ∣ \leq γ_{2} (3 + 8) = 11 γ_{2} \leq γ_{2} ∥ x ∥_{1} ∥ y ∥_{1} = 21 γ_{2} \approx 4.7 \cdot 10^{- 15} .$

Facts & Assumptions

Given: The vectors $x = (1, 2)$ , $y = (3, 4)$ , the exact dot product $x \cdot y = 11$ , the unit roundoff $u = 2^{- 53}$ with $2 u < 1$ , and the left-to-right computed sum $s_{2}$ of the two products $x_{0} y_{0} = 3$ and $x_{1} y_{1} = 8$ .

[L1]

The computed dot product obeys the componentwise form $s_{n} = \sum_{j < n} x_{j} y_{j} (1 + δ_{j})$ with $∣ δ_{j} ∣ \leq γ_{n} = n u / (1 - n u)$ , and the normwise bound $∣ s_{n} - x \cdot y ∣ \leq γ_{n} \sum_{j} ∣ x_{j} y_{j} ∣ \leq γ_{n} ∥ x ∥_{1} ∥ y ∥_{1}$ (The computed floating-point dot product obeys componentwise and normwise error bounds).

Verification

technique · direct

1.1L1algebra

With $n = 2$ and $2 u < 1$ , [L1] applies and yields $s_{2} = x_{0} y_{0} (1 + δ_{0}) + x_{1} y_{1} (1 + δ_{1})$ with $∣ δ_{0} ∣, ∣ δ_{1} ∣ \leq γ_{2}$ , which for $x = (1, 2)$ and $y = (3, 4)$ reads $s_{2} = 3 (1 + δ_{0}) + 8 (1 + δ_{1})$ .

1.2algebra

The exact dot product is $x \cdot y = 1 \cdot 3 + 2 \cdot 4 = 11$ , and the absolute summand total is $∣ x_{0} y_{0} ∣ + ∣ x_{1} y_{1} ∣ = 3 + 8 = 11$ , while $∥ x ∥_{1} ∥ y ∥_{1} = (1 + 2) (3 + 4) = 21$ .

2.1L1step 1.2algebra

By the normwise bound of [L1] applied to the numbers of step 1.2, $∣ s_{2} - 11 ∣ \leq γ_{2} \cdot 11 \leq γ_{2} \cdot 21$ ; substituting $u = 2^{- 53}$ gives $γ_{2} = 2^{- 52} / (1 - 2^{- 52})$ , so $∣ s_{2} - 11 ∣ \leq 11 \cdot 2^{- 52} / (1 - 2^{- 52})$ , a bound of order $10^{- 15}$ .

3.1step 1.1step 2.1∎

Step 1.1 verifies the componentwise perturbation form and step 2.1 the normwise bound for this short vector pair: the computed dot product agrees with the exact dot product of slightly perturbed summands and lies within $11 γ_{2}$ of $11$ .

Depends on

The computed floating-point dot product obeys componentwise and normwise error bounds

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

6 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

David Bindel, CS 6210: Sums, Dots, and Error in Linear Systems (standard reference, not scraped)