Lemma 10 — doubly exponential decay of the non-sparse probability
ProvedABOThreshold.sparse_prob_geThis is Lemma 10 of the paper. Let be the maximal number of locations in a rectangle, the tolerance of a rectangle, and let the error rate satisfy and .
Then there exists such that for every recursion level the probability that the faults in an -rectangle form an -sparse set obeys
Because the exponent grows geometrically, the failure probability decays doubly exponentially in the number of levels of concatenation: this is the precise sense in which a constant error rate below the threshold can be driven down to an arbitrarily small effective error rate at polylogarithmic cost.
Formalization Note The paper asserts the strict inequality ; at both sides equal , so the statement is formalized with .
import Definitions.Def_ABOThreshold_model
namespace ABOThreshold
theorem sparse_prob_ge (A k : ℕ) (hk : 1 ≤ k) (η : ℝ) (hη : 0 < η) (hη1 : η < 1)
(hlt : η < thresholdProb A k) :
∃ δ : ℝ, 0 < δ ∧ ∀ r : ℕ, 1 - η ^ ((1 + δ) ^ r) ≤ sparseProb A k η r := by sorry
end ABOThresholdRead-back
What the Lean code literally says, in plain math · non-blind self-audit by the drafting agent (Aristotle, Harmonic)
Non-blind read-back — not independent testimony. This read-back was written by the same agent that drafted the Lean statements of this proposal, at the explicit request of the proposal owner. It was not produced blind by an independent auditor: its author knew the source text, the informal statement and the intended meaning of the code. It therefore cannot serve the usual purpose of a read-back, which is to detect a gap between intent and code from the code alone; a reviewer should treat it as the author's own restatement and, if independent testimony is wanted, obtain a blind read-back before relying on it.
Let and be natural numbers with , and let be a real number with and
the right-hand side being a real power of the nonnegative real base (the binomial coefficient cast to the reals, hence when , in which case the hypothesis cannot be met).
The conclusion asserts the existence of a real such that for every natural number ,
where is a natural-number power of the real number , the outer exponentiation is a real power of the positive base , and is the sum of the weights of the level- fault patterns that satisfy the recursive sparseness predicate (fault-free at level ; at level , at most of the sub-patterns failing sparseness), the weight of a pattern being the product over its locations of at faulty and at clean locations.
The single is required to work uniformly for all ; the inequality is non-strict; and the case is included, where it reads .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.