Lemma 7.3, second bound — E(D)≤qdimD+dimD∗2/(q−1)dist(D)
ProvedTwoFoldOPI.schurFailureSum_le_dist_boundby sragavan · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)
coding-theoryoptimal-polynomial-intersectionschur-product-codes
Let K=Fq be a finite field, M≥0, and let D⊆FqM be any linear code (in the mission D=C⊥). For c∈FqM write wt(c) for its Hamming weight and Z(c)={i:ci=0} for its zero set; for a code W and S⊆[M] let W[S]={w∈W:wi=0 ∀i∈S} be the shortened code, and let D∗2 be the Schur square of D (the span of all coordinate-wise products u⊙v, u,v∈D). Let dist(D) be the least weight of a nonzero word of D. Then the ambiguity sum of Lemma 7.3 satisfies
E(D)=c∈D∖{0}∑(q−1)wt(c)qdim(D∗2)[Z(c)] ≤ (q−1)dist(D)qdimD+dimD∗2.
This is the second inequality of Lemma 7.3 (equivalently, after multiplying by 2∣D∣=2qdimD, the second inequality of Theorem 7.4): it replaces the refined failure sum, which depends on the shortened Schur squares, by a bound that only involves the distance of D and the dimensions of D and of its Schur square.
Formalization Note. q=∣K∣, dim is Module.finrank K, and dist(D) is minDist D, which equals 0 for D={0} by the convention sInf ∅ = 0. The inequality is stated for every linear code; for D={0} the left side is the empty sum 0 and the right side is qdimD∗2≥0, so no hypothesis D={0} is needed. The case q=2 is allowed.
Preamble
import Mathlib
import Definitions.Def_TwoFoldOPI_schurFailureSum
import Definitions.Def_TwoFoldOPI_minDist
Formal statement
namespace TwoFoldOPI
theorem schurFailureSum_le_dist_bound {K : Type*} [Field K] [Fintype K] [DecidableEq K] {M : ℕ}
(D : Submodule K (Fin M → K)) :
schurFailureSum D ≤
(Fintype.card K : ℝ) ^ (Module.finrank K D + Module.finrank K (schurSquare D)) /
((Fintype.card K : ℝ) - 1) ^ minDist D := by sorry
end TwoFoldOPI
Source
Ragavan, Shutty, Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability, arXiv:2610.00502 (version held), §7.2, Lemma 7.3, p.39 (displayed second inequality) and its proof, p.40: "Bounding each of the fewer than q^{dim C⊥} terms by q^{dim((C⊥)^{∗2})}(q−1)^{−dist(C⊥)} gives the second bound"; also the second inequality of Theorem 7.4, p.40.
View graph