Varieties with few subalgebras of powers

Berman, Joel; Idziak, Paweł; Marković, Petar; McKenzie, Ralph; Valeriote, Matthew; Willard, Ross

doi:10.1090/S0002-9947-09-04874-0

Varieties with few subalgebras of powers
HTML articles powered by AMS MathViewer

by Joel Berman, Paweł Idziak, Petar Marković, Ralph McKenzie, Matthew Valeriote and Ross Willard PDF

Trans. Amer. Math. Soc. 362 (2010), 1445-1473 Request permission

Abstract:

The Constraint Satisfaction Problem Dichotomy Conjecture of Feder and Vardi (1999) has in the last 10 years been profitably reformulated as a conjecture about the set $\sf {SP}_\textsf {fin}(\mathbf {A})$ of subalgebras of finite Cartesian powers of a finite universal algebra $\mathbf {A}$. One particular strategy, advanced by Dalmau in his doctoral thesis (2000), has confirmed the conjecture for a certain class of finite algebras $\mathbf {A}$ which, among other things, have the property that the number of subalgebras of $\mathbf {A}^n$ is bounded by an exponential polynomial. In this paper we characterize the finite algebras $\mathbf {A}$ with this property, which we call having few subpowers, and develop a representation theory for the subpowers of algebras having few subpowers. Our characterization shows that algebras having few subpowers are the finite members of a newly discovered and surprisingly robust Maltsev class defined by the existence of a special term we call an edge term. We also prove some tight connections between the asymptotic behavior of the number of subalgebras of $\mathbf {A}^n$ and some related functions on the one hand, and some standard algebraic properties of $\mathbf {A}$ on the other hand. The theory developed here was applied to the Constraint Satisfaction Problem Dichotomy Conjecture, completing Dalmau’s strategy.

References

Kirby A. Baker and Alden F. Pixley, Polynomial interpolation and the Chinese remainder theorem for algebraic systems, Math. Z. 143 (1975), no. 2, 165–174. MR 371782, DOI 10.1007/BF01187059
Joel Berman and PawełM. Idziak, Generative complexity in algebra, Mem. Amer. Math. Soc. 175 (2005), no. 828, viii+159. MR 2130585, DOI 10.1090/memo/0828
Andrei Bulatov, Hubie Chen, and Víctor Dalmau, Learning intersection-closed classes with signatures, Theoret. Comput. Sci. 382 (2007), no. 3, 209–220. MR 2348225, DOI 10.1016/j.tcs.2007.03.039
Andrei Bulatov and Víctor Dalmau, A simple algorithm for Mal′tsev constraints, SIAM J. Comput. 36 (2006), no. 1, 16–27. MR 2231638, DOI 10.1137/050628957
Andrei Bulatov, Peter Jeavons, and Andrei Krokhin, Classifying the complexity of constraints using finite algebras, SIAM J. Comput. 34 (2005), no. 3, 720–742. MR 2137072, DOI 10.1137/S0097539700376676
Stanley Burris and H. P. Sankappanavar, A course in universal algebra, Graduate Texts in Mathematics, vol. 78, Springer-Verlag, New York-Berlin, 1981. MR 648287, DOI 10.1007/978-1-4613-8130-3
Hubie Chen, The expressive rate of constraints, Ann. Math. Artif. Intell. 44 (2005), no. 4, 341–352. MR 2185700, DOI 10.1007/s10472-005-7031-4
Víctor Dalmau. Computational complexity of problems over generalized formulas. Ph.D. thesis, Universitat Politécnica de Catalunya, 2000.
Víctor Dalmau. Generalized majority-minority operations are tractable. In LICS ’05: Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science (LICS’ 05), pages 438–447, Washington, DC, USA, 2005. IEEE Computer Society.
Víctor Dalmau and Peter Jeavons, Learnability of quantified formulas, Theoret. Comput. Sci. 306 (2003), no. 1-3, 485–511. MR 2000189, DOI 10.1016/S0304-3975(03)00342-6
Alan Day, A characterization of modularity for congruence lattices of algebras, Canad. Math. Bull. 12 (1969), 167–173. MR 248063, DOI 10.4153/CMB-1969-016-6
Tomás Feder and Moshe Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory, SIAM J. Comput. 28 (1999), no. 1, 57–104. MR 1630445, DOI 10.1137/S0097539794266766
Ralph Freese and Ralph McKenzie, Commutator theory for congruence modular varieties, London Mathematical Society Lecture Note Series, vol. 125, Cambridge University Press, Cambridge, 1987. MR 909290
O. C. García and W. Taylor, The lattice of interpretability types of varieties, Mem. Amer. Math. Soc. 50 (1984), no. 305, v+125. MR 749524, DOI 10.1090/memo/0305
H. Peter Gumm, Geometrical methods in congruence modular algebras, Mem. Amer. Math. Soc. 45 (1983), no. 286, viii+79. MR 714648, DOI 10.1090/memo/0286
Bradd Hart, Sergei Starchenko, and Matthew Valeriote, Vaught’s conjecture for varieties, Trans. Amer. Math. Soc. 342 (1994), no. 1, 173–196. MR 1191612, DOI 10.1090/S0002-9947-1994-1191612-0
David Hobby and Ralph McKenzie, The structure of finite algebras, Contemporary Mathematics, vol. 76, American Mathematical Society, Providence, RI, 1988. MR 958685, DOI 10.1090/conm/076
Paweł Idziak, Petar Marković, Ralph McKenzie, Matthew Valeriote, and Ross Willard. Tractability and learnability arising from algebras with few subpowers. In LICS ’07: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, pages 213–224, Washington, DC, USA, 2007. IEEE Computer Society.
PawełIdziak, Ralph McKenzie, and Matthew Valeriote, The structure of locally finite varieties with polynomially many models, J. Amer. Math. Soc. 22 (2009), no. 1, 119–165. MR 2449056, DOI 10.1090/S0894-0347-08-00614-0
Peter Jeavons, On the algebraic structure of combinatorial problems, Theoret. Comput. Sci. 200 (1998), no. 1-2, 185–204. MR 1625523, DOI 10.1016/S0304-3975(97)00230-2
Keith Kearnes and Ágnes Szendrei. Clones of parallelogram algebras. preprint, 2007.
Petar Marković and Ralph McKenzie, Few subpowers, congruence distributivity and near-unanimity terms, Algebra Universalis 58 (2008), no. 2, 119–128. MR 2386525, DOI 10.1007/s00012-008-2049-1
Ralph N. McKenzie, George F. McNulty, and Walter F. Taylor, Algebras, lattices, varieties. Vol. I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1987. MR 883644
Michael Morley, Categoricity in power, Trans. Amer. Math. Soc. 114 (1965), 514–538. MR 175782, DOI 10.1090/S0002-9947-1965-0175782-0
Luís Sequeira, Near-unanimity is decomposable, Algebra Universalis 50 (2003), no. 2, 157–164. MR 2037523, DOI 10.1007/s00012-003-1830-4
S. Shelah, Classification theory and the number of nonisomorphic models, 2nd ed., Studies in Logic and the Foundations of Mathematics, vol. 92, North-Holland Publishing Co., Amsterdam, 1990. MR 1083551