Mal'cev clones over a three-element set up to minor-equivalence

Résumé Technique : Les Clones de Mal'cev sur un Ensemble à Trois Éléments Jusqu'à l'Équivalence de Minorité

Énoncé du Problème
L'article traite de la classification des clones sur un ensemble fini $A$ avec $|A|=3$, en se concentrant spécifiquement sur les clones de Mal'cev. Un clone est un ensemble d'opérations fermé par composition et contenant toutes les projections. Alors que le treillis de tous les clones sur un ensemble à deux éléments ($L_2$) est dénombrable et entièrement classifié (la classification de Post), le treillis $L_3$ sur un ensemble à trois éléments est indénombrable et ne possède pas de description complète.

Les auteurs étudient ces clones non pas sous l'ordre d'inclusion standard, mais jusqu'à l'équivalence de minorité (notée $\equiv_m$). Deux clones sont équivalents par minorité s'il existe des homomorphismes de minions (applications préservant les minors/identités de hauteur 1) dans les deux sens. Cette relation d'équivalence correspond à la notion de pp-constructibilité dans les problèmes de satisfaction de contraintes (CSP). L'objectif spécifique est de classifier tous les clones de Mal'cev (ceux contenant une opération ternaire $m$ satisfaisant $m(y, x, x) \approx m(x, x, y) \approx y$) sur un ensemble à trois éléments modulo cette équivalence.

Méthodologie
Les auteurs emploient une combinaison d'algèbre universelle, de théorie du commutateur et de l'approche algébrique des CSP.

1. Bases Relationnelles et Définitions pp : L'étude repose sur la connexion de Galois entre opérations et relations. Un clone est déterminé par ses relations invariantes. Les auteurs utilisent le fait que pour les algèbres de Mal'cev, les relations invariantes possèdent la propriété du parallélogramme.
2. Théorie du Commutateur : La section 3 passe en revue la théorie du commutateur pour les algèbres de Mal'cev, spécifiquement les concepts de centralisateurs et de congruences abéliennes. Cela est utilisé pour analyser les relations critiques (celles qui sont $\wedge$-irréductibles dans le treillis des sous-univers).
3. Preuve Alternative du Résultat de Bulatov : L'article fournit d'abord une preuve simplifiée d'un résultat de Bulatov [19], montrant que tout clone de Mal'cev sur un ensemble à trois éléments possède une base relationnelle composée de relations d'arité au plus 4. Cette preuve utilise la théorie du commutateur plutôt que la théorie des congruence tame utilisée dans le travail original.
4. Analyse de Cas via les Propriétés Structurelles : La classification procède par l'analyse des propriétés structurelles des algèbres sous-jacentes :
   • Cardinalité : Distinction entre les algèbres sur des ensembles de taille $\le 2$ et de taille 3.
   • Auto-dualité : Vérification si le clone préserve la permutation cyclique $\phi$.
   • Termes de Majorité : Détermination si le clone contient une opération de majorité (ce qui implique une base relationnelle binaire).
   • Structure de Congruence : Analyse de la présence de monolithes non triviaux (congruences minimales non triviales) et de savoir s'ils sont abéliens.
5. pp-Constructibilité et Homomorphismes de Minion : Pour établir l'équivalence ou l'inégalité entre les clones, les auteurs construisent des puissances-pp et des homomorphismes explicites entre structures relationnelles. Ils utilisent également des conditions de minorité (identités de hauteur 1) pour prouver que certains clones ne peuvent pas être projetés vers d'autres (par exemple, l'existence d'une quasi-majorité vs son absence).

Contributions Clés et Résultats

1. Preuve Simplifiée du Théorème de la Base de Bulatov : Les auteurs fournissent une preuve alternative que tout clone de Mal'cev sur un ensemble à trois éléments est fini par des relations d'arité au plus 4. Cette preuve évite la théorie des congruence tame au profit de la théorie du commutateur.

