Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Polylogarithmic overhead: K⌈log⁡2L⌉≤KLlog⁡2KK^{\lceil \log_2 L\rceil} \le K L^{\log_2 K}K⌈log2​L⌉≤KLlog2​K

Proved
KLZ97.overhead_polylog

by LG · Sep 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

analysisquantum-error-correction

The overhead estimate of Section II.F. With KKK a bound on the resources one encoded gate consumes at the level below, a concatenation depth of h=⌈log⁡2L⌉h = \lceil \log_2 L \rceilh=⌈log2​L⌉ levels costs KhK^{h}Kh resources per computational gate, and this is at most

K⋅Llog⁡2K.K \cdot L^{\log_2 K}.K⋅Llog2​K.

Applied with L=log⁡1/(fp)(n/q)L = \log_{1/(fp)}(n/q)L=log1/(fp)​(n/q) this is the paper's conclusion that the overhead is polylogarithmic in nnn and 1/q1/q1/q, with exponent log⁡2K\log_2 Klog2​K.

Preamble
import Mathlib
import Definitions.Def_KLZ97_model
Formal statement
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 KLZ97
Source
Knill, Laflamme, Zurek, Resilient Quantum Computation: Error Models and Thresholds, arXiv:quant-ph/9702058v1, https://arxiv.org/abs/quant-ph/9702058, Section II.F (Overheads), p. 9
Read-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 KKK and LLL be real numbers with K≥2K \ge 2K≥2 and L≥1L \ge 1L≥1. Let ⌈log⁡2L⌉+\lceil \log_2 L \rceil^{+}⌈log2​L⌉+ denote the least natural number greater than or equal to log⁡2L\log_2 Llog2​L (a natural-number ceiling, so it is 000 when log⁡2L≤0\log_2 L \le 0log2​L≤0, which here happens only for L=1L = 1L=1). The claim is

K ⌈log⁡2L⌉+  ≤  K⋅L log⁡2K.K^{\,\lceil \log_2 L \rceil^{+}} \;\le\; K \cdot L^{\,\log_2 K} .K⌈log2​L⌉+≤K⋅Llog2​K.

On the left the exponent is a natural number and the power is an ordinary iterated product. On the right the exponent log⁡2K=log⁡K/log⁡2\log_2 K = \log K / \log 2log2​K=logK/log2 is a real number and the power is the real power Lx=exp⁡(xlog⁡L)L^{x} = \exp(x \log L)Lx=exp(xlogL), which is well defined since L≥1>0L \ge 1 > 0L≥1>0. Both log⁡2L\log_2 Llog2​L and log⁡2K\log_2 Klog2​K are non-negative under the hypotheses, the latter being at least 111.

At L=1L = 1L=1 the two sides are K0=1K^{0} = 1K0=1 and K⋅1=KK \cdot 1 = KK⋅1=K. The inequality is non-strict, and nothing is asserted for K<2K < 2K<2 or for L<1L < 1L<1.

Human review
  • Endorsed by Shuze Chen · Sep 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by LG · Sep 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me