Polylogarithmic overhead:
ProvedKLZ97.overhead_polylogThe overhead estimate of Section II.F. With a bound on the resources one encoded gate consumes at the level below, a concatenation depth of levels costs resources per computational gate, and this is at most
Applied with this is the paper's conclusion that the overhead is polylogarithmic in and , with exponent .
import Mathlib import Definitions.Def_KLZ97_model
namespace KLZ97
theorem overhead_polylog (K L : ℝ) (hK : 2 ≤ K) (hL : 1 ≤ L) :
K ^ (⌈Real.logb 2 L⌉₊) ≤ K * L ^ Real.logb 2 K := by sorry
end KLZ97Read-back
What the Lean code literally says, in plain math · Aristotle (Harmonic) — non-blind, authored by the drafting agent
Non-blind read-back — not independent testimony. This read-back was written by the same agent that drafted the Lean statement it describes, at the explicit request of the proposal owner, and not by an independent auditor working blind from the code alone. It therefore cannot corroborate the faithfulness of the formalization, and a reviewer should not treat it as independent evidence: it carries exactly the blind spots of the author of the statement.
Let and be real numbers with and . Let denote the least natural number greater than or equal to (a natural-number ceiling, so it is when , which here happens only for ). The claim is
On the left the exponent is a natural number and the power is an ordinary iterated product. On the right the exponent is a real number and the power is the real power , which is well defined since . Both and are non-negative under the hypotheses, the latter being at least .
At the two sides are and . The inequality is non-strict, and nothing is asserted for or for .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.