ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pass

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 small residual at an ill-conditioned basis

Example

Let $δ = 2^{- 27}$ , $A = diag (1, δ)$ , $b = (1, δ)^{T}$ , and $c = (1, 1)^{T}$ . The exact primal solution is $x^{*} = (1, 1)$ and the dual vector $y = (1, δ^{- 1})$ satisfies $A^{T} y = c$ . Audit the finite binary candidate $\hat{x} = (1, 1 + δ)$ .

Facts & Assumptions

Given: The exact dyadic LP data and candidate in the Example.

[F1]

Exact residual audit of finite-precision simplex candidates: Otherwise use exact integer/rational arithmetic to compute $r_{p} = A \hat{x} - b$ , $r_{d} = c - A^{T} \hat{y}$ , and $g = c^{T} \hat{x} - b^{T} \hat{y}$ .

[F2]

Primal-dual residual gap bound for a simplex candidate: $∣ g ∣ \leq ∥ x ∥_{1} ∥ r_{d} ∥_{\infty} + ∥ y ∥_{1} ∥ r_{p} ∥_{\infty}$ .

Verification

1.1givenalgebra

The basis matrix has $∥ A ∥_{2} = 1$ and $∥ A^{- 1} ∥_{2} = δ^{- 1} = 2^{27}$ , so its 2-norm condition number is $2^{27}$ . The exact solution is $(1, 1)$ , while the candidate has forward error $\hat{x} - x^{*} = (0, δ)$ .

2.1F1step 1.1algebra

Exact multiplication gives $r_{p} = (0, δ^{2}) = (0, 2^{- 54})$ , $r_{d} = (0, 0)$ , and $g = δ = 2^{- 27}$ . Thus the residual norm is $2^{- 54}$ although the absolute forward error is $2^{- 27}$ , larger by the condition factor.

3.1F2step 2.1algebra∎

Here $∥ \hat{x} ∥_{1} = 2 + δ$ , $∥ y ∥_{1} = 1 + δ^{- 1}$ , so [F2] gives $∣ g ∣ \leq (1 + δ^{- 1}) δ^{2} = δ + δ^{2}$ . The candidate is not exactly primal feasible and has a positive gap; the small residual alone therefore does not certify exact optimality or infeasibility.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

3 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, residual-based bounds (standard reference, not scraped)
Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization, §3.3 (standard reference, not scraped)