ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge 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.

Duplicate columns and explicit zeros count as stored entries

Example

Let $m = 2$ , $n = 3$ , $s = 3$ and use $r = (0, 2, 3)$ , $c = (1, 1, 0)$ , $v = (2, - 2, 0)$ . The repeated column in row $0$ cancels, and the last stored entry is an explicit zero, so the represented matrix is the zero $2$ by $3$ matrix even though $s = 3$ and $nnz (A) = 0$ . For $x = (4, 5, 6)$ , the algorithm returns $(0, 0)$ with $3$ multiplications, $3$ additions, and $2$ zero initializations.

Facts & Assumptions

Given: The displayed arrays, $x = (4, 5, 6)$ over $Q$ , and exact rational arithmetic.

[L1]

Compressed sparse row matrices with stored-entry semantics: repeated column entries are summed, explicit zero values remain stored, and $s$ counts stored entries rather than nonzero matrix entries.

[L2]

Validated compressed sparse row matrix-vector product: each stored entry contributes one product-add update to its row accumulator.

[L3]

CSR matrix-vector multiplication returns the represented product: the result equals the represented matrix-vector product in exact field arithmetic.

[L4]

CSR storage and exact matrix-vector operation counts: a valid record with $s$ stored entries uses $s$ multiplications, $s$ additions, $m$ initializations, and $2 s + m + 1$ CSR input slots.

[L5]

The rationals form a field: the rational numbers with their standard operations form a field.

[L6]

Multiplication by zero: $0 \cdot a = 0$ : in a field, multiplying zero by any element gives zero.

Verification

1.1givenL1L5algebra

The pointers $0, 2, 3$ delimit two entries in row $0$ and one in row $1$ ; all column indices lie in ${0, 1, 2}$ . Row $0$ contributes $2 + (- 2) = 0$ to column $1$ , and row $1$ contributes $0$ to column $0$ . Thus every matrix entry is zero, while all three values are stored.

2.1L2L3L5L6step 1.1algebra

The products in row $0$ are $2 (5)$ and $(- 2) (5)$ , which sum to $0$ ; the row $1$ product is $0 (4) = 0$ . By [L3], the algorithm returns $(0, 0)$ .

3.1givenL1L4algebra∎

There are three stored entries and two rows, so [L4] gives $3$ multiplications, $3$ additions, $2$ initializations, and $2 (3) + 2 + 1 = 9$ CSR input slots. This noncanonical record has $s = 3 \neq nnz (A) = 0$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

15 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

Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., Chapter 3 §3.4, printed pp. 92–94 (standard reference, not scraped)