Cyclic terms via cyclic relations
ProvedBKAbsorption.cyclic_iff_subpowerabsorptionconstraint-satisfactioncyclic-termsmodel-theorytaylor-varietyuniversal-algebra
is a signature without relation symbols and a finite idempotent algebra ( for every basic operation); . has a -ary cyclic term operation (an idempotent term operation with ) iff every nonempty cyclic subuniverse of (closed under ) contains a constant tuple .
Preamble
import Definitions.Def_BKAbsorption_defs universe u v w w' open FirstOrder FirstOrder.Language
Formal statement
namespace BKAbsorption
variable {L : FirstOrder.Language.{u, v}} [L.IsAlgebraic]
/-- Barto–Kozik, Lemma 4.4 (from Barto–Kozik–Maróti–Niven). For a finite idempotent algebra `A`
and `k ≥ 2` the following are equivalent: `A` has a `k`-ary cyclic term operation; every
nonempty cyclic subuniverse of `A^k` contains a constant tuple. -/
theorem cyclic_iff_subpower {A : Type w} [L.Structure A] [Finite A] (hid : IsIdempotent L A)
(k : ℕ) (hk : 2 ≤ k) :
HasCyclicTermOp L A k ↔
∀ R : Set (Fin k → A), R.Nonempty → IsSubpower L R → IsCyclicRel R →
∃ a : A, (fun _ => a) ∈ R := by sorry
end BKAbsorptionSource
L. Barto, M. Kozik, Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem, Logical Methods in Computer Science 8(1:07) 2012, https://doi.org/10.2168/LMCS-8(1:7)2012 (arXiv:1201.0557), Lemma 4.4
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be a finite algebra in which every basic operation is idempotent, and let . Then the following are equivalent:
- There is a -ary term with for all and
- Every nonempty that is closed under coordinatewise basic operations and closed under the cyclic shift contains a constant tuple .
No Taylor hypothesis is assumed.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.