Lemma 7.3, core — the Schur-square relinearization has the unique solution except with probability
ProvedTwoFoldOPI.relin_unique_solution_boundLet be a finite field, let be a linear code (in the mission ), and let be fixed. For with for every , the unordered pairs determine and for any ordering of the pairs. Consider the linear relaxation of the constraints :
where is the Schur square and the coordinate-wise product. The pair always solves it, and it is the only solution exactly when no solution has .
If is uniform on , a set of size , then the relaxation has a solution with with probability at most
where is the zero set of and the shortened code. Equivalently,
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 when the solution is unique recovers the hidden codeword with probability at least .
Formalization Note. The count is Nat.card of the subtype of bad , and the probability bound is stated multiplied by . The equation is written with pointwise operations on Fin m → K, with and replaced by and , which they equal for every ordering of the pairs.
import Mathlib import Definitions.Def_TwoFoldOPI_schurFailureSum
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