Sufficient number of concatenation levels:
ProvedKLZ97.levels_sufficeThe paper's criterion for how many levels of concatenation are needed. For a computation of gates and a desired failure probability , the number of levels is sufficient provided
and then the computation's failure probability bound is smaller than . This is the inequality of Section II.F, together with the condition derived from it.
import Mathlib import Definitions.Def_KLZ97_model
namespace KLZ97
theorem levels_suffice (f p q : ℝ) (n : ℕ) (h : ℕ) (hp : 0 < f * p) (hfp : f * p < 1)
(hq : 0 < q) (hqn : q < n)
(hlevels : Real.log ((n : ℝ) / q) / Real.log (1 / (f * p)) < (2 : ℝ) ^ h) :
(n : ℝ) * (f * p) ^ (2 ^ h) < q := 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 , , be real numbers, and , natural numbers. Write for the product. Assume:
- and ;
- and (so in particular );
where is the natural logarithm, is a real quotient, and on the right is a real power of .
The conclusion is the strict inequality
where the exponent is a natural number.
Note that the hypotheses constrain only the product , not and individually: they are compatible with and both negative. Under them and , so the displayed quotient is a positive real and the hypothesis on is a genuine lower bound on ; at it requires that quotient to be less than . The conclusion is strict, and the statement asserts nothing when the hypothesis on fails, nor for , or .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.