A Whole Table Row in One Natural Number: Kernel-Checked Dynamic Programming with a Proved Width Bound
A proof assistant checks a computation by reducing it, so the data structure a verified algorithm is written over decides the cost of being checked, not only the cost of running. This paper measures that cost for one task with a locked specification: counting the partitions of n in Lean 4, where the answer must come with a machine-checked proof that holds for every n. Three designs compute the same recurrence. Evaluating the specification as written performs 672,182 primitive steps at n = 36, because every path to a table cell re-derives it.