§3.2, proof, Case 1, p. 14 — some probability vector has for all
ProvedSymBoolPCSP.LPRounding.case1_claimlinear-algebralinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let be a rational matrix whose diagonal entries satisfy for every . Then there is a rational vector with such that
In the Majority case of the correctness proof, is the matrix whose -th column is an LP solution with -th coordinate in , and is then an LP solution with no coordinate equal to , ready to be rounded.
Formalization Note The paper first finds a real and then perturbs it to a rational one; this item states the combined claim 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 1, p. 14: for an `n × n` rational matrix `M` with entries in `[0, 1]` and
every diagonal entry in `{0, 1}` (`n ≥ 1`), there is a rational `v ∈ [0, 1]^n` with coordinate
sum `1` such that `(Mv)_i ≠ 1/2` for all `i`. -/
theorem case1_claim (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) :
∃ v : Fin n → ℚ, (∀ j, 0 ≤ v j ∧ v j ≤ 1) ∧ ∑ j, v j = 1 ∧
∀ i, ∑ j, M i j * v j ≠ 1 / 2 := by sorry
end SymBoolPCSP.LPRounding
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 14, §3.2, proof, Case 1 (claim and the perturbation to rational v′)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.