2. Classification de 10 Classes d'Équivalence : Le résultat principal (Théorème 8.2) établit qu'il existe exactement 10 classes d'équivalence de minorité de clones de Mal'cev sur un ensemble à trois éléments. Ces classes sont représentées par les clones suivants (ou leurs équivalents par minorité) :

   • $T$ : Le clone sur un ensemble à 1 élément.
   • $I_2$ : Le clone de toutes les opérations sur $\{0, 1\}$.
   • $C_2$ : Le clone de polymorphisme de la structure $C_2 = (\{0, 1\}, \neq, \{0\}, \{1\})$.
   • $Z_2$ : Le clone des opérations affines idempotentes modulo 2.
   • $C_3$ : Le clone de polymorphisme du digraphe cyclique avec constantes.
   • $D$ : Un clone préservant une bijection partielle spécifique et des constantes.
   • $L_2$ : Un clone préservant une permutation cyclique, une transposition et une relation spécifique d'arité 4.
   • $Z_3$ : Le clone des opérations affines idempotentes modulo 3.
   • $M_1$ : Un clone préservant une transposition, une congruence et des constantes.
   • $M_0$ : Un clone préservant une transposition, le complément d'une congruence et des constantes.

3. Structure d'Ordre (Diagramme de Hasse) : L'article décrit entièrement l'ordre partiel induit par les homomorphismes de minion ($\le_m$) parmi ces 10 classes. La structure est illustrée dans la Figure 3. Notamment :

   • $L_2$ et $Z_3$ sont des atomes (éléments minimaux non triviaux) dans le poset des clones de Mal'cev.
   • $M_0$ et $M_1$ forment une chaîne sous $C_2$.
   • Le papier identifie explicitement les conditions de minorité (telles que l'existence d'opérations $n$-cycliques, de quasi-minorité ou de quasi-majorité) qui séparent ces classes.

4. Gestion des Sous-cas :

   • Clones Auto-duaux : L'article récupère la classification des clones de Mal'cev auto-duaux (ceux préservant $\phi$) de [15], identifiant 4 classes ($Z_3, L_2, D, C_3$).
   • Clones de Majorité : Pour les clones possédant un terme de majorité, les auteurs distinguent les algèbres simples de celles avec un monolithe non trivial, les réduisant aux classes équivalentes à $C_2, I_2, M_1$ ou $M_0$.
   • Non-Majorité, Non-Auto-Dual : Les auteurs prouvent que tout clone de Mal'cev idempotent sans terme de majorité et ne préservant pas $\phi$ est équivalent par minorité à $Z_2$.

Signification et Revendications
L'article affirme que cette classification représente une « étape significative vers une description complète de $P_3$ » (le poset des classes d'équivalence de minorité de clones sur 3 éléments).

• Complétude pour les Clones de Mal'cev : Il fournit la première classification complète des clones de Mal'cev jusqu'à l'équivalence de minorité pour $n=3$.
• Réduction du Problème Général : Les auteurs citent [41] pour noter que chaque élément de $P_{fin}$ (et donc de $P_3$) qui ne possède pas une opération quasi-Mal'cev se situe en dessous de la classe $B_2$. Par conséquent, les auteurs soutiennent que leur résultat, combiné à une description du sous-ensemble de $B_2$, suffirait à compléter la classification de $P_3$.
• Contribution Méthodologique : Le papier démontre l'utilité de la théorie du commutateur et des constructions pp pour analyser les structures de clones, offrant une approche plus fluide des résultats antérieurs plus complexes de Bulatov.

Le papier ne prétend pas résoudre la classification générale de $L_3$ ou $P_3$, reconnaissant que le sous-ensemble de $B_2$ reste un problème ouvert et difficile. Il présente son travail comme une composante nécessaire dans l'effort plus large de compréhension du treillis d'interprétabilité des algèbres finies et de la complexité des CSP.