Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 7.3, core — the Schur-square relinearization has the unique solution v=cv=cv=c except with probability ≤E\le E≤E

Proved
TwoFoldOPI.relin_unique_solution_bound

by sragavan · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theoryoptimal-polynomial-intersectionrelinearizationschur-product-codes

Let Fq\mathbb F_qFq​ be a finite field, let D⊆FqmD\subseteq\mathbb F_q^mD⊆Fqm​ be a linear code (in the mission D=C⊥D=C^\perpD=C⊥), and let c∈Dc\in Dc∈D be fixed. For c′∈Fqmc'\in\mathbb F_q^mc′∈Fqm​ with ci′≠cic'_i\neq c_ici′​=ci​ for every iii, the unordered pairs {ci,ci′}\{c_i,c'_i\}{ci​,ci′​} determine a+a′=c+c′a+a'=c+c'a+a′=c+c′ and a⊙a′=c⊙c′a\odot a'=c\odot c'a⊙a′=c⊙c′ for any ordering (ai,ai′)(a_i,a'_i)(ai​,ai′​) of the pairs. Consider the linear relaxation of the constraints (c−a)⊙(c−a′)=0(c-a)\odot(c-a')=0(c−a)⊙(c−a′)=0:

w−(c+c′)⊙v+c⊙c′=0,v∈D,w∈D∗2,w-(c+c')\odot v+c\odot c'=0,\qquad v\in D,\quad w\in D^{*2},w−(c+c′)⊙v+c⊙c′=0,v∈D,w∈D∗2,

where D∗2D^{*2}D∗2 is the Schur square and ⊙\odot⊙ the coordinate-wise product. The pair (v,w)=(c,c⊙c)(v,w)=(c,c\odot c)(v,w)=(c,c⊙c) always solves it, and it is the only solution exactly when no solution has v≠cv\neq cv=c.

If c′c'c′ is uniform on ∏i(Fq∖{ci})\prod_i(\mathbb F_q\setminus\{c_i\})∏i​(Fq​∖{ci​}), a set of size (q−1)m(q-1)^m(q−1)m, then the relaxation has a solution with v≠cv\ne cv=c with probability at most

E(D)=∑d∈D∖{0}qdim⁡(D∗2)[Z(d)](q−1)wt(d),E(D)=\sum_{d\in D\setminus\{0\}}\frac{q^{\dim (D^{*2})[Z(d)]}}{(q-1)^{\mathrm{wt}(d)}},E(D)=d∈D∖{0}∑​(q−1)wt(d)qdim(D∗2)[Z(d)]​,

where Z(d)Z(d)Z(d) is the zero set of ddd and W[S]W[S]W[S] the shortened code. Equivalently,

#{c′:ci′≠ci ∀i, ∃ (v,w) solving the relaxation with v≠c} ≤ E(D) (q−1)m.\#\{c' : c'_i\neq c_i\ \forall i,\ \exists\,(v,w)\text{ solving the relaxation with }v\neq c\}\ \le\ E(D)\,(q-1)^m .#{c′:ci′​=ci​ ∀i, ∃(v,w) solving the relaxation with v=c} ≤ E(D)(q−1)m.

This is the probabilistic heart of Lemma 7.3, stated independently of any machine model: an algorithm that solves the relaxation by Gaussian elimination and outputs vvv when the solution is unique recovers the hidden codeword ccc with probability at least 1−E(D)1-E(D)1−E(D).

Formalization Note. The count is Nat.card of the subtype of bad c′c'c′, and the probability bound is stated multiplied by (q−1)m(q-1)^m(q−1)m. The equation is written with pointwise operations on Fin m → K, with a+a′a+a'a+a′ and a⊙a′a\odot a'a⊙a′ replaced by c+c′c+c'c+c′ and c⊙c′c\odot c'c⊙c′, which they equal for every ordering of the pairs.

Preamble
import Mathlib
import Definitions.Def_TwoFoldOPI_schurFailureSum
Formal statement
namespace TwoFoldOPI

theorem relin_unique_solution_bound {K : Type*} [Field K] [Fintype K] [DecidableEq K] {m : ℕ}
    (D : Submodule K (Fin m → K)) (c : Fin m → K) (hc : c ∈ D) :
    (Nat.card {c' : Fin m → K // (∀ i, c' i ≠ c i) ∧
        ∃ v ∈ D, ∃ w ∈ schurSquare D, v ≠ c ∧ w - (c + c') * v + c * c' = 0} : ℝ) ≤
      schurFailureSum D * ((Fintype.card K : ℝ) - 1) ^ m := 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, and its proof, pp.39–40 (the relaxation w − (a+a′)⊙v + a⊙a′ = 0, Eq. (11), and the union bound over Δv ∈ C⊥∖{0}, Δw ∈ (C⊥)^{∗2}[Z(Δv)]).

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