2026/07/29 by Yuval Filmus
Computer Science · Mathematics · #cs.DM #math.CO
14 pages
arxiv created 2026/07/29 · arxiv updated 2026/07/30
Given two m-ary predicates P,Q, an n-ary polymorphism is a tuple (f1,…,fm) of functions such that x(1),…,x(n) ∈ P implies (f1(y1),…,fm(ym)) ∈ Q, where yi = (x(1)i,…,x(m)i). This generalizes the usual definition in universal algebra, in which P = Q and f1 = ⋯ = fm. In earlier work, we studied when all polymorphisms of a single predicate are "trivial": either all depend on a single coordinate (common to all of them), or they constitute a "certificate" for the predicate. We showed that it suffices to check this condition for 2-ary polymorphisms, and even for 1-ary polymorphisms, modulo an explicit list of obstructions. In this paper we generalize the first result to the P,Q setting, for a relaxed notion of certificate. We also generalize the second result in the promise setting, in which P,Q range over the same alphabets and P ⊆ Q.