§3.2, proof, Case 2, pp. 14–15 — some probability vector has wherever
ProvedSymBoolPCSP.LPRounding.case2_perturbationlinear-algebralinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be a rational matrix with for every , and let be any rational vector. Then there is a rational vector with such that satisfies
In the Alternating-Threshold case of the correctness proof, is a rational LP solution and is a second LP solution that differs from at every coordinate where is fractional.
Formalization Note The paper takes to be a rational LP solution; the statement here holds for every rational vector , which includes that case. The claim is stated directly over .
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_LPRounding_Basic open PCSPBLPAff.Symmetric
Formal statement
namespace SymBoolPCSP.LPRounding
/-- §3.2, proof, Case 2, pp. 14–15: for an `n × n` rational matrix `M` with entries in `[0, 1]`
and every diagonal entry in `{0, 1}` (`n ≥ 1`), and any rational vector `ŵ`, there is a rational
`v ∈ [0, 1]^n` with coordinate sum `1` such that `w = Mv` has `w_i ≠ ŵ_i` for every `i` with
`ŵ_i ∉ {0, 1}`. -/
theorem case2_perturbation (n : ℕ) (hn : 0 < n) (M : Fin n → Fin n → ℚ)
(hM : ∀ i j, 0 ≤ M i j ∧ M i j ≤ 1) (hdiag : ∀ i, M i i = 0 ∨ M i i = 1)
(what : Fin n → ℚ) :
∃ v : Fin n → ℚ, (∀ j, 0 ≤ v j ∧ v j ≤ 1) ∧ ∑ j, v j = 1 ∧
∀ i, what i ≠ 0 → what i ≠ 1 → ∑ j, M i j * v j ≠ what i := by sorry
end SymBoolPCSP.LPRounding
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, pp. 14–15, §3.2, proof, Case 2 (choice of v, w)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.