QuantumComputinglib learn · inspect · formalize
Checked on this commit 4,524 public declarations commit 4e2c5b2c0be5 Build record

Shared mathematical foundations / Stored Cost Refinement

Stored Cost Refinement

Exercise LA-216

basic · boundary · train

nl bridge from inspected source. Current content-bound mathematical second pass accepted. No new Lean verification is claimed for this NL view.

Assumptions and conventions

  • The identity is materialized by an index-equality comparison per entry
  • Materialization adds the two-read-two-write surcharge per entry and per row
  • Stored constants are not free primitives; counts are exact-real, not finite-bit
  • Original derivation from inspected local source; no fresh Lean verification

Question

In the stored exact-real model the identity matrix of size N is not a primitive constant but is materialized: each of the N*N entries is produced by an exact comparison deciding whether its row and column indices are equal (returning one or zero), and the materialization adds the standard two-read-two-write surcharge per entry and per row. The proved identity cost is N*N comparisons plus (N*N + N) times the two-read-two-write surcharge. A colleague treats the stored identity as a zero-cost input when bounding a larger algorithm. Explain why this is wrong in general, work out the exact summed cost, and determine the boundary size N at which the identity genuinely costs nothing.

Hint: mathematical route

Boundary: the stored identity costs 5*N*N+4*N exact-real operations, nonzero for all N at least 1, free only at the degenerate N=0.

  1. The identity is materialized with one index-equality comparison per entry.
  2. The summed cost is N*N comparisons plus 2*(N*N+N) reads and writes, i.e. 5*N*N+4*N.
  3. Only N=0 makes every counter vanish, so the identity is nonzero at any positive size.
Reference solution

Treating the stored identity as free is wrong because it is materialized entry by entry: producing it charges N*N exact comparisons (one per entry to test index equality) and the materialization surcharge of two reads and two writes on each of the N*N entries and each of the N rows. Summing all eight counters: the comparison counter contributes N*N, and the read and write counters each contribute 2*(N*N + N), so the summed total is N*N + 4*(N*N + N) = 5*N*N + 4*N. This is strictly positive for every N at least 1, so the identity is not free at any positive size, and in a composed algorithm this term must be added, not dropped. The unique boundary at which the stored identity costs nothing is N = 0: the empty matrix has no entries and no rows, so every counter is zero (5*0 + 0 = 0). Thus the only free identity is the degenerate zero-dimensional one; for all N at least 1 the quadratic comparison and storage work is real exact-real operation cost, carrying no finite-bit runtime claim but still contributing to the overall operation count.

Assessment rubric
  1. Explain the identity is materialized with one comparison per entry plus the storage surcharge (1 weight)
  2. Compute the exact summed cost 5*N*N + 4*N (1 weight)
  3. Identify N=0 as the unique boundary where the cost vanishes, so it is nonzero for all N at least 1 (1 weight)

Graph-grounded prerequisites

These are support/source anchors, not an automatically extracted theorem-dependency proof.

Download the shared core registry

Lean view and evidence boundary

No aligned Lean view has been admitted for this native core in this textbook checkpoint. This is not a claim that the underlying mathematics lacks a formal proof. Contributions must preserve this exact target contract and split.

Read the Lean track and existing diagnostic warmups

Sources and provenance

Contract: 76c269fb3e1099ec4c7dd2670ff1c0d3da03c47df4dc10e1cbc9ccec34d9efe7

Item digest: 06ed62cc08c6f5635662d9347275c6820fe449819d095626d4b19289a2acaf7f

Graph snapshot: qcb-snapshot-ffa644f0da3031a1ce754b9a

Authored support steps: 3. This is not measured graph distance or model difficulty.