Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The four-variable parity language Λ₄

Definition
StabilityDichotomies_Solvability_Supplement_FourParity

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

average-sensitivityboolean-cspconstraint-satisfactionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

For b ∈ {0,1}, let R_b be the relation of arity four given by

Rb={x∈{0,1}4:x1⊕x2⊕x3⊕x4=b},Λ4={R0,R1}.R_b=\{x\in\{0,1\}^4:x_1\oplus x_2\oplus x_3\oplus x_4=b\},\qquad\Lambda_4=\{R_0,R_1\}.Rb​={x∈{0,1}4:x1​⊕x2​⊕x3​⊕x4​=b},Λ4​={R0​,R1​}.

Here ⊕ is Boolean exclusive-or. Both relations are nonempty: the tuple (b,0,0,0) belongs to R_b. The language has both parity relations and uses the existing unrestricted constraint model. Its four argument positions can receive repeated variables; for example R_b(u,v,u,u) is the equation u ⊕ v = b.

This is the fixed source language for Proposition 4.11 and the approximation lower branch. Formalization Note The four positions are numbered 0 through 3 in Lean, and neither relation depends on any algorithm or code family.

Definition code
import Definitions.Def_StabilityDichotomies_Solvability_Model

noncomputable section
open scoped Classical

namespace StabilityDichotomies.Solvability.Supplement

/-- The XOR of the four argument positions, which remain distinct positions even under substitution. -/
def fourParity (x : Fin 4 → Bool) : Bool :=
  Bool.xor (Bool.xor (Bool.xor (x 0) (x 1)) (x 2)) (x 3)

/-- Section 4.3.1, p.24: R_b consists of all four-bit tuples of parity b. -/
def parityRelation (b : Bool) : Relation where
  arity := 4
  arity_pos := by decide
  tuples := Finset.univ.filter (fun x : Fin 4 → Bool => fourParity x = b)
  tuples_nonempty := by
    refine ⟨(fun i => if i = 0 then b else false), ?_⟩
    simp [fourParity]

/-- The entire language Λ₄ = {R₀,R₁}, with unrestricted scopes in the base CSP model. -/
def parityLanguage : Language where
  relations := {parityRelation false, parityRelation true}
  relations_nonempty := by simp

end StabilityDichotomies.Solvability.Supplement
Source
Chunyang Wang, Yuichi Yoshida, Stability Dichotomies for Boolean Constraint Satisfaction Problems, STOC 2027 submission #535 (October 2026), canonical source.pdf, SHA-256 9eeb0875db685945a8b4c78bc4d30bfdbf3289a943d06f464836530d0eb22467. p.24, Section 4.3.1, parity-relation display immediately before Proposition 4.11.

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