---
tag: XS41Y1Q01M
kind: statement
role: theorem
name: Cyclic term theorem
msc: [08B05, 08A70]
uses: [QEAMRNRJJD, N9M2N27END, PKD440G2XW, 9FS1JFZSX4, 01826KMG2H]
about: [QEAMRNRJJD]
sources:
  - url: https://en.wikipedia.org/wiki/Constraint_satisfaction_problem
---

## Statement

Let $A$ be a finite [[idempotent|9FS1JFZSX4]] algebra, meaning that every basic operation $f$ of $A$ satisfies $f(x, \dots, x) = x$.
A *cyclic term* of $A$ of arity $n \ge 2$ is a [[term|N9M2N27END]] $c(x_1, \dots, x_n)$ such that $A$ satisfies the [[identity|PKD440G2XW]] $c(x_1, x_2, \dots, x_n) \approx c(x_2, \dots, x_n, x_1)$.
Then the following are equivalent:

1. $A$ has a [[Taylor term|QEAMRNRJJD]].
2. $A$ has a cyclic term.
3. $A$ has a cyclic term of arity $p$ for every [[prime number|01826KMG2H]] $p > \abs{A}$.

## Remarks

The theorem is due to Libor Barto and Marcin Kozik.
A cyclic term is idempotent here because $A$ is idempotent.
An idempotent cyclic term $c$ of arity $n$ is a Taylor term.
For each place $i$, put $y$ in place $i$ and $x$ elsewhere.
The cyclic identity equates this with $c$ having $y$ in the previous place and $x$ elsewhere, and the two sides differ in place $i$.
So the real content is that a Taylor term forces cyclic terms; the proof uses the theory of absorbing subalgebras.
Example: a finite semilattice has the cyclic term $x_1 \wedge \cdots \wedge x_n$ for every $n$.
Example: the idempotent algebra $(\Z_3; x - y + z)$ has as term operations the affine combinations $\sum a_i x_i$ with $\sum a_i \equiv 1 \pmod 3$.
For the prime $p = 5 > 3$, the operation $2(x_1 + \cdots + x_5)$ is such a combination, since $2 \cdot 5 = 10 \equiv 1$, and it is cyclic.

## Explanations

### L1 human

A cyclic term is an operation that does not change when its inputs are rotated, like a symmetric way of combining $n$ items arranged in a circle.
The theorem says that, for finite idempotent algebras, such an operation exists as soon as the algebra has any Taylor term at all.
Moreover, one can choose the number of inputs to be any prime larger than the size of the algebra.

### L2 human

Cyclic terms give a clean test for tractability in the algebraic approach to constraint satisfaction.
A finite core structure has a polynomial-time constraint satisfaction problem exactly when its idempotent polymorphisms include a cyclic operation, by this theorem together with the [[CSP dichotomy theorem|ZA4YXJ9T1P]].
The theorem fits with other characterizations of Taylor algebras by a single identity, such as the [[Siggers term|JYW1H3J8SX]].
Unlike the Siggers identity, the cyclic identity has an arity that may be chosen freely among large primes, which is useful in arguments that combine several terms.