Lemma 8.8 — the operation t is cyclic
ProvedAlgebraicPCSP.OneInThree.lemma_8_8cyclic-operationsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphismspromise-csp
Let be a cyclic operation and let be the -ary operation
Then is cyclic as an operation of its arguments in the order :
Cyclicity of lets the proof replace a tuple by any cyclic shift of it without changing , which is how covers are built from line segments in Lemma 8.9.
Formalization Note Stated for every and every type ; only cyclicity of is assumed. The argument tuple is read into a matrix row-major via finProdFinEquiv.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_AlgebraicPCSP_OneInThree_Structures import Definitions.Def_AlgebraicPCSP_OneInThree_Matrices
Formal statement
namespace AlgebraicPCSP.OneInThree
/-- Lemma 8.8 (p. 54): if `s` is cyclic, then the `p²`-ary operation `t`, taken on its
arguments in row-major order `(x₁₁, x₁₂, …, x₁ₚ, x₂₁, …, x_pp)`, is cyclic. -/
theorem lemma_8_8 {D : Type} {p : ℕ} (s : (Fin p → D) → D) (hcyc : IsCyclic s) :
IsCyclic (tFlat s) := by sorry
end AlgebraicPCSP.OneInThree
Source
L. Barto, J. Bulín, A. Krokhin, J. Opršal, Algebraic approach to promise constraint satisfaction, arXiv:1811.00970v3, p. 54, Lemma 8.8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.